LIKE pattern matching in MySQL - Time & Space Complexity

Time Complexity: LIKE pattern matching

O(n)

Understanding Time Complexity

When searching text in a database, LIKE pattern matching helps find rows that fit a pattern.

We want to understand how the search time changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM products
WHERE product_name LIKE '%phone%';
    

This query finds all products with "phone" anywhere in their name.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's product_name against the pattern.
• How many times: Once for every row in the products table.

How Execution Grows With Input

As the number of rows grows, the database checks more product names one by one.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the search time grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "LIKE with % in front is fast because it uses indexes."

[OK] Correct: When % is at the start, indexes usually can't help, so the database checks every row.

Interview Connect

Understanding how pattern searches scale helps you explain database performance clearly and confidently.

Self-Check

"What if the pattern was 'phone%' instead of '%phone%'? How would the time complexity change?"

Practice

1. What does the % symbol represent in a MySQL LIKE pattern?

easy

A. Any sequence of zero or more characters

B. Exactly one character

C. A digit from 0 to 9

D. A special character like @ or #

Solution

1. Step 1: Understand the role of % in LIKE

   The % symbol in a LIKE pattern matches any sequence of characters, including an empty sequence.

2. Step 2: Compare with other wildcard symbols

   The _ symbol matches exactly one character, not a sequence. % is for zero or more characters.

3. Final Answer:

   Any sequence of zero or more characters -> Option A

4. Quick Check:

   % means any characters [OK]

Hint: Remember % means many chars, _ means one char [OK]

Common Mistakes:

• Confusing % with _
• Thinking % matches only one character
• Assuming % matches digits only

2. Which of the following is the correct syntax to find names starting with 'Jo' using LIKE in MySQL?

easy

A. WHERE name LIKE 'Jo%'

B. WHERE name LIKE '%Jo'

C. WHERE name LIKE '_Jo%'

D. WHERE name LIKE 'Jo_'

Solution

1. Step 1: Identify pattern for names starting with 'Jo'

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

2. Step 2: Check each option

   WHERE name LIKE 'Jo%' uses 'Jo%' which matches strings starting with 'Jo'. Others do not match this pattern correctly.

3. Final Answer:

   WHERE name LIKE 'Jo%' -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Putting % before 'Jo' instead of after
• Using _ instead of %
• Misplacing wildcards

3. Given a table users with a column email, what will this query return?

SELECT email FROM users WHERE email LIKE '%@gmail._om';

medium

A. Emails containing '@gmail' anywhere

B. Emails ending exactly with '@gmail._om' string

C. Emails ending with '@gmail.com' or '@gmail.dom' etc. (one char before 'om')

D. Emails starting with '@gmail' and ending with 'om'

Solution

1. Step 1: Analyze the pattern '%@gmail._om'

   The % matches any characters before '@gmail.', then _ matches exactly one character, then 'om' follows.

2. Step 2: Understand what emails match

   Emails ending with '@gmail.com', '@gmail.dom', '@gmail.xom' etc. match because _ matches one character before 'om'.

3. Final Answer:

   Emails ending with '@gmail.com' or '@gmail.dom' etc. (one char before 'om') -> Option C

4. Quick Check:

   _ matches one char before 'om' [OK]

Hint: Use _ for exactly one char, % for many chars [OK]

Common Mistakes:

• Thinking _ matches zero or many characters
• Ignoring the position of _ in pattern
• Assuming % matches only one character

4. You wrote this query but it returns no rows:

SELECT * FROM products WHERE name LIKE 'TV_';

What is the likely problem?

medium

A. The underscore _ is not a valid wildcard in LIKE

B. The pattern should be 'TV%' to match names starting with 'TV'

C. The query should use = instead of LIKE

D. The pattern 'TV_' matches only names with exactly 3 characters starting with 'TV'

Solution

1. Step 1: Understand the pattern 'TV_'

   The pattern 'TV_' matches strings starting with 'TV' and exactly one more character, so total length 3.

2. Step 2: Reason why no rows returned

   If no product names are exactly 3 characters starting with 'TV', no rows match. Longer names like 'TVS' or 'TV42' won't match.

3. Final Answer:

   The pattern 'TV_' matches only names with exactly 3 characters starting with 'TV' -> Option D

4. Quick Check:

   _ means exactly one char [OK]

Hint: Remember _ matches exactly one char, so length matters [OK]

Common Mistakes:

• Thinking _ matches zero or many characters
• Using LIKE incorrectly with =
• Assuming 'TV_' matches longer names

5. You want to find all customers whose phone numbers start with '555' and have exactly 10 digits total. Which query correctly uses LIKE?

hard

A. SELECT * FROM customers WHERE phone LIKE '555________';

B. SELECT * FROM customers WHERE phone LIKE '555_______';

C. SELECT * FROM customers WHERE phone LIKE '555_________';

D. SELECT * FROM customers WHERE phone LIKE '555%';

Solution

1. Step 1: Understand the requirement

   Phone numbers start with '555' and have exactly 10 digits total, so 3 fixed digits + 7 more digits.

2. Step 2: Count underscores needed

   Each underscore _ matches exactly one character. After '555', we need 7 underscores to make total length 10.

3. Step 3: Check options

   SELECT * FROM customers WHERE phone LIKE '555_______'; has '555' plus 7 underscores, matching exactly 10 characters. Others have wrong underscore counts or use % which allows variable length.

4. Final Answer:

   SELECT * FROM customers WHERE phone LIKE '555_______'; -> Option B

5. Quick Check:

   7 underscores after '555' = 10 chars total [OK]

Hint: Count underscores to match exact length after prefix [OK]

Common Mistakes:

• Using % which allows variable length
• Using wrong number of underscores
• Confusing _ with %