WHERE with LIKE pattern matching in SQL - Time & Space Complexity

Time Complexity: WHERE with LIKE pattern matching

O(n)

Understanding Time Complexity

When using WHERE with LIKE in SQL, we want to know how the search time changes as the data grows.

How does the database find matching rows when using pattern matching?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE name LIKE 'A%';
    

This query finds all employees whose names start with the letter 'A'.

Identify Repeating Operations

Look for repeated checks or scans in the query.

• Primary operation: Checking each row's name against the pattern.
• How many times: Once per row in the employees table.

How Execution Grows With Input

As the number of employees grows, the database checks more names.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows in a straight line with the number of rows.

Common Mistake

[X] Wrong: "LIKE with a pattern always uses an index and is very fast."

[OK] Correct: If the pattern starts with a wildcard (like '%abc'), the database cannot use an index efficiently and must check every row.

Interview Connect

Understanding how pattern matching affects search time helps you explain database performance clearly and confidently.

Self-Check

"What if we changed the pattern to '%A'? How would the time complexity change?"

Practice

1. Which SQL clause is used to filter rows based on a pattern in a text column?
SELECT * FROM employees WHERE name LIKE 'A%';

easy

A. GROUP BY

B. ORDER BY

C. WHERE with LIKE

D. JOIN

Solution

1. Step 1: Understand the purpose of LIKE

   The LIKE keyword is used to match text patterns in SQL queries.

2. Step 2: Identify the filtering clause

   The WHERE clause filters rows, and combined with LIKE, it filters rows matching a pattern.

3. Final Answer:

   WHERE with LIKE -> Option C

4. Quick Check:

   WHERE with LIKE = B [OK]

Hint: LIKE is always used with WHERE to filter text patterns [OK]

Common Mistakes:

• Confusing LIKE with GROUP BY
• Using LIKE without WHERE
• Thinking ORDER BY filters rows

2. Which of the following is the correct syntax to find names starting with 'Jo' in a table called users?

easy

A. SELECT * FROM users WHERE name LIKE '%Jo';

B. SELECT * FROM users WHERE name LIKE 'Jo%';

C. SELECT * FROM users WHERE name LIKE '_Jo%';

D. SELECT * FROM users WHERE name LIKE 'Jo_';

Solution

1. Step 1: Understand the pattern for names starting with 'Jo'

   Names starting with 'Jo' means 'Jo' followed by any characters, so pattern is 'Jo%'.

2. Step 2: Match the correct syntax

   SELECT * FROM users WHERE name LIKE 'Jo%'; uses LIKE 'Jo%' which matches names starting with 'Jo'. Others do not match this pattern.

3. Final Answer:

   SELECT * FROM users WHERE name LIKE 'Jo%'; -> Option B

4. Quick Check:

   Start with 'Jo' = LIKE 'Jo%' [OK]

Hint: Use % after text to match any ending characters [OK]

Common Mistakes:

• Using % before text to match start
• Using _ instead of %
• Misplacing wildcards

3. Given the table products with a column product_code, what rows will this query return?

SELECT * FROM products WHERE product_code LIKE '_A%';

medium

A. Rows where product_code starts with 'A'

B. Rows where product_code ends with 'A'

C. Rows where product_code contains 'A' anywhere

D. Rows where product_code has 'A' as the second character

Solution

1. Step 1: Understand the pattern '_A%'

   The underscore (_) matches exactly one character, so the first character can be anything. 'A' is the second character. '%' means any characters after.

2. Step 2: Interpret the query result

   The query returns rows where the second character of product_code is 'A', regardless of the first character or what follows.

3. Final Answer:

   Rows where product_code has 'A' as the second character -> Option D

4. Quick Check:

   _A% means second char is 'A' [OK]

Hint: Use _ for single char, % for any chars [OK]

Common Mistakes:

• Thinking _ matches zero or multiple characters
• Confusing position of 'A' in pattern
• Assuming LIKE matches anywhere without wildcards

4. Identify the error in this SQL query:

SELECT * FROM customers WHERE city LIKE '%York_';

It should find cities ending with 'York' followed by exactly one character.

medium

A. The pattern is correct; no error

B. The underscore should be before 'York' like '_%York'

C. The pattern should be '%York%' to match any after 'York'

D. The underscore should be after 'York' but without % like '%York_'

Solution

1. Step 1: Analyze the pattern '%York_'

   The % matches any characters before 'York', then 'York' literal, then _ matches exactly one character after.

2. Step 2: Check if it matches cities ending with 'York' plus one char

   This pattern correctly matches cities ending with 'York' plus exactly one character, so the query is correct.

3. Final Answer:

   The pattern is correct; no error -> Option A

4. Quick Check:

   '%York_' matches 'York' + 1 char [OK]

Hint: Check if _ and % are placed as intended [OK]

Common Mistakes:

• Thinking _ matches multiple characters
• Confusing placement of % and _
• Assuming pattern must end with %

5. You want to find all employees whose email ends with '.com' but have exactly one character before '.com'. Which query is correct?

hard

A. SELECT * FROM employees WHERE email LIKE '%_.com';

B. SELECT * FROM employees WHERE email LIKE '%_.com%';

C. SELECT * FROM employees WHERE email LIKE '%.__.com';

D. SELECT * FROM employees WHERE email LIKE '%.com';

Solution

1. Step 1: Understand the requirement

   The email should end with '.com' and have exactly one character before '.com'.

2. Step 2: Analyze each pattern

   SELECT * FROM employees WHERE email LIKE '%.com'; matches any email ending with '.com' but no restriction on characters before.
   SELECT * FROM employees WHERE email LIKE '%_.com'; uses '%_.com' meaning any characters, then exactly one character, then '.com' at the end.
   SELECT * FROM employees WHERE email LIKE '%.__.com'; expects two characters before '.com' which is incorrect.
   SELECT * FROM employees WHERE email LIKE '%_.com%'; allows any characters after '.com' which is incorrect for ending.

3. Final Answer:

   SELECT * FROM employees WHERE email LIKE '%_.com'; -> Option A

4. Quick Check:

   Use _ before '.com' for exactly one char [OK]

Hint: Use _ before '.com' to match exactly one char [OK]

Common Mistakes:

• Using % instead of _ for single character
• Placing % after '.com' allowing extra chars
• Miscounting characters before '.com'