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
Appearance settings

Commit e703261

Browse filesBrowse files
hlinnakahlinnaka
committed
Use a pairing heap for the priority queue in kNN-GiST searches.
This performs slightly better, uses less memory, and needs slightly less code in GiST, than the Red-Black tree previously used. Reviewed by Peter Geoghegan
1 parent 699300a commit e703261
Copy full SHA for e703261

File tree

Expand file treeCollapse file tree

7 files changed

+409
-134
lines changed
Filter options
Expand file treeCollapse file tree

7 files changed

+409
-134
lines changed

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

Copy file name to clipboardExpand all lines: src/backend/access/gist/gistget.c
+21-50Lines 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
GISTPageOpaque opaque;
244245
OffsetNumber maxoff;
245246
OffsetNumber i;
246-
GISTSearchTreeItem *tmpItem = so->tmpTreeItem;
247-
bool isNew;
248247
MemoryContext oldcxt;
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
static GISTSearchItem *
399388
getNextGISTSearchItem(GISTScanOpaque so)
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-
return item;
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-
return NULL;
402+
/* Return item; caller is responsible to pfree it */
403+
return item;
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

Copy file name to clipboardExpand all lines: src/backend/access/gist/gistscan.c
+12-63Lines changed: 12 additions & 63 deletions
Original file line numberDiff line numberDiff line change
@@ -22,74 +22,30 @@
2222

2323

2424
/*
25-
* RBTree support functions for the GISTSearchTreeItem queue
25+
* Pairing heap comparison function for the GISTSearchItem queue
2626
*/
27-
2827
static int
29-
GISTSearchTreeItemComparator(const RBNode *a, const RBNode *b, void *arg)
28+
pairingheap_GISTSearchItem_cmp(const pairingheap_node *a, const pairingheap_node *b, void *arg)
3029
{
31-
const GISTSearchTreeItem *sa = (const GISTSearchTreeItem *) a;
32-
const GISTSearchTreeItem *sb = (const GISTSearchTreeItem *) b;
30+
const GISTSearchItem *sa = (const GISTSearchItem *) a;
31+
const GISTSearchItem *sb = (const GISTSearchItem *) b;
3332
IndexScanDesc scan = (IndexScanDesc) arg;
3433
int i;
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-
return 0;
44-
}
45-
46-
static void
47-
GISTSearchTreeItemCombiner(RBNode *existing, const RBNode *newrb, void *arg)
48-
{
49-
GISTSearchTreeItem *scurrent = (GISTSearchTreeItem *) existing;
50-
const GISTSearchTreeItem *snew = (const GISTSearchTreeItem *) 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-
else if (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-
static RBNode *
82-
GISTSearchTreeItemAllocator(void *arg)
83-
{
84-
IndexScanDesc scan = (IndexScanDesc) arg;
85-
86-
return palloc(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+
return 1;
8847

89-
static void
90-
GISTSearchTreeItemDeleter(RBNode *rb, void *arg)
91-
{
92-
pfree(rb);
48+
return 0;
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

Copy file name to clipboardExpand all lines: src/backend/lib/Makefile
+1-1Lines 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.o pairingheap.o stringinfo.o
1616

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

‎src/backend/lib/README

Copy file name to clipboard
+24Lines 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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.