From fd94ac501f11a747093e0fa5af8514af7408dbc3 Mon Sep 17 00:00:00 2001 From: Heikki Linnakangas Date: Tue, 20 Sep 2016 11:38:25 +0300 Subject: [PATCH] Fix outdated comments, GIST search queue is not an RBTree anymore. The GiST search queue is implemented as a pairing heap rather than as Red-Black Tree, since 9.5 (commit e7032610). I neglected these comments in that commit. --- src/backend/access/gist/gistscan.c | 4 ++-- src/include/access/gist_private.h | 18 +++++++----------- 2 files changed, 9 insertions(+), 13 deletions(-) diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c index ba611ee490..2526a3965c 100644 --- a/src/backend/access/gist/gistscan.c +++ b/src/backend/access/gist/gistscan.c @@ -125,7 +125,7 @@ gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, * which is created on the second call and reset on later calls. Thus, in * the common case where a scan is only rescan'd once, we just put the * queue in scanCxt and don't pay the overhead of making a second memory - * context. If we do rescan more than once, the first RBTree is just left + * context. If we do rescan more than once, the first queue is just left * for dead until end of scan; this small wastage seems worth the savings * in the common case. */ @@ -181,7 +181,7 @@ gistrescan(IndexScanDesc scan, ScanKey key, int nkeys, ALLOCSET_DEFAULT_SIZES); } - /* create new, empty RBTree for search queue */ + /* create new, empty pairing heap for search queue */ oldCxt = MemoryContextSwitchTo(so->queueCxt); so->queue = pairingheap_allocate(pairingheap_GISTSearchItem_cmp, scan); MemoryContextSwitchTo(oldCxt); diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index 1231585017..78e87a6077 100644 --- a/src/include/access/gist_private.h +++ b/src/include/access/gist_private.h @@ -107,15 +107,11 @@ typedef struct GISTSTATE * upper index pages; this rule avoids doing extra work during a search that * ends early due to LIMIT. * - * To perform an ordered search, we use an RBTree to manage the distance-order - * queue. Each GISTSearchTreeItem stores all unvisited items of the same - * distance; they are GISTSearchItems chained together via their next fields. - * - * In a non-ordered search (no order-by operators), the RBTree degenerates - * to a single item, which we use as a queue of unvisited index pages only. - * In this case matched heap items from the current index leaf page are - * remembered in GISTScanOpaqueData.pageData[] and returned directly from - * there, instead of building a separate GISTSearchItem for each one. + * To perform an ordered search, we use a pairing heap to manage the + * distance-order queue. In a non-ordered search (no order-by operators), + * we use it to return heap tuples before unvisited index pages, to + * ensure depth-first order, but all entries are otherwise considered + * equal. */ /* Individual heap tuple to be visited */ @@ -298,8 +294,8 @@ typedef struct #define GIST_ROOT_BLKNO 0 /* - * Before PostgreSQL 9.1, we used rely on so-called "invalid tuples" on inner - * pages to finish crash recovery of incomplete page splits. If a crash + * Before PostgreSQL 9.1, we used to rely on so-called "invalid tuples" on + * inner pages to finish crash recovery of incomplete page splits. If a crash * happened in the middle of a page split, so that the downlink pointers were * not yet inserted, crash recovery inserted a special downlink pointer. The * semantics of an invalid tuple was that it if you encounter one in a scan, -- 2.40.0