SIMILAR TO for regex-lite matching in PostgreSQL - Time & Space Complexity

Time Complexity: SIMILAR TO for regex-lite matching

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check a pattern using SIMILAR TO grows as the data gets bigger.

How does the matching time change when the text or pattern size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM users
WHERE username SIMILAR TO '%(abc|def)%';
    

This query finds all usernames containing either "abc" or "def" using SIMILAR TO pattern matching.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each username against the SIMILAR TO pattern.
• How many times: Once per row in the users table.

How Execution Grows With Input

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

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

Pattern observation: The work grows directly with the number of rows; doubling rows doubles checks.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "SIMILAR TO uses indexes so it always runs fast no matter how many rows."

[OK] Correct: SIMILAR TO patterns usually require checking each row because indexes don't support this kind of pattern well, so time grows with rows.

Interview Connect

Understanding how pattern matching scales helps you explain query performance and shows you know how databases handle text searches.

Self-Check

"What if we replaced SIMILAR TO with a simple equality check? How would the time complexity change?"

Practice

1. Which of the following best describes the SIMILAR TO operator in PostgreSQL?

easy

A. It matches strings using simple patterns with % and _ wildcards and some regex features.

B. It performs exact string matching without any pattern support.

C. It is used to compare numeric values with tolerance.

D. It matches strings only using full regular expressions.

Solution

1. Step 1: Understand SIMILAR TO purpose

   The SIMILAR TO operator matches strings using patterns that include % (any sequence) and _ (any single character), plus some regex-like features such as + and |.

2. Step 2: Compare options

   It matches strings using simple patterns with % and _ wildcards and some regex features. correctly describes this behavior. Options B, C, and D describe other unrelated behaviors.

3. Final Answer:

   It matches strings using simple patterns with % and _ wildcards and some regex features. -> Option A

4. Quick Check:

   SIMILAR TO = simple pattern matching [OK]

Hint: SIMILAR TO uses % and _ plus simple regex features [OK]

Common Mistakes:

• Confusing SIMILAR TO with full regex matching (~ operator)
• Thinking SIMILAR TO matches exact strings only
• Assuming SIMILAR TO works like numeric comparison

2. Which of the following is the correct syntax to check if column name matches a pattern starting with 'A' followed by any characters using SIMILAR TO?

easy

A. name SIMILAR TO 'A_'

B. name SIMILAR TO '%A'

C. name SIMILAR TO '_A%'

D. name SIMILAR TO 'A%'

Solution

1. Step 1: Understand pattern meaning

   The pattern 'A%' means the string starts with 'A' followed by any sequence of characters.

2. Step 2: Match pattern to options

   name SIMILAR TO 'A%' uses 'A%' which matches strings starting with 'A'. name SIMILAR TO '%A' matches strings ending with 'A'. name SIMILAR TO '_A%' requires second character 'A'. name SIMILAR TO 'A_' matches strings starting with 'A' and exactly one more character.

3. Final Answer:

   name SIMILAR TO 'A%' -> Option D

4. Quick Check:

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

Hint: Use % after 'A' to match any characters after 'A' [OK]

Common Mistakes:

• Using % before 'A' to match start
• Confusing _ with %
• Using wrong pattern length

3. Given the table users(name TEXT) with rows: 'Anna', 'Anny', 'Andy', 'Any', which query returns only names starting with 'An' and ending with 'y' using SIMILAR TO?

medium

A. SELECT name FROM users WHERE name SIMILAR TO 'An%y';

B. SELECT name FROM users WHERE name SIMILAR TO 'An_y';

C. SELECT name FROM users WHERE name SIMILAR TO 'An_y%';

D. SELECT name FROM users WHERE name SIMILAR TO 'An_y_';

Solution

1. Step 1: Analyze pattern requirements

   We want names starting with 'An' and ending with 'y'. The middle can be any number of characters (including zero).

2. Step 2: Check each pattern

   SELECT name FROM users WHERE name SIMILAR TO 'An_y'; 'An_y' matches exactly 4 characters: 'An' + any single char + 'y' (matches 'Anny', 'Andy'; not 'Any'). SELECT name FROM users WHERE name SIMILAR TO 'An%y'; 'An%y' matches starting 'An', any characters in middle, ending with 'y' (matches 'Anny', 'Andy', 'Any'). SELECT name FROM users WHERE name SIMILAR TO 'An_y%'; 'An_y%' requires 4 characters minimum ('An' + single + 'y' + any after), matches 'Anny', 'Andy' (not 'Any'). SELECT name FROM users WHERE name SIMILAR TO 'An_y_'; 'An_y_' requires exactly 5 characters, no match.

3. Final Answer:

   SELECT name FROM users WHERE name SIMILAR TO 'An%y'; -> Option A

4. Quick Check:

   Start 'An', end 'y' = 'An%y' [OK]

Hint: Use % to match any length between start and end [OK]

Common Mistakes:

• Using _ instead of % for variable length
• Forgetting to include ending 'y' in pattern
• Assuming _ matches multiple characters

4. Consider this query: SELECT * FROM products WHERE code SIMILAR TO '[A-Z]+[0-9]'. It returns no rows even though some codes look like 'AB12'. What is the likely problem?

medium

A. The pattern matches only codes with exactly two characters.

B. SIMILAR TO does not support character classes like [A-Z] and [0-9].

C. The pattern should use % and _ instead of + for repetition.

D. The query syntax is invalid and causes an error.

Solution

1. Step 1: Understand SIMILAR TO pattern syntax

   SIMILAR TO supports some regex features but uses % for any sequence and _ for single character. The + operator is supported but character classes like [A-Z] are not fully supported as in full regex.

2. Step 2: Identify correct pattern usage

   Using [A-Z]+ is not valid in SIMILAR TO. Instead, use something like '(A|B|C|...)+'. Also, to match digits, use '[0-9]' carefully or replace with ranges or alternatives. The pattern should be rewritten using % and _ or explicit alternatives.

3. Final Answer:

   The pattern should use % and _ instead of + for repetition. -> Option C

4. Quick Check:

   SIMILAR TO needs %/_ for repetition, not + with classes [OK]

Hint: Use % and _ wildcards, not full regex classes [OK]

Common Mistakes:

• Assuming SIMILAR TO supports full regex syntax
• Using + without proper grouping
• Expecting character classes to work like full regex

5. You want to find all usernames in table users that start with either 'admin' or 'user' followed by exactly 3 digits. Which SIMILAR TO pattern correctly matches this?

hard

A. username SIMILAR TO '(admin|user)[0-9]{3}'

B. username SIMILAR TO '(admin|user)[0-9][0-9][0-9]'

C. username SIMILAR TO '(admin|user)%[0-9][0-9][0-9]'

D. username SIMILAR TO '(admin|user)_[0-9]{3}'

Solution

1. Step 1: Understand SIMILAR TO limitations

   SIMILAR TO supports alternation (|) and grouping with parentheses. However, it does not support {n} repetition syntax like full regex.

2. Step 2: Match exactly 3 digits

   To match exactly 3 digits, write [0-9][0-9][0-9] explicitly instead of [0-9]{3}.

3. Step 3: Check options

   username SIMILAR TO '(admin|user)[0-9]{3}' uses {3} which is invalid in SIMILAR TO. username SIMILAR TO '(admin|user)[0-9][0-9][0-9]' uses explicit three digit classes, correct. username SIMILAR TO '(admin|user)%[0-9][0-9][0-9]' uses % which matches any sequence, so it allows extra characters between prefix and digits, incorrect. username SIMILAR TO '(admin|user)_[0-9]{3}' uses _ which matches one character, but {3} is invalid.

4. Final Answer:

   username SIMILAR TO '(admin|user)[0-9][0-9][0-9]' -> Option B

5. Quick Check:

   Use explicit digit repeats, no {n} in SIMILAR TO [OK]

Hint: Write repeated patterns explicitly; no {n} in SIMILAR TO [OK]

Common Mistakes:

• Using {n} repetition syntax
• Using % wildcard to match exact length
• Confusing _ with digit matching