Primary keys and foreign keys in Supabase - Time & Space Complexity

Time Complexity: Primary keys and foreign keys

O(n)

Understanding Time Complexity

When working with primary keys and foreign keys in Supabase, it's important to understand how the number of database operations grows as data increases.

We want to know how the time to insert or query data changes when tables have these keys.

Scenario Under Consideration

Analyze the time complexity of inserting rows with primary and foreign keys.

// Insert a new user
const { data: user } = await supabase
  .from('users')
  .insert([{ id: 1, name: 'Alice' }])
  .select()

// Insert a new order linked to the user
const { data: order } = await supabase
  .from('orders')
  .insert([{ id: 101, user_id: 1, product: 'Book' }])
  .select()
    

This sequence inserts a user with a primary key and an order referencing that user via a foreign key.

Identify Repeating Operations

Look at the main database calls that happen repeatedly as data grows.

• Primary operation: Insert row into 'users' and 'orders' tables.
• How many times: Once per new user and once per new order.

How Execution Grows With Input

Each insert checks keys to keep data consistent. As you add more rows, each insert still does a quick check.

Input Size (n)	Approx. API Calls/Operations
10 users + 10 orders	20 insert operations
100 users + 100 orders	200 insert operations
1000 users + 1000 orders	2000 insert operations

Pattern observation: The number of operations grows directly with the number of rows inserted.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert rows grows linearly with the number of rows you add.

Common Mistake

[X] Wrong: "Adding foreign keys makes inserts take much longer as data grows exponentially."

[OK] Correct: Foreign key checks are efficient and use indexes, so insert time grows linearly, not exponentially.

Interview Connect

Understanding how keys affect database operations shows you can design data that stays fast and reliable as it grows.

Self-Check

"What if we added an index on the foreign key column? How would that affect the time complexity of inserts and queries?"