Time Complexity: Why full-text search matters
O(n)
0
0
Why full-text search matters in PostgreSQL - Performance Analysis
Understanding Time Complexity
When searching text in a large database, how fast the search runs is very important.
We want to know how the search time changes as the amount of text grows.
Scenario Under Consideration
Analyze the time complexity of the following full-text search query.
SELECT * FROM documents
WHERE to_tsvector('english', content) @@ to_tsquery('english', 'database & search');
This query finds all documents containing words related to "database" and "search" using full-text search.
Identify Repeating Operations
Look for repeated work done by the query.
- Primary operation: Checking each document's text vector against the search query.
- How many times: Once per document in the table.
How Execution Grows With Input
As the number of documents grows, the search work grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The work grows directly with the number of documents.
Final Time Complexity
Time Complexity: O(n)
This means the search time grows in a straight line as more documents are added.
Common Mistake
[X] Wrong: "Full-text search always runs instantly no matter how much data there is."
[OK] Correct: The search still checks many documents, so more data means more work unless indexes are used.
Interview Connect
Understanding how search time grows helps you explain how databases handle big text data efficiently.
Self-Check
"What if we add a full-text index on the content column? How would the time complexity change?"