Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7a2fe9b

Browse files
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 testcoverage. There is other work in the queue that will use this, aswell.Abhijit Menon-Sen, reviewed by Andres Freund, Robert Haas, ÁlvaroHerrera, Tom Lane, and others.
1 parent086cf14 commit7a2fe9b

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 aheap array (indexed by integers) which
46-
*contains integers which index into the slots array. These typedefs try to
47-
*clearitup, but they're only documentation.
47+
*We have one slot for each item in theheap array. We use SlotNumber
48+
*to store slot indexes. This doesn't actually provide any formal
49+
*type-safety, butitmakes the code more self-documenting.
4850
*/
49-
typedefintSlotNumber;
50-
typedefintHeapPosition;
51+
typedefint32SlotNumber;
5152

52-
staticvoidheap_insert_slot(MergeAppendState*node,SlotNumbernew_slot);
53-
staticvoidheap_siftup_slot(MergeAppendState*node);
54-
staticint32heap_compare_slots(MergeAppendState*node,SlotNumberslot1,SlotNumberslot2);
53+
staticintheap_compare_slots(Datuma,Datumb,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
returnmergestate;
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-
returnresult;
208-
}
209-
210-
/*
211-
* Insert a new slot into the heap. The slot must contain a valid tuple.
212-
*/
213-
staticvoid
214-
heap_insert_slot(MergeAppendState*node,SlotNumbernew_slot)
215-
{
216-
SlotNumber*heap=node->ms_heap;
217-
HeapPositionj;
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-
inti= (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-
staticvoid
238-
heap_siftup_slot(MergeAppendState*node)
239-
{
240-
SlotNumber*heap=node->ms_heap;
241-
HeapPositioni,
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-
intj=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+
returnresult;
262208
}
263209

264210
/*
265211
* Compare the tuples in the two given slots.
266212
*/
267213
staticint32
268-
heap_compare_slots(MergeAppendState*node,SlotNumberslot1,SlotNumberslot2)
214+
heap_compare_slots(Datuma,Datumb,void*arg)
269215
{
216+
MergeAppendState*node= (MergeAppendState*)arg;
217+
SlotNumberslot1=DatumGetInt32(a);
218+
SlotNumberslot2=DatumGetInt32(b);
219+
270220
TupleTableSlot*s1=node->ms_slots[slot1];
271221
TupleTableSlot*s2=node->ms_slots[slot2];
272222
intnkey;
@@ -291,7 +241,7 @@ heap_compare_slots(MergeAppendState *node, SlotNumber slot1, SlotNumber slot2)
291241
datum2,isNull2,
292242
sortKey);
293243
if (compare!=0)
294-
returncompare;
244+
return-compare;
295245
}
296246
return0;
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.obinaryheap.ostringinfo.o
1616

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

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp