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

Practice

1. What is the main purpose of creating a database index in Supabase?

easy

A. To speed up data searches and queries

B. To store more data in the database

C. To backup the database automatically

D. To encrypt the data for security

Solution

1. Step 1: Understand what an index does

   An index creates a quick lookup structure to find data faster.

2. Step 2: Compare options with index purpose

   Only speeding up searches matches the index function.

3. Final Answer:

   To speed up data searches and queries -> Option A

4. Quick Check:

   Index = Faster search [OK]

Hint: Indexes speed up searches, not storage or security [OK]

Common Mistakes:

• Thinking indexes store more data
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which of the following is the correct SQL syntax to create an index on the column email in a Supabase table named users?

easy

A. CREATE INDEX email ON users;

B. INDEX CREATE users.email;

C. CREATE INDEX ON users (email);

D. CREATE users INDEX email;

Solution

1. Step 1: Recall correct SQL index syntax

   The standard syntax is: CREATE INDEX index_name ON table_name (column_name); but index_name is optional.

2. Step 2: Match syntax with options

   CREATE INDEX ON users (email); uses correct syntax without specifying index name, which is allowed.

3. Final Answer:

   CREATE INDEX ON users (email); -> Option C

4. Quick Check:

   CREATE INDEX ON table (column) [OK]

Hint: Use CREATE INDEX ON table (column) for indexes [OK]

Common Mistakes:

• Placing column before table incorrectly
• Using wrong keyword order
• Omitting ON keyword

3. Given the table orders with an index on customer_id, what will be the effect of this query?

SELECT * FROM orders WHERE customer_id = 123;

medium

A. The query will return no results because indexes filter data

B. The query will ignore the index and scan the whole table

C. The query will fail due to missing index

D. The query will run faster by using the index on customer_id

Solution

1. Step 1: Understand index usage in queries

   Indexes help the database find matching rows quickly when filtering by indexed columns.

2. Step 2: Analyze the query filter

   The query filters by customer_id, which has an index, so the index will be used.

3. Final Answer:

   The query will run faster by using the index on customer_id -> Option D

4. Quick Check:

   Indexed column filter = faster query [OK]

Hint: Queries filtering indexed columns run faster [OK]

Common Mistakes:

• Thinking index causes query failure
• Assuming index filters out data
• Believing index is ignored automatically

4. You created multiple indexes on a Supabase table, but now data insertions are very slow. What is the most likely cause?

medium

A. Too many indexes slow down data changes

B. Indexes cause data loss during insert

C. Indexes prevent data from being inserted

D. Indexes automatically delete old data

Solution

1. Step 1: Recall how indexes affect data changes

   Each index must be updated when data changes, so many indexes slow inserts and updates.

2. Step 2: Match symptoms with cause

   Slow insertions match the effect of too many indexes.

3. Final Answer:

   Too many indexes slow down data changes -> Option A

4. Quick Check:

   Many indexes = slower inserts [OK]

Hint: More indexes = slower writes, fewer indexes = faster writes [OK]

Common Mistakes:

• Thinking indexes cause data loss
• Assuming indexes block inserts
• Believing indexes delete data automatically

5. You want to optimize a Supabase table products that is frequently searched by category and price. Which index strategy is best to improve query speed without slowing inserts too much?

hard

A. Create no indexes to keep inserts fast

B. Create a composite index on (category, price)

C. Create an index only on price

D. Create separate indexes on category and price

Solution

1. Step 1: Understand composite vs separate indexes

   A composite index on (category, price) helps queries filtering both columns efficiently.

2. Step 2: Consider insert performance

   One composite index is faster to update than two separate indexes, balancing speed and insert cost.

3. Step 3: Evaluate options

   Create a composite index on (category, price) optimizes queries on both columns with minimal insert slowdown.

4. Final Answer:

   Create a composite index on (category, price) -> Option B

5. Quick Check:

   Composite index = faster multi-column queries [OK]

Hint: Use composite indexes for multi-column searches [OK]

Common Mistakes:

• Creating too many separate indexes
• Indexing only one column when both are searched
• Avoiding indexes and hurting query speed