Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitc6a11b8

Browse files
committed
Teach SPGiST to store nulls and do whole-index scans.
This patch fixes the other major compatibility-breaking limitation ofSPGiST, that it didn't store anything for null values of the indexedcolumn, and so could not support whole-index scans or "x IS NULL"tests. The approach is to create a wholly separate search tree forthe null entries, and use fixed "allTheSame" insertion and searchrules when processing this tree, instead of calling the index opclassmethods. This way the opclass methods do not need to worry aboutdealing with nulls.Catversion bump is for pg_am updates as well as the change in on-diskformat of SPGiST indexes; there are some tweaks in SPGiST WAL recordsas well.Heavily rewritten version of a patch by Oleg Bartunov and Teodor Sigaev.(The original also stored nulls separately, but it reused GIN code to doso; which required undesirable compromises in the on-disk format, andwould likely lead to bugs due to the GIN code being required to work intwo very different contexts.)
1 parentfc227a4 commitc6a11b8

File tree

13 files changed

+534
-166
lines changed

13 files changed

+534
-166
lines changed

‎doc/src/sgml/spgist.sgml

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,18 @@
100100
value when that is needed.
101101
</para>
102102

103+
<note>
104+
<para>
105+
The <acronym>SP-GiST</acronym> core code takes care of NULL entries.
106+
Although <acronym>SP-GiST</acronym> indexes do store entries for nulls
107+
in indexed columns, this is hidden from the index operator class code:
108+
no null index entries or search conditions will ever be passed to the
109+
operator class methods. (It is assumed that <acronym>SP-GiST</acronym>
110+
operators are strict and so cannot succeed for NULL values.) NULLs
111+
are therefore not discussed further here.
112+
</para>
113+
</note>
114+
103115
<para>
104116
There are five user-defined methods that an index operator class for
105117
<acronym>SP-GiST</acronym> must provide. All five follow the convention

‎src/backend/access/spgist/README

Lines changed: 27 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ should have a high fanout to minimize I/O. The challenge is to map tree
1111
nodes to disk pages in such a way that the search algorithm accesses only a
1212
few disk pages, even if it traverses many nodes.
1313

14+
1415
COMMON STRUCTURE DESCRIPTION
1516

1617
Logically, an SP-GiST tree is a set of tuples, each of which can be either
@@ -71,6 +72,21 @@ Leaf tuple consists of:
7172

7273
ItemPointer to the heap
7374

75+
76+
NULLS HANDLING
77+
78+
We assume that SPGiST-indexable operators are strict (can never succeed for
79+
null inputs). It is still desirable to index nulls, so that whole-table
80+
indexscans are possible and so that "x IS NULL" can be implemented by an
81+
SPGiST indexscan. However, we prefer that SPGiST index opclasses not have
82+
to cope with nulls. Therefore, the main tree of an SPGiST index does not
83+
include any null entries. We store null entries in a separate SPGiST tree
84+
occupying a disjoint set of pages (in particular, its own root page).
85+
Insertions and searches in the nulls tree do not use any of the
86+
opclass-supplied functions, but just use hardwired logic comparable to
87+
AllTheSame cases in the normal tree.
88+
89+
7490
INSERTION ALGORITHM
7591

7692
Insertion algorithm is designed to keep the tree in a consistent state at
@@ -181,6 +197,7 @@ described in (5).
181197
and a new tuple to another page, if the list is short enough. This improves
182198
space utilization, but doesn't change the basis of the algorithm.
183199

200+
184201
CONCURRENCY
185202

186203
While descending the tree, the insertion algorithm holds exclusive lock on
@@ -218,6 +235,7 @@ scan that had already visited the parent level could possibly reach such a
218235
redirect tuple, so we can remove redirects once all active transactions have
219236
been flushed out of the system.
220237

238+
221239
DEAD TUPLES
222240

223241
Tuples on leaf pages can be in one of four states:
@@ -269,6 +287,7 @@ to PLACEHOLDER status by VACUUM, and are then candidates for replacement.
269287
DEAD state is not currently possible, since VACUUM does not attempt to
270288
remove unused inner tuples.
271289

290+
272291
VACUUM
273292

274293
VACUUM (or more precisely, spgbulkdelete) performs a single sequential scan
@@ -302,13 +321,16 @@ performed; otherwise, it does an spgbulkdelete scan with an empty target
302321
list, so as to clean up redirections and placeholders, update the free
303322
space map, and gather statistics.
304323

324+
305325
LAST USED PAGE MANAGEMENT
306326

307-
List of last used pages contains four pages - a leaf page and three inner
308-
pages, one from each "triple parity" group. This list is stored between
309-
calls on the index meta page, but updates are never WAL-logged to decrease
310-
WAL traffic. Incorrect data on meta page isn't critical, because we could
311-
allocate a new page at any moment.
327+
The list of last used pages contains four pages - a leaf page and three
328+
inner pages, one from each "triple parity" group. (Actually, there's one
329+
such list for the main tree and a separate one for the nulls tree.) This
330+
list is stored between calls on the index meta page, but updates are never
331+
WAL-logged to decrease WAL traffic. Incorrect data on meta page isn't
332+
critical, because we could allocate a new page at any moment.
333+
312334

313335
AUTHORS
314336

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp