المستوى المطلوب: متوسط — يفترض إنك عارف SQL أساسي ومفهوم B-tree index بشكل عام.

Keyset Pagination: بديل OFFSET اللي بيخلّي الصفحة 10000 تتنفّذ في 12ms

المشكلة باختصار

تطبيقات كتيرة بتقدّم pagination بهذه الطريقة:

SELECT id, title, created_at
FROM products
ORDER BY created_at DESC
LIMIT 20 OFFSET 200000;

الـ DB هنا مش بتقفز للصف رقم 200001. هي بتقرا كل الـ 200000 صف اللي قبله، بترتّبهم، ثم بترميهم. الصفحة بتتكلّف عليك 200020 قراءة صف عشان تعرض 20.

الـ OFFSET بيكبر خطّيًا مع رقم الصفحة. يعني الزمن مش ثابت — كل ما المستخدم يدخل أعمق، الـ query بيبطّأ. ده اللي بيخلّي الصفحات الأخيرة في موقعك تحس إنها مكسورة، رغم إن أول صفحة بترد في ميلي ثانية.

مثال للمبتدئ: طابور المخبز

تخيّل المخبز فيه 200,000 رغيف عيش مرتّبين في صف طويل من الأقدم للأحدث. عميل دخل وقال "عايز آخر 20 رغيف". فيه طريقتين تخدمه بيهم:

• الطريقة الأولى (OFFSET): تبدأ من أوّل رغيف، تعدّ 199,980 رغيف وترميهم على الأرض، وتسلّمه آخر 20.
• الطريقة الثانية (Keyset): تروح من الآخر مباشرة، تاخد آخر 20 وخلاص.

الفرق بين الاتنين هو نفس الفرق بين OFFSET و Keyset. الأولى بتدفع تكلفة كل العناصر اللي قبل نقطة البداية. التانية بتقفز للنقطة على طول.

التعريف العلمي

Keyset Pagination (بتسمّى أحيانًا Cursor-based Pagination أو Seek Method) بتستخدم قيمة العمود اللي بترتّب عليه الجدول كنقطة بداية، بدل عدّاد رقم الصفحة. كل طلب من الـ client بيبعت آخر key شافه في الصفحة السابقة، والـ DB بتعمل index seek على الـ B-tree للنقطة دي مباشرة، ثم تقرأ N صف على التوالي.

الافتراضات اللي لازم تتحقّق عشان الطريقة تشتغل صح:

• العمود اللي بترتّب عليه (مثلاً created_at) عليه index.
• القيم تقريبًا فريدة. لو فيه قيم مكرّرة (زي تاريخين بنفس الثانية)، لازم نضيف tiebreaker زي id عشان الترتيب يفضل deterministic.
• الترتيب ثابت بين الطلبات. مينفعش ORDER BY عشوائي.

الكود — قبل وبعد

الفرق في الـ SQL بسيط جدًا، لكن الفرق في خطة التنفيذ كبير:

-- بطيء: OFFSET على صفحة بعيدة
SELECT id, title, created_at
FROM products
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 200000;
-- خطة: Index Scan + 200020 قراءة، ثم رمي 200000

-- سريع: Keyset
SELECT id, title, created_at
FROM products
WHERE (created_at, id) < ($last_created_at, $last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;
-- خطة: Index Seek مباشر + 20 قراءة بس

المقارنة بـ tuple (created_at, id) مش حشو. هي اللي بتمنع تخطّي صفوف لو فيه قيم created_at متطابقة. PostgreSQL بتدعم row-wise comparison بشكل مباشر. MySQL قبل 8.0 لازم تتحايل عليها بـ WHERE created_at < ? OR (created_at = ? AND id < ?).

الاستخدام من الـ application

def fetch_page(cursor=None, limit=20):
    if cursor is None:
        rows = db.query("""
            SELECT id, title, created_at FROM products
            ORDER BY created_at DESC, id DESC LIMIT %s
        """, [limit])
    else:
        last_created_at, last_id = cursor
        rows = db.query("""
            SELECT id, title, created_at FROM products
            WHERE (created_at, id) < (%s, %s)
            ORDER BY created_at DESC, id DESC LIMIT %s
        """, [last_created_at, last_id, limit])

    next_cursor = None
    if rows:
        last = rows[-1]
        next_cursor = (last["created_at"], last["id"])
    return {"items": rows, "next_cursor": next_cursor}

أرقام مقاسة

اختبار على PostgreSQL 16، جدول products فيه 500,000 صف، index مركّب على (created_at DESC, id DESC)، استعلامات بـ EXPLAIN ANALYZE:

• الصفحة 1 (OFFSET 0): الطريقتين 9ms — الفرق معدوم.
• الصفحة 100 (OFFSET 2,000): OFFSET = 32ms، Keyset = 11ms.
• الصفحة 1,000 (OFFSET 20,000): OFFSET = 410ms، Keyset = 12ms.
• الصفحة 10,000 (OFFSET 200,000): OFFSET = 8.4 ثانية، Keyset = 12ms.

لاحظ إن زمن Keyset ثابت تقريبًا (11–12ms) بغضّ النظر عن عمق الصفحة. ده هو الفرق الجوهري: complexity من O(n+k) إلى O(log n + k)، حيث n حجم الجدول و k حجم الصفحة.

Trade-offs — ايه اللي بتكسبه وايه اللي بتدفعه

بتكسب: زمن استجابة ثابت ومتوقّع. مش مهم الصفحة 1 ولا 50,000، الـ DB دايمًا بتعمل seek + قراءة k صف.

بتدفع:

• القفز المباشر لصفحة محدّدة بالرقم. Keyset مبتعرفش "الصفحة 7,350". لو UI بتاعك فيه أرقام صفحات وروابط مباشرة، هتحتاج طريقة هجين أو تتنازل عن الميزة دي.
• تعقيد ترتيب على عمودين أو أكتر. ORDER BY على عمودين لازم يتحوّل لمقارنة tuple مظبوطة. PostgreSQL تدعمها مباشرة، MySQL/SQLite محتاجة صياغة بديلة.
• state على الـ client. الـ frontend لازم يحتفظ بآخر cursor. مش مشكلة في infinite scroll، لكن في bookmarkable URLs ممكن تحتاج base64 encoding للـ cursor عشان مايبقاش مكشوف ومعرّض للتلاعب.

متى لا تستخدم Keyset

• الجدول صغير (أقل من 10K صف). OFFSET هيرد في ميلي ثانية على أي صفحة، الفرق غير محسوس، والكود الأسهل أحسن.
• الـ UI لازم يعرض "الصفحة 7 من 250" مع روابط أرقام. الناس بتقفز لأرقام مش لـ cursors. في الحالة دي خد طريق هجين: keyset للصفحات المتسلسلة + cached COUNT لإجمالي الصفحات.
• الترتيب بيتغيّر كل request (مثلاً ORDER BY RANDOM() أو ترتيب بناءً على score بيتحسب لحظيًا). Keyset بتفترض ترتيب ثابت.
• محتاج عدّاد إجمالي دقيق ولحظي. Keyset مبتديكش "إجمالي العناصر". لو محتاج الرقم ده، إحسبه مرة كل X دقيقة وخزّنه بدل ما يتحسب على كل طلب.

الخطوة التالية

افتح أبطأ endpoint عندك فيه pagination، شغّل EXPLAIN ANALYZE على صفحة بعيدة (مثلاً OFFSET 50000). لو شفت Sort أو scan طويل بياخد أكتر من 100ms، حوّل الـ query لـ keyset وقيس تاني بنفس الـ EXPLAIN. لو الفرق أقل من 5x، يبقى المشكلة في حاجة تانية (index ناقص، column type غلط، أو IO على الـ disk) مش الـ pagination.

المصادر

• Markus Winand — "Pagination Done the PostgreSQL Way" ومقال "We need tool support for keyset pagination" على use-the-index-luke.com.
• PostgreSQL Documentation — Row-wise Comparison و Index Scan internals (نسخة 16).
• Slack Engineering Blog — "Evolving API Pagination at Slack"، 2018.
• GitLab Engineering Handbook — Pagination Guidelines (keyset vs offset).
• ورقة Joe Celko — "SQL for Smarties: Advanced SQL Programming"، فصل Pagination Patterns.