Primary key declaration in MySQL - Time & Space Complexity

Time Complexity: Primary key declaration

O(log n)

Understanding Time Complexity

When we declare a primary key in a database table, the system creates a unique index to quickly find rows.

We want to understand how the time to insert or find data changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of declaring a primary key and inserting rows.

CREATE TABLE users (
  id INT NOT NULL,
  name VARCHAR(100),
  PRIMARY KEY (id)
);

INSERT INTO users (id, name) VALUES (1, 'Alice');
INSERT INTO users (id, name) VALUES (2, 'Bob');
-- More inserts follow
    

This code creates a table with a primary key on the 'id' column and inserts rows.

Identify Repeating Operations

When inserting rows, the database must maintain the primary key index.

• Primary operation: Inserting into a balanced tree index (like B-tree) for the primary key.
• How many times: Once per insert operation, repeated for each row inserted.

How Execution Grows With Input

As the number of rows grows, inserting a new row requires searching the index to place the key correctly.

Input Size (n)	Approx. Operations
10	About 3 steps to insert
100	About 7 steps to insert
1000	About 10 steps to insert

Pattern observation: The number of steps grows slowly as the table grows larger, not directly proportional.

Final Time Complexity

Time Complexity: O(log n)

This means inserting or searching by primary key takes a little more time as the table grows, but it grows slowly and efficiently.

Common Mistake

[X] Wrong: "Inserting with a primary key is always slow because it checks every row."

[OK] Correct: The database uses an index structure that avoids checking every row, so it only needs a few steps even for large tables.

Interview Connect

Understanding how primary keys affect performance shows you know how databases keep data organized and fast to access, a key skill for many roles.

Self-Check

"What if we changed the primary key to a non-indexed column? How would the time complexity for searching change?"

Practice

1. What is the main purpose of a PRIMARY KEY in a MySQL table?

easy

A. To uniquely identify each row and prevent duplicates

B. To allow NULL values in a column

C. To speed up SELECT queries only

D. To store large text data

Solution

1. Step 1: Understand the role of PRIMARY KEY

   A PRIMARY KEY uniquely identifies each row in a table and ensures no duplicate or NULL values exist in that column.

2. Step 2: Compare options with PRIMARY KEY purpose

   Only To uniquely identify each row and prevent duplicates correctly states the unique identification and prevention of duplicates, which is the main purpose.

3. Final Answer:

   To uniquely identify each row and prevent duplicates -> Option A

4. Quick Check:

   Primary key = unique row ID [OK]

Hint: Primary key means unique and no duplicates [OK]

Common Mistakes:

• Thinking primary key allows NULL values
• Confusing primary key with indexing only
• Assuming primary key stores large text

2. Which of the following is the correct syntax to declare a primary key inline in a MySQL CREATE TABLE statement?

easy

A. CREATE TABLE users (id INT, name VARCHAR(50 PRIMARY KEY));

B. CREATE TABLE users (id INT, name VARCHAR(50), PRIMARY KEY id);

C. CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50));

D. CREATE TABLE users (id INT, PRIMARY KEY, name VARCHAR(50));

Solution

1. Step 1: Review inline primary key syntax

   Inline primary key declaration is done by adding PRIMARY KEY right after the column type, like id INT PRIMARY KEY.

2. Step 2: Check each option

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); correctly places PRIMARY KEY inline after id INT. Others have syntax errors or misplaced keywords.

3. Final Answer:

   CREATE TABLE users (id INT PRIMARY KEY, name VARCHAR(50)); -> Option C

4. Quick Check:

   Inline primary key = column type + PRIMARY KEY [OK]

Hint: Inline primary key goes right after column type [OK]

Common Mistakes:

• Placing PRIMARY KEY after column list without parentheses
• Using PRIMARY KEY without column name
• Putting PRIMARY KEY after another column

3. Given the table creation below, what will be the result of inserting two rows with the same id?

CREATE TABLE products (
  id INT PRIMARY KEY,
  name VARCHAR(100)
);
INSERT INTO products (id, name) VALUES (1, 'Pen');
INSERT INTO products (id, name) VALUES (1, 'Pencil');

medium

A. Both rows inserted successfully

B. Error due to duplicate primary key value

C. Second row overwrites the first row

D. NULL inserted for the second row's id

Solution

1. Step 1: Understand primary key uniqueness

   The primary key column id must have unique values. Duplicate values cause errors.

2. Step 2: Analyze the insert statements

   The first insert adds id=1. The second insert tries to add the same id=1, violating uniqueness.

3. Final Answer:

   Error due to duplicate primary key value -> Option B

4. Quick Check:

   Duplicate primary key = error [OK]

Hint: Primary key duplicates cause insert errors [OK]

Common Mistakes:

• Assuming duplicate inserts overwrite existing rows
• Thinking NULL can be inserted in primary key
• Believing both rows insert without error

4. Identify the error in the following MySQL table creation statement:

CREATE TABLE orders (
  order_id INT,
  customer_id INT,
  PRIMARY KEY order_id
);

medium

A. No error, statement is correct

B. Primary key cannot be declared separately

C. order_id must be VARCHAR type

D. Missing parentheses around the primary key column

Solution

1. Step 1: Check syntax for separate primary key declaration

   When declaring a primary key separately, the column name(s) must be inside parentheses, like PRIMARY KEY (order_id).

2. Step 2: Identify the error in the statement

   The statement uses PRIMARY KEY order_id without parentheses, causing a syntax error.

3. Final Answer:

   Missing parentheses around the primary key column -> Option D

4. Quick Check:

   Separate primary key needs parentheses [OK]

Hint: Separate primary key needs ( ) around columns [OK]

Common Mistakes:

• Omitting parentheses in separate primary key
• Thinking primary key must be inline only
• Assuming INT type is invalid for primary key

5. You want to create a table employees with a composite primary key consisting of department_id and employee_number. Which is the correct way to declare this primary key?

hard

A. CREATE TABLE employees (department_id INT, employee_number INT, PRIMARY KEY (department_id, employee_number));

B. CREATE TABLE employees (department_id INT PRIMARY KEY, employee_number INT PRIMARY KEY);

C. CREATE TABLE employees (department_id INT, employee_number INT PRIMARY KEY);

D. CREATE TABLE employees (department_id INT, employee_number INT, PRIMARY KEY department_id, employee_number);

Solution

1. Step 1: Understand composite primary key syntax

   A composite primary key is declared by listing multiple columns inside parentheses after PRIMARY KEY.

2. Step 2: Evaluate each option

   CREATE TABLE employees (department_id INT, employee_number INT, PRIMARY KEY (department_id, employee_number)); correctly declares both columns together as a composite primary key. CREATE TABLE employees (department_id INT PRIMARY KEY, employee_number INT PRIMARY KEY); tries to assign two primary keys separately, which is invalid. CREATE TABLE employees (department_id INT, employee_number INT PRIMARY KEY); declares only one column as primary key. CREATE TABLE employees (department_id INT, employee_number INT, PRIMARY KEY department_id, employee_number); has syntax errors missing parentheses.

3. Final Answer:

   CREATE TABLE employees (department_id INT, employee_number INT, PRIMARY KEY (department_id, employee_number)); -> Option A

4. Quick Check:

   Composite key = PRIMARY KEY (col1, col2) [OK]

Hint: Composite keys list columns inside parentheses [OK]

Common Mistakes:

• Declaring multiple primary keys separately
• Missing parentheses for composite keys
• Assigning primary key to only one column