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?

Practice

1. What does the ts_rank function do in PostgreSQL full-text search?

easy

A. It creates a search query from a string.

B. It converts text into a searchable vector format.

C. It calculates the relevance ranking of a document for a search query.

D. It sorts rows alphabetically by a text column.

Solution

1. Step 1: Understand the purpose of ts_rank

   The ts_rank function scores how well a document matches a search query in full-text search.

2. Step 2: Differentiate from related functions

   to_tsvector prepares text, to_tsquery creates queries, but ts_rank ranks results.

3. Final Answer:

   It calculates the relevance ranking of a document for a search query. -> Option C

4. Quick Check:

   ts_rank = relevance score [OK]

Hint: Remember ts_rank ranks relevance, not text conversion [OK]

Common Mistakes:

• Confusing ts_rank with to_tsvector
• Thinking ts_rank creates search queries
• Assuming ts_rank sorts alphabetically

2. Which of the following is the correct syntax to rank search results using ts_rank in PostgreSQL?

easy

A. SELECT *, ts_rank(to_tsvector(text_column), to_tsquery('search')) AS rank FROM table ORDER BY rank DESC;

B. SELECT *, ts_rank(text_column, 'search') AS rank FROM table ORDER BY rank ASC;

C. SELECT *, ts_rank(to_tsquery(text_column), to_tsvector('search')) AS rank FROM table;

D. SELECT *, ts_rank('search', text_column) AS rank FROM table ORDER BY rank DESC;

Solution

1. Step 1: Check correct function arguments

   ts_rank requires a tsvector and a tsquery, so to_tsvector(text_column) and to_tsquery('search') are correct.

2. Step 2: Verify ordering and syntax

   Ordering by rank descending shows best matches first, matching SELECT *, ts_rank(to_tsvector(text_column), to_tsquery('search')) AS rank FROM table ORDER BY rank DESC;.

3. Final Answer:

   SELECT *, ts_rank(to_tsvector(text_column), to_tsquery('search')) AS rank FROM table ORDER BY rank DESC; -> Option A

4. Quick Check:

   Correct ts_rank syntax = SELECT *, ts_rank(to_tsvector(text_column), to_tsquery('search')) AS rank FROM table ORDER BY rank DESC; [OK]

Hint: ts_rank needs to_tsvector first, then to_tsquery second [OK]

Common Mistakes:

• Swapping to_tsvector and to_tsquery arguments
• Ordering results ascending instead of descending
• Passing plain text instead of tsvector or tsquery

3. Given the table documents with column content, what will this query return?

SELECT content, ts_rank(to_tsvector(content), to_tsquery('cat & dog')) AS rank FROM documents ORDER BY rank DESC LIMIT 2;

medium

A. The two documents containing either 'cat' or 'dog', sorted alphabetically.

B. The two documents with the highest relevance to both 'cat' and 'dog'.

C. All documents containing 'cat' or 'dog' without ranking.

D. An error because ts_rank cannot be used with LIMIT.

Solution

1. Step 1: Understand the query components

   The query uses to_tsquery('cat & dog') which searches for documents containing both 'cat' and 'dog'.

2. Step 2: Analyze ordering and limit

   Results are ordered by ts_rank descending, so highest relevance first, limited to 2 rows.

3. Final Answer:

   The two documents with the highest relevance to both 'cat' and 'dog'. -> Option B

4. Quick Check:

   ts_rank orders best matches first [OK]

Hint: AND in tsquery means both terms must appear [OK]

Common Mistakes:

• Thinking it returns documents with either word
• Assuming alphabetical order instead of rank
• Believing LIMIT causes an error with ts_rank

4. Identify the error in this query:

SELECT content, ts_rank(to_tsquery(content), to_tsvector('search')) AS rank FROM documents ORDER BY rank DESC;

medium

A. Arguments to ts_rank are reversed; tsvector should be first, tsquery second.

B. to_tsquery cannot be used on a column; it only accepts strings.

C. ORDER BY rank DESC is invalid syntax here.

D. The query is correct and will run without errors.

Solution

1. Step 1: Check ts_rank argument order

   ts_rank expects tsvector first, then tsquery. Here, they are reversed.

2. Step 2: Confirm argument types

   to_tsquery(content) is incorrect because content is text, not a query string; also to_tsvector('search') is a vector, but arguments are swapped.

3. Final Answer:

   Arguments to ts_rank are reversed; tsvector should be first, tsquery second. -> Option A

4. Quick Check:

   ts_rank(tsvector, tsquery) order matters [OK]

Hint: ts_rank always: tsvector first, tsquery second [OK]

Common Mistakes:

• Swapping ts_rank arguments
• Using to_tsquery on text column
• Ignoring argument types for ts_rank

5. You want to find the top 3 most relevant documents containing either 'apple' or 'orange' using high weights to boost relevance. Which query correctly uses ts_rank with weights to achieve this?

hard

A. SELECT content, ts_rank(setweight(to_tsvector(content), 'D'), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank ASC LIMIT 3;

B. SELECT content, ts_rank(to_tsvector(content), to_tsquery('apple & orange')) AS rank FROM documents ORDER BY rank DESC LIMIT 3;

C. SELECT content, ts_rank(to_tsvector(content), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank ASC LIMIT 3;

D. SELECT content, ts_rank(setweight(to_tsvector(content), 'A'), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank DESC LIMIT 3;

Solution

1. Step 1: Understand weighting with setweight

   Using setweight with 'A' assigns highest weight to terms in to_tsvector, boosting the relevance of matching terms.

2. Step 2: Analyze the query logic

   to_tsquery('apple | orange') searches for either word, and ordering by rank descending with LIMIT 3 returns top 3 relevant documents.

3. Step 3: Compare options

   SELECT content, ts_rank(to_tsvector(content), to_tsquery('apple & orange')) AS rank FROM documents ORDER BY rank DESC LIMIT 3; uses AND (&) which requires both words, not either. SELECT content, ts_rank(to_tsvector(content), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank ASC LIMIT 3; orders ascending, showing least relevant first. SELECT content, ts_rank(setweight(to_tsvector(content), 'D'), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank ASC LIMIT 3; uses weight 'D' which is lowest, so it does not boost relevance as much.

4. Final Answer:

   SELECT content, ts_rank(setweight(to_tsvector(content), 'A'), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank DESC LIMIT 3; -> Option D

5. Quick Check:

   Weighted ts_rank with OR query = SELECT content, ts_rank(setweight(to_tsvector(content), 'A'), to_tsquery('apple | orange')) AS rank FROM documents ORDER BY rank DESC LIMIT 3; [OK]

Hint: Use setweight with 'A' to boost preferred terms [OK]

Common Mistakes:

• Using AND instead of OR in tsquery
• Ordering by rank ascending instead of descending
• Assigning lowest weight to preferred terms