diff options
46 files changed, 212 insertions, 2953 deletions
diff --git a/contrib/cube/cube.c b/contrib/cube/cube.c index fca03f02d70..0bc88ef6f14 100644 --- a/contrib/cube/cube.c +++ b/contrib/cube/cube.c @@ -10,7 +10,7 @@ #include <math.h> #include "access/gist.h" -#include "access/rtree.h" +#include "access/skey.h" #include "lib/stringinfo.h" #include "utils/builtins.h" diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h index 2231bdb095b..96f2b116a9f 100644 --- a/contrib/intarray/_int.h +++ b/contrib/intarray/_int.h @@ -4,7 +4,7 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" +#include "access/skey.h" #include "catalog/pg_type.h" #include "utils/array.h" #include "utils/builtins.h" diff --git a/contrib/ltree/_ltree_gist.c b/contrib/ltree/_ltree_gist.c index f68e9902b52..0344b6dc134 100644 --- a/contrib/ltree/_ltree_gist.c +++ b/contrib/ltree/_ltree_gist.c @@ -5,8 +5,7 @@ #include "ltree.h" #include "access/gist.h" -#include "access/rtree.h" -#include "access/nbtree.h" +#include "access/skey.h" #include "utils/array.h" #include "crc32.h" diff --git a/contrib/ltree/ltree_gist.c b/contrib/ltree/ltree_gist.c index 7e7ede02853..2be6449329c 100644 --- a/contrib/ltree/ltree_gist.c +++ b/contrib/ltree/ltree_gist.c @@ -5,8 +5,8 @@ #include "ltree.h" #include "access/gist.h" -#include "access/rtree.h" #include "access/nbtree.h" +#include "access/skey.h" #include "utils/array.h" #include "crc32.h" diff --git a/contrib/pg_trgm/trgm_gist.c b/contrib/pg_trgm/trgm_gist.c index 33ed6d5e1f0..9f1c20cf047 100644 --- a/contrib/pg_trgm/trgm_gist.c +++ b/contrib/pg_trgm/trgm_gist.c @@ -2,13 +2,10 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" -#include "utils/elog.h" -#include "utils/palloc.h" +#include "access/tuptoaster.h" +#include "storage/bufpage.h" #include "utils/array.h" #include "utils/builtins.h" -#include "storage/bufpage.h" -#include "access/tuptoaster.h" PG_FUNCTION_INFO_V1(gtrgm_in); Datum gtrgm_in(PG_FUNCTION_ARGS); diff --git a/contrib/seg/seg.c b/contrib/seg/seg.c index 52f65b062c8..0a694a52ddf 100644 --- a/contrib/seg/seg.c +++ b/contrib/seg/seg.c @@ -9,7 +9,7 @@ #include <float.h> #include "access/gist.h" -#include "access/rtree.h" +#include "access/skey.h" #include "utils/builtins.h" #include "segdata.h" @@ -53,7 +53,7 @@ bool *gseg_same(SEG * b1, SEG * b2, bool *result); /* -** R-tree suport functions +** R-tree support functions */ bool seg_same(SEG * a, SEG * b); bool seg_contains_int(SEG * a, int *b); diff --git a/contrib/tsearch2/gistidx.c b/contrib/tsearch2/gistidx.c index c0d15de6913..a01d06d65e7 100644 --- a/contrib/tsearch2/gistidx.c +++ b/contrib/tsearch2/gistidx.c @@ -4,11 +4,10 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" +#include "access/tuptoaster.h" +#include "storage/bufpage.h" #include "utils/array.h" #include "utils/builtins.h" -#include "storage/bufpage.h" -#include "access/tuptoaster.h" #include "tsvector.h" #include "query.h" diff --git a/contrib/tsearch2/query.c b/contrib/tsearch2/query.c index 013f0031965..a260d459355 100644 --- a/contrib/tsearch2/query.c +++ b/contrib/tsearch2/query.c @@ -15,10 +15,9 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" +#include "storage/bufpage.h" #include "utils/array.h" #include "utils/builtins.h" -#include "storage/bufpage.h" #include "ts_cfg.h" #include "tsvector.h" diff --git a/contrib/tsearch2/rewrite.c b/contrib/tsearch2/rewrite.c index e7b5045c9e9..2e9b39f18db 100644 --- a/contrib/tsearch2/rewrite.c +++ b/contrib/tsearch2/rewrite.c @@ -9,7 +9,6 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" #include "storage/bufpage.h" #include "utils/array.h" #include "utils/builtins.h" 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/backup.sgml,v 2.75 2005/11/04 23:13:59 petere Exp $ +$PostgreSQL: pgsql/doc/src/sgml/backup.sgml,v 2.76 2005/11/07 17:36:44 tgl Exp $ --> <chapter id="backup"> <title>Backup and Restore</title> @@ -1129,8 +1129,8 @@ restore_command = 'copy /mnt/server/archivedir/%f "%p"' # Windows <itemizedlist> <listitem> <para> - 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 <command>REINDEX</> each such index after completing a recovery operation. </para> 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/geqo.sgml,v 1.33 2005/10/25 13:38:09 momjian Exp $ +$PostgreSQL: pgsql/doc/src/sgml/geqo.sgml,v 1.34 2005/11/07 17:36:44 tgl Exp $ Genetic Optimizer --> @@ -51,8 +51,8 @@ Genetic Optimizer caused by the support of a variety of <firstterm>join methods</firstterm> (e.g., nested loop, hash join, merge join in <productname>PostgreSQL</productname>) to process individual joins - and a diversity of <firstterm>indexes</firstterm> (e.g., R-tree, - B-tree, hash in <productname>PostgreSQL</productname>) as access + and a diversity of <firstterm>indexes</firstterm> (e.g., + B-tree, hash, GiST in <productname>PostgreSQL</productname>) as access paths for relations. </para> 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.24 2005/11/04 23:14:00 petere Exp $ +$PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.25 2005/11/07 17:36:44 tgl Exp $ --> <chapter id="GiST"> <title>GiST Indexes</title> -<sect1 id="gist-intro"> - <title>Introduction</title> - - <para> <indexterm> <primary>index</primary> <secondary>GiST</secondary> </indexterm> - <indexterm> - <primary>GiST</primary> - <see>index</see> - </indexterm> + +<sect1 id="gist-intro"> + <title>Introduction</title> + + <para> <acronym>GiST</acronym> 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 <acronym>GiST</acronym>. </para> @@ -60,17 +57,17 @@ $PostgreSQL: pgsql/doc/src/sgml/gist.sgml,v 1.24 2005/11/04 23:14:00 petere Exp <para> 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, <productname>PostgreSQL</productname> supports extensible B+-trees - and R-trees. That means that you can use - <productname>PostgreSQL</productname> to build a B+-tree or R-tree over any - data type you want. But B+-trees only support range predicates + example, <productname>PostgreSQL</productname> supports extensible B-trees + and hash indexes. That means that you can use + <productname>PostgreSQL</productname> to build a B-tree or hash over any + data type you want. But B-trees only support range predicates (<literal><</literal>, <literal>=</literal>, <literal>></literal>), - and R-trees only support n-D range queries (contains, contained, equals). + and hash indexes only support equality queries. </para> <para> So if you index, say, an image collection with a - <productname>PostgreSQL</productname> B+-tree, you can only issue queries + <productname>PostgreSQL</productname> B-tree, you can only issue queries such as <quote>is imagex equal to imagey</quote>, <quote>is imagex less than imagey</quote> and <quote>is imagex greater than imagey</quote>? Depending on how you define <quote>equals</quote>, <quote>less than</quote> @@ -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 <acronym>GiST</acronym> 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, <acronym>GiST</acronym> 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 @@ -<!-- $PostgreSQL: pgsql/doc/src/sgml/indices.sgml,v 1.54 2005/11/04 23:14:00 petere Exp $ --> +<!-- $PostgreSQL: pgsql/doc/src/sgml/indices.sgml,v 1.55 2005/11/07 17:36:44 tgl Exp $ --> <chapter id="indexes"> <title id="indexes-title">Indexes</title> @@ -104,7 +104,7 @@ CREATE INDEX test1_id_index ON test1 (id); <para> <productname>PostgreSQL</productname> 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 <command>CREATE INDEX</command> command will create a B-tree index, which fits the most common situations. @@ -155,43 +155,6 @@ CREATE INDEX test1_id_index ON test1 (id); <para> <indexterm> <primary>index</primary> - <secondary>R-tree</secondary> - </indexterm> - <indexterm> - <primary>R-tree</primary> - <see>index</see> - </indexterm> - R-tree indexes are suited for queries on two-dimensional spatial data. - To create an R-tree index, use a command of the form -<synopsis> -CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> USING rtree (<replaceable>column</replaceable>); -</synopsis> - The <productname>PostgreSQL</productname> query planner will - consider using an R-tree index whenever an indexed column is - involved in a comparison using one of these operators: - - <simplelist> - <member><literal><<</literal></member> - <member><literal>&<</literal></member> - <member><literal>&></literal></member> - <member><literal>>></literal></member> - <member><literal><<|</literal></member> - <member><literal>&<|</literal></member> - <member><literal>|&></literal></member> - <member><literal>|>></literal></member> - <member><literal>~</literal></member> - <member><literal>@</literal></member> - <member><literal>~=</literal></member> - <member><literal>&&</literal></member> - </simplelist> - - (See <xref linkend="functions-geometry"> for the meaning of - these operators.) - </para> - - <para> - <indexterm> - <primary>index</primary> <secondary>hash</secondary> </indexterm> <indexterm> @@ -208,18 +171,6 @@ CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> </synopsis> </para> - <para> - 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 <firstterm>operator - class</>). The standard distribution of - <productname>PostgreSQL</productname> includes GiST operator classes - equivalent to the R-tree operator classes, and many other GiST operator - classes are available in the <literal>contrib</> collection or as separate - projects. For more information see <xref linkend="GiST">. - </para> - <note> <para> Testing has shown <productname>PostgreSQL</productname>'s hash @@ -230,21 +181,47 @@ CREATE INDEX <replaceable>name</replaceable> ON <replaceable>table</replaceable> after a database crash. For these reasons, hash index use is presently discouraged. </para> + </note> - <para> - 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. - </para> + <para> + <indexterm> + <primary>index</primary> + <secondary>GiST</secondary> + </indexterm> + <indexterm> + <primary>GiST</primary> + <see>index</see> + </indexterm> + 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 <firstterm>operator + class</>). As an example, the standard distribution of + <productname>PostgreSQL</productname> includes GiST operator classes + for several two-dimensional geometric data types, which support indexed + queries using these operators: - <para> - 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. - </para> - </note> + <simplelist> + <member><literal><<</literal></member> + <member><literal>&<</literal></member> + <member><literal>&></literal></member> + <member><literal>>></literal></member> + <member><literal><<|</literal></member> + <member><literal>&<|</literal></member> + <member><literal>|&></literal></member> + <member><literal>|>></literal></member> + <member><literal>~</literal></member> + <member><literal>@</literal></member> + <member><literal>~=</literal></member> + <member><literal>&&</literal></member> + </simplelist> + + (See <xref linkend="functions-geometry"> for the meaning of + these operators.) + Many other GiST operator + classes are available in the <literal>contrib</> collection or as separate + projects. For more information see <xref linkend="GiST">. + </para> </sect1> 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/mvcc.sgml,v 2.52 2005/10/21 01:41:28 tgl Exp $ +$PostgreSQL: pgsql/doc/src/sgml/mvcc.sgml,v 2.53 2005/11/07 17:36:44 tgl Exp $ --> <chapter id="mvcc"> @@ -991,18 +991,6 @@ UPDATE accounts SET balance = balance - 100.00 WHERE acctnum = 22222; </para> </listitem> </varlistentry> - - <varlistentry> - <term> - R-tree indexes - </term> - <listitem> - <para> - Share/exclusive index-level locks are used for read/write access. - Locks are released after the entire command is done. - </para> - </listitem> - </varlistentry> </variablelist> </para> @@ -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. </para> </sect1> </chapter> 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/ref/create_index.sgml,v 1.51 2005/01/04 00:39:53 tgl Exp $ +$PostgreSQL: pgsql/doc/src/sgml/ref/create_index.sgml,v 1.52 2005/11/07 17:36:44 tgl Exp $ PostgreSQL documentation --> @@ -34,7 +34,7 @@ CREATE [ UNIQUE ] INDEX <replaceable class="parameter">name</replaceable> ON <re <command>CREATE INDEX</command> constructs an index <replaceable class="parameter">index_name</replaceable> 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). </para> <para> @@ -55,11 +55,7 @@ CREATE [ UNIQUE ] INDEX <replaceable class="parameter">name</replaceable> ON <re <para> <productname>PostgreSQL</productname> 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. </para> @@ -137,9 +133,9 @@ CREATE [ UNIQUE ] INDEX <replaceable class="parameter">name</replaceable> ON <re <term><replaceable class="parameter">method</replaceable></term> <listitem> <para> - The name of the method to be used for the index. Choices are + The name of the index method to be used. Choices are <literal>btree</literal>, <literal>hash</literal>, - <literal>rtree</literal>, and <literal>gist</literal>. The + and <literal>gist</literal>. The default method is <literal>btree</literal>. </para> </listitem> @@ -243,6 +239,15 @@ CREATE [ UNIQUE ] INDEX <replaceable class="parameter">name</replaceable> ON <re The best way to use indexes in such cases is to create a partial index using an <literal>IS NULL</> predicate. </para> + + <para> + Prior releases of <productname>PostgreSQL</productname> also had an + R-tree index method. This method has been removed because + it had no significant advantages over the GiST method. + If <literal>USING rtree</> is specified, <command>CREATE INDEX</> + will interpret it as <literal>USING gist</>, to simplify conversion + of old databases to GiST. + </para> </refsect1> <refsect1> @@ -270,13 +275,13 @@ CREATE INDEX code_idx ON films(code) TABLESPACE indexspace; Is this example correct? </comment> <para> - 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: </para> <programlisting> 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; </programlisting> 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 @@ <!-- -$PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp $ +$PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.42 2005/11/07 17:36:44 tgl Exp $ --> <sect1 id="xindex"> @@ -170,8 +170,12 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp </table> <para> - 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 <quote>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 <quote>R-tree</> strategies shown in <xref linkend="xindex-rtree-strat-table">. 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 </para> <table tocentry="1" id="xindex-rtree-strat-table"> - <title>R-tree Strategies</title> + <title>GiST Two-Dimensional <quote>R-tree</> Strategies</title> <tgroup cols="2"> <thead> <row> @@ -241,13 +245,6 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp </table> <para> - GiST indexes are even more flexible: they do not have a fixed set of - strategies at all. Instead, the <quote>consistency</> support routine - of each particular GiST operator class interprets the strategy numbers - however it likes. - </para> - - <para> Note that all strategy operators return Boolean values. In practice, all operators defined as index method strategies must return type <type>boolean</type>, since they must appear at the top @@ -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. </para> @@ -340,37 +336,6 @@ $PostgreSQL: pgsql/doc/src/sgml/xindex.sgml,v 1.41 2005/07/19 01:27:59 neilc Exp </table> <para> - R-tree indexes require three support functions, - shown in <xref linkend="xindex-rtree-support-table">. - </para> - - <table tocentry="1" id="xindex-rtree-support-table"> - <title>R-tree Support Functions</title> - <tgroup cols="2"> - <thead> - <row> - <entry>Function</entry> - <entry>Support Number</entry> - </row> - </thead> - <tbody> - <row> - <entry>union</entry> - <entry>1</entry> - </row> - <row> - <entry>intersection</entry> - <entry>2</entry> - </row> - <row> - <entry>size</entry> - <entry>3</entry> - </row> - </tbody> - </tgroup> - </table> - - <para> GiST indexes require seven support functions, shown in <xref linkend="xindex-gist-support-table">. </para> @@ -746,7 +711,7 @@ SELECT * FROM table WHERE integer_column < 4; </programlisting> 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 <literal>WHERE</> condition that tests overlap between nonrectangular objects such as polygons. Yet we could use the index to find objects whose bounding diff --git a/src/backend/access/Makefile b/src/backend/access/Makefile index 769ed8eecb1..82cd7a90ed5 100644 --- a/src/backend/access/Makefile +++ b/src/backend/access/Makefile @@ -1,14 +1,14 @@ # # Makefile for the access methods module # -# $PostgreSQL: pgsql/src/backend/access/Makefile,v 1.9 2003/11/29 19:51:39 pgsql Exp $ +# $PostgreSQL: pgsql/src/backend/access/Makefile,v 1.10 2005/11/07 17:36:44 tgl Exp $ # subdir = src/backend/access top_builddir = ../../.. include $(top_builddir)/src/Makefile.global -SUBDIRS := common gist hash heap index nbtree rtree transam +SUBDIRS := common gist hash heap index nbtree transam SUBDIROBJS := $(SUBDIRS:%=%/SUBSYS.o) all: SUBSYS.o diff --git a/src/backend/access/gist/gistproc.c b/src/backend/access/gist/gistproc.c index b9e0469b05b..25531259124 100644 --- a/src/backend/access/gist/gistproc.c +++ b/src/backend/access/gist/gistproc.c @@ -10,7 +10,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/gist/gistproc.c,v 1.3 2005/10/15 02:49:08 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/access/gist/gistproc.c,v 1.4 2005/11/07 17:36:44 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -18,7 +18,7 @@ #include "access/gist.h" #include "access/itup.h" -#include "access/rtree.h" +#include "access/skey.h" #include "utils/geo_decls.h" @@ -40,6 +40,47 @@ static bool rtree_internal_consistent(BOX *key, BOX *query, * Box ops **************************************************/ +static Datum +rt_box_union(PG_FUNCTION_ARGS) +{ + BOX *a = PG_GETARG_BOX_P(0); + BOX *b = PG_GETARG_BOX_P(1); + BOX *n; + + n = (BOX *) palloc(sizeof(BOX)); + + n->high.x = Max(a->high.x, b->high.x); + n->high.y = Max(a->high.y, b->high.y); + n->low.x = Min(a->low.x, b->low.x); + n->low.y = Min(a->low.y, b->low.y); + + PG_RETURN_BOX_P(n); +} + +static Datum +rt_box_inter(PG_FUNCTION_ARGS) +{ + BOX *a = PG_GETARG_BOX_P(0); + BOX *b = PG_GETARG_BOX_P(1); + BOX *n; + + n = (BOX *) palloc(sizeof(BOX)); + + n->high.x = Min(a->high.x, b->high.x); + n->high.y = Min(a->high.y, b->high.y); + n->low.x = Max(a->low.x, b->low.x); + n->low.y = Max(a->low.y, b->low.y); + + if (n->high.x < n->low.x || n->high.y < n->low.y) + { + pfree(n); + /* Indicate "no intersection" by returning NULL pointer */ + n = NULL; + } + + PG_RETURN_BOX_P(n); +} + /* * The GiST Consistent method for boxes * @@ -493,8 +534,6 @@ size_box(Datum dbox) * * We can use the same function since all types use bounding boxes as the * internal-page representation. - * - * This implements the same logic as the rtree internal-page strategy map. */ static bool rtree_internal_consistent(BOX *key, BOX *query, StrategyNumber strategy) diff --git a/src/backend/access/rtree/Makefile b/src/backend/access/rtree/Makefile deleted file mode 100644 index d53626c637d..00000000000 --- a/src/backend/access/rtree/Makefile +++ /dev/null @@ -1,31 +0,0 @@ -#------------------------------------------------------------------------- -# -# Makefile-- -# Makefile for access/rtree -# -# IDENTIFICATION -# $PostgreSQL: pgsql/src/backend/access/rtree/Makefile,v 1.11 2003/11/29 19:51:40 pgsql Exp $ -# -#------------------------------------------------------------------------- - -subdir = src/backend/access/rtree -top_builddir = ../../../.. -include $(top_builddir)/src/Makefile.global - -OBJS = rtget.o rtproc.o rtree.o rtscan.o rtstrat.o - -all: SUBSYS.o - -SUBSYS.o: $(OBJS) - $(LD) $(LDREL) $(LDOUT) SUBSYS.o $(OBJS) - -depend dep: - $(CC) -MM $(CFLAGS) *.c >depend - -clean: - rm -f SUBSYS.o $(OBJS) - -ifeq (depend,$(wildcard depend)) -include depend -endif - diff --git a/src/backend/access/rtree/rtget.c b/src/backend/access/rtree/rtget.c deleted file mode 100644 index 010a493d20e..00000000000 --- a/src/backend/access/rtree/rtget.c +++ /dev/null @@ -1,281 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtget.c - * fetch tuples from an rtree scan. - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/rtree/rtget.c,v 1.37 2005/10/15 02:49:09 momjian Exp $ - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "access/iqual.h" -#include "access/relscan.h" -#include "access/rtree.h" -#include "pgstat.h" - - -static OffsetNumber findnext(IndexScanDesc s, OffsetNumber n, - ScanDirection dir); -static bool rtnext(IndexScanDesc s, ScanDirection dir); - - -Datum -rtgettuple(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1); - RTreeScanOpaque so = (RTreeScanOpaque) s->opaque; - Page page; - OffsetNumber offnum; - - /* - * If we've already produced a tuple and the executor has informed us that - * it should be marked "killed", do so now. - */ - if (s->kill_prior_tuple && ItemPointerIsValid(&(s->currentItemData))) - { - offnum = ItemPointerGetOffsetNumber(&(s->currentItemData)); - page = BufferGetPage(so->curbuf); - PageGetItemId(page, offnum)->lp_flags |= LP_DELETE; - SetBufferCommitInfoNeedsSave(so->curbuf); - } - - /* - * Get the next tuple that matches the search key; if asked to skip killed - * tuples, find the first non-killed tuple that matches. Return as soon as - * we've run out of matches or we've found an acceptable match. - */ - for (;;) - { - bool res = rtnext(s, dir); - - if (res && s->ignore_killed_tuples) - { - offnum = ItemPointerGetOffsetNumber(&(s->currentItemData)); - page = BufferGetPage(so->curbuf); - if (ItemIdDeleted(PageGetItemId(page, offnum))) - continue; - } - - PG_RETURN_BOOL(res); - } -} - -Datum -rtgetmulti(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - ItemPointer tids = (ItemPointer) PG_GETARG_POINTER(1); - int32 max_tids = PG_GETARG_INT32(2); - int32 *returned_tids = (int32 *) PG_GETARG_POINTER(3); - RTreeScanOpaque so = (RTreeScanOpaque) s->opaque; - bool res = true; - int32 ntids = 0; - - /* XXX generic implementation: loop around guts of rtgettuple */ - while (ntids < max_tids) - { - res = rtnext(s, ForwardScanDirection); - if (res && s->ignore_killed_tuples) - { - Page page; - OffsetNumber offnum; - - offnum = ItemPointerGetOffsetNumber(&(s->currentItemData)); - page = BufferGetPage(so->curbuf); - if (ItemIdDeleted(PageGetItemId(page, offnum))) - continue; - } - - if (!res) - break; - tids[ntids] = s->xs_ctup.t_self; - ntids++; - } - - *returned_tids = ntids; - PG_RETURN_BOOL(res); -} - -static bool -rtnext(IndexScanDesc s, ScanDirection dir) -{ - Page p; - OffsetNumber n; - RTreePageOpaque po; - RTreeScanOpaque so; - - so = (RTreeScanOpaque) s->opaque; - - if (!ItemPointerIsValid(&(s->currentItemData))) - { - /* first call: start at the root */ - Assert(BufferIsValid(so->curbuf) == false); - so->curbuf = ReadBuffer(s->indexRelation, P_ROOT); - pgstat_count_index_scan(&s->xs_pgstat_info); - } - - p = BufferGetPage(so->curbuf); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - if (!ItemPointerIsValid(&(s->currentItemData))) - { - /* first call: start at first/last offset */ - if (ScanDirectionIsForward(dir)) - n = FirstOffsetNumber; - else - n = PageGetMaxOffsetNumber(p); - } - else - { - /* go on to the next offset */ - n = ItemPointerGetOffsetNumber(&(s->currentItemData)); - if (ScanDirectionIsForward(dir)) - n = OffsetNumberNext(n); - else - n = OffsetNumberPrev(n); - } - - for (;;) - { - IndexTuple it; - RTSTACK *stk; - - n = findnext(s, n, dir); - - /* no match on this page, so read in the next stack entry */ - if (n == InvalidOffsetNumber) - { - /* if out of stack entries, we're done */ - if (so->s_stack == NULL) - { - ReleaseBuffer(so->curbuf); - so->curbuf = InvalidBuffer; - return false; - } - - stk = so->s_stack; - so->curbuf = ReleaseAndReadBuffer(so->curbuf, s->indexRelation, - stk->rts_blk); - p = BufferGetPage(so->curbuf); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - if (ScanDirectionIsBackward(dir)) - n = OffsetNumberPrev(stk->rts_child); - else - n = OffsetNumberNext(stk->rts_child); - so->s_stack = stk->rts_parent; - pfree(stk); - - continue; - } - - if (po->flags & F_LEAF) - { - ItemPointerSet(&(s->currentItemData), - BufferGetBlockNumber(so->curbuf), - n); - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - s->xs_ctup.t_self = it->t_tid; - return true; - } - else - { - BlockNumber blk; - - stk = (RTSTACK *) palloc(sizeof(RTSTACK)); - stk->rts_child = n; - stk->rts_blk = BufferGetBlockNumber(so->curbuf); - stk->rts_parent = so->s_stack; - so->s_stack = stk; - - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - blk = ItemPointerGetBlockNumber(&(it->t_tid)); - - /* - * Note that we release the pin on the page as we descend down the - * tree, even though there's a good chance we'll eventually need - * to re-read the buffer later in this scan. This may or may not - * be optimal, but it doesn't seem likely to make a huge - * performance difference either way. - */ - so->curbuf = ReleaseAndReadBuffer(so->curbuf, s->indexRelation, blk); - p = BufferGetPage(so->curbuf); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - if (ScanDirectionIsBackward(dir)) - n = PageGetMaxOffsetNumber(p); - else - n = FirstOffsetNumber; - } - } -} - -/* - * Return the offset of the next matching index entry. We begin the - * search at offset "n" and search for matches in the direction - * "dir". If no more matching entries are found on the page, - * InvalidOffsetNumber is returned. - */ -static OffsetNumber -findnext(IndexScanDesc s, OffsetNumber n, ScanDirection dir) -{ - OffsetNumber maxoff; - IndexTuple it; - RTreePageOpaque po; - RTreeScanOpaque so; - Page p; - - so = (RTreeScanOpaque) s->opaque; - p = BufferGetPage(so->curbuf); - - maxoff = PageGetMaxOffsetNumber(p); - po = (RTreePageOpaque) PageGetSpecialPointer(p); - - /* - * If we modified the index during the scan, we may have a pointer to a - * ghost tuple, before the scan. If this is the case, back up one. - */ - - if (so->s_flags & RTS_CURBEFORE) - { - so->s_flags &= ~RTS_CURBEFORE; - n = OffsetNumberPrev(n); - } - - while (n >= FirstOffsetNumber && n <= maxoff) - { - it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); - if (po->flags & F_LEAF) - { - if (index_keytest(it, - RelationGetDescr(s->indexRelation), - s->numberOfKeys, s->keyData)) - break; - } - else - { - if (index_keytest(it, - RelationGetDescr(s->indexRelation), - so->s_internalNKey, so->s_internalKey)) - break; - } - - if (ScanDirectionIsBackward(dir)) - n = OffsetNumberPrev(n); - else - n = OffsetNumberNext(n); - } - - if (n >= FirstOffsetNumber && n <= maxoff) - return n; /* found a match on this page */ - else - return InvalidOffsetNumber; /* no match, go to next page */ -} diff --git a/src/backend/access/rtree/rtproc.c b/src/backend/access/rtree/rtproc.c deleted file mode 100644 index 292dac6a130..00000000000 --- a/src/backend/access/rtree/rtproc.c +++ /dev/null @@ -1,175 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtproc.c - * pg_amproc entries for rtrees. - * - * NOTE: for largely-historical reasons, the intersection functions should - * return a NULL pointer (*not* an SQL null value) to indicate "no - * intersection". The size functions must be prepared to accept such - * a pointer and return 0. This convention means that only pass-by-reference - * data types can be used as the output of the union and intersection - * routines, but that's not a big problem. - * - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/rtree/rtproc.c,v 1.43 2005/10/15 02:49:09 momjian Exp $ - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "utils/geo_decls.h" - - -Datum -rt_box_union(PG_FUNCTION_ARGS) -{ - BOX *a = PG_GETARG_BOX_P(0); - BOX *b = PG_GETARG_BOX_P(1); - BOX *n; - - n = (BOX *) palloc(sizeof(BOX)); - - n->high.x = Max(a->high.x, b->high.x); - n->high.y = Max(a->high.y, b->high.y); - n->low.x = Min(a->low.x, b->low.x); - n->low.y = Min(a->low.y, b->low.y); - - PG_RETURN_BOX_P(n); -} - -Datum -rt_box_inter(PG_FUNCTION_ARGS) -{ - BOX *a = PG_GETARG_BOX_P(0); - BOX *b = PG_GETARG_BOX_P(1); - BOX *n; - - n = (BOX *) palloc(sizeof(BOX)); - - n->high.x = Min(a->high.x, b->high.x); - n->high.y = Min(a->high.y, b->high.y); - n->low.x = Max(a->low.x, b->low.x); - n->low.y = Max(a->low.y, b->low.y); - - if (n->high.x < n->low.x || n->high.y < n->low.y) - { - pfree(n); - /* Indicate "no intersection" by returning NULL pointer */ - n = NULL; - } - - PG_RETURN_BOX_P(n); -} - -Datum -rt_box_size(PG_FUNCTION_ARGS) -{ - BOX *a = PG_GETARG_BOX_P(0); - - /* NB: size is an output argument */ - float *size = (float *) PG_GETARG_POINTER(1); - - if (a == NULL || a->high.x <= a->low.x || a->high.y <= a->low.y) - *size = 0.0; - else - *size = (float) ((a->high.x - a->low.x) * (a->high.y - a->low.y)); - - PG_RETURN_VOID(); -} - -Datum -rt_poly_union(PG_FUNCTION_ARGS) -{ - POLYGON *a = PG_GETARG_POLYGON_P(0); - POLYGON *b = PG_GETARG_POLYGON_P(1); - POLYGON *p; - - p = (POLYGON *) palloc0(sizeof(POLYGON)); /* zero any holes */ - p->size = sizeof(POLYGON); - p->npts = 0; - p->boundbox.high.x = Max(a->boundbox.high.x, b->boundbox.high.x); - p->boundbox.high.y = Max(a->boundbox.high.y, b->boundbox.high.y); - p->boundbox.low.x = Min(a->boundbox.low.x, b->boundbox.low.x); - p->boundbox.low.y = Min(a->boundbox.low.y, b->boundbox.low.y); - - /* Avoid leaking memory when handed toasted input. */ - PG_FREE_IF_COPY(a, 0); - PG_FREE_IF_COPY(b, 1); - - PG_RETURN_POLYGON_P(p); -} - -Datum -rt_poly_inter(PG_FUNCTION_ARGS) -{ - POLYGON *a = PG_GETARG_POLYGON_P(0); - POLYGON *b = PG_GETARG_POLYGON_P(1); - POLYGON *p; - - p = (POLYGON *) palloc0(sizeof(POLYGON)); /* zero any holes */ - p->size = sizeof(POLYGON); - p->npts = 0; - p->boundbox.high.x = Min(a->boundbox.high.x, b->boundbox.high.x); - p->boundbox.high.y = Min(a->boundbox.high.y, b->boundbox.high.y); - p->boundbox.low.x = Max(a->boundbox.low.x, b->boundbox.low.x); - p->boundbox.low.y = Max(a->boundbox.low.y, b->boundbox.low.y); - - if (p->boundbox.high.x < p->boundbox.low.x || - p->boundbox.high.y < p->boundbox.low.y) - { - pfree(p); - /* Indicate "no intersection" by returning NULL pointer */ - p = NULL; - } - - /* Avoid leaking memory when handed toasted input. */ - PG_FREE_IF_COPY(a, 0); - PG_FREE_IF_COPY(b, 1); - - PG_RETURN_POLYGON_P(p); -} - -Datum -rt_poly_size(PG_FUNCTION_ARGS) -{ - Pointer aptr = PG_GETARG_POINTER(0); - - /* NB: size is an output argument */ - float *size = (float *) PG_GETARG_POINTER(1); - POLYGON *a; - double xdim, - ydim; - - /* - * Can't just use GETARG because of possibility that input is NULL; since - * POLYGON is toastable, GETARG will try to inspect its value - */ - if (aptr == NULL) - { - *size = 0.0; - PG_RETURN_VOID(); - } - /* Now safe to apply GETARG */ - a = PG_GETARG_POLYGON_P(0); - - if (a->boundbox.high.x <= a->boundbox.low.x || - a->boundbox.high.y <= a->boundbox.low.y) - *size = 0.0; - else - { - xdim = (a->boundbox.high.x - a->boundbox.low.x); - ydim = (a->boundbox.high.y - a->boundbox.low.y); - - *size = (float) (xdim * ydim); - } - - /* Avoid leaking memory when handed toasted input. */ - PG_FREE_IF_COPY(a, 0); - - PG_RETURN_VOID(); -} diff --git a/src/backend/access/rtree/rtree.c b/src/backend/access/rtree/rtree.c deleted file mode 100644 index d684101d261..00000000000 --- a/src/backend/access/rtree/rtree.c +++ /dev/null @@ -1,1298 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtree.c - * interface routines for the postgres rtree indexed access method. - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/rtree/rtree.c,v 1.92 2005/10/15 02:49:09 momjian Exp $ - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "access/genam.h" -#include "access/heapam.h" -#include "access/rtree.h" -#include "access/xlogutils.h" -#include "catalog/index.h" -#include "commands/vacuum.h" -#include "executor/executor.h" -#include "miscadmin.h" - - -/* - * XXX We assume that all datatypes indexable in rtrees are pass-by-reference. - * To fix this, you'd need to improve the IndexTupleGetDatum() macro, and - * do something with the various datum-pfreeing code. However, it's not that - * unreasonable an assumption in practice. - */ -#define IndexTupleGetDatum(itup) \ - PointerGetDatum(((char *) (itup)) + sizeof(IndexTupleData)) - -/* - * Space-allocation macros. Note we count the item's line pointer in its size. - */ -#define RTPageAvailSpace \ - (BLCKSZ - (sizeof(PageHeaderData) - sizeof(ItemIdData)) \ - - MAXALIGN(sizeof(RTreePageOpaqueData))) -#define IndexTupleTotalSize(itup) \ - (MAXALIGN(IndexTupleSize(itup)) + sizeof(ItemIdData)) -#define IndexTupleAttSize(itup) \ - (IndexTupleSize(itup) - sizeof(IndexTupleData)) - -/* results of rtpicksplit() */ -typedef struct SPLITVEC -{ - OffsetNumber *spl_left; - int spl_nleft; - Datum spl_ldatum; - OffsetNumber *spl_right; - int spl_nright; - Datum spl_rdatum; -} SPLITVEC; - -/* for sorting tuples by cost, for picking split */ -typedef struct SPLITCOST -{ - OffsetNumber offset_number; - float cost_differential; - bool choose_left; -} SPLITCOST; - -typedef struct RTSTATE -{ - FmgrInfo unionFn; /* union function */ - FmgrInfo sizeFn; /* size function */ - FmgrInfo interFn; /* intersection function */ -} RTSTATE; - -/* Working state for rtbuild and its callback */ -typedef struct -{ - RTSTATE rtState; - double indtuples; -} RTBuildState; - -/* non-export function prototypes */ -static void rtbuildCallback(Relation index, - HeapTuple htup, - Datum *values, - bool *isnull, - bool tupleIsAlive, - void *state); -static void rtdoinsert(Relation r, IndexTuple itup, RTSTATE *rtstate); -static void rttighten(Relation r, RTSTACK *stk, Datum datum, int att_size, - RTSTATE *rtstate); -static void rtdosplit(Relation r, Buffer buffer, RTSTACK *stack, - IndexTuple itup, RTSTATE *rtstate); -static void rtintinsert(Relation r, RTSTACK *stk, IndexTuple ltup, - IndexTuple rtup, RTSTATE *rtstate); -static void rtnewroot(Relation r, IndexTuple lt, IndexTuple rt); -static void rtpicksplit(Relation r, Page page, SPLITVEC *v, IndexTuple itup, - RTSTATE *rtstate); -static void RTInitBuffer(Buffer b, uint32 f); -static OffsetNumber choose(Relation r, Page p, IndexTuple it, - RTSTATE *rtstate); -static int nospace(Page p, IndexTuple it); -static void initRtstate(RTSTATE *rtstate, Relation index); -static int qsort_comp_splitcost(const void *a, const void *b); - - -/* - * routine to build an index. Basically calls insert over and over - */ -Datum -rtbuild(PG_FUNCTION_ARGS) -{ - Relation heap = (Relation) PG_GETARG_POINTER(0); - Relation index = (Relation) PG_GETARG_POINTER(1); - IndexInfo *indexInfo = (IndexInfo *) PG_GETARG_POINTER(2); - double reltuples; - RTBuildState buildstate; - Buffer buffer; - - /* no locking is needed */ - - initRtstate(&buildstate.rtState, index); - - /* - * We expect to be called exactly once for any index relation. If that's - * not the case, big trouble's what we have. - */ - if (RelationGetNumberOfBlocks(index) != 0) - elog(ERROR, "index \"%s\" already contains data", - RelationGetRelationName(index)); - - /* initialize the root page */ - buffer = ReadBuffer(index, P_NEW); - RTInitBuffer(buffer, F_LEAF); - WriteBuffer(buffer); - - /* build the index */ - buildstate.indtuples = 0; - - /* do the heap scan */ - reltuples = IndexBuildHeapScan(heap, index, indexInfo, - rtbuildCallback, (void *) &buildstate); - - /* okay, all heap tuples are indexed */ - - /* since we just counted the # of tuples, may as well update stats */ - IndexCloseAndUpdateStats(heap, reltuples, index, buildstate.indtuples); - - PG_RETURN_VOID(); -} - -/* - * Per-tuple callback from IndexBuildHeapScan - */ -static void -rtbuildCallback(Relation index, - HeapTuple htup, - Datum *values, - bool *isnull, - bool tupleIsAlive, - void *state) -{ - RTBuildState *buildstate = (RTBuildState *) state; - IndexTuple itup; - - /* form an index tuple and point it at the heap tuple */ - itup = index_form_tuple(RelationGetDescr(index), values, isnull); - itup->t_tid = htup->t_self; - - /* rtree indexes don't index nulls, see notes in rtinsert */ - if (IndexTupleHasNulls(itup)) - { - pfree(itup); - return; - } - - /* - * Since we already have the index relation locked, we call rtdoinsert - * directly. Normal access method calls dispatch through rtinsert, which - * locks the relation for write. This is the right thing to do if you're - * inserting single tups, but not when you're initializing the whole index - * at once. - */ - rtdoinsert(index, itup, &buildstate->rtState); - - buildstate->indtuples += 1; - - pfree(itup); -} - -/* - * rtinsert -- wrapper for rtree tuple insertion. - * - * This is the public interface routine for tuple insertion in rtrees. - * It doesn't do any work; just locks the relation and passes the buck. - */ -Datum -rtinsert(PG_FUNCTION_ARGS) -{ - Relation r = (Relation) PG_GETARG_POINTER(0); - Datum *values = (Datum *) PG_GETARG_POINTER(1); - bool *isnull = (bool *) PG_GETARG_POINTER(2); - ItemPointer ht_ctid = (ItemPointer) PG_GETARG_POINTER(3); - -#ifdef NOT_USED - Relation heapRel = (Relation) PG_GETARG_POINTER(4); - bool checkUnique = PG_GETARG_BOOL(5); -#endif - IndexTuple itup; - RTSTATE rtState; - - /* generate an index tuple */ - itup = index_form_tuple(RelationGetDescr(r), values, isnull); - itup->t_tid = *ht_ctid; - - /* - * Currently, rtrees do not support indexing NULLs; considerable - * infrastructure work would have to be done to do anything reasonable - * with a NULL. - */ - if (IndexTupleHasNulls(itup)) - { - pfree(itup); - PG_RETURN_BOOL(false); - } - - initRtstate(&rtState, r); - - /* - * Since rtree is not marked "amconcurrent" in pg_am, caller should have - * acquired exclusive lock on index relation. We need no locking here. - */ - rtdoinsert(r, itup, &rtState); - - PG_RETURN_BOOL(true); -} - -static void -rtdoinsert(Relation r, IndexTuple itup, RTSTATE *rtstate) -{ - Page page; - Buffer buffer; - BlockNumber blk; - IndexTuple which; - OffsetNumber l; - RTSTACK *stack; - RTreePageOpaque opaque; - Datum datum; - - blk = P_ROOT; - buffer = InvalidBuffer; - stack = NULL; - - do - { - /* release the current buffer, read in the next one */ - buffer = ReleaseAndReadBuffer(buffer, r, blk); - page = (Page) BufferGetPage(buffer); - - opaque = (RTreePageOpaque) PageGetSpecialPointer(page); - if (!(opaque->flags & F_LEAF)) - { - RTSTACK *n; - ItemId iid; - - n = (RTSTACK *) palloc(sizeof(RTSTACK)); - n->rts_parent = stack; - n->rts_blk = blk; - n->rts_child = choose(r, page, itup, rtstate); - stack = n; - - iid = PageGetItemId(page, n->rts_child); - which = (IndexTuple) PageGetItem(page, iid); - blk = ItemPointerGetBlockNumber(&(which->t_tid)); - } - } while (!(opaque->flags & F_LEAF)); - - if (nospace(page, itup)) - { - /* need to do a split */ - rtdosplit(r, buffer, stack, itup, rtstate); - freestack(stack); - WriteBuffer(buffer); /* don't forget to release buffer! */ - return; - } - - /* add the item and write the buffer */ - if (PageIsEmpty(page)) - { - l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), - FirstOffsetNumber, - LP_USED); - } - else - { - l = PageAddItem(page, (Item) itup, IndexTupleSize(itup), - OffsetNumberNext(PageGetMaxOffsetNumber(page)), - LP_USED); - } - if (l == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - - WriteBuffer(buffer); - - datum = IndexTupleGetDatum(itup); - - /* now expand the page boundary in the parent to include the new child */ - rttighten(r, stack, datum, IndexTupleAttSize(itup), rtstate); - freestack(stack); -} - -static void -rttighten(Relation r, - RTSTACK *stk, - Datum datum, - int att_size, - RTSTATE *rtstate) -{ - Datum oldud; - Datum tdatum; - Page p; - float old_size, - newd_size; - Buffer b; - - if (stk == NULL) - return; - - b = ReadBuffer(r, stk->rts_blk); - p = BufferGetPage(b); - - oldud = IndexTupleGetDatum(PageGetItem(p, - PageGetItemId(p, stk->rts_child))); - - FunctionCall2(&rtstate->sizeFn, oldud, - PointerGetDatum(&old_size)); - - datum = FunctionCall2(&rtstate->unionFn, oldud, datum); - - FunctionCall2(&rtstate->sizeFn, datum, - PointerGetDatum(&newd_size)); - - /* - * If newd_size == 0 we have degenerate rectangles, so we don't know if - * there was any change, so we have to assume there was. - */ - if ((newd_size == 0) || (newd_size != old_size)) - { - TupleDesc td = RelationGetDescr(r); - - if (td->attrs[0]->attlen < 0) - { - /* - * This is an internal page, so 'oldud' had better be a union - * (constant-length) key, too. (See comment below.) - */ - Assert(VARSIZE(DatumGetPointer(datum)) == - VARSIZE(DatumGetPointer(oldud))); - memmove(DatumGetPointer(oldud), DatumGetPointer(datum), - VARSIZE(DatumGetPointer(datum))); - } - else - { - memmove(DatumGetPointer(oldud), DatumGetPointer(datum), - att_size); - } - WriteBuffer(b); - - /* - * The user may be defining an index on variable-sized data (like - * polygons). If so, we need to get a constant-sized datum for - * insertion on the internal page. We do this by calling the union - * proc, which is required to return a rectangle. - */ - tdatum = FunctionCall2(&rtstate->unionFn, datum, datum); - - rttighten(r, stk->rts_parent, tdatum, att_size, rtstate); - pfree(DatumGetPointer(tdatum)); - } - else - ReleaseBuffer(b); - pfree(DatumGetPointer(datum)); -} - -/* - * rtdosplit -- split a page in the tree. - * - * rtpicksplit does the interesting work of choosing the split. - * This routine just does the bit-pushing. - */ -static void -rtdosplit(Relation r, - Buffer buffer, - RTSTACK *stack, - IndexTuple itup, - RTSTATE *rtstate) -{ - Page p; - Buffer leftbuf, - rightbuf; - Page left, - right; - ItemId itemid; - IndexTuple item; - IndexTuple ltup, - rtup; - OffsetNumber maxoff; - OffsetNumber i; - OffsetNumber leftoff, - rightoff; - BlockNumber lbknum, - rbknum; - BlockNumber bufblock; - RTreePageOpaque opaque; - bool *isnull; - SPLITVEC v; - OffsetNumber *spl_left, - *spl_right; - TupleDesc tupDesc; - int n; - OffsetNumber newitemoff; - - p = (Page) BufferGetPage(buffer); - opaque = (RTreePageOpaque) PageGetSpecialPointer(p); - - rtpicksplit(r, p, &v, itup, rtstate); - - /* - * The root of the tree is the first block in the relation. If we're - * about to split the root, we need to do some hocus-pocus to enforce this - * guarantee. - */ - - if (BufferGetBlockNumber(buffer) == P_ROOT) - { - leftbuf = ReadBuffer(r, P_NEW); - RTInitBuffer(leftbuf, opaque->flags); - lbknum = BufferGetBlockNumber(leftbuf); - left = (Page) BufferGetPage(leftbuf); - } - else - { - leftbuf = buffer; - IncrBufferRefCount(buffer); - lbknum = BufferGetBlockNumber(buffer); - left = (Page) PageGetTempPage(p, sizeof(RTreePageOpaqueData)); - } - - rightbuf = ReadBuffer(r, P_NEW); - RTInitBuffer(rightbuf, opaque->flags); - rbknum = BufferGetBlockNumber(rightbuf); - right = (Page) BufferGetPage(rightbuf); - - spl_left = v.spl_left; - spl_right = v.spl_right; - leftoff = rightoff = FirstOffsetNumber; - maxoff = PageGetMaxOffsetNumber(p); - newitemoff = OffsetNumberNext(maxoff); - - /* - * spl_left contains a list of the offset numbers of the tuples that will - * go to the left page. For each offset number, get the tuple item, then - * add the item to the left page. Similarly for the right side. - */ - - /* fill left node */ - for (n = 0; n < v.spl_nleft; n++) - { - i = *spl_left; - if (i == newitemoff) - item = itup; - else - { - itemid = PageGetItemId(p, i); - item = (IndexTuple) PageGetItem(p, itemid); - } - - if (PageAddItem(left, (Item) item, IndexTupleSize(item), - leftoff, LP_USED) == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - leftoff = OffsetNumberNext(leftoff); - - spl_left++; /* advance in left split vector */ - } - - /* fill right node */ - for (n = 0; n < v.spl_nright; n++) - { - i = *spl_right; - if (i == newitemoff) - item = itup; - else - { - itemid = PageGetItemId(p, i); - item = (IndexTuple) PageGetItem(p, itemid); - } - - if (PageAddItem(right, (Item) item, IndexTupleSize(item), - rightoff, LP_USED) == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - rightoff = OffsetNumberNext(rightoff); - - spl_right++; /* advance in right split vector */ - } - - /* Make sure we consumed all of the split vectors, and release 'em */ - Assert(*spl_left == InvalidOffsetNumber); - Assert(*spl_right == InvalidOffsetNumber); - pfree(v.spl_left); - pfree(v.spl_right); - - if ((bufblock = BufferGetBlockNumber(buffer)) != P_ROOT) - PageRestoreTempPage(left, p); - WriteBuffer(leftbuf); - WriteBuffer(rightbuf); - - /* - * Okay, the page is split. We have three things left to do: - * - * 1) Adjust any active scans on this index to cope with changes we - * introduced in its structure by splitting this page. - * - * 2) "Tighten" the bounding box of the pointer to the left page in the - * parent node in the tree, if any. Since we moved a bunch of stuff off - * the left page, we expect it to get smaller. This happens in the - * internal insertion routine. - * - * 3) Insert a pointer to the right page in the parent. This may cause the - * parent to split. If it does, we need to repeat steps one and two for - * each split node in the tree. - */ - - /* adjust active scans */ - rtadjscans(r, RTOP_SPLIT, bufblock, FirstOffsetNumber); - - tupDesc = r->rd_att; - isnull = (bool *) palloc(r->rd_rel->relnatts * sizeof(bool)); - memset(isnull, false, r->rd_rel->relnatts * sizeof(bool)); - - ltup = index_form_tuple(tupDesc, &(v.spl_ldatum), isnull); - rtup = index_form_tuple(tupDesc, &(v.spl_rdatum), isnull); - - pfree(isnull); - pfree(DatumGetPointer(v.spl_ldatum)); - pfree(DatumGetPointer(v.spl_rdatum)); - - /* set pointers to new child pages in the internal index tuples */ - ItemPointerSet(&(ltup->t_tid), lbknum, 1); - ItemPointerSet(&(rtup->t_tid), rbknum, 1); - - rtintinsert(r, stack, ltup, rtup, rtstate); - - pfree(ltup); - pfree(rtup); -} - -static void -rtintinsert(Relation r, - RTSTACK *stk, - IndexTuple ltup, - IndexTuple rtup, - RTSTATE *rtstate) -{ - IndexTuple old; - Buffer b; - Page p; - Datum ldatum, - rdatum, - newdatum; - - if (stk == NULL) - { - rtnewroot(r, ltup, rtup); - return; - } - - b = ReadBuffer(r, stk->rts_blk); - p = BufferGetPage(b); - old = (IndexTuple) PageGetItem(p, PageGetItemId(p, stk->rts_child)); - - /* - * This is a hack. Right now, we force rtree internal keys to be constant - * size. To fix this, need delete the old key and add both left and right - * for the two new pages. The insertion of left may force a split if the - * new left key is bigger than the old key. - */ - - if (IndexTupleSize(old) != IndexTupleSize(ltup)) - ereport(ERROR, - (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), - errmsg("variable-length rtree keys are not supported"))); - - /* install pointer to left child */ - memmove(old, ltup, IndexTupleSize(ltup)); - - if (nospace(p, rtup)) - { - newdatum = IndexTupleGetDatum(ltup); - rttighten(r, stk->rts_parent, newdatum, - IndexTupleAttSize(ltup), rtstate); - rtdosplit(r, b, stk->rts_parent, rtup, rtstate); - WriteBuffer(b); /* don't forget to release buffer! - 01/31/94 */ - } - else - { - if (PageAddItem(p, (Item) rtup, IndexTupleSize(rtup), - PageGetMaxOffsetNumber(p), - LP_USED) == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - WriteBuffer(b); - ldatum = IndexTupleGetDatum(ltup); - rdatum = IndexTupleGetDatum(rtup); - newdatum = FunctionCall2(&rtstate->unionFn, ldatum, rdatum); - - rttighten(r, stk->rts_parent, newdatum, - IndexTupleAttSize(rtup), rtstate); - - pfree(DatumGetPointer(newdatum)); - } -} - -static void -rtnewroot(Relation r, IndexTuple lt, IndexTuple rt) -{ - Buffer b; - Page p; - - b = ReadBuffer(r, P_ROOT); - RTInitBuffer(b, 0); - p = BufferGetPage(b); - if (PageAddItem(p, (Item) lt, IndexTupleSize(lt), - FirstOffsetNumber, - LP_USED) == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - if (PageAddItem(p, (Item) rt, IndexTupleSize(rt), - OffsetNumberNext(FirstOffsetNumber), - LP_USED) == InvalidOffsetNumber) - elog(ERROR, "failed to add index item to \"%s\"", - RelationGetRelationName(r)); - WriteBuffer(b); -} - -/* - * Choose how to split an rtree page into two pages. - * - * We return two vectors of index item numbers, one for the items to be - * put on the left page, one for the items to be put on the right page. - * In addition, the item to be added (itup) is listed in the appropriate - * vector. It is represented by item number N+1 (N = # of items on page). - * - * Both vectors have a terminating sentinel value of InvalidOffsetNumber, - * but the sentinal value is no longer used, because the SPLITVEC - * vector also contains the length of each vector, and that information - * is now used to iterate over them in rtdosplit(). --kbb, 21 Sept 2001 - * - * The bounding-box datums for the two new pages are also returned in *v. - * - * This is the quadratic-cost split algorithm Guttman describes in - * his paper. The reason we chose it is that you can implement this - * with less information about the data types on which you're operating. - * - * We must also deal with a consideration not found in Guttman's algorithm: - * variable-length data. In particular, the incoming item might be - * large enough that not just any split will work. In the worst case, - * our "split" may have to be the new item on one page and all the existing - * items on the other. Short of that, we have to take care that we do not - * make a split that leaves both pages too full for the new item. - */ -static void -rtpicksplit(Relation r, - Page page, - SPLITVEC *v, - IndexTuple itup, - RTSTATE *rtstate) -{ - OffsetNumber maxoff, - newitemoff; - OffsetNumber i, - j; - IndexTuple item_1, - item_2; - Datum datum_alpha, - datum_beta; - Datum datum_l, - datum_r; - Datum union_d, - union_dl, - union_dr; - Datum inter_d; - bool firsttime; - float size_alpha, - size_beta, - size_union, - size_inter; - float size_waste, - waste; - float size_l, - size_r; - int nbytes; - OffsetNumber seed_1 = 0, - seed_2 = 0; - OffsetNumber *left, - *right; - Size newitemsz, - item_1_sz, - item_2_sz, - left_avail_space, - right_avail_space; - int total_num_tuples, - num_tuples_without_seeds, - max_after_split; /* in Guttman's lingo, (M - m) */ - float diff; /* diff between cost of putting tuple left or - * right */ - SPLITCOST *cost_vector; - int n; - - /* - * First, make sure the new item is not so large that we can't possibly - * fit it on a page, even by itself. (It's sufficient to make this test - * here, since any oversize tuple must lead to a page split attempt.) - */ - newitemsz = IndexTupleTotalSize(itup); - if (newitemsz > RTPageAvailSpace) - ereport(ERROR, - (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), - errmsg("index row size %lu exceeds rtree maximum, %lu", - (unsigned long) newitemsz, - (unsigned long) RTPageAvailSpace), - errhint("Values larger than a buffer page cannot be indexed."))); - - maxoff = PageGetMaxOffsetNumber(page); - newitemoff = OffsetNumberNext(maxoff); /* phony index for new item */ - total_num_tuples = newitemoff; - num_tuples_without_seeds = total_num_tuples - 2; - max_after_split = total_num_tuples / 2; /* works for m = M/2 */ - - /* Make arrays big enough for worst case, including sentinel */ - nbytes = (maxoff + 2) * sizeof(OffsetNumber); - v->spl_left = (OffsetNumber *) palloc(nbytes); - v->spl_right = (OffsetNumber *) palloc(nbytes); - - firsttime = true; - waste = 0.0; - - for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i)) - { - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); - datum_alpha = IndexTupleGetDatum(item_1); - item_1_sz = IndexTupleTotalSize(item_1); - - for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j)) - { - item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, j)); - datum_beta = IndexTupleGetDatum(item_2); - item_2_sz = IndexTupleTotalSize(item_2); - - /* - * Ignore seed pairs that don't leave room for the new item on - * either split page. - */ - if (newitemsz + item_1_sz > RTPageAvailSpace && - newitemsz + item_2_sz > RTPageAvailSpace) - continue; - - /* compute the wasted space by unioning these guys */ - union_d = FunctionCall2(&rtstate->unionFn, - datum_alpha, datum_beta); - FunctionCall2(&rtstate->sizeFn, union_d, - PointerGetDatum(&size_union)); - inter_d = FunctionCall2(&rtstate->interFn, - datum_alpha, datum_beta); - - /* - * The interFn may return a NULL pointer (not an SQL null!) to - * indicate no intersection. sizeFn must cope with this. - */ - FunctionCall2(&rtstate->sizeFn, inter_d, - PointerGetDatum(&size_inter)); - size_waste = size_union - size_inter; - - if (DatumGetPointer(union_d) != NULL) - pfree(DatumGetPointer(union_d)); - if (DatumGetPointer(inter_d) != NULL) - pfree(DatumGetPointer(inter_d)); - - /* - * are these a more promising split that what we've already seen? - */ - if (size_waste > waste || firsttime) - { - waste = size_waste; - seed_1 = i; - seed_2 = j; - firsttime = false; - } - } - } - - if (firsttime) - { - /* - * There is no possible split except to put the new item on its own - * page. Since we still have to compute the union rectangles, we play - * dumb and run through the split algorithm anyway, setting seed_1 = - * first item on page and seed_2 = new item. - */ - seed_1 = FirstOffsetNumber; - seed_2 = newitemoff; - } - - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_1)); - datum_alpha = IndexTupleGetDatum(item_1); - datum_l = FunctionCall2(&rtstate->unionFn, datum_alpha, datum_alpha); - FunctionCall2(&rtstate->sizeFn, datum_l, PointerGetDatum(&size_l)); - left_avail_space = RTPageAvailSpace - IndexTupleTotalSize(item_1); - - if (seed_2 == newitemoff) - { - item_2 = itup; - /* Needn't leave room for new item in calculations below */ - newitemsz = 0; - } - else - item_2 = (IndexTuple) PageGetItem(page, PageGetItemId(page, seed_2)); - datum_beta = IndexTupleGetDatum(item_2); - datum_r = FunctionCall2(&rtstate->unionFn, datum_beta, datum_beta); - FunctionCall2(&rtstate->sizeFn, datum_r, PointerGetDatum(&size_r)); - right_avail_space = RTPageAvailSpace - IndexTupleTotalSize(item_2); - - /* - * Now split up the regions between the two seeds. - * - * The cost_vector array will contain hints for determining where each tuple - * should go. Each record in the array will contain a boolean, - * choose_left, that indicates which node the tuple prefers to be on, and - * the absolute difference in cost between putting the tuple in its - * favored node and in the other node. - * - * Later, we will sort the cost_vector in descending order by cost - * difference, and consider the tuples in that order for placement. That - * way, the tuples that *really* want to be in one node or the other get - * to choose first, and the tuples that don't really care choose last. - * - * First, build the cost_vector array. The new index tuple will also be - * handled in this loop, and represented in the array, with i==newitemoff. - * - * In the case of variable size tuples it is possible that we only have the - * two seeds and no other tuples, in which case we don't do any of this - * cost_vector stuff. - */ - - /* to keep compiler quiet */ - cost_vector = NULL; - - if (num_tuples_without_seeds > 0) - { - cost_vector = - (SPLITCOST *) palloc(num_tuples_without_seeds * sizeof(SPLITCOST)); - n = 0; - for (i = FirstOffsetNumber; i <= newitemoff; i = OffsetNumberNext(i)) - { - /* Compute new union datums and sizes for both choices */ - - if ((i == seed_1) || (i == seed_2)) - continue; - else if (i == newitemoff) - item_1 = itup; - else - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); - - datum_alpha = IndexTupleGetDatum(item_1); - union_dl = FunctionCall2(&rtstate->unionFn, datum_l, datum_alpha); - union_dr = FunctionCall2(&rtstate->unionFn, datum_r, datum_alpha); - FunctionCall2(&rtstate->sizeFn, union_dl, - PointerGetDatum(&size_alpha)); - FunctionCall2(&rtstate->sizeFn, union_dr, - PointerGetDatum(&size_beta)); - pfree(DatumGetPointer(union_dl)); - pfree(DatumGetPointer(union_dr)); - - diff = (size_alpha - size_l) - (size_beta - size_r); - - cost_vector[n].offset_number = i; - cost_vector[n].cost_differential = fabs(diff); - cost_vector[n].choose_left = (diff < 0); - - n++; - } - - /* - * Sort the array. The function qsort_comp_splitcost is set up - * "backwards", to provided descending order. - */ - qsort(cost_vector, num_tuples_without_seeds, sizeof(SPLITCOST), - &qsort_comp_splitcost); - } - - /* - * Now make the final decisions about where each tuple will go, and build - * the vectors to return in the SPLITVEC record. - * - * The cost_vector array contains (descriptions of) all the tuples, in the - * order that we want to consider them, so we we just iterate through it - * and place each tuple in left or right nodes, according to the criteria - * described below. - */ - - left = v->spl_left; - v->spl_nleft = 0; - right = v->spl_right; - v->spl_nright = 0; - - /* - * Place the seeds first. left avail space, left union, right avail space, - * and right union have already been adjusted for the seeds. - */ - - *left++ = seed_1; - v->spl_nleft++; - - *right++ = seed_2; - v->spl_nright++; - - for (n = 0; n < num_tuples_without_seeds; n++) - { - bool left_feasible, - right_feasible, - choose_left; - - /* - * We need to figure out which page needs the least enlargement in - * order to store the item. - */ - - i = cost_vector[n].offset_number; - - /* Compute new union datums and sizes for both possible additions */ - if (i == newitemoff) - { - item_1 = itup; - /* Needn't leave room for new item anymore */ - newitemsz = 0; - } - else - item_1 = (IndexTuple) PageGetItem(page, PageGetItemId(page, i)); - item_1_sz = IndexTupleTotalSize(item_1); - - datum_alpha = IndexTupleGetDatum(item_1); - union_dl = FunctionCall2(&rtstate->unionFn, datum_l, datum_alpha); - union_dr = FunctionCall2(&rtstate->unionFn, datum_r, datum_alpha); - FunctionCall2(&rtstate->sizeFn, union_dl, - PointerGetDatum(&size_alpha)); - FunctionCall2(&rtstate->sizeFn, union_dr, - PointerGetDatum(&size_beta)); - - /* - * We prefer the page that shows smaller enlargement of its union area - * (Guttman's algorithm), but we must take care that at least one page - * will still have room for the new item after this one is added. - * - * (We know that all the old items together can fit on one page, so we - * need not worry about any other problem than failing to fit the new - * item.) - * - * Guttman's algorithm actually has two factors to consider (in order): - * 1. if one node has so many tuples already assigned to it that the - * other needs all the rest in order to satisfy the condition that - * neither node has fewer than m tuples, then that is decisive; 2. - * otherwise, choose the page that shows the smaller enlargement of - * its union area. - * - * I have chosen m = M/2, where M is the maximum number of tuples on a - * page. (Actually, this is only strictly true for fixed size tuples. - * For variable size tuples, there still might have to be only one - * tuple on a page, if it is really big. But even with variable size - * tuples we still try to get m as close as possible to M/2.) - * - * The question of which page shows the smaller enlargement of its union - * area has already been answered, and the answer stored in the - * choose_left field of the SPLITCOST record. - */ - left_feasible = (left_avail_space >= item_1_sz && - ((left_avail_space - item_1_sz) >= newitemsz || - right_avail_space >= newitemsz)); - right_feasible = (right_avail_space >= item_1_sz && - ((right_avail_space - item_1_sz) >= newitemsz || - left_avail_space >= newitemsz)); - if (left_feasible && right_feasible) - { - /* - * Both feasible, use Guttman's algorithm. First check the m - * condition described above, and if that doesn't apply, choose - * the page with the smaller enlargement of its union area. - */ - if (v->spl_nleft > max_after_split) - choose_left = false; - else if (v->spl_nright > max_after_split) - choose_left = true; - else - choose_left = cost_vector[n].choose_left; - } - else if (left_feasible) - choose_left = true; - else if (right_feasible) - choose_left = false; - else - { - elog(ERROR, "failed to find a workable rtree page split"); - choose_left = false; /* keep compiler quiet */ - } - - if (choose_left) - { - pfree(DatumGetPointer(datum_l)); - pfree(DatumGetPointer(union_dr)); - datum_l = union_dl; - size_l = size_alpha; - left_avail_space -= item_1_sz; - *left++ = i; - v->spl_nleft++; - } - else - { - pfree(DatumGetPointer(datum_r)); - pfree(DatumGetPointer(union_dl)); - datum_r = union_dr; - size_r = size_beta; - right_avail_space -= item_1_sz; - *right++ = i; - v->spl_nright++; - } - } - - if (num_tuples_without_seeds > 0) - pfree(cost_vector); - - *left = *right = InvalidOffsetNumber; /* add ending sentinels */ - - v->spl_ldatum = datum_l; - v->spl_rdatum = datum_r; -} - -static void -RTInitBuffer(Buffer b, uint32 f) -{ - RTreePageOpaque opaque; - Page page; - Size pageSize; - - pageSize = BufferGetPageSize(b); - - page = BufferGetPage(b); - - PageInit(page, pageSize, sizeof(RTreePageOpaqueData)); - - opaque = (RTreePageOpaque) PageGetSpecialPointer(page); - opaque->flags = f; -} - -static OffsetNumber -choose(Relation r, Page p, IndexTuple it, RTSTATE *rtstate) -{ - OffsetNumber maxoff; - OffsetNumber i; - Datum ud, - id; - Datum datum; - float usize, - dsize; - OffsetNumber which; - float which_grow; - - id = IndexTupleGetDatum(it); - maxoff = PageGetMaxOffsetNumber(p); - which_grow = -1.0; - which = -1; - - for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i)) - { - datum = IndexTupleGetDatum(PageGetItem(p, PageGetItemId(p, i))); - FunctionCall2(&rtstate->sizeFn, datum, - PointerGetDatum(&dsize)); - ud = FunctionCall2(&rtstate->unionFn, datum, id); - FunctionCall2(&rtstate->sizeFn, ud, - PointerGetDatum(&usize)); - pfree(DatumGetPointer(ud)); - if (which_grow < 0 || usize - dsize < which_grow) - { - which = i; - which_grow = usize - dsize; - if (which_grow == 0) - break; - } - } - - return which; -} - -static int -nospace(Page p, IndexTuple it) -{ - return PageGetFreeSpace(p) < IndexTupleSize(it); -} - -void -freestack(RTSTACK *s) -{ - RTSTACK *p; - - while (s != NULL) - { - p = s->rts_parent; - pfree(s); - s = p; - } -} - -/* - * Bulk deletion of all index entries pointing to a set of heap tuples. - * The set of target tuples is specified via a callback routine that tells - * whether any given heap tuple (identified by ItemPointer) is being deleted. - * - * Result: a palloc'd struct containing statistical info for VACUUM displays. - */ -Datum -rtbulkdelete(PG_FUNCTION_ARGS) -{ - Relation rel = (Relation) PG_GETARG_POINTER(0); - IndexBulkDeleteCallback callback = (IndexBulkDeleteCallback) PG_GETARG_POINTER(1); - void *callback_state = (void *) PG_GETARG_POINTER(2); - IndexBulkDeleteResult *result; - BlockNumber num_pages; - double tuples_removed; - double num_index_tuples; - IndexScanDesc iscan; - - tuples_removed = 0; - num_index_tuples = 0; - - /* - * Since rtree is not marked "amconcurrent" in pg_am, caller should have - * acquired exclusive lock on index relation. We need no locking here. - */ - - /* - * XXX generic implementation --- should be improved! - */ - - /* walk through the entire index */ - iscan = index_beginscan(NULL, rel, SnapshotAny, 0, NULL); - /* including killed tuples */ - iscan->ignore_killed_tuples = false; - - while (index_getnext_indexitem(iscan, ForwardScanDirection)) - { - vacuum_delay_point(); - - if (callback(&iscan->xs_ctup.t_self, callback_state)) - { - ItemPointerData indextup = iscan->currentItemData; - BlockNumber blkno; - OffsetNumber offnum; - Buffer buf; - Page page; - - blkno = ItemPointerGetBlockNumber(&indextup); - offnum = ItemPointerGetOffsetNumber(&indextup); - - /* adjust any scans that will be affected by this deletion */ - /* (namely, my own scan) */ - rtadjscans(rel, RTOP_DEL, blkno, offnum); - - /* delete the index tuple */ - buf = ReadBuffer(rel, blkno); - page = BufferGetPage(buf); - - PageIndexTupleDelete(page, offnum); - - WriteBuffer(buf); - - tuples_removed += 1; - } - else - num_index_tuples += 1; - } - - index_endscan(iscan); - - /* return statistics */ - num_pages = RelationGetNumberOfBlocks(rel); - - result = (IndexBulkDeleteResult *) palloc0(sizeof(IndexBulkDeleteResult)); - result->num_pages = num_pages; - result->num_index_tuples = num_index_tuples; - result->tuples_removed = tuples_removed; - - PG_RETURN_POINTER(result); -} - - -static void -initRtstate(RTSTATE *rtstate, Relation index) -{ - fmgr_info_copy(&rtstate->unionFn, - index_getprocinfo(index, 1, RT_UNION_PROC), - CurrentMemoryContext); - fmgr_info_copy(&rtstate->sizeFn, - index_getprocinfo(index, 1, RT_SIZE_PROC), - CurrentMemoryContext); - fmgr_info_copy(&rtstate->interFn, - index_getprocinfo(index, 1, RT_INTER_PROC), - CurrentMemoryContext); -} - -/* for sorting SPLITCOST records in descending order */ -static int -qsort_comp_splitcost(const void *a, const void *b) -{ - float diff = - ((SPLITCOST *) a)->cost_differential - - ((SPLITCOST *) b)->cost_differential; - - if (diff < 0) - return 1; - else if (diff > 0) - return -1; - else - return 0; -} - -#ifdef RTDEBUG - -void -_rtdump(Relation r) -{ - Buffer buf; - Page page; - OffsetNumber offnum, - maxoff; - BlockNumber blkno; - BlockNumber nblocks; - RTreePageOpaque po; - IndexTuple itup; - BlockNumber itblkno; - OffsetNumber itoffno; - Datum datum; - char *itkey; - - nblocks = RelationGetNumberOfBlocks(r); - for (blkno = 0; blkno < nblocks; blkno++) - { - buf = ReadBuffer(r, blkno); - page = BufferGetPage(buf); - po = (RTreePageOpaque) PageGetSpecialPointer(page); - maxoff = PageGetMaxOffsetNumber(page); - printf("Page %d maxoff %d <%s>\n", blkno, maxoff, - (po->flags & F_LEAF ? "LEAF" : "INTERNAL")); - - if (PageIsEmpty(page)) - { - ReleaseBuffer(buf); - continue; - } - - for (offnum = FirstOffsetNumber; - offnum <= maxoff; - offnum = OffsetNumberNext(offnum)) - { - itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, offnum)); - itblkno = ItemPointerGetBlockNumber(&(itup->t_tid)); - itoffno = ItemPointerGetOffsetNumber(&(itup->t_tid)); - datum = IndexTupleGetDatum(itup); - itkey = DatumGetCString(DirectFunctionCall1(box_out, - datum)); - printf("\t[%d] size %d heap <%d,%d> key:%s\n", - offnum, IndexTupleSize(itup), itblkno, itoffno, itkey); - pfree(itkey); - } - - ReleaseBuffer(buf); - } -} -#endif /* defined RTDEBUG */ - -void -rtree_redo(XLogRecPtr lsn, XLogRecord *record) -{ - elog(PANIC, "rtree_redo: unimplemented"); -} - -void -rtree_desc(char *buf, uint8 xl_info, char *rec) -{ -} diff --git a/src/backend/access/rtree/rtscan.c b/src/backend/access/rtree/rtscan.c deleted file mode 100644 index 577c6a64369..00000000000 --- a/src/backend/access/rtree/rtscan.c +++ /dev/null @@ -1,493 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtscan.c - * routines to manage scans on index relations - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/rtree/rtscan.c,v 1.60 2005/10/15 02:49:09 momjian Exp $ - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "access/genam.h" -#include "access/rtree.h" -#include "utils/lsyscache.h" -#include "utils/resowner.h" - - -/* routines defined and used here */ -static void rtregscan(IndexScanDesc s); -static void rtdropscan(IndexScanDesc s); -static void rtadjone(IndexScanDesc s, int op, BlockNumber blkno, - OffsetNumber offnum); -static void adjuststack(RTSTACK *stk, BlockNumber blkno); -static void adjustiptr(IndexScanDesc s, ItemPointer iptr, - int op, BlockNumber blkno, OffsetNumber offnum); - -/* - * Whenever we start an rtree scan in a backend, we register it in private - * space. Then if the rtree index gets updated, we check all registered - * scans and adjust them if the tuple they point at got moved by the - * update. We only need to do this in private space, because when we update - * an rtree we have a write lock on the tree, so no other process can have - * any locks at all on it. A single transaction can have write and read - * locks on the same object, so that's why we need to handle this case. - */ - -typedef struct RTScanListData -{ - IndexScanDesc rtsl_scan; - ResourceOwner rtsl_owner; - struct RTScanListData *rtsl_next; -} RTScanListData; - -typedef RTScanListData *RTScanList; - -/* pointer to list of local scans on rtrees */ -static RTScanList RTScans = NULL; - -Datum -rtbeginscan(PG_FUNCTION_ARGS) -{ - Relation r = (Relation) PG_GETARG_POINTER(0); - int nkeys = PG_GETARG_INT32(1); - ScanKey key = (ScanKey) PG_GETARG_POINTER(2); - IndexScanDesc s; - - s = RelationGetIndexScan(r, nkeys, key); - - rtregscan(s); - - PG_RETURN_POINTER(s); -} - -Datum -rtrescan(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - ScanKey key = (ScanKey) PG_GETARG_POINTER(1); - RTreeScanOpaque p; - int i; - - /* - * Clear all the pointers. - */ - ItemPointerSetInvalid(&s->currentItemData); - ItemPointerSetInvalid(&s->currentMarkData); - - p = (RTreeScanOpaque) s->opaque; - if (p != NULL) - { - /* rescan an existing indexscan --- reset state */ - freestack(p->s_stack); - freestack(p->s_markstk); - p->s_stack = p->s_markstk = NULL; - p->s_flags = 0x0; - /* drop pins on buffers -- no locks held */ - if (BufferIsValid(p->curbuf)) - { - ReleaseBuffer(p->curbuf); - p->curbuf = InvalidBuffer; - } - if (BufferIsValid(p->markbuf)) - { - ReleaseBuffer(p->markbuf); - p->markbuf = InvalidBuffer; - } - } - else - { - /* initialize opaque data */ - p = (RTreeScanOpaque) palloc(sizeof(RTreeScanOpaqueData)); - p->s_stack = p->s_markstk = NULL; - p->curbuf = p->markbuf = InvalidBuffer; - p->s_internalNKey = s->numberOfKeys; - p->s_flags = 0x0; - s->opaque = p; - if (s->numberOfKeys > 0) - p->s_internalKey = (ScanKey) palloc(sizeof(ScanKeyData) * s->numberOfKeys); - } - - /* Update scan key, if a new one is given */ - if (key && s->numberOfKeys > 0) - { - memmove(s->keyData, - key, - s->numberOfKeys * sizeof(ScanKeyData)); - - /* - * Scans on internal pages use different operators than they do on - * leaf pages. For example, if the user wants all boxes that exactly - * match (x1,y1,x2,y2), then on internal pages we need to find all - * boxes that contain (x1,y1,x2,y2). rtstrat.c knows how to pick the - * opclass member to use for internal pages. In some cases we need to - * negate the result of the opclass member. - */ - for (i = 0; i < s->numberOfKeys; i++) - { - AttrNumber attno = s->keyData[i].sk_attno; - Oid opclass; - Oid subtype; - StrategyNumber orig_strategy; - StrategyNumber int_strategy; - Oid int_oper; - RegProcedure int_proc; - int int_flags; - - opclass = s->indexRelation->rd_indclass->values[attno - 1]; - subtype = s->keyData[i].sk_subtype; - orig_strategy = s->keyData[i].sk_strategy; - int_strategy = RTMapToInternalOperator(orig_strategy); - int_oper = get_opclass_member(opclass, subtype, int_strategy); - Assert(OidIsValid(int_oper)); - int_proc = get_opcode(int_oper); - int_flags = s->keyData[i].sk_flags; - if (RTMapToInternalNegate(orig_strategy)) - int_flags |= SK_NEGATE; - ScanKeyEntryInitialize(&(p->s_internalKey[i]), - int_flags, - attno, - int_strategy, - subtype, - int_proc, - s->keyData[i].sk_argument); - } - } - - PG_RETURN_VOID(); -} - -Datum -rtmarkpos(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - RTreeScanOpaque p; - RTSTACK *o, - *n, - *tmp; - - s->currentMarkData = s->currentItemData; - p = (RTreeScanOpaque) s->opaque; - if (p->s_flags & RTS_CURBEFORE) - p->s_flags |= RTS_MRKBEFORE; - else - p->s_flags &= ~RTS_MRKBEFORE; - - o = NULL; - n = p->s_stack; - - /* copy the parent stack from the current item data */ - while (n != NULL) - { - tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); - tmp->rts_child = n->rts_child; - tmp->rts_blk = n->rts_blk; - tmp->rts_parent = o; - o = tmp; - n = n->rts_parent; - } - - freestack(p->s_markstk); - p->s_markstk = o; - - /* Update markbuf: make sure to bump ref count on curbuf */ - if (BufferIsValid(p->markbuf)) - { - ReleaseBuffer(p->markbuf); - p->markbuf = InvalidBuffer; - } - if (BufferIsValid(p->curbuf)) - { - IncrBufferRefCount(p->curbuf); - p->markbuf = p->curbuf; - } - - PG_RETURN_VOID(); -} - -Datum -rtrestrpos(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - RTreeScanOpaque p; - RTSTACK *o, - *n, - *tmp; - - s->currentItemData = s->currentMarkData; - p = (RTreeScanOpaque) s->opaque; - if (p->s_flags & RTS_MRKBEFORE) - p->s_flags |= RTS_CURBEFORE; - else - p->s_flags &= ~RTS_CURBEFORE; - - o = NULL; - n = p->s_markstk; - - /* copy the parent stack from the current item data */ - while (n != NULL) - { - tmp = (RTSTACK *) palloc(sizeof(RTSTACK)); - tmp->rts_child = n->rts_child; - tmp->rts_blk = n->rts_blk; - tmp->rts_parent = o; - o = tmp; - n = n->rts_parent; - } - - freestack(p->s_stack); - p->s_stack = o; - - /* Update curbuf; be sure to bump ref count on markbuf */ - if (BufferIsValid(p->curbuf)) - { - ReleaseBuffer(p->curbuf); - p->curbuf = InvalidBuffer; - } - if (BufferIsValid(p->markbuf)) - { - IncrBufferRefCount(p->markbuf); - p->curbuf = p->markbuf; - } - - PG_RETURN_VOID(); -} - -Datum -rtendscan(PG_FUNCTION_ARGS) -{ - IndexScanDesc s = (IndexScanDesc) PG_GETARG_POINTER(0); - RTreeScanOpaque p; - - p = (RTreeScanOpaque) s->opaque; - - if (p != NULL) - { - freestack(p->s_stack); - freestack(p->s_markstk); - if (BufferIsValid(p->curbuf)) - ReleaseBuffer(p->curbuf); - if (BufferIsValid(p->markbuf)) - ReleaseBuffer(p->markbuf); - pfree(s->opaque); - } - - rtdropscan(s); - - PG_RETURN_VOID(); -} - -static void -rtregscan(IndexScanDesc s) -{ - RTScanList l; - - l = (RTScanList) palloc(sizeof(RTScanListData)); - l->rtsl_scan = s; - l->rtsl_owner = CurrentResourceOwner; - l->rtsl_next = RTScans; - RTScans = l; -} - -static void -rtdropscan(IndexScanDesc s) -{ - RTScanList l; - RTScanList prev; - - prev = NULL; - - for (l = RTScans; - l != NULL && l->rtsl_scan != s; - l = l->rtsl_next) - prev = l; - - if (l == NULL) - elog(ERROR, "rtree scan list corrupted -- could not find 0x%p", - (void *) s); - - if (prev == NULL) - RTScans = l->rtsl_next; - else - prev->rtsl_next = l->rtsl_next; - - pfree(l); -} - -/* - * ReleaseResources_rtree() --- clean up rtree subsystem resources. - * - * This is here because it needs to touch this module's static var RTScans. - */ -void -ReleaseResources_rtree(void) -{ - RTScanList l; - RTScanList prev; - RTScanList next; - - /* - * Note: this should be a no-op during normal query shutdown. However, in - * an abort situation ExecutorEnd is not called and so there may be open - * index scans to clean up. - */ - prev = NULL; - - for (l = RTScans; l != NULL; l = next) - { - next = l->rtsl_next; - if (l->rtsl_owner == CurrentResourceOwner) - { - if (prev == NULL) - RTScans = next; - else - prev->rtsl_next = next; - - pfree(l); - /* prev does not change */ - } - else - prev = l; - } -} - -void -rtadjscans(Relation r, int op, BlockNumber blkno, OffsetNumber offnum) -{ - RTScanList l; - Oid relid; - - relid = RelationGetRelid(r); - for (l = RTScans; l != NULL; l = l->rtsl_next) - { - if (RelationGetRelid(l->rtsl_scan->indexRelation) == relid) - rtadjone(l->rtsl_scan, op, blkno, offnum); - } -} - -/* - * rtadjone() -- adjust one scan for update. - * - * By here, the scan passed in is on a modified relation. Op tells - * us what the modification is, and blkno and offind tell us what - * block and offset index were affected. This routine checks the - * current and marked positions, and the current and marked stacks, - * to see if any stored location needs to be changed because of the - * update. If so, we make the change here. - */ -static void -rtadjone(IndexScanDesc s, - int op, - BlockNumber blkno, - OffsetNumber offnum) -{ - RTreeScanOpaque so; - - adjustiptr(s, &(s->currentItemData), op, blkno, offnum); - adjustiptr(s, &(s->currentMarkData), op, blkno, offnum); - - so = (RTreeScanOpaque) s->opaque; - - if (op == RTOP_SPLIT) - { - adjuststack(so->s_stack, blkno); - adjuststack(so->s_markstk, blkno); - } -} - -/* - * adjustiptr() -- adjust current and marked item pointers in the scan - * - * Depending on the type of update and the place it happened, we - * need to do nothing, to back up one record, or to start over on - * the same page. - */ -static void -adjustiptr(IndexScanDesc s, - ItemPointer iptr, - int op, - BlockNumber blkno, - OffsetNumber offnum) -{ - OffsetNumber curoff; - RTreeScanOpaque so; - - if (ItemPointerIsValid(iptr)) - { - if (ItemPointerGetBlockNumber(iptr) == blkno) - { - curoff = ItemPointerGetOffsetNumber(iptr); - so = (RTreeScanOpaque) s->opaque; - - switch (op) - { - case RTOP_DEL: - /* back up one if we need to */ - if (curoff >= offnum) - { - - if (curoff > FirstOffsetNumber) - { - /* just adjust the item pointer */ - ItemPointerSet(iptr, blkno, OffsetNumberPrev(curoff)); - } - else - { - /* - * remember that we're before the current tuple - */ - ItemPointerSet(iptr, blkno, FirstOffsetNumber); - if (iptr == &(s->currentItemData)) - so->s_flags |= RTS_CURBEFORE; - else - so->s_flags |= RTS_MRKBEFORE; - } - } - break; - - case RTOP_SPLIT: - /* back to start of page on split */ - ItemPointerSet(iptr, blkno, FirstOffsetNumber); - if (iptr == &(s->currentItemData)) - so->s_flags &= ~RTS_CURBEFORE; - else - so->s_flags &= ~RTS_MRKBEFORE; - break; - - default: - elog(ERROR, "unrecognized operation in rtree scan adjust: %d", op); - } - } - } -} - -/* - * adjuststack() -- adjust the supplied stack for a split on a page in - * the index we're scanning. - * - * If a page on our parent stack has split, we need to back up to the - * beginning of the page and rescan it. The reason for this is that - * the split algorithm for rtrees doesn't order tuples in any useful - * way on a single page. This means on that a split, we may wind up - * looking at some heap tuples more than once. This is handled in the - * access method update code for heaps; if we've modified the tuple we - * are looking at already in this transaction, we ignore the update - * request. - */ -static void -adjuststack(RTSTACK *stk, BlockNumber blkno) -{ - while (stk != NULL) - { - if (stk->rts_blk == blkno) - stk->rts_child = FirstOffsetNumber; - - stk = stk->rts_parent; - } -} diff --git a/src/backend/access/rtree/rtstrat.c b/src/backend/access/rtree/rtstrat.c deleted file mode 100644 index 1b72d980da6..00000000000 --- a/src/backend/access/rtree/rtstrat.c +++ /dev/null @@ -1,79 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtstrat.c - * strategy map data for rtrees. - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * - * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/access/rtree/rtstrat.c,v 1.27 2005/06/24 20:53:30 tgl Exp $ - * - *------------------------------------------------------------------------- - */ - -#include "postgres.h" - -#include "access/rtree.h" - - -/* - * Here's something peculiar to rtrees that doesn't apply to most other - * indexing structures: When we're searching a tree for a given value, we - * can't do the same sorts of comparisons on internal node entries as we - * do at leaves. The reason is that if we're looking for (say) all boxes - * that are the same as (0,0,10,10), then we need to find all leaf pages - * that overlap that region. So internally we search for overlap, and at - * the leaf we search for equality. - * - * This array maps leaf search operators to the internal search operators. - */ -static const StrategyNumber RTOperMap[RTNStrategies] = { - RTOverRightStrategyNumber, /* left */ - RTRightStrategyNumber, /* overleft */ - RTOverlapStrategyNumber, /* overlap */ - RTLeftStrategyNumber, /* overright */ - RTOverLeftStrategyNumber, /* right */ - RTContainsStrategyNumber, /* same */ - RTContainsStrategyNumber, /* contains */ - RTOverlapStrategyNumber, /* contained-by */ - RTAboveStrategyNumber, /* overbelow */ - RTOverAboveStrategyNumber, /* below */ - RTOverBelowStrategyNumber, /* above */ - RTBelowStrategyNumber /* overabove */ -}; - -/* - * We may need to negate the result of the selected operator. (This could - * be avoided by expanding the set of operators required for an opclass.) - */ -static const bool RTNegateMap[RTNStrategies] = { - true, /* left */ - true, /* overleft */ - false, /* overlap */ - true, /* overright */ - true, /* right */ - false, /* same */ - false, /* contains */ - false, /* contained-by */ - true, /* overbelow */ - true, /* below */ - true, /* above */ - true /* overabove */ -}; - - -StrategyNumber -RTMapToInternalOperator(StrategyNumber strat) -{ - Assert(strat > 0 && strat <= RTNStrategies); - return RTOperMap[strat - 1]; -} - -bool -RTMapToInternalNegate(StrategyNumber strat) -{ - Assert(strat > 0 && strat <= RTNStrategies); - return RTNegateMap[strat - 1]; -} diff --git a/src/backend/access/transam/rmgr.c b/src/backend/access/transam/rmgr.c index 3b8bcb131d0..f7b48df1263 100644 --- a/src/backend/access/transam/rmgr.c +++ b/src/backend/access/transam/rmgr.c @@ -3,7 +3,7 @@ * * Resource managers definition * - * $PostgreSQL: pgsql/src/backend/access/transam/rmgr.c,v 1.20 2005/06/14 11:45:14 teodor Exp $ + * $PostgreSQL: pgsql/src/backend/access/transam/rmgr.c,v 1.21 2005/11/07 17:36:45 tgl Exp $ */ #include "postgres.h" @@ -13,7 +13,6 @@ #include "access/heapam.h" #include "access/multixact.h" #include "access/nbtree.h" -#include "access/rtree.h" #include "access/xact.h" #include "access/xlog_internal.h" #include "commands/dbcommands.h" @@ -36,7 +35,7 @@ const RmgrData RmgrTable[RM_MAX_ID + 1] = { {"Heap", heap_redo, heap_desc, NULL, NULL}, {"Btree", btree_redo, btree_desc, btree_xlog_startup, btree_xlog_cleanup}, {"Hash", hash_redo, hash_desc, NULL, NULL}, - {"Rtree", rtree_redo, rtree_desc, NULL, NULL}, + {"Reserved 13", NULL, NULL, NULL, NULL}, {"Gist", gist_redo, gist_desc, gist_xlog_startup, gist_xlog_cleanup}, {"Sequence", seq_redo, seq_desc, NULL, NULL} }; diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c index 07654e455ab..0a19168179f 100644 --- a/src/backend/commands/indexcmds.c +++ b/src/backend/commands/indexcmds.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/commands/indexcmds.c,v 1.134 2005/10/15 02:49:15 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/commands/indexcmds.c,v 1.135 2005/11/07 17:36:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -226,10 +226,27 @@ DefineIndex(RangeVar *heapRelation, PointerGetDatum(accessMethodName), 0, 0, 0); if (!HeapTupleIsValid(tuple)) - ereport(ERROR, - (errcode(ERRCODE_UNDEFINED_OBJECT), - errmsg("access method \"%s\" does not exist", - accessMethodName))); + { + /* + * Hack to provide more-or-less-transparent updating of old RTREE + * indexes to GIST: if RTREE is requested and not found, use GIST. + */ + if (strcmp(accessMethodName, "rtree") == 0) + { + ereport(NOTICE, + (errmsg("substituting access method \"gist\" for obsolete method \"rtree\""))); + accessMethodName = "gist"; + tuple = SearchSysCache(AMNAME, + PointerGetDatum(accessMethodName), + 0, 0, 0); + } + + if (!HeapTupleIsValid(tuple)) + ereport(ERROR, + (errcode(ERRCODE_UNDEFINED_OBJECT), + errmsg("access method \"%s\" does not exist", + accessMethodName))); + } accessMethodId = HeapTupleGetOid(tuple); accessMethodForm = (Form_pg_am) GETSTRUCT(tuple); diff --git a/src/backend/utils/adt/geo_selfuncs.c b/src/backend/utils/adt/geo_selfuncs.c index dddfaa3dbc4..9aa33831379 100644 --- a/src/backend/utils/adt/geo_selfuncs.c +++ b/src/backend/utils/adt/geo_selfuncs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/geo_selfuncs.c,v 1.24 2004/12/31 22:01:22 pgsql Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/geo_selfuncs.c,v 1.25 2005/11/07 17:36:45 tgl Exp $ * * XXX These are totally bogus. Perhaps someone will make them do * something reasonable, someday. @@ -22,19 +22,19 @@ /* - * Selectivity functions for rtrees. These are bogus -- unless we know - * the actual key distribution in the index, we can't make a good prediction - * of the selectivity of these operators. + * Selectivity functions for geometric operators. These are bogus -- unless + * we know the actual key distribution in the index, we can't make a good + * prediction of the selectivity of these operators. * * Note: the values used here may look unreasonably small. Perhaps they * are. For now, we want to make sure that the optimizer will make use - * of an r-tree index if one is available, so the selectivity had better + * of a geometric index if one is available, so the selectivity had better * be fairly small. * - * In general, rtrees need to search multiple subtrees in order to guarantee + * In general, GiST needs to search multiple subtrees in order to guarantee * that all occurrences of the same key have been found. Because of this, * the estimated cost for scanning the index ought to be higher than the - * output selectivity would indicate. rtcostestimate(), over in selfuncs.c, + * output selectivity would indicate. gistcostestimate(), over in selfuncs.c, * ought to be adjusted accordingly --- but until we can generate somewhat * realistic numbers here, it hardly matters... */ diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 95980ca1e03..85c22ca6c45 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -15,7 +15,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.191 2005/10/15 02:49:29 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/selfuncs.c,v 1.192 2005/11/07 17:36:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -4471,24 +4471,6 @@ btcostestimate(PG_FUNCTION_ARGS) } Datum -rtcostestimate(PG_FUNCTION_ARGS) -{ - PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0); - IndexOptInfo *index = (IndexOptInfo *) PG_GETARG_POINTER(1); - List *indexQuals = (List *) PG_GETARG_POINTER(2); - Cost *indexStartupCost = (Cost *) PG_GETARG_POINTER(3); - Cost *indexTotalCost = (Cost *) PG_GETARG_POINTER(4); - Selectivity *indexSelectivity = (Selectivity *) PG_GETARG_POINTER(5); - double *indexCorrelation = (double *) PG_GETARG_POINTER(6); - - genericcostestimate(root, index, indexQuals, 0.0, - indexStartupCost, indexTotalCost, - indexSelectivity, indexCorrelation); - - PG_RETURN_VOID(); -} - -Datum hashcostestimate(PG_FUNCTION_ARGS) { PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0); diff --git a/src/backend/utils/resowner/resowner.c b/src/backend/utils/resowner/resowner.c index 97933de820b..dfdb9958f91 100644 --- a/src/backend/utils/resowner/resowner.c +++ b/src/backend/utils/resowner/resowner.c @@ -14,7 +14,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/resowner/resowner.c,v 1.14 2005/10/15 02:49:36 momjian Exp $ + * $PostgreSQL: pgsql/src/backend/utils/resowner/resowner.c,v 1.15 2005/11/07 17:36:45 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -23,7 +23,6 @@ #include "utils/resowner.h" #include "access/gistscan.h" #include "access/hash.h" -#include "access/rtree.h" #include "storage/bufmgr.h" #include "storage/proc.h" #include "utils/memutils.h" @@ -280,7 +279,6 @@ ResourceOwnerReleaseInternal(ResourceOwner owner, /* Clean up index scans too */ ReleaseResources_gist(); ReleaseResources_hash(); - ReleaseResources_rtree(); } /* Let add-on modules get a chance too */ diff --git a/src/bin/psql/tab-complete.c b/src/bin/psql/tab-complete.c index 27d7469b935..d96a375f5df 100644 --- a/src/bin/psql/tab-complete.c +++ b/src/bin/psql/tab-complete.c @@ -3,7 +3,7 @@ * * Copyright (c) 2000-2005, PostgreSQL Global Development Group * - * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.138 2005/10/15 02:49:40 momjian Exp $ + * $PostgreSQL: pgsql/src/bin/psql/tab-complete.c,v 1.139 2005/11/07 17:36:45 tgl Exp $ */ /*---------------------------------------------------------------------- @@ -1025,7 +1025,7 @@ psql_completion(char *text, int start, int end) else if (pg_strcasecmp(prev_wd, "USING") == 0) { static const char *const index_mth[] = - {"BTREE", "RTREE", "HASH", "GIST", NULL}; + {"BTREE", "HASH", "GIST", NULL}; COMPLETE_WITH_LIST(index_mth); } diff --git a/src/include/access/gist.h b/src/include/access/gist.h index 22c897959f2..b48c492f7f8 100644 --- a/src/include/access/gist.h +++ b/src/include/access/gist.h @@ -9,18 +9,18 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/access/gist.h,v 1.50 2005/10/15 02:49:42 momjian Exp $ + * $PostgreSQL: pgsql/src/include/access/gist.h,v 1.51 2005/11/07 17:36:46 tgl Exp $ * *------------------------------------------------------------------------- */ #ifndef GIST_H #define GIST_H +#include "access/xlog.h" +#include "access/xlogdefs.h" #include "storage/bufpage.h" #include "storage/off.h" #include "utils/rel.h" -#include "access/xlog.h" -#include "access/xlogdefs.h" /* * amproc indexes for GiST indexes. @@ -35,6 +35,23 @@ #define GISTNProcs 7 /* + * strategy numbers for GiST opclasses that want to implement the old + * RTREE behavior. + */ +#define RTLeftStrategyNumber 1 +#define RTOverLeftStrategyNumber 2 +#define RTOverlapStrategyNumber 3 +#define RTOverRightStrategyNumber 4 +#define RTRightStrategyNumber 5 +#define RTSameStrategyNumber 6 +#define RTContainsStrategyNumber 7 +#define RTContainedByStrategyNumber 8 +#define RTOverBelowStrategyNumber 9 +#define RTBelowStrategyNumber 10 +#define RTAboveStrategyNumber 11 +#define RTOverAboveStrategyNumber 12 + +/* * Page opaque data in a GiST index page. */ #define F_LEAF (1 << 0) diff --git a/src/include/access/rmgr.h b/src/include/access/rmgr.h index 17ef0d7866d..da6bc696835 100644 --- a/src/include/access/rmgr.h +++ b/src/include/access/rmgr.h @@ -3,7 +3,7 @@ * * Resource managers definition * - * $PostgreSQL: pgsql/src/include/access/rmgr.h,v 1.14 2005/06/06 17:01:24 tgl Exp $ + * $PostgreSQL: pgsql/src/include/access/rmgr.h,v 1.15 2005/11/07 17:36:46 tgl Exp $ */ #ifndef RMGR_H #define RMGR_H @@ -23,7 +23,6 @@ typedef uint8 RmgrId; #define RM_HEAP_ID 10 #define RM_BTREE_ID 11 #define RM_HASH_ID 12 -#define RM_RTREE_ID 13 #define RM_GIST_ID 14 #define RM_SEQ_ID 15 #define RM_MAX_ID RM_SEQ_ID diff --git a/src/include/access/rtree.h b/src/include/access/rtree.h deleted file mode 100644 index d5aa103af7c..00000000000 --- a/src/include/access/rtree.h +++ /dev/null @@ -1,145 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtree.h - * common declarations for the rtree access method code. - * - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * $PostgreSQL: pgsql/src/include/access/rtree.h,v 1.41 2005/06/24 20:53:31 tgl Exp $ - * - *------------------------------------------------------------------------- - */ -#ifndef RTREE_H -#define RTREE_H - -#include "access/itup.h" -#include "access/sdir.h" -#include "access/skey.h" -#include "access/xlog.h" -#include "utils/rel.h" - -/* see rtstrat.c for what all this is about */ -#define RTNStrategies 12 -#define RTLeftStrategyNumber 1 -#define RTOverLeftStrategyNumber 2 -#define RTOverlapStrategyNumber 3 -#define RTOverRightStrategyNumber 4 -#define RTRightStrategyNumber 5 -#define RTSameStrategyNumber 6 -#define RTContainsStrategyNumber 7 -#define RTContainedByStrategyNumber 8 -#define RTOverBelowStrategyNumber 9 -#define RTBelowStrategyNumber 10 -#define RTAboveStrategyNumber 11 -#define RTOverAboveStrategyNumber 12 - -#define RTNProcs 3 -#define RT_UNION_PROC 1 -#define RT_INTER_PROC 2 -#define RT_SIZE_PROC 3 - -#define F_LEAF (1 << 0) - -typedef struct RTreePageOpaqueData -{ - uint32 flags; -} RTreePageOpaqueData; - -typedef RTreePageOpaqueData *RTreePageOpaque; - -/* - * When we descend a tree, we keep a stack of parent pointers. - */ - -typedef struct RTSTACK -{ - struct RTSTACK *rts_parent; - OffsetNumber rts_child; - BlockNumber rts_blk; -} RTSTACK; - -/* - * When we're doing a scan, we need to keep track of the parent stack - * for the marked and current items. Also, rtrees have the following - * property: if you're looking for the box (1,1,2,2), on the internal - * nodes you have to search for all boxes that *contain* (1,1,2,2), - * and not the ones that match it. We have a private scan key for - * internal nodes in the opaque structure for rtrees for this reason. - * See access/index-rtree/rtscan.c and rtstrat.c for how it gets - * initialized. We also keep pins on the scan's current buffer and - * marked buffer, if any: this avoids the need to invoke ReadBuffer() - * for each tuple produced by the index scan. - */ - -typedef struct RTreeScanOpaqueData -{ - struct RTSTACK *s_stack; - struct RTSTACK *s_markstk; - uint16 s_flags; - int s_internalNKey; - ScanKey s_internalKey; - Buffer curbuf; - Buffer markbuf; -} RTreeScanOpaqueData; - -typedef RTreeScanOpaqueData *RTreeScanOpaque; - -/* - * When we're doing a scan and updating a tree at the same time, the - * updates may affect the scan. We use the flags entry of the scan's - * opaque space to record our actual position in response to updates - * that we can't handle simply by adjusting pointers. - */ - -#define RTS_CURBEFORE ((uint16) (1 << 0)) -#define RTS_MRKBEFORE ((uint16) (1 << 1)) - -/* root page of an rtree */ -#define P_ROOT 0 - -/* - * When we update a relation on which we're doing a scan, we need to - * check the scan and fix it if the update affected any of the pages it - * touches. Otherwise, we can miss records that we should see. The only - * times we need to do this are for deletions and splits. See the code in - * rtscan.c for how the scan is fixed. These two contants tell us what sort - * of operation changed the index. - */ - -#define RTOP_DEL 0 -#define RTOP_SPLIT 1 - -/* defined in rtree.c */ -extern void freestack(RTSTACK *s); - -/* - * RTree code. - * Defined in access/rtree/ - */ -extern Datum rtinsert(PG_FUNCTION_ARGS); -extern Datum rtbulkdelete(PG_FUNCTION_ARGS); -extern Datum rtbeginscan(PG_FUNCTION_ARGS); -extern Datum rtgettuple(PG_FUNCTION_ARGS); -extern Datum rtgetmulti(PG_FUNCTION_ARGS); -extern Datum rtendscan(PG_FUNCTION_ARGS); -extern Datum rtmarkpos(PG_FUNCTION_ARGS); -extern Datum rtrestrpos(PG_FUNCTION_ARGS); -extern Datum rtrescan(PG_FUNCTION_ARGS); -extern Datum rtbuild(PG_FUNCTION_ARGS); -extern void _rtdump(Relation r); - -extern void rtree_redo(XLogRecPtr lsn, XLogRecord *record); -extern void rtree_desc(char *buf, uint8 xl_info, char *rec); - -/* rtscan.c */ -extern void rtadjscans(Relation r, int op, BlockNumber blkno, - OffsetNumber offnum); -extern void ReleaseResources_rtree(void); - -/* rtstrat.c */ -extern StrategyNumber RTMapToInternalOperator(StrategyNumber strat); -extern bool RTMapToInternalNegate(StrategyNumber strat); - -#endif /* RTREE_H */ diff --git a/src/include/access/rtscan.h b/src/include/access/rtscan.h deleted file mode 100644 index 596ec2825c9..00000000000 --- a/src/include/access/rtscan.h +++ /dev/null @@ -1,23 +0,0 @@ -/*------------------------------------------------------------------------- - * - * rtscan.h - * routines defined in access/rtree/rtscan.c - * - * - * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group - * Portions Copyright (c) 1994, Regents of the University of California - * - * $PostgreSQL: pgsql/src/include/access/rtscan.h,v 1.18 2004/12/31 22:03:21 pgsql Exp $ - * - *------------------------------------------------------------------------- - */ -#ifndef RTSCAN_H -#define RTSCAN_H - -#include "storage/block.h" -#include "storage/off.h" -#include "utils/rel.h" - -void rtadjscans(Relation r, int op, BlockNumber blkno, OffsetNumber offnum); - -#endif /* RTSCAN_H */ diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h index 3986f7a7fa1..94cadcd492e 100644 --- a/src/include/catalog/catversion.h +++ b/src/include/catalog/catversion.h @@ -37,7 +37,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.305 2005/10/21 15:45:06 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/catversion.h,v 1.306 2005/11/07 17:36:46 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -53,6 +53,6 @@ */ /* yyyymmddN */ -#define CATALOG_VERSION_NO 200510211 +#define CATALOG_VERSION_NO 200511071 #endif diff --git a/src/include/catalog/pg_am.h b/src/include/catalog/pg_am.h index 4f21202fa9b..2ef62c24944 100644 --- a/src/include/catalog/pg_am.h +++ b/src/include/catalog/pg_am.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.38 2005/10/15 02:49:42 momjian Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_am.h,v 1.39 2005/11/07 17:36:46 tgl Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -104,8 +104,6 @@ typedef FormData_pg_am *Form_pg_am; * ---------------- */ -DATA(insert OID = 402 ( rtree 12 3 0 f f f f f rtinsert rtbeginscan rtgettuple rtgetmulti rtrescan rtendscan rtmarkpos rtrestrpos rtbuild rtbulkdelete - rtcostestimate )); -DESCR("r-tree index access method"); DATA(insert OID = 403 ( btree 5 1 1 t t t t t btinsert btbeginscan btgettuple btgetmulti btrescan btendscan btmarkpos btrestrpos btbuild btbulkdelete btvacuumcleanup btcostestimate )); DESCR("b-tree index access method"); #define BTREE_AM_OID 403 diff --git a/src/include/catalog/pg_amop.h b/src/include/catalog/pg_amop.h index 09ea2d9856a..55b289212d9 100644 --- a/src/include/catalog/pg_amop.h +++ b/src/include/catalog/pg_amop.h @@ -23,7 +23,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_amop.h,v 1.66 2005/10/15 02:49:42 momjian Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_amop.h,v 1.67 2005/11/07 17:36:46 tgl Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -81,40 +81,6 @@ typedef FormData_pg_amop *Form_pg_amop; */ /* - * rtree box_ops - */ - -DATA(insert ( 425 0 1 f 493 )); -DATA(insert ( 425 0 2 f 494 )); -DATA(insert ( 425 0 3 f 500 )); -DATA(insert ( 425 0 4 f 495 )); -DATA(insert ( 425 0 5 f 496 )); -DATA(insert ( 425 0 6 f 499 )); -DATA(insert ( 425 0 7 f 498 )); -DATA(insert ( 425 0 8 f 497 )); -DATA(insert ( 425 0 9 f 2571 )); -DATA(insert ( 425 0 10 f 2570 )); -DATA(insert ( 425 0 11 f 2573 )); -DATA(insert ( 425 0 12 f 2572 )); - -/* - * rtree poly_ops (supports polygons) - */ - -DATA(insert ( 1993 0 1 f 485 )); -DATA(insert ( 1993 0 2 f 486 )); -DATA(insert ( 1993 0 3 f 492 )); -DATA(insert ( 1993 0 4 f 487 )); -DATA(insert ( 1993 0 5 f 488 )); -DATA(insert ( 1993 0 6 f 491 )); -DATA(insert ( 1993 0 7 f 490 )); -DATA(insert ( 1993 0 8 f 489 )); -DATA(insert ( 1993 0 9 f 2575 )); -DATA(insert ( 1993 0 10 f 2574 )); -DATA(insert ( 1993 0 11 f 2577 )); -DATA(insert ( 1993 0 12 f 2576 )); - -/* * btree int2_ops */ diff --git a/src/include/catalog/pg_amproc.h b/src/include/catalog/pg_amproc.h index 38c4f257837..c4d494dea09 100644 --- a/src/include/catalog/pg_amproc.h +++ b/src/include/catalog/pg_amproc.h @@ -19,7 +19,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_amproc.h,v 1.54 2005/07/01 19:19:03 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_amproc.h,v 1.55 2005/11/07 17:36:46 tgl Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -74,15 +74,6 @@ typedef FormData_pg_amproc *Form_pg_amproc; * ---------------- */ -/* rtree */ -DATA(insert ( 425 0 1 193 )); -DATA(insert ( 425 0 2 194 )); -DATA(insert ( 425 0 3 195 )); -DATA(insert ( 1993 0 1 197 )); -DATA(insert ( 1993 0 2 198 )); -DATA(insert ( 1993 0 3 199 )); - - /* btree */ DATA(insert ( 397 0 1 382 )); DATA(insert ( 421 0 1 357 )); diff --git a/src/include/catalog/pg_opclass.h b/src/include/catalog/pg_opclass.h index 24b4059a831..aa2f86d9e2c 100644 --- a/src/include/catalog/pg_opclass.h +++ b/src/include/catalog/pg_opclass.h @@ -27,7 +27,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_opclass.h,v 1.66 2005/07/01 19:19:03 tgl Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_opclass.h,v 1.67 2005/11/07 17:36:46 tgl Exp $ * * NOTES * the genbki.sh script reads this file and generates .bki @@ -94,7 +94,6 @@ DATA(insert OID = 397 ( 403 array_ops PGNSP PGUID 2277 t 0 )); DATA(insert OID = 423 ( 403 bit_ops PGNSP PGUID 1560 t 0 )); DATA(insert OID = 424 ( 403 bool_ops PGNSP PGUID 16 t 0 )); #define BOOL_BTREE_OPS_OID 424 -DATA(insert OID = 425 ( 402 box_ops PGNSP PGUID 603 t 0 )); DATA(insert OID = 426 ( 403 bpchar_ops PGNSP PGUID 1042 t 0 )); #define BPCHAR_BTREE_OPS_OID 426 DATA(insert OID = 427 ( 405 bpchar_ops PGNSP PGUID 1042 t 0 )); @@ -135,7 +134,6 @@ DATA(insert OID = 1989 ( 403 oid_ops PGNSP PGUID 26 t 0 )); DATA(insert OID = 1990 ( 405 oid_ops PGNSP PGUID 26 t 0 )); DATA(insert OID = 1991 ( 403 oidvector_ops PGNSP PGUID 30 t 0 )); DATA(insert OID = 1992 ( 405 oidvector_ops PGNSP PGUID 30 t 0 )); -DATA(insert OID = 1993 ( 402 poly_ops PGNSP PGUID 604 t 0 )); DATA(insert OID = 1994 ( 403 text_ops PGNSP PGUID 25 t 0 )); #define TEXT_BTREE_OPS_OID 1994 DATA(insert OID = 1995 ( 405 text_ops PGNSP PGUID 25 t 0 )); diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h index b63b2d4a8b0..5b0af25c1c0 100644 --- a/src/include/catalog/pg_proc.h +++ b/src/include/catalog/pg_proc.h @@ -7,7 +7,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.387 2005/10/15 02:49:42 momjian Exp $ + * $PostgreSQL: pgsql/src/include/catalog/pg_proc.h,v 1.388 2005/11/07 17:36:46 tgl Exp $ * * NOTES * The script catalog/genbki.sh reads this file and generates .bki @@ -394,18 +394,6 @@ DATA(insert OID = 191 ( box_right PGNSP PGUID 12 f f t f i 2 16 "603 603" _ DESCR("is right of"); DATA(insert OID = 192 ( box_contained PGNSP PGUID 12 f f t f i 2 16 "603 603" _null_ _null_ _null_ box_contained - _null_ )); DESCR("contained in?"); -DATA(insert OID = 193 ( rt_box_union PGNSP PGUID 12 f f t f i 2 603 "603 603" _null_ _null_ _null_ rt_box_union - _null_ )); -DESCR("r-tree"); -DATA(insert OID = 194 ( rt_box_inter PGNSP PGUID 12 f f t f i 2 2278 "603 603" _null_ _null_ _null_ rt_box_inter - _null_ )); -DESCR("r-tree"); -DATA(insert OID = 195 ( rt_box_size PGNSP PGUID 12 f f t f i 2 2278 "603 2281" _null_ _null_ _null_ rt_box_size - _null_ )); -DESCR("r-tree"); -DATA(insert OID = 197 ( rt_poly_union PGNSP PGUID 12 f f t f i 2 604 "604 604" _null_ _null_ _null_ rt_poly_union - _null_ )); -DESCR("r-tree"); -DATA(insert OID = 198 ( rt_poly_inter PGNSP PGUID 12 f f t f i 2 2278 "604 604" _null_ _null_ _null_ rt_poly_inter - _null_ )); -DESCR("r-tree"); -DATA(insert OID = 199 ( rt_poly_size PGNSP PGUID 12 f f t f i 2 2278 "604 2281" _null_ _null_ _null_ rt_poly_size - _null_ )); -DESCR("r-tree"); /* OIDS 200 - 299 */ @@ -668,29 +656,6 @@ DESCR("convert int4 to float4"); DATA(insert OID = 319 ( int4 PGNSP PGUID 12 f f t f i 1 23 "700" _null_ _null_ _null_ ftoi4 - _null_ )); DESCR("convert float4 to int4"); -DATA(insert OID = 320 ( rtinsert PGNSP PGUID 12 f f t f v 6 16 "2281 2281 2281 2281 2281 2281" _null_ _null_ _null_ rtinsert - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 322 ( rtgettuple PGNSP PGUID 12 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ rtgettuple - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 635 ( rtgetmulti PGNSP PGUID 12 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ rtgetmulti - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 323 ( rtbuild PGNSP PGUID 12 f f t f v 3 2278 "2281 2281 2281" _null_ _null_ _null_ rtbuild - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 324 ( rtbeginscan PGNSP PGUID 12 f f t f v 3 2281 "2281 2281 2281" _null_ _null_ _null_ rtbeginscan - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 325 ( rtendscan PGNSP PGUID 12 f f t f v 1 2278 "2281" _null_ _null_ _null_ rtendscan - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 326 ( rtmarkpos PGNSP PGUID 12 f f t f v 1 2278 "2281" _null_ _null_ _null_ rtmarkpos - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 327 ( rtrestrpos PGNSP PGUID 12 f f t f v 1 2278 "2281" _null_ _null_ _null_ rtrestrpos - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 328 ( rtrescan PGNSP PGUID 12 f f t f v 2 2278 "2281 2281" _null_ _null_ _null_ rtrescan - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 321 ( rtbulkdelete PGNSP PGUID 12 f f t f v 3 2281 "2281 2281 2281" _null_ _null_ _null_ rtbulkdelete - _null_ )); -DESCR("r-tree(internal)"); -DATA(insert OID = 1265 ( rtcostestimate PGNSP PGUID 12 f f t f v 7 2278 "2281 2281 2281 2281 2281 2281 2281" _null_ _null_ _null_ rtcostestimate - _null_ )); -DESCR("r-tree(internal)"); - DATA(insert OID = 330 ( btgettuple PGNSP PGUID 12 f f t f v 2 16 "2281 2281" _null_ _null_ _null_ btgettuple - _null_ )); DESCR("btree(internal)"); DATA(insert OID = 636 ( btgetmulti PGNSP PGUID 12 f f t f v 4 16 "2281 2281 2281 2281" _null_ _null_ _null_ btgetmulti - _null_ )); diff --git a/src/include/utils/geo_decls.h b/src/include/utils/geo_decls.h index 1795a9f14a0..7e27150ea2d 100644 --- a/src/include/utils/geo_decls.h +++ b/src/include/utils/geo_decls.h @@ -6,7 +6,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/utils/geo_decls.h,v 1.48 2005/07/01 19:19:04 tgl Exp $ + * $PostgreSQL: pgsql/src/include/utils/geo_decls.h,v 1.49 2005/11/07 17:36:47 tgl Exp $ * * NOTE * These routines do *not* use the float types from adt/. @@ -406,14 +406,6 @@ extern Datum poly_circle(PG_FUNCTION_ARGS); extern Datum circle_poly(PG_FUNCTION_ARGS); extern Datum circle_area(PG_FUNCTION_ARGS); -/* support routines for the rtree access method (access/rtree/rtproc.c) */ -extern Datum rt_box_union(PG_FUNCTION_ARGS); -extern Datum rt_box_inter(PG_FUNCTION_ARGS); -extern Datum rt_box_size(PG_FUNCTION_ARGS); -extern Datum rt_poly_size(PG_FUNCTION_ARGS); -extern Datum rt_poly_union(PG_FUNCTION_ARGS); -extern Datum rt_poly_inter(PG_FUNCTION_ARGS); - /* support routines for the GiST access method (access/gist/gistproc.c) */ extern Datum gist_box_compress(PG_FUNCTION_ARGS); extern Datum gist_box_decompress(PG_FUNCTION_ARGS); diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h index ba91b0b4022..7ba2dde1d90 100644 --- a/src/include/utils/selfuncs.h +++ b/src/include/utils/selfuncs.h @@ -8,7 +8,7 @@ * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group * Portions Copyright (c) 1994, Regents of the University of California * - * $PostgreSQL: pgsql/src/include/utils/selfuncs.h,v 1.24 2005/10/15 02:49:46 momjian Exp $ + * $PostgreSQL: pgsql/src/include/utils/selfuncs.h,v 1.25 2005/11/07 17:36:47 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -124,7 +124,6 @@ extern Selectivity estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets); extern Datum btcostestimate(PG_FUNCTION_ARGS); -extern Datum rtcostestimate(PG_FUNCTION_ARGS); extern Datum hashcostestimate(PG_FUNCTION_ARGS); extern Datum gistcostestimate(PG_FUNCTION_ARGS); diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out index 7bd4e0c5226..13aca04270b 100644 --- a/src/test/regress/expected/create_index.out +++ b/src/test/regress/expected/create_index.out @@ -46,55 +46,6 @@ CREATE INDEX onek2_u2_prtl ON onek2 USING btree(unique2 int4_ops) CREATE INDEX onek2_stu1_prtl ON onek2 USING btree(stringu1 name_ops) where onek2.stringu1 >= 'J' and onek2.stringu1 < 'K'; -- --- RTREE --- --- rtrees use a quadratic page-splitting algorithm that takes a --- really, really long time. we don't test all rtree opclasses --- in the regression test (we check them using the sequoia 2000 --- benchmark). --- -CREATE INDEX rect2ind ON fast_emp4000 USING rtree (home_base); -SET enable_seqscan = ON; -SET enable_indexscan = OFF; -SET enable_bitmapscan = OFF; -SELECT * FROM fast_emp4000 - WHERE home_base @ '(200,200),(2000,1000)'::box - ORDER BY home_base USING <; - home_base ------------------------ - (1444,403),(1346,344) - (337,455),(240,359) -(2 rows) - -SELECT count(*) FROM fast_emp4000 WHERE home_base && '(1000,1000,0,0)'::box; - count -------- - 2 -(1 row) - -SET enable_seqscan = OFF; -SET enable_indexscan = ON; -SET enable_bitmapscan = ON; --- there's no easy way to check that these commands actually use --- the index, unfortunately. (EXPLAIN would work, but its output --- changes too often for me to want to put an EXPLAIN in the test...) -SELECT * FROM fast_emp4000 - WHERE home_base @ '(200,200),(2000,1000)'::box - ORDER BY home_base USING <; - home_base ------------------------ - (1444,403),(1346,344) - (337,455),(240,359) -(2 rows) - -SELECT count(*) FROM fast_emp4000 WHERE home_base && '(1000,1000,0,0)'::box; - count -------- - 2 -(1 row) - -DROP INDEX rect2ind; --- -- GiST (rtree-equivalent opclasses only) -- CREATE INDEX grect2ind ON fast_emp4000 USING gist (home_base); diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out index 2904585883f..aad7a10ed0a 100644 --- a/src/test/regress/expected/opr_sanity.out +++ b/src/test/regress/expected/opr_sanity.out @@ -798,18 +798,6 @@ FROM pg_amop p1 LEFT JOIN pg_opclass p2 ON amopclaid = p2.oid ORDER BY 1, 2, 3; opcamid | amopstrategy | oprname ---------+--------------+--------- - 402 | 1 | << - 402 | 2 | &< - 402 | 3 | && - 402 | 4 | &> - 402 | 5 | >> - 402 | 6 | ~= - 402 | 7 | ~ - 402 | 8 | @ - 402 | 9 | &<| - 402 | 10 | <<| - 402 | 11 | |>> - 402 | 12 | |&> 403 | 1 | < 403 | 1 | ~<~ 403 | 2 | <= @@ -834,7 +822,7 @@ ORDER BY 1, 2, 3; 783 | 10 | <<| 783 | 11 | |>> 783 | 12 | |&> -(36 rows) +(24 rows) -- Check that all operators linked to by opclass entries have selectivity -- estimators. This is not absolutely required, but it seems a reasonable diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql index 07f40f5c775..aa70bdd46f5 100644 --- a/src/test/regress/sql/create_index.sql +++ b/src/test/regress/sql/create_index.sql @@ -68,42 +68,6 @@ CREATE INDEX onek2_stu1_prtl ON onek2 USING btree(stringu1 name_ops) where onek2.stringu1 >= 'J' and onek2.stringu1 < 'K'; -- --- RTREE --- --- rtrees use a quadratic page-splitting algorithm that takes a --- really, really long time. we don't test all rtree opclasses --- in the regression test (we check them using the sequoia 2000 --- benchmark). --- -CREATE INDEX rect2ind ON fast_emp4000 USING rtree (home_base); - -SET enable_seqscan = ON; -SET enable_indexscan = OFF; -SET enable_bitmapscan = OFF; - -SELECT * FROM fast_emp4000 - WHERE home_base @ '(200,200),(2000,1000)'::box - ORDER BY home_base USING <; - -SELECT count(*) FROM fast_emp4000 WHERE home_base && '(1000,1000,0,0)'::box; - -SET enable_seqscan = OFF; -SET enable_indexscan = ON; -SET enable_bitmapscan = ON; - --- there's no easy way to check that these commands actually use --- the index, unfortunately. (EXPLAIN would work, but its output --- changes too often for me to want to put an EXPLAIN in the test...) -SELECT * FROM fast_emp4000 - WHERE home_base @ '(200,200),(2000,1000)'::box - ORDER BY home_base USING <; - -SELECT count(*) FROM fast_emp4000 WHERE home_base && '(1000,1000,0,0)'::box; - -DROP INDEX rect2ind; - - --- -- GiST (rtree-equivalent opclasses only) -- CREATE INDEX grect2ind ON fast_emp4000 USING gist (home_base); diff --git a/src/tools/backend/backend_dirs.html b/src/tools/backend/backend_dirs.html index 30898c446ce..9ce2bedfcb6 100644 --- a/src/tools/backend/backend_dirs.html +++ b/src/tools/backend/backend_dirs.html @@ -212,9 +212,6 @@ index types<br /> <a id="access_nbtree" name="access_nbtree"></a> <a href="../../backend/access/nbtree">access/nbtree</a> - Lehman and Yao's btree management algorithm<br /> - <a id="access_rtree" name="access_rtree"></a> <a -href="../../backend/access/rtree">access/rtree</a> - used for -indexing of 2-dimensional data<br /> <a id="access_transam" name="access_transam"></a> <a href="../../backend/access/transam">access/transam</a> - transaction manager (BEGIN/ABORT/COMMIT)<br /> |