tsvector and tsquery types in PostgreSQL - Time & Space Complexity

Time Complexity: tsvector and tsquery types

O(n)

Understanding Time Complexity

We want to understand how the time to search text grows when using tsvector and tsquery types in PostgreSQL.

How does the search time change as the amount of text data increases?

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL full-text search query.

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

This query finds rows where the text content matches the search query using full-text search types.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Checking each document's tsvector against the tsquery.
• How many times: Once per document row scanned.

How Execution Grows With Input

As the number of documents grows, the search checks more tsvectors.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the number of documents to check.

Common Mistake

[X] Wrong: "Full-text search always runs instantly no matter how much data there is."

[OK] Correct: Without indexes, the search must check each document, so time grows with data size.

Interview Connect

Understanding how full-text search scales helps you explain database performance clearly and confidently.

Self-Check

"What if we add a GIN index on the tsvector column? How would the time complexity change?"