Re: Proposal: q-gram GIN and GiST indexes

Currently PostgreSQL has support for trigram-based string collection indexing in pg_trgm module. Indexes in pg_trgm was originally focused on trigram similatiry queries optimization. LIKE/ILIKE operations support was added by my patch, but this support is limited, because trigrams not always can be extracted from wildcard.

I would like to propose a q-gram module which would have following differences in comparison with pg_trgm:

1) Focus on acceleration of edit distance (e.g. levenshtein distance) queries and LIKE/ILIKE queries

2) Support of various q

3) Support of positional q-grams (q-gram which contain position in which it appears in text) in GIN which give a hope to handle edit distance queries better than ordinal q-grams

4) LIKE/ILIKE acceleration even in case when no q-gram can be extracted from wildcard (via partial match)

5) Support of various signature size in GiST

6) Store exact string value in leaf pages of GiST index tree (In spite of set of q-grams, exact string value takes less space and allow exact filtering for LIKE/ILIKE and edit distance filtering)

Additional support of q-gram indexing will consolidate PostgreSQL as most advanced DBMS in fuzzy search on string collections. Q-gram indexes will be applicable for industry tasks. 

Acceleration of edit distance queries and LIKE/ILIKE queries.

Basic idea is so [1]:

1) Extract q-grams which should anyway present in string which conforms to wildcard.

2) Filter only string which contain q-grams extracted on previous step. As the rule, recheck is required.

Currently this approach was impelemented for pg_trgm, but there is following limitation besides fixed q. In some cases we can extract no q-grams from wildcard (for example '%zz%' and q = 3). In GIN we could filter all q-grams which starts from 'zz' using partial match. But it require to store original q-gram in index (in pg_trgm crc32 in stored in the case of multibyte encoding).

Number of common trigrams in strings p and r is at least max{length(p), length(r)} − q + 1 − k*q [2,5]. If p is query string and r is indexed string, we don't know exactly length of r. Then we can use following minimal common q-grams number bound length(p) − q + 1 − k*q. This bound allow us to filter strings using q-gram GIN and GiST indexes. Moreover, when filtering using GIN or GiST index we know about absence in indexing string of particular q-grams. In some cases it should be more effective then minimal bound of common q-grams. For examle, if query string is 'abcdefg' then absence of trigrams 'abc' and 'efg' can ensure us that minimal possible edit distance is 2.

In string to set of q-grams decomposition not only q-gram presence itself but also q-gram position is useful information [3,4,5]. GIN index can store q-gram position as lower part of key. Q-gram position can be-used for edit distance filtering. For example, if we extract q-gram x with position l from query with threshold k, then corresponding q-gram in indexed string should have position in interval [l-k,l+k]. This condition can be used for more effective filtering than with ordinal q-grams.

1) Find a way to give additional parameters to index (value of q and signature size for GiST). If it wouldn't be possible to add extension-specific parameters to GiST and GIN indexes then distinct opclasses can be created for various parameters values;

2) Find a way to represent edit distance query. Edit distance query require two parameters query string and threshold. Threshold is maximum edit distance between result string and query string. Similar problem presents in pg_trgm for trigram similarity query: we need threshold of matchind trigrams amount. In pg_trgm threshold is declared as global session parameter and it can be manipulated by set_limit show_limit. However this approach have some limitation. For example, different thresholds can't be combined in same query. Probably, we should consider using of composite type for edit distance query respresentation.

3) Find appropriate place for proposed functionality: core, contrib module or a separate project. 

1) Produce a solution af architecture questions with help of community.

2) Edit distance operator implementation

3) Implement GIN qgram index

    b) Index building implementation

    c) Edit distance strategy implementation

    d) LIKE/ILIKE strategy implementation

4) Implement GIN pqgram index

    a) Index building implementation

    b) Edit distance strategy implementation

    c) LIKE/ILIKE strategy implementation

5) Implement GiST qgram index

    a) Index building implementation

    b) Edit distance strategy implementation

    c) Edit distance KNN-strategy implementation

    d) LIKE/ILIKE strategy implementation

6) Perfomance testing on real life datasets

7) Manual writing

8) Code cleanup and commiting

until May 22

Solve architecture questins with help of commutiny.

May 23 - May 29

Implement edit distance filter operator and KNN-operator.

May 30 - June 12

Implement GIN q-gram index.

June 13 - June 26

Implement GIN pq-gram index.

June 27 - July 10

Implement GiST q-gram index.

July 11 - July 24

Perform testing on real life data.

July 25 - July 31

Manural writing.

August 1 - August 16

Final code cleanup and commiting.

1) http://nlp.stanford.edu/IR-book/html/htmledition/k-gram-indexes-for-wildcard-queries-1.html

2) Jokinen, P., Ukkonen, E.: Two Algorithms for Approximate String Matching in Static Texts, Proceedings of the 16th Symposium on Mathematical Foundations of Computer Science, number 520 in LNCS, Springer, 1991.

3) Erkki Sutinen and Jorma Tarhio. On using q-gram locations in approximate string matching. Algorithms — ESA '95, p. 327-340

4) Chen Li, Bin Wang, Xiaochun Yang. VGRAM: improving performance of approximate queries on string collections using variable-length grams. VLDB '07 Proceedings of the 33rd international conference on Very large data bases

5) Luis Gravano, Panagiotis G. Ipeirotis, H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Divesh Srivastava. Approximate String Joins in a Database (Almost) for Free. VLDB '01 Proceedings of the 27th International Conference on Very Large Data Bases