GIN - Generalized Inverted iNdex. Try 2.

We (me and Oleg) are glad to present GIN to PostgreSQL. If community will agree,
we will commit it to HEAD branch.

http://www.sigaev.ru/gin/gin.gz
http://www.sigaev.ru/gin/README.txt

Install:
% cd pgsql
% zcat gin.gz | patch -p0
make and initdb, install tsearch2

Changes from previous patch:
* add support for tsearch2
* add 'fuzzy' limit
* fixes

README:

Gin for PostgreSQL

Gin was sponsored by jfg://networks (http://www.jfg-networks.com/)

Gin stands for Generalized Inverted Index and should be considered as a genie,
not a drink.

Generalized means that index doesn't know what operation it accelerates, it
works with strategies, defined for specific data type (read Index Method
Strategies chapter in PostgreSQL documentation). In that sense, gin is similar
to the GiST and differs from btree index, which has predefined comparison based
operations.

Inverted index is an index structure storing a (key,posting list) pairs, where
posting list is a set of documents in which key occurs (document, usually,
contains many keys). The primary goal of the Gin index is a support for
scalable full text search in PostgreSQL.

Gin is consists of a B-tree constructed over entries (ET, entries tree), where
entry is an element of indexed value ( element of array, lexeme for tsvector)
and where each tuple in the leaf pages is either pointer to B-tree over item
pointers (PT, posting tree), or list of item pointers (PL, posting list) if
tuple is small enough.

Notes: There is no delete operation for ET. The reason for this, is that from
our experience, a set of unique words of a whole collection changed very rare.
This greatly simplify code and concurrency algorithm.

Gin comes with built-in support for one dimensional arrays ( integer[], text[],
no support for NULL elements) and following operations:

* contains : value_array @ query_array
* overlap : value_array && query_array
* contained: value_array ~ query_array

Synopsis

=# create index txt_idx on aa using gin(a);

Features

* Concurrency
* WAL-logging (recoverable)
* user-defined opclass, the scheme is similar to GiST
* optimized index creation (make use of maintenance_work_mem to accumulate
postings in memory)
* tsearch2 opclass
* soft upper limit of the returned results set using GUC variable
gin_fuzzy_search_limit

Gin fuzzy limit

There are often situations, when full text search returns a very big set of
results, which is very difficult to manage, since reading tuples from disk and
their ordering could takes a lot of time, which is unacceptable for the
production (notice, that search itself is very fast). Such queries are usually
contain very frequent lexemes, so results are not very helpful. To facilitate
execution of such queries we introduced a configurable soft upper limit of the
size of the returned set - GUC variable gin_fuzzy_search_limit, which is 0 on
default (no limitation). This subset randomly chosen from the whole result set.
Soft means that the actual number of returned results could slightly differs
from this limit, depending on the query and the quality of system random
generator. From our experience, we found that value about several thousands
(5000-20000) is ok, i.e., gin fuzzy limit will have no effects for queries
returning result set lesser than this number.

Limitations

* no support for multicolumn indices
* Gin doesn't uses scan->kill_prior_tuple & scan->ignore_killed_tuples
* Gin searches entry only by equality matching, this may be improved in
future
* Gin doesn't supports full scan of index
* Gin doesn't index NULL value

Gin interface

OpClass interface (pseudocode). Example for opclas is in ginarayproc.c.

Datum* extractValue(Datum inputValue, uint32* nentries)
Returns array of Datum of entries of value to be indexed, nentries should
contains number of returning entries
int compareEntry( Datum a, Datum b )
Compares two entries (not the indexing values!)
Datum* extractQuery(Datum query, uint32* nentries, StrategyNumber n)
Returns array of Datum of entries of query to be searched, n contains
Strategy number of operation.
bool consistent( bool[] check, StrategyNumber n, Datum query)
The size of check array is the same as sizeof of array returned by
extractQuery. Each element of check array is true if indexed value has
corresponding entry in the query, i.e. if check[i] == TRUE then i-th entry
of query is presented in indexed value. Function should returns true if
indexed value matches by StrategyNumber and query.

Open items

We appreciate any comments, help and recommendations.

* teach optimizer/executor, that GIN is intrinsically clustered, i.e., it
always returns ItemPointer in ascending order.
* tweak gincostestimate
* GIN stores several ItemPointer to heap tuple, so vacuum full produces
warning message:

WARNING: index "idx" contains 88395 row versions, but table contains 51812
row versions
HINT: Rebuild the index with REINDEX.

TODO

Nearest future:

* opclasses for all types (no programming, just many changes of the catalog).

Distant future:

* Replace entry btree to something like the GiST
* Add multicolumn support
* Optimize insert operation (background index insertion)

Authors: All work was done by Teodor Sigaev (teodor(at)sigaev(dot)ru) and Oleg
Bartunov (oleg(at)sai(dot)msu(dot)su).

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Wed, 26 Apr 2006, Teodor Sigaev wrote:

>
> We (me and Oleg) are glad to present GIN to PostgreSQL. If community will
> agree, we will commit it to HEAD branch.
>
> http://www.sigaev.ru/gin/gin.gz
> http://www.sigaev.ru/gin/README.txt
>
> Install:
> % cd pgsql
> % zcat gin.gz | patch -p0
> make and initdb, install tsearch2

I just built this, and noticed that the regression test for "opr_sanity"
fails with your patch. I attached the regression.diffs.

--
BOFH excuse #85:

Windows 95 undocumented "feature"

> I just built this, and noticed that the regression test for "opr_sanity"
> fails with your patch. I attached the regression.diffs.

Sorry, this part isn't done yet, because we are waiting of community decision..
We don't add regression test yet.

If community don't like to include GIN in core, we make a contrib/gin, but in
this case GIN can't use WAL feature because of WAL interface can't call
user-defined function.

The reason for first diff is a hardcoded 'gist' index:
-- We have to exclude GiST, unfortunately, since it hasn't got any fixed
-- requirements about strategy operators.

SELECT p1.oid, p1.amname, p2.oid, p2.opcname, p3.amopsubtype
FROM pg_am AS p1, pg_opclass AS p2, pg_amop AS p3
WHERE p2.opcamid = p1.oid AND p3.amopclaid = p2.oid AND
p1.amname != 'gist' AND
p1.amstrategies != (SELECT count(*) FROM pg_amop AS p4
WHERE p4.amopclaid = p2.oid AND
p4.amopsubtype = p3.amopsubtype);

Second is right diff.

For the thread one reason is that operations &&, ~, @ defined for anyarray, but
used for particular types.

>
>
> ------------------------------------------------------------------------
>
> *** ./expected/opr_sanity.out Wed Jan 25 18:35:51 2006
> --- ./results/opr_sanity.out Wed Apr 26 08:31:13 2006
> ***************
> *** 778,785 ****
> WHERE p4.amopclaid = p2.oid AND
> p4.amopsubtype = p3.amopsubtype);
> oid | amname | oid | opcname | amopsubtype
> ! -----+--------+-----+---------+-------------
> ! (0 rows)
>
> -- Check that amopopr points at a reasonable-looking operator, ie a binary
> -- operator yielding boolean.
> --- 778,791 ----
> WHERE p4.amopclaid = p2.oid AND
> p4.amopsubtype = p3.amopsubtype);
> oid | amname | oid | opcname | amopsubtype
> ! ------+--------+------+-----------+-------------
> ! 2742 | gin | 2745 | _int4_ops | 0
> ! 2742 | gin | 2745 | _int4_ops | 0
> ! 2742 | gin | 2745 | _int4_ops | 0
> ! 2742 | gin | 2746 | _text_ops | 0
> ! 2742 | gin | 2746 | _text_ops | 0
> ! 2742 | gin | 2746 | _text_ops | 0
> ! (6 rows)
>
> -- Check that amopopr points at a reasonable-looking operator, ie a binary
> -- operator yielding boolean.
> ***************
> *** 825,831 ****
> 783 | 10 | <<|
> 783 | 11 | |>>
> 783 | 12 | |&>
> ! (24 rows)
>
> -- Check that all operators linked to by opclass entries have selectivity
> -- estimators. This is not absolutely required, but it seems a reasonable
> --- 831,840 ----
> 783 | 10 | <<|
> 783 | 11 | |>>
> 783 | 12 | |&>
> ! 2742 | 1 | &&
> ! 2742 | 2 | @
> ! 2742 | 3 | ~
> ! (27 rows)
>
> -- Check that all operators linked to by opclass entries have selectivity
> -- estimators. This is not absolutely required, but it seems a reasonable
> ***************
> *** 847,854 ****
> WHERE p1.amopopr = p2.oid AND p1.amopclaid = p3.oid AND
> NOT binary_coercible(p3.opcintype, p2.oprleft);
> amopclaid | amopopr | oid | oprname | opcname
> ! -----------+---------+-----+---------+---------
> ! (0 rows)
>
> SELECT p1.amopclaid, p1.amopopr, p2.oid, p2.oprname, p3.opcname
> FROM pg_amop AS p1, pg_operator AS p2, pg_opclass AS p3
> --- 856,869 ----
> WHERE p1.amopopr = p2.oid AND p1.amopclaid = p3.oid AND
> NOT binary_coercible(p3.opcintype, p2.oprleft);
> amopclaid | amopopr | oid | oprname | opcname
> ! -----------+---------+------+---------+-----------
> ! 2746 | 2750 | 2750 | && | _text_ops
> ! 2745 | 2750 | 2750 | && | _int4_ops
> ! 2746 | 2751 | 2751 | @ | _text_ops
> ! 2745 | 2751 | 2751 | @ | _int4_ops
> ! 2746 | 2752 | 2752 | ~ | _text_ops
> ! 2745 | 2752 | 2752 | ~ | _int4_ops
> ! (6 rows)
>
> SELECT p1.amopclaid, p1.amopopr, p2.oid, p2.oprname, p3.opcname
> FROM pg_amop AS p1, pg_operator AS p2, pg_opclass AS p3
>
> ======================================================================
>
>
>
> ------------------------------------------------------------------------
>
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

What changed between Try 1 and Try 2?

Teodor Sigaev wrote:
>
> We (me and Oleg) are glad to present GIN to PostgreSQL. If community
> will agree, we will commit it to HEAD branch.

Oh I can't read - ignore me :)

Teodor Sigaev wrote:

> Changes from previous patch:
> * add support for tsearch2
> * add 'fuzzy' limit
> * fixes

> I took the liberty of revising your README.txt as a native speaker :) I
> cleaned up the grammar a lot, etc.

Thank you very much. I added your README to patch.

New version of GIN is available:

http://www.sigaev.ru/gin/gin.gz
http://www.sigaev.ru/gin/README.txt

Changes from Try 2:
* add regression tests for &&,@,~ operators
* add regression tests for GIN over int4[] and text[]
* fix regression opr_sanity test
* update README ( by Christopher )

Open Items:
* Teach optimizer/executor that GIN is intrinsically clustered. i.e., it
always returns ItemPointer in ascending order.
* Tweak gincostestimate.
* GIN stores several ItemPointer to heap tuple, so VACUUM FULL produces
this warning message:
WARNING: index "idx" contains 88395 row versions, but table contains
51812 row versions
HINT: Rebuild the index with REINDEX.

We appreciate any comments, help and suggestions. For third item we haven't idea
how fix it except to exclude GIN index from check.

Sorry for our persistence, but we really need to known about choice of community
about commiting or making contrib, because it will be difficult to support a big
enough patch up to date...

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev wrote:

> * GIN stores several ItemPointer to heap tuple, so VACUUM FULL produces
> this warning message:
> WARNING: index "idx" contains 88395 row versions, but table contains
> 51812 row versions
> HINT: Rebuild the index with REINDEX.
>
> We appreciate any comments, help and suggestions. For third item we haven't
> idea how fix it except to exclude GIN index from check.

How about adding a column to pg_am indicating "these indexes must always
keep same tuple count as heap". This would be true for all current AMs,
false for GIN.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Alvaro Herrera <alvherre(at)commandprompt(dot)com> writes:
> Teodor Sigaev wrote:
>> We appreciate any comments, help and suggestions. For third item we haven't
>> idea how fix it except to exclude GIN index from check.

> How about adding a column to pg_am indicating "these indexes must always
> keep same tuple count as heap". This would be true for all current AMs,
> false for GIN.

There's a definitional issue here, which is what does it mean to be
counting index tuples. I think GIN could bypass the VACUUM error check
by always returning the heap tuple count as its index tuple count. This
would result in the index's reltuples field getting set to that value
rather than the number of index entries, but arguably that's what we
want anyway. From what I recollect of the planner's use of index
reltuples, values greater than heap tuple count would not behave sanely:
it considers index.reltuples to be an upper bound on the number of rows
an indexscan could fetch.

The ideal thing would be for GIN to return a count of the number of
distinct heap tuples referenced by the entries in the index, but I
suppose that would be impractical for VACUUM to compute.

regards, tom lane

> How about adding a column to pg_am indicating "these indexes must always
> keep same tuple count as heap". This would be true for all current AMs,
> false for GIN.

Yes, it's simplest solution, but it doesn't check of index consistency.

Possible, we can count number of itempointers to heap tuple during build/insert,
and during bulkdelete we count number of deleted and leaved itempointers. So,

N[before bulkdelete] == N[after bulkdelete] + N[deleted]

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> The ideal thing would be for GIN to return a count of the number of
> distinct heap tuples referenced by the entries in the index, but I
> suppose that would be impractical for VACUUM to compute.

Of course, in this case we should collect heap pointers in memory..

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> There's a definitional issue here, which is what does it mean to be
> counting index tuples. I think GIN could bypass the VACUUM error check
> by always returning the heap tuple count as its index tuple count. This

One problem: ambulkdelete hasn't any access to heap or heap's statistics
(num_tuples in scan_index() and vacuum_index() in vacuum.c). So, ambulkdelete
can't set stats->num_index_tuples equal to num_tuples. With partial index
problem is increased...

After looking into vacuum.c I found following ways to skip check:
1) Simplest: just return NULL by ginvacuumcleanup. Disadvantage:
drop any statistics
2) Quick hack in vacuum.c to be fixed in a future:
if ( indrel->rd_rel->relam == GIN_AM_OID )
stats->num_index_tuples = num_tuples;
else if (stats->num_index_tuples != num_tuples ) {
checking as now
}
3) Add column to pg_am pointed to scan_index/vacuum_index's behaviour
like above. I don't think that column is frequent case - only for
inverted indexes.

If there is not objections, at Tuesday we add quick hack (2) and commit GIN.
After that our plan is:
1) add opclasses for other array
2) add indisclustered=true for all GIN indexes by changes in
UpdateIndexRelation() and mark_index_clustered(). The issue is:
can table be clustered on several indexes now? Because GIN is always 'clustered'
table can be clustered on several GIN index and one any other. Cluster command
on GIN index should do nothing. May be, it will be cleaner to add indclustered
column to pg_am.
3) Return to WAL problem with GiST
4) work on gincostesimate and, possibly, GIN's opclasses costestimate tweak...
Including num_tuples issue

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
> One problem: ambulkdelete hasn't any access to heap or heap's statistics
> (num_tuples in scan_index() and vacuum_index() in vacuum.c). So, ambulkdelete
> can't set stats->num_index_tuples equal to num_tuples.

We could probably fix that by adding it to the stats structs that are
passed around during VACUUM. I'd rather not hardwire a GIN special case
in vacuum.c as per your "quick hack".

> 2) add indisclustered=true for all GIN indexes by changes in
> UpdateIndexRelation() and mark_index_clustered(). The issue is:
> can table be clustered on several indexes now? Because GIN is always 'clustered'
> table can be clustered on several GIN index and one any other. Cluster command
> on GIN index should do nothing. May be, it will be cleaner to add indclustered
> column to pg_am.

Here I think it would be best to add an indclusterable column to pg_am.
Actually, does clustering on *any* current index type except btree make
sense? None of them have semantically interesting index ordering
AFAIR, so maybe we should just reject CLUSTER on all of 'em not only GIN.

regards, tom lane

On Fri, Apr 28, 2006 at 10:14:09AM -0400, Tom Lane wrote:
> Here I think it would be best to add an indclusterable column to pg_am.
> Actually, does clustering on *any* current index type except btree make
> sense? None of them have semantically interesting index ordering
> AFAIR, so maybe we should just reject CLUSTER on all of 'em not only GIN.

It seems to me that amorderstrategy already handles this? It's
documented as:

zero if the index offers no sort order, otherwise the strategy number
of the strategy operator that describes the sort order

ergo, if this is non-zero, CLUSTER uses that to sort, otherwise CLUSTER
is forbidden.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.

> We could probably fix that by adding it to the stats structs that are
> passed around during VACUUM. I'd rather not hardwire a GIN special case
> in vacuum.c as per your "quick hack".

ok. amskipcheck?

> Here I think it would be best to add an indclusterable column to pg_am.
GIN is _always_ clustered, it returns pointers to heap in ascending order.

> Actually, does clustering on *any* current index type except btree make
> sense? None of them have semantically interesting index ordering
I don't know about hash index, but for GiST clustering can speed up query's
execution.

As I understand your point, cluster on btree very useful on range searches (
BETWEEN clause ), but don't significantly speeds up queries with OR ( id=1 or
id=500000 or id=6000000 ). Several GiST's opclasses has similar behaviour:
* ltree with queries to search descendant of node. ltree uses B-tree like
structure
* R-tree - contains operation

In any case, clustering can prevent from chaotic seeks on disk.

So, two columns about clustering?
amclustered
amclusterable

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> We could probably fix that by adding it to the stats structs that are
>> passed around during VACUUM. I'd rather not hardwire a GIN special case
>> in vacuum.c as per your "quick hack".

> ok. amskipcheck?

Oh, I was thinking of having VACUUM put the heap tuple count into the
struct and then amvacuumcleanup could copy it over to the index tuple
count. A "skipcheck" flag only solves the cosmetic problem of not
getting the warning, it doesn't fix things so that the correct count
ends up in the index's reltuples entry.

>> Actually, does clustering on *any* current index type except btree make
>> sense? None of them have semantically interesting index ordering

> I don't know about hash index, but for GiST clustering can speed up query's
> execution.

OK, in that case we'd better add a real amclusterable flag to pg_am,
rather than assuming amorderstrategy can be used to decide.

> So, two columns about clustering?
> amclustered
> amclusterable

Huh? Why two? Either you are allowed to cluster on indexes of this
type, or you're not. I don't see the point of any other distinction.

regards, tom lane

>> ok. amskipcheck?
>
> Oh, I was thinking of having VACUUM put the heap tuple count into the
> struct and then amvacuumcleanup could copy it over to the index tuple
> count. A "skipcheck" flag only solves the cosmetic problem of not
> getting the warning, it doesn't fix things so that the correct count
> ends up in the index's reltuples entry.

Yes, it is. So for cosmetic purpose I suggested just a quick hack until we have
good solution.

Both ways, counting pointer and getting number from heap, are not good because of:
* counting pointers - it's not what planner is waiting
* getting number from heap - problems with null values and partial indexes.
And it will be done only pass check...

As you say, the best way is a fair count during vacuum, but for this
ginbulkdelete should collect in memory all pointers, uniques and counts it. But
how much memory it will takes for big tables? At least sizeof(ItemPointerData) *
number of tuples

Using non-exact calculation we may count approximate number of heap's tuples by
finding the greatest heap's blocknumber from pointers stored in index and
multiply it by density of tuples ( average number of heap's tuple on one heap's
page )... But in this case we should skip check too.

> OK, in that case we'd better add a real amclusterable flag to pg_am,
> rather than assuming amorderstrategy can be used to decide.
>
>> So, two columns about clustering?
>> amclustered
>> amclusterable
>
> Huh? Why two? Either you are allowed to cluster on indexes of this
> type, or you're not. I don't see the point of any other distinction.

amclusterable - as you suggest: Does cluster command something or not?
amclustered - table on such index is always clustered, cluster command does
nothing, but optimizer/planner takes clustering into
consideration for query planning.

We can use only amclustered, but in this case we can't forbid to cluster table
on any index. Just current situation.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> Huh? Why two? Either you are allowed to cluster on indexes of this
>> type, or you're not. I don't see the point of any other distinction.

> amclusterable - as you suggest: Does cluster command something or not?

This is what we need.

> amclustered - table on such index is always clustered, cluster command does
> nothing, but optimizer/planner takes clustering into
> consideration for query planning.

"Takes clustering into account" means nothing. We don't need that. Any
such consideration would be handled by the AM-specific amcostestimate
function.

regards, tom lane

> "Takes clustering into account" means nothing. We don't need that. Any
> such consideration would be handled by the AM-specific amcostestimate
> function.

Ok, I see. Sorry for misunderstanding. I thought that planner use that.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/