Full-text search with Postgres in Supabase - Time & Space Complexity

Time Complexity: Full-text search with Postgres

O(log n)

Understanding Time Complexity

When using full-text search in Postgres via Supabase, it's important to understand how the search time changes as your data grows.

We want to know how the number of search operations grows when the number of documents increases.

Scenario Under Consideration

Analyze the time complexity of this full-text search query using Supabase.

const { data, error } = await supabase
  .from('articles')
  .select('*')
  .textSearch('content', 'cloud & infrastructure')
  .limit(10)

This query searches the 'content' column in the 'articles' table for the phrase 'cloud & infrastructure' and returns up to 10 matching rows.

Identify Repeating Operations

Look at what happens when this search runs:

• Primary operation: The database performs an index scan on the full-text index on the 'content' column.
• How many times: Roughly O(log n) index lookups, where n is the number of documents.

How Execution Grows With Input

As the number of articles grows, the search uses the index to quickly find matches.

Input Size (n)	Approx. Api Calls/Operations
10	About 3-4 index lookups
100	About 7 index lookups
1000	About 10 index lookups

Pattern observation: The search time grows roughly logarithmically with the number of documents because the index height grows logarithmically.

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows logarithmically with the number of documents in the table.

Common Mistake

[X] Wrong: "Full-text search always runs instantly no matter how much data there is."

[OK] Correct: Even with an index, larger datasets mean larger indexes with greater depth (log n growth) and potentially larger posting lists to process.

Interview Connect

Understanding how search time grows helps you design better queries and indexes, a useful skill for real-world cloud database work.

Self-Check

"What if we added a more selective filter before the full-text search? How would that affect the time complexity?"

Practice

1. What is the main purpose of using to_tsvector in Postgres full-text search?

easy

A. To convert text into a searchable document format

B. To insert new rows into a table

C. To delete unwanted text from a column

D. To create a backup of the database

Solution

1. Step 1: Understand to_tsvector function

   to_tsvector converts plain text into a special searchable format called a tsvector, which breaks text into words and normalizes them for searching.

2. Step 2: Identify its role in full-text search

   This conversion allows Postgres to quickly find matching words during a search query.

3. Final Answer:

   To convert text into a searchable document format -> Option A

4. Quick Check:

   to_tsvector = searchable format [OK]

Hint: Remember: to_tsvector prepares text for searching [OK]

Common Mistakes:

• Confusing to_tsvector with data insertion
• Thinking it deletes text
• Assuming it backs up data

2. Which of the following is the correct syntax to perform a full-text search using to_tsquery in Postgres?

easy

A. SELECT * FROM articles WHERE to_tsquery('search & term') @@ content;

B. SELECT * FROM articles WHERE to_tsquery(content) @@ 'search & term';

C. SELECT * FROM articles WHERE to_tsquery('search & term') = content;

D. SELECT * FROM articles WHERE content @@ to_tsquery('search & term');

Solution

1. Step 1: Understand to_tsquery usage

   to_tsquery creates a search query from a string like 'search & term'. It should be on the right side of the @@ operator.

2. Step 2: Check correct operator usage

   The @@ operator checks if the tsvector (usually a column) matches the tsquery. So the column (tsvector) is on the left, and to_tsquery is on the right.

3. Final Answer:

   SELECT * FROM articles WHERE content @@ to_tsquery('search & term'); -> Option D

4. Quick Check:

   tsvector @@ tsquery = correct syntax [OK]

Hint: Remember: tsvector column @@ to_tsquery('query') [OK]

Common Mistakes:

• Putting to_tsquery on the left side
• Using = instead of @@ operator
• Passing column name inside to_tsquery

3. Given the table products with a column description, what will this query return?

SELECT id FROM products WHERE to_tsvector(description) @@ to_tsquery('red & apple');

medium

A. All products with descriptions containing both 'red' and 'apple'

B. All products with descriptions containing either 'red' or 'apple'

C. All products with descriptions containing the exact phrase 'red apple'

D. No products because the syntax is incorrect

Solution

1. Step 1: Analyze the query logic

   The query uses to_tsvector(description) to convert descriptions into searchable format, then checks if it matches to_tsquery('red & apple').

2. Step 2: Understand the & operator in tsquery

   The & means AND, so it matches rows containing both 'red' and 'apple' anywhere in the description, not necessarily as a phrase.

3. Final Answer:

   All products with descriptions containing both 'red' and 'apple' -> Option A

4. Quick Check:

   'red & apple' means both words present [OK]

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

Common Mistakes:

• Thinking & means OR
• Assuming exact phrase match
• Confusing syntax causing no results

4. You wrote this query but it returns no results:

SELECT * FROM feedback WHERE to_tsvector(comment) @@ to_tsquery('happy | sad');

What is the most likely reason?

medium

A. The to_tsquery syntax is invalid

B. The comment column is not indexed with a tsvector column

C. The @@ operator is used incorrectly

D. The query should use LIKE instead of full-text search

Solution

1. Step 1: Check query correctness

   The syntax and operator usage are correct for full-text search with to_tsvector and to_tsquery.

2. Step 2: Identify performance and result issues

   If no results appear, often the comment column is not indexed as a tsvector, so the search is slow or ineffective.

3. Final Answer:

   The comment column is not indexed with a tsvector column -> Option B

4. Quick Check:

   Missing tsvector index causes no results [OK]

Hint: Always create a tsvector index for fast full-text search [OK]

Common Mistakes:

• Assuming syntax error when query is correct
• Using LIKE instead of full-text search
• Misusing @@ operator

5. You want to build a search feature on a blog using Supabase and Postgres full-text search. Which approach best improves search speed and accuracy for large text columns?

hard

A. Store search keywords in a separate table and join on it

B. Use LIKE '%keyword%' queries on the text column without indexes

C. Create a generated tsvector column indexed with GIN and query using @@ operator

D. Use regular expressions to scan text columns at query time

Solution

1. Step 1: Understand full-text search optimization

   Creating a generated column that stores the tsvector form of the text allows fast searching without recalculating on each query.

2. Step 2: Use GIN index for fast lookup

   Adding a GIN index on the tsvector column speeds up searches dramatically, making queries efficient and scalable.

3. Step 3: Query with @@ operator for accuracy

   Using the @@ operator with to_tsquery on the indexed tsvector column ensures accurate full-text matching.

4. Final Answer:

   Create a generated tsvector column indexed with GIN and query using @@ operator -> Option C

5. Quick Check:

   Generated tsvector + GIN index = fast, accurate search [OK]

Hint: Index tsvector columns with GIN for best full-text search [OK]

Common Mistakes:

• Using LIKE instead of full-text search
• Not indexing tsvector columns
• Relying on regex for large text search