@@ match operator in PostgreSQL - Time & Space Complexity

Time Complexity: @@ match operator

O(n)

Understanding Time Complexity

We want to understand how the time it takes to search text using the @@ match operator changes as the amount of data grows.

How does the search time increase when we have more text to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM documents
WHERE content_vector @@ to_tsquery('search & term');
    

This query finds all rows in the documents table where the content_vector matches the search terms using full-text search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the search condition against each document's text vector.
• How many times: Once per document row, but optimized by an index if available.

How Execution Grows With Input

As the number of documents grows, the search checks more entries, but indexes help keep it efficient.

Input Size (n)	Approx. Operations
10	About 10 checks, quickly filtered by index
100	About 100 checks, still fast with index
1000	About 1000 checks, index keeps search efficient

Pattern observation: The search time grows roughly in proportion to the number of matching entries, but indexes prevent a full scan, keeping it close to linear or better.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows roughly in proportion to the number of documents, but indexes help keep it efficient.

Common Mistake

[X] Wrong: "The @@ operator always searches instantly no matter how much data there is."

[OK] Correct: Without an index, the search must check every document, which takes longer as data grows.

Interview Connect

Understanding how text search scales helps you explain how databases handle large amounts of text efficiently, a useful skill in many real projects.

Self-Check

"What if we removed the index on content_vector? How would the time complexity change?"