28 GIN

28.1 Overview

According to its authors, GIN stands for a potent and undaunted spirit, not for an alcoholic beverage.¹ But there is also a formal interpretation: this acronym is expanded as Generalized Inverted Index.

The GIN access method is designed for data types representing non-atomic values made up of separate elements (for example, documents consist of lexemes in the context of full-text search). Unlike GiST, which indexes values as a whole, GIN indexes only their elements; each element is mapped to all the values that contain it.

We can compare this method to a book’s index, which comprises all the important terms and lists all the pages where these terms are mentioned. To be convenient to use, it must be compiled in alphabetical order, otherwise it would be impossible to navigate through quickly. In a similar way, GIN relies on the fact that all elements of compound values can be sorted; its main data structure is B-tree. (p. 421)

The implementation of the GIN tree of elements is less complex than that of a regular B-tree: it has been designed to contain rather small sets of elements repeated multiple times.

This assumption leads to two important conclusions:

• An element must be stored in an index only once.

Each element is mapped to a list of TIDs, which is called a posting list. If this list is rather short, it is stored together with the element; longer lists are moved into a separate posting tree, which is actually a B-tree. Just like element trees, posting lists are sorted; it does not matter much from the user’s perspective but helps to speed up data access and reduce index size.

• There is no point in removing elements from a tree.

Even if the list of TIDs for a particular element is empty, the same element is likely to appear again as part of some other value.

Thus, an index is a tree of elements whose leaf entries are bound to either flat lists or trees of TIDs.

Just like GiST and SP-GiST access methods, GIN can be used to index a whole variety of data types via a simplified interface of operator classes. Operators of such classes usually check whether the indexed composite value matches a particular set of elements (just like the @@ operator checks whether a document satisfies a full-text search query).

To index a particular data type, the GIN method must be able to split composite values into elements, sort these elements, and check whether the found value satisfies the query. These operations are implemented by support functions of the operator class.

28.2 Index for Full-Text Search

GIN is mainly applied to speed up full-text search, so I will go on with the example used to illustrate GiST indexing. As you can guess, compound values in this case are documents, while elements of these values are lexemes. (p. 463)

Let’s build a GIN index on the “Old MacDonald” table: (p. 463)

=> CREATE INDEX ts_gin_idx ON ts USING gin(doc_tsv);

A possible structure of this index is shown below. Unlike in the previous illustrations, here I provide actual TID values (shown with a grey background), as they are important for understanding the algorithms. These values suggest that heap tuples have the following IDs:

=> SELECT ctid, * FROM ts;
  ctid |                doc                 |            doc_tsv
-------+------------------------------------+--------------------------------
 (0,1) | Old MacDonald had a farm           | 'farm':5 'macdonald':2 'old':1
 (0,2) | And on his farm he had some cows   | 'cow':8 'farm':4
 (0,3) | Here a moo, there a moo            | 'moo':3,6
 (0,4) | Everywhere a moo moo               | 'everywher':1 'moo':3,4
 (1,1) | Old MacDonald had a farm           | 'farm':5 'macdonald':2 'old':1
 (1,2) | And on his farm he had some chicks | 'chick':8 'farm':4
 (1,3) | Here a cluck, there a cluck        | 'cluck':3,6
 (1,4) | Everywhere a cluck cluck           | 'cluck':3,4 'everywher':1
 (2,1) | Old MacDonald had a farm           | 'farm':5 'macdonald':2 'old':1
 (2,2) | And on his farm he had some pigs   | 'farm':4 'pig':8
 (2,3) | Here an oink, there an oink        | 'oink':3,6
 (2,4) | Everywhere an oink oink            | 'everywher':1 'oink':3,4
(12 rows)

Note some differences from a regular B-tree index here. The leftmost keys in inner B-tree nodes are empty, as they are actually redundant; in a GIN index, they are not stored at all. For this reason, references to child nodes are shifted too. The high key is used in both indexes, but in GIN it takes its legitimate rightmost position. Same-level nodes in a B-tree are bound into a bidirectional list; GIN uses a unidirectional list, since the tree is always traversed in only one direction. (p. 426)

In this theoretical example, all posting lists fit regular pages, except the one for the “farm” lexeme. This lexeme occurred in as many as six documents, so its IDs were moved into a separate posting tree.

Page Layout

GIN page layout is very similar to that of a B-tree. We can peek into an index using the pageinspect extension. Let’s create a GIN index on the table that stores emails of the pgsql-hackers mailing list: (p. 468)

=> CREATE INDEX mail_gin_idx ON mail_messages USING gin(tsv);

The zero page (the metapage) contains the basic statistics, such as the number of elements and pages of other types:

=> SELECT *
FROM gin_metapage_info(get_raw_page('mail_gin_idx',0)) \gx
-[ RECORD 1 ]----+-----------
pending_head     | 4294967295
pending_tail     | 4294967295
tail_free_size   | 0
n_pending_pages  | 0
n_pending_tuples | 0
n_total_pages    | 22957
n_entry_pages    | 13522
n_data_pages     | 9434
n_entries        | 999109
version          | 2

GIN uses the special space of index pages; for example, this space stores the bits that define the page type: (p. 63)

=> SELECT flags, count(*)
FROM generate_series(0,22956) AS p, -- n_total_pages
  gin_page_opaque_info(get_raw_page('mail_gin_idx',p))
GROUP BY flags
ORDER BY 2;
         flags          | count
------------------------+-------
 {meta}                 |     1
 {}                     |   137
 {data}                 |  1525
 {data,leaf,compressed} |  7909
 {leaf}                 | 13385
(5 rows)

The page with the meta attribute is of course the metapage. Pages with the data attribute belong to posting lists, while pages without this attribute are related to element trees. Leaf pages have the leaf attribute.

In the next example, another pageinspect function returns the information on TIDs that are stored in trees’ leaf pages. Each entry of such a tree is virtually a small list of TIDs rather than a single TID:

=> SELECT left(tids::text,60)||'...' tids
FROM gin_leafpage_items(get_raw_page('mail_gin_idx',24));
                              tids
-----------------------------------------------------------------
 {"(4771,4)","(4775,2)","(4775,5)","(4777,4)","(4779,1)","(47...
 {"(5004,2)","(5011,2)","(5013,1)","(5013,2)","(5013,3)","(50...
 {"(5435,6)","(5438,3)","(5439,3)","(5439,4)","(5439,5)","(54...
 ...
 {"(9789,4)","(9791,6)","(9792,4)","(9794,4)","(9794,5)","(97...
 {"(9937,4)","(9937,6)","(9938,4)","(9939,1)","(9939,5)","(99...
 {"(10116,5)","(10118,1)","(10118,4)","(10119,2)","(10121,2)"...
(27 rows)

Posting lists are ordered, which allows them to be compressed (hence the same-name attribute). Instead of a six-byte TID, they store its difference with the previous value, which is represented by a variable number of bytes:² the smaller this difference, the less space the data takes.

Operator Class

Here is the list of support functions for GIN operator classes:³

=> SELECT amprocnum, amproc::regproc
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amproc amop ON amprocfamily = opcfamily
WHERE amname = 'gin'
AND opcname = 'tsvector_ops'
ORDER BY amprocnum;
 amprocnum |              amproc
-----------+-----------------------------------
         1 | gin_cmp_tslexeme
         2 | pg_catalog.gin_extract_tsvector
         3 | pg_catalog.gin_extract_tsquery
         4 | pg_catalog.gin_tsquery_consistent
         5 | gin_cmp_prefix
         6 | gin_tsquery_triconsistent
(6 rows)

The first support function compares two elements (two lexemes in this case). If the lexemes were represented by a regular SQL type supported by B-tree, GIN would automatically use comparison operators defined in the B-tree operator class.

The fifth (optional) function is used in partial search to check whether an index element partially matches the search key. In this particular case, partial search consists in searching lexemes by a prefix. For example, the query “c:*” corresponds to all lexemes starting with letter “c.”

The second function extracts lexemes from the document, while the third one extracts lexemes from the search query. The use of different functions is justified because, at the very least, the document and the query are represented by different data types, namely tsvector and tsquery. Besides, the function for the search query determines how the search will be performed. If the query requires the document to contain a particular lexeme, the search will be limited to the documents that contain at least one lexeme specified in the query. If there is no such condition (for example, if you need documents that do not contain a particular lexeme), all the documents have to be scanned—which is of course much more expensive. (v. 13)

The fourth and sixth functions are consistency functions, which determine whether the found document satisfies the search query. As input, the fourth function gets the exact information on which lexemes specified in the query appear in the document. The sixth function operates in the context of uncertainty and can be called when it is not yet clear whether some of the lexemes are present in the document or not. An operator class does not have to implement both functions: it is enough to provide only one of them, but search efficiency may suffer in this case.

The tsvector_ops operator class supports only one operator that matches the document against the search query: @@,⁴ which is also included into the GiST operator class.

Search

Let’s take a look at the search algorithm for the “everywhere | oink” query, where two lexemes are connected by the OR operator. First, a support function⁵ extracts lexemes “everywher” and “oink” (search keys) from the search string of the tsquery type.

Since the query demands particular lexemes to be present, TIDs of the documents that contain at least one key specified in the query are bound into a list. For this purpose, the TIDs that correspond to each search key are searched in the tree of lexemes and are added into a common list. All the TIDs stored in an index are ordered, which allows merging several sorted streams of TIDs into one.⁶ (p. 387)

Note that at this point it does not matter yet whether the keys were combined by AND, OR, or any other operator: the search engine deals with the list of keys and knows nothing about the search query semantics.

Each found TID that corresponds to a document is checked by the consistency function.⁷ It is this function that interprets the search query and leaves only those TIDs that satisfy the query (or at least may satisfy it and have to be rechecked by the table).

In this particular case, the consistency function leaves all the TIDs:

Instead of a regular lexeme, search queries can contain a prefix. It is useful if an application user can enter the first letters of a word into the search field, expecting to get the results right away. For example, the “pig:*” query will match all the documents that contain lexemes starting with “pig”: here we get “pigs,” and we would also get “pigeons” if old MacDonald had bred them on his farm.

Such partial search matches indexed lexemes against the search key using a special support function;⁸ in addition to prefix matching, this function can also implement other logic for partial search.

Frequent and Rare Lexemes

If searched lexemes occur in a document multiple times, the created list of TIDs will turn out long, which is of course inefficient. Fortunately, it can often be avoided if the query also contains some rare lexemes.

Let’s consider the “farm & cluck” query. The “cluck” lexeme occurs two times, while the “farm” lexeme appears six times. Instead of treating both lexemes equally and building the full list of TIDs by them, the rare “cluck” lexeme is considered mandatory, while the more frequent “farm” lexeme is treated as optional, as it is clear that (taking the query semantics into account) a document with the “farm” lexeme can satisfy the query only if it contains the “cluck” lexeme too.

Thus, an index scan determines the first document that contains “cluck”; its TID is (1,3). Then we have to find out whether this document also contains the “farm” lexeme, but all the documents whose TIDs are smaller than (1,3) can be skipped. Since frequent lexemes are likely to correspond to many TIDs, chances are high that they are stored in a separate tree, so some pages can be skipped as well. In this particular case, the search in the tree of “farm” lexemes starts with (1,3).

This procedure is repeated for the subsequent values of the mandatory lexeme.

Clearly, this optimization can also be applied to more complex search scenarios that involve more than two lexemes. The algorithm sorts the lexemes in the order of their frequency, adds them one by one to the list of mandatory lexemes, and stops when the remaining lexemes are no longer able to guarantee that the document satisfies the query.⁹

For example, let’s consider the query “farm & ( cluck | chick )”. The least frequent lexeme is “chick”; it is added to the list of mandatory lexemes right away. To check whether other lexemes can be considered optional, the consistency function takes false for the mandatory lexeme and true for all the other lexemes. It returns true AND (true OR false) = true, which means that the remaining lexemes are “self-sufficient,” and at least one of them must become mandatory.

The next least frequent lexeme (“cluck”) is added into the list, and now the consistency function returns true AND (false OR false) = false. Thus, “chick” and “cluck” lexemes become mandatory, while “farm” remains optional.

The length of the posting list is three, as the mandatory lexemes have occurred three times:

Thus, if lexeme frequencies are known, it is possible to merge trees of lexemes in the most efficient way, starting from rare lexemes and skipping those page ranges of frequent lexemes that are sure to be redundant. It reduces the number of times the consistency function has to be called. (p. 283)

To make sure that this optimization really works, let’s query the pgsql-hackers archive. We will need to specify two lexemes, a common and a rare one: (p. 468)

=> SELECT word, ndoc
FROM ts_stat('SELECT tsv FROM mail_messages')
WHERE word IN ('wrote', 'tattoo');
  word  |  ndoc
--------+--------
 wrote  | 231173
 tattoo |      2
(2 rows)

It turns out that a document that contains them both does exist:

=> \timing on
=> SELECT count(*) FROM mail_messages
WHERE tsv @@ to_tsquery('wrote & tattoo');
 count
-------
     1
(1 row)
Time: 0,631 ms

This query is performed almost just as fast as the search for a single word “tattoo”:

=> SELECT count(*) FROM mail_messages
WHERE tsv @@ to_tsquery('tattoo');
 count
-------
     2
(1 row)
Time: 2,227 ms

But if we were looking for a single word “wrote,” the search would take much longer:

=> SELECT count(*) FROM mail_messages
WHERE tsv @@ to_tsquery('wrote');

 count
--------
 231173
(1 row)
Time: 343,556 ms
=> \timing off

Insertions

A GIN index cannot contain duplicates;¹⁰ if an element to be added is already present in the index, its TID is simply added to the posting list or tree of an already existing element.

A posting list is a part of an index entry that cannot take too much space in a page, so if the allotted space is exceeded, the list is transformed into a tree.¹¹

When a new element (or a new TID) is being added into a tree, a page overflow can occur; in this case, the page is split into two, and the elements are redistributed between them.¹²

But each document typically contains many lexemes that have to be indexed. So even if we create or modify just one document, the index tree still undergoes a lot of modifications. That is why GIN updates are rather slow.

The illustration below shows the state of the tree after the row “Everywhere clucks, moos, and oinks” with TID (4,1) was inserted into the table. The posting lists of lexemes “cluck,” “moo,” and “oink” were extended; the list of the “everywher” lexeme exceeded the maximal size and was split off as a separate tree.

However, if an index gets updated to incorporate changes related to several documents at once, the total amount of work is likely to be reduced as compared to consecutive changes, as these documents may contain some common lexemes.

This optimization is controlled by the fastupdate storage parameter. Deferred index updates are accumulated in an unordered pending list, which is physically stored in separate list pages outside the element tree. When this list becomes big enough, all its contents is transferred into the index in one go, and the list is cleared.¹³ The maximal size of the list is defined either by the gin_pending_list_limit parameter or by the same-name index storage parameter. (default: on) (p. 233) (default: 4MB)

By default, such deferred updates are enabled, but you should keep in mind that they slow down search: apart from the tree itself, the whole unordered list of lexemes has to be scanned. Besides, insertion time becomes less predictable, as any change can lead to an overflow that incurs an expensive merge procedure. The latter is partially smoothed by the fact that the merge can be also performed asynchronously during index vacuuming.

When a new index is created,¹⁴ the elements also get added in batches rather than one by one, which would be too slow. Instead of being saved into an unordered list on disk, all the changes are accumulated in a maintenance_work_mem memory chunk and get transferred into an index once this chunk has no more free space. The more memory is allocated for this operation, the faster the index is built. (default: 64MB)

The examples provided in this chapter prove GIN superiority over GiST signature trees when it comes to search precision. For this reason, it is GIN that is typically used for full-text search. However, the problem of slow GIN updates may tip the scale in favor of GiST if the data is being actively updated. (p. 463)

Limiting Result Set Size

The GIN access method always returns the result as a bitmap; it is impossible to get TIDs one by one. In other words, the BITMAP SCAN property is supported, but the INDEX SCAN property is not. (p. 326)

The reason for this limitation is the unordered list of deferred updates. In the case of an index access, this list is scanned to build a bitmap, and then this bitmap is updated with the data of the tree. If the unordered list gets merged with the tree (as the result of an index update or during vacuuming) while search is in progress, the same value can be returned twice, which is unacceptable. But in the case of a bitmap it does not pose any problems: the same bit will simply be set twice.

Consequently, using the LIMIT clause with a GIN index is not quite efficient, as the bitmap still has to be built in full, which contributes a fair share to the total cost:

=> EXPLAIN SELECT * FROM mail_messages
WHERE tsv @@ to_tsquery('hacker')
LIMIT 1000;
                        QUERY PLAN
-----------------------------------------------------------
 Limit  (cost=481.41..1964.22 rows=1000 width=1258)
   -> Bitmap Heap Scan on mail_messages
       (cost=481.41..74939.28 rows=50214 width=1258)
       Recheck Cond: (tsv @@ to_tsquery('hacker'::text))
       -> Bitmap Index Scan on mail_gin_idx
           (cost=0.00..468.85 rows=50214 width=0)
           Index Cond: (tsv @@ to_tsquery('hacker'::text))
(7 rows)

Therefore, the GIN method offers a special feature that limits the number of results returned by an index scan. This limit is imposed by the gin_fuzzy_search_limit parameter, which is turned off by default. If this parameter is enabled, the index access method will randomly skip some values to get roughly the specified number of rows (hence the name “fuzzy”):¹⁵ (default: 0)

=> SET gin_fuzzy_search_limit = 1000;
=> SELECT count(*)
FROM mail_messages
WHERE tsv @@ to_tsquery('hacker');
 count
-------
   727
(1 row)
=> SELECT count(*)
FROM mail_messages
WHERE tsv @@ to_tsquery('hacker');
 count
-------
   791
(1 row)
=> RESET gin_fuzzy_search_limit;

Note that there are no LIMIT clauses in these queries. It is the only legitimate way to get different data when using an index scan and a heap scan. The planner knows nothing about such behavior of GIN indexes and does not take this parameter value into account when estimating the cost.

Properties

All the properties of the gin access method are the same at all levels; they do not depend on a particular operator class.

Access Method Properties

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'gin';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 gin    | can_order     | f
 gin    | can_unique    | f
 gin    | can_multi_col | t
 gin    | can_exclude   | f
 gin    | can_include   | f
(5 rows)

GIN supports neither sorting nor unique constraints.

Multicolumn indexes are supported, but it is worth mentioning that the order of their columns is irrelevant. Unlike a regular B-tree, a multicolumn GIN index does not store composite keys; instead, it extends separate elements with the corresponding column number.

Exclusion constraints cannot be supported because the INDEX SCAN property is unavailable.

GIN does not support additional INCLUDE columns. Such columns simply do not make much sense here, as it is hardly possible to use a GIN index as covering: it contains only separate elements of an index value, while the value itself is stored in the table.

Index-Level Properties

=>  SELECT p.name, pg_index_has_property('mail_gin_idx', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | f
 bitmap_scan   | t
 backward_scan | f
(4 rows)

Fetching results one by one is not supported: the index access always returns a bitmap.

For the same reason, it makes no sense to reorder tables by a GIN index: the bitmap always corresponds to the physical layout of data in a table, whichever it is.

Backward scanning is not supported: this feature is useful for regular index scans, not for bitmap scans.

Column-Level Properties

=> SELECT p.name,
  pg_index_column_has_property('mail_gin_idx', 1, p.name)
FROM unnest(array[
  'orderable', 'search_array', 'search_nulls',
  'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 orderable          | f
 search_array       | f
 search_nulls       | f
 returnable         | f
 distance_orderable | f
(5 rows)

None of the column-level properties are available: neither sorting (for obvious reasons) nor using the index as covering (since the document itself is not stored in the index). NULL support is not available either (it does not make sense for elements of non-atomic types).

GIN Limitations and RUM Index

Potent as it is, GIN still cannot address all the challenges of full-text search. Although the tsvector type does indicate positions of lexemes, this information does not make it into an index. Therefore, GIN cannot be used to speed up phrase search, which takes lexeme proximity into account. Moreover, search engines usually return results by relevance (whatever this term might mean), and since GIN does not support ordering operators, the only solution here would be computing the ranking function for each resulting row, which is of course very slow.

These drawbacks have been addressed by the RUM access method (whose name makes us doubt developers’sincerity when it comes to the true meaning of GIN). This access method is provided as an extension; you can either download the corresponding package from the PGDG repository¹⁶ or get the source code itself.¹⁷

RUM is based on GIN, but they have two major differences. First, RUM does not provide deferred updates, so it supports regular index scans in addition to bitmap scans and implements ordering operators. Second, RUM index keys can be extended with additional information. This feature resembles INCLUDE columns to some extent, but here additional information is bound to a particular key. In the context of full-text search, RUM operator class maps lexeme occurrences to their positions in the document, which speeds up phrase search and result ranking.

The downsides of this approach are slow updates and larger index sizes. Besides, since the rum access method is provided as an extension, it relies on the generic WAL mechanism,¹⁸ which is slower than the built-in logging and generates bigger volumes of WAL.

28.3 Trigrams

The pg_trgm¹⁹ extension can assess word similarity by comparing the number of coinciding three-letter sequences (trigrams). Word similarity can be used alongside full-text search to return some results even if the words to search for have been entered with typos.

The gin_trgm_ops operator class implements text string indexing. To single out elements of text values, it extracts various three-letter substrings rather than words or lexemes (only letters and digits are taken into account; other characters are ignored). Within an index, trigrams are represented as integers. Note that for non-Latin characters, which take from two to four bytes in the UTF-8 encoding, such representation does not allow decoding the original symbols.

=> CREATE EXTENSION pg_trgm;
=> SELECT unnest(show_trgm('macdonald')),
          unnest(show_trgm('McDonald'));
 unnest | unnest
--------+--------
   m    |   m
  ma    |  mc
 acd    | ald
 ald    | cdo
 cdo    | don
 don    | ld
 ld     | mcd
 mac    | nal
 nal    | ona
 ona    |
(10 rows)

This class supports operators for both precise and fuzzy comparison of strings and words.

=> SELECT amopopr::regoperator, oprcode::regproc
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gin'
AND opcname = 'gin_trgm_ops'
ORDER BY amopstrategy;
    amopopr     |               oprcode
----------------+--------------------------------------
 %(text,text)   | similarity_op
 ~~(text,text)  | textlike

LIKE and ILIKE

~~*(text,text) | texticlike
~(text,text)   | textregexeq

regular expressions

 ~*(text,text)  | texticregexeq
 %>(text,text)  | word_similarity_commutator_op
 %>>(text,text) | strict_word_similarity_commutator_op
 =(text,text)   | texteq
(8 rows)

To perform fuzzy comparison, we can define the distance between strings as a ratio of common trigrams to the total number of trigrams in the query string. But as I have already shown, GIN does not support ordering operators, so all operators in the class must be Boolean. Therefore, for %, %>, and %>> operators that implement strategies of fuzzy comparison, the consistency function returns true if the computed distance does not exceed the defined threshold.

For = and LIKE operators, the consistency function demands that the value contains all the trigrams of the query string. Matching a document against a regular expression requires a much more complex check.

In any case, trigram search is always fuzzy, and the results have to be rechecked.

28.4 Indexing Arrays

The array data type is also supported by GIN. Built over array elements, a GIN index can be used to quickly determine whether an array overlaps with or is contained in another array:

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gin'
AND opcname = 'array_ops'
ORDER BY amopstrategy;
        amopopr        |    oprcode     | amopstrategy
-----------------------+----------------+--------------
 &&(anyarray,anyarray) | arrayoverlap   |            1
 @>(anyarray,anyarray) | arraycontains  |            2
 <@(anyarray,anyarray) | arraycontained |            3
 =(anyarray,anyarray)  | array_eq       |            4
(4 rows)

As an example, let’s take the routes view of the demo database that shows the information on flights. The days_of_week column is an array of days of the week on which flights are performed. To build an index, we first have to materialize the view:

=> CREATE TABLE routes_tbl AS
SELECT * FROM routes;
SELECT 710
=> CREATE INDEX ON routes_tbl USING gin(days_of_week);

Let’s use the created index to select the flights that depart on Tuesdays, Thursdays, and Sundays. I turn off sequential scanning; otherwise, the planner would not use the index for such a small table:

=> SET enable_seqscan = off;
=> EXPLAIN (costs off)
SELECT *
FROM routes_tbl
WHERE days_of_week = ARRAY[2,4,7];
                       QUERY PLAN
---------------------------------------------------------
 Bitmap Heap Scan on routes_tbl
   Recheck Cond: (days_of_week = '{2,4,7}'::integer[])
   -> Bitmap Index Scan on routes_tbl_days_of_week_idx
       Index Cond: (days_of_week = '{2,4,7}'::integer[])
(4 rows)

It turns out that there are eleven such flights:

=> SELECT flight_no, departure_airport, arrival_airport, days_of_week
FROM routes_tbl
WHERE days_of_week = ARRAY[2,4,7];
 flight_no | departure_airport | arrival_airport | days_of_week
-----------+-------------------+-----------------+--------------
 PG0023    | OSW               | KRO             | {2,4,7}
 PG0123    | NBC               | ROV             | {2,4,7}
 PG0155    | ARH               | TJM             | {2,4,7}
 PG0260    | STW               | CEK             | {2,4,7}
 PG0261    | SVO               | GDZ             | {2,4,7}
 PG0310    | UUD               | NYM             | {2,4,7}
 PG0370    | DME               | KRO             | {2,4,7}
 PG0371    | KRO               | DME             | {2,4,7}
 PG0448    | VKO               | STW             | {2,4,7}
 PG0482    | DME               | KEJ             | {2,4,7}
 PG0651    | UIK               | KHV             | {2,4,7}
(11 rows)

The built index contains only seven elements: integer numbers from 1 to 7 that represent days of the week.

The query execution is quite similar to what I have shown before for the full-text search. In this particular case, the search query is represented by a regular array rather than by a special data type; it is assumed that the indexed array must contain all the specified elements. An important distinction here is that the equality condition also requires the indexed array to contain no other elements. The consistency function²⁰ knows about this requirement thanks to the strategy number, but it cannot verify that there are no unwanted elements, so it requests the indexing engine to recheck the results by the table:

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM routes_tbl
WHERE days_of_week = ARRAY[2,4,7];
                             QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on routes_tbl (actual rows=11 loops=1)
   Recheck Cond: (days_of_week = '{2,4,7}'::integer[])
   Rows Removed by Index Recheck: 482
   Heap Blocks: exact=16
   -> Bitmap Index Scan on routes_tbl_days_of_week_idx (actual ro...
       Index Cond: (days_of_week = '{2,4,7}'::integer[])
(6 rows)

It may be useful to extend the GIN index with additional columns. For example, to enable search for the flights that depart on Tuesdays, Thursdays, and Sundays from Moscow, the index lacks the departure_city column. But there are no operator classes implemented for regular scalar data types:

=> CREATE INDEX ON routes_tbl USING gin(days_of_week, departure_city);
ERROR:  data type text has no default operator class for access
method "gin"
HINT:  You must specify an operator class for the index or define a
default operator class for the data type.

Such situations can be addressed by the btree_gin extension. It adds GIN operator classes that simulate regular B-tree processing by representing a scalar value as a composite value with a single element. (p. 459)

=> CREATE EXTENSION btree_gin;
=> CREATE INDEX ON routes_tbl USING gin(days_of_week,departure_city);
=> EXPLAIN (costs off)
SELECT * FROM routes_tbl
WHERE days_of_week = ARRAY[2,4,7]
AND departure_city = 'Moscow';
                             QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on routes_tbl
   Recheck Cond: ((days_of_week = '{2,4,7}'::integer[]) AND
   (departure_city = 'Moscow'::text))
   -> Bitmap Index Scan on routes_tbl_days_of_week_departure_city...
       Index Cond: ((days_of_week = '{2,4,7}'::integer[]) AND
       (departure_city = 'Moscow'::text))
(6 rows)
=> RESET enable_seqscan;

The remark made about btree_gist holds true for btree_gin as well: a B-tree is much more efficient when it comes to comparison operations, so it makes sense to use the btree_gin extension only when a GIN index is really needed. For instance, a search by less than or less than or equal to conditions can be performed by a backward scan in a B-tree, but not in GIN.

28.5 Indexing JSON

One more non-atomic data type with built-in GIN support is jsonb.²¹ It offers a whole range of operators for JSON, and some of them can perform faster using GIN.

There are two operator classes that extract different sets of elements from a JSON document:

=> SELECT opcname
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
WHERE amname = 'gin'
AND opcintype = 'jsonb'::regtype;
    opcname
----------------
 jsonb_ops
 jsonb_path_ops
(2 rows)

jsonb_ops Operator Class

The jsonb_ops operator class is the default one. All the keys, values, and array elements of the original JSON document are converted into index entries.²² It speeds up queries that check for inclusion of JSON values (@>), existence of keys (?, ?|, and ?&), or JSON path matches (@? and @@):

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gin'
AND opcname = 'jsonb_ops'
ORDER BY amopstrategy;
      amopopr       |        oprcode        | amopstrategy
--------------------+-----------------------+--------------
 @>(jsonb,jsonb)    | jsonb_contains        |            7
 ?(jsonb,text)      | jsonb_exists          |            9
 ?|(jsonb,text[])   | jsonb_exists_any      |           10
 ?&(jsonb,text[])   | jsonb_exists_all      |           11
 @?(jsonb,jsonpath) | jsonb_path_exists_opr |           15
 @@(jsonb,jsonpath) | jsonb_path_match_opr  |           16
(6 rows)

Let’s convert several rows of the routes view into the JSON format:

=> CREATE TABLE routes_jsonb AS
SELECT to_jsonb(t) route
FROM (
  SELECT departure_airport_name, arrival_airport_name, days_of_week
  FROM routes
  ORDER BY flight_no
  LIMIT 4
) t;
=> SELECT ctid, jsonb_pretty(route) FROM routes_jsonb;
 ctid  |                         jsonb_pretty
-------+-------------------------------------------------------------
 (0,1) | {                                                            +
       |     "days_of_week": [                                       +
       |         6                                                   +
       |     ],                                                      +
       |     "arrival_airport_name": "Surgut Airport",              +
       |     "departure_airport_name": "Ust-Ilimsk Airport"         +
       | }
 (0,2) | {                                                            +
       |     "days_of_week": [                                       +
       |         7                                                   +
       |     ],                                                      +
       |     "arrival_airport_name": "Ust-Ilimsk Airport",          +
       |     "departure_airport_name": "Surgut Airport"             +
       | }
 (0,3) | {                                                            +
       |     "days_of_week": [                                       +
       |         2,                                                  +
       |         6                                                   +
       |     ],                                                      +
       |     "arrival_airport_name": "Sochi International Airport", +
       |     "departure_airport_name": "Ivanovo South Airport"      +
       | }
 (0,4) | {                                                            +
       |     "days_of_week": [                                       +
       |         3,                                                  +
       |         7                                                   +
       |     ],                                                      +
       |     "arrival_airport_name": "Ivanovo South Airport",       +
       |     "departure_airport_name": "Sochi International Airport"+
       | }
(4 rows)
=> CREATE INDEX ON routes_jsonb USING gin(route);

Let’s consider a query with condition route @> '{"days_of_week": [6]}', which selects JSON documents containing the specified path (that is, the flights performed on Saturdays).

The support function²³ extracts the search keys from the JSON value of the search query: “days_of_week” and “6”. These keys are searched in the element tree, and the documents that contain at least one of them are checked by the consistency function.²⁴ For the contains strategy, this function demands that all the search keys are available, but the results still have to be rechecked by the table: from the point of view of an index, the specified path can also correspond to documents like {"days_of_week": [2],"foo": [6]}.

The created index can be illustrated as follows:

jsonb_path_ops Operator Class

The second class called jsonb_path_ops contains fewer operators:

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gin'
AND opcname = 'jsonb_path_ops'
ORDER BY amopstrategy;
      amopopr       |        oprcode        | amopstrategy
--------------------+-----------------------+--------------
 @>(jsonb,jsonb)    | jsonb_contains        |            7
 @?(jsonb,jsonpath) | jsonb_path_exists_opr |           15
 @@(jsonb,jsonpath) | jsonb_path_match_opr  |           16
(3 rows)

If this class is used, the index will contain paths from the root of the document to all the values and all the array elements rather than isolated JSON fragments.²⁵ It makes the search much more precise and efficient, but there is no speedup for operations with arguments represented by separate keys instead of paths.

As a path can be quite lengthy, it is not paths themselves but their hashes that actually get indexed.

Let’s create an index for the same table using this operator class:

=> CREATE INDEX ON routes_jsonb USING gin(route jsonb_path_ops);

The created index can be represented by the following tree:

When executing a query with the same condition route @> '{"days_of_week": [6]}', the support function²⁶ extracts the whole path “days_of_week, 6” rather than its separate components. The TIDs of the two matching documents will be found in the element tree right away.

Clearly, these entries will be checked by the consistency function²⁷ and then rechecked by the indexing engine (to rule out hash collisions, for example). But the search through the tree is much more efficient, so it makes sense to always choose the jsonb_path_ops class if the index support provided by its operators is sufficient for queries.

28.6 Indexing Other Data Types

GIN support via extensions is also provided for the following data types:

Arrays of integers. The intarray extension adds the gin__int_ops operator class for integer arrays. It is very similar to the standard array_ops operator class, but it supports the match operator @@, which matches a document against a search query.

Key–value storage. The hstore extension implements a storage for key–value pairs and provides the gin_hstore_ops operator class. Both keys and values get indexed.

JSON query language. An external jsquery extension provides its own query language and GIN index support for JSON.

After the SQL:2016 standard was adopted and the SQL/JSON query language was implemented in PostgreSQL, the standard built-in capabilities seem to be a better choice. (v. 12)