Skip to content

Commit 8daeb5d

Browse files
tglsfdctglsfdc
committed
Add SP-GiST (space-partitioned GiST) index access method.
SP-GiST is comparable to GiST in flexibility, but supports non-balanced partitioned search structures rather than balanced trees. As described at PGCon 2011, this new indexing structure can beat GiST in both index build time and query speed for search problems that it is well matched to. There are a number of areas that could still use improvement, but at this point the code seems committable. Teodor Sigaev and Oleg Bartunov, with considerable revisions by Tom Lane
1 parent 19fc0fe commit 8daeb5d

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

46 files changed

+10416
-122
lines changed

‎doc/src/sgml/acronyms.sgml

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -569,6 +569,15 @@
569569
</listitem>
570570
</varlistentry>
571571

572+
<varlistentry>
573+
<term><acronym>SP-GiST</acronym></term>
574+
<listitem>
575+
<para>
576+
<link linkend="SPGiST">Space-Partitioned Generalized Search Tree</link>
577+
</para>
578+
</listitem>
579+
</varlistentry>
580+
572581
<varlistentry>
573582
<term><acronym>SQL</acronym></term>
574583
<listitem>

‎doc/src/sgml/filelist.sgml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,7 @@
8282
<!ENTITY catalogs SYSTEM "catalogs.sgml">
8383
<!ENTITY geqo SYSTEM "geqo.sgml">
8484
<!ENTITY gist SYSTEM "gist.sgml">
85+
<!ENTITY spgist SYSTEM "spgist.sgml">
8586
<!ENTITY gin SYSTEM "gin.sgml">
8687
<!ENTITY planstats SYSTEM "planstats.sgml">
8788
<!ENTITY indexam SYSTEM "indexam.sgml">

‎doc/src/sgml/indices.sgml

Lines changed: 33 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -116,7 +116,7 @@ CREATE INDEX test1_id_index ON test1 (id);
116116

117117
<para>
118118
<productname>PostgreSQL</productname> provides several index types:
119-
B-tree, Hash, GiST and GIN. Each index type uses a different
119+
B-tree, Hash, GiST, SP-GiST and GIN. Each index type uses a different
120120
algorithm that is best suited to different types of queries.
121121
By default, the <command>CREATE INDEX</command> command creates
122122
B-tree indexes, which fit the most common situations.
@@ -253,6 +253,37 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
253253
to do this is again dependent on the particular operator class being used.
254254
</para>
255255

256+
<para>
257+
<indexterm>
258+
<primary>index</primary>
259+
<secondary>SP-GiST</secondary>
260+
</indexterm>
261+
<indexterm>
262+
<primary>SP-GiST</primary>
263+
<see>index</see>
264+
</indexterm>
265+
SP-GiST indexes, like GiST indexes, offer an infrastructure that supports
266+
various kinds of searches. SP-GiST permits implementation of a wide range
267+
of different non-balanced disk-based data structures, such as quadtrees,
268+
k-d trees, and suffix trees (tries). As an example, the standard distribution of
269+
<productname>PostgreSQL</productname> includes SP-GiST operator classes
270+
for two-dimensional points, which support indexed
271+
queries using these operators:
272+
273+
<simplelist>
274+
<member><literal>&lt;&lt;</literal></member>
275+
<member><literal>&gt;&gt;</literal></member>
276+
<member><literal>~=</literal></member>
277+
<member><literal>&lt;@</literal></member>
278+
<member><literal>&lt;^</literal></member>
279+
<member><literal>&gt;^</literal></member>
280+
</simplelist>
281+
282+
(See <xref linkend="functions-geometry"> for the meaning of
283+
these operators.)
284+
For more information see <xref linkend="SPGiST">.
285+
</para>
286+
256287
<para>
257288
<indexterm>
258289
<primary>index</primary>
@@ -263,7 +294,7 @@ SELECT * FROM places ORDER BY location <-> point '(101,456)' LIMIT 10;
263294
<see>index</see>
264295
</indexterm>
265296
GIN indexes are inverted indexes which can handle values that contain more
266-
than one key, arrays for example. Like GiST, GIN can support
297+
than one key, arrays for example. Like GiST and SP-GiST, GIN can support
267298
many different user-defined indexing strategies and the particular
268299
operators with which a GIN index can be used vary depending on the
269300
indexing strategy.

‎doc/src/sgml/mvcc.sgml

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -525,7 +525,7 @@ ERROR: could not serialize access due to concurrent update
525525
As an example,
526526
consider a table <structname>mytab</>, initially containing:
527527
<screen>
528-
class | value
528+
class | value
529529
-------+-------
530530
1 | 10
531531
1 | 20
@@ -1460,7 +1460,7 @@ SELECT pg_advisory_lock(q.id) FROM
14601460
<variablelist>
14611461
<varlistentry>
14621462
<term>
1463-
B-tree and <acronym>GiST</acronym> indexes
1463+
B-tree, <acronym>GiST</acronym> and <acronym>SP-GiST</acronym> indexes
14641464
</term>
14651465
<listitem>
14661466
<para>
@@ -1510,8 +1510,8 @@ SELECT pg_advisory_lock(q.id) FROM
15101510
applications; since they also have more features than hash
15111511
indexes, they are the recommended index type for concurrent
15121512
applications that need to index scalar data. When dealing with
1513-
non-scalar data, B-trees are not useful, and GiST or GIN indexes should
1514-
be used instead.
1513+
non-scalar data, B-trees are not useful, and GiST, SP-GiST or GIN
1514+
indexes should be used instead.
15151515
</para>
15161516
</sect1>
15171517
</chapter>

‎doc/src/sgml/postgres.sgml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -242,6 +242,7 @@
242242
&geqo;
243243
&indexam;
244244
&gist;
245+
&spgist;
245246
&gin;
246247
&storage;
247248
&bki;

‎doc/src/sgml/ref/alter_opfamily.sgml

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -144,8 +144,8 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
144144
and hash functions it is not necessary to specify <replaceable
145145
class="parameter">op_type</replaceable> since the function's input
146146
data type(s) are always the correct ones to use. For B-tree sort
147-
support functions and all functions in GiST and GIN operator classes,
148-
it is necessary to specify the operand data type(s) the function
147+
support functions and all functions in GiST, SP-GiST and GIN operator
148+
classes, it is necessary to specify the operand data type(s) the function
149149
is to be used with.
150150
</para>
151151

@@ -245,8 +245,8 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
245245
type(s). The name of the operator or function occupying the slot is not
246246
mentioned. Also, for <literal>DROP FUNCTION</> the type(s) to specify
247247
are the input data type(s) the function is intended to support; for
248-
GIN and GiST indexes this might have nothing to do with the actual input
249-
argument types of the function.
248+
GiST, SP-GiST and GIN indexes this might have nothing to do with the actual
249+
input argument types of the function.
250250
</para>
251251

252252
<para>

‎doc/src/sgml/ref/create_index.sgml

Lines changed: 23 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -57,7 +57,7 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
5757

5858
<para>
5959
<productname>PostgreSQL</productname> provides the index methods
60-
B-tree, hash, GiST, and GIN. Users can also define their own index
60+
B-tree, hash, GiST, SP-GiST, and GIN. Users can also define their own index
6161
methods, but that is fairly complicated.
6262
</para>
6363

@@ -154,8 +154,8 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
154154
<para>
155155
The name of the index method to be used. Choices are
156156
<literal>btree</literal>, <literal>hash</literal>,
157-
<literal>gist</literal>, and <literal>gin</>. The
158-
default method is <literal>btree</literal>.
157+
<literal>gist</literal>, <literal>spgist</> and <literal>gin</>.
158+
The default method is <literal>btree</literal>.
159159
</para>
160160
</listitem>
161161
</varlistentry>
@@ -281,12 +281,11 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
281281
<para>
282282
The optional <literal>WITH</> clause specifies <firstterm>storage
283283
parameters</> for the index. Each index method has its own set of allowed
284-
storage parameters. The B-tree, hash and GiST index methods all accept a
285-
single parameter:
284+
storage parameters. The B-tree, hash, GiST and SP-GiST index methods all
285+
accept this parameter:
286286
</para>
287287

288288
<variablelist>
289-
290289
<varlistentry>
291290
<term><literal>FILLFACTOR</></term>
292291
<listitem>
@@ -307,15 +306,32 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
307306
</para>
308307
</listitem>
309308
</varlistentry>
309+
</variablelist>
310+
311+
<para>
312+
GiST indexes additionally accept this parameter:
313+
</para>
310314

315+
<variablelist>
316+
<varlistentry>
317+
<term><literal>BUFFERING</></term>
318+
<listitem>
319+
<para>
320+
Determines whether the buffering build technique described in
321+
<xref linkend="gist-buffering-build"> is used to build the index. With
322+
<literal>OFF</> it is disabled, with <literal>ON</> it is enabled, and
323+
with <literal>AUTO</> it is initially disabled, but turned on
324+
on-the-fly once the index size reaches <xref linkend="guc-effective-cache-size">. The default is <literal>AUTO</>.
325+
</para>
326+
</listitem>
327+
</varlistentry>
311328
</variablelist>
312329

313330
<para>
314331
GIN indexes accept a different parameter:
315332
</para>
316333

317334
<variablelist>
318-
319335
<varlistentry>
320336
<term><literal>FASTUPDATE</></term>
321337
<listitem>
@@ -339,27 +355,6 @@ CREATE [ UNIQUE ] INDEX [ CONCURRENTLY ] [ <replaceable class="parameter">name</
339355
</note>
340356
</listitem>
341357
</varlistentry>
342-
343-
</variablelist>
344-
<para>
345-
GiST indexes additionally accept parameter:
346-
</para>
347-
348-
<variablelist>
349-
350-
<varlistentry>
351-
<term><literal>BUFFERING</></term>
352-
<listitem>
353-
<para>
354-
Determines whether the buffering build technique described in
355-
<xref linkend="gist-buffering-build"> is used to build the index. With
356-
<literal>OFF</> it is disabled, with <literal>ON</> it is enabled, and
357-
with <literal>AUTO</> it is initially disabled, but turned on
358-
on-the-fly once the index size reaches <xref linkend="guc-effective-cache-size">. The default is <literal>AUTO</>.
359-
</para>
360-
</listitem>
361-
</varlistentry>
362-
363358
</variablelist>
364359
</refsect2>
365360

‎doc/src/sgml/ref/create_opclass.sgml

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -172,7 +172,7 @@ CREATE OPERATOR CLASS <replaceable class="parameter">name</replaceable> [ DEFAUL
172172
the input data type(s) of the function (for B-tree comparison functions
173173
and hash functions)
174174
or the class's data type (for B-tree sort support functions and all
175-
functions in GiST and GIN operator classes). These defaults
175+
functions in GiST, SP-GiST and GIN operator classes). These defaults
176176
are correct, and so <replaceable
177177
class="parameter">op_type</replaceable> need not be specified in
178178
<literal>FUNCTION</> clauses, except for the case of a B-tree sort
@@ -232,7 +232,7 @@ CREATE OPERATOR CLASS <replaceable class="parameter">name</replaceable> [ DEFAUL
232232
<para>
233233
The data type actually stored in the index. Normally this is
234234
the same as the column data type, but some index methods
235-
(currently GIN and GiST) allow it to be different. The
235+
(currently GiST and GIN) allow it to be different. The
236236
<literal>STORAGE</> clause must be omitted unless the index
237237
method allows a different type to be used.
238238
</para>

‎doc/src/sgml/ref/create_table.sgml

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -540,7 +540,8 @@ CREATE [ [ GLOBAL | LOCAL ] { TEMPORARY | TEMP } | UNLOGGED ] TABLE [ IF NOT EXI
540540
cannot be used. Although it's allowed, there is little point in using
541541
B-tree or hash indexes with an exclusion constraint, because this
542542
does nothing that an ordinary unique constraint doesn't do better.
543-
So in practice the access method will always be <acronym>GiST</>.
543+
So in practice the access method will always be <acronym>GiST</> or
544+
<acronym>SP-GiST</>.
544545
</para>
545546

546547
<para>

0 commit comments

Comments
 (0)