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

Commite703261

Browse files
committed
Use a pairing heap for the priority queue in kNN-GiST searches.
This performs slightly better, uses less memory, and needs slightly lesscode in GiST, than the Red-Black tree previously used.Reviewed by Peter Geoghegan
1 parent699300a commite703261

File tree

7 files changed

+409
-134
lines changed

7 files changed

+409
-134
lines changed

‎src/backend/access/gist/gistget.c

Lines changed: 21 additions & 50 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
#include"access/relscan.h"
1919
#include"miscadmin.h"
2020
#include"pgstat.h"
21+
#include"lib/pairingheap.h"
2122
#include"utils/builtins.h"
2223
#include"utils/memutils.h"
2324
#include"utils/rel.h"
@@ -243,8 +244,6 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
243244
GISTPageOpaqueopaque;
244245
OffsetNumbermaxoff;
245246
OffsetNumberi;
246-
GISTSearchTreeItem*tmpItem=so->tmpTreeItem;
247-
boolisNew;
248247
MemoryContextoldcxt;
249248

250249
Assert(!GISTSearchItemIsHeap(*pageItem));
@@ -275,18 +274,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
275274
oldcxt=MemoryContextSwitchTo(so->queueCxt);
276275

277276
/* Create new GISTSearchItem for the right sibling index page */
278-
item=palloc(sizeof(GISTSearchItem));
279-
item->next=NULL;
277+
item=palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
280278
item->blkno=opaque->rightlink;
281279
item->data.parentlsn=pageItem->data.parentlsn;
282280

283281
/* Insert it into the queue using same distances as for this page */
284-
tmpItem->head=item;
285-
tmpItem->lastHeap=NULL;
286-
memcpy(tmpItem->distances,myDistances,
282+
memcpy(item->distances,myDistances,
287283
sizeof(double)*scan->numberOfOrderBys);
288284

289-
(void)rb_insert(so->queue,(RBNode*)tmpItem,&isNew);
285+
pairingheap_add(so->queue,&item->phNode);
290286

291287
MemoryContextSwitchTo(oldcxt);
292288
}
@@ -348,8 +344,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
348344
oldcxt=MemoryContextSwitchTo(so->queueCxt);
349345

350346
/* Create new GISTSearchItem for this item */
351-
item=palloc(sizeof(GISTSearchItem));
352-
item->next=NULL;
347+
item=palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
353348

354349
if (GistPageIsLeaf(page))
355350
{
@@ -372,12 +367,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
372367
}
373368

374369
/* Insert it into the queue using new distance data */
375-
tmpItem->head=item;
376-
tmpItem->lastHeap=GISTSearchItemIsHeap(*item) ?item :NULL;
377-
memcpy(tmpItem->distances,so->distances,
370+
memcpy(item->distances,so->distances,
378371
sizeof(double)*scan->numberOfOrderBys);
379372

380-
(void)rb_insert(so->queue,(RBNode*)tmpItem,&isNew);
373+
pairingheap_add(so->queue,&item->phNode);
381374

382375
MemoryContextSwitchTo(oldcxt);
383376
}
@@ -390,44 +383,24 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
390383
* Extract next item (in order) from search queue
391384
*
392385
* Returns a GISTSearchItem or NULL. Caller must pfree item when done with it.
393-
*
394-
* NOTE: on successful return, so->curTreeItem is the GISTSearchTreeItem that
395-
* contained the result item. Callers can use so->curTreeItem->distances as
396-
* the distances value for the item.
397386
*/
398387
staticGISTSearchItem*
399388
getNextGISTSearchItem(GISTScanOpaqueso)
400389
{
401-
for (;;)
402-
{
403-
GISTSearchItem*item;
404-
405-
/* Update curTreeItem if we don't have one */
406-
if (so->curTreeItem==NULL)
407-
{
408-
so->curTreeItem= (GISTSearchTreeItem*)rb_leftmost(so->queue);
409-
/* Done when tree is empty */
410-
if (so->curTreeItem==NULL)
411-
break;
412-
}
390+
GISTSearchItem*item;
413391

414-
item=so->curTreeItem->head;
415-
if (item!=NULL)
416-
{
417-
/* Delink item from chain */
418-
so->curTreeItem->head=item->next;
419-
if (item==so->curTreeItem->lastHeap)
420-
so->curTreeItem->lastHeap=NULL;
421-
/* Return item; caller is responsible to pfree it */
422-
returnitem;
423-
}
424-
425-
/* curTreeItem is exhausted, so remove it from rbtree */
426-
rb_delete(so->queue, (RBNode*)so->curTreeItem);
427-
so->curTreeItem=NULL;
392+
if (!pairingheap_is_empty(so->queue))
393+
{
394+
item= (GISTSearchItem*)pairingheap_remove_first(so->queue);
395+
}
396+
else
397+
{
398+
/* Done when both heaps are empty */
399+
item=NULL;
428400
}
429401

430-
returnNULL;
402+
/* Return item; caller is responsible to pfree it */
403+
returnitem;
431404
}
432405

433406
/*
@@ -458,7 +431,7 @@ getNextNearest(IndexScanDesc scan)
458431
/* visit an index page, extract its items into queue */
459432
CHECK_FOR_INTERRUPTS();
460433

461-
gistScanPage(scan,item,so->curTreeItem->distances,NULL,NULL);
434+
gistScanPage(scan,item,item->distances,NULL,NULL);
462435
}
463436

464437
pfree(item);
@@ -491,7 +464,6 @@ gistgettuple(PG_FUNCTION_ARGS)
491464
pgstat_count_index_scan(scan->indexRelation);
492465

493466
so->firstCall= false;
494-
so->curTreeItem=NULL;
495467
so->curPageData=so->nPageData=0;
496468

497469
fakeItem.blkno=GIST_ROOT_BLKNO;
@@ -534,7 +506,7 @@ gistgettuple(PG_FUNCTION_ARGS)
534506
* this page, we fall out of the inner "do" and loop around to
535507
* return them.
536508
*/
537-
gistScanPage(scan,item,so->curTreeItem->distances,NULL,NULL);
509+
gistScanPage(scan,item,item->distances,NULL,NULL);
538510

539511
pfree(item);
540512
}while (so->nPageData==0);
@@ -560,7 +532,6 @@ gistgetbitmap(PG_FUNCTION_ARGS)
560532
pgstat_count_index_scan(scan->indexRelation);
561533

562534
/* Begin the scan by processing the root page */
563-
so->curTreeItem=NULL;
564535
so->curPageData=so->nPageData=0;
565536

566537
fakeItem.blkno=GIST_ROOT_BLKNO;
@@ -580,7 +551,7 @@ gistgetbitmap(PG_FUNCTION_ARGS)
580551

581552
CHECK_FOR_INTERRUPTS();
582553

583-
gistScanPage(scan,item,so->curTreeItem->distances,tbm,&ntids);
554+
gistScanPage(scan,item,item->distances,tbm,&ntids);
584555

585556
pfree(item);
586557
}

‎src/backend/access/gist/gistscan.c

Lines changed: 12 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -22,74 +22,30 @@
2222

2323

2424
/*
25-
*RBTree support functionsfor theGISTSearchTreeItem queue
25+
*Pairing heap comparison functionfor theGISTSearchItem queue
2626
*/
27-
2827
staticint
29-
GISTSearchTreeItemComparator(constRBNode*a,constRBNode*b,void*arg)
28+
pairingheap_GISTSearchItem_cmp(constpairingheap_node*a,constpairingheap_node*b,void*arg)
3029
{
31-
constGISTSearchTreeItem*sa= (constGISTSearchTreeItem*)a;
32-
constGISTSearchTreeItem*sb= (constGISTSearchTreeItem*)b;
30+
constGISTSearchItem*sa= (constGISTSearchItem*)a;
31+
constGISTSearchItem*sb= (constGISTSearchItem*)b;
3332
IndexScanDescscan= (IndexScanDesc)arg;
3433
inti;
3534

3635
/* Order according to distance comparison */
3736
for (i=0;i<scan->numberOfOrderBys;i++)
3837
{
3938
if (sa->distances[i]!=sb->distances[i])
40-
return (sa->distances[i]>sb->distances[i]) ?1 :-1;
41-
}
42-
43-
return0;
44-
}
45-
46-
staticvoid
47-
GISTSearchTreeItemCombiner(RBNode*existing,constRBNode*newrb,void*arg)
48-
{
49-
GISTSearchTreeItem*scurrent= (GISTSearchTreeItem*)existing;
50-
constGISTSearchTreeItem*snew= (constGISTSearchTreeItem*)newrb;
51-
GISTSearchItem*newitem=snew->head;
52-
53-
/* snew should have just one item in its chain */
54-
Assert(newitem&&newitem->next==NULL);
55-
56-
/*
57-
* If new item is heap tuple, it goes to front of chain; otherwise insert
58-
* it before the first index-page item, so that index pages are visited in
59-
* LIFO order, ensuring depth-first search of index pages. See comments
60-
* in gist_private.h.
61-
*/
62-
if (GISTSearchItemIsHeap(*newitem))
63-
{
64-
newitem->next=scurrent->head;
65-
scurrent->head=newitem;
66-
if (scurrent->lastHeap==NULL)
67-
scurrent->lastHeap=newitem;
39+
return (sa->distances[i]<sb->distances[i]) ?1 :-1;
6840
}
69-
elseif (scurrent->lastHeap==NULL)
70-
{
71-
newitem->next=scurrent->head;
72-
scurrent->head=newitem;
73-
}
74-
else
75-
{
76-
newitem->next=scurrent->lastHeap->next;
77-
scurrent->lastHeap->next=newitem;
78-
}
79-
}
8041

81-
staticRBNode*
82-
GISTSearchTreeItemAllocator(void*arg)
83-
{
84-
IndexScanDescscan= (IndexScanDesc)arg;
85-
86-
returnpalloc(GSTIHDRSZ+sizeof(double)*scan->numberOfOrderBys);
87-
}
42+
/* Heap items go before inner pages, to ensure a depth-first search */
43+
if (GISTSearchItemIsHeap(*sa)&& !GISTSearchItemIsHeap(*sb))
44+
return-1;
45+
if (!GISTSearchItemIsHeap(*sa)&&GISTSearchItemIsHeap(*sb))
46+
return1;
8847

89-
staticvoid
90-
GISTSearchTreeItemDeleter(RBNode*rb,void*arg)
91-
{
92-
pfree(rb);
48+
return0;
9349
}
9450

9551

@@ -127,7 +83,6 @@ gistbeginscan(PG_FUNCTION_ARGS)
12783
so->queueCxt=giststate->scanCxt;/* see gistrescan */
12884

12985
/* workspaces with size dependent on numberOfOrderBys: */
130-
so->tmpTreeItem=palloc(GSTIHDRSZ+sizeof(double)*scan->numberOfOrderBys);
13186
so->distances=palloc(sizeof(double)*scan->numberOfOrderBys);
13287
so->qual_ok= true;/* in case there are zero keys */
13388

@@ -188,15 +143,9 @@ gistrescan(PG_FUNCTION_ARGS)
188143

189144
/* create new, empty RBTree for search queue */
190145
oldCxt=MemoryContextSwitchTo(so->queueCxt);
191-
so->queue=rb_create(GSTIHDRSZ+sizeof(double)*scan->numberOfOrderBys,
192-
GISTSearchTreeItemComparator,
193-
GISTSearchTreeItemCombiner,
194-
GISTSearchTreeItemAllocator,
195-
GISTSearchTreeItemDeleter,
196-
scan);
146+
so->queue=pairingheap_allocate(pairingheap_GISTSearchItem_cmp,scan);
197147
MemoryContextSwitchTo(oldCxt);
198148

199-
so->curTreeItem=NULL;
200149
so->firstCall= true;
201150

202151
/* Update scan key, if a new one is given */

‎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 binaryheap.o stringinfo.o
15+
OBJS = ilist.o binaryheap.opairingheap.ostringinfo.o
1616

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

‎src/backend/lib/README

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
This directory contains a general purpose data structures, for use anywhere
2+
in the backend:
3+
4+
binaryheap.c - a binary heap
5+
6+
pairingheap.c - a pairing heap
7+
8+
ilist.c - single and double-linked lists.
9+
10+
stringinfo.c - an extensible string type
11+
12+
13+
Aside from the inherent characteristics of the data structures, there are a
14+
few practical differences between the binary heap and the pairing heap. The
15+
binary heap is fully allocated at creation, and cannot be expanded beyond the
16+
allocated size. The pairing heap on the other hand has no inherent maximum
17+
size, but the caller needs to allocate each element being stored in the heap,
18+
while the binary heap works with plain Datums or pointers.
19+
20+
The linked-lists in ilist.c can be embedded directly into other structs, as
21+
opposed to the List interface in nodes/pg_list.h.
22+
23+
In addition to these, there is an implementation of a Red-Black tree in
24+
src/backend/utils/adt/rbtree.c.

0 commit comments

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