Inverted indexes (GIN)

An inverted index turns the table around: instead of row to values, it stores value to rows. PostgreSQL’s GIN (generalized inverted index) pulls keys out of each composite value (array elements, JSON keys and values, text-search lexemes or, with pg_trgm, three-letter pieces of a string) and stores each key once with a posting list of row IDs, or a posting tree when the list grows large. That serves “contains” questions: tags @> ARRAY['red'], attrs @> '{"color": "red"}', tsv @@ query, and name ILIKE '%c4ca42%' through trigrams. On 1 million rows, a jsonb containment query took 18.7 ms with GIN against 162 ms for a sequential scan, and a substring search 0.9 ms against 669 ms.

The price is paid on writes and disk. One row can add many entries, one per key, so by default (fastupdate) GIN puts new entries in an unsorted pending list and merges them in bulk when vacuum runs or the list passes gin_pending_list_limit. Searches must scan that list too, and the insert that overflows it pays for the merge. GIN can’t do index-only scans, because entries hold only parts of values. The trigram index in the example took 114 MB for a 135 MB table; for jsonb, jsonb_path_ops is usually much smaller than the default jsonb_ops but supports fewer operators.

Search engines rest on the same structure. The Lucene library keeps for each term the documents that contain it, with frequencies and positions for ranking; the search concept covers analyzers, ranking and when a separate engine beats an index inside the database.