GIN index for full-text search in PostgreSQL - Time & Space Complexity

Time Complexity: GIN index for full-text search

O(k + log n)

Understanding Time Complexity

When using a GIN index for full-text search, we want to know how fast the search will be as the data grows.

We ask: How does the search time change when we add more documents or words?

Scenario Under Consideration

Analyze the time complexity of this full-text search query using a GIN index.

CREATE INDEX idx_fts ON documents USING GIN(to_tsvector('english', content));

SELECT * FROM documents
WHERE to_tsvector('english', content) @@ to_tsquery('search & term');
    

This code creates a GIN index on the text content and then searches for documents matching the query.

Identify Repeating Operations

Look at what repeats when searching with a GIN index.

• Primary operation: The index looks up each search term in its internal structure.
• How many times: Once per search term, then combines results.

How Execution Grows With Input

The search time grows mostly with the number of unique terms and the size of the posting lists for those terms.

Input Size (n)	Approx. Operations
10 documents	Few lookups, very fast
1000 documents	More lookups, still quick due to index
100,000 documents	More posting list checks, but still efficient

Pattern observation: The search time grows slowly compared to scanning all documents because the index narrows down candidates quickly.

Final Time Complexity

Time Complexity: O(k + log n)

This means the search time grows with the number of search terms (k) and logarithmically with the number of indexed entries (n).

Common Mistake

[X] Wrong: "Searching with a GIN index is always instant, no matter how big the data is."

[OK] Correct: While GIN indexes speed up search a lot, the time still grows with more terms and larger data, just much slower than scanning everything.

Interview Connect

Understanding how GIN indexes scale helps you explain efficient search in databases, a useful skill for real projects and interviews.

Self-Check

What if we changed the search to use multiple OR terms instead of AND? How would the time complexity change?