SUBSTRING extraction in SQL - Time & Space Complexity

Time Complexity: SUBSTRING extraction

O(k)

Understanding Time Complexity

When we extract parts of text from database fields, it is important to know how the work grows as the text gets longer.

We want to understand how the time to get a substring changes when the input text size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT SUBSTRING(description, 1, 10) AS short_desc
FROM products;

This code extracts the first 10 characters from the "description" column for every product.

Identify Repeating Operations

• Primary operation: Extracting a substring from each text field.
• How many times: Once per row in the products table.

How Execution Grows With Input

Extracting a fixed-length substring takes time proportional to the length of the substring, not the full text.

Input Size (length of full text)	Approx. Operations
10	About 10 operations (extract 10 chars)
100	Still about 10 operations (only first 10 chars extracted)
1000	Still about 10 operations (substring length fixed)

Pattern observation: The time depends on the substring length, not the full text length.

Final Time Complexity

Time Complexity: O(k)

This means the time grows with the length of the substring extracted, which is fixed here, so it stays constant regardless of full text size.

Common Mistake

[X] Wrong: "Extracting a substring always takes time proportional to the full text length."

[OK] Correct: The operation only copies the requested substring length, so if that length is fixed, the time does not grow with the full text size.

Interview Connect

Understanding how substring extraction scales helps you reason about text processing in databases, a common task in real projects and interviews.

Self-Check

What if we changed the substring length to be the full length of the text? How would the time complexity change?

Practice

1. What does the SQL function SUBSTRING('Hello World', 7, 5) return?

easy

A. 'Hello W'

B. 'Hello'

C. 'World!'

D. 'World'

Solution

1. Step 1: Understand SUBSTRING parameters

   The function takes the string 'Hello World', starts at position 7, and extracts 5 characters.

2. Step 2: Extract substring from position 7

   Counting characters: H(1) e(2) l(3) l(4) o(5) space(6) W(7) o(8) r(9) l(10) d(11). Starting at 7, 5 characters are 'World'.

3. Final Answer:

   'World' -> Option D

4. Quick Check:

   SUBSTRING('Hello World',7,5) = 'World' [OK]

Hint: Count characters starting at 1, then extract length [OK]

Common Mistakes:

• Starting count at 0 instead of 1
• Extracting fewer or more characters than length
• Including spaces incorrectly

2. Which of the following is the correct syntax to extract 3 characters starting from position 2 in SQL?

easy

A. SUBSTRING('Example', 3)

B. SUBSTRING('Example', 3, 2)

C. SUBSTRING('Example', 2, 3)

D. SUBSTRING('Example', 2)

Solution

1. Step 1: Recall SUBSTRING syntax

   SUBSTRING(string, start_position, length) extracts length characters from start_position.

2. Step 2: Match parameters to requirement

   We want 3 characters starting at position 2, so SUBSTRING('Example', 2, 3) is correct.

3. Final Answer:

   SUBSTRING('Example', 2, 3) -> Option C

4. Quick Check:

   Syntax = SUBSTRING(string, start, length) [OK]

Hint: Syntax is SUBSTRING(string, start, length) [OK]

Common Mistakes:

• Swapping start and length parameters
• Omitting length parameter
• Using zero-based start position

3. Given the table Users with a column username containing 'john_doe123', what is the result of SELECT SUBSTRING(username, 6, 4) FROM Users;?

medium

A. 'doe1'

B. 'doe_'

C. '_doe'

D. 'doe12'

Solution

1. Step 1: Identify substring start and length

   Start at position 6 and extract 4 characters from 'john_doe123'.

2. Step 2: Count characters and extract

   Characters: j(1) o(2) h(3) n(4) _(5) d(6) o(7) e(8) 1(9) 2(10) 3(11). Starting at 6: d(6), o(7), e(8), 1(9) -> 'doe1'.

3. Final Answer:

   'doe1' -> Option A

4. Quick Check:

   SUBSTRING('john_doe123',6,4) = 'doe1' [OK]

Hint: Count characters carefully starting at 1 [OK]

Common Mistakes:

• Starting count at 0
• Extracting wrong number of characters
• Confusing underscore with letter

4. Identify the error in the SQL query: SELECT SUBSTRING('Database', 0, 4);

medium

A. Start position cannot be zero

B. Length cannot be less than 5

C. String must be in double quotes

D. SUBSTRING requires only two parameters

Solution

1. Step 1: Check SUBSTRING start position rules

   In SQL, string positions start at 1, not 0.

2. Step 2: Analyze given query

   Start position is 0, which is invalid and causes an error.

3. Final Answer:

   Start position cannot be zero -> Option A

4. Quick Check:

   Positions start at 1, zero is invalid [OK]

Hint: Start counting at 1, never zero [OK]

Common Mistakes:

• Using zero as start position
• Confusing string quotes
• Wrong number of parameters

5. You have a column product_code with values like 'AB12345XYZ'. Write a SQL query to extract the numeric part (5 digits) starting from position 3. Which query correctly extracts '12345'?

hard

A. SELECT SUBSTRING(product_code, 4, 5) FROM products;

B. SELECT SUBSTRING(product_code, 3, 5) FROM products;

C. SELECT SUBSTRING(product_code, 3, 4) FROM products;

D. SELECT SUBSTRING(product_code, 2, 5) FROM products;

Solution

1. Step 1: Understand the string structure

   'AB12345XYZ' has 'A'(1), 'B'(2), '1'(3), '2'(4), '3'(5), '4'(6), '5'(7), 'X'(8), 'Y'(9), 'Z'(10).

2. Step 2: Extract 5 digits starting at position 3

   Starting at 3, extract 5 characters: '1'(3), '2'(4), '3'(5), '4'(6), '5'(7) -> '12345'.

3. Final Answer:

   SELECT SUBSTRING(product_code, 3, 5) FROM products; -> Option B

4. Quick Check:

   Start=3, length=5 extracts '12345' [OK]

Hint: Count start position carefully, length matches digits needed [OK]

Common Mistakes:

• Starting extraction at wrong position
• Extracting fewer or more characters
• Confusing character positions