diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index fec07b8..d4911bd 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -1100,10 +1100,8 @@ typedef struct AppendState * nkeys number of sort key columns * sortkeys sort keys in SortSupport representation * slots current output tuple of each subplan - * heap heap of active tuples (represented as array indexes) - * heap_size number of active heap entries + * heap heap of active tuples * initialized true if we have fetched first tuple from each subplan - * last_slot last subplan fetched from (which must be re-called) * ---------------- */ typedef struct MergeAppendState @@ -1114,10 +1112,8 @@ typedef struct MergeAppendState int ms_nkeys; SortSupport ms_sortkeys; /* array of length ms_nkeys */ TupleTableSlot **ms_slots; /* array of length ms_nplans */ - int *ms_heap; /* array of length ms_nplans */ - int ms_heap_size; /* current active length of ms_heap[] */ + struct binaryheap *ms_heap; /* binary heap of slot indices */ bool ms_initialized; /* are subplans started? */ - int ms_last_slot; /* last subplan slot we returned from */ } MergeAppendState; /* ---------------- diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c index d5141ba..6b2fef2 100644 --- a/src/backend/executor/nodeMergeAppend.c +++ b/src/backend/executor/nodeMergeAppend.c @@ -41,6 +41,8 @@ #include "executor/execdebug.h" #include "executor/nodeMergeAppend.h" +#include "lib/binaryheap.h" + /* * It gets quite confusing having a heap array (indexed by integers) which * contains integers which index into the slots array. These typedefs try to @@ -49,9 +51,7 @@ typedef int SlotNumber; typedef int HeapPosition; -static void heap_insert_slot(MergeAppendState *node, SlotNumber new_slot); -static void heap_siftup_slot(MergeAppendState *node); -static int32 heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2); +static int heap_compare_slots(binaryheap_node *a, binaryheap_node *b); /* ---------------------------------------------------------------- @@ -88,7 +88,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags) mergestate->ms_nplans = nplans; mergestate->ms_slots = (TupleTableSlot **) palloc0(sizeof(TupleTableSlot *) * nplans); - mergestate->ms_heap = (int *) palloc0(sizeof(int) * nplans); + mergestate->ms_heap = binaryheap_allocate(nplans, heap_compare_slots); /* * Miscellaneous initialization @@ -143,9 +143,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags) /* * initialize to show we have not run the subplans yet */ - mergestate->ms_heap_size = 0; mergestate->ms_initialized = false; - mergestate->ms_last_slot = -1; return mergestate; } @@ -160,6 +158,7 @@ TupleTableSlot * ExecMergeAppend(MergeAppendState *node) { TupleTableSlot *result; + binaryheap_node *hn; SlotNumber i; if (!node->ms_initialized) @@ -172,7 +171,9 @@ ExecMergeAppend(MergeAppendState *node) { node->ms_slots[i] = ExecProcNode(node->mergeplans[i]); if (!TupIsNull(node->ms_slots[i])) - heap_insert_slot(node, i); + { + binaryheap_add(node->ms_heap, node, (void *)i); + } } node->ms_initialized = true; } @@ -184,19 +185,22 @@ ExecMergeAppend(MergeAppendState *node) * the logic a bit by doing this before returning from the prior call, * but it's better to not pull tuples until necessary.) */ - i = node->ms_last_slot; + hn = binaryheap_first(node->ms_heap); + i = (int)hn->value; node->ms_slots[i] = ExecProcNode(node->mergeplans[i]); - if (!TupIsNull(node->ms_slots[i])) - heap_insert_slot(node, i); + if (!TupIsNull(node->ms_slots[i])) { + binaryheap_replace_first(node->ms_heap, node, (void *)i); + } + else { + (void)binaryheap_remove_first(node->ms_heap); + } } - if (node->ms_heap_size > 0) + hn = binaryheap_first(node->ms_heap); + if (hn) { - /* Return the topmost heap node, and sift up the remaining nodes */ - i = node->ms_heap[0]; + i = (int)hn->value; result = node->ms_slots[i]; - node->ms_last_slot = i; - heap_siftup_slot(node); } else { @@ -208,65 +212,15 @@ ExecMergeAppend(MergeAppendState *node) } /* - * Insert a new slot into the heap. The slot must contain a valid tuple. - */ -static void -heap_insert_slot(MergeAppendState *node, SlotNumber new_slot) -{ - SlotNumber *heap = node->ms_heap; - HeapPosition j; - - Assert(!TupIsNull(node->ms_slots[new_slot])); - - j = node->ms_heap_size++; /* j is where the "hole" is */ - while (j > 0) - { - int i = (j - 1) / 2; - - if (heap_compare_slots(node, new_slot, node->ms_heap[i]) >= 0) - break; - heap[j] = heap[i]; - j = i; - } - heap[j] = new_slot; -} - -/* - * Delete the heap top (the slot in heap[0]), and sift up. - */ -static void -heap_siftup_slot(MergeAppendState *node) -{ - SlotNumber *heap = node->ms_heap; - HeapPosition i, - n; - - if (--node->ms_heap_size <= 0) - return; - n = node->ms_heap_size; /* heap[n] needs to be reinserted */ - i = 0; /* i is where the "hole" is */ - for (;;) - { - int j = 2 * i + 1; - - if (j >= n) - break; - if (j + 1 < n && heap_compare_slots(node, heap[j], heap[j + 1]) > 0) - j++; - if (heap_compare_slots(node, heap[n], heap[j]) <= 0) - break; - heap[i] = heap[j]; - i = j; - } - heap[i] = heap[n]; -} - -/* * Compare the tuples in the two given slots. */ static int32 -heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2) +heap_compare_slots(binaryheap_node *a, binaryheap_node *b) { + MergeAppendState *node = (MergeAppendState *)a->key; + SlotNumber slot1 = (int)a->value; + SlotNumber slot2 = (int)b->value; + TupleTableSlot *s1 = node->ms_slots[slot1]; TupleTableSlot *s2 = node->ms_slots[slot2]; int nkey; @@ -291,7 +245,7 @@ heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2) datum2, isNull2, sortKey); if (compare != 0) - return compare; + return -compare; } return 0; } @@ -347,7 +301,5 @@ ExecReScanMergeAppend(MergeAppendState *node) if (subnode->chgParam == NULL) ExecReScan(subnode); } - node->ms_heap_size = 0; node->ms_initialized = false; - node->ms_last_slot = -1; }