diff options
| author | Heikki Linnakangas <heikki.linnakangas@iki.fi> | 2016-09-20 11:38:25 +0300 |
|---|---|---|
| committer | Heikki Linnakangas <heikki.linnakangas@iki.fi> | 2016-09-20 11:38:25 +0300 |
| commit | 45310221a9afccd98e78813459472370ade9dc4c (patch) | |
| tree | b44ad2bee06d77f7cfe8906a8b5630dcd8d61c3c /src/include/access/gist_private.h | |
| parent | 40c3fe4980e73acb0db75a3c737a4a52e09d4cf4 (diff) | |
| download | postgresql-45310221a9afccd98e78813459472370ade9dc4c.tar.gz postgresql-45310221a9afccd98e78813459472370ade9dc4c.zip | |
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.
Diffstat (limited to 'src/include/access/gist_private.h')
| -rw-r--r-- | src/include/access/gist_private.h | 18 |
1 files changed, 7 insertions, 11 deletions
diff --git a/src/include/access/gist_private.h b/src/include/access/gist_private.h index 12315850173..78e87a60771 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, |