CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 8 of 8 · 4 min read

Exercises

Easy

Easy 1: Scan against lookup (20 minutes)

A table has 50 million rows. A scan reads 2 million rows per second. An index lookup needs 4 page reads of 0.2 ms each. Find the time for each, the ratio, and the work per second at 100 lookups a second.

Done when: two times, a ratio and two work figures.

Hint

Time = rows ÷ rows per second, or reads × time per read.

Easy 2: Is it selective (20 minutes)

For a table of 20 million rows, judge each column: country (190 values), email (all different), is_active (2 values, 95 percent true), order_id. Say whether an index helps a query that fixes one value.

Done when: four verdicts, each with the number of rows matched per value.

Hint

Rows per value = rows ÷ distinct values.

Easy 3: Which queries use it (20 minutes)

An index exists on (country, city, name). Say which queries can use it: country = 'IN', city = 'Pune', country = 'IN' AND city = 'Pune', country = 'IN' AND name = 'Asha'.

Done when: four answers, each with the prefix it uses.

Hint

Look at the columns from the left; a gap breaks the prefix.

Medium

Medium 1: Design the index (30 minutes)

A messaging app shows the newest 50 messages of a conversation and also counts unread messages for a user. Write the two queries, and choose indexes. State the leftmost prefix each uses.

Done when: two queries, two or fewer indexes, and the order of columns defended.

Hint

For the unread count, think of the filter columns first.

Medium 2: Write cost (30 minutes)

A table receives 3,000 inserts and 1,000 updates per second. It has the primary key and 3 secondary indexes. An update changes one indexed column. Count the write operations a second. Then count them with one secondary index fewer.

Done when: two totals with the working shown.

Hint

An updated indexed column costs a delete plus an insert in that index.

Medium 3: Memory for indexes (30 minutes)

A table has 80 million rows and 5 secondary indexes with 28 bytes per entry. Find the size of the indexes. A server has 32 GB of memory and the database may use 60 percent of it for caching. Do the indexes fit? What can be done if not?

Done when: a size in GB, a verdict and two actions.

Hint

Rows × bytes × number of indexes, then convert to GB.

Hard

Hard 1: Fix the slow page (45 minutes)

A page lists a seller's open orders in a city, newest first, 20 at a time: WHERE seller_id = ? AND status = 'open' AND city = ? ORDER BY created_at DESC. The table has 100 million rows, 2 million sellers and 5 statuses. Propose a composite index, explain the column order, estimate the rows read, and show how cursor paging (Level 1, module 2) works with it.

Done when: an index definition, the reason for the order, a row estimate and a paging query.

Hint

Equalities first, the sort column last.

Hard 2: Nearby places (45 minutes)

A map app stores 5 million places with latitude and longitude and must return the places in a viewing rectangle. Compare a B-tree on latitude, a B-tree on longitude, a geohash prefix search and an R-tree. For each, say how many rows may need to be checked if the rectangle holds about 400 places and the rows in the latitude strip are 20,000.

Done when: a table of four options with the rows checked, strengths and weaknesses.

Hint

The strip rows are those a one-dimensional index must read and then filter.

Hard 3: Index audit (50 minutes)

A table has indexes on (a), (a, b), (b), (c), (a, b, c) and (d). The queries in use are: a = ?, a = ? AND b = ?, b = ?, a = ? AND b = ? AND c = ?, and d = ? ORDER BY c. Find redundant indexes, a missing index and write a clean-up plan that avoids downtime.

Done when: a list of indexes to drop with reasons, one to add, and an ordered plan with a check at each step.

Hint

An index on (a, b) makes (a) redundant.