Database indexes in Supabase - Time & Space Complexity

Time Complexity: Database indexes

O(log n)

Understanding Time Complexity

When we use database indexes, we want to know how they affect the speed of finding data.

We ask: How does the time to find data change as the database grows?

Scenario Under Consideration

Analyze the time complexity of querying a table with and without an index.

// Query without index
const { data, error } = await supabase
  .from('users')
  .select('*')
  .eq('email', '[e-mail]')

// Query with index on 'email' column
// (Index created separately in database)

This code fetches user data by email, once without an index and once assuming an index exists.

Identify Repeating Operations

Look at what happens when the query runs multiple times as data grows.

• Primary operation: Searching rows in the database for matching email.
• How many times: Once per query, but the cost depends on how many rows must be checked.

How Execution Grows With Input

Without an index, the database checks each row one by one.

Input Size (n)	Approx. Rows Checked
10	10
100	100
1000	1000

With an index, the database uses a shortcut to find the row quickly, checking far fewer rows.

Input Size (n)	Approx. Rows Checked
10	About 3
100	About 7
1000	About 10

Pattern observation: Without index, work grows directly with data size; with index, work grows slowly as data grows.

Final Time Complexity

Time Complexity: O(log n)

This means finding data with an index takes a small, slowly growing amount of time even as the database gets much bigger.

Common Mistake

[X] Wrong: "Adding an index makes every query instant no matter what."

[OK] Correct: Indexes speed up searches but still take some time that grows slowly with data size. Also, indexes add some cost when adding or changing data.

Interview Connect

Understanding how indexes affect query speed shows you know how to make databases work well as they grow. This skill helps you design systems that stay fast and reliable.

Self-Check

"What if we added multiple indexes on different columns? How would the time complexity of queries change?"