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?"

Practice

1. What does the tsvector type represent in PostgreSQL full-text search?

easy

A. A table storing user data

B. A searchable document converted into lexemes

C. A function to rank search results

D. A query pattern to search text

Solution

1. Step 1: Understand tsvector role

   tsvector stores processed text as lexemes for searching.

2. Step 2: Differentiate from tsquery

   tsquery is the search pattern, not the stored text.

3. Final Answer:

   A searchable document converted into lexemes -> Option B

4. Quick Check:

   tsvector = searchable text [OK]

Hint: Remember: tsvector stores text, tsquery stores search pattern [OK]

Common Mistakes:

• Confusing tsvector with tsquery
• Thinking tsvector is a function
• Assuming tsvector stores raw text

2. Which of the following is the correct syntax to check if a tsvector matches a tsquery in PostgreSQL?

easy

A. tsvector = tsquery

B. tsquery @@ tsvector

C. tsvector @@ tsquery

D. tsvector LIKE tsquery

Solution

1. Step 1: Recall operator for matching

   The @@ operator tests if tsvector matches tsquery.

2. Step 2: Confirm operand order

   The syntax is tsvector @@ tsquery, not reversed or using other operators.

3. Final Answer:

   tsvector @@ tsquery -> Option C

4. Quick Check:

   Match operator = @@ [OK]

Hint: Use tsvector @@ tsquery to test matches [OK]

Common Mistakes:

• Reversing operands in @@ operator
• Using = or LIKE instead of @@
• Confusing tsquery and tsvector roles

3. Given the table documents with a column content_tsv of type tsvector, what will this query return?

SELECT id FROM documents WHERE content_tsv @@ to_tsquery('cat & dog');

medium

A. Rows where content contains both 'cat' and 'dog'

B. Rows where content contains either 'cat' or 'dog'

C. Rows where content contains the exact phrase 'cat dog'

D. Rows where content contains 'cat' but not 'dog'

Solution

1. Step 1: Understand to_tsquery('cat & dog')

   The & operator means AND, so it searches for both words.

2. Step 2: Apply @@ operator

   The query returns rows where content_tsv matches both 'cat' and 'dog'.

3. Final Answer:

   Rows where content contains both 'cat' and 'dog' -> Option A

4. Quick Check:

   AND operator & means both words [OK]

Hint: Use & in tsquery for AND search [OK]

Common Mistakes:

• Thinking & means OR
• Assuming phrase match instead of AND
• Confusing tsquery syntax operators

4. Identify the error in this PostgreSQL query:

SELECT * FROM articles WHERE to_tsquery('dog | cat') @@ content_tsv;

medium

A. The operands of @@ are reversed; tsvector must be on the left

B. The operator | is invalid in tsquery

C. to_tsquery requires two arguments

D. content_tsv must be cast to text before matching

Solution

1. Step 1: Check @@ operator usage

   The left operand must be tsvector, right operand tsquery.

2. Step 2: Identify operand order in query

   The query has to_tsquery('dog | cat') on left (tsquery), which is incorrect.

3. Final Answer:

   The operands of @@ are reversed; tsvector must be on the left -> Option A

4. Quick Check:

   tsvector @@ tsquery order matters [OK]

Hint: Always put tsvector left, tsquery right in @@ [OK]

Common Mistakes:

• Swapping operands in @@ operator
• Misunderstanding tsquery syntax
• Casting tsvector to text unnecessarily

5. You want to find rows in table notes where the content column contains the word 'apple' but not 'pie'. Which tsquery expression correctly achieves this?

SELECT * FROM notes WHERE to_tsvector(content) @@ to_tsquery( ? );

hard

A. 'apple ! pie'

B. 'apple | !pie'

C. 'apple & pie'

D. 'apple & !pie'

Solution

1. Step 1: Understand tsquery operators

   & means AND, ! means NOT, | means OR.

2. Step 2: Construct query for 'apple' AND NOT 'pie'

   The correct expression is 'apple & !pie' to include 'apple' but exclude 'pie'.

3. Final Answer:

   'apple & !pie' -> Option D

4. Quick Check:

   AND + NOT = & ! [OK]

Hint: Use & for AND and ! for NOT in tsquery [OK]

Common Mistakes:

• Using | instead of & for AND
• Omitting & between terms
• Incorrect spacing or missing operators