Regular expression matching (~ operator) in PostgreSQL - Time & Space Complexity

Time Complexity: Regular expression matching (~ operator)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check if text matches a pattern grows as the text gets longer.

How does the matching process scale when the input text size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM documents
WHERE content ~ '^[A-Z0-9]*$';
    

This query finds all rows where the content column matches a pattern: only uppercase letters and digits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regular expression engine checks each character in the content string to see if it fits the pattern.
• How many times: For each row, it scans through the content string characters once, from start to end or until a mismatch is found.

How Execution Grows With Input

As the length of the content string grows, the time to check the pattern grows roughly in proportion to the string length.

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

Pattern observation: The work grows linearly as the string gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows in a straight line with the length of the text being checked.

Common Mistake

[X] Wrong: "Regular expression matching always takes the same time no matter how long the text is."

[OK] Correct: The engine usually checks each character, so longer text means more work and more time.

Interview Connect

Understanding how pattern matching time grows helps you write efficient queries and explain performance in real projects.

Self-Check

"What if the regular expression included a wildcard that can match many characters? How would that affect the time complexity?"

Practice

1. What does the PostgreSQL operator ~ do when used in a query like column_name ~ 'pattern'?

easy

A. Returns the length of the column value

B. Replaces the column value with the pattern

C. Checks if the column value matches the regular expression pattern

D. Counts the number of times the pattern appears in the column

Solution

1. Step 1: Understand the ~ operator

   The ~ operator in PostgreSQL is used to check if a string matches a regular expression pattern.

2. Step 2: Apply to the query context

   When used as column_name ~ 'pattern', it returns true if the column's value matches the pattern, otherwise false.

3. Final Answer:

   Checks if the column value matches the regular expression pattern -> Option C

4. Quick Check:

   ~ means match pattern [OK]

Hint: Remember: ~ means 'matches pattern' in PostgreSQL [OK]

Common Mistakes:

• Thinking ~ replaces or modifies data
• Confusing ~ with counting occurrences
• Assuming ~ returns string length

2. Which of the following is the correct syntax to find rows where the column email contains the domain example.com using the ~ operator?

easy

A. SELECT * FROM users WHERE email ~ 'example.com';

B. SELECT * FROM users WHERE email ~ '@example\.com$';

C. SELECT * FROM users WHERE email LIKE '%example.com%';

D. SELECT * FROM users WHERE email = '~example.com';

Solution

1. Step 1: Understand the pattern for matching domain

   To match emails ending with '@example.com', the regex should be @example\.com$ where \. escapes the literal dot and $ means end of string.

2. Step 2: Check the syntax of the ~ operator usage

   The correct syntax is email ~ '@example\.com$' to find emails ending with that domain.

3. Final Answer:

   SELECT * FROM users WHERE email ~ '@example\.com$'; -> Option B

4. Quick Check:

   Regex match with ~ and end anchor [OK]

Hint: Use $ to anchor regex at string end with ~ operator [OK]

Common Mistakes:

• Using LIKE instead of ~ for regex matching
• Missing anchors like $ for exact domain match
• Using = operator with regex pattern

3. Given the table products with a column code containing values: 'A123', 'B234', 'A345', 'C456', what will the query SELECT code FROM products WHERE code ~ '^A'; return?

medium

A. A123, A345

B. B234, C456

C. All codes

D. No rows

Solution

1. Step 1: Understand the regex pattern ^A

   The caret ^ means the string must start with 'A'.

2. Step 2: Apply pattern to each code

   Codes starting with 'A' are 'A123' and 'A345'.

3. Final Answer:

   A123, A345 -> Option A

4. Quick Check:

   ^ means start with 'A' [OK]

Hint: ^ anchors regex to start of string [OK]

Common Mistakes:

• Confusing ^ with end anchor $
• Expecting all rows to match
• Ignoring regex anchors

4. You wrote the query SELECT * FROM users WHERE username ~ '*'; but it returns an error. What is the most likely cause?

medium

A. The regex pattern is missing escape characters for special symbols

B. The ~ operator requires the pattern to be enclosed in double quotes

C. The regex pattern is invalid because it lacks anchors

D. The pattern is correct but the column contains NULL values causing error

Solution

1. Step 1: Check regex pattern syntax

   The pattern * is invalid because the * quantifier requires a preceding atom (e.g., a character or group).

2. Step 2: Identify common error with special characters

   Regex special symbols like *, +, ? need escape characters (e.g., \* in SQL string) when used literally.

3. Final Answer:

   The regex pattern is missing escape characters for special symbols -> Option A

4. Quick Check:

   Escape special regex chars in SQL strings [OK]

Hint: Escape special regex characters properly in SQL strings [OK]

Common Mistakes:

• Using single quotes incorrectly for regex
• Assuming ~ needs double quotes
• Ignoring NULL values causing errors

5. You want to select all rows from orders where the order_id starts with a letter followed by exactly three digits. Which query using the ~ operator is correct?

hard

A. SELECT * FROM orders WHERE order_id ~ '^\w{4}$';

B. SELECT * FROM orders WHERE order_id ~ '^[0-9]{3}[A-Za-z]$';

C. SELECT * FROM orders WHERE order_id ~ '[A-Za-z][0-9]{3}';

D. SELECT * FROM orders WHERE order_id ~ '^[A-Za-z][0-9]{3}$';

Solution

1. Step 1: Understand the pattern requirements

   The order_id must start with a letter [A-Za-z] followed by exactly three digits [0-9]{3}, and nothing else.

2. Step 2: Check regex anchors and pattern

   Using ^ and $ anchors ensures the entire string matches. '^[A-Za-z][0-9]{3}$' matches a letter then three digits exactly.

3. Final Answer:

   SELECT * FROM orders WHERE order_id ~ '^[A-Za-z][0-9]{3}$'; -> Option D

4. Quick Check:

   ^ and $ anchor full string match [OK]

Hint: Use ^ and $ to match entire string pattern [OK]

Common Mistakes:

• Swapping letter and digit order
• Missing anchors causing partial matches
• Using \w which includes digits and letters