10000 Basic binary heap implementation. · postgres/postgres@7a2fe9b · GitHub
[go: up one dir, main page]
Skip to content

Commit 7a2fe9b

Browse files
robertmhaasrobertmhaas
committed
Basic binary heap implementation.
There are probably other places where this can be used, but for now, this just makes MergeAppend use it, so that this code will have test coverage. There is other work in the queue that will use this, as well. Abhijit Menon-Sen, reviewed by Andres Freund, Robert Haas, Álvaro Herrera, Tom Lane, and others.
1 parent 086cf14 commit 7a2fe9b

File tree

5 files changed

+380
-90
lines changed

5 files changed

+380
-90
lines changed

‎src/backend/executor/nodeMergeAppend.c

Lines changed: 31 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -41,17 +41,16 @@
4141
#include "executor/execdebug.h"
4242
#include "executor/nodeMergeAppend.h"
4343

44+
#include "lib/binaryheap.h"
45+
4446
/*
45-
* It gets quite confusing having a heap array (indexed by integers) which
46-
* contains integers which index into the slots array. These typedefs try to
47-
* clear it up, but they're only documentation.
47+
* We have one slot for each item in the heap array. We use SlotNumber
48+
* to store slot indexes. This doesn't actually provide any formal
49+
* type-safety, but it makes the code more self-documenting.
4850
*/
49-
typedef int SlotNumber;
50-
typedef int HeapPosition;
51+
typedef int32 SlotNumber;
5152

52-
static void heap_insert_slot(MergeAppendState *node, SlotNumber new_slot);
53-
static void heap_siftup_slot(MergeAppendState *node);
54-
static int32 heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2);
53+
static int heap_compare_slots(Datum a, Datum b, void *arg);
5554

5655

5756
/* ----------------------------------------------------------------
@@ -88,7 +87,8 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
8887
mergestate->ms_nplans = nplans;
8988

9089
mergestate->ms_slots = (TupleTableSlot **) palloc0(sizeof(TupleTableSlot *) * nplans);
91-
mergestate->ms_heap = (int *) palloc0(sizeof(int) * nplans);
90+
mergestate->ms_heap = binaryheap_allocate(nplans, heap_compare_slots,
91+
mergestate);
9292

9393
/*
9494
* Miscellaneous initialization
@@ -143,9 +143,7 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
143143
/*
144144
* initialize to show we have not run the subplans yet
145145
*/
146-
mergestate->ms_heap_size = 0;
147146
mergestate->ms_initialized = false;
148-
mergestate->ms_last_slot = -1;
149147

150148
return mergestate;
151149
}
@@ -172,101 +170,53 @@ ExecMergeAppend(MergeAppendState *node)
172170
{
173171
node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
174172
if (!TupIsNull(node->ms_slots[i]))
175-
heap_insert_slot(node, i);
173+
binaryheap_add_unordered(node->ms_heap, Int32GetDatum(i));
176174
}
175+
binaryheap_build(node->ms_heap);
177176
node->ms_initialized = true;
178177
}
179178
else
180179
{
181180
/*
182181
* Otherwise, pull the next tuple from whichever subplan we returned
183-
* from last time, and insert it into the heap. (We could simplify
184-
* the logic a bit by doing this before returning from the prior call,
185-
* but it's better to not pull tuples until necessary.)
182+
* from last time, and reinsert the subplan index into the heap,
183+
* because it might now compare differently against the existing
184+
* elements of the heap. (We could perhaps simplify the logic a bit
185+
* by doing this before returning from the prior call, but it's better
186+
* to not pull tuples until necessary.)
186187
*/
187-
i = node->ms_last_slot;
188+
i = DatumGetInt32(binaryheap_first(node->ms_heap));
188189
node->ms_slots[i] = ExecProcNode(node->mergeplans[i]);
189190
if (!TupIsNull(node->ms_slots[i]))
190-
heap_insert_slot(node, i);
191+
binaryheap_replace_first(node->ms_heap, Int32GetDatum(i));
192+
else
193+
(void) binaryheap_remove_first(node->ms_heap);
191194
}
192195

193-
if (node->ms_heap_size > 0)
194-
{
195-
/* Return the topmost heap node, and sift up the remaining nodes */
196-
i = node->ms_heap[0];
197-
result = node->ms_slots[i];
198-
node->ms_last_slot = i;
199-
heap_siftup_slot(node);
200-
}
201-
else
196+
if (binaryheap_empty(node->ms_heap))
202197
{
203198
/* All the subplans are exhausted, and so is the heap */
204199
result = ExecClearTuple(node->ps.ps_ResultTupleSlot);
205200
}
206-
207-
return result;
208-
}
209-
210-
/*
211-
* Insert a new slot into the heap. The slot must contain a valid tuple.
212-
*/
213-
static void
214-
heap_insert_slot(MergeAppendState *node, SlotNumber new_slot)
215-
{
216-
SlotNumber *heap = node->ms_heap;
217-
HeapPosition j;
218-
219-
Assert(!TupIsNull(node->ms_slots[new_slot]));
220-
221-
j = node->ms_heap_size++; /* j is where the "hole" is */
222-
while (j > 0)
201+
else
223202
{
224-
int i = (j - 1) / 2;
225-
226-
if (heap_compare_slots(node, new_slot, node->ms_heap[i]) >= 0)
227-
break;
228-
heap[j] = heap[i];
229-
j = i;
203+
i = DatumGetInt32(binaryheap_first(node->ms_heap));
204+
result = node->ms_slots[i];
230205
}
231-
heap[j] = new_slot;
232-
}
233206

234-
/*
235-
* Delete the heap top (the slot in heap[0]), and sift up.
236-
*/
237-
static void
238-
heap_siftup_slot(MergeAppendState *node)
239-
{
240-
SlotNumber *heap = node->ms_heap;
241-
HeapPosition i,
242-
n;
243-
244-
if (--node->ms_heap_size <= 0)
245-
return;
246-
n = node->ms_heap_size; /* heap[n] needs to be reinserted */
247-
i = 0; /* i is where the "hole" is */
248-
for (;;)
249-
{
250-
int j = 2 * i + 1;
251-
252-
if (j >= n)
253-
break;
254-
if (j + 1 < n && heap_compare_slots(node, heap[j], heap[j + 1]) > 0)
255-
j++;
256-
if (heap_compare_slots(node, heap[n], heap[j]) <= 0)
257-
break;
258-
heap[i] = heap[j];
259-
i = j;
260-
}
261-
heap[i] = heap[n];
207+
return result;
262208
}
263209

264210
/*
265211
* Compare the tuples in the two given slots.
266212
*/
267213
static int32
268-
heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2)
214+
heap_compare_slots(Datum a, Datum b, void *arg)
269215
{
216+
MergeAppendState *node = (MergeAppendState *) arg;
217+
SlotNumber slot1 = DatumGetInt32(a);
218+
SlotNumber slot2 = DatumGetInt32(b);
219+
270220
TupleTableSlot *s1 = node->ms_slots[slot1];
271221
TupleTableSlot *s2 = node->ms_slots[slot2];
272222
int nkey;
@@ -291,7 +241,7 @@ heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2)
291241
datum2, isNull2,
292242
sortKey);
293243
if (compare != 0)
294-
return compare;
244+
return -compare;
295245
}
296246
return 0;
297247
}
@@ -347,7 +297,5 @@ ExecReScanMergeAppend(MergeAppendState *node)
347297
if (subnode->chgParam == NULL)
348298
ExecReScan(subnode);
349299
}
350-
node->ms_heap_size = 0;
351300
node->ms_initialized = false;
352-
node->ms_last_slot = -1;
353301
}

‎src/backend/lib/Makefile

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,6 @@ subdir = src/backend/lib
1212
top_builddir = ../../..
1313
include $(top_builddir)/src/Makefile.global
1414

15-
OBJS = ilist.o stringinfo.o
15+
OBJS = ilist.o binaryheap.o stringinfo.o
1616

1717
include $(top_srcdir)/src/backend/common.mk

0 commit comments

Comments
 (0)
0