CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Name when a sort happens in memory (15 minutes)

State the condition under which sorting happens directly in memory, without external sort.

Done when: the data to be sorted fitting entirely in memory is correctly named.

Hint

The data being sorted fits entirely in memory.

Easy 2: Name what satisfies ORDER BY without sorting (15 minutes)

State what kind of existing structure can let a query skip a separate sort step for its ORDER BY clause.

Done when: an index whose key order matches the ORDER BY column is correctly named.

Hint

An index whose key order already matches the ORDER BY column.

Easy 3: Name the execution-plan signal (15 minutes)

State what appears in an execution plan when ORDER BY is not satisfied by an existing index.

Done when: a separate sort step is correctly named.

Hint

A separate sort step.

Medium

Medium 1: Decide if a sort step will appear (25 minutes)

A query orders by placed_on, and an index exists on placed_on. A second, otherwise identical query orders by total_spent, with no index on that column. Decide which query's execution plan will show a separate sort step.

Done when: only the second query is correctly identified as showing a separate sort step.

Hint

Only the second query, ordering by total_spent with no supporting index, will show a separate sort step.

Medium 2: Explain why external sort costs more (25 minutes)

Explain why an external sort is more expensive than an in-memory sort of the same number of rows.

Done when: the explanation correctly notes external sort involves writing sorted chunks to disk and merging them, incurring real disk I/O that an in-memory sort avoids entirely.

Hint

External sort writes sorted chunks to disk and then merges them, incurring real disk I/O that a purely in-memory sort never needs.

Medium 3: Predict when a sort step dominates query cost (30 minutes)

A query finds its matching rows almost instantly via an index, but returns ten million rows with no index on its ORDER BY column. Predict which part of this query is likely to dominate its total cost.

Done when: the sort step is correctly identified as likely dominating, since finding the rows was cheap but sorting ten million unsorted rows is not.

Hint

The sort step, since finding the rows was fast via the index, but sorting ten million unsorted rows afterward is expensive.

Hard

Hard 1: Decide whether adding an index is worth it purely for sorting (30 minutes)

A report runs occasionally and currently incurs an expensive sort step, with no index on the sort column, on a table that is written to very heavily. Decide whether adding an index purely to remove this sort step is a good trade, referencing Level 5's index cost material.

Done when: the decision correctly weighs the occasional report's benefit against the heavy, constant write-maintenance cost the new index would impose, per the "When indexes hurt" page from Level 5, reaching a reasoned conclusion either way.

Hint

The occasional report's benefit must be weighed against the heavy, constant write-maintenance cost on this heavily written table, following the same cost-benefit reasoning as Level 5's "When indexes hurt" page; a reasonable answer could go either way depending on how occasional and how costly each side is.

Hard 2: Explain why an index helps sorting even without a WHERE clause match (35 minutes)

A query has no WHERE clause at all, only ORDER BY placed_on. Explain how an index on placed_on still helps this query, even though it is not being used to filter anything.

Done when: the explanation correctly notes the index's sorted leaf chain directly provides the needed order, letting the database read rows off the index in order and skip a separate sort step, independent of any filtering benefit.

Hint

The index's sorted leaf chain already holds every row in the needed order, so reading straight off the index produces sorted output directly, with no connection to filtering needed for this benefit.

Hard 3: Diagnose a slow query from its execution plan (40 minutes)

An execution plan shows a fast index scan finding a few hundred rows, followed by a sort step reported as the single most expensive part of the plan, sorting a much larger number of rows than the index scan returned. Explain what this combination suggests went wrong.

Done when: the explanation correctly notes this pattern suggests the sort step is sorting a different, larger set of rows than the index scan filtered, such as sorting after a join or union that expanded the row count, and that the ORDER BY column likely needs its own supporting index on the larger result set, or a restructured query.

Hint

The much larger number of sorted rows compared to the index scan's result suggests the sort is happening after an operation, such as a join or union, that expanded the row count, meaning the index on the original column no longer helps; the query may need a different index or restructuring to avoid sorting the expanded set.