Ranking with ts_rank in PostgreSQL - Time & Space Complexity

Time Complexity: Ranking with ts_rank

O(n log n)

Understanding Time Complexity

When we rank search results using ts_rank, we want to know how the time to get results changes as the data grows.

We ask: How does the ranking process scale when there are more rows to check?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT id, ts_rank(to_tsvector(content), query) AS rank
FROM documents, (SELECT to_tsquery('search & term') AS query) q
WHERE to_tsvector(content) @@ query
ORDER BY rank DESC
LIMIT 10;
    

This query finds documents matching a search query, ranks them by relevance, and returns the top 10.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating ts_rank for each matching row.
• How many times: Once for every row that matches the search condition.

How Execution Grows With Input

As the number of matching rows grows, the database must calculate ts_rank for each one before sorting.

Input Size (n)	Approx. Operations
10	About 10 rank calculations and sorting
100	About 100 rank calculations and sorting
1000	About 1000 rank calculations and sorting

Pattern observation: The work grows roughly in direct proportion to the number of matching rows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of matching rows because of sorting after ranking.

Common Mistake

[X] Wrong: "Ranking results with ts_rank is always very slow because it checks every row in the table."

[OK] Correct: The query uses an index to find matching rows first, so ts_rank runs only on those matches, not the whole table.

Interview Connect

Understanding how ranking scales helps you explain search query performance clearly and confidently.

Self-Check

What if we removed the LIMIT 10? How would the time complexity change?