From 2a8d3d83efeafe7f5d7ba2e56d165f2cc78a7d56 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Mon, 7 Nov 2005 17:36:47 +0000 Subject: R-tree is dead ... long live GiST. --- doc/src/sgml/backup.sgml | 6 +-- doc/src/sgml/geqo.sgml | 6 +-- doc/src/sgml/gist.sgml | 31 +++++------ doc/src/sgml/indices.sgml | 105 +++++++++++++++---------------------- doc/src/sgml/mvcc.sgml | 17 +----- doc/src/sgml/ref/create_index.sgml | 27 ++++++---- doc/src/sgml/xindex.sgml | 57 ++++---------------- 7 files changed, 90 insertions(+), 159 deletions(-) (limited to 'doc/src') diff --git a/doc/src/sgml/backup.sgml b/doc/src/sgml/backup.sgml index 1cbe26f77ab..2341105a353 100644 --- a/doc/src/sgml/backup.sgml +++ b/doc/src/sgml/backup.sgml @@ -1,5 +1,5 @@ Backup and Restore @@ -1129,8 +1129,8 @@ restore_command = 'copy /mnt/server/archivedir/%f "%p"' # Windows - Operations on hash and R-tree indexes are - not presently WAL-logged, so replay will not update these index types. + Operations on hash indexes are + not presently WAL-logged, so replay will not update these indexes. The recommended workaround is to manually REINDEX each such index after completing a recovery operation. diff --git a/doc/src/sgml/geqo.sgml b/doc/src/sgml/geqo.sgml index 9de43beeb7c..35bb36f22af 100644 --- a/doc/src/sgml/geqo.sgml +++ b/doc/src/sgml/geqo.sgml @@ -1,5 +1,5 @@ @@ -51,8 +51,8 @@ Genetic Optimizer caused by the support of a variety of join methods (e.g., nested loop, hash join, merge join in PostgreSQL) to process individual joins - and a diversity of indexes (e.g., R-tree, - B-tree, hash in PostgreSQL) as access + and a diversity of indexes (e.g., + B-tree, hash, GiST in PostgreSQL) as access paths for relations. diff --git a/doc/src/sgml/gist.sgml b/doc/src/sgml/gist.sgml index ed4c689a728..56e72f69bea 100644 --- a/doc/src/sgml/gist.sgml +++ b/doc/src/sgml/gist.sgml @@ -1,25 +1,22 @@ GiST Indexes - - Introduction - - index GiST - - GiST - index - + + + Introduction + + GiST stands for Generalized Search Tree. It is a balanced, tree-structured access method, that acts as a base template in - which to implement arbitrary indexing schemes. B+-trees, R-trees and many + which to implement arbitrary indexing schemes. B-trees, R-trees and many other indexing schemes can be implemented in GiST. @@ -60,17 +57,17 @@ $PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.24 2005/11/04 23:14:00 petere Exp This extensibility should not be confused with the extensibility of the other standard search trees in terms of the data they can handle. For - example, PostgreSQL supports extensible B+-trees - and R-trees. That means that you can use - PostgreSQL to build a B+-tree or R-tree over any - data type you want. But B+-trees only support range predicates + example, PostgreSQL supports extensible B-trees + and hash indexes. That means that you can use + PostgreSQL to build a B-tree or hash over any + data type you want. But B-trees only support range predicates (<, =, >), - and R-trees only support n-D range queries (contains, contained, equals). + and hash indexes only support equality queries. So if you index, say, an image collection with a - PostgreSQL B+-tree, you can only issue queries + PostgreSQL B-tree, you can only issue queries such as is imagex equal to imagey, is imagex less than imagey and is imagex greater than imagey? Depending on how you define equals, less than @@ -84,7 +81,7 @@ $PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.24 2005/11/04 23:14:00 petere Exp All it takes to get a GiST access method up and running is to implement seven user-defined methods, which define the behavior of keys in the tree. Of course these methods have to be pretty fancy to - support fancy queries, but for all the standard queries (B+-trees, + support fancy queries, but for all the standard queries (B-trees, R-trees, etc.) they're relatively straightforward. In short, GiST combines extensibility along with generality, code reuse, and a clean interface. diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml index d3bc74da92a..5fa1e79fefb 100644 --- a/doc/src/sgml/indices.sgml +++ b/doc/src/sgml/indices.sgml @@ -1,4 +1,4 @@ - + Indexes @@ -104,7 +104,7 @@ CREATE INDEX test1_id_index ON test1 (id); PostgreSQL provides several index types: - B-tree, R-tree, Hash, and GiST. Each index type uses a different + B-tree, Hash, and GiST. Each index type uses a different algorithm that is best suited to different types of queries. By default, the CREATE INDEX command will create a B-tree index, which fits the most common situations. @@ -152,43 +152,6 @@ CREATE INDEX test1_id_index ON test1 (id); See below. - - - index - R-tree - - - R-tree - index - - R-tree indexes are suited for queries on two-dimensional spatial data. - To create an R-tree index, use a command of the form - -CREATE INDEX name ON table USING rtree (column); - - The PostgreSQL query planner will - consider using an R-tree index whenever an indexed column is - involved in a comparison using one of these operators: - - - << - &< - &> - >> - <<| - &<| - |&> - |>> - ~ - @ - ~= - && - - - (See for the meaning of - these operators.) - - index @@ -208,18 +171,6 @@ CREATE INDEX name ON table - - GiST indexes are not a single kind of index, but rather an infrastructure - within which many different indexing strategies can be implemented. - Accordingly, the particular operators with which a GiST index can be - used vary depending on the indexing strategy (the operator - class). The standard distribution of - PostgreSQL includes GiST operator classes - equivalent to the R-tree operator classes, and many other GiST operator - classes are available in the contrib collection or as separate - projects. For more information see . - - Testing has shown PostgreSQL's hash @@ -230,21 +181,47 @@ CREATE INDEX name ON table after a database crash. For these reasons, hash index use is presently discouraged. + - - Similarly, R-tree indexes do not seem to have any performance - advantages compared to the equivalent operations of GiST indexes. - Like hash indexes, they are not WAL-logged and may need - reindexing after a database crash. - + + + index + GiST + + + GiST + index + + GiST indexes are not a single kind of index, but rather an infrastructure + within which many different indexing strategies can be implemented. + Accordingly, the particular operators with which a GiST index can be + used vary depending on the indexing strategy (the operator + class). As an example, the standard distribution of + PostgreSQL includes GiST operator classes + for several two-dimensional geometric data types, which support indexed + queries using these operators: - - While the problems with hash indexes may be fixed eventually, - it is likely that the R-tree index type will be retired in a future - release. Users are encouraged to migrate applications that use R-tree - indexes to GiST indexes. - - + + << + &< + &> + >> + <<| + &<| + |&> + |>> + ~ + @ + ~= + && + + + (See for the meaning of + these operators.) + Many other GiST operator + classes are available in the contrib collection or as separate + projects. For more information see . + diff --git a/doc/src/sgml/mvcc.sgml b/doc/src/sgml/mvcc.sgml index ea01104d937..9e2adc4e46f 100644 --- a/doc/src/sgml/mvcc.sgml +++ b/doc/src/sgml/mvcc.sgml @@ -1,5 +1,5 @@ @@ -991,18 +991,6 @@ UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 22222; - - - - R-tree indexes - - - - Share/exclusive index-level locks are used for read/write access. - Locks are released after the entire command is done. - - - @@ -1012,8 +1000,7 @@ UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 22222; indexes, they are the recommended index type for concurrent applications that need to index scalar data. When dealing with non-scalar data, B-trees are not useful, and GiST indexes should - be used instead. R-tree indexes are deprecated and are likely - to disappear entirely in a future release. + be used instead. diff --git a/doc/src/sgml/ref/create_index.sgml b/doc/src/sgml/ref/create_index.sgml index 745a0a465e9..676fa8b4e6e 100644 --- a/doc/src/sgml/ref/create_index.sgml +++ b/doc/src/sgml/ref/create_index.sgml @@ -1,5 +1,5 @@ @@ -34,7 +34,7 @@ CREATE [ UNIQUE ] INDEX name ON CREATE INDEX constructs an index index_name on the specified table. Indexes are primarily used to enhance database performance (though - inappropriate use will result in slower performance). + inappropriate use can result in slower performance). @@ -55,11 +55,7 @@ CREATE [ UNIQUE ] INDEX name ON PostgreSQL provides the index methods - B-tree, R-tree, hash, and GiST. The B-tree index method is an - implementation of Lehman-Yao high-concurrency B-trees. The R-tree - index method implements standard R-trees using Guttman's quadratic - split algorithm. The hash index method is an implementation of - Litwin's linear hashing. Users can also define their own index + B-tree, hash, and GiST. Users can also define their own index methods, but that is fairly complicated. @@ -137,9 +133,9 @@ CREATE [ UNIQUE ] INDEX name ON method - The name of the method to be used for the index. Choices are + The name of the index method to be used. Choices are btree, hash, - rtree, and gist. The + and gist. The default method is btree. @@ -243,6 +239,15 @@ CREATE [ UNIQUE ] INDEX name ON IS NULL predicate. + + + Prior releases of PostgreSQL also had an + R-tree index method. This method has been removed because + it had no significant advantages over the GiST method. + If USING rtree is specified, CREATE INDEX + will interpret it as USING gist, to simplify conversion + of old databases to GiST. + @@ -270,13 +275,13 @@ CREATE INDEX code_idx ON films(code) TABLESPACE indexspace; Is this example correct? - To create a R-tree index on a point attribute so that we + To create a GiST index on a point attribute so that we can efficiently use box operators on the result of the conversion function: CREATE INDEX pointloc - ON points USING RTREE (point2box(location) box_ops); + ON points USING GIST (point2box(location) box_ops); SELECT * FROM points WHERE point2box(points.pointloc) = boxes.box; diff --git a/doc/src/sgml/xindex.sgml b/doc/src/sgml/xindex.sgml index 6afcf752205..c63b1a148df 100644 --- a/doc/src/sgml/xindex.sgml +++ b/doc/src/sgml/xindex.sgml @@ -1,5 +1,5 @@ @@ -170,8 +170,12 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp - R-tree indexes express relationships in two-dimensional space. - They use twelve strategies, shown in + GiST indexes are even more flexible: they do not have a fixed set of + strategies at all. Instead, the consistency support routine + of each particular GiST operator class interprets the strategy numbers + however it likes. As an example, several of the built-in GiST index + operator classes index two-dimensional geometric objects, providing + the R-tree strategies shown in . Four of these are true two-dimensional tests (overlaps, same, contains, contained by); four of them consider only the X direction; and the other four @@ -179,7 +183,7 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp - R-tree Strategies + GiST Two-Dimensional <quote>R-tree</> Strategies @@ -240,13 +244,6 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp
- - GiST indexes are even more flexible: they do not have a fixed set of - strategies at all. Instead, the consistency support routine - of each particular GiST operator class interprets the strategy numbers - however it likes. - - Note that all strategy operators return Boolean values. In practice, all operators defined as index method strategies must @@ -274,9 +271,8 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp additional support routines in order to work. For example, the B-tree index method must be able to compare two keys and determine whether one is greater than, equal to, or less than the other. Similarly, the - R-tree index method must be able to compute - intersections, unions, and sizes of rectangles. These - operations do not correspond to operators used in qualifications in + hash index method must be able to compute hash codes for key values. + These operations do not correspond to operators used in qualifications in SQL commands; they are administrative routines used by the index methods, internally. @@ -339,37 +335,6 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp - - R-tree indexes require three support functions, - shown in . - - - - R-tree Support Functions - - - - Function - Support Number - - - - - union - 1 - - - intersection - 2 - - - size - 3 - - - -
- GiST indexes require seven support functions, shown in . @@ -746,7 +711,7 @@ SELECT * FROM table WHERE integer_column < 4; can be satisfied exactly by a B-tree index on the integer column. But there are cases where an index is useful as an inexact guide to - the matching rows. For example, if an R-tree index stores only + the matching rows. For example, if a GiST index stores only bounding boxes for objects, then it cannot exactly satisfy a WHERE condition that tests overlap between nonrectangular objects such as polygons. Yet we could use the index to find objects whose bounding -- cgit v1.2.3