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