Keyset Pagination

Keyset Pagination

Keyset Pagination and Other Anti-Pattern Fixes

OFFSET 450000 reads and discards 450,000 rows, so every page is slower than the last. Keyset pagination remembers the previous page's last key and seeks past it:

Page 22,501 of the order list by OFFSET and by keysetSQL

xa() { sudo mysql shop -Nre "EXPLAIN ANALYZE $1" |
       sed -E 's/^( *)(.*[^ ])  +(\(.*)$/\1\2\n\1     \3/'; }
xa "SELECT id, status FROM orders ORDER BY id LIMIT 20 OFFSET 450000"
xa "SELECT id, status FROM orders WHERE id > 450000 ORDER BY id LIMIT 20"

Output

-> Limit/Offset: 20/450000 row(s)
     (cost=40925 rows=20) (actual time=251..251 rows=20 loops=1)
    -> Index scan on orders using PRIMARY
         (cost=40925 rows=450020) (actual time=5.53..234 rows=450020 loops=1)
-> Limit: 20 row(s)
     (cost=21326 rows=20) (actual time=5.69..5.71 rows=20 loops=1)
    -> Filter: (orders.id > 450000)
         (cost=21326 rows=106490) (actual time=5.69..5.7 rows=20 loops=1)
        -> Index range scan on orders using PRIMARY over (450000 < id)
             (cost=21326 rows=106490) (actual time=5.68..5.69 rows=20 loops=1)

The seek read 20 rows instead of 450,020, the same on every page. Sort on a unique key (append the primary key to a non-unique column) and give up jumping to page N. Spell the tie-breaker out: in the container of Sargable Predicates, ordered_at > ? OR (ordered_at = ? AND id > ?) was a range scan taking 0.37 ms, while (ordered_at, id) > (?, ?) walked 474,401 index entries in 175 ms.

Other recurring fixes: replace N+1 loops with one join or IN batch (Databases with PDO, eager loading in Laravel); name columns instead of SELECT * so a covering index can serve (Covering Indexes); join a temporary table instead of a huge IN list; test existence with EXISTS, not COUNT(*) > 0; match literal types to columns (NULLs and Conversion); and keep leading wildcards out of LIKE.

MENU