Substring and overlay functions in PostgreSQL - Time & Space Complexity

Time Complexity: Substring and overlay functions

O(n)

Understanding Time Complexity

We want to understand how the time to extract or replace parts of text grows as the text gets longer.

How does the work change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT substring(text_column FROM 5 FOR 10) AS part,
       overlay(text_column PLACING 'new' FROM 3 FOR 4) AS replaced
FROM example_table;
    

This code extracts a part of the text and replaces a part of the text in each row.

Identify Repeating Operations

Look for repeated work done by the functions.

• Primary operation: Scanning the input string to find and extract or replace the substring.
• How many times: Once per row in the table, each operation processes a portion of the string.

How Execution Grows With Input

As the input string gets longer, the functions need to look through more characters.

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 roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to extract or replace grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Substring and overlay run instantly no matter how long the string is."

[OK] Correct: The functions must check characters to find the right part, so longer strings take more time.

Interview Connect

Understanding how string functions scale helps you write efficient queries and explain performance clearly.

Self-Check

"What if we used substring with a pattern match instead of fixed positions? How would the time complexity change?"

Practice

1. What does the PostgreSQL substring function do when given a string and a start position?

easy

A. Returns the length of the string

B. Extracts part of the string starting from the given position to the end

C. Replaces part of the string starting from the given position

D. Converts the string to uppercase

Solution

1. Step 1: Understand substring function purpose

   The substring function extracts a portion of a string starting at a specified position.

2. Step 2: Analyze given parameters

   When only a start position is given, substring returns from that position to the end of the string.

3. Final Answer:

   Extracts part of the string starting from the given position to the end -> Option B

4. Quick Check:

   substring extracts substring from position [OK]

Hint: Substring cuts string from start position to end if length missing [OK]

Common Mistakes:

• Confusing substring with overlay
• Thinking substring replaces text
• Assuming substring returns string length

2. Which of the following is the correct syntax to replace part of a string using the overlay function in PostgreSQL?

easy

A. overlay(string placing new_substring from start for length)

B. overlay(string from start for length placing new_substring)

C. overlay(string for length from start placing new_substring)

D. overlay(new_substring placing string from start for length)

Solution

1. Step 1: Recall overlay syntax

   The correct syntax is overlay(string placing new_substring from start for length).

2. Step 2: Match options to syntax

   overlay(string placing new_substring from start for length) matches the correct order: string placing new_substring from start for length.

3. Final Answer:

   overlay(string placing new_substring from start for length) -> Option A

4. Quick Check:

   Overlay syntax = string placing new_substring from start for length [OK]

Hint: Remember: overlay(string placing new from start for length) [OK]

Common Mistakes:

• Mixing order of 'from' and 'placing'
• Omitting 'for length' keyword
• Swapping string and new_substring positions

3. What is the result of this query?
SELECT overlay('abcdef' placing 'XYZ' from 2 for 3);

medium

A. 'abXYZf'

B. 'aXYZdef'

C. 'XYZdef'

D. 'aXYZef'

Solution

1. Step 1: Understand overlay parameters

   We replace 3 characters starting at position 2 in 'abcdef' with 'XYZ'. Positions start at 1.

2. Step 2: Apply replacement

   Characters at positions 2,3,4 ('b','c','d') are replaced by 'XYZ', resulting in 'aXYZef'.

3. Final Answer:

   'aXYZef' -> Option D

4. Quick Check:

   Overlay replaces substring from pos 2 length 3 with 'XYZ' [OK]

Hint: Overlay replaces exact length starting at position [OK]

Common Mistakes:

• Replacing wrong substring length
• Starting replacement at wrong position
• Appending instead of replacing

4. Identify the error in this query:
SELECT overlay('hello' placing 'y' for 2 from 3);

medium

A. String literals not quoted

B. Missing length parameter

C. Incorrect order of 'for' and 'from' keywords

D. Overlay function does not exist

Solution

1. Step 1: Check overlay syntax order

   The correct syntax is overlay(string placing new_substring from start for length). The query uses 'placing' then 'for' then 'from', which is wrong order.

2. Step 2: Identify error cause

   The keywords 'for' and 'from' are swapped, causing syntax error.

3. Final Answer:

   Incorrect order of 'for' and 'from' keywords -> Option C

4. Quick Check:

   Overlay syntax order matters: from then for then placing [OK]

Hint: Overlay syntax: from before for before placing [OK]

Common Mistakes:

• Swapping 'for' and 'from' keywords
• Omitting quotes around strings
• Using overlay without required keywords

5. Given the string 'PostgreSQL', which query correctly replaces 'gre' with 'XYZ' using overlay and then extracts the substring starting at position 5 with length 4?

hard

A. SELECT substring(overlay('PostgreSQL' placing 'XYZ' from 5 for 3) from 5 for 4);

B. SELECT substring(overlay('PostgreSQL' from 5 for 3 placing 'XYZ') from 5 for 4);

C. SELECT overlay(substring('PostgreSQL' from 5 for 3) placing 'XYZ' from 5 for 4);

D. SELECT overlay('PostgreSQL' from 5 for 4 placing 'XYZ');

Solution

1. Step 1: Replace 'gre' with 'XYZ' using overlay

   'gre' starts at position 5 and has length 3. Correct overlay syntax is overlay(string placing new_substring from start for length). SELECT substring(overlay('PostgreSQL' placing 'XYZ' from 5 for 3) from 5 for 4); matches this.

2. Step 2: Extract substring from position 5 length 4

   Apply substring on the result starting at position 5 for length 4. SELECT substring(overlay('PostgreSQL' placing 'XYZ' from 5 for 3) from 5 for 4); applies substring correctly after overlay.

3. Final Answer:

   SELECT substring(overlay('PostgreSQL' placing 'XYZ' from 5 for 3) from 5 for 4); -> Option A

4. Quick Check:

   Overlay then substring with correct syntax = SELECT substring(overlay('PostgreSQL' placing 'XYZ' from 5 for 3) from 5 for 4); [OK]

Hint: Overlay syntax: placing after string, then substring after overlay [OK]

Common Mistakes:

• Mixing overlay keyword order
• Applying substring before overlay
• Wrong positions or lengths in functions