First query execution in MySQL - Time & Space Complexity

Time Complexity: First query execution

O(n)

Understanding Time Complexity

When a database runs a query for the first time, it needs to do some extra work to prepare. This affects how long the query takes.

We want to understand how the time to run the first query changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees WHERE department_id = 5;
    

This query fetches all employees who work in department 5. It runs for the first time after the database starts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the employees table rows to find matches.
• How many times: Once for each row in the employees table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows to find matches.

Input Size (n)	Approx. Operations
10	10 row checks
100	100 row checks
1000	1000 row checks

Pattern observation: The work grows directly with the number of rows. More rows mean more checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the first query grows in a straight line with the number of rows in the table.

Common Mistake

[X] Wrong: "The first query always runs instantly no matter the data size."

[OK] Correct: The database must check each row to find matches, so more data means more work and longer time.

Interview Connect

Understanding how the first query runs helps you explain how databases handle data and why some queries take longer. This shows you think about real-world data sizes and performance.

Self-Check

"What if the employees table had an index on department_id? How would the time complexity change?"

Practice

1. What does the SELECT statement do in MySQL?

easy

A. It retrieves data from a database table.

B. It deletes data from a database table.

C. It updates data in a database table.

D. It creates a new database table.

Solution

1. Step 1: Understand the purpose of SELECT

   The SELECT statement is used to get or read data from a table in a database.

2. Step 2: Compare with other SQL commands

   DELETE removes data, UPDATE changes data, and CREATE makes new tables, so they are different from SELECT.

3. Final Answer:

   It retrieves data from a database table. -> Option A

4. Quick Check:

   SELECT = retrieve data [OK]

Hint: SELECT means get data from a table [OK]

Common Mistakes:

• Confusing SELECT with DELETE or UPDATE
• Thinking SELECT creates tables
• Mixing SELECT with data modification commands

2. Which of the following is the correct syntax to select all columns from a table named users?

easy

A. SELECT users FROM *;

B. SELECT * FROM users;

C. SELECT * users FROM;

D. FROM users SELECT *;

Solution

1. Step 1: Recall the basic SELECT syntax

   The correct syntax to get all columns is: SELECT * FROM table_name;

2. Step 2: Check each option

   SELECT * FROM users; matches the correct syntax. Others have wrong order or misplaced keywords.

3. Final Answer:

   SELECT * FROM users; -> Option B

4. Quick Check:

   SELECT * FROM table_name; is correct [OK]

Hint: SELECT * FROM table_name; gets all columns [OK]

Common Mistakes:

• Swapping SELECT and FROM keywords
• Omitting the FROM keyword
• Placing * in wrong position

3. Given a table products with columns id, name, and price, what will this query return?

SELECT name FROM products;

medium

A. All product names from the products table.

B. All product prices from the products table.

C. All columns from the products table.

D. An error because price column is missing.

Solution

1. Step 1: Understand the SELECT clause

   The query selects only the 'name' column from the products table.

2. Step 2: Check what is returned

   It returns all rows but only the 'name' column values, not price or id.

3. Final Answer:

   All product names from the products table. -> Option A

4. Quick Check:

   SELECT name returns names only [OK]

Hint: SELECT column_name returns that column's data [OK]

Common Mistakes:

• Assuming all columns are returned
• Thinking missing columns cause errors
• Confusing column names in SELECT

4. What is wrong with this query?

SELECT FROM users;

medium

A. FROM keyword should be after WHERE.

B. Table name is incorrect.

C. Missing column names or * after SELECT.

D. SELECT cannot be used with FROM.

Solution

1. Step 1: Check the SELECT syntax

   SELECT must be followed by column names or * to specify what to retrieve.

2. Step 2: Identify the error in the query

   The query has SELECT but no columns or * after it, causing a syntax error.

3. Final Answer:

   Missing column names or * after SELECT. -> Option C

4. Quick Check:

   SELECT needs columns or * [OK]

Hint: Always specify columns or * after SELECT [OK]

Common Mistakes:

• Leaving SELECT empty
• Misplacing FROM keyword
• Thinking FROM is optional

5. You want to see all columns from a table employees but only for employees with the job title 'Manager'. Which query should you use?

hard

A. SELECT * WHERE job_title = 'Manager' FROM employees;

B. SELECT job_title FROM employees WHERE job_title = 'Manager';

C. SELECT * FROM employees;

D. SELECT * FROM employees WHERE job_title = 'Manager';

Solution

1. Step 1: Identify the need to filter rows

   We want all columns but only rows where job_title is 'Manager', so we need a WHERE clause.

2. Step 2: Check query syntax and logic

   SELECT * FROM employees WHERE job_title = 'Manager'; correctly uses SELECT * FROM employees WHERE job_title = 'Manager'; which returns all columns filtered by job title.

3. Final Answer:

   SELECT * FROM employees WHERE job_title = 'Manager'; -> Option D

4. Quick Check:

   Use WHERE to filter rows [OK]

Hint: Use WHERE to filter rows after FROM [OK]

Common Mistakes:

• Omitting WHERE clause for filtering
• Placing WHERE before FROM
• Selecting only job_title instead of all columns