Signature tree

As explained in Just Use Postgres!

A signature tree is a GiST index structure whose entries summarize text documents with bit-string signatures.

A signature tree is the GiST structure PostgreSQL creates for indexing tsvector lexemes. Each entry summarizes a text document as a bit string. section 6.6.2

Signature construction follows three steps:

• Assign each lexeme a signature with one bit set to 1. section 6.6.2
• Combine the lexeme signatures with bitwise OR to represent a document. section 6.6.2
• Traverse the tree from root pages to leaf entries containing document signatures and table-row references. section 6.6.2

Create and inspect a GiST signature tree

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 reports an Index Scan using idx_movie_lexemes_gist, returning three rows.

Figure 6.2 A sample GiST index highlighting all the index entries visited during a search for documents containing the “histor” lexeme (00000001)

Follow the tree search for the “histor” lexeme from the root through visited index entries. section 6.6.2

How Just Use Postgres! covers it

How deep it goes

Explains signature construction and tree traversal, then stops short of implementation internals beyond index pages and bit strings.

Examples

Demonstrates lexeme signatures, a document signature, a GiST index definition, and an EXPLAIN query plan.

What it assumes

Assumes tsvector lexemes and GiST indexing, while defining signatures and their construction directly.

What you can do after

Operate/configure a GiST index over tsvector lexemes and inspect its use with EXPLAIN.

How it connects

Connects signature trees with GiST indexes, tsvector lexemes, bitwise OR, and full-text queries.

liveBookmanning.com

Read Just Use Postgres! on liveBook Get the book at manning.com

Related concepts

• GiST indexpart of · A GiST index is a PostgreSQL extensible index structure that supports generalized searches over diverse data types and predicates.

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.