ORDER BY single column in SQL - Time & Space Complexity

Time Complexity: ORDER BY single column

O(n log n)

Understanding Time Complexity

When we sort data in a database using ORDER BY on one column, the database needs to arrange rows in order. Understanding how the time to sort grows as the data grows helps us know how fast or slow queries might be.

We want to answer: How does sorting time change when the number of rows increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
ORDER BY salary;
    

This query selects all employees and sorts them by their salary in ascending order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of rows by the salary column.
• How many times: The sorting algorithm compares and rearranges rows multiple times, depending on the number of rows.

How Execution Grows With Input

As the number of rows increases, the sorting work grows faster than just adding a few more rows. Sorting usually takes more time than just reading rows one by one.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons and swaps
100	About 600 to 700 comparisons and swaps
1000	About 10,000 to 12,000 comparisons and swaps

Pattern observation: When the number of rows grows 10 times, the sorting work grows roughly 10 times more than that, showing a faster growth than just linear.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes a bit more than just looking at each row once; it grows a little faster as the data grows bigger.

Common Mistake

[X] Wrong: "Sorting with ORDER BY takes the same time no matter how many rows there are."

[OK] Correct: Sorting needs to compare and rearrange rows, so more rows mean more work, and the time grows faster than just the number of rows.

Interview Connect

Knowing how sorting time grows helps you explain query performance clearly. It shows you understand how databases handle data and can help you write better queries or explain why some queries take longer.

Self-Check

"What if we added an index on the salary column? How would the time complexity of sorting change?"

Practice

1. What does the SQL clause ORDER BY do when used with a single column?

easy

A. It deletes rows that have duplicate values in that column.

B. It filters the rows to only show those with unique values in that column.

C. It groups the rows by the values in that column.

D. It sorts the query results based on the values in that column.

Solution

1. Step 1: Understand the purpose of ORDER BY

   The ORDER BY clause is used to arrange the rows returned by a query in a specific order based on one or more columns.

2. Step 2: Focus on single column sorting

   When used with a single column, it sorts the results either ascending (default) or descending based on that column's values.

3. Final Answer:

   It sorts the query results based on the values in that column. -> Option D

4. Quick Check:

   ORDER BY = Sort results [OK]

Hint: ORDER BY arranges rows by column values [OK]

Common Mistakes:

• Confusing ORDER BY with filtering or grouping
• Thinking ORDER BY removes duplicates
• Assuming ORDER BY changes data in the table

2. Which of the following is the correct syntax to sort the table Employees by the column LastName in ascending order?

easy

A. SELECT * FROM Employees ORDER BY LastName DESC;

B. SELECT * FROM Employees SORT BY LastName;

C. SELECT * FROM Employees ORDER BY LastName ASC;

D. SELECT * FROM Employees ORDER LastName;

Solution

1. Step 1: Recall correct ORDER BY syntax

   The correct syntax to sort results is ORDER BY column_name. To specify ascending order, use ASC (which is also default).

2. Step 2: Check each option

   SELECT * FROM Employees ORDER BY LastName ASC; uses correct syntax with ORDER BY LastName ASC. SELECT * FROM Employees SORT BY LastName; uses invalid keyword SORT BY. SELECT * FROM Employees ORDER LastName; misses BY. SELECT * FROM Employees ORDER BY LastName DESC; sorts descending, not ascending.

3. Final Answer:

   SELECT * FROM Employees ORDER BY LastName ASC; -> Option C

4. Quick Check:

   ORDER BY + column + ASC = correct syntax [OK]

Hint: Use ORDER BY column ASC for ascending sort [OK]

Common Mistakes:

• Using SORT BY instead of ORDER BY
• Omitting BY keyword
• Confusing ASC with DESC

3. Given the table Products with columns ProductID and Price, what will be the order of ProductID after running this query?

SELECT ProductID FROM Products ORDER BY Price DESC;

Assume the data:
ProductID: 1, 2, 3
Price: 10, 30, 20

medium

A. [1, 3, 2]

B. [2, 3, 1]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Understand ORDER BY Price DESC

   The query sorts rows by Price in descending order, so highest price first.

2. Step 2: Sort the data by Price descending

   Prices are 10 (ProductID 1), 30 (ProductID 2), 20 (ProductID 3). Descending order: 30, 20, 10. Corresponding ProductIDs: 2, 3, 1.

3. Final Answer:

   [2, 3, 1] -> Option B

4. Quick Check:

   Price DESC sorts highest to lowest [OK]

Hint: Sort by column DESC to get highest values first [OK]

Common Mistakes:

• Mixing ascending and descending order
• Sorting by ProductID instead of Price
• Assuming default ascending order

4. Identify the error in this SQL query:

SELECT Name FROM Customers ORDER LastName;

medium

A. Missing BY keyword after ORDER

B. ORDER BY cannot be used with SELECT

C. Name column does not exist

D. ORDER BY requires two columns

Solution

1. Step 1: Check ORDER BY syntax

   The correct syntax requires the keyword BY after ORDER. The query uses ORDER LastName which is invalid.

2. Step 2: Verify other parts

   The SELECT statement is valid, and Name is assumed to exist. ORDER BY can be used with SELECT. Only one column is needed for ORDER BY.

3. Final Answer:

   Missing BY keyword after ORDER -> Option A

4. Quick Check:

   ORDER BY requires BY keyword [OK]

Hint: ORDER BY must include BY keyword [OK]

Common Mistakes:

• Omitting BY after ORDER
• Thinking ORDER BY needs multiple columns
• Assuming ORDER BY can't be used with SELECT

5. You have a table Students with columns StudentID, Name, and Score. You want to list all students ordered by their Score from highest to lowest, but if two students have the same score, order them alphabetically by Name. Which query correctly achieves this?

hard

A. SELECT * FROM Students ORDER BY Score DESC, Name ASC;

B. SELECT * FROM Students ORDER BY Name ASC, Score DESC;

C. SELECT * FROM Students ORDER BY Score ASC, Name DESC;

D. SELECT * FROM Students ORDER BY Score DESC;

Solution

1. Step 1: Understand sorting requirements

   Primary sort is by Score descending (highest first). Secondary sort for ties is by Name ascending (alphabetical).

2. Step 2: Analyze each option

   SELECT * FROM Students ORDER BY Score DESC, Name ASC; orders by Score DESC then Name ASC, matching requirements. SELECT * FROM Students ORDER BY Name ASC, Score DESC; reverses order priorities. SELECT * FROM Students ORDER BY Score ASC, Name DESC; sorts Score ascending and Name descending, wrong directions. SELECT * FROM Students ORDER BY Score DESC; only sorts by Score DESC, no tie-breaker.

3. Final Answer:

   SELECT * FROM Students ORDER BY Score DESC, Name ASC; -> Option A

4. Quick Check:

   ORDER BY primary DESC, secondary ASC for tie-break [OK]

Hint: Use ORDER BY primary DESC, secondary ASC for tie-breaks [OK]

Common Mistakes:

• Reversing sort order directions
• Not adding secondary column for tie-break
• Using only one column when two are needed