Terminology issue: suffix tree
Started by Alexander Korotkovover 12 years ago5 messages
Hackers,
we have SP-GiST opclass called suffix tree. Apparently is NOT suffix tree.
In suffix tree we insert every suffix of source string into the tree.
http://en.wikipedia.org/wiki/Suffix_tree
Actually opclass implemented radix tree or patricia tree.
http://en.wikipedia.org/wiki/Radix_tree
Likely we need a patch to rename it in all the places it mentioned.
------
With best regards,
Alexander Korotkov.
Re: Terminology issue: suffix tree
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov <aekorotkov@gmail.com>wrote:
Hackers,
we have SP-GiST opclass called suffix tree. Apparently is NOT suffix tree.
To be clear: not opclass name itself, but comments, readmes and docs are
affected.
In suffix tree we insert every suffix of source string into the tree.
http://en.wikipedia.org/wiki/Suffix_tree
Actually opclass implemented radix tree or patricia tree.
http://en.wikipedia.org/wiki/Radix_tree
Likely we need a patch to rename it in all the places it mentioned.
Patch is attached. Apparently, we have same issue in contrib/unaccent.
------
With best regards,
Alexander Korotkov.
Attachments:
suffix-fix.patchapplication/octet-stream; name=suffix-fix.patchDownload
diff --git a/doc/src/sgml/indices.sgml b/doc/src/sgml/indices.sgml
new file mode 100644
index e6a14de..b1c8f22
*** a/doc/src/sgml/indices.sgml
--- b/doc/src/sgml/indices.sgml
*************** SELECT * FROM places ORDER BY location <
*** 267,273 ****
SP-GiST indexes, like GiST indexes, offer an infrastructure that supports
various kinds of searches. SP-GiST permits implementation of a wide range
of different non-balanced disk-based data structures, such as quadtrees,
! k-d trees, and suffix trees (tries). As an example, the standard distribution of
<productname>PostgreSQL</productname> includes SP-GiST operator classes
for two-dimensional points, which support indexed
queries using these operators:
--- 267,273 ----
SP-GiST indexes, like GiST indexes, offer an infrastructure that supports
various kinds of searches. SP-GiST permits implementation of a wide range
of different non-balanced disk-based data structures, such as quadtrees,
! k-d trees, and radix trees (tries). As an example, the standard distribution of
<productname>PostgreSQL</productname> includes SP-GiST operator classes
for two-dimensional points, which support indexed
queries using these operators:
diff --git a/doc/src/sgml/spgist.sgml b/doc/src/sgml/spgist.sgml
new file mode 100644
index cec40b8..a043ffb
*** a/doc/src/sgml/spgist.sgml
--- b/doc/src/sgml/spgist.sgml
***************
*** 15,21 ****
<acronym>SP-GiST</acronym> is an abbreviation for space-partitioned
<acronym>GiST</acronym>. <acronym>SP-GiST</acronym> supports partitioned
search trees, which facilitate development of a wide range of different
! non-balanced data structures, such as quad-trees, k-d trees, and suffix
trees (tries). The common feature of these structures is that they
repeatedly divide the search space into partitions that need not be
of equal size. Searches that are well matched to the partitioning rule
--- 15,21 ----
<acronym>SP-GiST</acronym> is an abbreviation for space-partitioned
<acronym>GiST</acronym>. <acronym>SP-GiST</acronym> supports partitioned
search trees, which facilitate development of a wide range of different
! non-balanced data structures, such as quad-trees, k-d trees, and radix
trees (tries). The common feature of these structures is that they
repeatedly divide the search space into partitions that need not be
of equal size. Searches that are well matched to the partitioning rule
***************
*** 81,89 ****
A node contains a downlink that leads to either another, lower-level inner
tuple, or a short list of leaf tuples that all lie on the same index page.
Each node has a <firstterm>label</> that describes it; for example,
! in a suffix tree the node label could be the next character of the string
value. Optionally, an inner tuple can have a <firstterm>prefix</> value
! that describes all its members. In a suffix tree this could be the common
prefix of the represented strings. The prefix value is not necessarily
really a prefix, but can be any data needed by the operator class;
for example, in a quad-tree it can store the central point that the four
--- 81,89 ----
A node contains a downlink that leads to either another, lower-level inner
tuple, or a short list of leaf tuples that all lie on the same index page.
Each node has a <firstterm>label</> that describes it; for example,
! in a radix tree the node label could be the next character of the string
value. Optionally, an inner tuple can have a <firstterm>prefix</> value
! that describes all its members. In a radix tree this could be the common
prefix of the represented strings. The prefix value is not necessarily
really a prefix, but can be any data needed by the operator class;
for example, in a quad-tree it can store the central point that the four
*************** typedef struct spgLeafConsistentOut
*** 636,642 ****
<para>
Individual leaf tuples and inner tuples must fit on a single index page
(8KB by default). Therefore, when indexing values of variable-length
! data types, long values can only be supported by methods such as suffix
trees, in which each level of the tree includes a prefix that is short
enough to fit on a page, and the final leaf level includes a suffix also
short enough to fit on a page. The operator class should set
--- 636,642 ----
<para>
Individual leaf tuples and inner tuples must fit on a single index page
(8KB by default). Therefore, when indexing values of variable-length
! data types, long values can only be supported by methods such as radix
trees, in which each level of the tree includes a prefix that is short
enough to fit on a page, and the final leaf level includes a suffix also
short enough to fit on a page. The operator class should set
*************** typedef struct spgLeafConsistentOut
*** 740,746 ****
<para>
The <productname>PostgreSQL</productname> source distribution includes
several examples of index operator classes for
! <acronym>SP-GiST</acronym>. The core system currently provides suffix
trees over text columns and two types of trees over points: quad-tree and
k-d tree. Look into <filename>src/backend/access/spgist/</> to see the
code.
--- 740,746 ----
<para>
The <productname>PostgreSQL</productname> source distribution includes
several examples of index operator classes for
! <acronym>SP-GiST</acronym>. The core system currently provides radix
trees over text columns and two types of trees over points: quad-tree and
k-d tree. Look into <filename>src/backend/access/spgist/</> to see the
code.
diff --git a/src/backend/access/spgist/README b/src/backend/access/spgist/README
new file mode 100644
index 1b86e27..c231a9c
*** a/src/backend/access/spgist/README
--- b/src/backend/access/spgist/README
*************** src/backend/access/spgist/README
*** 2,8 ****
SP-GiST is an abbreviation of space-partitioned GiST. It provides a
generalized infrastructure for implementing space-partitioned data
! structures, such as quadtrees, k-d trees, and suffix trees (tries). When
implemented in main memory, these structures are usually designed as a set of
dynamically-allocated nodes linked by pointers. This is not suitable for
direct storing on disk, since the chains of pointers can be rather long and
--- 2,8 ----
SP-GiST is an abbreviation of space-partitioned GiST. It provides a
generalized infrastructure for implementing space-partitioned data
! structures, such as quadtrees, k-d trees, and radix trees (tries). When
implemented in main memory, these structures are usually designed as a set of
dynamically-allocated nodes linked by pointers. This is not suitable for
direct storing on disk, since the chains of pointers can be rather long and
*************** Inner tuple consists of:
*** 56,73 ****
optional prefix value - all successors must be consistent with it.
Example:
! suffix tree - prefix value is a common prefix string
quad tree - centroid
k-d tree - one coordinate
list of nodes, where node is a (label, pointer) pair.
! Example of a label: a single character for suffix tree
Leaf tuple consists of:
a leaf value
Example:
! suffix tree - the rest of string (postfix)
quad and k-d tree - the point itself
ItemPointer to the heap
--- 56,73 ----
optional prefix value - all successors must be consistent with it.
Example:
! radix tree - prefix value is a common prefix string
quad tree - centroid
k-d tree - one coordinate
list of nodes, where node is a (label, pointer) pair.
! Example of a label: a single character for radix tree
Leaf tuple consists of:
a leaf value
Example:
! radix tree - the rest of string (postfix)
quad and k-d tree - the point itself
ItemPointer to the heap
*************** space is as good as we can easily make i
*** 122,128 ****
(2) Current implementation allows to do picksplit and insert a new leaf tuple
in one operation, if the new list of leaf tuples fits on one page. It's
always possible for trees with small nodes like quad tree or k-d tree, but
! suffix trees may require another picksplit.
(3) Addition of node must keep size of inner tuple small enough to fit on a
page. After addition, inner tuple could become too large to be stored on
--- 122,128 ----
(2) Current implementation allows to do picksplit and insert a new leaf tuple
in one operation, if the new list of leaf tuples fits on one page. It's
always possible for trees with small nodes like quad tree or k-d tree, but
! radix trees may require another picksplit.
(3) Addition of node must keep size of inner tuple small enough to fit on a
page. After addition, inner tuple could become too large to be stored on
*************** another page, we can't change the number
*** 132,145 ****
we'd make downlink pointers to them invalid. To prevent that, SP-GiST leaves
a "placeholder" tuple, which can be reused later whenever another tuple is
added to the page. See also Concurrency and Vacuum sections below. Right now
! only suffix trees could add a node to the tuple; quad trees and k-d trees
make all possible nodes at once in PickSplitFn() call.
(4) Prefix value could only partially match a new value, so the SplitTuple
action allows breaking the current tree branch into upper and lower sections.
Another way to say it is that we can split the current inner tuple into
"prefix" and "postfix" parts, where the prefix part is able to match the
! incoming new value. Consider example of insertion into a suffix tree. We use
the following notation, where tuple's id is just for discussion (no such id
is actually stored):
--- 132,145 ----
we'd make downlink pointers to them invalid. To prevent that, SP-GiST leaves
a "placeholder" tuple, which can be reused later whenever another tuple is
added to the page. See also Concurrency and Vacuum sections below. Right now
! only radix trees could add a node to the tuple; quad trees and k-d trees
make all possible nodes at once in PickSplitFn() call.
(4) Prefix value could only partially match a new value, so the SplitTuple
action allows breaking the current tree branch into upper and lower sections.
Another way to say it is that we can split the current inner tuple into
"prefix" and "postfix" parts, where the prefix part is able to match the
! incoming new value. Consider example of insertion into a radix tree. We use
the following notation, where tuple's id is just for discussion (no such id
is actually stored):
diff --git a/src/backend/access/spgist/spgtextproc.c b/src/backend/access/spgist/spgtextproc.c
new file mode 100644
index 9ffc870..8d50dcc
*** a/src/backend/access/spgist/spgtextproc.c
--- b/src/backend/access/spgist/spgtextproc.c
***************
*** 1,7 ****
/*-------------------------------------------------------------------------
*
* spgtextproc.c
! * implementation of compressed-suffix tree over text
*
*
* Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
--- 1,7 ----
/*-------------------------------------------------------------------------
*
* spgtextproc.c
! * implementation of radix tree (compressed trie) over text
*
*
* Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
***************
*** 23,29 ****
/*
! * In the worst case, a inner tuple in a text suffix tree could have as many
* as 256 nodes (one for each possible byte value). Each node can take 16
* bytes on MAXALIGN=8 machines. The inner tuple must fit on an index page
* of size BLCKSZ. Rather than assuming we know the exact amount of overhead
--- 23,29 ----
/*
! * In the worst case, a inner tuple in a text radix tree could have as many
* as 256 nodes (one for each possible byte value). Each node can take 16
* bytes on MAXALIGN=8 machines. The inner tuple must fit on an index page
* of size BLCKSZ. Rather than assuming we know the exact amount of overhead
diff --git a/src/include/catalog/pg_proc.h b/src/include/catalog/pg_proc.h
new file mode 100644
index ef89297..e46692a
*** a/src/include/catalog/pg_proc.h
--- b/src/include/catalog/pg_proc.h
*************** DATA(insert OID = 4026 ( spg_kd_inner_c
*** 4702,4716 ****
DESCR("SP-GiST support for k-d tree over point");
DATA(insert OID = 4027 ( spg_text_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_config _null_ _null_ _null_ ));
! DESCR("SP-GiST support for suffix tree over text");
DATA(insert OID = 4028 ( spg_text_choose PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_choose _null_ _null_ _null_ ));
! DESCR("SP-GiST support for suffix tree over text");
DATA(insert OID = 4029 ( spg_text_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_picksplit _null_ _null_ _null_ ));
! DESCR("SP-GiST support for suffix tree over text");
DATA(insert OID = 4030 ( spg_text_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_inner_consistent _null_ _null_ _null_ ));
! DESCR("SP-GiST support for suffix tree over text");
DATA(insert OID = 4031 ( spg_text_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_text_leaf_consistent _null_ _null_ _null_ ));
! DESCR("SP-GiST support for suffix tree over text");
DATA(insert OID = 3469 ( spg_range_quad_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_config _null_ _null_ _null_ ));
DESCR("SP-GiST support for quad tree over range");
--- 4702,4716 ----
DESCR("SP-GiST support for k-d tree over point");
DATA(insert OID = 4027 ( spg_text_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_config _null_ _null_ _null_ ));
! DESCR("SP-GiST support for radix tree over text");
DATA(insert OID = 4028 ( spg_text_choose PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_choose _null_ _null_ _null_ ));
! DESCR("SP-GiST support for radix tree over text");
DATA(insert OID = 4029 ( spg_text_picksplit PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_picksplit _null_ _null_ _null_ ));
! DESCR("SP-GiST support for radix tree over text");
DATA(insert OID = 4030 ( spg_text_inner_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_text_inner_consistent _null_ _null_ _null_ ));
! DESCR("SP-GiST support for radix tree over text");
DATA(insert OID = 4031 ( spg_text_leaf_consistent PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 16 "2281 2281" _null_ _null_ _null_ _null_ spg_text_leaf_consistent _null_ _null_ _null_ ));
! DESCR("SP-GiST support for radix tree over text");
DATA(insert OID = 3469 ( spg_range_quad_config PGNSP PGUID 12 1 0 0 0 f f f f t f i 2 0 2278 "2281 2281" _null_ _null_ _null_ _null_ spg_range_quad_config _null_ _null_ _null_ ));
DESCR("SP-GiST support for quad tree over range");
diff --git a/src/test/regress/expected/create_index.out b/src/test/regress/expected/create_index.out
new file mode 100644
index 2ae991e..ad3a678
*** a/src/test/regress/expected/create_index.out
--- b/src/test/regress/expected/create_index.out
*************** INSERT INTO quad_point_tbl VALUES (NULL)
*** 72,84 ****
CREATE INDEX sp_quad_ind ON quad_point_tbl USING spgist (p);
CREATE TABLE kd_point_tbl AS SELECT * FROM quad_point_tbl;
CREATE INDEX sp_kd_ind ON kd_point_tbl USING spgist (p kd_point_ops);
! CREATE TABLE suffix_text_tbl AS
SELECT name AS t FROM road WHERE name !~ '^[0-9]';
! INSERT INTO suffix_text_tbl
SELECT 'P0123456789abcdef' FROM generate_series(1,1000);
! INSERT INTO suffix_text_tbl VALUES ('P0123456789abcde');
! INSERT INTO suffix_text_tbl VALUES ('P0123456789abcdefF');
! CREATE INDEX sp_suff_ind ON suffix_text_tbl USING spgist (t);
--
-- Test GiST and SP-GiST indexes
--
--- 72,84 ----
CREATE INDEX sp_quad_ind ON quad_point_tbl USING spgist (p);
CREATE TABLE kd_point_tbl AS SELECT * FROM quad_point_tbl;
CREATE INDEX sp_kd_ind ON kd_point_tbl USING spgist (p kd_point_ops);
! CREATE TABLE radix_text_tbl AS
SELECT name AS t FROM road WHERE name !~ '^[0-9]';
! INSERT INTO radix_text_tbl
SELECT 'P0123456789abcdef' FROM generate_series(1,1000);
! INSERT INTO radix_text_tbl VALUES ('P0123456789abcde');
! INSERT INTO radix_text_tbl VALUES ('P0123456789abcdefF');
! CREATE INDEX sp_radix_ind ON radix_text_tbl USING spgist (t);
--
-- Test GiST and SP-GiST indexes
--
*************** SELECT count(*) FROM quad_point_tbl WHER
*** 288,366 ****
1
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
--- 288,366 ----
1
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
*************** SELECT count(*) FROM kd_point_tbl WHERE
*** 952,1146 ****
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t = 'P0123456789abcdef'::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t = 'P0123456789abcde'::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t = 'P0123456789abcdefF'::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t < 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
QUERY PLAN
------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t ~<~ 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
QUERY PLAN
-----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t <= 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
QUERY PLAN
-------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t ~<=~ 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t = 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t = 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
QUERY PLAN
-----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t >= 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
QUERY PLAN
-------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t ~>=~ 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t > 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
QUERY PLAN
------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_suff_ind on suffix_text_tbl
Index Cond: (t ~>~ 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
--- 952,1146 ----
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t = 'P0123456789abcdef'::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t = 'P0123456789abcde'::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t = 'P0123456789abcdefF'::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t < 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
QUERY PLAN
------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t ~<~ 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
QUERY PLAN
-----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t <= 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
QUERY PLAN
-------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t ~<=~ 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t = 'Aztec Ct '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t = 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
QUERY PLAN
-----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t >= 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
QUERY PLAN
-------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t ~>=~ 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t > 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
QUERY PLAN
------------------------------------------------------------------------
Aggregate
! -> Index Only Scan using sp_radix_ind on radix_text_tbl
Index Cond: (t ~>~ 'Worth St '::text)
(3 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
*************** SELECT count(*) FROM kd_point_tbl WHERE
*** 1459,1679 ****
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
QUERY PLAN
-----------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t = 'P0123456789abcdef'::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t = 'P0123456789abcdef'::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
QUERY PLAN
----------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t = 'P0123456789abcde'::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t = 'P0123456789abcde'::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t = 'P0123456789abcdefF'::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t = 'P0123456789abcdefF'::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t < 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t < 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
QUERY PLAN
------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t ~<~ 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t ~<~ 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
QUERY PLAN
-----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t <= 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t <= 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t ~<=~ 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t ~<=~ 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t = 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t = 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t = 'Worth St '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t = 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
QUERY PLAN
-----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t >= 'Worth St '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t >= 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t ~>=~ 'Worth St '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t ~>=~ 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t > 'Worth St '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t > 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
QUERY PLAN
------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on suffix_text_tbl
Recheck Cond: (t ~>~ 'Worth St '::text)
! -> Bitmap Index Scan on sp_suff_ind
Index Cond: (t ~>~ 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
--- 1459,1679 ----
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
QUERY PLAN
-----------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t = 'P0123456789abcdef'::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t = 'P0123456789abcdef'::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
count
-------
1000
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
QUERY PLAN
----------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t = 'P0123456789abcde'::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t = 'P0123456789abcde'::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
QUERY PLAN
------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t = 'P0123456789abcdefF'::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t = 'P0123456789abcdefF'::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t < 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t < 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
QUERY PLAN
------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t ~<~ 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t ~<~ 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
count
-------
272
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
QUERY PLAN
-----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t <= 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t <= 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t ~<=~ 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t ~<=~ 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
count
-------
273
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t = 'Aztec Ct '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t = 'Aztec Ct '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
count
-------
1
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t = 'Worth St '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t = 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
count
-------
2
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
QUERY PLAN
-----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t >= 'Worth St '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t >= 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t ~>=~ 'Worth St '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t ~>=~ 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
count
-------
50
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
QUERY PLAN
----------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t > 'Worth St '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t > 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
count
-------
48
(1 row)
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
QUERY PLAN
------------------------------------------------------------------------------
Aggregate
! -> Bitmap Heap Scan on radix_text_tbl
Recheck Cond: (t ~>~ 'Worth St '::text)
! -> Bitmap Index Scan on sp_radix_ind
Index Cond: (t ~>~ 'Worth St '::text)
(5 rows)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
count
-------
48
diff --git a/src/test/regress/expected/sanity_check.out b/src/test/regress/expected/sanity_check.out
new file mode 100644
index 3f04442..432d39a
*** a/src/test/regress/expected/sanity_check.out
--- b/src/test/regress/expected/sanity_check.out
*************** SELECT relname, relhasindex
*** 137,142 ****
--- 137,143 ----
point_tbl | t
polygon_tbl | t
quad_point_tbl | t
+ radix_text_tbl | t
ramp | f
real_city | f
reltime_tbl | f
*************** SELECT relname, relhasindex
*** 152,158 ****
sql_sizing_profiles | f
stud_emp | f
student | f
- suffix_text_tbl | t
tenk1 | t
tenk2 | t
test_range_excl | t
--- 153,158 ----
diff --git a/src/test/regress/output/misc.source b/src/test/regress/output/misc.source
new file mode 100644
index 2dd5b23..29cbb22
*** a/src/test/regress/output/misc.source
--- b/src/test/regress/output/misc.source
*************** SELECT user_relns() AS user_relns
*** 660,665 ****
--- 660,666 ----
point_tbl
polygon_tbl
quad_point_tbl
+ radix_text_tbl
ramp
random_tbl
real_city
*************** SELECT user_relns() AS user_relns
*** 671,677 ****
stud_emp
student
subselect_tbl
- suffix_text_tbl
t
tenk1
tenk2
--- 672,677 ----
diff --git a/src/test/regress/sql/create_index.sql b/src/test/regress/sql/create_index.sql
new file mode 100644
index 914e7a5..04b69c6
*** a/src/test/regress/sql/create_index.sql
--- b/src/test/regress/sql/create_index.sql
*************** CREATE TABLE kd_point_tbl AS SELECT * FR
*** 110,124 ****
CREATE INDEX sp_kd_ind ON kd_point_tbl USING spgist (p kd_point_ops);
! CREATE TABLE suffix_text_tbl AS
SELECT name AS t FROM road WHERE name !~ '^[0-9]';
! INSERT INTO suffix_text_tbl
SELECT 'P0123456789abcdef' FROM generate_series(1,1000);
! INSERT INTO suffix_text_tbl VALUES ('P0123456789abcde');
! INSERT INTO suffix_text_tbl VALUES ('P0123456789abcdefF');
! CREATE INDEX sp_suff_ind ON suffix_text_tbl USING spgist (t);
--
-- Test GiST and SP-GiST indexes
--- 110,124 ----
CREATE INDEX sp_kd_ind ON kd_point_tbl USING spgist (p kd_point_ops);
! CREATE TABLE radix_text_tbl AS
SELECT name AS t FROM road WHERE name !~ '^[0-9]';
! INSERT INTO radix_text_tbl
SELECT 'P0123456789abcdef' FROM generate_series(1,1000);
! INSERT INTO radix_text_tbl VALUES ('P0123456789abcde');
! INSERT INTO radix_text_tbl VALUES ('P0123456789abcdefF');
! CREATE INDEX sp_radix_ind ON radix_text_tbl USING spgist (t);
--
-- Test GiST and SP-GiST indexes
*************** SELECT count(*) FROM quad_point_tbl WHER
*** 194,224 ****
SELECT count(*) FROM quad_point_tbl WHERE p ~= '(4585, 365)';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
-- Now check the results from plain indexscan
SET enable_seqscan = OFF;
--- 194,224 ----
SELECT count(*) FROM quad_point_tbl WHERE p ~= '(4585, 365)';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
-- Now check the results from plain indexscan
SET enable_seqscan = OFF;
*************** SELECT count(*) FROM kd_point_tbl WHERE
*** 382,437 ****
SELECT count(*) FROM kd_point_tbl WHERE p ~= '(4585, 365)';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
-- Now check the results from bitmap indexscan
SET enable_seqscan = OFF;
--- 382,437 ----
SELECT count(*) FROM kd_point_tbl WHERE p ~= '(4585, 365)';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
-- Now check the results from bitmap indexscan
SET enable_seqscan = OFF;
*************** SELECT count(*) FROM kd_point_tbl WHERE
*** 511,566 ****
SELECT count(*) FROM kd_point_tbl WHERE p ~= '(4585, 365)';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdef';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcde';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'P0123456789abcdefF';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t < 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t <= 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t = 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t >= 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>=~ 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t > 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
! SELECT count(*) FROM suffix_text_tbl WHERE t ~>~ 'Worth St ';
RESET enable_seqscan;
RESET enable_indexscan;
--- 511,566 ----
SELECT count(*) FROM kd_point_tbl WHERE p ~= '(4585, 365)';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdef';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcde';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'P0123456789abcdefF';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t < 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t <= 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~<=~ 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Aztec Ct ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t = 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t >= 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>=~ 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t > 'Worth St ';
EXPLAIN (COSTS OFF)
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
! SELECT count(*) FROM radix_text_tbl WHERE t ~>~ 'Worth St ';
RESET enable_seqscan;
RESET enable_indexscan;
Re: Terminology issue: suffix tree
On 06.05.2013 14:10, Alexander Korotkov wrote:
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov<aekorotkov@gmail.com>wrote:
In suffix tree we insert every suffix of source string into the tree.
http://en.wikipedia.org/wiki/Suffix_tree
Actually opclass implemented radix tree or patricia tree.
http://en.wikipedia.org/wiki/Radix_tree
Likely we need a patch to rename it in all the places it mentioned.Patch is attached.
Thanks, committed.
Apparently, we have same issue in contrib/unaccent.
Yeah. The data structure in contrib/unaccent seems to be a plain old
trie, rather than a radix trie, though. According to wikipedia at least,
the difference is that in a radix tree, the edges are labeled with
sequences of elements, rather than single elements. Want to patch that too?
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
Re: Terminology issue: suffix tree
On Wed, May 8, 2013 at 3:50 PM, Heikki Linnakangas
<hlinnakangas@vmware.com>wrote:
On 06.05.2013 14:10, Alexander Korotkov wrote:
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov<aekorotkov@gmail.com>
**wrote:In suffix tree we insert every suffix of source string into the tree.
http://en.wikipedia.org/wiki/**Suffix_tree<http://en.wikipedia.org/wiki/Suffix_tree>
Actually opclass implemented radix tree or patricia tree.
http://en.wikipedia.org/wiki/**Radix_tree<http://en.wikipedia.org/wiki/Radix_tree>
Likely we need a patch to rename it in all the places it mentioned.Patch is attached.
Thanks, committed.
Thanks!
Apparently, we have same issue in contrib/unaccent.
Yeah. The data structure in contrib/unaccent seems to be a plain old trie,
rather than a radix trie, though. According to wikipedia at least, the
difference is that in a radix tree, the edges are labeled with sequences of
elements, rather than single elements. Want to patch that too?
Agree, trie is most comforming term here. Patch is attached.
------
With best regards,
Alexander Korotkov.
Attachments:
unaccent-suffix-fix.patchapplication/octet-stream; name=unaccent-suffix-fix.patchDownload
diff --git a/contrib/unaccent/unaccent.c b/contrib/unaccent/unaccent.c
new file mode 100644
index 4182376..8caa7c2
*** a/contrib/unaccent/unaccent.c
--- b/contrib/unaccent/unaccent.c
***************
*** 23,52 ****
PG_MODULE_MAGIC;
/*
! * Unaccent dictionary uses uncompressed suffix tree to find a
! * character to replace. Each node of tree is an array of
! * SuffixChar struct with length = 256 (n-th element of array
* corresponds to byte)
*/
! typedef struct SuffixChar
{
! struct SuffixChar *nextChar;
char *replaceTo;
int replacelen;
! } SuffixChar;
/*
! * placeChar - put str into tree's structure, byte by byte.
*/
! static SuffixChar *
! placeChar(SuffixChar *node, unsigned char *str, int lenstr, char *replaceTo, int replacelen)
{
! SuffixChar *curnode;
if (!node)
{
! node = palloc(sizeof(SuffixChar) * 256);
! memset(node, 0, sizeof(SuffixChar) * 256);
}
curnode = node + *str;
--- 23,51 ----
PG_MODULE_MAGIC;
/*
! * Unaccent dictionary uses trie to find a character to replace. Each node of
! * trie is an array of TrieChar struct with length = 256 (n-th element of array
* corresponds to byte)
*/
! typedef struct TrieChar
{
! struct TrieChar *nextChar;
char *replaceTo;
int replacelen;
! } TrieChar;
/*
! * placeChar - put str into trie's structure, byte by byte.
*/
! static TrieChar *
! placeChar(TrieChar *node, unsigned char *str, int lenstr, char *replaceTo, int replacelen)
{
! TrieChar *curnode;
if (!node)
{
! node = palloc(sizeof(TrieChar) * 256);
! memset(node, 0, sizeof(TrieChar) * 256);
}
curnode = node + *str;
*************** placeChar(SuffixChar *node, unsigned cha
*** 71,83 ****
}
/*
! * initSuffixTree - create suffix tree from file. Function converts
* UTF8-encoded file into current encoding.
*/
! static SuffixChar *
! initSuffixTree(char *filename)
{
! SuffixChar *volatile rootSuffixTree = NULL;
MemoryContext ccxt = CurrentMemoryContext;
tsearch_readline_state trst;
volatile bool skip;
--- 70,82 ----
}
/*
! * initTrie - create trie from file. Function converts
* UTF8-encoded file into current encoding.
*/
! static TrieChar *
! initTrie(char *filename)
{
! TrieChar *volatile rootTrie = NULL;
MemoryContext ccxt = CurrentMemoryContext;
tsearch_readline_state trst;
volatile bool skip;
*************** initSuffixTree(char *filename)
*** 161,167 ****
}
if (state >= 3)
! rootSuffixTree = placeChar(rootSuffixTree,
(unsigned char *) src, srclen,
trg, trglen);
--- 160,166 ----
}
if (state >= 3)
! rootTrie = placeChar(rootTrie,
(unsigned char *) src, srclen,
trg, trglen);
*************** initSuffixTree(char *filename)
*** 192,205 ****
tsearch_readline_end(&trst);
! return rootSuffixTree;
}
/*
! * findReplaceTo - find multibyte character in tree
*/
! static SuffixChar *
! findReplaceTo(SuffixChar *node, unsigned char *src, int srclen)
{
while (node)
{
--- 191,204 ----
tsearch_readline_end(&trst);
! return rootTrie;
}
/*
! * findReplaceTo - find multibyte character in trie
*/
! static TrieChar *
! findReplaceTo(TrieChar *node, unsigned char *src, int srclen)
{
while (node)
{
*************** Datum
*** 221,227 ****
unaccent_init(PG_FUNCTION_ARGS)
{
List *dictoptions = (List *) PG_GETARG_POINTER(0);
! SuffixChar *rootSuffixTree = NULL;
bool fileloaded = false;
ListCell *l;
--- 220,226 ----
unaccent_init(PG_FUNCTION_ARGS)
{
List *dictoptions = (List *) PG_GETARG_POINTER(0);
! TrieChar *rootTrie = NULL;
bool fileloaded = false;
ListCell *l;
*************** unaccent_init(PG_FUNCTION_ARGS)
*** 235,241 ****
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("multiple Rules parameters")));
! rootSuffixTree = initSuffixTree(defGetString(defel));
fileloaded = true;
}
else
--- 234,240 ----
ereport(ERROR,
(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
errmsg("multiple Rules parameters")));
! rootTrie = initTrie(defGetString(defel));
fileloaded = true;
}
else
*************** unaccent_init(PG_FUNCTION_ARGS)
*** 254,260 ****
errmsg("missing Rules parameter")));
}
! PG_RETURN_POINTER(rootSuffixTree);
}
PG_FUNCTION_INFO_V1(unaccent_lexize);
--- 253,259 ----
errmsg("missing Rules parameter")));
}
! PG_RETURN_POINTER(rootTrie);
}
PG_FUNCTION_INFO_V1(unaccent_lexize);
*************** Datum unaccent_lexize(PG_FUNCTION_ARGS)
*** 262,282 ****
Datum
unaccent_lexize(PG_FUNCTION_ARGS)
{
! SuffixChar *rootSuffixTree = (SuffixChar *) PG_GETARG_POINTER(0);
char *srcchar = (char *) PG_GETARG_POINTER(1);
int32 len = PG_GETARG_INT32(2);
char *srcstart,
*trgchar = NULL;
int charlen;
TSLexeme *res = NULL;
! SuffixChar *node;
srcstart = srcchar;
while (srcchar - srcstart < len)
{
charlen = pg_mblen(srcchar);
! node = findReplaceTo(rootSuffixTree, (unsigned char *) srcchar, charlen);
if (node && node->replaceTo)
{
if (!res)
--- 261,281 ----
Datum
unaccent_lexize(PG_FUNCTION_ARGS)
{
! TrieChar *rootTrie = (TrieChar *) PG_GETARG_POINTER(0);
char *srcchar = (char *) PG_GETARG_POINTER(1);
int32 len = PG_GETARG_INT32(2);
char *srcstart,
*trgchar = NULL;
int charlen;
TSLexeme *res = NULL;
! TrieChar *node;
srcstart = srcchar;
while (srcchar - srcstart < len)
{
charlen = pg_mblen(srcchar);
! node = findReplaceTo(rootTrie, (unsigned char *) srcchar, charlen);
if (node && node->replaceTo)
{
if (!res)
Re: Terminology issue: suffix tree
On 08.05.2013 15:49, Alexander Korotkov wrote:
On Wed, May 8, 2013 at 3:50 PM, Heikki Linnakangas
<hlinnakangas@vmware.com>wrote:Yeah. The data structure in contrib/unaccent seems to be a plain old trie,
rather than a radix trie, though. According to wikipedia at least, the
difference is that in a radix tree, the edges are labeled with sequences of
elements, rather than single elements. Want to patch that too?Agree, trie is most comforming term here. Patch is attached.
Ok, applied.
- Heikki
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers