Pagination in SQL: OFFSET vs. Keyset Pagination

1. Das OFFSET-Problem: Warum Seite 1000 langsam ist

OFFSET/LIMIT ist die intuitive SQL-Pagination: Man überspringt die ersten N Zeilen und gibt die nächsten M zurück. Das funktioniert auf Seite 1, 2 oder auch 10 noch schnell. Auf Seite 1000 wird es zum Problem — und das ist kein akademisches Problem, sondern ein reales, das viele Systeme in Produktion trifft.

Das fundamental Problem mit Keyset Pagination vs. OFFSET: MySQL muss bei LIMIT 20 OFFSET 19980 zuerst 20.000 Zeilen lesen, sortieren und dann 19.980 davon verwerfen, um die 20 gewünschten Zeilen zurückzugeben. Die verworfenen Zeilen werden vollständig gelesen und sortiert — die Arbeit ist real, auch wenn das Ergebnis klein ist.

-- Seite 1: schnell (liest 20 Zeilen)
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 0;

-- Seite 100: noch akzeptabel (liest 2020 Zeilen, verwirft 2000)
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 2000;

-- Seite 1000: langsam (liest 20020 Zeilen, verwirft 20000!)
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 20000;

-- Seite 50000: sehr langsam (liest 1.000.020 Zeilen!)
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 1000000;

-- Laufzeit-Messung
SELECT SQL_NO_CACHE id, title
FROM sales_order
ORDER BY created_at DESC
LIMIT 20 OFFSET 500000;
-- Bei 600k Bestellungen: kann mehrere Sekunden dauern

2. EXPLAIN zeigt das Problem deutlich

Ein EXPLAIN-Plan für eine OFFSET-Query auf einer großen Tabelle zeigt das Problem klar: MySQL scannt einen Index, muss aber trotzdem alle OFFSET Zeilen materialisieren, bevor er die LIMIT-Zeilen zurückgeben kann. Das rows-Feld in EXPLAIN zeigt wie viele Zeilen MySQL schätzt verarbeiten zu müssen — nicht wie viele zurückgegeben werden.

-- EXPLAIN für OFFSET-Query
EXPLAIN SELECT id, title, created_at
FROM sales_order
ORDER BY created_at DESC
LIMIT 20 OFFSET 100000\G

-- Typische Ausgabe:
-- select_type: SIMPLE
-- type: index          <- Index-Scan (nicht range!)
-- key: IDX_CREATED_AT  <- Nutzt Index
-- rows: 100020         <- Muss 100.020 Zeilen verarbeiten!
-- Extra: Using index   <- Covering Index hilft, aber OFFSET-Cost bleibt

-- EXPLAIN ANALYZE (MySQL 8): echte Kosten
EXPLAIN ANALYZE
SELECT id, created_at
FROM sales_order
ORDER BY created_at DESC
LIMIT 20 OFFSET 50000;

-- Zeigt: actual rows= 50020, actual time für den Sort-Step

-- Vergleich: Keyset-Query EXPLAIN
EXPLAIN SELECT id, title, created_at
FROM sales_order
WHERE created_at < '2025-01-01 12:00:00'
   OR (created_at = '2025-01-01 12:00:00' AND id < 98765)
ORDER BY created_at DESC, id DESC
LIMIT 20\G
-- rows: 20   <- Nur 20 Zeilen werden verarbeitet!

3. Keyset Pagination: Das Grundprinzip

Keyset Pagination (auch Cursor Pagination oder Seek Method genannt) löst das OFFSET-Problem fundamental. Statt "überspringe N Zeilen" verwendet man "finde Zeilen nach dem letzten gesehenen Wert". Der letzte Wert der vorherigen Seite wird als Cursor verwendet. MySQL kann dank Index direkt zu dieser Position springen, ohne alle vorigen Zeilen zu lesen.

-- Keyset Pagination: Erste Seite (kein Cursor)
SELECT id, title, created_at
FROM articles
ORDER BY id DESC
LIMIT 20;
-- Letzte zurückgegebene id: 5432 -> wird als Cursor gespeichert

-- Nächste Seite: WHERE id < :last_seen_id
SELECT id, title, created_at
FROM articles
WHERE id < 5432    -- Cursor aus vorheriger Seite
ORDER BY id DESC
LIMIT 20;
-- Letzte zurückgegebene id: 5412 -> neuer Cursor

-- Und so weiter, jede Seite ist gleich schnell:
SELECT id, title, created_at
FROM articles
WHERE id < 5412
ORDER BY id DESC
LIMIT 20;

-- Performance-Vergleich auf 1 Million Einträge:
-- OFFSET 500000 LIMIT 20: ~800ms
-- WHERE id < 500020 LIMIT 20: ~0.5ms

-- In der Anwendung (Pseudocode):
-- Erste Seite: GET /articles?limit=20
-- Nächste Seite: GET /articles?limit=20&before_id=5432
-- Zurückgegeben: { items: [...], next_cursor: 5412, has_more: true }

4. Composite Cursor für Sort-Ties

Wenn nach einer nicht-eindeutigen Spalte sortiert wird (z.B. created_at), können mehrere Zeilen denselben Wert haben (Sort-Ties). Ein einfacher WHERE created_at < :ts-Cursor würde dann Zeilen auslassen oder doppelt zeigen. Die Lösung ist ein Composite Cursor: zwei Bedingungen, die zusammen eindeutig sind.

-- Problem: Mehrere Bestellungen mit identischem created_at
-- Einfacher Cursor überspringt oder dupliziert Zeilen!

-- FALSCH (bei Sort-Ties):
SELECT id, created_at FROM sales_order
WHERE created_at < '2025-01-15 14:30:00'
ORDER BY created_at DESC
LIMIT 20;

-- RICHTIG: Composite Cursor mit id als Tiebreaker
SELECT id, created_at FROM sales_order
WHERE created_at < '2025-01-15 14:30:00'
   OR (created_at = '2025-01-15 14:30:00' AND id < 98765)
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- Erklärung:
-- "Alle Zeilen die zeitlich früher sind"
-- ODER
-- "Zeilen mit demselben Zeitstempel aber kleinerer id"
-- Das erfasst exakt alle Zeilen nach dem Cursor-Punkt

-- In API-Parametern: ?before_ts=2025-01-15T14:30:00&before_id=98765

-- Variante mit TUPLE COMPARISON (eleganter, aber MySQL unterstützt es nicht nativ):
-- WHERE (created_at, id) < ('2025-01-15 14:30:00', 98765)
-- MySQL: Diese Syntax ist technisch gültig, aber der Optimizer nutzt
-- den Index oft nicht optimal dafür

-- Besser lesbar mit CTE:
WITH cursor_pos AS (
    SELECT '2025-01-15 14:30:00' AS ts, 98765 AS id
)
SELECT o.id, o.created_at, o.grand_total
FROM sales_order o, cursor_pos c
WHERE o.created_at < c.ts
   OR (o.created_at = c.ts AND o.id < c.id)
ORDER BY o.created_at DESC, o.id DESC
LIMIT 20;

5. Konsistenz bei gleichzeitigen Inserts und Deletes

Keyset Pagination hat gegenüber OFFSET einen wichtigen Konsistenz-Vorteil: Wenn während des Durchblätterns neue Zeilen eingefügt oder alte gelöscht werden, bleiben die Seiten bei Keyset konsistent. OFFSET hingegen verschiebt alle Positionen: Ein Delete auf Seite 2 kann dazu führen, dass beim Blättern eine Zeile von Seite 3 auf Seite 2 "rutscht" und damit zweimal gesehen oder übersprungen wird.

-- OFFSET-Pagination: Konsistenz-Problem bei Concurrent Inserts
-- Szenario: Nutzer ist auf Seite 3 von news_articles

-- Seite 2 (bereits gesehen): OFFSET 20 LIMIT 20 -> Artikel 21-40
-- Gleichzeitig: Neuer Artikel wird eingefügt (bekommt id 41 in sortierter Liste)
-- Seite 3: OFFSET 40 LIMIT 20 -> Jetzt erscheinen Artikel 41-60
-- Artikel 41 (neu) erscheint auf Seite 3, obwohl er eigentlich auf Seite 2 wäre
-- Ergebnis: Artikel 40 wird ZWEIMAL gezeigt (auf Seite 2 UND 3)

-- KEYSET-Pagination: Konsistent trotz Concurrent Changes
-- Seite 2 letzte id: 40, Cursor: id < 40
-- Neuer Artikel eingefügt mit id 41
-- Seite 3: WHERE id < 40 -> Zeigt ids 39, 38, 37... — korrekt!
-- Neuer Artikel 41 taucht nicht auf (hat höhere id als Cursor)

-- Praxisfall Magento: Bestellliste mit Live-Updates
SELECT
    entity_id,
    increment_id,
    created_at,
    grand_total,
    status
FROM sales_order
WHERE entity_id < :last_seen_entity_id  -- Cursor
  AND store_id = 1
ORDER BY entity_id DESC
LIMIT 25;

-- Wo zuletzt: entity_id 89432 -> nächste Seite: entity_id < 89432

6. Trade-offs: Was Keyset Pagination nicht kann

Keyset Pagination ist kein Allheilmittel. Sie hat wichtige Einschränkungen, die man kennen muss, bevor man sie implementiert. Das entscheidende Manko: Man kann nicht direkt zu einer beliebigen Seitennummer springen. "Zeige mir Seite 500" ist mit Keyset nicht möglich, ohne vorher alle 499 Seiten zu traversieren.

-- Trade-off 1: Kein "Sprung" zu beliebiger Seite möglich
-- Keyset kann nur "nächste Seite" und "vorherige Seite"
-- "Seite 500 von 1000" ist nicht direkt möglich

-- Trade-off 2: Rückwärts-Navigation braucht umgekehrten Cursor
-- Vorwärts: WHERE id < :last_id ORDER BY id DESC
-- Rückwärts: WHERE id > :first_id ORDER BY id ASC LIMIT 20
--            Dann die Ergebnisse in der Anwendung umkehren

-- Trade-off 3: Totalanzahl nicht effizient
-- Keyset gibt nicht automatisch "Seite X von Y" an
-- COUNT(*) muss separat ausgeführt werden (oder weggelassen werden)

-- Trade-off 4: Komplexer bei mehrspaltiger Sortierung
-- Je mehr Sortierspalten, desto komplexer der Composite Cursor

-- Wann OFFSET besser ist:
-- - Kleine Tabellen (< 100k Zeilen)
-- - Nutzer braucht direkten Seitensprung
-- - Admin-Backend wo Seite 1000 kein Produktionsfall ist

-- Wann Keyset besser ist:
-- - Große Tabellen (> 100k Zeilen)
-- - Infinite Scroll / Load More
-- - APIs mit Cursor-based Pagination
-- - Datenexporte die durch alle Zeilen iterieren

-- Hybrid-Ansatz für APIs:
-- Kleine Seitenzahlen: OFFSET (für direkten Sprung)
-- Große Seitenzahlen: Keyset (für Performance)
-- Umschalten bei z.B. OFFSET > 10000
SELECT id, title FROM articles
WHERE (:cursor_id IS NULL OR id < :cursor_id)
ORDER BY id DESC
LIMIT 20;

7. Magento Produktgrid und Deep Pagination

Magento's Produktliste auf Kategorieseiten nutzt standardmäßig OFFSET/LIMIT für die Paginierung — ein bekanntes Performance-Problem bei großen Katalogen. Magneto limitiert die erlaubten Seitenzahlen standardmäßig auf maximal 1000, was einem OFFSET von 20.000 bei 20 Produkten pro Seite entspricht. Das ist ein pragmatischer Kompromiss, löst das fundamentale Problem aber nicht.

-- Magento Produktliste: OFFSET-basierte Paginierung
-- Intern erzeugt Magento in etwa diese Query:
SELECT
    e.entity_id
FROM catalog_product_entity e
INNER JOIN catalog_product_index_price ip
    ON ip.entity_id = e.entity_id
    AND ip.website_id = 1
    AND ip.customer_group_id = 0
WHERE e.entity_id IN (
    SELECT product_id FROM catalog_category_product_index_store1
    WHERE category_id = 5
)
ORDER BY ip.min_price ASC
LIMIT 24 OFFSET 480;  -- Seite 21 bei 24 Produkten pro Seite

-- Magento's Limit für tiefe Seiten in XML konfigurierbar:
-- vendor/magento/module-catalog/etc/config.xml
-- <catalog_product_collection_max_page_size>1000</catalog_product_collection_max_page_size>

-- Performance der tiefen Seite prüfen
EXPLAIN SELECT e.entity_id
FROM catalog_product_entity e
INNER JOIN catalog_product_index_price ip ON ip.entity_id = e.entity_id
    AND ip.website_id = 1 AND ip.customer_group_id = 0
WHERE e.entity_id IN (SELECT product_id FROM catalog_category_product_index_store1 WHERE category_id = 5)
ORDER BY ip.min_price ASC
LIMIT 24 OFFSET 10000;

-- Magento Toolbar: Seitenzahl-Limit aus der Datenbank
SELECT path, value
FROM core_config_data
WHERE path = 'catalog/frontend/max_page_size_allowed';

8. SELECT SQL_CALC_FOUND_ROWS vs. separates COUNT

Für Paginierung braucht man oft die Gesamtzahl der Zeilen (für "Seite X von Y"). MySQL bietet SQL_CALC_FOUND_ROWS als vermeintliche Abkürzung: Es berechnet beim SELECT gleichzeitig die Gesamtzahl. In der Praxis ist das aber oft langsamer als ein separates COUNT(*), weil MySQL intern trotzdem alle Zeilen scannen muss.

-- SQL_CALC_FOUND_ROWS: eine Query, zwei Ergebnisse
SELECT SQL_CALC_FOUND_ROWS id, title, created_at
FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20 OFFSET 0;

SELECT FOUND_ROWS();  -- Gibt Gesamtzahl zurück: z.B. 15420

-- Problem: SQL_CALC_FOUND_ROWS ist seit MySQL 8.0.17 deprecated
-- Grund: Internt muss MySQL trotzdem alle Zeilen verarbeiten (kein Vorteil)
-- Besser: Separates COUNT

-- Separates COUNT (empfohlen):
SELECT COUNT(*) FROM articles WHERE status = 'published';
SELECT id, title, created_at FROM articles
WHERE status = 'published'
ORDER BY created_at DESC
LIMIT 20 OFFSET 0;

-- Wenn COUNT teuer ist: Approximation aus INFORMATION_SCHEMA
SELECT table_rows
FROM information_schema.tables
WHERE table_schema = DATABASE() AND table_name = 'articles';
-- Nicht exakt, aber schnell und für "ca. X Ergebnisse" ausreichend

-- Cache für Count-Ergebnis nutzen (Magento macht das):
-- Count nur neu berechnen wenn sich die Filterbedingung ändert
-- Nicht bei jedem Seitenaufruf neu abfragen

-- Für APIs mit Keyset: Gesamtzahl weglassen
-- "has_more": true/false ist oft aussagekräftiger als "Seite X von Y"
SELECT id, title FROM articles
WHERE id < :cursor_id AND status = 'published'
ORDER BY id DESC
LIMIT 21;  -- 1 extra abfragen: wenn 21 zurück -> has_more = true

9. Covering Index für Keyset-Queries

Keyset Pagination profitiert enorm von Covering Indexes. Ein Covering Index enthält alle Spalten, die die Query braucht — MySQL kann die Query dann direkt aus dem Index beantworten, ohne die Tabellenzeilen zu lesen (kein "table access by primary key"). Das ist der entscheidende Performance-Faktor, der Keyset Pagination auf großen Tabellen so schnell macht.

-- Query für Keyset Pagination auf Bestellliste
SELECT id, customer_id, created_at, grand_total
FROM sales_order
WHERE created_at < '2025-01-15 14:30:00'
   OR (created_at = '2025-01-15 14:30:00' AND id < 98765)
ORDER BY created_at DESC, id DESC
LIMIT 20;

-- Covering Index für diese Query:
CREATE INDEX idx_order_pagination
ON sales_order (created_at DESC, id DESC, customer_id, grand_total);
-- Enthält alle SELECT-Spalten + WHERE/ORDER BY Spalten

-- EXPLAIN prüft: Extra: "Using index" bedeutet Covering Index aktiv
EXPLAIN SELECT id, customer_id, created_at, grand_total
FROM sales_order
WHERE created_at < '2025-01-15 14:30:00'
ORDER BY created_at DESC, id DESC
LIMIT 20\G

-- Wenn Extra: "Using index" -> kein Table-Lookup nötig!

-- Late Row Lookup: Alternative zu Covering Index bei breiten Tabellen
-- Erst IDs per Keyset holen (aus Index), dann JOIN für volle Zeilen
SELECT so.*
FROM (
    SELECT id FROM sales_order
    WHERE created_at < '2025-01-15 14:30:00'
      OR (created_at = '2025-01-15 14:30:00' AND id < 98765)
    ORDER BY created_at DESC, id DESC
    LIMIT 20
) AS pagination
JOIN sales_order so ON so.id = pagination.id
ORDER BY so.created_at DESC, so.id DESC;

-- Vorhandene Indizes prüfen
SHOW INDEX FROM sales_order;
SHOW INDEX FROM catalog_product_entity;

11. Zusammenfassung

Keyset Pagination löst ein fundamentales Problem von OFFSET/LIMIT: MySQL muss bei OFFSET N tatsächlich N Zeilen lesen und verwerfen. Das wird bei großen Seitenzahlen linear langsamer. Keyset Pagination mit WHERE id < :last_seen_id springt direkt zur richtigen Position im Index — jede Seite ist gleich schnell, egal ob Seite 1 oder Seite 10.000.

Der wichtigste Einschränkung: Keyset kann nicht direkt zu einer beliebigen Seite springen. Für Systeme, die "Sprung zu Seite X" brauchen (wie Magento Kategorieseiten), ist OFFSET die einzige Option — aber man sollte dann die maximal erlaubte Seitenzahl begrenzen. Für APIs, Infinite Scroll und Datenexporte ist Keyset Pagination die deutlich bessere Wahl.

12. FAQ: Keyset Pagination vs. OFFSET