public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v15] Enforce foreign key correctly during cross-partition updates 13+ messages / 3 participants [nested] [flat]
* [PATCH v15] Enforce foreign key correctly during cross-partition updates @ 2022-03-18 10:01 Alvaro Herrera <[email protected]> 0 siblings, 0 replies; 13+ messages in thread From: Alvaro Herrera @ 2022-03-18 10:01 UTC (permalink / raw) When an update on a partitioned table referenced in foreign keys constraint causes a row to move from one partition to another, which is implemented by deleting the old row from the source leaf partition followed by inserting the new row into the destination leaf partition, firing the foreign key triggers on that delete event can result in surprising outcomes for those keys. For example, a given foreign key's delete trigger which implements the ON DELETE CASCADE clause of that key will delete any referencing rows when triggerred for that internal DELETE, although it should not, because the referenced row is simply being moved from one partition of the referenced root partitioned table into another, not being deleted from it. This commit teaches trigger.c to skip queuing such delete trigger events on the leaf partitions in favor of an UPDATE event fired on the root target relation. Doing so makes sense because both the old and the new tuple "logically" belong to the root relation. The after trigger event queuing interface now allows passing the source and the destination partitions of a particular cross-partition update when registering the update event for the root partitioned table. Along with the 2 ctids of the old and the new tuple, an after trigger event now also stores the OIDs of those partitions. The tuples fetched from the source and the destination partitions are converted into the root table format before they are passed to the trigger function. The implementation currently has a limitation that only the foreign keys pointing into the query's target relation are considered, not those of its sub-partitioned partitions. That seems like a reasonable limitation, because it sounds rare to have distinct foreign keys pointing into sub-partitioned partitions, but not into the root table. Author: Amit Langote --- doc/src/sgml/ref/update.sgml | 7 + src/backend/commands/trigger.c | 389 +++++++++++++++++++--- src/backend/executor/execMain.c | 86 ++++- src/backend/executor/execReplication.c | 5 +- src/backend/executor/nodeModifyTable.c | 155 ++++++++- src/backend/utils/adt/ri_triggers.c | 6 + src/include/commands/trigger.h | 8 +- src/include/executor/executor.h | 4 +- src/include/nodes/execnodes.h | 6 + src/test/regress/expected/foreign_key.out | 204 +++++++++++- src/test/regress/sql/foreign_key.sql | 135 +++++++- 11 files changed, 925 insertions(+), 80 deletions(-) diff --git a/doc/src/sgml/ref/update.sgml b/doc/src/sgml/ref/update.sgml index 3fa54e5f70..3ba13010e7 100644 --- a/doc/src/sgml/ref/update.sgml +++ b/doc/src/sgml/ref/update.sgml @@ -316,6 +316,13 @@ UPDATE <replaceable class="parameter">count</replaceable> partition (provided the foreign data wrapper supports tuple routing), they cannot be moved from a foreign-table partition to another partition. </para> + + <para> + An attempt of moving a row from one partition to another will fail if a + foreign key is found to directly reference a non-root partitioned table + in the partition tree, unless that table is also directly mentioned + in the <command>UPDATE</command>query. + </para> </refsect1> <refsect1> diff --git a/src/backend/commands/trigger.c b/src/backend/commands/trigger.c index e08bd9a370..a9aa043981 100644 --- a/src/backend/commands/trigger.c +++ b/src/backend/commands/trigger.c @@ -95,10 +95,13 @@ static HeapTuple ExecCallTriggerFunc(TriggerData *trigdata, Instrumentation *instr, MemoryContext per_tuple_context); static void AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, + ResultRelInfo *src_partinfo, + ResultRelInfo *dst_partinfo, int event, bool row_trigger, TupleTableSlot *oldtup, TupleTableSlot *newtup, List *recheckIndexes, Bitmapset *modifiedCols, - TransitionCaptureState *transition_capture); + TransitionCaptureState *transition_capture, + bool is_crosspart_update); static void AfterTriggerEnlargeQueryState(void); static bool before_stmt_triggers_fired(Oid relid, CmdType cmdType); @@ -2458,8 +2461,10 @@ ExecASInsertTriggers(EState *estate, ResultRelInfo *relinfo, TriggerDesc *trigdesc = relinfo->ri_TrigDesc; if (trigdesc && trigdesc->trig_insert_after_statement) - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_INSERT, - false, NULL, NULL, NIL, NULL, transition_capture); + AfterTriggerSaveEvent(estate, relinfo, NULL, NULL, + TRIGGER_EVENT_INSERT, + false, NULL, NULL, NIL, NULL, transition_capture, + false); } bool @@ -2547,10 +2552,12 @@ ExecARInsertTriggers(EState *estate, ResultRelInfo *relinfo, if ((trigdesc && trigdesc->trig_insert_after_row) || (transition_capture && transition_capture->tcs_insert_new_table)) - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_INSERT, + AfterTriggerSaveEvent(estate, relinfo, NULL, NULL, + TRIGGER_EVENT_INSERT, true, NULL, slot, recheckIndexes, NULL, - transition_capture); + transition_capture, + false); } bool @@ -2672,8 +2679,10 @@ ExecASDeleteTriggers(EState *estate, ResultRelInfo *relinfo, TriggerDesc *trigdesc = relinfo->ri_TrigDesc; if (trigdesc && trigdesc->trig_delete_after_statement) - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_DELETE, - false, NULL, NULL, NIL, NULL, transition_capture); + AfterTriggerSaveEvent(estate, relinfo, NULL, NULL, + TRIGGER_EVENT_DELETE, + false, NULL, NULL, NIL, NULL, transition_capture, + false); } /* @@ -2768,11 +2777,17 @@ ExecBRDeleteTriggers(EState *estate, EPQState *epqstate, return result; } +/* + * Note: is_crosspart_update must be true if the DELETE is being performed + * as part of a cross-partition update. + */ void -ExecARDeleteTriggers(EState *estate, ResultRelInfo *relinfo, +ExecARDeleteTriggers(EState *estate, + ResultRelInfo *relinfo, ItemPointer tupleid, HeapTuple fdw_trigtuple, - TransitionCaptureState *transition_capture) + TransitionCaptureState *transition_capture, + bool is_crosspart_update) { TriggerDesc *trigdesc = relinfo->ri_TrigDesc; @@ -2793,9 +2808,11 @@ ExecARDeleteTriggers(EState *estate, ResultRelInfo *relinfo, else ExecForceStoreHeapTuple(fdw_trigtuple, slot, false); - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_DELETE, + AfterTriggerSaveEvent(estate, relinfo, NULL, NULL, + TRIGGER_EVENT_DELETE, true, slot, NULL, NIL, NULL, - transition_capture); + transition_capture, + is_crosspart_update); } } @@ -2914,10 +2931,12 @@ ExecASUpdateTriggers(EState *estate, ResultRelInfo *relinfo, Assert(relinfo->ri_RootResultRelInfo == NULL); if (trigdesc && trigdesc->trig_update_after_statement) - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_UPDATE, + AfterTriggerSaveEvent(estate, relinfo, NULL, NULL, + TRIGGER_EVENT_UPDATE, false, NULL, NULL, NIL, ExecGetAllUpdatedCols(relinfo, estate), - transition_capture); + transition_capture, + false); } bool @@ -3052,13 +3071,26 @@ ExecBRUpdateTriggers(EState *estate, EPQState *epqstate, return true; } +/* + * Note: 'src_partinfo' and 'dst_partinfo', when non-NULL, refer to the source + * and destination partitions, respectively, of a cross-partition update of + * the root partitioned table mentioned in the query, given by 'relinfo'. + * 'tupleid' in that case refers to the ctid of the "old" tuple in the source + * partition, and 'newslot' contains the "new" tuple in the destination + * partition. This interface allows to support the requirements of + * ExecCrossPartitionUpdateForeignKey(); is_crosspart_update must be true in + * that case. + */ void ExecARUpdateTriggers(EState *estate, ResultRelInfo *relinfo, + ResultRelInfo *src_partinfo, + ResultRelInfo *dst_partinfo, ItemPointer tupleid, HeapTuple fdw_trigtuple, TupleTableSlot *newslot, List *recheckIndexes, - TransitionCaptureState *transition_capture) + TransitionCaptureState *transition_capture, + bool is_crosspart_update) { TriggerDesc *trigdesc = relinfo->ri_TrigDesc; @@ -3073,12 +3105,19 @@ ExecARUpdateTriggers(EState *estate, ResultRelInfo *relinfo, * separately for DELETE and INSERT to capture transition table rows. * In such case, either old tuple or new tuple can be NULL. */ - TupleTableSlot *oldslot = ExecGetTriggerOldSlot(estate, relinfo); + TupleTableSlot *oldslot; + ResultRelInfo *tupsrc; + + Assert((src_partinfo != NULL && dst_partinfo != NULL) || + !is_crosspart_update); + + tupsrc = src_partinfo ? src_partinfo : relinfo; + oldslot = ExecGetTriggerOldSlot(estate, tupsrc); if (fdw_trigtuple == NULL && ItemPointerIsValid(tupleid)) GetTupleForTrigger(estate, NULL, - relinfo, + tupsrc, tupleid, LockTupleExclusive, oldslot, @@ -3088,10 +3127,14 @@ ExecARUpdateTriggers(EState *estate, ResultRelInfo *relinfo, else ExecClearTuple(oldslot); - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_UPDATE, - true, oldslot, newslot, recheckIndexes, + AfterTriggerSaveEvent(estate, relinfo, + src_partinfo, dst_partinfo, + TRIGGER_EVENT_UPDATE, + true, + oldslot, newslot, recheckIndexes, ExecGetAllUpdatedCols(relinfo, estate), - transition_capture); + transition_capture, + is_crosspart_update); } } @@ -3214,8 +3257,11 @@ ExecASTruncateTriggers(EState *estate, ResultRelInfo *relinfo) TriggerDesc *trigdesc = relinfo->ri_TrigDesc; if (trigdesc && trigdesc->trig_truncate_after_statement) - AfterTriggerSaveEvent(estate, relinfo, TRIGGER_EVENT_TRUNCATE, - false, NULL, NULL, NIL, NULL, NULL); + AfterTriggerSaveEvent(estate, relinfo, + NULL, NULL, + TRIGGER_EVENT_TRUNCATE, + false, NULL, NULL, NIL, NULL, NULL, + false); } @@ -3496,9 +3542,9 @@ typedef SetConstraintStateData *SetConstraintState; * Per-trigger-event data * * The actual per-event data, AfterTriggerEventData, includes DONE/IN_PROGRESS - * status bits and up to two tuple CTIDs. Each event record also has an - * associated AfterTriggerSharedData that is shared across all instances of - * similar events within a "chunk". + * status bits, up to two tuple CTIDs, and optionally two OIDs of partitions + * Each event record also has an associated AfterTriggerSharedData that is + * shared across all instances of similar events within a "chunk". * * For row-level triggers, we arrange not to waste storage on unneeded ctid * fields. Updates of regular tables use two; inserts and deletes of regular @@ -3509,6 +3555,10 @@ typedef SetConstraintStateData *SetConstraintState; * tuple(s). This permits storing tuples once regardless of the number of * row-level triggers on a foreign table. * + * When updates move tuples in partitioned tables to different partitions, + * the OIDs of both partitions are stored too, so that the tuples can be + * fetched. + * * Note that we need triggers on foreign tables to be fired in exactly the * order they were queued, so that the tuples come out of the tuplestore in * the right order. To ensure that, we forbid deferrable (constraint) @@ -3531,16 +3581,16 @@ typedef SetConstraintStateData *SetConstraintState; */ typedef uint32 TriggerFlags; -#define AFTER_TRIGGER_OFFSET 0x0FFFFFFF /* must be low-order bits */ -#define AFTER_TRIGGER_DONE 0x10000000 -#define AFTER_TRIGGER_IN_PROGRESS 0x20000000 +#define AFTER_TRIGGER_OFFSET 0x07FFFFFF /* must be low-order bits */ +#define AFTER_TRIGGER_DONE 0x80000000 +#define AFTER_TRIGGER_IN_PROGRESS 0x40000000 /* bits describing the size and tuple sources of this event */ #define AFTER_TRIGGER_FDW_REUSE 0x00000000 -#define AFTER_TRIGGER_FDW_FETCH 0x80000000 -#define AFTER_TRIGGER_1CTID 0x40000000 -#define AFTER_TRIGGER_2CTID 0xC0000000 -#define AFTER_TRIGGER_TUP_BITS 0xC0000000 - +#define AFTER_TRIGGER_FDW_FETCH 0x20000000 +#define AFTER_TRIGGER_1CTID 0x10000000 +#define AFTER_TRIGGER_2CTID 0x30000000 +#define AFTER_TRIGGER_CP_UPDATE 0x08000000 +#define AFTER_TRIGGER_TUP_BITS 0x38000000 typedef struct AfterTriggerSharedData *AfterTriggerShared; typedef struct AfterTriggerSharedData @@ -3560,8 +3610,24 @@ typedef struct AfterTriggerEventData TriggerFlags ate_flags; /* status bits and offset to shared data */ ItemPointerData ate_ctid1; /* inserted, deleted, or old updated tuple */ ItemPointerData ate_ctid2; /* new updated tuple */ + + /* + * During a cross-partition update of a partitioned table, we also store + * the OIDs of source and destination partitions that are needed to fetch + * the old (ctid1) and the new tuple (ctid2) from, respectively. + */ + Oid ate_src_part; + Oid ate_dst_part; } AfterTriggerEventData; +/* AfterTriggerEventData, minus ate_src_part, ate_dst_part */ +typedef struct AfterTriggerEventDataNoOids +{ + TriggerFlags ate_flags; + ItemPointerData ate_ctid1; + ItemPointerData ate_ctid2; +} AfterTriggerEventDataNoOids; + /* AfterTriggerEventData, minus ate_ctid2 */ typedef struct AfterTriggerEventDataOneCtid { @@ -3576,11 +3642,13 @@ typedef struct AfterTriggerEventDataZeroCtids } AfterTriggerEventDataZeroCtids; #define SizeofTriggerEvent(evt) \ - (((evt)->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_2CTID ? \ + (((evt)->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_CP_UPDATE ? \ sizeof(AfterTriggerEventData) : \ - ((evt)->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_1CTID ? \ - sizeof(AfterTriggerEventDataOneCtid) : \ - sizeof(AfterTriggerEventDataZeroCtids)) + (((evt)->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_2CTID ? \ + sizeof(AfterTriggerEventDataNoOids) : \ + (((evt)->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_1CTID ? \ + sizeof(AfterTriggerEventDataOneCtid) : \ + sizeof(AfterTriggerEventDataZeroCtids)))) #define GetTriggerSharedData(evt) \ ((AfterTriggerShared) ((char *) (evt) + ((evt)->ate_flags & AFTER_TRIGGER_OFFSET))) @@ -3762,6 +3830,8 @@ static AfterTriggersData afterTriggers; static void AfterTriggerExecute(EState *estate, AfterTriggerEvent event, ResultRelInfo *relInfo, + ResultRelInfo *src_relInfo, + ResultRelInfo *dst_relInfo, TriggerDesc *trigdesc, FmgrInfo *finfo, Instrumentation *instr, @@ -4096,8 +4166,16 @@ afterTriggerDeleteHeadEventChunk(AfterTriggersQueryData *qs) * fmgr lookup cache space at the caller level. (For triggers fired at * the end of a query, we can even piggyback on the executor's state.) * + * When fired for a cross-partition update of a partitioned table, the old + * tuple is fetched using 'src_relInfo' (the source leaf partition) and + * the new tuple using 'dst_relInfo' (the destination leaf partition), though + * both are converted into the root partitioned table's format before passing + * to the trigger function. + * * event: event currently being fired. - * rel: open relation for event. + * relInfo: result relation for event. + * src_relInfo: source partition of a cross-partition update + * dst_relInfo: its destination partition * trigdesc: working copy of rel's trigger info. * finfo: array of fmgr lookup cache entries (one per trigger in trigdesc). * instr: array of EXPLAIN ANALYZE instrumentation nodes (one per trigger), @@ -4111,6 +4189,8 @@ static void AfterTriggerExecute(EState *estate, AfterTriggerEvent event, ResultRelInfo *relInfo, + ResultRelInfo *src_relInfo, + ResultRelInfo *dst_relInfo, TriggerDesc *trigdesc, FmgrInfo *finfo, Instrumentation *instr, MemoryContext per_tuple_context, @@ -4118,6 +4198,8 @@ AfterTriggerExecute(EState *estate, TupleTableSlot *trig_tuple_slot2) { Relation rel = relInfo->ri_RelationDesc; + Relation src_rel = src_relInfo->ri_RelationDesc; + Relation dst_rel = dst_relInfo->ri_RelationDesc; AfterTriggerShared evtshared = GetTriggerSharedData(event); Oid tgoid = evtshared->ats_tgoid; TriggerData LocTriggerData = {0}; @@ -4198,12 +4280,35 @@ AfterTriggerExecute(EState *estate, default: if (ItemPointerIsValid(&(event->ate_ctid1))) { - LocTriggerData.tg_trigslot = ExecGetTriggerOldSlot(estate, relInfo); + TupleTableSlot *src_slot = ExecGetTriggerOldSlot(estate, + src_relInfo); - if (!table_tuple_fetch_row_version(rel, &(event->ate_ctid1), + if (!table_tuple_fetch_row_version(src_rel, + &(event->ate_ctid1), SnapshotAny, - LocTriggerData.tg_trigslot)) + src_slot)) elog(ERROR, "failed to fetch tuple1 for AFTER trigger"); + + /* + * Store the tuple fetched from the source partition into the + * target (root partitioned) table slot, converting if needed. + */ + if (src_relInfo != relInfo) + { + TupleConversionMap *map = ExecGetChildToRootMap(src_relInfo); + + LocTriggerData.tg_trigslot = ExecGetTriggerOldSlot(estate, relInfo); + if (map) + { + execute_attr_map_slot(map->attrMap, + src_slot, + LocTriggerData.tg_trigslot); + } + else + ExecCopySlot(LocTriggerData.tg_trigslot, src_slot); + } + else + LocTriggerData.tg_trigslot = src_slot; LocTriggerData.tg_trigtuple = ExecFetchSlotHeapTuple(LocTriggerData.tg_trigslot, false, &should_free_trig); } @@ -4213,16 +4318,40 @@ AfterTriggerExecute(EState *estate, } /* don't touch ctid2 if not there */ - if ((event->ate_flags & AFTER_TRIGGER_TUP_BITS) == - AFTER_TRIGGER_2CTID && + if (((event->ate_flags & AFTER_TRIGGER_TUP_BITS) == AFTER_TRIGGER_2CTID || + (event->ate_flags & AFTER_TRIGGER_CP_UPDATE)) && ItemPointerIsValid(&(event->ate_ctid2))) { - LocTriggerData.tg_newslot = ExecGetTriggerNewSlot(estate, relInfo); + TupleTableSlot *dst_slot = ExecGetTriggerNewSlot(estate, + dst_relInfo); - if (!table_tuple_fetch_row_version(rel, &(event->ate_ctid2), + if (!table_tuple_fetch_row_version(dst_rel, + &(event->ate_ctid2), SnapshotAny, - LocTriggerData.tg_newslot)) + dst_slot)) elog(ERROR, "failed to fetch tuple2 for AFTER trigger"); + + /* + * Store the tuple fetched from the destination partition into + * the target (root partitioned) table slot, converting if + * needed. + */ + if (dst_relInfo != relInfo) + { + TupleConversionMap *map = ExecGetChildToRootMap(dst_relInfo); + + LocTriggerData.tg_newslot = ExecGetTriggerNewSlot(estate, relInfo); + if (map) + { + execute_attr_map_slot(map->attrMap, + dst_slot, + LocTriggerData.tg_newslot); + } + else + ExecCopySlot(LocTriggerData.tg_newslot, dst_slot); + } + else + LocTriggerData.tg_newslot = dst_slot; LocTriggerData.tg_newtuple = ExecFetchSlotHeapTuple(LocTriggerData.tg_newslot, false, &should_free_new); } @@ -4451,13 +4580,17 @@ afterTriggerInvokeEvents(AfterTriggerEventList *events, if ((event->ate_flags & AFTER_TRIGGER_IN_PROGRESS) && evtshared->ats_firing_id == firing_id) { + ResultRelInfo *src_rInfo, + *dst_rInfo; + /* * So let's fire it... but first, find the correct relation if * this is not the same relation as before. */ if (rel == NULL || RelationGetRelid(rel) != evtshared->ats_relid) { - rInfo = ExecGetTriggerResultRel(estate, evtshared->ats_relid); + rInfo = ExecGetTriggerResultRel(estate, evtshared->ats_relid, + NULL); rel = rInfo->ri_RelationDesc; /* Catch calls with insufficient relcache refcounting */ Assert(!RelationHasReferenceCountZero(rel)); @@ -4482,12 +4615,33 @@ afterTriggerInvokeEvents(AfterTriggerEventList *events, evtshared->ats_relid); } + /* + * Look up source and destination partition result rels of a + * cross-partition update event. + */ + if ((event->ate_flags & AFTER_TRIGGER_TUP_BITS) == + AFTER_TRIGGER_CP_UPDATE) + { + Assert(OidIsValid(event->ate_src_part) && + OidIsValid(event->ate_dst_part)); + src_rInfo = ExecGetTriggerResultRel(estate, + event->ate_src_part, + rInfo); + dst_rInfo = ExecGetTriggerResultRel(estate, + event->ate_dst_part, + rInfo); + } + else + src_rInfo = dst_rInfo = rInfo; + /* * Fire it. Note that the AFTER_TRIGGER_IN_PROGRESS flag is * still set, so recursive examinations of the event list * won't try to re-fire it. */ - AfterTriggerExecute(estate, event, rInfo, trigdesc, finfo, instr, + AfterTriggerExecute(estate, event, rInfo, + src_rInfo, dst_rInfo, + trigdesc, finfo, instr, per_tuple_context, slot1, slot2); /* @@ -5767,14 +5921,35 @@ AfterTriggerPendingOnRel(Oid relid) * Transition tuplestores are built now, rather than when events are pulled * off of the queue because AFTER ROW triggers are allowed to select from the * transition tables for the statement. + * + * This contains special support to queue the update events for the case where + * a partitioned table undergoing a cross-partition update may have foreign + * keys pointing into it. Normally, a partitioned table's row triggers are + * not fired because the leaf partition(s) which are modified as a result of + * the operation on the partitioned table contain the same triggers which are + * fired instead. But that general scheme can cause problematic behavior with + * foreign key triggers during cross-partition updates, which are implemented + * as DELETE on the source partition followed by INSERT into the destination + * partition. Specifically, firing DELETE triggers would lead to the wrong + * foreign key action to be enforced considering that the original command is + * UPDATE; in this case, this function is called with relinfo as the + * partitioned table, and src_partinfo and dst_partinfo referring to the + * source and target leaf partitions, respectively. + * + * is_crosspart_update is true either when a DELETE event is fired on the + * source partition (which is to be ignored) or an UPDATE event is fired on + * the root partitioned table. * ---------- */ static void AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, + ResultRelInfo *src_partinfo, + ResultRelInfo *dst_partinfo, int event, bool row_trigger, TupleTableSlot *oldslot, TupleTableSlot *newslot, List *recheckIndexes, Bitmapset *modifiedCols, - TransitionCaptureState *transition_capture) + TransitionCaptureState *transition_capture, + bool is_crosspart_update) { Relation rel = relinfo->ri_RelationDesc; TriggerDesc *trigdesc = relinfo->ri_TrigDesc; @@ -5854,6 +6029,19 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, return; } + /* + * We normally don't see partitioned tables here for row level triggers + * except in the special case of a cross-partition update. In that case, + * nodeModifyTable.c:ExecCrossPartitionUpdateForeignKey() calls here to + * queue an update event on the root target partitioned table, also + * passing the source and destination partitions and their tuples. + */ + Assert(!row_trigger || + rel->rd_rel->relkind != RELKIND_PARTITIONED_TABLE || + (is_crosspart_update && + TRIGGER_FIRED_BY_UPDATE(event) && + src_partinfo != NULL && dst_partinfo != NULL)); + /* * Validate the event code and collect the associated tuple CTIDs. * @@ -5914,6 +6102,19 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, Assert(newslot != NULL); ItemPointerCopy(&(oldslot->tts_tid), &(new_event.ate_ctid1)); ItemPointerCopy(&(newslot->tts_tid), &(new_event.ate_ctid2)); + + /* + * Also remember the OIDs of partitions to fetch these tuples + * out of later in AfterTriggerExecute(). + */ + if (rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE) + { + Assert(src_partinfo != NULL && dst_partinfo != NULL); + new_event.ate_src_part = + RelationGetRelid(src_partinfo->ri_RelationDesc); + new_event.ate_dst_part = + RelationGetRelid(dst_partinfo->ri_RelationDesc); + } } else { @@ -5938,13 +6139,53 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, break; } + /* Determine flags */ if (!(relkind == RELKIND_FOREIGN_TABLE && row_trigger)) - new_event.ate_flags = (row_trigger && event == TRIGGER_EVENT_UPDATE) ? - AFTER_TRIGGER_2CTID : AFTER_TRIGGER_1CTID; + { + if (row_trigger && event == TRIGGER_EVENT_UPDATE) + { + if (relkind == RELKIND_PARTITIONED_TABLE) + new_event.ate_flags = AFTER_TRIGGER_CP_UPDATE; + else + new_event.ate_flags = AFTER_TRIGGER_2CTID; + } + else + new_event.ate_flags = AFTER_TRIGGER_1CTID; + } + /* else, we'll initialize ate_flags for each trigger */ tgtype_level = (row_trigger ? TRIGGER_TYPE_ROW : TRIGGER_TYPE_STATEMENT); + /* + * Must convert/copy the source and destination partition tuples into the + * root partitioned table's format/slot, because the processing in the + * loop below expects both oldslot and newslot tuples to be in that form. + */ + if (row_trigger && rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE) + { + TupleTableSlot *rootslot; + TupleConversionMap *map; + + rootslot = ExecGetTriggerOldSlot(estate, relinfo); + map = ExecGetChildToRootMap(src_partinfo); + if (map) + oldslot = execute_attr_map_slot(map->attrMap, + oldslot, + rootslot); + else + oldslot = ExecCopySlot(rootslot, oldslot); + + rootslot = ExecGetTriggerNewSlot(estate, relinfo); + map = ExecGetChildToRootMap(dst_partinfo); + if (map) + newslot = execute_attr_map_slot(map->attrMap, + newslot, + rootslot); + else + newslot = ExecCopySlot(rootslot, newslot); + } + for (i = 0; i < trigdesc->numtriggers; i++) { Trigger *trigger = &trigdesc->triggers[i]; @@ -5973,13 +6214,30 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, /* * If the trigger is a foreign key enforcement trigger, there are * certain cases where we can skip queueing the event because we can - * tell by inspection that the FK constraint will still pass. + * tell by inspection that the FK constraint will still pass. There + * are also some cases during cross-partition updates of a partitioned + * table where queuing the event can be skipped. */ if (TRIGGER_FIRED_BY_UPDATE(event) || TRIGGER_FIRED_BY_DELETE(event)) { switch (RI_FKey_trigger_type(trigger->tgfoid)) { case RI_TRIGGER_PK: + + /* + * For cross-partitioned updates of partitioned PK table, + * skip the event fired by the component delete on the + * source leaf partition unless the constraint originates + * in the partition itself (!tgisclone), because the + * update event that will be fired on the root + * (partitioned) target table will be used to perform the + * necessary foreign key enforcement action. + */ + if (is_crosspart_update && + TRIGGER_FIRED_BY_DELETE(event) && + trigger->tgisclone) + continue; + /* Update or delete on trigger's PK table */ if (!RI_FKey_pk_upd_check_required(trigger, rel, oldslot, newslot)) @@ -5990,8 +6248,20 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, break; case RI_TRIGGER_FK: - /* Update on trigger's FK table */ - if (!RI_FKey_fk_upd_check_required(trigger, rel, + + /* + * Update on trigger's FK table. We can skip the update + * event fired on a partitioned table during a + * cross-partition of that table, because the insert event + * that is fired on the destination leaf partition would + * suffice to perform the necessary foreign key check. + * Moreover, RI_FKey_fk_upd_check_required() expects to be + * passed a tuple that contains system attributes, most of + * which are not present in the virtual slot belonging to + * a partitioned table. + */ + if (rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE || + !RI_FKey_fk_upd_check_required(trigger, rel, oldslot, newslot)) { /* skip queuing this event */ @@ -6000,7 +6270,18 @@ AfterTriggerSaveEvent(EState *estate, ResultRelInfo *relinfo, break; case RI_TRIGGER_NONE: - /* Not an FK trigger */ + + /* + * Not an FK trigger. No need to queue the update event + * fired during a cross-partitioned update of a + * partitioned table, because the same row trigger must be + * present in the leaf partition(s) that are affected as + * part of this update and the events fired on them are + * queued instead. + */ + if (row_trigger && + rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE) + continue; break; } } diff --git a/src/backend/executor/execMain.c b/src/backend/executor/execMain.c index 549d9eb696..473d2e00a2 100644 --- a/src/backend/executor/execMain.c +++ b/src/backend/executor/execMain.c @@ -44,6 +44,7 @@ #include "access/transam.h" #include "access/xact.h" #include "catalog/namespace.h" +#include "catalog/partition.h" #include "catalog/pg_publication.h" #include "commands/matview.h" #include "commands/trigger.h" @@ -1279,7 +1280,8 @@ InitResultRelInfo(ResultRelInfo *resultRelInfo, * in es_trig_target_relations. */ ResultRelInfo * -ExecGetTriggerResultRel(EState *estate, Oid relid) +ExecGetTriggerResultRel(EState *estate, Oid relid, + ResultRelInfo *rootRelInfo) { ResultRelInfo *rInfo; ListCell *l; @@ -1330,7 +1332,7 @@ ExecGetTriggerResultRel(EState *estate, Oid relid) InitResultRelInfo(rInfo, rel, 0, /* dummy rangetable index */ - NULL, + rootRelInfo, estate->es_instrument); estate->es_trig_target_relations = lappend(estate->es_trig_target_relations, rInfo); @@ -1344,6 +1346,69 @@ ExecGetTriggerResultRel(EState *estate, Oid relid) return rInfo; } +/* + * Return the ancestor relations of a given leaf partition result relation + * up to and including the query's root target relation. + * + * These work much like the ones opened by ExecGetTriggerResultRel, except + * that we need to keep them in a separate list. + * + * These are closed by ExecCloseResultRelations. + */ +List * +ExecGetAncestorResultRels(EState *estate, ResultRelInfo *resultRelInfo) +{ + ResultRelInfo *rootRelInfo = resultRelInfo->ri_RootResultRelInfo; + Relation partRel = resultRelInfo->ri_RelationDesc; + Oid rootRelOid; + + if (!partRel->rd_rel->relispartition) + elog(ERROR, "cannot find ancestors of a non-partition result relation"); + Assert(rootRelInfo != NULL); + rootRelOid = RelationGetRelid(rootRelInfo->ri_RelationDesc); + if (resultRelInfo->ri_ancestorResultRels == NIL) + { + ListCell *lc; + List *oids = get_partition_ancestors(RelationGetRelid(partRel)); + List *ancResultRels = NIL; + + foreach(lc, oids) + { + Oid ancOid = lfirst_oid(lc); + Relation ancRel; + ResultRelInfo *rInfo; + + /* + * Ignore the root ancestor here, and use ri_RootResultRelInfo + * (below) for it instead. Also, we stop climbing up the + * hierarchy when we find the table that was mentioned in the + * query. + */ + if (ancOid == rootRelOid) + break; + + /* + * All ancestors up to the root target relation must have been + * locked by the planner or AcquireExecutorLocks(). + */ + ancRel = table_open(ancOid, NoLock); + rInfo = makeNode(ResultRelInfo); + + /* dummy rangetable index */ + InitResultRelInfo(rInfo, ancRel, 0, NULL, + estate->es_instrument); + ancResultRels = lappend(ancResultRels, rInfo); + } + ancResultRels = lappend(ancResultRels, rootRelInfo); + resultRelInfo->ri_ancestorResultRels = ancResultRels; + } + + /* We must have found some ancestor */ + Assert(resultRelInfo->ri_ancestorResultRels != NIL); + + return resultRelInfo->ri_ancestorResultRels; +} + /* ---------------------------------------------------------------- * ExecPostprocessPlan * @@ -1443,12 +1508,29 @@ ExecCloseResultRelations(EState *estate) /* * close indexes of result relation(s) if any. (Rels themselves are * closed in ExecCloseRangeTableRelations()) + * + * In addition, close the stub RTs that may be in each resultrel's + * ri_ancestorResultRels. */ foreach(l, estate->es_opened_result_relations) { ResultRelInfo *resultRelInfo = lfirst(l); + ListCell *lc; ExecCloseIndices(resultRelInfo); + foreach(lc, resultRelInfo->ri_ancestorResultRels) + { + ResultRelInfo *rInfo = lfirst(lc); + + /* + * Ancestors with RTI > 0 (should only be the root ancestor) are + * closed by ExecCloseRangeTableRelations. + */ + if (rInfo->ri_RangeTableIndex > 0) + continue; + + table_close(rInfo->ri_RelationDesc, NoLock); + } } /* Close any relations that have been opened by ExecGetTriggerResultRel(). */ diff --git a/src/backend/executor/execReplication.c b/src/backend/executor/execReplication.c index 09f78f2244..13328141e2 100644 --- a/src/backend/executor/execReplication.c +++ b/src/backend/executor/execReplication.c @@ -517,8 +517,9 @@ ExecSimpleRelationUpdate(ResultRelInfo *resultRelInfo, /* AFTER ROW UPDATE Triggers */ ExecARUpdateTriggers(estate, resultRelInfo, + NULL, NULL, tid, NULL, slot, - recheckIndexes, NULL); + recheckIndexes, NULL, false); list_free(recheckIndexes); } @@ -557,7 +558,7 @@ ExecSimpleRelationDelete(ResultRelInfo *resultRelInfo, /* AFTER ROW DELETE Triggers */ ExecARDeleteTriggers(estate, resultRelInfo, - tid, NULL, NULL); + tid, NULL, NULL, false); } } diff --git a/src/backend/executor/nodeModifyTable.c b/src/backend/executor/nodeModifyTable.c index 6239abae90..46f7ba6d84 100644 --- a/src/backend/executor/nodeModifyTable.c +++ b/src/backend/executor/nodeModifyTable.c @@ -122,6 +122,12 @@ static void ExecBatchInsert(ModifyTableState *mtstate, int numSlots, EState *estate, bool canSetTag); +static void ExecCrossPartitionUpdateForeignKey(ModifyTableContext *context, + ResultRelInfo *sourcePartInfo, + ResultRelInfo *destPartInfo, + ItemPointer tupleid, + TupleTableSlot *oldslot, + TupleTableSlot *newslot); static bool ExecOnConflictUpdate(ModifyTableContext *context, ResultRelInfo *resultRelInfo, ItemPointer conflictTid, @@ -635,6 +641,9 @@ ExecGetUpdateNewTuple(ResultRelInfo *relinfo, * slot contains the new tuple value to be stored. * * Returns RETURNING result if any, otherwise NULL. + * *inserted_tuple is the tuple that's effectively inserted; + * *inserted_destrel is the relation where it was inserted. + * These are only set on success. * * This may change the currently active tuple conversion map in * mtstate->mt_transition_capture, so the callers must take care to @@ -645,7 +654,9 @@ static TupleTableSlot * ExecInsert(ModifyTableContext *context, ResultRelInfo *resultRelInfo, TupleTableSlot *slot, - bool canSetTag) + bool canSetTag, + TupleTableSlot **inserted_tuple, + ResultRelInfo **insert_destrel) { ModifyTableState *mtstate = context->mtstate; EState *estate = context->estate; @@ -1008,11 +1019,14 @@ ExecInsert(ModifyTableContext *context, if (mtstate->operation == CMD_UPDATE && mtstate->mt_transition_capture && mtstate->mt_transition_capture->tcs_update_new_table) { - ExecARUpdateTriggers(estate, resultRelInfo, NULL, + ExecARUpdateTriggers(estate, resultRelInfo, + NULL, NULL, + NULL, NULL, slot, NULL, - mtstate->mt_transition_capture); + mtstate->mt_transition_capture, + false); /* * We've already captured the NEW TABLE row, so make sure any AR @@ -1046,6 +1060,11 @@ ExecInsert(ModifyTableContext *context, if (resultRelInfo->ri_projectReturning) result = ExecProcessReturning(resultRelInfo, slot, planSlot); + if (inserted_tuple) + *inserted_tuple = slot; + if (insert_destrel) + *insert_destrel = resultRelInfo; + return result; } @@ -1160,7 +1179,7 @@ ExecDeleteAct(ModifyTableContext *context, ResultRelInfo *resultRelInfo, */ static void ExecDeleteEpilogue(ModifyTableContext *context, ResultRelInfo *resultRelInfo, - ItemPointer tupleid, HeapTuple oldtuple) + ItemPointer tupleid, HeapTuple oldtuple, bool changingPart) { ModifyTableState *mtstate = context->mtstate; EState *estate = context->estate; @@ -1176,8 +1195,11 @@ ExecDeleteEpilogue(ModifyTableContext *context, ResultRelInfo *resultRelInfo, if (mtstate->operation == CMD_UPDATE && mtstate->mt_transition_capture && mtstate->mt_transition_capture->tcs_update_old_table) { - ExecARUpdateTriggers(estate, resultRelInfo, tupleid, oldtuple, - NULL, NULL, mtstate->mt_transition_capture); + ExecARUpdateTriggers(estate, resultRelInfo, + NULL, NULL, + tupleid, oldtuple, + NULL, NULL, mtstate->mt_transition_capture, + false); /* * We've already captured the NEW TABLE row, so make sure any AR @@ -1188,7 +1210,7 @@ ExecDeleteEpilogue(ModifyTableContext *context, ResultRelInfo *resultRelInfo, /* AFTER ROW DELETE Triggers */ ExecARDeleteTriggers(estate, resultRelInfo, tupleid, oldtuple, - ar_delete_trig_tcs); + ar_delete_trig_tcs, changingPart); } /* ---------------------------------------------------------------- @@ -1457,7 +1479,7 @@ ldelete:; if (tupleDeleted) *tupleDeleted = true; - ExecDeleteEpilogue(context, resultRelInfo, tupleid, oldtuple); + ExecDeleteEpilogue(context, resultRelInfo, tupleid, oldtuple, changingPart); /* Process RETURNING if present and if requested */ if (processReturning && resultRelInfo->ri_projectReturning) @@ -1517,8 +1539,8 @@ ldelete:; * for the caller. * * False is returned if the tuple we're trying to move is found to have been - * concurrently updated. In that case, the caller must to check if the - * updated tuple that's returned in *retry_slot still needs to be re-routed, + * concurrently updated. In that case, the caller must check if the + * updated tuple (in updateCxt->cpUpdateRetrySlot) still needs to be re-routed, * and call this function again or perform a regular update accordingly. */ static bool @@ -1526,7 +1548,10 @@ ExecCrossPartitionUpdate(ModifyTableContext *context, ResultRelInfo *resultRelInfo, ItemPointer tupleid, HeapTuple oldtuple, TupleTableSlot *slot, - bool canSetTag, UpdateContext *updateCxt) + bool canSetTag, + UpdateContext *updateCxt, + TupleTableSlot **inserted_tuple, + ResultRelInfo **insert_destrel) { ModifyTableState *mtstate = context->mtstate; EState *estate = mtstate->ps.state; @@ -1652,7 +1677,8 @@ ExecCrossPartitionUpdate(ModifyTableContext *context, /* Tuple routing starts from the root table. */ context->cpUpdateReturningSlot = - ExecInsert(context, mtstate->rootResultRelInfo, slot, canSetTag); + ExecInsert(context, mtstate->rootResultRelInfo, slot, canSetTag, + inserted_tuple, insert_destrel); /* * Reset the transition state that may possibly have been written by @@ -1793,6 +1819,9 @@ lreplace:; */ if (partition_constraint_failed) { + TupleTableSlot *inserted_tuple; + ResultRelInfo *insert_destrel; + /* * ExecCrossPartitionUpdate will first DELETE the row from the * partition it's currently in and then insert it back into the root @@ -1801,11 +1830,37 @@ lreplace:; */ if (ExecCrossPartitionUpdate(context, resultRelInfo, tupleid, oldtuple, slot, - canSetTag, updateCxt)) + canSetTag, updateCxt, + &inserted_tuple, + &insert_destrel)) { /* success! */ updateCxt->updated = true; updateCxt->crossPartUpdate = true; + + /* + * If the partitioned table being updated is referenced in foreign + * keys, queue up trigger events to check that none of them were + * violated. No special treatment is needed in + * non-cross-partition update situations, because the leaf + * partition's AR update triggers will take care of that. During + * cross-partition updates implemented as delete on the source + * partition followed by insert on the destination partition, + * AR-UPDATE triggers of the root table (that is, the table + * mentioned in the query) must be fired. + * + * NULL insert_destrel means that the move failed to occur, that + * is, the update failed, so no need to anything in that case. + */ + if (insert_destrel && + resultRelInfo->ri_TrigDesc && + resultRelInfo->ri_TrigDesc->trig_update_after_row) + ExecCrossPartitionUpdateForeignKey(context, + resultRelInfo, + insert_destrel, + tupleid, slot, + inserted_tuple); + return TM_Ok; } @@ -1871,11 +1926,13 @@ ExecUpdateEpilogue(ModifyTableContext *context, UpdateContext *updateCxt, /* AFTER ROW UPDATE Triggers */ ExecARUpdateTriggers(context->estate, resultRelInfo, + NULL, NULL, tupleid, oldtuple, slot, recheckIndexes, mtstate->operation == CMD_INSERT ? mtstate->mt_oc_transition_capture : - mtstate->mt_transition_capture); + mtstate->mt_transition_capture, + false); /* * Check any WITH CHECK OPTION constraints from parent views. We are @@ -1891,6 +1948,74 @@ ExecUpdateEpilogue(ModifyTableContext *context, UpdateContext *updateCxt, slot, context->estate); } +/* + * Queues up an update event using the target root partitioned table's + * trigger to check that a cross-partition update hasn't broken any foreign + * keys pointing into it. + */ +static void +ExecCrossPartitionUpdateForeignKey(ModifyTableContext *context, + ResultRelInfo *sourcePartInfo, + ResultRelInfo *destPartInfo, + ItemPointer tupleid, + TupleTableSlot *oldslot, + TupleTableSlot *newslot) +{ + ListCell *lc; + ResultRelInfo *rootRelInfo; + List *ancestorRels; + + rootRelInfo = sourcePartInfo->ri_RootResultRelInfo; + ancestorRels = ExecGetAncestorResultRels(context->estate, sourcePartInfo); + + /* + * For any foreign keys that point directly into a non-root ancestors of + * the source partition, we can in theory fire an update event to enforce + * those constraints using their triggers, if we could tell that both the + * source and the destination partitions are under the same ancestor. But + * for now, we simply report an error that those cannot be enforced. + */ + foreach(lc, ancestorRels) + { + ResultRelInfo *rInfo = lfirst(lc); + TriggerDesc *trigdesc = rInfo->ri_TrigDesc; + bool has_noncloned_fkey = false; + + /* Ignore the root ancestor, because ...?? */ + if (rInfo == rootRelInfo) + continue; + + if (trigdesc && trigdesc->trig_update_after_row) + { + for (int i = 0; i < trigdesc->numtriggers; i++) + { + Trigger *trig = &trigdesc->triggers[i]; + + if (!trig->tgisclone && + RI_FKey_trigger_type(trig->tgfoid) == RI_TRIGGER_PK) + { + has_noncloned_fkey = true; + break; + } + } + } + + if (has_noncloned_fkey) + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("cannot move tuple across partitions when a non-root ancestor of the source partition is directly referenced in a foreign key"), + errdetail("A foreign key points to ancestor \"%s\", but not the root ancestor \"%s\".", + RelationGetRelationName(rInfo->ri_RelationDesc), + RelationGetRelationName(rootRelInfo->ri_RelationDesc)), + errhint("Consider defining the foreign key on \"%s\".", + RelationGetRelationName(rootRelInfo->ri_RelationDesc)))); + } + + /* Perform the root table's triggers. */ + ExecARUpdateTriggers(context->estate, + rootRelInfo, sourcePartInfo, destPartInfo, + tupleid, NULL, newslot, NIL, NULL, true); +} /* ---------------------------------------------------------------- * ExecUpdate @@ -2745,7 +2870,7 @@ ExecModifyTable(PlanState *pstate) ExecInitInsertProjection(node, resultRelInfo); slot = ExecGetInsertNewTuple(resultRelInfo, planSlot); slot = ExecInsert(&context, resultRelInfo, slot, - node->canSetTag); + node->canSetTag, NULL, NULL); break; case CMD_UPDATE: diff --git a/src/backend/utils/adt/ri_triggers.c b/src/backend/utils/adt/ri_triggers.c index c95cd32402..01d4c22cfc 100644 --- a/src/backend/utils/adt/ri_triggers.c +++ b/src/backend/utils/adt/ri_triggers.c @@ -1261,6 +1261,12 @@ RI_FKey_fk_upd_check_required(Trigger *trigger, Relation fk_rel, TransactionId xmin; bool isnull; + /* + * AfterTriggerSaveEvent() handles things such that this function is never + * called for partitioned tables. + */ + Assert(fk_rel->rd_rel->relkind != RELKIND_PARTITIONED_TABLE); + riinfo = ri_FetchConstraintInfo(trigger, fk_rel, false); ri_nullcheck = ri_NullCheck(RelationGetDescr(fk_rel), newslot, riinfo, false); diff --git a/src/include/commands/trigger.h b/src/include/commands/trigger.h index e1271420e5..66bf6c16e3 100644 --- a/src/include/commands/trigger.h +++ b/src/include/commands/trigger.h @@ -214,7 +214,8 @@ extern void ExecARDeleteTriggers(EState *estate, ResultRelInfo *relinfo, ItemPointer tupleid, HeapTuple fdw_trigtuple, - TransitionCaptureState *transition_capture); + TransitionCaptureState *transition_capture, + bool is_crosspart_update); extern bool ExecIRDeleteTriggers(EState *estate, ResultRelInfo *relinfo, HeapTuple trigtuple); @@ -231,11 +232,14 @@ extern bool ExecBRUpdateTriggers(EState *estate, TupleTableSlot *slot); extern void ExecARUpdateTriggers(EState *estate, ResultRelInfo *relinfo, + ResultRelInfo *src_partinfo, + ResultRelInfo *dst_partinfo, ItemPointer tupleid, HeapTuple fdw_trigtuple, TupleTableSlot *slot, List *recheckIndexes, - TransitionCaptureState *transition_capture); + TransitionCaptureState *transition_capture, + bool is_crosspart_update); extern bool ExecIRUpdateTriggers(EState *estate, ResultRelInfo *relinfo, HeapTuple trigtuple, diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index 344399f6a8..82925b4b63 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -203,7 +203,9 @@ extern void InitResultRelInfo(ResultRelInfo *resultRelInfo, Index resultRelationIndex, ResultRelInfo *partition_root_rri, int instrument_options); -extern ResultRelInfo *ExecGetTriggerResultRel(EState *estate, Oid relid); +extern ResultRelInfo *ExecGetTriggerResultRel(EState *estate, Oid relid, + ResultRelInfo *rootRelInfo); +extern List *ExecGetAncestorResultRels(EState *estate, ResultRelInfo *resultRelInfo); extern void ExecConstraints(ResultRelInfo *resultRelInfo, TupleTableSlot *slot, EState *estate); extern bool ExecPartitionCheck(ResultRelInfo *resultRelInfo, diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index dd95dc40c7..44dd73fc80 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -530,6 +530,12 @@ typedef struct ResultRelInfo /* for use by copyfrom.c when performing multi-inserts */ struct CopyMultiInsertBuffer *ri_CopyMultiInsertBuffer; + + /* + * Used when a leaf partition is involved in a cross-partition update of + * one of its ancestors; see ExecCrossPartitionUpdateForeignKey(). + */ + List *ri_ancestorResultRels; } ResultRelInfo; /* ---------------- diff --git a/src/test/regress/expected/foreign_key.out b/src/test/regress/expected/foreign_key.out index 4c5274983d..da26f083bc 100644 --- a/src/test/regress/expected/foreign_key.out +++ b/src/test/regress/expected/foreign_key.out @@ -2556,7 +2556,7 @@ DELETE FROM pk WHERE a = 20; ERROR: update or delete on table "pk11" violates foreign key constraint "fk_a_fkey2" on table "fk" DETAIL: Key (a)=(20) is still referenced from table "fk". UPDATE pk SET a = 90 WHERE a = 30; -ERROR: update or delete on table "pk11" violates foreign key constraint "fk_a_fkey2" on table "fk" +ERROR: update or delete on table "pk" violates foreign key constraint "fk_a_fkey" on table "fk" DETAIL: Key (a)=(30) is still referenced from table "fk". SELECT tableoid::regclass, * FROM fk; tableoid | a @@ -2625,15 +2625,213 @@ CREATE SCHEMA fkpart10 CREATE TABLE tbl1(f1 int PRIMARY KEY) PARTITION BY RANGE(f1) CREATE TABLE tbl1_p1 PARTITION OF tbl1 FOR VALUES FROM (minvalue) TO (1) CREATE TABLE tbl1_p2 PARTITION OF tbl1 FOR VALUES FROM (1) TO (maxvalue) - CREATE TABLE tbl2(f1 int REFERENCES tbl1 DEFERRABLE INITIALLY DEFERRED); + CREATE TABLE tbl2(f1 int REFERENCES tbl1 DEFERRABLE INITIALLY DEFERRED) + CREATE TABLE tbl3(f1 int PRIMARY KEY) PARTITION BY RANGE(f1) + CREATE TABLE tbl3_p1 PARTITION OF tbl3 FOR VALUES FROM (minvalue) TO (1) + CREATE TABLE tbl3_p2 PARTITION OF tbl3 FOR VALUES FROM (1) TO (maxvalue) + CREATE TABLE tbl4(f1 int REFERENCES tbl3 DEFERRABLE INITIALLY DEFERRED); INSERT INTO fkpart10.tbl1 VALUES (0), (1); INSERT INTO fkpart10.tbl2 VALUES (0), (1); +INSERT INTO fkpart10.tbl3 VALUES (-2), (-1), (0); +INSERT INTO fkpart10.tbl4 VALUES (-2), (-1); BEGIN; DELETE FROM fkpart10.tbl1 WHERE f1 = 0; UPDATE fkpart10.tbl1 SET f1 = 2 WHERE f1 = 1; INSERT INTO fkpart10.tbl1 VALUES (0), (1); COMMIT; +-- test that cross-partition updates correctly enforces the foreign key +-- restriction (specifically testing INITIAILLY DEFERRED) +BEGIN; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +INSERT INTO fkpart10.tbl1 VALUES (4); +COMMIT; +ERROR: update or delete on table "tbl1" violates foreign key constraint "tbl2_f1_fkey" on table "tbl2" +DETAIL: Key (f1)=(0) is still referenced from table "tbl2". +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +UPDATE fkpart10.tbl3 SET f1 = f1 + 3; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +INSERT INTO fkpart10.tbl1 VALUES (0); +COMMIT; +ERROR: update or delete on table "tbl3" violates foreign key constraint "tbl4_f1_fkey" on table "tbl4" +DETAIL: Key (f1)=(-2) is still referenced from table "tbl4". +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +INSERT INTO fkpart10.tbl1 VALUES (0); +INSERT INTO fkpart10.tbl3 VALUES (-2), (-1); +COMMIT; +-- test where the updated table now has both an IMMEDIATE and a DEFERRED +-- constraint pointing into it +CREATE TABLE fkpart10.tbl5(f1 int REFERENCES fkpart10.tbl3); +INSERT INTO fkpart10.tbl5 VALUES (-2), (-1); +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -3; +ERROR: update or delete on table "tbl3" violates foreign key constraint "tbl5_f1_fkey" on table "tbl5" +DETAIL: Key (f1)=(-2) is still referenced from table "tbl5". +COMMIT; +-- Now test where the row referenced from the table with an IMMEDIATE +-- constraint stays in place, while those referenced from the table with a +-- DEFERRED constraint don't. +DELETE FROM fkpart10.tbl5; +INSERT INTO fkpart10.tbl5 VALUES (0); +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -3; +COMMIT; +ERROR: update or delete on table "tbl3" violates foreign key constraint "tbl4_f1_fkey" on table "tbl4" +DETAIL: Key (f1)=(-2) is still referenced from table "tbl4". DROP SCHEMA fkpart10 CASCADE; -NOTICE: drop cascades to 2 other objects +NOTICE: drop cascades to 5 other objects DETAIL: drop cascades to table fkpart10.tbl1 drop cascades to table fkpart10.tbl2 +drop cascades to table fkpart10.tbl3 +drop cascades to table fkpart10.tbl4 +drop cascades to table fkpart10.tbl5 +-- verify foreign keys are enforced during cross-partition updates, +-- especially on the PK side +CREATE SCHEMA fkpart11 + CREATE TABLE pk (a INT PRIMARY KEY, b text) PARTITION BY LIST (a) + CREATE TABLE fk ( + a INT, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES pk(a) ON UPDATE CASCADE ON DELETE CASCADE + ) + CREATE TABLE fk_parted ( + a INT PRIMARY KEY, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES pk(a) ON UPDATE CASCADE ON DELETE CASCADE + ) PARTITION BY LIST (a) + CREATE TABLE fk_another ( + a INT, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fk_parted (a) ON UPDATE CASCADE ON DELETE CASCADE + ) + CREATE TABLE pk1 PARTITION OF pk FOR VALUES IN (1, 2) PARTITION BY LIST (a) + CREATE TABLE pk2 PARTITION OF pk FOR VALUES IN (3) + CREATE TABLE pk3 PARTITION OF pk FOR VALUES IN (4) + CREATE TABLE fk1 PARTITION OF fk_parted FOR VALUES IN (1, 2) + CREATE TABLE fk2 PARTITION OF fk_parted FOR VALUES IN (3) + CREATE TABLE fk3 PARTITION OF fk_parted FOR VALUES IN (4); +CREATE TABLE fkpart11.pk11 (b text, a int NOT NULL); +ALTER TABLE fkpart11.pk1 ATTACH PARTITION fkpart11.pk11 FOR VALUES IN (1); +CREATE TABLE fkpart11.pk12 (b text, c int, a int NOT NULL); +ALTER TABLE fkpart11.pk12 DROP c; +ALTER TABLE fkpart11.pk1 ATTACH PARTITION fkpart11.pk12 FOR VALUES IN (2); +INSERT INTO fkpart11.pk VALUES (1, 'xxx'), (3, 'yyy'); +INSERT INTO fkpart11.fk VALUES (1), (3); +INSERT INTO fkpart11.fk_parted VALUES (1), (3); +INSERT INTO fkpart11.fk_another VALUES (1), (3); +-- moves 2 rows from one leaf partition to another, with both updates being +-- cascaded to fk and fk_parted. Updates of fk_parted, of which one is +-- cross-partition (3 -> 4), are further cascaded to fk_another. +UPDATE fkpart11.pk SET a = a + 1 RETURNING tableoid::pg_catalog.regclass, *; + tableoid | a | b +---------------+---+----- + fkpart11.pk12 | 2 | xxx + fkpart11.pk3 | 4 | yyy +(2 rows) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; + tableoid | a +-------------+--- + fkpart11.fk | 2 + fkpart11.fk | 4 +(2 rows) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_parted; + tableoid | a +--------------+--- + fkpart11.fk1 | 2 + fkpart11.fk3 | 4 +(2 rows) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_another; + tableoid | a +---------------------+--- + fkpart11.fk_another | 2 + fkpart11.fk_another | 4 +(2 rows) + +-- let's try with the foreign key pointing at tables in the partition tree +-- that are not the same as the query's target table +-- 1. foreign key pointing into a non-root ancestor +-- +-- A cross-partition update on the root table will fail, because we currently +-- can't enforce the foreign keys pointing into a non-leaf partition +ALTER TABLE fkpart11.fk DROP CONSTRAINT fkey; +DELETE FROM fkpart11.fk WHERE a = 4; +ALTER TABLE fkpart11.fk ADD CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fkpart11.pk1 (a) ON UPDATE CASCADE ON DELETE CASCADE; +UPDATE fkpart11.pk SET a = a - 1; +ERROR: cannot move tuple across partitions when a non-root ancestor of the source partition is directly referenced in a foreign key +DETAIL: A foreign key points to ancestor "pk1", but not the root ancestor "pk". +HINT: Consider defining the foreign key on "pk". +-- it's okay though if the non-leaf partition is updated directly +UPDATE fkpart11.pk1 SET a = a - 1; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.pk; + tableoid | a | b +---------------+---+----- + fkpart11.pk11 | 1 | xxx + fkpart11.pk3 | 4 | yyy +(2 rows) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; + tableoid | a +-------------+--- + fkpart11.fk | 1 +(1 row) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_parted; + tableoid | a +--------------+--- + fkpart11.fk1 | 1 + fkpart11.fk3 | 4 +(2 rows) + +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_another; + tableoid | a +---------------------+--- + fkpart11.fk_another | 4 + fkpart11.fk_another | 1 +(2 rows) + +-- 2. foreign key pointing into a single leaf partition +-- +-- A cross-partition update that deletes from the pointed-to leaf partition +-- is allowed to succeed +ALTER TABLE fkpart11.fk DROP CONSTRAINT fkey; +ALTER TABLE fkpart11.fk ADD CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fkpart11.pk11 (a) ON UPDATE CASCADE ON DELETE CASCADE; +-- will delete (1) from p11 which is cascaded to fk +UPDATE fkpart11.pk SET a = a + 1 WHERE a = 1; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; + tableoid | a +----------+--- +(0 rows) + +DROP TABLE fkpart11.fk; +-- check that regular and deferrable AR triggers on the PK tables +-- still work as expected +CREATE FUNCTION fkpart11.print_row () RETURNS TRIGGER LANGUAGE plpgsql AS $$ + BEGIN + RAISE NOTICE 'TABLE: %, OP: %, OLD: %, NEW: %', TG_RELNAME, TG_OP, OLD, NEW; + RETURN NULL; + END; +$$; +CREATE TRIGGER trig_upd_pk AFTER UPDATE ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE TRIGGER trig_del_pk AFTER DELETE ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE TRIGGER trig_ins_pk AFTER INSERT ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_upd_fk_parted AFTER UPDATE ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_del_fk_parted AFTER DELETE ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_ins_fk_parted AFTER INSERT ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +UPDATE fkpart11.pk SET a = 3 WHERE a = 4; +NOTICE: TABLE: pk3, OP: DELETE, OLD: (4,yyy), NEW: <NULL> +NOTICE: TABLE: pk2, OP: INSERT, OLD: <NULL>, NEW: (3,yyy) +NOTICE: TABLE: fk3, OP: DELETE, OLD: (4), NEW: <NULL> +NOTICE: TABLE: fk2, OP: INSERT, OLD: <NULL>, NEW: (3) +UPDATE fkpart11.pk SET a = 1 WHERE a = 2; +NOTICE: TABLE: pk12, OP: DELETE, OLD: (xxx,2), NEW: <NULL> +NOTICE: TABLE: pk11, OP: INSERT, OLD: <NULL>, NEW: (xxx,1) +NOTICE: TABLE: fk1, OP: UPDATE, OLD: (2), NEW: (1) +DROP SCHEMA fkpart11 CASCADE; +NOTICE: drop cascades to 4 other objects +DETAIL: drop cascades to table fkpart11.pk +drop cascades to table fkpart11.fk_parted +drop cascades to table fkpart11.fk_another +drop cascades to function fkpart11.print_row() diff --git a/src/test/regress/sql/foreign_key.sql b/src/test/regress/sql/foreign_key.sql index fa781b6e32..725a59a525 100644 --- a/src/test/regress/sql/foreign_key.sql +++ b/src/test/regress/sql/foreign_key.sql @@ -1871,12 +1871,145 @@ CREATE SCHEMA fkpart10 CREATE TABLE tbl1(f1 int PRIMARY KEY) PARTITION BY RANGE(f1) CREATE TABLE tbl1_p1 PARTITION OF tbl1 FOR VALUES FROM (minvalue) TO (1) CREATE TABLE tbl1_p2 PARTITION OF tbl1 FOR VALUES FROM (1) TO (maxvalue) - CREATE TABLE tbl2(f1 int REFERENCES tbl1 DEFERRABLE INITIALLY DEFERRED); + CREATE TABLE tbl2(f1 int REFERENCES tbl1 DEFERRABLE INITIALLY DEFERRED) + CREATE TABLE tbl3(f1 int PRIMARY KEY) PARTITION BY RANGE(f1) + CREATE TABLE tbl3_p1 PARTITION OF tbl3 FOR VALUES FROM (minvalue) TO (1) + CREATE TABLE tbl3_p2 PARTITION OF tbl3 FOR VALUES FROM (1) TO (maxvalue) + CREATE TABLE tbl4(f1 int REFERENCES tbl3 DEFERRABLE INITIALLY DEFERRED); INSERT INTO fkpart10.tbl1 VALUES (0), (1); INSERT INTO fkpart10.tbl2 VALUES (0), (1); +INSERT INTO fkpart10.tbl3 VALUES (-2), (-1), (0); +INSERT INTO fkpart10.tbl4 VALUES (-2), (-1); BEGIN; DELETE FROM fkpart10.tbl1 WHERE f1 = 0; UPDATE fkpart10.tbl1 SET f1 = 2 WHERE f1 = 1; INSERT INTO fkpart10.tbl1 VALUES (0), (1); COMMIT; + +-- test that cross-partition updates correctly enforces the foreign key +-- restriction (specifically testing INITIAILLY DEFERRED) +BEGIN; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +INSERT INTO fkpart10.tbl1 VALUES (4); +COMMIT; + +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +UPDATE fkpart10.tbl3 SET f1 = f1 + 3; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +INSERT INTO fkpart10.tbl1 VALUES (0); +COMMIT; + +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -1; +UPDATE fkpart10.tbl1 SET f1 = 3 WHERE f1 = 0; +INSERT INTO fkpart10.tbl1 VALUES (0); +INSERT INTO fkpart10.tbl3 VALUES (-2), (-1); +COMMIT; + +-- test where the updated table now has both an IMMEDIATE and a DEFERRED +-- constraint pointing into it +CREATE TABLE fkpart10.tbl5(f1 int REFERENCES fkpart10.tbl3); +INSERT INTO fkpart10.tbl5 VALUES (-2), (-1); +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -3; +COMMIT; + +-- Now test where the row referenced from the table with an IMMEDIATE +-- constraint stays in place, while those referenced from the table with a +-- DEFERRED constraint don't. +DELETE FROM fkpart10.tbl5; +INSERT INTO fkpart10.tbl5 VALUES (0); +BEGIN; +UPDATE fkpart10.tbl3 SET f1 = f1 * -3; +COMMIT; + DROP SCHEMA fkpart10 CASCADE; + +-- verify foreign keys are enforced during cross-partition updates, +-- especially on the PK side +CREATE SCHEMA fkpart11 + CREATE TABLE pk (a INT PRIMARY KEY, b text) PARTITION BY LIST (a) + CREATE TABLE fk ( + a INT, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES pk(a) ON UPDATE CASCADE ON DELETE CASCADE + ) + CREATE TABLE fk_parted ( + a INT PRIMARY KEY, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES pk(a) ON UPDATE CASCADE ON DELETE CASCADE + ) PARTITION BY LIST (a) + CREATE TABLE fk_another ( + a INT, + CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fk_parted (a) ON UPDATE CASCADE ON DELETE CASCADE + ) + CREATE TABLE pk1 PARTITION OF pk FOR VALUES IN (1, 2) PARTITION BY LIST (a) + CREATE TABLE pk2 PARTITION OF pk FOR VALUES IN (3) + CREATE TABLE pk3 PARTITION OF pk FOR VALUES IN (4) + CREATE TABLE fk1 PARTITION OF fk_parted FOR VALUES IN (1, 2) + CREATE TABLE fk2 PARTITION OF fk_parted FOR VALUES IN (3) + CREATE TABLE fk3 PARTITION OF fk_parted FOR VALUES IN (4); +CREATE TABLE fkpart11.pk11 (b text, a int NOT NULL); +ALTER TABLE fkpart11.pk1 ATTACH PARTITION fkpart11.pk11 FOR VALUES IN (1); +CREATE TABLE fkpart11.pk12 (b text, c int, a int NOT NULL); +ALTER TABLE fkpart11.pk12 DROP c; +ALTER TABLE fkpart11.pk1 ATTACH PARTITION fkpart11.pk12 FOR VALUES IN (2); +INSERT INTO fkpart11.pk VALUES (1, 'xxx'), (3, 'yyy'); +INSERT INTO fkpart11.fk VALUES (1), (3); +INSERT INTO fkpart11.fk_parted VALUES (1), (3); +INSERT INTO fkpart11.fk_another VALUES (1), (3); +-- moves 2 rows from one leaf partition to another, with both updates being +-- cascaded to fk and fk_parted. Updates of fk_parted, of which one is +-- cross-partition (3 -> 4), are further cascaded to fk_another. +UPDATE fkpart11.pk SET a = a + 1 RETURNING tableoid::pg_catalog.regclass, *; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_parted; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_another; + +-- let's try with the foreign key pointing at tables in the partition tree +-- that are not the same as the query's target table + +-- 1. foreign key pointing into a non-root ancestor +-- +-- A cross-partition update on the root table will fail, because we currently +-- can't enforce the foreign keys pointing into a non-leaf partition +ALTER TABLE fkpart11.fk DROP CONSTRAINT fkey; +DELETE FROM fkpart11.fk WHERE a = 4; +ALTER TABLE fkpart11.fk ADD CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fkpart11.pk1 (a) ON UPDATE CASCADE ON DELETE CASCADE; +UPDATE fkpart11.pk SET a = a - 1; +-- it's okay though if the non-leaf partition is updated directly +UPDATE fkpart11.pk1 SET a = a - 1; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.pk; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_parted; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk_another; + +-- 2. foreign key pointing into a single leaf partition +-- +-- A cross-partition update that deletes from the pointed-to leaf partition +-- is allowed to succeed +ALTER TABLE fkpart11.fk DROP CONSTRAINT fkey; +ALTER TABLE fkpart11.fk ADD CONSTRAINT fkey FOREIGN KEY (a) REFERENCES fkpart11.pk11 (a) ON UPDATE CASCADE ON DELETE CASCADE; +-- will delete (1) from p11 which is cascaded to fk +UPDATE fkpart11.pk SET a = a + 1 WHERE a = 1; +SELECT tableoid::pg_catalog.regclass, * FROM fkpart11.fk; +DROP TABLE fkpart11.fk; + +-- check that regular and deferrable AR triggers on the PK tables +-- still work as expected +CREATE FUNCTION fkpart11.print_row () RETURNS TRIGGER LANGUAGE plpgsql AS $$ + BEGIN + RAISE NOTICE 'TABLE: %, OP: %, OLD: %, NEW: %', TG_RELNAME, TG_OP, OLD, NEW; + RETURN NULL; + END; +$$; +CREATE TRIGGER trig_upd_pk AFTER UPDATE ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE TRIGGER trig_del_pk AFTER DELETE ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE TRIGGER trig_ins_pk AFTER INSERT ON fkpart11.pk FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_upd_fk_parted AFTER UPDATE ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_del_fk_parted AFTER DELETE ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +CREATE CONSTRAINT TRIGGER trig_ins_fk_parted AFTER INSERT ON fkpart11.fk_parted INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION fkpart11.print_row(); +UPDATE fkpart11.pk SET a = 3 WHERE a = 4; +UPDATE fkpart11.pk SET a = 1 WHERE a = 2; + +DROP SCHEMA fkpart11 CASCADE; -- 2.30.2 --v3m6mf22af7dxoz2-- ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-01 13:14 Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-01 13:14 UTC (permalink / raw) To: Dagfinn Ilmari Mannsåker <[email protected]>; +Cc: pgsql-hackers On Mon, Jul 1, 2024, at 15:11, Joel Jacobson wrote: > Not really sure why. Maybe the code I tried can be optimized further: If anyone want experiment with the int128 version, here is a patch that adds a separate numeric_mul_patched() function, so it's easier to benchmark against the unmodified numeric_mul(). /Joel Attachments: [application/octet-stream] 0001-Optimize-mul_var-for-var2ndigits-4.patch (14.7K, ../../[email protected]/2-0001-Optimize-mul_var-for-var2ndigits-4.patch) download | inline diff: From c443f44d1338a69a21632ba0cd3fb069b6cbbcf5 Mon Sep 17 00:00:00 2001 From: Joel Jakobsson <[email protected]> Date: Mon, 1 Jul 2024 07:17:50 +0200 Subject: [PATCH] Optimize mul_var() for var2ndigits <= 4 --- src/backend/utils/adt/numeric.c | 457 ++++++++++++++++++++++++++++++++ src/include/catalog/pg_proc.dat | 3 + src/include/utils/numeric.h | 2 + 3 files changed, 462 insertions(+) diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5510a203b0..87980fa771 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -551,6 +551,9 @@ static void sub_var(const NumericVar *var1, const NumericVar *var2, static void mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale); +static void mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, + int rscale); static void div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale, bool round); @@ -3115,6 +3118,130 @@ numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error) } +/* + * numeric_mul_patched() - + * + * This function multiplies two numeric values using the patched algorithm, + * designed for efficient handling of large numbers. It's introduced to allow + * direct benchmark comparisons with the standard numeric_mul() function. + */ +Datum +numeric_mul_patched(PG_FUNCTION_ARGS) +{ + Numeric num1 = PG_GETARG_NUMERIC(0); + Numeric num2 = PG_GETARG_NUMERIC(1); + Numeric res; + + res = numeric_mul_patched_opt_error(num1, num2, NULL); + + PG_RETURN_NUMERIC(res); +} + + +/* + * numeric_mul_patched_opt_error() - + * + * Internal version of numeric_mul_patched(). + * If "*have_error" flag is provided, on error it's set to true, NULL returned. + * This is helpful when caller need to handle errors by itself. + */ +Numeric +numeric_mul_patched_opt_error(Numeric num1, Numeric num2, bool *have_error) +{ + NumericVar arg1; + NumericVar arg2; + NumericVar result; + Numeric res; + + /* + * Handle NaN and infinities + */ + if (NUMERIC_IS_SPECIAL(num1) || NUMERIC_IS_SPECIAL(num2)) + { + if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2)) + return make_result(&const_nan); + if (NUMERIC_IS_PINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* Inf * 0 */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + if (NUMERIC_IS_NINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* -Inf * 0 */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + /* by here, num1 must be finite, so num2 is not */ + if (NUMERIC_IS_PINF(num2)) + { + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * Inf */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + Assert(NUMERIC_IS_NINF(num2)); + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * -Inf */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + + /* + * Unpack the values, let mul_var() compute the result and return it. + * Unlike add_var() and sub_var(), mul_var() will round its result. In the + * case of numeric_mul(), which is invoked for the * operator on numerics, + * we request exact representation for the product (rscale = sum(dscale of + * arg1, dscale of arg2)). If the exact result has more digits after the + * decimal point than can be stored in a numeric, we round it. Rounding + * after computing the exact result ensures that the final result is + * correctly rounded (rounding in mul_var() using a truncated product + * would not guarantee this). + */ + init_var_from_num(num1, &arg1); + init_var_from_num(num2, &arg2); + + init_var(&result); + + mul_var_patched(&arg1, &arg2, &result, arg1.dscale + arg2.dscale); + + if (result.dscale > NUMERIC_DSCALE_MAX) + round_var(&result, NUMERIC_DSCALE_MAX); + + res = make_result_opt_error(&result, have_error); + + free_var(&result); + + return res; +} + + /* * numeric_div() - * @@ -8864,6 +8991,336 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, strip_var(result); } +/* + * mul_var_patched() - + * + * Implements patched multiplication for large numbers, introduced + * alongside the unchanged original mul_var(). This function is part of + * an optimization effort, allowing direct benchmark comparisons with + * mul_var(). It selects full or half patched based on input size. + * This is a temporary measure before considering its replacement of + * mul_var() based on benchmark outcomes. + */ +static void +mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, int rscale) +{ + int res_ndigits; + int res_sign; + int res_weight; + int maxdigits; + int *dig; + int carry; + int maxdig; + int newdig; + int var1ndigits; + int var2ndigits; + NumericDigit *var1digits; + NumericDigit *var2digits; + NumericDigit *res_digits; + int i, + i1, + i2; + + /* + * Arrange for var1 to be the shorter of the two numbers. This improves + * performance because the inner multiplication loop is much simpler than + * the outer loop, so it's better to have a smaller number of iterations + * of the outer loop. This also reduces the number of times that the + * accumulator array needs to be normalized. + */ + if (var1->ndigits > var2->ndigits) + { + const NumericVar *tmp = var1; + + var1 = var2; + var2 = tmp; + } + + /* copy these values into local vars for speed in inner loop */ + var1ndigits = var1->ndigits; + var2ndigits = var2->ndigits; + var1digits = var1->digits; + var2digits = var2->digits; + + if (var1ndigits == 0 || var2ndigits == 0) + { + /* one or both inputs is zero; so is result */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* Determine result sign and (maximum possible) weight */ + if (var1->sign == var2->sign) + res_sign = NUMERIC_POS; + else + res_sign = NUMERIC_NEG; + res_weight = var1->weight + var2->weight + 2; + + /* + * Determine the number of result digits to compute. If the exact result + * would have more than rscale fractional digits, truncate the computation + * with MUL_GUARD_DIGITS guard digits, i.e., ignore input digits that + * would only contribute to the right of that. (This will give the exact + * rounded-to-rscale answer unless carries out of the ignored positions + * would have propagated through more than MUL_GUARD_DIGITS digits.) + * + * Note: an exact computation could not produce more than var1ndigits + + * var2ndigits digits, but we allocate one extra output digit in case + * rscale-driven rounding produces a carry out of the highest exact digit. + */ + res_ndigits = var1ndigits + var2ndigits + 1; + maxdigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS + + MUL_GUARD_DIGITS; + res_ndigits = Min(res_ndigits, maxdigits); + + if (res_ndigits < 3) + { + /* All input digits will be ignored; so result is zero */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* + * If var1 and var2 are just one or two NBASE digits, their product will + * fit in an int64 can be computed directly, which is significantly faster. + */ + if (var2ndigits <= 2) + { + int64 product = 0; + switch (var1ndigits) + { + case 1: + product = var1digits[0]; + break; + case 2: + product = var1digits[0] * NBASE + var1digits[1]; + break; + } + + switch (var2ndigits) + { + case 1: + product *= var2digits[0]; + break; + case 2: + product *= var2digits[0] * NBASE + var2digits[1]; + break; + } + + alloc_var(result, res_ndigits); + res_digits = result->digits; + for (i = res_ndigits - 1; i >= 0; i--) + { + res_digits[i] = product % NBASE; + product /= NBASE; + } + Assert(product == 0); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } +#ifdef HAVE_INT128 + /* + * If var1 and var2 are up to four digits, their product will fit in + * an int128 can be computed directly, which is significantly faster. + */ + if (var2ndigits <= 4) + { + int128 product = 0; + + switch (var1ndigits) + { + case 1: + product = var1digits[0]; + break; + case 2: + product = var1digits[0] * NBASE + var1digits[1]; + break; + case 3: + product = ((int128) var1digits[0] * NBASE + var1digits[1]) + * NBASE + var1digits[2]; + break; + case 4: + product = (((int128) var1digits[0] * NBASE + var1digits[1]) + * NBASE + var1digits[2]) * NBASE + var1digits[3]; + break; + } + + switch (var2ndigits) + { + case 1: + product *= var2digits[0]; + break; + case 2: + product *= var2digits[0] * NBASE + var2digits[1]; + break; + case 3: + product = ((int128) var2digits[0] * NBASE + var2digits[1]) + * NBASE + var2digits[2]; + break; + case 4: + product = (((int128) var2digits[0] * NBASE + var2digits[1]) + * NBASE + var2digits[2]) * NBASE + var2digits[3]; + break; + } + + alloc_var(result, res_ndigits); + res_digits = result->digits; + for (i = res_ndigits - 1; i >= 0; i--) + { + res_digits[i] = product % NBASE; + product /= NBASE; + } + Assert(product == 0); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } +#endif + + /* + * We do the arithmetic in an array "dig[]" of signed int's. Since + * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom + * to avoid normalizing carries immediately. + * + * maxdig tracks the maximum possible value of any dig[] entry; when this + * threatens to exceed INT_MAX, we take the time to propagate carries. + * Furthermore, we need to ensure that overflow doesn't occur during the + * carry propagation passes either. The carry values could be as much as + * INT_MAX/NBASE, so really we must normalize when digits threaten to + * exceed INT_MAX - INT_MAX/NBASE. + * + * To avoid overflow in maxdig itself, it actually represents the max + * possible value divided by NBASE-1, ie, at the top of the loop it is + * known that no dig[] entry exceeds maxdig * (NBASE-1). + */ + dig = (int *) palloc0(res_ndigits * sizeof(int)); + maxdig = 0; + + /* + * The least significant digits of var1 should be ignored if they don't + * contribute directly to the first res_ndigits digits of the result that + * we are computing. + * + * Digit i1 of var1 and digit i2 of var2 are multiplied and added to digit + * i1+i2+2 of the accumulator array, so we need only consider digits of + * var1 for which i1 <= res_ndigits - 3. + */ + for (i1 = Min(var1ndigits - 1, res_ndigits - 3); i1 >= 0; i1--) + { + NumericDigit var1digit = var1digits[i1]; + + if (var1digit == 0) + continue; + + /* Time to normalize? */ + maxdig += var1digit; + if (maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1)) + { + /* Yes, do it */ + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + dig[i] = newdig; + } + Assert(carry == 0); + /* Reset maxdig to indicate new worst-case */ + maxdig = 1 + var1digit; + } + + /* + * Add the appropriate multiple of var2 into the accumulator. + * + * As above, digits of var2 can be ignored if they don't contribute, + * so we only include digits for which i1+i2+2 < res_ndigits. + * + * This inner loop is the performance bottleneck for multiplication, + * so we want to keep it simple enough so that it can be + * auto-vectorized. Accordingly, process the digits left-to-right + * even though schoolbook multiplication would suggest right-to-left. + * Since we aren't propagating carries in this loop, the order does + * not matter. + */ + { + int i2limit = Min(var2ndigits, res_ndigits - i1 - 2); + int *dig_i1_2 = &dig[i1 + 2]; + + for (i2 = 0; i2 < i2limit; i2++) + dig_i1_2[i2] += var1digit * var2digits[i2]; + } + } + + /* + * Now we do a final carry propagation pass to normalize the result, which + * we combine with storing the result digits into the output. Note that + * this is still done at full precision w/guard digits. + */ + alloc_var(result, res_ndigits); + res_digits = result->digits; + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + res_digits[i] = newdig; + } + Assert(carry == 0); + + pfree(dig); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + +} + /* * div_var() - diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index 6a5476d3c4..15dde0f3c3 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -4465,6 +4465,9 @@ { oid => '1726', proname => 'numeric_mul', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_mul' }, +{ oid => '6347', + proname => 'numeric_mul_patched', prorettype => 'numeric', + proargtypes => 'numeric numeric', prosrc => 'numeric_mul_patched' }, { oid => '1727', proname => 'numeric_div', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_div' }, diff --git a/src/include/utils/numeric.h b/src/include/utils/numeric.h index 43c75c436f..9036c9db50 100644 --- a/src/include/utils/numeric.h +++ b/src/include/utils/numeric.h @@ -97,6 +97,8 @@ extern Numeric numeric_sub_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error); +extern Numeric numeric_mul_patched_opt_error(Numeric num1, Numeric num2, + bool *have_error); extern Numeric numeric_div_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mod_opt_error(Numeric num1, Numeric num2, -- 2.45.1 ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-01 19:56 Joel Jacobson <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-01 19:56 UTC (permalink / raw) To: Dagfinn Ilmari Mannsåker <[email protected]>; +Cc: pgsql-hackers On Mon, Jul 1, 2024, at 15:14, Joel Jacobson wrote: > * 0001-Optimize-mul_var-for-var2ndigits-4.patch Found a typo, fixed in new version. The int128 version is still slower though, I wonder if there is something that can be done to speed it up further. Below is a more realistic benchmark than just microbenchmarking mul_var(), not testing the int128 version, but the code for up to 2 NBASE-digits: ``` CREATE TABLE bench_mul_var (num1 numeric, num2 numeric); INSERT INTO bench_mul_var (num1, num2) SELECT random(0::numeric,1e8::numeric), random(0::numeric,1e8::numeric) FROM generate_series(1,1e8); SELECT SUM(num1*num2) FROM bench_mul_var; Time: 8331.953 ms (00:08.332) Time: 7415.241 ms (00:07.415) Time: 7298.296 ms (00:07.298) Time: 7314.754 ms (00:07.315) Time: 7289.560 ms (00:07.290) SELECT SUM(numeric_mul_patched(num1,num2)) FROM bench_mul_var; Time: 6403.426 ms (00:06.403) Time: 6401.797 ms (00:06.402) Time: 6366.136 ms (00:06.366) Time: 6376.049 ms (00:06.376) Time: 6317.282 ms (00:06.317) `` Benchmarked on a Intel Core i9-14900K machine. /Joel Attachments: [application/octet-stream] v2-0001-Optimize-mul_var-for-var2ndigits-4.patch (14.7K, ../../[email protected]/2-v2-0001-Optimize-mul_var-for-var2ndigits-4.patch) download | inline diff: From b075e18c2ae94f2ada20572c05ff35730d2c5968 Mon Sep 17 00:00:00 2001 From: Joel Jakobsson <[email protected]> Date: Mon, 1 Jul 2024 07:17:50 +0200 Subject: [PATCH] Optimize mul_var() for var2ndigits <= 4 --- src/backend/utils/adt/numeric.c | 457 ++++++++++++++++++++++++++++++++ src/include/catalog/pg_proc.dat | 3 + src/include/utils/numeric.h | 2 + 3 files changed, 462 insertions(+) diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5510a203b0..b74e03eefa 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -551,6 +551,9 @@ static void sub_var(const NumericVar *var1, const NumericVar *var2, static void mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale); +static void mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, + int rscale); static void div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale, bool round); @@ -3115,6 +3118,130 @@ numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error) } +/* + * numeric_mul_patched() - + * + * This function multiplies two numeric values using the patched algorithm, + * designed for efficient handling of large numbers. It's introduced to allow + * direct benchmark comparisons with the standard numeric_mul() function. + */ +Datum +numeric_mul_patched(PG_FUNCTION_ARGS) +{ + Numeric num1 = PG_GETARG_NUMERIC(0); + Numeric num2 = PG_GETARG_NUMERIC(1); + Numeric res; + + res = numeric_mul_patched_opt_error(num1, num2, NULL); + + PG_RETURN_NUMERIC(res); +} + + +/* + * numeric_mul_patched_opt_error() - + * + * Internal version of numeric_mul_patched(). + * If "*have_error" flag is provided, on error it's set to true, NULL returned. + * This is helpful when caller need to handle errors by itself. + */ +Numeric +numeric_mul_patched_opt_error(Numeric num1, Numeric num2, bool *have_error) +{ + NumericVar arg1; + NumericVar arg2; + NumericVar result; + Numeric res; + + /* + * Handle NaN and infinities + */ + if (NUMERIC_IS_SPECIAL(num1) || NUMERIC_IS_SPECIAL(num2)) + { + if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2)) + return make_result(&const_nan); + if (NUMERIC_IS_PINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* Inf * 0 */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + if (NUMERIC_IS_NINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* -Inf * 0 */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + /* by here, num1 must be finite, so num2 is not */ + if (NUMERIC_IS_PINF(num2)) + { + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * Inf */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + Assert(NUMERIC_IS_NINF(num2)); + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * -Inf */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + + /* + * Unpack the values, let mul_var() compute the result and return it. + * Unlike add_var() and sub_var(), mul_var() will round its result. In the + * case of numeric_mul(), which is invoked for the * operator on numerics, + * we request exact representation for the product (rscale = sum(dscale of + * arg1, dscale of arg2)). If the exact result has more digits after the + * decimal point than can be stored in a numeric, we round it. Rounding + * after computing the exact result ensures that the final result is + * correctly rounded (rounding in mul_var() using a truncated product + * would not guarantee this). + */ + init_var_from_num(num1, &arg1); + init_var_from_num(num2, &arg2); + + init_var(&result); + + mul_var_patched(&arg1, &arg2, &result, arg1.dscale + arg2.dscale); + + if (result.dscale > NUMERIC_DSCALE_MAX) + round_var(&result, NUMERIC_DSCALE_MAX); + + res = make_result_opt_error(&result, have_error); + + free_var(&result); + + return res; +} + + /* * numeric_div() - * @@ -8864,6 +8991,336 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, strip_var(result); } +/* + * mul_var_patched() - + * + * Implements patched multiplication for large numbers, introduced + * alongside the unchanged original mul_var(). This function is part of + * an optimization effort, allowing direct benchmark comparisons with + * mul_var(). It selects full or half patched based on input size. + * This is a temporary measure before considering its replacement of + * mul_var() based on benchmark outcomes. + */ +static void +mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, int rscale) +{ + int res_ndigits; + int res_sign; + int res_weight; + int maxdigits; + int *dig; + int carry; + int maxdig; + int newdig; + int var1ndigits; + int var2ndigits; + NumericDigit *var1digits; + NumericDigit *var2digits; + NumericDigit *res_digits; + int i, + i1, + i2; + + /* + * Arrange for var1 to be the shorter of the two numbers. This improves + * performance because the inner multiplication loop is much simpler than + * the outer loop, so it's better to have a smaller number of iterations + * of the outer loop. This also reduces the number of times that the + * accumulator array needs to be normalized. + */ + if (var1->ndigits > var2->ndigits) + { + const NumericVar *tmp = var1; + + var1 = var2; + var2 = tmp; + } + + /* copy these values into local vars for speed in inner loop */ + var1ndigits = var1->ndigits; + var2ndigits = var2->ndigits; + var1digits = var1->digits; + var2digits = var2->digits; + + if (var1ndigits == 0 || var2ndigits == 0) + { + /* one or both inputs is zero; so is result */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* Determine result sign and (maximum possible) weight */ + if (var1->sign == var2->sign) + res_sign = NUMERIC_POS; + else + res_sign = NUMERIC_NEG; + res_weight = var1->weight + var2->weight + 2; + + /* + * Determine the number of result digits to compute. If the exact result + * would have more than rscale fractional digits, truncate the computation + * with MUL_GUARD_DIGITS guard digits, i.e., ignore input digits that + * would only contribute to the right of that. (This will give the exact + * rounded-to-rscale answer unless carries out of the ignored positions + * would have propagated through more than MUL_GUARD_DIGITS digits.) + * + * Note: an exact computation could not produce more than var1ndigits + + * var2ndigits digits, but we allocate one extra output digit in case + * rscale-driven rounding produces a carry out of the highest exact digit. + */ + res_ndigits = var1ndigits + var2ndigits + 1; + maxdigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS + + MUL_GUARD_DIGITS; + res_ndigits = Min(res_ndigits, maxdigits); + + if (res_ndigits < 3) + { + /* All input digits will be ignored; so result is zero */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* + * If var1 and var2 are just one or two NBASE digits, their product will + * fit in an int64 can be computed directly, which is significantly faster. + */ + if (var2ndigits <= 2) + { + int64 product = 0; + switch (var1ndigits) + { + case 1: + product = var1digits[0]; + break; + case 2: + product = var1digits[0] * NBASE + var1digits[1]; + break; + } + + switch (var2ndigits) + { + case 1: + product *= var2digits[0]; + break; + case 2: + product *= var2digits[0] * NBASE + var2digits[1]; + break; + } + + alloc_var(result, res_ndigits); + res_digits = result->digits; + for (i = res_ndigits - 1; i >= 0; i--) + { + res_digits[i] = product % NBASE; + product /= NBASE; + } + Assert(product == 0); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } +#ifdef HAVE_INT128 + /* + * If var1 and var2 are up to four digits, their product will fit in + * an int128 can be computed directly, which is significantly faster. + */ + if (var2ndigits <= 4) + { + int128 product = 0; + + switch (var1ndigits) + { + case 1: + product = var1digits[0]; + break; + case 2: + product = var1digits[0] * NBASE + var1digits[1]; + break; + case 3: + product = ((int128) var1digits[0] * NBASE + var1digits[1]) + * NBASE + var1digits[2]; + break; + case 4: + product = (((int128) var1digits[0] * NBASE + var1digits[1]) + * NBASE + var1digits[2]) * NBASE + var1digits[3]; + break; + } + + switch (var2ndigits) + { + case 1: + product *= var2digits[0]; + break; + case 2: + product *= var2digits[0] * NBASE + var2digits[1]; + break; + case 3: + product *= ((int128) var2digits[0] * NBASE + var2digits[1]) + * NBASE + var2digits[2]; + break; + case 4: + product *= (((int128) var2digits[0] * NBASE + var2digits[1]) + * NBASE + var2digits[2]) * NBASE + var2digits[3]; + break; + } + + alloc_var(result, res_ndigits); + res_digits = result->digits; + for (i = res_ndigits - 1; i >= 0; i--) + { + res_digits[i] = product % NBASE; + product /= NBASE; + } + Assert(product == 0); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } +#endif + + /* + * We do the arithmetic in an array "dig[]" of signed int's. Since + * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom + * to avoid normalizing carries immediately. + * + * maxdig tracks the maximum possible value of any dig[] entry; when this + * threatens to exceed INT_MAX, we take the time to propagate carries. + * Furthermore, we need to ensure that overflow doesn't occur during the + * carry propagation passes either. The carry values could be as much as + * INT_MAX/NBASE, so really we must normalize when digits threaten to + * exceed INT_MAX - INT_MAX/NBASE. + * + * To avoid overflow in maxdig itself, it actually represents the max + * possible value divided by NBASE-1, ie, at the top of the loop it is + * known that no dig[] entry exceeds maxdig * (NBASE-1). + */ + dig = (int *) palloc0(res_ndigits * sizeof(int)); + maxdig = 0; + + /* + * The least significant digits of var1 should be ignored if they don't + * contribute directly to the first res_ndigits digits of the result that + * we are computing. + * + * Digit i1 of var1 and digit i2 of var2 are multiplied and added to digit + * i1+i2+2 of the accumulator array, so we need only consider digits of + * var1 for which i1 <= res_ndigits - 3. + */ + for (i1 = Min(var1ndigits - 1, res_ndigits - 3); i1 >= 0; i1--) + { + NumericDigit var1digit = var1digits[i1]; + + if (var1digit == 0) + continue; + + /* Time to normalize? */ + maxdig += var1digit; + if (maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1)) + { + /* Yes, do it */ + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + dig[i] = newdig; + } + Assert(carry == 0); + /* Reset maxdig to indicate new worst-case */ + maxdig = 1 + var1digit; + } + + /* + * Add the appropriate multiple of var2 into the accumulator. + * + * As above, digits of var2 can be ignored if they don't contribute, + * so we only include digits for which i1+i2+2 < res_ndigits. + * + * This inner loop is the performance bottleneck for multiplication, + * so we want to keep it simple enough so that it can be + * auto-vectorized. Accordingly, process the digits left-to-right + * even though schoolbook multiplication would suggest right-to-left. + * Since we aren't propagating carries in this loop, the order does + * not matter. + */ + { + int i2limit = Min(var2ndigits, res_ndigits - i1 - 2); + int *dig_i1_2 = &dig[i1 + 2]; + + for (i2 = 0; i2 < i2limit; i2++) + dig_i1_2[i2] += var1digit * var2digits[i2]; + } + } + + /* + * Now we do a final carry propagation pass to normalize the result, which + * we combine with storing the result digits into the output. Note that + * this is still done at full precision w/guard digits. + */ + alloc_var(result, res_ndigits); + res_digits = result->digits; + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + res_digits[i] = newdig; + } + Assert(carry == 0); + + pfree(dig); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + +} + /* * div_var() - diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index 6a5476d3c4..15dde0f3c3 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -4465,6 +4465,9 @@ { oid => '1726', proname => 'numeric_mul', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_mul' }, +{ oid => '6347', + proname => 'numeric_mul_patched', prorettype => 'numeric', + proargtypes => 'numeric numeric', prosrc => 'numeric_mul_patched' }, { oid => '1727', proname => 'numeric_div', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_div' }, diff --git a/src/include/utils/numeric.h b/src/include/utils/numeric.h index 43c75c436f..9036c9db50 100644 --- a/src/include/utils/numeric.h +++ b/src/include/utils/numeric.h @@ -97,6 +97,8 @@ extern Numeric numeric_sub_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error); +extern Numeric numeric_mul_patched_opt_error(Numeric num1, Numeric num2, + bool *have_error); extern Numeric numeric_div_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mod_opt_error(Numeric num1, Numeric num2, -- 2.45.1 ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-01 22:19 Dean Rasheed <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Dean Rasheed @ 2024-07-01 22:19 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Mon, 1 Jul 2024 at 20:56, Joel Jacobson <[email protected]> wrote: > > Below is a more realistic benchmark > > CREATE TABLE bench_mul_var (num1 numeric, num2 numeric); > > INSERT INTO bench_mul_var (num1, num2) > SELECT random(0::numeric,1e8::numeric), random(0::numeric,1e8::numeric) FROM generate_series(1,1e8); > > SELECT SUM(num1*num2) FROM bench_mul_var; I had a play with this, and came up with a slightly different way of doing it that works for var2 of any size, as long as var1 is just 1 or 2 digits. Repeating your benchmark where both numbers have up to 2 NBASE-digits, this new approach was slightly faster: SELECT SUM(num1*num2) FROM bench_mul_var; -- HEAD Time: 4762.990 ms (00:04.763) Time: 4332.166 ms (00:04.332) Time: 4276.211 ms (00:04.276) Time: 4247.321 ms (00:04.247) Time: 4166.738 ms (00:04.167) SELECT SUM(num1*num2) FROM bench_mul_var; -- v2 patch Time: 4398.812 ms (00:04.399) Time: 3672.668 ms (00:03.673) Time: 3650.227 ms (00:03.650) Time: 3611.420 ms (00:03.611) Time: 3534.218 ms (00:03.534) SELECT SUM(num1*num2) FROM bench_mul_var; -- this patch Time: 3350.596 ms (00:03.351) Time: 3336.224 ms (00:03.336) Time: 3335.599 ms (00:03.336) Time: 3336.990 ms (00:03.337) Time: 3351.453 ms (00:03.351) (This was on an older Intel Core i9-9900K, so I'm not sure why all the timings are faster. What compiler settings are you using?) The approach taken in this patch only uses 32-bit integers, so in theory it could be extended to work for var1ndigits = 3, 4, or even more, but the code would get increasingly complex, and I ran out of steam at 2 digits. It might be worth trying though. Regards, Dean diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c new file mode 100644 index 5510a20..adbfd5c --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -8748,6 +8748,74 @@ mul_var(const NumericVar *var1, const Nu } /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 2) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + + for (i = res_ndigits - 4; i > 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + + /* * We do the arithmetic in an array "dig[]" of signed int's. Since * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom * to avoid normalizing carries immediately. Attachments: [text/plain] optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt (2.4K, ../../CAEZATCV2qPTGo2Fd8xDs06Q7iU5aorgSa9+Fw9zkuQv1y15rcw@mail.gmail.com/2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt) download | inline diff: diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c new file mode 100644 index 5510a20..adbfd5c --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -8748,6 +8748,74 @@ mul_var(const NumericVar *var1, const Nu } /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 2) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + + for (i = res_ndigits - 4; i > 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + + /* * We do the arithmetic in an array "dig[]" of signed int's. Since * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom * to avoid normalizing carries immediately. ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 07:49 Joel Jacobson <[email protected]> parent: Dean Rasheed <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 07:49 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 00:19, Dean Rasheed wrote: > I had a play with this, and came up with a slightly different way of > doing it that works for var2 of any size, as long as var1 is just 1 or > 2 digits. > > Repeating your benchmark where both numbers have up to 2 NBASE-digits, > this new approach was slightly faster: > ... > > (This was on an older Intel Core i9-9900K, so I'm not sure why all the > timings are faster. What compiler settings are you using?) Strange. I just did `./configure` with a --prefix. Compiler settings on my Intel Core i9-14900K machine: $ pg_config | grep -E '^(CC|CFLAGS|CPPFLAGS|LDFLAGS)' CC = gcc CPPFLAGS = -D_GNU_SOURCE CFLAGS = -Wall -Wmissing-prototypes -Wpointer-arith -Wdeclaration-after-statement -Werror=vla -Wendif-labels -Wmissing-format-attribute -Wimplicit-fallthrough=3 -Wcast-function-type -Wshadow=compatible-local -Wformat-security -fno-strict-aliasing -fwrapv -fexcess-precision=standard -Wno-format-truncation -Wno-stringop-truncation -O2 CFLAGS_SL = -fPIC LDFLAGS = -Wl,--as-needed -Wl,-rpath,'/home/joel/pg-dev/lib',--enable-new-dtags LDFLAGS_EX = LDFLAGS_SL = > The approach taken in this patch only uses 32-bit integers, so in > theory it could be extended to work for var1ndigits = 3, 4, or even > more, but the code would get increasingly complex, and I ran out of > steam at 2 digits. It might be worth trying though. > > Regards, > Dean > > Attachments: > * optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt Really nice! I've benchmarked your patch on my three machines with great results. I added a setseed() step, to make the benchmarks reproducible, shouldn't matter much since it should statistically average out, but I thought why not. CREATE TABLE bench_mul_var (num1 numeric, num2 numeric); SELECT setseed(0.12345); INSERT INTO bench_mul_var (num1, num2) SELECT random(0::numeric,1e8::numeric), random(0::numeric,1e8::numeric) FROM generate_series(1,1e8); \timing /* * Apple M3 Max */ SELECT SUM(num1*num2) FROM bench_mul_var; -- HEAD Time: 3622.342 ms (00:03.622) Time: 3029.786 ms (00:03.030) Time: 3046.497 ms (00:03.046) Time: 3035.910 ms (00:03.036) Time: 3034.073 ms (00:03.034) SELECT SUM(num1*num2) FROM bench_mul_var; -- optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt Time: 2484.685 ms (00:02.485) Time: 2478.341 ms (00:02.478) Time: 2494.397 ms (00:02.494) Time: 2470.987 ms (00:02.471) Time: 2490.215 ms (00:02.490) /* * Intel Core i9-14900K */ SELECT SUM(num1*num2) FROM bench_mul_var; -- HEAD Time: 2555.569 ms (00:02.556) Time: 2523.145 ms (00:02.523) Time: 2518.671 ms (00:02.519) Time: 2514.501 ms (00:02.515) Time: 2516.919 ms (00:02.517) SELECT SUM(num1*num2) FROM bench_mul_var; -- optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt Time: 2246.441 ms (00:02.246) Time: 2243.900 ms (00:02.244) Time: 2245.350 ms (00:02.245) Time: 2245.080 ms (00:02.245) Time: 2247.856 ms (00:02.248) /* * AMD Ryzen 9 7950X3D */ SELECT SUM(num1*num2) FROM bench_mul_var; -- HEAD Time: 3037.497 ms (00:03.037) Time: 3010.037 ms (00:03.010) Time: 3000.956 ms (00:03.001) Time: 2989.424 ms (00:02.989) Time: 2984.911 ms (00:02.985) SELECT SUM(num1*num2) FROM bench_mul_var; -- optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt Time: 2645.530 ms (00:02.646) Time: 2640.472 ms (00:02.640) Time: 2638.613 ms (00:02.639) Time: 2637.889 ms (00:02.638) Time: 2638.054 ms (00:02.638) /Joel ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 08:22 Dean Rasheed <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Dean Rasheed @ 2024-07-02 08:22 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, 2 Jul 2024 at 08:50, Joel Jacobson <[email protected]> wrote: > > On Tue, Jul 2, 2024, at 00:19, Dean Rasheed wrote: > > > Attachments: > > * optimize-numeric-mul_var-small-var1-arbitrary-var2.patch.txt > Shortly after posting that, I realised that there was a small bug. This bit: case 2: newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; isn't quite right in the case where rscale is less than the full result. In that case, the least significant result digit has a contribution from one more var2 digit, so it needs to be: newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; if (res_ndigits - 3 < var2ndigits) newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; That doesn't noticeably affect the performance though. Update attached. > I've benchmarked your patch on my three machines with great results. > I added a setseed() step, to make the benchmarks reproducible, > shouldn't matter much since it should statistically average out, but I thought why not. Nice. The results on the Apple M3 Max look particularly impressive. I think it'd probably be worth trying to extend this to 3 or maybe 4 var1 digits, since that would cover a lot of "everyday" sized numeric values that a lot of people might be using. I don't think we should go beyond that though. Regards, Dean Attachments: [text/x-patch] v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch (2.5K, ../../CAEZATCWEou=NjpvS-r1WxymbAYihsdKQoQBj1HfBeocoNcv5Ww@mail.gmail.com/2-v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch) download | inline diff: diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c new file mode 100644 index 5510a20..f77ad8b --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -8748,6 +8748,76 @@ mul_var(const NumericVar *var1, const Nu } /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 2) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + + for (i = res_ndigits - 4; i > 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + + /* * We do the arithmetic in an array "dig[]" of signed int's. Since * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom * to avoid normalizing carries immediately. ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 09:05 Joel Jacobson <[email protected]> parent: Dean Rasheed <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 09:05 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 10:22, Dean Rasheed wrote: > Shortly after posting that, I realised that there was a small bug. This bit: > > case 2: > newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; > > isn't quite right in the case where rscale is less than the full > result. In that case, the least significant result digit has a > contribution from one more var2 digit, so it needs to be: > > newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; > if (res_ndigits - 3 < var2ndigits) > newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; > > That doesn't noticeably affect the performance though. Update attached. Nice catch. Could we add a test somehow that would test mul_var() with rscale less than the full result, that would catch bugs like this one and others? I created a new benchmark, that specifically tests different var1ndigits. I've only run it on Apple M3 Max yet. More to come. \timing SELECT setseed(0.12345); CREATE TABLE bench_mul_var_var1ndigits_1 (var1 numeric, var2 numeric); INSERT INTO bench_mul_var_var1ndigits_1 (var1, var2) SELECT random(0::numeric,9999::numeric), random(10000000::numeric,1e32::numeric) FROM generate_series(1,1e8); CREATE TABLE bench_mul_var_var1ndigits_2 (var1 numeric, var2 numeric); INSERT INTO bench_mul_var_var1ndigits_2 (var1, var2) SELECT random(10000000::numeric,99999999::numeric), random(100000000000::numeric,1e32::numeric) FROM generate_series(1,1e8); CREATE TABLE bench_mul_var_var1ndigits_3 (var1 numeric, var2 numeric); INSERT INTO bench_mul_var_var1ndigits_3 (var1, var2) SELECT random(100000000000::numeric,999999999999::numeric), random(1000000000000000::numeric,1e32::numeric) FROM generate_series(1,1e8); CREATE TABLE bench_mul_var_var1ndigits_4 (var1 numeric, var2 numeric); INSERT INTO bench_mul_var_var1ndigits_4 (var1, var2) SELECT random(1000000000000000::numeric,9999999999999999::numeric), random(10000000000000000000::numeric,1e32::numeric) FROM generate_series(1,1e8); /* * Apple M3 Max */ SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- HEAD Time: 2986.952 ms (00:02.987) Time: 2991.765 ms (00:02.992) Time: 2987.253 ms (00:02.987) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_1; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 2874.841 ms (00:02.875) Time: 2883.070 ms (00:02.883) Time: 2899.973 ms (00:02.900) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- HEAD Time: 3459.556 ms (00:03.460) Time: 3304.983 ms (00:03.305) Time: 3299.728 ms (00:03.300) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_2; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3053.140 ms (00:03.053) Time: 3065.227 ms (00:03.065) Time: 3069.995 ms (00:03.070) /* * Just for completeness, also testing var1ndigits 3 and 4, * although no change is expected since not yet implemented. */ SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD Time: 3809.005 ms (00:03.809) Time: 3438.260 ms (00:03.438) Time: 3453.920 ms (00:03.454) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3437.592 ms (00:03.438) Time: 3457.586 ms (00:03.458) Time: 3474.344 ms (00:03.474) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- HEAD Time: 4133.193 ms (00:04.133) Time: 3554.477 ms (00:03.554) Time: 3560.855 ms (00:03.561) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_4; -- v2-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3508.540 ms (00:03.509) Time: 3566.721 ms (00:03.567) Time: 3524.083 ms (00:03.524) > I think it'd probably be worth trying to extend this to 3 or maybe 4 > var1 digits, since that would cover a lot of "everyday" sized numeric > values that a lot of people might be using. I don't think we should go > beyond that though. I think so too. I'm working on var1ndigits=3 now. /Joel ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 10:23 Joel Jacobson <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 10:23 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 11:05, Joel Jacobson wrote: > On Tue, Jul 2, 2024, at 10:22, Dean Rasheed wrote: >> Shortly after posting that, I realised that there was a small bug. This bit: >> >> case 2: >> newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; >> >> isn't quite right in the case where rscale is less than the full >> result. In that case, the least significant result digit has a >> contribution from one more var2 digit, so it needs to be: >> >> newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; >> if (res_ndigits - 3 < var2ndigits) >> newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; >> Just to be able to verify mul_var() is working as expected when rscale is less than the full result, I've added a numeric_mul_patched() function that takes a third rscale_adjustment parameter: I've tried to get a different result with and without the fix, but I'm failing to hit the bug. Can you think of an example that should trigger the bug? Example usage: SELECT numeric_mul_patched(9999.999,2,0); var1ndigits=1 var2ndigits=2 rscale=3 numeric_mul_patched --------------------- 19999.998 (1 row) SELECT numeric_mul_patched(9999.999,2,1); var1ndigits=1 var2ndigits=2 rscale=4 numeric_mul_patched --------------------- 19999.9980 (1 row) SELECT numeric_mul_patched(9999.999,2,-1); var1ndigits=1 var2ndigits=2 rscale=2 numeric_mul_patched --------------------- 20000.00 (1 row) SELECT numeric_mul_patched(9999.999,2,-2); var1ndigits=1 var2ndigits=2 rscale=1 numeric_mul_patched --------------------- 20000.0 (1 row) /Joel ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 11:44 Dean Rasheed <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Dean Rasheed @ 2024-07-02 11:44 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, 2 Jul 2024 at 11:23, Joel Jacobson <[email protected]> wrote: > > Just to be able to verify mul_var() is working as expected when > rscale is less than the full result, I've added a numeric_mul_patched() > function that takes a third rscale_adjustment parameter: Yeah, we could expose such a function, and maybe it would be generally useful, not just for testing, but that's really a separate proposal. In general, mul_var() with reduced rscale doesn't guarantee correctly rounded results though, which might make it less generally acceptable. For this patch though, the aim is just to ensure the results are the same as before. > I've tried to get a different result with and without the fix, > but I'm failing to hit the bug. > > Can you think of an example that should trigger the bug? 9999.0001 * 5000.9999_9999 with rscale = 0 triggers it (returned 50004999 instead of 50005000). Regards, Dean ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 16:20 Joel Jacobson <[email protected]> parent: Dean Rasheed <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 16:20 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 13:44, Dean Rasheed wrote: >> Can you think of an example that should trigger the bug? > > 9999.0001 * 5000.9999_9999 with rscale = 0 triggers it (returned > 50004999 instead of 50005000). Thanks, helpful. Attached patch adds the var1ndigits=3 case. Benchmark: /* * Apple M3 Max */ SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD Time: 3809.005 ms (00:03.809) Time: 3438.260 ms (00:03.438) Time: 3453.920 ms (00:03.454) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3230.017 ms (00:03.230) Time: 3244.094 ms (00:03.244) Time: 3246.370 ms (00:03.246) /* * Intel Core i9-14900K */ SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD Time: 4082.759 ms (00:04.083) Time: 4077.372 ms (00:04.077) Time: 4080.830 ms (00:04.081) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3989.021 ms (00:03.989) Time: 3978.263 ms (00:03.978) Time: 3955.331 ms (00:03.955) /* * AMD Ryzen 9 7950X3D */ SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- HEAD Time: 3791.271 ms (00:03.791) Time: 3760.138 ms (00:03.760) Time: 3758.773 ms (00:03.759) SELECT SUM(var1*var2) FROM bench_mul_var_var1ndigits_3; -- v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Time: 3400.824 ms (00:03.401) Time: 3373.714 ms (00:03.374) Time: 3345.505 ms (00:03.346) Regards, Joel Attachments: [application/octet-stream] v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch (4.1K, ../../[email protected]/2-v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch) download | inline diff: From ece9611d080f0c048cef6e413f4a5e51683ec177 Mon Sep 17 00:00:00 2001 From: Joel Jakobsson <[email protected]> Date: Tue, 2 Jul 2024 17:54:25 +0200 Subject: [PATCH] numeric: Simplified fast-path computation for mul_var() --- src/backend/utils/adt/numeric.c | 100 ++++++++++++++++++++++++++++++++ 1 file changed, 100 insertions(+) diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5510a203b0..0fb217f6e9 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -8747,6 +8747,106 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, return; } + /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 3) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 1; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + + case 3: + newdig = (int) var1digits[2] * var2digits[res_ndigits - 5]; + if (res_ndigits - 4 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 2; i--) + { + newdig = carry; + if (i < var2ndigits) + newdig += (int) var1digits[0] * var2digits[i]; + if (i - 1 >= 0 && i - 1 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[i - 1]; + if (i - 2 >= 0 && i - 2 < var2ndigits) + newdig += (int) var1digits[2] * var2digits[i - 2]; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = carry; + if (var2ndigits > 1) + newdig += (int) var1digits[0] * var2digits[1]; + if (var2ndigits > 0) + newdig += (int) var1digits[1] * var2digits[0]; + res_digits[2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + /* * We do the arithmetic in an array "dig[]" of signed int's. Since * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom -- 2.45.1 ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 18:53 Joel Jacobson <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 18:53 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 18:20, Joel Jacobson wrote: > * v3-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch Hmm, v3 contains a bug which I haven't been able to solve yet. Reporting now to avoid time waste reviewing it since it's buggy. The attached patch is how I tested and found the bug. It contains a file test-mul-var.sql, which tests mul_var() with varying rscale, using the SQL-callable numeric_mul_patched(), which third argument is the rscale_adjustment. Out of 2481600 random tests, all passed except 4: SELECT result = numeric_mul_patched(var1,var2,rscale_adjustment), COUNT(*) FROM test_numeric_mul_patched GROUP BY 1 ORDER BY 1; ?column? | count ----------+--------- f | 4 t | 2481596 (2 rows) SELECT var1, var2, var1*var2 AS full_resolution, rscale_adjustment, result AS expected, numeric_mul_patched(var1,var2,rscale_adjustment) AS actual FROM test_numeric_mul_patched WHERE result <> numeric_mul_patched(var1,var2,rscale_adjustment); var1 | var2 | full_resolution | rscale_adjustment | expected | actual -------------------+----------------+---------------------------+-------------------+----------+-------- 676.797214075 | 0.308068877759 | 208.500158210502929257925 | -21 | 209 | 208 555.07029 | 0.381033094735 | 211.50015039415392315 | -17 | 212 | 211 0.476637718921 | 66.088276 | 31.500165120061470196 | -18 | 32 | 31 0.060569165063082 | 998.85933 | 60.50007563356949425506 | -20 | 61 | 60 (4 rows) Trying to wrap my head around what could cause this. It's rounding down instead of up, and these cases all end with decimal .500XXXX. Regards, Joel From 074aeb223ab496f23c2075eabd35e6e76241d1d8 Mon Sep 17 00:00:00 2001 From: Joel Jakobsson <[email protected]> Date: Mon, 1 Jul 2024 07:17:50 +0200 Subject: [PATCH] Add SQL-callable numeric_mul_patched() to bench Simplified fast-path computation --- src/backend/utils/adt/numeric.c | 438 ++++++++++++++++++++++++++++++++ src/include/catalog/pg_proc.dat | 3 + src/include/utils/numeric.h | 2 + test-mul-var.sql | 48 ++++ 4 files changed, 491 insertions(+) create mode 100644 test-mul-var.sql diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5510a203b0..8f5d553f15 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -551,6 +551,9 @@ static void sub_var(const NumericVar *var1, const NumericVar *var2, static void mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale); +static void mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, + int rscale); static void div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale, bool round); @@ -3115,6 +3118,131 @@ numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error) } +/* + * numeric_mul_patched() - + * + * This function multiplies two numeric values using the patched algorithm, + * designed for efficient handling of large numbers. It's introduced to allow + * direct benchmark comparisons with the standard numeric_mul() function. + */ +Datum +numeric_mul_patched(PG_FUNCTION_ARGS) +{ + Numeric num1 = PG_GETARG_NUMERIC(0); + Numeric num2 = PG_GETARG_NUMERIC(1); + int32 rscale_adjustment = PG_GETARG_INT32(2); + Numeric res; + + res = numeric_mul_patched_opt_error(num1, num2, rscale_adjustment, NULL); + + PG_RETURN_NUMERIC(res); +} + + +/* + * numeric_mul_patched_opt_error() - + * + * Internal version of numeric_mul_patched(). + * If "*have_error" flag is provided, on error it's set to true, NULL returned. + * This is helpful when caller need to handle errors by itself. + */ +Numeric +numeric_mul_patched_opt_error(Numeric num1, Numeric num2, int32 rscale_adjustment, bool *have_error) +{ + NumericVar arg1; + NumericVar arg2; + NumericVar result; + Numeric res; + + /* + * Handle NaN and infinities + */ + if (NUMERIC_IS_SPECIAL(num1) || NUMERIC_IS_SPECIAL(num2)) + { + if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2)) + return make_result(&const_nan); + if (NUMERIC_IS_PINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* Inf * 0 */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + if (NUMERIC_IS_NINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* -Inf * 0 */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + /* by here, num1 must be finite, so num2 is not */ + if (NUMERIC_IS_PINF(num2)) + { + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * Inf */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + Assert(NUMERIC_IS_NINF(num2)); + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * -Inf */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + + /* + * Unpack the values, let mul_var() compute the result and return it. + * Unlike add_var() and sub_var(), mul_var() will round its result. In the + * case of numeric_mul(), which is invoked for the * operator on numerics, + * we request exact representation for the product (rscale = sum(dscale of + * arg1, dscale of arg2)). If the exact result has more digits after the + * decimal point than can be stored in a numeric, we round it. Rounding + * after computing the exact result ensures that the final result is + * correctly rounded (rounding in mul_var() using a truncated product + * would not guarantee this). + */ + init_var_from_num(num1, &arg1); + init_var_from_num(num2, &arg2); + + init_var(&result); + + mul_var_patched(&arg1, &arg2, &result, arg1.dscale + arg2.dscale + rscale_adjustment); + + if (result.dscale > NUMERIC_DSCALE_MAX) + round_var(&result, NUMERIC_DSCALE_MAX); + + res = make_result_opt_error(&result, have_error); + + free_var(&result); + + return res; +} + + /* * numeric_div() - * @@ -8864,6 +8992,316 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, strip_var(result); } +/* + * mul_var_patched() - + * + * Implements patched multiplication for large numbers, introduced + * alongside the unchanged original mul_var(). This function is part of + * an optimization effort, allowing direct benchmark comparisons with + * mul_var(). It selects full or half patched based on input size. + * This is a temporary measure before considering its replacement of + * mul_var() based on benchmark outcomes. + */ +static void +mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, int rscale) +{ + int res_ndigits; + int res_sign; + int res_weight; + int maxdigits; + int *dig; + int carry; + int maxdig; + int newdig; + int var1ndigits; + int var2ndigits; + NumericDigit *var1digits; + NumericDigit *var2digits; + NumericDigit *res_digits; + int i, + i1, + i2; + + /* + * Arrange for var1 to be the shorter of the two numbers. This improves + * performance because the inner multiplication loop is much simpler than + * the outer loop, so it's better to have a smaller number of iterations + * of the outer loop. This also reduces the number of times that the + * accumulator array needs to be normalized. + */ + if (var1->ndigits > var2->ndigits) + { + const NumericVar *tmp = var1; + + var1 = var2; + var2 = tmp; + } + + /* copy these values into local vars for speed in inner loop */ + var1ndigits = var1->ndigits; + var2ndigits = var2->ndigits; + var1digits = var1->digits; + var2digits = var2->digits; + + if (var1ndigits == 0 || var2ndigits == 0) + { + /* one or both inputs is zero; so is result */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* Determine result sign and (maximum possible) weight */ + if (var1->sign == var2->sign) + res_sign = NUMERIC_POS; + else + res_sign = NUMERIC_NEG; + res_weight = var1->weight + var2->weight + 2; + + /* + * Determine the number of result digits to compute. If the exact result + * would have more than rscale fractional digits, truncate the computation + * with MUL_GUARD_DIGITS guard digits, i.e., ignore input digits that + * would only contribute to the right of that. (This will give the exact + * rounded-to-rscale answer unless carries out of the ignored positions + * would have propagated through more than MUL_GUARD_DIGITS digits.) + * + * Note: an exact computation could not produce more than var1ndigits + + * var2ndigits digits, but we allocate one extra output digit in case + * rscale-driven rounding produces a carry out of the highest exact digit. + */ + res_ndigits = var1ndigits + var2ndigits + 1; + maxdigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS + + MUL_GUARD_DIGITS; + res_ndigits = Min(res_ndigits, maxdigits); + + if (res_ndigits < 3) + { + /* All input digits will be ignored; so result is zero */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 3) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 1; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + + case 3: + newdig = (int) var1digits[2] * var2digits[res_ndigits - 5]; + if (res_ndigits - 4 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 2; i--) + { + newdig = carry; + if (i < var2ndigits) + newdig += (int) var1digits[0] * var2digits[i]; + if (i - 1 >= 0 && i - 1 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[i - 1]; + if (i - 2 >= 0 && i - 2 < var2ndigits) + newdig += (int) var1digits[2] * var2digits[i - 2]; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = carry; + if (var2ndigits > 1) + newdig += (int) var1digits[0] * var2digits[1]; + if (var2ndigits > 0) + newdig += (int) var1digits[1] * var2digits[0]; + res_digits[2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + + /* + * We do the arithmetic in an array "dig[]" of signed int's. Since + * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom + * to avoid normalizing carries immediately. + * + * maxdig tracks the maximum possible value of any dig[] entry; when this + * threatens to exceed INT_MAX, we take the time to propagate carries. + * Furthermore, we need to ensure that overflow doesn't occur during the + * carry propagation passes either. The carry values could be as much as + * INT_MAX/NBASE, so really we must normalize when digits threaten to + * exceed INT_MAX - INT_MAX/NBASE. + * + * To avoid overflow in maxdig itself, it actually represents the max + * possible value divided by NBASE-1, ie, at the top of the loop it is + * known that no dig[] entry exceeds maxdig * (NBASE-1). + */ + dig = (int *) palloc0(res_ndigits * sizeof(int)); + maxdig = 0; + + /* + * The least significant digits of var1 should be ignored if they don't + * contribute directly to the first res_ndigits digits of the result that + * we are computing. + * + * Digit i1 of var1 and digit i2 of var2 are multiplied and added to digit + * i1+i2+2 of the accumulator array, so we need only consider digits of + * var1 for which i1 <= res_ndigits - 3. + */ + for (i1 = Min(var1ndigits - 1, res_ndigits - 3); i1 >= 0; i1--) + { + NumericDigit var1digit = var1digits[i1]; + + if (var1digit == 0) + continue; + + /* Time to normalize? */ + maxdig += var1digit; + if (maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1)) + { + /* Yes, do it */ + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + dig[i] = newdig; + } + Assert(carry == 0); + /* Reset maxdig to indicate new worst-case */ + maxdig = 1 + var1digit; + } + + /* + * Add the appropriate multiple of var2 into the accumulator. + * + * As above, digits of var2 can be ignored if they don't contribute, + * so we only include digits for which i1+i2+2 < res_ndigits. + * + * This inner loop is the performance bottleneck for multiplication, + * so we want to keep it simple enough so that it can be + * auto-vectorized. Accordingly, process the digits left-to-right + * even though schoolbook multiplication would suggest right-to-left. + * Since we aren't propagating carries in this loop, the order does + * not matter. + */ + { + int i2limit = Min(var2ndigits, res_ndigits - i1 - 2); + int *dig_i1_2 = &dig[i1 + 2]; + + for (i2 = 0; i2 < i2limit; i2++) + dig_i1_2[i2] += var1digit * var2digits[i2]; + } + } + + /* + * Now we do a final carry propagation pass to normalize the result, which + * we combine with storing the result digits into the output. Note that + * this is still done at full precision w/guard digits. + */ + alloc_var(result, res_ndigits); + res_digits = result->digits; + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + res_digits[i] = newdig; + } + Assert(carry == 0); + + pfree(dig); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + +} + /* * div_var() - diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index d4ac578ae6..5b3024cb6d 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -4465,6 +4465,9 @@ { oid => '1726', proname => 'numeric_mul', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_mul' }, +{ oid => '6347', + proname => 'numeric_mul_patched', prorettype => 'numeric', + proargtypes => 'numeric numeric int4', prosrc => 'numeric_mul_patched' }, { oid => '1727', proname => 'numeric_div', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_div' }, diff --git a/src/include/utils/numeric.h b/src/include/utils/numeric.h index 43c75c436f..454a56da9a 100644 --- a/src/include/utils/numeric.h +++ b/src/include/utils/numeric.h @@ -97,6 +97,8 @@ extern Numeric numeric_sub_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error); +extern Numeric numeric_mul_patched_opt_error(Numeric num1, Numeric num2, + int32 rscale_adjustment, bool *have_error); extern Numeric numeric_div_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mod_opt_error(Numeric num1, Numeric num2, diff --git a/test-mul-var.sql b/test-mul-var.sql new file mode 100644 index 0000000000..ee7e3855bc --- /dev/null +++ b/test-mul-var.sql @@ -0,0 +1,48 @@ +CREATE TABLE test_numeric_mul_patched ( + var1 numeric, + var2 numeric, + rscale_adjustment int, + result numeric +); + +DO $$ +DECLARE +var1 numeric; +var2 numeric; +BEGIN + FOR i IN 1..100 LOOP + RAISE NOTICE '%', i; + FOR var1ndigits IN 1..4 LOOP + FOR var2ndigits IN 1..4 LOOP + FOR var1dscale IN 0..(var1ndigits*4) LOOP + FOR var2dscale IN 0..(var2ndigits*4) LOOP + FOR rscale_adjustment IN 0..(var1dscale+var2dscale) LOOP + var1 := round(random( + format('1%s',repeat('0',(var1ndigits-1)*4-1))::numeric, + format('%s',repeat('9',var1ndigits*4))::numeric + ) / 10::numeric^var1dscale, var1dscale); + var2 := round(random( + format('1%s',repeat('0',(var2ndigits-1)*4-1))::numeric, + format('%s',repeat('9',var2ndigits*4))::numeric + ) / 10::numeric^var2dscale, var2dscale); + INSERT INTO test_numeric_mul_patched + (var1, var2, rscale_adjustment) + VALUES + (var1, var2, -rscale_adjustment); + END LOOP; + END LOOP; + END LOOP; + END LOOP; + END LOOP; + END LOOP; +END $$; + +-- First, set result with a numeric_mul_patched() version where +-- the Simplified fast-path computation code has been commented out. +UPDATE test_numeric_mul_patched SET result = numeric_mul_patched(var1, var2, rscale_adjustment); + +-- Then, recompile with the Simplified fast-path computation code, +-- and check if any differences can be found: +SELECT *, numeric_mul_patched(var1,var2,rscale_adjustment) +FROM test_numeric_mul_patched +WHERE result IS DISTINCT FROM numeric_mul_patched(var1,var2,rscale_adjustment); -- 2.45.1 Attachments: [text/plain] numeric_mul_patched.txt (17.5K, ../../[email protected]/2-numeric_mul_patched.txt) download | inline diff: From 074aeb223ab496f23c2075eabd35e6e76241d1d8 Mon Sep 17 00:00:00 2001 From: Joel Jakobsson <[email protected]> Date: Mon, 1 Jul 2024 07:17:50 +0200 Subject: [PATCH] Add SQL-callable numeric_mul_patched() to bench Simplified fast-path computation --- src/backend/utils/adt/numeric.c | 438 ++++++++++++++++++++++++++++++++ src/include/catalog/pg_proc.dat | 3 + src/include/utils/numeric.h | 2 + test-mul-var.sql | 48 ++++ 4 files changed, 491 insertions(+) create mode 100644 test-mul-var.sql diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c index 5510a203b0..8f5d553f15 100644 --- a/src/backend/utils/adt/numeric.c +++ b/src/backend/utils/adt/numeric.c @@ -551,6 +551,9 @@ static void sub_var(const NumericVar *var1, const NumericVar *var2, static void mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale); +static void mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, + int rscale); static void div_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, int rscale, bool round); @@ -3115,6 +3118,131 @@ numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error) } +/* + * numeric_mul_patched() - + * + * This function multiplies two numeric values using the patched algorithm, + * designed for efficient handling of large numbers. It's introduced to allow + * direct benchmark comparisons with the standard numeric_mul() function. + */ +Datum +numeric_mul_patched(PG_FUNCTION_ARGS) +{ + Numeric num1 = PG_GETARG_NUMERIC(0); + Numeric num2 = PG_GETARG_NUMERIC(1); + int32 rscale_adjustment = PG_GETARG_INT32(2); + Numeric res; + + res = numeric_mul_patched_opt_error(num1, num2, rscale_adjustment, NULL); + + PG_RETURN_NUMERIC(res); +} + + +/* + * numeric_mul_patched_opt_error() - + * + * Internal version of numeric_mul_patched(). + * If "*have_error" flag is provided, on error it's set to true, NULL returned. + * This is helpful when caller need to handle errors by itself. + */ +Numeric +numeric_mul_patched_opt_error(Numeric num1, Numeric num2, int32 rscale_adjustment, bool *have_error) +{ + NumericVar arg1; + NumericVar arg2; + NumericVar result; + Numeric res; + + /* + * Handle NaN and infinities + */ + if (NUMERIC_IS_SPECIAL(num1) || NUMERIC_IS_SPECIAL(num2)) + { + if (NUMERIC_IS_NAN(num1) || NUMERIC_IS_NAN(num2)) + return make_result(&const_nan); + if (NUMERIC_IS_PINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* Inf * 0 */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + if (NUMERIC_IS_NINF(num1)) + { + switch (numeric_sign_internal(num2)) + { + case 0: + return make_result(&const_nan); /* -Inf * 0 */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + /* by here, num1 must be finite, so num2 is not */ + if (NUMERIC_IS_PINF(num2)) + { + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * Inf */ + case 1: + return make_result(&const_pinf); + case -1: + return make_result(&const_ninf); + } + Assert(false); + } + Assert(NUMERIC_IS_NINF(num2)); + switch (numeric_sign_internal(num1)) + { + case 0: + return make_result(&const_nan); /* 0 * -Inf */ + case 1: + return make_result(&const_ninf); + case -1: + return make_result(&const_pinf); + } + Assert(false); + } + + /* + * Unpack the values, let mul_var() compute the result and return it. + * Unlike add_var() and sub_var(), mul_var() will round its result. In the + * case of numeric_mul(), which is invoked for the * operator on numerics, + * we request exact representation for the product (rscale = sum(dscale of + * arg1, dscale of arg2)). If the exact result has more digits after the + * decimal point than can be stored in a numeric, we round it. Rounding + * after computing the exact result ensures that the final result is + * correctly rounded (rounding in mul_var() using a truncated product + * would not guarantee this). + */ + init_var_from_num(num1, &arg1); + init_var_from_num(num2, &arg2); + + init_var(&result); + + mul_var_patched(&arg1, &arg2, &result, arg1.dscale + arg2.dscale + rscale_adjustment); + + if (result.dscale > NUMERIC_DSCALE_MAX) + round_var(&result, NUMERIC_DSCALE_MAX); + + res = make_result_opt_error(&result, have_error); + + free_var(&result); + + return res; +} + + /* * numeric_div() - * @@ -8864,6 +8992,316 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result, strip_var(result); } +/* + * mul_var_patched() - + * + * Implements patched multiplication for large numbers, introduced + * alongside the unchanged original mul_var(). This function is part of + * an optimization effort, allowing direct benchmark comparisons with + * mul_var(). It selects full or half patched based on input size. + * This is a temporary measure before considering its replacement of + * mul_var() based on benchmark outcomes. + */ +static void +mul_var_patched(const NumericVar *var1, const NumericVar *var2, + NumericVar *result, int rscale) +{ + int res_ndigits; + int res_sign; + int res_weight; + int maxdigits; + int *dig; + int carry; + int maxdig; + int newdig; + int var1ndigits; + int var2ndigits; + NumericDigit *var1digits; + NumericDigit *var2digits; + NumericDigit *res_digits; + int i, + i1, + i2; + + /* + * Arrange for var1 to be the shorter of the two numbers. This improves + * performance because the inner multiplication loop is much simpler than + * the outer loop, so it's better to have a smaller number of iterations + * of the outer loop. This also reduces the number of times that the + * accumulator array needs to be normalized. + */ + if (var1->ndigits > var2->ndigits) + { + const NumericVar *tmp = var1; + + var1 = var2; + var2 = tmp; + } + + /* copy these values into local vars for speed in inner loop */ + var1ndigits = var1->ndigits; + var2ndigits = var2->ndigits; + var1digits = var1->digits; + var2digits = var2->digits; + + if (var1ndigits == 0 || var2ndigits == 0) + { + /* one or both inputs is zero; so is result */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* Determine result sign and (maximum possible) weight */ + if (var1->sign == var2->sign) + res_sign = NUMERIC_POS; + else + res_sign = NUMERIC_NEG; + res_weight = var1->weight + var2->weight + 2; + + /* + * Determine the number of result digits to compute. If the exact result + * would have more than rscale fractional digits, truncate the computation + * with MUL_GUARD_DIGITS guard digits, i.e., ignore input digits that + * would only contribute to the right of that. (This will give the exact + * rounded-to-rscale answer unless carries out of the ignored positions + * would have propagated through more than MUL_GUARD_DIGITS digits.) + * + * Note: an exact computation could not produce more than var1ndigits + + * var2ndigits digits, but we allocate one extra output digit in case + * rscale-driven rounding produces a carry out of the highest exact digit. + */ + res_ndigits = var1ndigits + var2ndigits + 1; + maxdigits = res_weight + 1 + (rscale + DEC_DIGITS - 1) / DEC_DIGITS + + MUL_GUARD_DIGITS; + res_ndigits = Min(res_ndigits, maxdigits); + + if (res_ndigits < 3) + { + /* All input digits will be ignored; so result is zero */ + zero_var(result); + result->dscale = rscale; + return; + } + + /* + * Simplified fast-path computation, if var1 has just one or two digits. + * This is significantly faster, since it avoids allocating a separate + * digit array, making multiple passes over var2, and having separate + * carry-propagation passes. + */ + if (var1ndigits <= 3) + { + NumericDigit *res_buf; + + /* Allocate result digit array */ + res_buf = digitbuf_alloc(res_ndigits); + res_buf[0] = 0; /* spare digit for later rounding */ + res_digits = res_buf + 1; + + /* + * Compute the result digits directly, in one pass, propagating the + * carry up as we go. + */ + switch (var1ndigits) + { + case 1: + carry = 0; + for (i = res_ndigits - 3; i >= 0; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + res_digits[0] = (NumericDigit) carry; + break; + + case 2: + newdig = (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 1; i--) + { + newdig = (int) var1digits[0] * var2digits[i] + + (int) var1digits[1] * var2digits[i - 1] + carry; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + + case 3: + newdig = (int) var1digits[2] * var2digits[res_ndigits - 5]; + if (res_ndigits - 4 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[res_ndigits - 4]; + if (res_ndigits - 3 < var2ndigits) + newdig += (int) var1digits[0] * var2digits[res_ndigits - 3]; + res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + for (i = res_ndigits - 4; i >= 2; i--) + { + newdig = carry; + if (i < var2ndigits) + newdig += (int) var1digits[0] * var2digits[i]; + if (i - 1 >= 0 && i - 1 < var2ndigits) + newdig += (int) var1digits[1] * var2digits[i - 1]; + if (i - 2 >= 0 && i - 2 < var2ndigits) + newdig += (int) var1digits[2] * var2digits[i - 2]; + res_digits[i + 1] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + } + newdig = carry; + if (var2ndigits > 1) + newdig += (int) var1digits[0] * var2digits[1]; + if (var2ndigits > 0) + newdig += (int) var1digits[1] * var2digits[0]; + res_digits[2] = (NumericDigit) (newdig % NBASE); + carry = newdig / NBASE; + newdig = (int) var1digits[0] * var2digits[0] + carry; + res_digits[1] = (NumericDigit) (newdig % NBASE); + res_digits[0] = (NumericDigit) (newdig / NBASE); + break; + } + + /* Store the product in result (minus extra rounding digit) */ + digitbuf_free(result->buf); + result->ndigits = res_ndigits - 1; + result->buf = res_buf; + result->digits = res_digits; + result->weight = res_weight - 1; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + + return; + } + + /* + * We do the arithmetic in an array "dig[]" of signed int's. Since + * INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom + * to avoid normalizing carries immediately. + * + * maxdig tracks the maximum possible value of any dig[] entry; when this + * threatens to exceed INT_MAX, we take the time to propagate carries. + * Furthermore, we need to ensure that overflow doesn't occur during the + * carry propagation passes either. The carry values could be as much as + * INT_MAX/NBASE, so really we must normalize when digits threaten to + * exceed INT_MAX - INT_MAX/NBASE. + * + * To avoid overflow in maxdig itself, it actually represents the max + * possible value divided by NBASE-1, ie, at the top of the loop it is + * known that no dig[] entry exceeds maxdig * (NBASE-1). + */ + dig = (int *) palloc0(res_ndigits * sizeof(int)); + maxdig = 0; + + /* + * The least significant digits of var1 should be ignored if they don't + * contribute directly to the first res_ndigits digits of the result that + * we are computing. + * + * Digit i1 of var1 and digit i2 of var2 are multiplied and added to digit + * i1+i2+2 of the accumulator array, so we need only consider digits of + * var1 for which i1 <= res_ndigits - 3. + */ + for (i1 = Min(var1ndigits - 1, res_ndigits - 3); i1 >= 0; i1--) + { + NumericDigit var1digit = var1digits[i1]; + + if (var1digit == 0) + continue; + + /* Time to normalize? */ + maxdig += var1digit; + if (maxdig > (INT_MAX - INT_MAX / NBASE) / (NBASE - 1)) + { + /* Yes, do it */ + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + dig[i] = newdig; + } + Assert(carry == 0); + /* Reset maxdig to indicate new worst-case */ + maxdig = 1 + var1digit; + } + + /* + * Add the appropriate multiple of var2 into the accumulator. + * + * As above, digits of var2 can be ignored if they don't contribute, + * so we only include digits for which i1+i2+2 < res_ndigits. + * + * This inner loop is the performance bottleneck for multiplication, + * so we want to keep it simple enough so that it can be + * auto-vectorized. Accordingly, process the digits left-to-right + * even though schoolbook multiplication would suggest right-to-left. + * Since we aren't propagating carries in this loop, the order does + * not matter. + */ + { + int i2limit = Min(var2ndigits, res_ndigits - i1 - 2); + int *dig_i1_2 = &dig[i1 + 2]; + + for (i2 = 0; i2 < i2limit; i2++) + dig_i1_2[i2] += var1digit * var2digits[i2]; + } + } + + /* + * Now we do a final carry propagation pass to normalize the result, which + * we combine with storing the result digits into the output. Note that + * this is still done at full precision w/guard digits. + */ + alloc_var(result, res_ndigits); + res_digits = result->digits; + carry = 0; + for (i = res_ndigits - 1; i >= 0; i--) + { + newdig = dig[i] + carry; + if (newdig >= NBASE) + { + carry = newdig / NBASE; + newdig -= carry * NBASE; + } + else + carry = 0; + res_digits[i] = newdig; + } + Assert(carry == 0); + + pfree(dig); + + /* + * Finally, round the result to the requested precision. + */ + result->weight = res_weight; + result->sign = res_sign; + + /* Round to target rscale (and set result->dscale) */ + round_var(result, rscale); + + /* Strip leading and trailing zeroes */ + strip_var(result); + +} + /* * div_var() - diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index d4ac578ae6..5b3024cb6d 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -4465,6 +4465,9 @@ { oid => '1726', proname => 'numeric_mul', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_mul' }, +{ oid => '6347', + proname => 'numeric_mul_patched', prorettype => 'numeric', + proargtypes => 'numeric numeric int4', prosrc => 'numeric_mul_patched' }, { oid => '1727', proname => 'numeric_div', prorettype => 'numeric', proargtypes => 'numeric numeric', prosrc => 'numeric_div' }, diff --git a/src/include/utils/numeric.h b/src/include/utils/numeric.h index 43c75c436f..454a56da9a 100644 --- a/src/include/utils/numeric.h +++ b/src/include/utils/numeric.h @@ -97,6 +97,8 @@ extern Numeric numeric_sub_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mul_opt_error(Numeric num1, Numeric num2, bool *have_error); +extern Numeric numeric_mul_patched_opt_error(Numeric num1, Numeric num2, + int32 rscale_adjustment, bool *have_error); extern Numeric numeric_div_opt_error(Numeric num1, Numeric num2, bool *have_error); extern Numeric numeric_mod_opt_error(Numeric num1, Numeric num2, diff --git a/test-mul-var.sql b/test-mul-var.sql new file mode 100644 index 0000000000..ee7e3855bc --- /dev/null +++ b/test-mul-var.sql @@ -0,0 +1,48 @@ +CREATE TABLE test_numeric_mul_patched ( + var1 numeric, + var2 numeric, + rscale_adjustment int, + result numeric +); + +DO $$ +DECLARE +var1 numeric; +var2 numeric; +BEGIN + FOR i IN 1..100 LOOP + RAISE NOTICE '%', i; + FOR var1ndigits IN 1..4 LOOP + FOR var2ndigits IN 1..4 LOOP + FOR var1dscale IN 0..(var1ndigits*4) LOOP + FOR var2dscale IN 0..(var2ndigits*4) LOOP + FOR rscale_adjustment IN 0..(var1dscale+var2dscale) LOOP + var1 := round(random( + format('1%s',repeat('0',(var1ndigits-1)*4-1))::numeric, + format('%s',repeat('9',var1ndigits*4))::numeric + ) / 10::numeric^var1dscale, var1dscale); + var2 := round(random( + format('1%s',repeat('0',(var2ndigits-1)*4-1))::numeric, + format('%s',repeat('9',var2ndigits*4))::numeric + ) / 10::numeric^var2dscale, var2dscale); + INSERT INTO test_numeric_mul_patched + (var1, var2, rscale_adjustment) + VALUES + (var1, var2, -rscale_adjustment); + END LOOP; + END LOOP; + END LOOP; + END LOOP; + END LOOP; + END LOOP; +END $$; + +-- First, set result with a numeric_mul_patched() version where +-- the Simplified fast-path computation code has been commented out. +UPDATE test_numeric_mul_patched SET result = numeric_mul_patched(var1, var2, rscale_adjustment); + +-- Then, recompile with the Simplified fast-path computation code, +-- and check if any differences can be found: +SELECT *, numeric_mul_patched(var1,var2,rscale_adjustment) +FROM test_numeric_mul_patched +WHERE result IS DISTINCT FROM numeric_mul_patched(var1,var2,rscale_adjustment); -- 2.45.1 ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-02 19:55 Joel Jacobson <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 1 reply; 13+ messages in thread From: Joel Jacobson @ 2024-07-02 19:55 UTC (permalink / raw) To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, Jul 2, 2024, at 20:53, Joel Jacobson wrote: > Trying to wrap my head around what could cause this. > > It's rounding down instead of up, and these cases all end with decimal .500XXXX. Interesting, I actually think there is a bug in the normal mul_var() code. Found a case that rounds down, when it should round up: Calling mul_var() with: var1=51.2945442386599 var2=0.828548712212 rscale=0 returns 42, but I think it should return 43, since 51.2945442386599*0.828548712212=42.5000285724431241296446988 But maybe this is expected and OK, having to do with MUL_GUARD_DIGITS? /Joel ^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. @ 2024-07-03 10:41 Dean Rasheed <[email protected]> parent: Joel Jacobson <[email protected]> 0 siblings, 0 replies; 13+ messages in thread From: Dean Rasheed @ 2024-07-03 10:41 UTC (permalink / raw) To: Joel Jacobson <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers On Tue, 2 Jul 2024 at 20:55, Joel Jacobson <[email protected]> wrote: > > Interesting, I actually think there is a bug in the normal mul_var() code. > Found a case that rounds down, when it should round up: > > Calling mul_var() with: > var1=51.2945442386599 > var2=0.828548712212 > rscale=0 > > returns 42, but I think it should return 43, > since 51.2945442386599*0.828548712212=42.5000285724431241296446988 > > But maybe this is expected and OK, having to do with MUL_GUARD_DIGITS? > No, that's not a bug. It's to be expected. The point of using only MUL_GUARD_DIGITS extra digits is to get the correctly rounded result *most of the time*, while saving a lot of effort by not computing the full result. The callers of mul_var() that ask for reduced rscale results are the transcendental functions like ln_var() and exp_var(), which are working to some limited precision intended to compute the final result reasonably accurately to a particular rscale. Regards, Dean ^ permalink raw reply [nested|flat] 13+ messages in thread
end of thread, other threads:[~2024-07-03 10:41 UTC | newest] Thread overview: 13+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2022-03-18 10:01 [PATCH v15] Enforce foreign key correctly during cross-partition updates Alvaro Herrera <[email protected]> 2024-07-01 13:14 Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-01 19:56 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-01 22:19 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Dean Rasheed <[email protected]> 2024-07-02 07:49 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-02 08:22 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Dean Rasheed <[email protected]> 2024-07-02 09:05 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-02 10:23 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-02 11:44 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Dean Rasheed <[email protected]> 2024-07-02 16:20 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-02 18:53 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-02 19:55 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]> 2024-07-03 10:41 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Dean Rasheed <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox