ORDER BY with NULLS FIRST and NULLS LAST in PostgreSQL - Time & Space Complexity

Time Complexity: ORDER BY with NULLS FIRST and NULLS LAST

O(n log n)

Understanding Time Complexity

When sorting data in a database, it is important to understand how the sorting time grows as the data grows.

We want to know how adding NULLS FIRST or NULLS LAST affects the sorting time.

Scenario Under Consideration

Analyze the time complexity of this query that sorts data with NULL values:

SELECT id, score
FROM results
ORDER BY score NULLS LAST;
    

This query sorts rows by the score column, placing NULL values at the end.

Identify Repeating Operations

Sorting involves comparing and ordering rows repeatedly.

• Primary operation: Comparing two rows' score values to decide order.
• How many times: Many comparisons happen, depending on the number of rows.

How Execution Grows With Input

Sorting time grows as the number of rows increases, but not simply by doubling.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The number of comparisons grows faster than the number of rows, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as data grows, but it is still efficient for large data sets.

Common Mistake

[X] Wrong: "Adding NULLS FIRST or NULLS LAST makes sorting much slower because it adds extra steps."

[OK] Correct: The NULLS FIRST or NULLS LAST option only changes how NULLs are treated during comparisons, not the overall sorting method or its time complexity.

Interview Connect

Understanding how sorting scales with data size helps you explain query performance clearly and confidently.

Self-Check

What if we added an index on the score column? How would that affect the time complexity of this ORDER BY query?

Practice

1. What does ORDER BY column_name NULLS FIRST do in a PostgreSQL query?

easy

A. It ignores NULL values while sorting by column_name.

B. It sorts the rows by column_name and places NULL values at the end.

C. It causes a syntax error because NULLS FIRST is not valid.

D. It sorts the rows by column_name and places NULL values at the beginning.

Solution

1. Step 1: Understand ORDER BY behavior with NULLS FIRST

   The ORDER BY clause sorts rows by the specified column. Adding NULLS FIRST means any NULL values in that column appear before non-NULL values.

2. Step 2: Confirm the effect on sorting

   So, the rows with NULL in column_name come first, then the rest sorted normally.

3. Final Answer:

   It sorts the rows by column_name and places NULL values at the beginning. -> Option D

4. Quick Check:

   NULLS FIRST means NULLs appear first [OK]

Hint: NULLS FIRST puts empty values at the top of the list [OK]

Common Mistakes:

• Confusing NULLS FIRST with NULLS LAST
• Thinking NULLs are ignored in sorting
• Assuming NULLS FIRST causes errors

2. Which of the following is the correct syntax to sort a table by column score in ascending order with NULL values last?

easy

A. SELECT * FROM table ORDER BY score ASC NULLS LAST;

B. SELECT * FROM table ORDER BY score NULLS LAST ASC;

C. SELECT * FROM table ORDER BY NULLS LAST score ASC;

D. SELECT * FROM table ORDER BY score ASC LAST NULLS;

Solution

1. Step 1: Recall correct ORDER BY syntax with NULLS LAST

   The correct syntax places the column name first, then the sort order (ASC or DESC), followed by NULLS FIRST or NULLS LAST.

2. Step 2: Check each option

   SELECT * FROM table ORDER BY score ASC NULLS LAST; follows this order: score ASC NULLS LAST. Others mix the order or use invalid syntax.

3. Final Answer:

   SELECT * FROM table ORDER BY score ASC NULLS LAST; -> Option A

4. Quick Check:

   Column, order, then NULLS position [OK]

Hint: Order: column, ASC/DESC, then NULLS FIRST/LAST [OK]

Common Mistakes:

• Placing NULLS FIRST/LAST before column name
• Swapping ASC/DESC and NULLS keywords
• Using invalid keyword order causing syntax errors

3. Given the table students with column grade containing values (NULL, 85, 90, NULL, 75), what is the order of grade values after running:
SELECT grade FROM students ORDER BY grade DESC NULLS FIRST;?

medium

A. [NULL, NULL, 90, 85, 75]

B. [90, 85, 75, NULL, NULL]

C. [75, 85, 90, NULL, NULL]

D. [NULL, 90, 85, 75, NULL]

Solution

1. Step 1: Understand DESC with NULLS FIRST

   Sorting by grade DESC means highest grades first. Adding NULLS FIRST places NULL values before all grades.

2. Step 2: Arrange values accordingly

   NULLs come first: [NULL, NULL], then grades in descending order: 90, 85, 75.

3. Final Answer:

   [NULL, NULL, 90, 85, 75] -> Option A

4. Quick Check:

   DESC sorts high to low, NULLS FIRST puts NULLs upfront [OK]

Hint: NULLS FIRST always puts NULLs before sorted values [OK]

Common Mistakes:

• Placing NULLs at the end despite NULLS FIRST
• Sorting grades ascending instead of descending
• Mixing order of NULLs and values

4. You wrote this query but it gives a syntax error:
SELECT * FROM employees ORDER BY salary NULLS FIRST DESC;
What is the error and how to fix it?

medium

A. The column name salary is missing ASC or DESC.

B. NULLS FIRST cannot be used with DESC; remove NULLS FIRST.

C. The order of NULLS FIRST and DESC is wrong; use ORDER BY salary DESC NULLS FIRST.

D. You must use parentheses around NULLS FIRST and DESC.

Solution

1. Step 1: Identify correct keyword order in ORDER BY

   The correct syntax is: column name, then ASC or DESC, then NULLS FIRST or NULLS LAST.

2. Step 2: Fix the query

   Change ORDER BY salary NULLS FIRST DESC to ORDER BY salary DESC NULLS FIRST to fix the syntax error.

3. Final Answer:

   The order of NULLS FIRST and DESC is wrong; use ORDER BY salary DESC NULLS FIRST. -> Option C

4. Quick Check:

   Column, order, then NULLS position [OK]

Hint: Put ASC/DESC before NULLS FIRST/LAST [OK]

Common Mistakes:

• Placing NULLS FIRST before ASC/DESC
• Assuming NULLS FIRST is invalid with DESC
• Missing ASC/DESC keyword

5. You have a table products with a price column containing some NULLs. You want to list products sorted by price ascending, but show NULL prices at the end. Then, for products with the same price, sort by name ascending. Which query achieves this?

hard

A. SELECT * FROM products ORDER BY price NULLS LAST ASC, name ASC;

B. SELECT * FROM products ORDER BY price ASC NULLS LAST, name ASC;

C. SELECT * FROM products ORDER BY price ASC, name ASC NULLS LAST;

D. SELECT * FROM products ORDER BY price ASC NULLS FIRST, name ASC;

Solution

1. Step 1: Sort by price ascending with NULLs last

   Use ORDER BY price ASC NULLS LAST to sort prices low to high and put NULLs at the end.

2. Step 2: Add secondary sort by name ascending

   After sorting by price, add name ASC to sort products with the same price alphabetically.

3. Final Answer:

   SELECT * FROM products ORDER BY price ASC NULLS LAST, name ASC; -> Option B

4. Quick Check:

   Price ASC NULLS LAST, then name ASC [OK]

Hint: Chain ORDER BY: main column with NULLS, then tie-breaker column [OK]

Common Mistakes:

• Placing NULLS LAST before ASC
• Applying NULLS LAST to wrong column
• Using NULLS FIRST instead of NULLS LAST