liveBook · Manning

Signature collision

As explained in Just Use Postgres!

A signature collision occurs when different lexemes set the same bit positions in a signature-based index.

A signature collision occurs when different lexemes set identical bit positions in a GiST signature. Matching documents may therefore require table-row rechecks to confirm that the queried lexemes are present. section 6.6.2

Practical consequences of signature collisions include:

  • GiST lookups can be slower because matching rows require additional verification. section 6.6.2
  • Increasing the signature size from 124 bytes up to 2,024 bytes can reduce collisions. section 6.6.2

Inspecting a GiST search

CREATE INDEX idx_movie_lexemes_gist ON omdb.movies USING GIST (lexemes); EXPLAIN (analyze, costs off) SELECT id, name FROM omdb.movies WHERE lexemes @@ to_tsquery('historical & fight'); The plan uses an Index Scan and reports 0.395 ms execution time.

How Just Use Postgres! covers it

How deep it goes
Defines collisions, explains their recheck cost, and identifies signature sizing as a mitigation without developing the hashing internals.
Examples
Uses a movie-search GiST index, an EXPLAIN query, and an Index Scan plan with measured execution time.
What it assumes
Assumes familiarity with Postgres full-text search, GiST indexes, GIN indexes, and EXPLAIN output.
What you can do after
Diagnose GiST lookup overhead and configure a larger signature size when collision-related rechecks matter.
How it connects
Connects signature collisions with GiST indexes, GIN indexes, full-text search, and tsvector lexemes.
Cover of Just Use Postgres!
liveBookmanning.com
Read Just Use Postgres! on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Just Use Postgres!. The section links point to the parts of the book it draws on.