to_tsquery for search terms in PostgreSQL - Time & Space Complexity

Time Complexity: to_tsquery for search terms

O(n * m)

Understanding Time Complexity

We want to understand how the time to process search terms using to_tsquery grows as the input size changes.

Specifically, how does the search query processing time increase when we add more words or terms?

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL snippet using to_tsquery.

SELECT *
FROM documents
WHERE to_tsvector('english', content) @@ to_tsquery('english', 'search & term & example');
    

This code searches the documents table for rows where the content matches all the words in the search query.

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 row in the documents table.

How Execution Grows With Input

The time grows roughly with the number of rows and the number of search terms.

Input Size (n)	Approx. Operations
10 rows, 2 terms	About 20 checks
100 rows, 3 terms	About 300 checks
1000 rows, 5 terms	About 5000 checks

Pattern observation: More rows and more search terms increase the work roughly by multiplying together.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of rows n and the number of search terms m.

Common Mistake

[X] Wrong: "Adding more search terms does not affect the query time much because the database just matches words quickly."

[OK] Correct: Each additional search term adds more checks per row, increasing the total work and time needed.

Interview Connect

Understanding how search queries scale helps you explain performance in real projects and shows you can think about how data size affects response time.

Self-Check

"What if we used a phrase search instead of multiple AND terms? How would the time complexity change?"

Practice

1. What does the to_tsquery function do in PostgreSQL?

easy

A. It converts search terms into a format for full-text search queries.

B. It creates a new table for storing search terms.

C. It updates text columns with search keywords.

D. It deletes rows that match search terms.

Solution

1. Step 1: Understand the purpose of to_tsquery

   to_tsquery converts plain search words into a special query format that PostgreSQL can use for full-text searching.

2. Step 2: Compare options with the function's role

   Only It converts search terms into a format for full-text search queries. correctly describes this conversion role. Other options describe unrelated database actions.

3. Final Answer:

   It converts search terms into a format for full-text search queries. -> Option A

4. Quick Check:

   to_tsquery = converts search terms [OK]

Hint: Remember: to_tsquery prepares search words for text search [OK]

Common Mistakes:

• Thinking it creates or modifies tables
• Confusing it with data update or delete operations
• Assuming it returns raw text instead of a query format

2. Which of the following is the correct syntax to create a to_tsquery for searching the words 'cat' AND 'dog' using the explicit AND operator?

easy

A. to_tsquery('cat | dog')

B. to_tsquery('cat & dog')

C. to_tsquery('cat dog')

D. to_tsquery('cat && dog')

Solution

1. Step 1: Recall the AND operator in to_tsquery

   The AND operator is represented by & in to_tsquery syntax.

2. Step 2: Match the correct syntax

   to_tsquery('cat & dog') uses & correctly between 'cat' and 'dog'. to_tsquery('cat | dog') uses OR, C misses operator, and D uses invalid &&.

3. Final Answer:

   to_tsquery('cat & dog') -> Option B

4. Quick Check:

   AND = & in to_tsquery [OK]

Hint: Use & for AND, | for OR in to_tsquery strings [OK]

Common Mistakes:

• Using spaces without operators to mean AND
• Using double ampersands (&&) instead of single &
• Confusing OR (|) with AND (&)

3. Given the query:
SELECT to_tsquery('fast & !slow');
What is the expected output?

medium

A. 'fast' | !'slow'

B. Syntax error

C. 'fast' & !'slow'

D. 'fast slow'

Solution

1. Step 1: Understand the operators in the query

   The query uses AND (&) between 'fast' and NOT (!) 'slow'. This means search for 'fast' but exclude 'slow'.

2. Step 2: Check the output format of to_tsquery

   PostgreSQL returns the query as a string with words quoted and operators preserved. So output is 'fast' & !'slow'.

3. Final Answer:

   'fast' & !'slow' -> Option C

4. Quick Check:

   AND = & and NOT = ! in output [OK]

Hint: NOT is !, AND is & in to_tsquery output [OK]

Common Mistakes:

• Confusing OR (|) with AND (&)
• Expecting raw words without quotes
• Thinking the query causes syntax error

4. Identify the error in this query:
SELECT to_tsquery('apple & | orange');

medium

A. Syntax error due to consecutive operators & |

B. No error, valid query

C. Error because words must be uppercase

D. Error because to_tsquery needs two arguments

Solution

1. Step 1: Analyze the operator usage in the query string

   The string has & | operators consecutively without a word between them, which is invalid syntax.

2. Step 2: Confirm PostgreSQL behavior

   PostgreSQL will raise a syntax error because operators must separate valid search terms, not each other.

3. Final Answer:

   Syntax error due to consecutive operators & | -> Option A

4. Quick Check:

   Operators must separate words, not each other [OK]

Hint: Avoid placing operators consecutively without words [OK]

Common Mistakes:

• Assuming multiple operators in a row are allowed
• Thinking case of words matters
• Believing to_tsquery requires multiple arguments

5. You want to search for documents containing the word 'run' but not 'running'. Which to_tsquery expression correctly achieves this?

hard

A. to_tsquery('run ! running')

B. to_tsquery('run | !running')

C. to_tsquery('run & !run')

D. to_tsquery('run & !running')

Solution

1. Step 1: Understand the requirement

   You want documents that contain 'run' but exclude those that contain 'running'. This means AND 'run' and NOT 'running'.

2. Step 2: Choose the correct operator usage

   AND is & and NOT is !. to_tsquery('run & !running') uses these correctly. to_tsquery('run | !running') uses OR which is wrong. to_tsquery('run & !run') excludes 'run' itself. to_tsquery('run ! running') has invalid syntax (missing operator between 'run' and '!').

3. Final Answer:

   to_tsquery('run & !running') -> Option D

4. Quick Check:

   AND = & and NOT = ! for correct filtering [OK]

Hint: Use & for AND, ! for NOT to exclude terms [OK]

Common Mistakes:

• Using OR instead of AND for inclusion
• Excluding the main word accidentally
• Missing operators between words