CREATE INDEX syntax in SQL - Time & Space Complexity

Time Complexity: CREATE INDEX syntax

O(n log n)

Understanding Time Complexity

Let's explore how the time to create an index changes as the data grows.

We want to know how the work done by the database increases when building an index on a table.

Scenario Under Consideration

Analyze the time complexity of the following SQL command.

CREATE INDEX idx_customer_name
ON customers (last_name);
    

This command creates an index on the last_name column of the customers table to speed up searches.

Identify Repeating Operations

When creating an index, the database must process each row to build the index structure.

• Primary operation: Reading each row's last_name value and inserting it into the index.
• How many times: Once for every row in the customers table.

How Execution Grows With Input

As the number of rows grows, the work to create the index grows too.

Input Size (n)	Approx. Operations
10	About 10 reads and inserts
100	About 100 reads and inserts
1000	About 1000 reads and inserts

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n log n)

This means creating the index takes a bit more than just looking at each row once, because it also organizes the data efficiently.

Common Mistake

[X] Wrong: "Creating an index is just as fast as scanning the table once, so it is O(n)."

[OK] Correct: Building the index involves sorting or organizing data, which adds extra steps, making it slower than a simple scan.

Interview Connect

Understanding how index creation time grows helps you explain database performance clearly and shows you know what happens behind the scenes.

Self-Check

"What if the index was created on multiple columns instead of one? How would the time complexity change?"

Practice

1. What is the main purpose of using CREATE INDEX in a database?

easy

A. To speed up data retrieval by creating shortcuts on columns

B. To delete rows faster from a table

C. To backup the database automatically

D. To encrypt the data stored in the table

Solution

1. Step 1: Understand what an index does

   An index creates a shortcut to quickly find data in a column without scanning the whole table.

2. Step 2: Identify the main benefit

   This shortcut speeds up data retrieval, especially for searches and sorts.

3. Final Answer:

   To speed up data retrieval by creating shortcuts on columns -> Option A

4. Quick Check:

   CREATE INDEX improves search speed [OK]

Hint: Indexes speed up searches by creating shortcuts [OK]

Common Mistakes:

• Thinking indexes speed up data deletion
• Confusing indexes with backups
• Believing indexes encrypt data

2. Which of the following is the correct syntax to create an index named idx_name on the column last_name of the table employees?

easy

A. CREATE idx_name INDEX ON employees (last_name);

B. CREATE INDEX idx_name ON employees (last_name);

C. INDEX CREATE idx_name ON employees (last_name);

D. CREATE INDEX ON employees idx_name (last_name);

Solution

1. Step 1: Recall the standard CREATE INDEX syntax

   The correct syntax is: CREATE INDEX index_name ON table_name (column_name);

2. Step 2: Match the syntax with options

   CREATE INDEX idx_name ON employees (last_name); matches the correct order and keywords exactly.

3. Final Answer:

   CREATE INDEX idx_name ON employees (last_name); -> Option B

4. Quick Check:

   CREATE INDEX index_name ON table (column) [OK]

Hint: Remember: CREATE INDEX name ON table (column) [OK]

Common Mistakes:

• Swapping index name and table name positions
• Using wrong keyword order
• Omitting ON keyword

3. Given the table products(id INT, name VARCHAR, price DECIMAL), what will be the result of this SQL command?

CREATE INDEX idx_price ON products(price);

medium

A. The products table is duplicated with the name idx_price

B. The price column is deleted from the products table

C. An index named idx_price is created on the price column to speed up queries filtering by price

D. Syntax error because price is not a primary key

Solution

1. Step 1: Understand what the CREATE INDEX command does here

   The command creates an index named idx_price on the price column of products.

2. Step 2: Identify the effect of the index

   This index helps speed up queries that filter or sort by price without changing the table structure.

3. Final Answer:

   An index named idx_price is created on the price column to speed up queries filtering by price -> Option C

4. Quick Check:

   CREATE INDEX adds search speed, no deletion [OK]

Hint: CREATE INDEX speeds up search, does not delete or duplicate [OK]

Common Mistakes:

• Thinking index creation deletes columns
• Assuming index requires primary key
• Confusing index with table duplication

4. Identify the error in this SQL statement:

CREATE INDEX ON employees (last_name);

medium

A. Cannot create index on last_name column

B. Missing table name after ON

C. Incorrect use of parentheses around column name

D. Missing index name after CREATE INDEX

Solution

1. Step 1: Check the syntax of CREATE INDEX

   The syntax requires an index name after CREATE INDEX before ON.

2. Step 2: Identify the missing part

   The statement lacks the index name, which causes a syntax error.

3. Final Answer:

   Missing index name after CREATE INDEX -> Option D

4. Quick Check:

   CREATE INDEX must have a name [OK]

Hint: Always name your index after CREATE INDEX [OK]

Common Mistakes:

• Omitting the index name
• Confusing table name with index name
• Misplacing parentheses

5. You want to speed up queries that filter by both category and price columns in the items table. Which is the best way to create an index?

hard

A. CREATE INDEX idx_cat_price ON items (category, price);

B. CREATE INDEX idx_cat ON items (category); CREATE INDEX idx_price ON items (price);

C. CREATE INDEX idx_price_cat ON items (price, category);

D. CREATE INDEX idx_items ON items (category);

Solution

1. Step 1: Understand multi-column index usage

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

2. Step 2: Compare options

   CREATE INDEX idx_cat_price ON items (category, price); creates a composite index on category and price in that order, which is best for combined filters.

3. Final Answer:

   CREATE INDEX idx_cat_price ON items (category, price); -> Option A

4. Quick Check:

   Composite index on both columns is best [OK]

Hint: Use composite index for multiple columns searched together [OK]

Common Mistakes:

• Creating separate indexes instead of composite
• Wrong column order in composite index
• Creating index on only one column when filtering by two