Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 02/17/2015 02:56 PM, Alexander Korotkov wrote: Hi! On Mon, Dec 22, 2014 at 1:07 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: Ok, thanks for the review! I have committed this, with some cleanup and more comments added. ISTM that checks in pairingheap_GISTSearchItem_cmp is incorrect. This function should perform inverse comparison. Thus, if item a should be checked first function should return 1. Current behavior doesn't lead to incorrect query answers, but it could be slower than correct version. Good catch. Fixed, thanks. While testing this, I also noticed a bug in the pairing heap code itself. Fixed that too. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
Hi! On Mon, Dec 22, 2014 at 1:07 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: Ok, thanks for the review! I have committed this, with some cleanup and more comments added. ISTM that checks in pairingheap_GISTSearchItem_cmp is incorrect. This function should perform inverse comparison. Thus, if item a should be checked first function should return 1. Current behavior doesn't lead to incorrect query answers, but it could be slower than correct version. -- With best regards, Alexander Korotkov. pairing_heap_cmp_fix.patch Description: Binary data -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 12/20/2014 10:50 PM, Peter Geoghegan wrote: On Wed, Dec 17, 2014 at 6:07 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: How about adding a src/backend/lib/README for that, per attached? I took a quick look at this. Some observations: * I like the idea of adding a .../lib README. However, the README fails to note that ilist.c implements an *integrated* list, unlike the much more prevalent cell-based List structure. It should note that, since that's the whole point of ilist.c. Added a sentence on that. * pairingheap_remove() is technically dead code. It still makes sense that you'd have it in this patch, but I think there's an argument for not including it at all on the theory that if you need to use it you should use a different data structure. After all, the actual (non-amortized) complexity of that operation is O(n) [1], and if remove operations are infrequent as we might expect, that might be the more important consideration. As long as you are including pairingheap_remove(), though, why is the local variable prev_ptr a pointer to a pointer to a pairingheap_node, rather than just a pointer to a pairingheap_node? * Similarly, the function-like macro pairingheap_reset() doesn't seem to pull its weight. Why does it exist alongside pairingheap_free()? I'm not seeing a need to re-use a heap like that. pairingheap_remove and pairingheap_reset are both unused in this patch, but they were needed for the other use case, tracking snapshots to advance xmin more aggressively, discussed here: http://www.postgresql.org/message-id/5488acf0.8050...@vmware.com. In fact, without the pairingheap_remove() operation, the prev_or_parent pointer wouldn't be necessarily at all. We could've added them as a separate patch, but that seems like unnecessary code churn. The prev_ptr variable is used to set the parent's first_child pointer, or the previous sibling's next_sibling pointer, depending on whether the removed node is the parent's first child or not. I'll add more comments in pairingheap_remove to explain that. * Assert(!pairingheap_is_empty(heap)) appears in a few places. You're basically asserting that a pointer isn't null, often immediately before dereferencing the pointer. This seems to be of questionable value. I copied that from binaryheap.c. It has some documentation value; they make it easy to see that the functions require the heap to not be empty. It's also explained in comments, but still. * I think that the indentation of code could use some tweaking. * More comments, please. In particular, comment the struct fields in pairingheap_node. There are various blocks of code that could use at least an additional terse comment, too. Added some comments, hope it's better now. * You talked about tuplesort.c integration. In order for that to happen, I think the comparator logic should know less about min-heaps. This should formally be a max-heap, with the ability to provide customizations only encapsulated in the comparator (like inverting the comparison logic to get a min-heap, or like custom NULLs first/last behavior). So IMV this comment should be more generic/anticipatory: + /* + * For a max-heap, the comparator must return 0 iff a b, 0 iff a == b, + * and 0 iff a b. For a min-heap, the conditions are reversed. + */ + typedef int (*pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg); I think the functions should be called pairing_max_heap* for this reason, too. Although that isn't consistent with binaryheap.c, so I guess this whole argument is a non-starter. I don't see what the problem is. The pairingheap.c (and binaryheap.c) code works the same for min and max-heaps. The comments assume a max-heap in a few places, but that seems OK to me in the context. * We should just move rbtree.c to .../lib. We're not using CVS anymore -- the history will be magically preserved. Yeah, I tend to agree. Tom Lane has not liked moving things, because it breaks back-patching. That's true in general, even though git has some smarts to follow renames. I think it would work in this case, though. Anyway, let's discuss and do that as a separate patch, so that we don't get stuck on that. Anyway, to get to the heart of the matter: in general, I think the argument for the patch is sound. It's not a stellar improvement, but it's worthwhile. That's all I have for now... Ok, thanks for the review! I have committed this, with some cleanup and more comments added. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On Wed, Dec 17, 2014 at 6:07 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: How about adding a src/backend/lib/README for that, per attached? I took a quick look at this. Some observations: * I like the idea of adding a .../lib README. However, the README fails to note that ilist.c implements an *integrated* list, unlike the much more prevalent cell-based List structure. It should note that, since that's the whole point of ilist.c. * pairingheap_remove() is technically dead code. It still makes sense that you'd have it in this patch, but I think there's an argument for not including it at all on the theory that if you need to use it you should use a different data structure. After all, the actual (non-amortized) complexity of that operation is O(n) [1], and if remove operations are infrequent as we might expect, that might be the more important consideration. As long as you are including pairingheap_remove(), though, why is the local variable prev_ptr a pointer to a pointer to a pairingheap_node, rather than just a pointer to a pairingheap_node? * Similarly, the function-like macro pairingheap_reset() doesn't seem to pull its weight. Why does it exist alongside pairingheap_free()? I'm not seeing a need to re-use a heap like that. * Assert(!pairingheap_is_empty(heap)) appears in a few places. You're basically asserting that a pointer isn't null, often immediately before dereferencing the pointer. This seems to be of questionable value. * I think that the indentation of code could use some tweaking. * More comments, please. In particular, comment the struct fields in pairingheap_node. There are various blocks of code that could use at least an additional terse comment, too. * You talked about tuplesort.c integration. In order for that to happen, I think the comparator logic should know less about min-heaps. This should formally be a max-heap, with the ability to provide customizations only encapsulated in the comparator (like inverting the comparison logic to get a min-heap, or like custom NULLs first/last behavior). So IMV this comment should be more generic/anticipatory: + /* + * For a max-heap, the comparator must return 0 iff a b, 0 iff a == b, + * and 0 iff a b. For a min-heap, the conditions are reversed. + */ + typedef int (*pairingheap_comparator) (const pairingheap_node *a, const pairingheap_node *b, void *arg); I think the functions should be called pairing_max_heap* for this reason, too. Although that isn't consistent with binaryheap.c, so I guess this whole argument is a non-starter. * We should just move rbtree.c to .../lib. We're not using CVS anymore -- the history will be magically preserved. Anyway, to get to the heart of the matter: in general, I think the argument for the patch is sound. It's not a stellar improvement, but it's worthwhile. That's all I have for now... [1] https://www.cise.ufl.edu/~sahni/dsaac/enrich/c13/pairing.htm -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 12/15/2014 03:14 PM, Andres Freund wrote:
If we add another heap implementation we probably should at least hint
at the different advantages somewhere.
How about adding a src/backend/lib/README for that, per attached?
- Heikki
diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile
index 327a1bc..b24ece6 100644
--- a/src/backend/lib/Makefile
+++ b/src/backend/lib/Makefile
@@ -12,6 +12,6 @@ subdir = src/backend/lib
top_builddir = ../../..
include $(top_builddir)/src/Makefile.global
-OBJS = ilist.o binaryheap.o stringinfo.o
+OBJS = ilist.o binaryheap.o pairingheap.o stringinfo.o
include $(top_srcdir)/src/backend/common.mk
diff --git a/src/backend/lib/README b/src/backend/lib/README
new file mode 100644
index 000..49cf99a
--- /dev/null
+++ b/src/backend/lib/README
@@ -0,0 +1,21 @@
+This directory contains a general purpose data structures, for use anywhere
+in the backend:
+
+binaryheap.c - a binary heap
+
+pairingheap.c - a pairing heap
+
+ilist.c - single and double-linked lists.
+
+stringinfo.c - an extensible string type
+
+
+Aside from the inherent characteristics of the data structures, there are a
+few practical differences between the binary heap and the pairing heap. The
+binary heap is fully allocated at creation, and cannot be expanded beyond the
+allocated size. The pairing heap on the other hand has no inherent maximum
+size, but the caller needs to allocate each element being stored in the heap,
+while the binary heap works with plain Datums or pointers.
+
+In addition to these, there is an implementation of a Red-Black tree in
+src/backend/utils/adt/rbtree.c.
diff --git a/src/backend/lib/pairingheap.c b/src/backend/lib/pairingheap.c
new file mode 100644
index 000..a7e8901
--- /dev/null
+++ b/src/backend/lib/pairingheap.c
@@ -0,0 +1,235 @@
+/*-
+ *
+ * pairingheap.c
+ * A Pairing Heap implementation
+ *
+ * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/backend/lib/pairingheap.c
+ *
+ *-
+ */
+
+#include postgres.h
+
+#include lib/pairingheap.h
+
+static pairingheap_node *merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b);
+static pairingheap_node *merge_children(pairingheap *heap, pairingheap_node *children);
+
+/*
+ * pairingheap_allocate
+ *
+ * Returns a pointer to a newly-allocated heap, with the heap property
+ * defined by the given comparator function, which will be invoked with the
+ * additional argument specified by 'arg'.
+ */
+pairingheap *
+pairingheap_allocate(pairingheap_comparator compare, void *arg)
+{
+ pairingheap *heap;
+
+ heap = (pairingheap *) palloc(sizeof(pairingheap));
+ heap-ph_compare = compare;
+ heap-ph_arg = arg;
+
+ heap-ph_root = NULL;
+
+ return heap;
+}
+
+/*
+ * pairingheap_free
+ *
+ * Releases memory used by the given pairingheap.
+ *
+ * Note: The items in the heap are not released!
+ */
+void
+pairingheap_free(pairingheap *heap)
+{
+ pfree(heap);
+}
+
+
+/* A helper function to merge two subheaps into one. */
+static pairingheap_node *
+merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
+{
+ if (a == NULL)
+ return b;
+ if (b == NULL)
+ return a;
+
+ /* Put the larger of the items as a child of the smaller one */
+ if (heap-ph_compare(a, b, heap-ph_arg) 0)
+ {
+ pairingheap_node *tmp;
+
+ tmp = a;
+ a = b;
+ b = tmp;
+ }
+
+ if (a-first_child)
+ a-first_child-prev_or_parent = b;
+ b-prev_or_parent = a;
+ b-next_sibling = a-first_child;
+ a-first_child = b;
+ return a;
+}
+
+/*
+ * pairingheap_add
+ *
+ * Adds the given datum to the heap in O(1) time.
+ */
+void
+pairingheap_add(pairingheap *heap, pairingheap_node *d)
+{
+ d-first_child = NULL;
+
+ /* Link the new item as a new tree */
+ heap-ph_root = merge(heap, heap-ph_root, d);
+}
+
+/*
+ * pairingheap_first
+ *
+ * Returns a pointer to the first (root, topmost) node in the heap
+ * without modifying the heap. The caller must ensure that this
+ * routine is not used on an empty heap. Always O(1).
+ */
+pairingheap_node *
+pairingheap_first(pairingheap *heap)
+{
+ Assert(!pairingheap_is_empty(heap));
+ return heap-ph_root;
+}
+
+/*
+ * pairingheap_remove_first
+ *
+ * Removes the first (root, topmost) node in the heap and returns a
+ * pointer to it after rebalancing the heap. The caller must ensure
+ * that this routine is not used on an empty heap. O(log n) amortized.
+ */
+pairingheap_node *
+pairingheap_remove_first(pairingheap *heap)
+{
+ pairingheap_node *result;
+ pairingheap_node *children;
+
+ Assert(!pairingheap_is_empty(heap));
+
+ /* Remove the smallest root. */
+ result = heap-ph_root;
+ children = result-first_child;
+
+ heap-ph_root = merge_children(heap, children);
+
+ return result;
+}
+
+/*
+ * Merge a list of subheaps into a single heap.
+ *
+ * This implements the basic two-pass merging strategy, first forming
+
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 12/15/2014 11:59 PM, Jeff Janes wrote:
On Mon, Dec 15, 2014 at 5:08 AM, Heikki Linnakangas hlinnakan...@vmware.com
wrote:
Here's a new version of the patch. It now uses the same pairing heap code
that I posted in the other thread (advance local xmin more aggressivley,
http://www.postgresql.org/message-id/5488acf0.8050...@vmware.com). The
pairingheap_remove() function is unused in this patch, but it is needed by
that other patch.
Under enable-cassert, this tries to call pairingheap_empty, but that
function doesn't exist.
I looked in the other patch and didn't find it defined there, either.
Ah, I renamed pairingheap_empty to pairingheap_is_empty at the last
minute, and missed the Asserts. Here's a corrected version.
- Heikki
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 7a8692b..e5eb6f6 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -18,6 +18,7 @@
#include access/relscan.h
#include miscadmin.h
#include pgstat.h
+#include lib/pairingheap.h
#include utils/builtins.h
#include utils/memutils.h
#include utils/rel.h
@@ -243,8 +244,6 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
GISTPageOpaque opaque;
OffsetNumber maxoff;
OffsetNumber i;
- GISTSearchTreeItem *tmpItem = so-tmpTreeItem;
- bool isNew;
MemoryContext oldcxt;
Assert(!GISTSearchItemIsHeap(*pageItem));
@@ -275,18 +274,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
oldcxt = MemoryContextSwitchTo(so-queueCxt);
/* Create new GISTSearchItem for the right sibling index page */
- item = palloc(sizeof(GISTSearchItem));
- item-next = NULL;
+ item = palloc(SizeOfGISTSearchItem(scan-numberOfOrderBys));
item-blkno = opaque-rightlink;
item-data.parentlsn = pageItem-data.parentlsn;
/* Insert it into the queue using same distances as for this page */
- tmpItem-head = item;
- tmpItem-lastHeap = NULL;
- memcpy(tmpItem-distances, myDistances,
+ memcpy(item-distances, myDistances,
sizeof(double) * scan-numberOfOrderBys);
- (void) rb_insert(so-queue, (RBNode *) tmpItem, isNew);
+ pairingheap_add(so-queue, item-phNode);
MemoryContextSwitchTo(oldcxt);
}
@@ -348,8 +344,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
oldcxt = MemoryContextSwitchTo(so-queueCxt);
/* Create new GISTSearchItem for this item */
- item = palloc(sizeof(GISTSearchItem));
- item-next = NULL;
+ item = palloc(SizeOfGISTSearchItem(scan-numberOfOrderBys));
if (GistPageIsLeaf(page))
{
@@ -372,12 +367,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
}
/* Insert it into the queue using new distance data */
- tmpItem-head = item;
- tmpItem-lastHeap = GISTSearchItemIsHeap(*item) ? item : NULL;
- memcpy(tmpItem-distances, so-distances,
+ memcpy(item-distances, so-distances,
sizeof(double) * scan-numberOfOrderBys);
- (void) rb_insert(so-queue, (RBNode *) tmpItem, isNew);
+ pairingheap_add(so-queue, item-phNode);
MemoryContextSwitchTo(oldcxt);
}
@@ -390,44 +383,24 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
* Extract next item (in order) from search queue
*
* Returns a GISTSearchItem or NULL. Caller must pfree item when done with it.
- *
- * NOTE: on successful return, so-curTreeItem is the GISTSearchTreeItem that
- * contained the result item. Callers can use so-curTreeItem-distances as
- * the distances value for the item.
*/
static GISTSearchItem *
getNextGISTSearchItem(GISTScanOpaque so)
{
- for (;;)
- {
- GISTSearchItem *item;
-
- /* Update curTreeItem if we don't have one */
- if (so-curTreeItem == NULL)
- {
- so-curTreeItem = (GISTSearchTreeItem *) rb_leftmost(so-queue);
- /* Done when tree is empty */
- if (so-curTreeItem == NULL)
-break;
- }
+ GISTSearchItem *item;
- item = so-curTreeItem-head;
- if (item != NULL)
- {
- /* Delink item from chain */
- so-curTreeItem-head = item-next;
- if (item == so-curTreeItem-lastHeap)
-so-curTreeItem-lastHeap = NULL;
- /* Return item; caller is responsible to pfree it */
- return item;
- }
-
- /* curTreeItem is exhausted, so remove it from rbtree */
- rb_delete(so-queue, (RBNode *) so-curTreeItem);
- so-curTreeItem = NULL;
+ if (!pairingheap_is_empty(so-queue))
+ {
+ item = (GISTSearchItem *) pairingheap_remove_first(so-queue);
+ }
+ else
+ {
+ /* Done when both heaps are empty */
+ item = NULL;
}
- return NULL;
+ /* Return item; caller is responsible to pfree it */
+ return item;
}
/*
@@ -458,7 +431,7 @@ getNextNearest(IndexScanDesc scan)
/* visit an index page, extract its items into queue */
CHECK_FOR_INTERRUPTS();
- gistScanPage(scan, item, so-curTreeItem-distances, NULL, NULL);
+ gistScanPage(scan, item, item-distances, NULL, NULL);
}
pfree(item);
@@ -491,7 +464,6 @@
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 12/15/2014 03:49 AM, Michael Paquier wrote: On Thu, Dec 11, 2014 at 12:50 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 01/28/2014 04:12 PM, Alexander Korotkov wrote: 3. A binary heap would be a better data structure to buffer the rechecked values. A Red-Black tree allows random insertions and deletions, but in this case you need to insert arbitrary values but only remove the minimum item. That's exactly what a binary heap excels at. We have a nice binary heap implementation in the backend that you can use, see src/backend/lib/binaryheap.c. Hmm. For me binary heap would be a better data structure for KNN-GiST at all :-) I decided to give this a shot, replacing the red-black tree in GiST with the binary heap we have in lib/binaryheap.c. It made the GiST code somewhat simpler, as the binaryheap interface is simpler than the red-black tree one. Unfortunately, performance was somewhat worse. That was quite surprising, as insertions and deletions are both O(log N) in both data structures, but the red-black tree implementation is more complicated. I implemented another data structure called a Pairing Heap. It's also a fairly simple data structure, but insertions are O(1) instead of O(log N). It also performs fairly well in practice. With that, I got a small but measurable improvement. To test, I created a table like this: create table gisttest (id integer, p point); insert into gisttest select id, point(random(), random()) from generate_series(1, 100) id; create index i_gisttest on gisttest using gist (p); And I ran this query with pgbench: select id from gisttest order by p - '(0,0)' limit 1000; With unpatched master, I got about 650 TPS, and with the patch 720 TPS. That's a nice little improvement, but perhaps more importantly, the pairing heap implementation consumes less memory. To measure that, I put a MemoryContextStats(so-queueCtx) call into gistendscan. With the above query, but without the limit clause, on master I got: GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks); 21296 used And with the patch: GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks); 21072 used That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to reduce that memory consumption, as there is no hard upper bound on how much might be needed. If the GiST tree is really disorganized for some reason, a query might need a lot more. So all in all, I quite like this patch, even though it doesn't do anything too phenomenal. It adds a some code, in the form of the new pairing heap implementation, but it makes the GiST code a little bit simpler. And it gives a small performance gain, and reduces memory usage a bit. Hum. It looks that this patch using binary heap is intended to be a replacement red-black tree method. Right. Here's a new version of the patch. It now uses the same pairing heap code that I posted in the other thread (advance local xmin more aggressivley, http://www.postgresql.org/message-id/5488acf0.8050...@vmware.com). The pairingheap_remove() function is unused in this patch, but it is needed by that other patch. Any reason why it isn't added to the CF to track it? No. Will add. - Heikki diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c index 7a8692b..e5eb6f6 100644 --- a/src/backend/access/gist/gistget.c +++ b/src/backend/access/gist/gistget.c @@ -18,6 +18,7 @@ #include access/relscan.h #include miscadmin.h #include pgstat.h +#include lib/pairingheap.h #include utils/builtins.h #include utils/memutils.h #include utils/rel.h @@ -243,8 +244,6 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances, GISTPageOpaque opaque; OffsetNumber maxoff; OffsetNumber i; - GISTSearchTreeItem *tmpItem = so-tmpTreeItem; - bool isNew; MemoryContext oldcxt; Assert(!GISTSearchItemIsHeap(*pageItem)); @@ -275,18 +274,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances, oldcxt = MemoryContextSwitchTo(so-queueCxt); /* Create new GISTSearchItem for the right sibling index page */ - item = palloc(sizeof(GISTSearchItem)); - item-next = NULL; + item = palloc(SizeOfGISTSearchItem(scan-numberOfOrderBys)); item-blkno = opaque-rightlink; item-data.parentlsn = pageItem-data.parentlsn; /* Insert it into the queue using same distances as for this page */ - tmpItem-head = item; - tmpItem-lastHeap = NULL; - memcpy(tmpItem-distances, myDistances, + memcpy(item-distances, myDistances, sizeof(double) * scan-numberOfOrderBys); - (void) rb_insert(so-queue, (RBNode *) tmpItem, isNew); + pairingheap_add(so-queue, item-phNode); MemoryContextSwitchTo(oldcxt); } @@ -348,8 +344,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances, oldcxt = MemoryContextSwitchTo(so-queueCxt); /* Create new GISTSearchItem for this item */ - item =
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 2014-12-15 15:08:28 +0200, Heikki Linnakangas wrote: +/*- + * + * pairingheap.c + * A Pairing Heap implementation + * + * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/lib/pairingheap.c + * + *- + */ diff --git a/src/include/lib/pairingheap.h b/src/include/lib/pairingheap.h new file mode 100644 index 000..e78196d --- /dev/null +++ b/src/include/lib/pairingheap.h @@ -0,0 +1,67 @@ +/* + * pairingheap.h + * + * A Pairing Heap implementation + * + * Portions Copyright (c) 2012-2014, PostgreSQL Global Development Group + * + * src/include/lib/pairingheap.h + */ + If we add another heap implementation we probably should at least hint at the different advantages somewhere. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On Thu, Dec 11, 2014 at 12:50 AM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 01/28/2014 04:12 PM, Alexander Korotkov wrote: 3. A binary heap would be a better data structure to buffer the rechecked values. A Red-Black tree allows random insertions and deletions, but in this case you need to insert arbitrary values but only remove the minimum item. That's exactly what a binary heap excels at. We have a nice binary heap implementation in the backend that you can use, see src/backend/lib/binaryheap.c. Hmm. For me binary heap would be a better data structure for KNN-GiST at all :-) I decided to give this a shot, replacing the red-black tree in GiST with the binary heap we have in lib/binaryheap.c. It made the GiST code somewhat simpler, as the binaryheap interface is simpler than the red-black tree one. Unfortunately, performance was somewhat worse. That was quite surprising, as insertions and deletions are both O(log N) in both data structures, but the red-black tree implementation is more complicated. I implemented another data structure called a Pairing Heap. It's also a fairly simple data structure, but insertions are O(1) instead of O(log N). It also performs fairly well in practice. With that, I got a small but measurable improvement. To test, I created a table like this: create table gisttest (id integer, p point); insert into gisttest select id, point(random(), random()) from generate_series(1, 100) id; create index i_gisttest on gisttest using gist (p); And I ran this query with pgbench: select id from gisttest order by p - '(0,0)' limit 1000; With unpatched master, I got about 650 TPS, and with the patch 720 TPS. That's a nice little improvement, but perhaps more importantly, the pairing heap implementation consumes less memory. To measure that, I put a MemoryContextStats(so-queueCtx) call into gistendscan. With the above query, but without the limit clause, on master I got: GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks); 21296 used And with the patch: GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks); 21072 used That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to reduce that memory consumption, as there is no hard upper bound on how much might be needed. If the GiST tree is really disorganized for some reason, a query might need a lot more. So all in all, I quite like this patch, even though it doesn't do anything too phenomenal. It adds a some code, in the form of the new pairing heap implementation, but it makes the GiST code a little bit simpler. And it gives a small performance gain, and reduces memory usage a bit. Hum. It looks that this patch using binary heap is intended to be a replacement red-black tree method. Any reason why it isn't added to the CF to track it? -- Michael -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 01/28/2014 04:12 PM, Alexander Korotkov wrote:
3. A binary heap would be a better data structure to buffer the rechecked
values. A Red-Black tree allows random insertions and deletions, but in
this case you need to insert arbitrary values but only remove the minimum
item. That's exactly what a binary heap excels at. We have a nice binary
heap implementation in the backend that you can use, see
src/backend/lib/binaryheap.c.
Hmm. For me binary heap would be a better data structure for KNN-GiST at
all :-)
I decided to give this a shot, replacing the red-black tree in GiST with
the binary heap we have in lib/binaryheap.c. It made the GiST code
somewhat simpler, as the binaryheap interface is simpler than the
red-black tree one. Unfortunately, performance was somewhat worse. That
was quite surprising, as insertions and deletions are both O(log N) in
both data structures, but the red-black tree implementation is more
complicated.
I implemented another data structure called a Pairing Heap. It's also a
fairly simple data structure, but insertions are O(1) instead of O(log
N). It also performs fairly well in practice.
With that, I got a small but measurable improvement. To test, I created
a table like this:
create table gisttest (id integer, p point);
insert into gisttest select id, point(random(), random()) from
generate_series(1, 100) id;
create index i_gisttest on gisttest using gist (p);
And I ran this query with pgbench:
select id from gisttest order by p - '(0,0)' limit 1000;
With unpatched master, I got about 650 TPS, and with the patch 720 TPS.
That's a nice little improvement, but perhaps more importantly, the
pairing heap implementation consumes less memory. To measure that, I put
a MemoryContextStats(so-queueCtx) call into gistendscan. With the above
query, but without the limit clause, on master I got:
GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998
chunks); 21296 used
And with the patch:
GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502
chunks); 21072 used
That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice
to reduce that memory consumption, as there is no hard upper bound on
how much might be needed. If the GiST tree is really disorganized for
some reason, a query might need a lot more.
So all in all, I quite like this patch, even though it doesn't do
anything too phenomenal. It adds a some code, in the form of the new
pairing heap implementation, but it makes the GiST code a little bit
simpler. And it gives a small performance gain, and reduces memory usage
a bit.
- Heikki
diff --git a/src/backend/access/gist/gistget.c b/src/backend/access/gist/gistget.c
index 7a8692b..52b2c53 100644
--- a/src/backend/access/gist/gistget.c
+++ b/src/backend/access/gist/gistget.c
@@ -18,6 +18,7 @@
#include access/relscan.h
#include miscadmin.h
#include pgstat.h
+#include lib/pairingheap.h
#include utils/builtins.h
#include utils/memutils.h
#include utils/rel.h
@@ -243,8 +244,6 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
GISTPageOpaque opaque;
OffsetNumber maxoff;
OffsetNumber i;
- GISTSearchTreeItem *tmpItem = so-tmpTreeItem;
- bool isNew;
MemoryContext oldcxt;
Assert(!GISTSearchItemIsHeap(*pageItem));
@@ -275,18 +274,15 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
oldcxt = MemoryContextSwitchTo(so-queueCxt);
/* Create new GISTSearchItem for the right sibling index page */
- item = palloc(sizeof(GISTSearchItem));
- item-next = NULL;
+ item = palloc(SizeOfGISTSearchItem(scan-numberOfOrderBys));
item-blkno = opaque-rightlink;
item-data.parentlsn = pageItem-data.parentlsn;
/* Insert it into the queue using same distances as for this page */
- tmpItem-head = item;
- tmpItem-lastHeap = NULL;
- memcpy(tmpItem-distances, myDistances,
+ memcpy(item-distances, myDistances,
sizeof(double) * scan-numberOfOrderBys);
- (void) rb_insert(so-queue, (RBNode *) tmpItem, isNew);
+ pairingheap_add(so-queue, item-fbNode);
MemoryContextSwitchTo(oldcxt);
}
@@ -348,8 +344,7 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
oldcxt = MemoryContextSwitchTo(so-queueCxt);
/* Create new GISTSearchItem for this item */
- item = palloc(sizeof(GISTSearchItem));
- item-next = NULL;
+ item = palloc(SizeOfGISTSearchItem(scan-numberOfOrderBys));
if (GistPageIsLeaf(page))
{
@@ -372,12 +367,10 @@ gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
}
/* Insert it into the queue using new distance data */
- tmpItem-head = item;
- tmpItem-lastHeap = GISTSearchItemIsHeap(*item) ? item : NULL;
- memcpy(tmpItem-distances, so-distances,
+ memcpy(item-distances, so-distances,
sizeof(double) * scan-numberOfOrderBys);
- (void) rb_insert(so-queue, (RBNode *) tmpItem, isNew);
+
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On Wed, Dec 10, 2014 at 1:50 PM, Heikki Linnakangas hlinnakan...@vmware.com wrote: On 01/28/2014 04:12 PM, Alexander Korotkov wrote: 3. A binary heap would be a better data structure to buffer the rechecked values. A Red-Black tree allows random insertions and deletions, but in this case you need to insert arbitrary values but only remove the minimum item. That's exactly what a binary heap excels at. We have a nice binary heap implementation in the backend that you can use, see src/backend/lib/binaryheap.c. Hmm. For me binary heap would be a better data structure for KNN-GiST at all :-) I decided to give this a shot, replacing the red-black tree in GiST with the binary heap we have in lib/binaryheap.c. It made the GiST code somewhat simpler, as the binaryheap interface is simpler than the red-black tree one. Unfortunately, performance was somewhat worse. That was quite surprising, as insertions and deletions are both O(log N) in both data structures, but the red-black tree implementation is more complicated. I implemented another data structure called a Pairing Heap. It's also a fairly simple data structure, but insertions are O(1) instead of O(log N). It also performs fairly well in practice. With that, I got a small but measurable improvement. To test, I created a table like this: create table gisttest (id integer, p point); insert into gisttest select id, point(random(), random()) from generate_series(1, 100) id; create index i_gisttest on gisttest using gist (p); And I ran this query with pgbench: select id from gisttest order by p - '(0,0)' limit 1000; With unpatched master, I got about 650 TPS, and with the patch 720 TPS. That's a nice little improvement, but perhaps more importantly, the pairing heap implementation consumes less memory. To measure that, I put a MemoryContextStats(so-queueCtx) call into gistendscan. With the above query, but without the limit clause, on master I got: GiST scan context: 2109752 total in 10 blocks; 2088456 free (24998 chunks); 21296 used And with the patch: GiST scan context: 1061160 total in 9 blocks; 1040088 free (12502 chunks); 21072 used That's 2MB vs 1MB. While that's not much in absolute terms, it'd be nice to reduce that memory consumption, as there is no hard upper bound on how much might be needed. If the GiST tree is really disorganized for some reason, a query might need a lot more. So all in all, I quite like this patch, even though it doesn't do anything too phenomenal. It adds a some code, in the form of the new pairing heap implementation, but it makes the GiST code a little bit simpler. And it gives a small performance gain, and reduces memory usage a bit. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers It may be better to replace the lib/binaryheap altogether as it offers comparable/better performance.
Re: [HACKERS] GiST kNN search queue (Re: KNN-GiST with recheck)
On 12/10/2014 10:59 PM, Arthur Silva wrote: It may be better to replace the lib/binaryheap altogether as it offers comparable/better performance. It's not always better. A binary heap is more memory-efficient, for starters. There are only two uses of lib/binaryheap: reorderbuffer.c and merge append. Reorderbuffer isn't that performance critical, although a binary heap may well be better there, because the comparison function is very cheap. For merge append, it might be a win, especially if the comparison function is expensive. (That's on the assumption that the overall number of comparisons needed with a pairing heap is smaller - I'm not sure how true that is). That would be worth testing. I'd love to test some other heap implementation in in tuplesort.c. It has a custom binary heap implementation that's used in the final merge phase of an external sort, and also when doing a so-called bounded sort, i.e. ORDER BY x LIMIT Y. But that would be difficult to replace, because tuplesort.c collects tuples in an array in memory, and then turns that into a heap. An array is efficient to turn into a binary heap, but to switch to another data structure, you'd suddenly need extra memory. And we do the switch when we run out of work_mem, so allocating more isn't really an option. - Heikki -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
