Index vs scan
0-day streakReview

Your progress

Level 1

0 XP100 XP to level 2
0day streak
0best streak
0topics started
0cards reviewed
    Review cards

    Progress is stored only in this browser. No account is required.

    Layer 3 · Go deeper · 8 min

    Go deeper

    Size it, build it, then make the calls an interviewer will push you on.

    Back of the envelope

    Size it up

    Tap through each step of the arithmetic.

    Where does a plain index scan on user_id stop beating the scan?

      What does a bitmap heap scan cost for RAC, 0.5% of bookings?

        Build-up · 6 steps

        Combine two indexes with a bitmap

        Separate indexes on train_no and journey_date, not one on both. A bitmap plan uses both, then reads the table in page order.

        Step 1 of 6

        Two filters, two indexes

        One query, two filters, two single-column indexes. Bitmaps let the planner combine both indexes before it touches the table.

        4 interview moments

        You’re the candidate

        The interviewer pushes on the hard parts. Pick an approach and see how it holds up.

        1. Deep dive 1 of 4

          Interviewer

          “Your bookings database moves to fast SSDs. A teammate wants random_page_cost = 1.1 everywhere, today. What do you do?”

          Your move. Pick an approach:

        2. Deep dive 2 of 4

          Interviewer

          “After a bulk load, RAC is 20% of bookings. Its bitmap scan now touches nearly every page, with lossy rechecks. What do you do?”

          The planner still estimates RAC at 0.5% of rows.

          Your move. Pick an approach:

        3. Deep dive 3 of 4

          Interviewer

          ““Latest 20 bookings on train 4417” takes 8.7 seconds. The plan walks the booked_at index backwards, filtering on train_no. What do you do?”

          Separate indexes exist on booked_at and train_no. Train 4417 is a summer special: all its bookings are from April.

          Your move. Pick an approach:

        4. Deep dive 4 of 4

          Interviewer

          “A query runs as an Index Only Scan, yet on a busy table Heap Fetches is close to the row count. What do you do?”

          Your move. Pick an approach:

        Build-up · 5 steps

        Watch correlation move the crossover

        The same 10-million-row bookings table and default costs. Only the column’s correlation changes, and with it how far an index scan keeps winning.

        Step 1 of 5

        Correlation 0, scattered rows

        user_id’s correlation is −0.0012, so physical order says nothing about it. Every match costs a random page, and the index scan stops winning at about 0.8% of rows.