Why ordering organizes results in MySQL - Performance Analysis

Time Complexity: Why ordering organizes results

O(n log n)

Understanding Time Complexity

When we ask a database to sort data, it takes some time to arrange the rows in order.

We want to understand how the time needed grows as the amount of data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
ORDER BY last_name ASC;

This query fetches all employees and sorts them by their last name in alphabetical order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the list of employee rows by last_name.
• How many times: The sorting process compares and rearranges rows multiple times depending on the number of rows.

How Execution Grows With Input

As the number of employees grows, the sorting work grows faster than just counting rows.

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

Pattern observation: The work grows faster than the number of rows, roughly multiplying by a bit more than n each time.

Final Time Complexity

Time Complexity: O(n log n)

This means that if you double the number of rows, the sorting work grows a bit more than double, but not as fast as squaring.

Common Mistake

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

[OK] Correct: Sorting needs to compare and arrange rows, so more rows mean more work, not a fixed time.

Interview Connect

Understanding how sorting time grows helps you explain how databases handle ordering efficiently, a useful skill in many real tasks.

Self-Check

"What if we added an index on last_name? How would the time complexity of ordering change?"

Practice

1. What does the ORDER BY clause do in a MySQL query?

easy

A. It groups rows with the same values.

B. It sorts the query results based on one or more columns.

C. It filters rows based on a condition.

D. It limits the number of rows returned.

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.

2. Step 2: Identify the sorting action

   It sorts the results based on one or more columns, either ascending or descending.

3. Final Answer:

   It sorts the query results based on one or more columns. -> Option B

4. Quick Check:

   ORDER BY = Sort results [OK]

Hint: ORDER BY means sorting results by column values [OK]

Common Mistakes:

• Confusing ORDER BY with WHERE filtering
• Thinking ORDER BY limits rows
• Mixing ORDER BY with GROUP BY

2. Which of the following is the correct syntax to sort results in descending order by the column price?

easy

A. SELECT * FROM products ORDER BY price DESC;

B. SELECT * FROM products SORT BY price DESC;

C. SELECT * FROM products ORDER price DESC;

D. SELECT * FROM products ORDER BY price DOWN;

Solution

1. Step 1: Recall correct ORDER BY syntax

   The correct syntax uses ORDER BY followed by the column name and then DESC for descending order.

2. Step 2: Check each option

   Only SELECT * FROM products ORDER BY price DESC; uses the correct keywords and order: ORDER BY price DESC.

3. Final Answer:

   SELECT * FROM products ORDER BY price DESC; -> Option A

4. Quick Check:

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

Hint: Use ORDER BY column DESC for descending sort [OK]

Common Mistakes:

• Using SORT BY instead of ORDER BY
• Omitting BY after ORDER
• Using DOWN instead of DESC

3. Given the table employees with columns id, name, and salary, what will be the order of name in the result of this query?

SELECT name FROM employees ORDER BY salary ASC;

medium

A. Names sorted by salary from lowest to highest.

B. Names in random order.

C. Names sorted alphabetically by name.

D. Names sorted by salary from highest to lowest.

Solution

1. Step 1: Understand ORDER BY salary ASC

   The query sorts rows by the salary column in ascending order, meaning from smallest to largest salary.

2. Step 2: Determine the order of names

   Since the query selects name but orders by salary, the names will appear sorted by their salary from lowest to highest.

3. Final Answer:

   Names sorted by salary from lowest to highest. -> Option A

4. Quick Check:

   ORDER BY salary ASC = lowest to highest [OK]

Hint: ORDER BY column ASC sorts from smallest to largest [OK]

Common Mistakes:

• Assuming ORDER BY sorts by selected column only
• Confusing ASC with DESC
• Thinking order is alphabetical by default

4. Identify the error in this query:

SELECT * FROM orders ORDER BY DESC order_date;

medium

A. ORDER BY cannot be used with the DESC keyword.

B. The query is missing a WHERE clause.

C. The table name 'orders' is misspelled.

D. The DESC keyword is placed before the column name incorrectly.

Solution

1. Step 1: Analyze ORDER BY syntax

   The correct syntax is ORDER BY column_name DESC, where DESC comes after the column name.

2. Step 2: Identify the error in the query

   The query places DESC before the column name, which is incorrect and causes a syntax error.

3. Final Answer:

   The DESC keyword is placed before the column name incorrectly. -> Option D

4. Quick Check:

   DESC must follow column name in ORDER BY [OK]

Hint: DESC always follows the column name in ORDER BY [OK]

Common Mistakes:

• Placing DESC before column name
• Thinking DESC is optional
• Confusing ORDER BY with WHERE clause

5. You want to list products with the highest price first, but if two products have the same price, you want to sort those by name alphabetically. Which query achieves this?

hard

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

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

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

D. SELECT * FROM products ORDER BY price DESC name ASC;

Solution

1. Step 1: Understand sorting priorities

   The main sort should be by price descending to get highest prices first.

2. Step 2: Add secondary sort by name ascending

   For ties in price, sorting by name ascending alphabetically resolves order.

3. Step 3: Check query syntax

   SELECT * FROM products ORDER BY price DESC, name ASC; correctly uses ORDER BY price DESC, name ASC with proper commas and keywords.

4. Final Answer:

   SELECT * FROM products ORDER BY price DESC, name ASC; -> Option C

5. Quick Check:

   ORDER BY price DESC, name ASC = correct multi-level sort [OK]

Hint: Use comma to separate columns in ORDER BY with directions [OK]

Common Mistakes:

• Reversing sort order priorities
• Omitting comma between columns
• Using wrong ASC/DESC for desired order