CoursesBackend engineering from first request to production

Puzzle 8 · 9 of 18

Why does the same page cost less to read?

Inspect a query plan before and after adding an index.

All puzzles in this course

The problem

A route lists five recent bookmarks. Reading five rows sounds cheap. What if the database must inspect two thousand candidates first?

See it

Why does the same page cost less to read? Filter owner Sort ties Add index Same five

Scroll sideways to see the full diagram.

  1. The query selects one owner.

    Step 1 of 4
  2. Time plus row number gives a stable order.

    Step 2 of 4
  3. The index stores keys in the requested order.

    Step 3 of 4
  4. Check that both versions return the same five rows.

    Step 4 of 4

The building block

The data drill generates repeated timestamps and several owners. The query filters by owner and sorts by time, then by a unique row number to settle ties. Without a matching index the database scans the table and uses temporary storage for sorting in this example. An index arranged by owner, time and row number can locate the matching range in order. Compare the plans and the actual rows. Extra indexes occupy space and must be maintained on writes. For the next page, carry the last time and row number together and continue below that pair using the same ordering.

Trace the page boundary

Use ascending order for this small example. The rows for one owner are (time 10, id 1), (10, 2) and (11, 3). With a page size of one, the first response ends at (10, 1). A next-page filter requiring a time greater than ten jumps straight to row 3. A filter accepting a later time or the same time and a larger row number returns row 2. For descending order, reverse the direction of both the ordering and continuation comparison. First verify the pages contain the right rows in order. Then inspect the query plan to learn how much searching and sorting produced them.

Try it

Run the browser experiment

Optional local lab

Run the data drills, inspect both plans and implement a second page. Check that two tied rows across the page boundary are each returned once.

Open the local exercise files

Check yourself

Two bookmarks share a time. What belongs in the page cursor?

Not quite. A timestamp alone cannot distinguish the tied rows. Re-read that part ↑

Right. An index matching the owner and sort order can serve the same page with less searching and sorting.

Which failure can a fast query still have?

Right. An index speeds access but cannot repair the wrong continuation condition.

Not quite. An index speeds access but cannot repair the wrong continuation condition. Re-read that part ↑

Why include the owner before time in this particular index?

Right. Choose an index for the actual filter and ordering.

Not quite. Choose an index for the actual filter and ordering. Re-read that part ↑

Sources

What you now know

An index matching the owner and sort order can serve the same page with less searching and sorting.