BETWEEN for range filtering in PostgreSQL - Time & Space Complexity

Time Complexity: BETWEEN for range filtering

O(n)

Understanding Time Complexity

When we use BETWEEN to filter rows in a database, we want to know how the time to get results changes as the data grows.

We ask: How does the query speed change when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM orders
WHERE order_date BETWEEN '2023-01-01' AND '2023-01-31';
    

This query selects all orders placed in January 2023 by checking if the order_date falls within the given range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row's order_date to check if it falls in the range.
• How many times: Once for each row in the orders table.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "BETWEEN instantly finds the rows without checking many entries."

[OK] Correct: Without an index, the database must look at each row to see if it fits the range.

Interview Connect

Understanding how range filters like BETWEEN scale helps you explain query performance clearly and shows you know how databases handle data.

Self-Check

"What if we add an index on order_date? How would the time complexity change?"

Practice

1. What does the BETWEEN operator do in PostgreSQL?

easy

A. Filters rows where a column's value is NULL.

B. Filters rows where a column's value is exactly equal to a single value.

C. Filters rows where a column's value is within a specified range, inclusive.

D. Filters rows where a column's value is outside a specified range.

Solution

1. Step 1: Understand the purpose of BETWEEN

   The BETWEEN operator checks if a value lies between two given values, including both ends.

2. Step 2: Compare with other filtering options

   Unlike equality or NULL checks, BETWEEN covers a range inclusively.

3. Final Answer:

   Filters rows where a column's value is within a specified range, inclusive. -> Option C

4. Quick Check:

   BETWEEN means inclusive range filter [OK]

Hint: BETWEEN includes both range ends, like a closed interval [OK]

Common Mistakes:

• Thinking BETWEEN excludes the range ends
• Confusing BETWEEN with equality (=)
• Assuming BETWEEN works only with numbers

2. Which of the following is the correct syntax to select rows where the column age is between 18 and 30 (inclusive)?

easy

A. SELECT * FROM users WHERE age BETWEEN 18 TO 30;

B. SELECT * FROM users WHERE age BETWEEN 18 AND 30;

C. SELECT * FROM users WHERE age >= 18 AND <= 30;

D. SELECT * FROM users WHERE age IN BETWEEN (18, 30);

Solution

1. Step 1: Recall correct BETWEEN syntax

   The correct syntax uses BETWEEN followed by the lower and upper bounds separated by AND.

2. Step 2: Check each option

   SELECT * FROM users WHERE age BETWEEN 18 AND 30; uses BETWEEN 18 AND 30 correctly; others have syntax errors or wrong keywords.

3. Final Answer:

   SELECT * FROM users WHERE age BETWEEN 18 AND 30; -> Option B

4. Quick Check:

   BETWEEN ... AND ... is correct syntax [OK]

Hint: BETWEEN always uses AND, not TO or commas [OK]

Common Mistakes:

• Using TO instead of AND
• Using incomplete comparison operators
• Misplacing parentheses or commas

3. Given the table orders with a column order_date of type DATE, what will this query return?

SELECT order_id FROM orders WHERE order_date BETWEEN '2023-01-01' AND '2023-01-31';

medium

A. Orders placed exactly on January 1, 2023, only.

B. All orders placed before January 1, 2023.

C. All orders placed after January 31, 2023.

D. All orders placed from January 1, 2023, to January 31, 2023, inclusive.

Solution

1. Step 1: Understand the BETWEEN date range

   The query filters orders where order_date is between '2023-01-01' and '2023-01-31', including both dates.

2. Step 2: Interpret the result set

   It returns all orders placed on any date from January 1 to January 31, 2023, inclusive.

3. Final Answer:

   All orders placed from January 1, 2023, to January 31, 2023, inclusive. -> Option D

4. Quick Check:

   BETWEEN includes both start and end dates [OK]

Hint: BETWEEN dates includes both start and end days [OK]

Common Mistakes:

• Assuming BETWEEN excludes the end date
• Confusing BETWEEN with less than or greater than only
• Thinking it returns only one date

4. Identify the error in this query:

SELECT * FROM products WHERE price BETWEEN 100, 500;

medium

A. The BETWEEN clause uses a comma instead of AND between values.

B. The price column cannot be used with BETWEEN.

C. BETWEEN requires parentheses around the values.

D. The query is correct and will run without errors.

Solution

1. Step 1: Check BETWEEN syntax

   BETWEEN requires two values separated by AND, not a comma.

2. Step 2: Identify the syntax error

   The query uses a comma between 100 and 500, which is invalid syntax.

3. Final Answer:

   The BETWEEN clause uses a comma instead of AND between values. -> Option A

4. Quick Check:

   BETWEEN needs AND, not commas [OK]

Hint: BETWEEN always uses AND, never commas [OK]

Common Mistakes:

• Using commas instead of AND
• Adding unnecessary parentheses
• Assuming BETWEEN works with any separator

5. You want to find all employees hired between January 1, 2020, and December 31, 2022, but exclude those hired exactly on January 1, 2020. Which query achieves this?

hard

A. All of the above queries will work correctly.

B. SELECT * FROM employees WHERE hire_date > '2020-01-01' AND hire_date <= '2022-12-31';

C. SELECT * FROM employees WHERE hire_date BETWEEN '2020-01-02' AND '2022-12-31';

D. SELECT * FROM employees WHERE hire_date BETWEEN '2020-01-01' AND '2022-12-31' AND hire_date <> '2020-01-01';

Solution

1. Step 1: Understand the requirement

   We want employees hired after January 1, 2020, up to December 31, 2022, excluding January 1, 2020 itself.

2. Step 2: Analyze each query

   SELECT * FROM employees WHERE hire_date BETWEEN '2020-01-01' AND '2022-12-31' AND hire_date <> '2020-01-01'; uses BETWEEN including '2020-01-01' but excludes it with <> condition.
   SELECT * FROM employees WHERE hire_date > '2020-01-01' AND hire_date <= '2022-12-31'; uses > and <= to exclude '2020-01-01' naturally.
   SELECT * FROM employees WHERE hire_date BETWEEN '2020-01-02' AND '2022-12-31'; shifts the BETWEEN range to start from '2020-01-02', excluding '2020-01-01'.

3. Step 3: Confirm all queries meet the condition

   All three queries exclude '2020-01-01' and include dates up to '2022-12-31'.

4. Final Answer:

   All of the above queries will work correctly. -> Option A

5. Quick Check:

   Multiple ways to exclude start date in range [OK]

Hint: Exclude start date by > or adjust BETWEEN start or add <> [OK]

Common Mistakes:

• Assuming BETWEEN excludes start date by default
• Using BETWEEN without excluding the start date
• Confusing BETWEEN with exclusive range