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.

2 files changed, 9 insertions, 13 deletions

diff --git a/src/backend/access/gist/gistscan.c b/src/backend/access/gist/gistscan.c
index ee3289ae8ea..62f1fdd8da2 100644
--- a/src/backend/access/gist/gistscan.c
+++ b/src/backend/access/gist/gistscan.c
@@ -126,7 +126,7 @@ gistrescan(PG_FUNCTION_ARGS)
 	 * 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.
 	 */
@@ -186,7 +186,7 @@ gistrescan(PG_FUNCTION_ARGS)
 												ALLOCSET_DEFAULT_MAXSIZE);
 	}
 
-	/* 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 4f1a5c33eae..8eac5ebd36b 100644
--- a/src/include/access/gist_private.h
+++ b/src/include/access/gist_private.h
@@ -105,15 +105,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 */
@@ -288,8 +284,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,