Pagination: offset বনাম cursor, আর ৯,৫০০ নম্বর পাতা ধীর কেন

যে তালিকা বাড়তে পারে, যেমন post, order বা notification, তার জন্য pagination লাগে: সব না পাঠিয়ে একবারে এক পাতা। সোজা উপায় LIMIT 20 OFFSET 40। বাস্তব জীবন না আসা পর্যন্ত এটি কাজ করে: কেউ পড়ার সময় নতুন row আসে, আর ব্যবহারকারী গভীরে স্ক্রল করেন। নিচের কোড ও ফল প্রকাশের আগে Python 3 ও SQLite-এ (২,০০,০০০ row) চালানো হয়েছে।

দুটি পদ্ধতি

• Offset pagination: "N-টি row এড়িয়ে পরের ২০টি দাও।" URL দেখতে ?page=3 বা ?limit=20&offset=40।
• Cursor (keyset) pagination: "এই row-টির পরের ২০টি দাও।" Client শেষ দেখা row থেকে একটি চিহ্ন পাঠায়, যেমন ?after=199996।

একটি চালানো যায় এমন উদাহরণ

pagination.py নামে সংরক্ষণ করুন:

import sqlite3
import time

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE posts (id INTEGER PRIMARY KEY, title TEXT)")
db.executemany("INSERT INTO posts (title) VALUES (?)", [(f"post {i}",) for i in range(1, 200_001)])


def offset_page(limit, offset):
    return db.execute(
        "SELECT id FROM posts ORDER BY id DESC LIMIT ? OFFSET ?", (limit, offset)
    ).fetchall()


def cursor_page(limit, before_id=None):
    """Keyset pagination: 'give me the next rows after this id'."""
    if before_id is None:
        rows = db.execute("SELECT id FROM posts ORDER BY id DESC LIMIT ?", (limit,)).fetchall()
    else:
        rows = db.execute(
            "SELECT id FROM posts WHERE id < ? ORDER BY id DESC LIMIT ?", (before_id, limit)
        ).fetchall()
    ids = [r[0] for r in rows]
    next_cursor = ids[-1] if len(ids) == limit else None
    return ids, next_cursor


print("== 1. A new post arrives while the user reads ==")
p1 = [r[0] for r in offset_page(5, 0)]
db.execute("INSERT INTO posts (title) VALUES ('brand new')")  # id 200001
p2 = [r[0] for r in offset_page(5, 5)]
print("offset page 1:", p1)
print("offset page 2:", p2, "<- repeats", sorted(set(p1) & set(p2)))

db.execute("DELETE FROM posts WHERE id = 200001")  # reset
c1, nxt = cursor_page(5)
db.execute("INSERT INTO posts (title) VALUES ('brand new')")
c2, _ = cursor_page(5, nxt)
print("cursor page 1:", c1)
print("cursor page 2:", c2, "<- no repeats:", not set(c1) & set(c2))

print()
print("== 2. Cost of going deep ==")
print("OFFSET plan :", db.execute(
    "EXPLAIN QUERY PLAN SELECT id FROM posts ORDER BY id DESC LIMIT 20 OFFSET 190000").fetchall()[0][3])
print("cursor plan :", db.execute(
    "EXPLAIN QUERY PLAN SELECT id FROM posts WHERE id < 10000 ORDER BY id DESC LIMIT 20").fetchall()[0][3])


def timed(fn, repeat=20):
    t = time.perf_counter()
    for _ in range(repeat):
        fn()
    return (time.perf_counter() - t) / repeat * 1000


print(f"offset page 1     : {timed(lambda: offset_page(20, 0)):.3f} ms")
print(f"offset page 9500  : {timed(lambda: offset_page(20, 190000)):.3f} ms")
print(f"cursor deep page  : {timed(lambda: cursor_page(20, 10000)):.3f} ms")

python3 pagination.py-এর ফল:

== 1. A new post arrives while the user reads ==
offset page 1: [200000, 199999, 199998, 199997, 199996]
offset page 2: [199996, 199995, 199994, 199993, 199992] <- repeats [199996]
cursor page 1: [200000, 199999, 199998, 199997, 199996]
cursor page 2: [199995, 199994, 199993, 199992, 199991] <- no repeats: True

== 2. Cost of going deep ==
OFFSET plan : SCAN posts
cursor plan : SEARCH posts USING INTEGER PRIMARY KEY (rowid<?)
offset page 1     : 0.016 ms
offset page 9500  : 3.563 ms
cursor deep page  : 0.019 ms

সমস্যা ১: item পুনরাবৃত্ত হয় বা হারায়

পাতা ১ ও পাতা ২-এর মাঝে একটি নতুন post এসেছে। Offset-এ সবকিছু এক ঘর নিচে সরে গেল, ফলে পাতা ২ শুরু হলো 199996 দিয়ে, যা ব্যবহারকারী পাতা ১-এই দেখেছেন। কিছু মুছে গেলে উল্টোটা হতো: একটি item ক্রম থেকে হারিয়ে যেত। Cursor-এ পাতা ২ মানে "199996-এর চেয়ে পুরোনো row", তাই নতুন row তাকে বিরক্ত করে না: পুনরাবৃত্তি নেই, ফাঁকও নেই।

Feed, timeline ও যা ঘন ঘন বদলায়, তার জন্য শুধু এটিই cursor বেছে নেওয়ার জোরালো কারণ।

সমস্যা ২: গভীর পাতা ধীর

Database ১,৯০,০০০ নম্বর row-তে লাফ দিতে পারে না। OFFSET 190000-এ তাকে ১,৯০,০০০ row পার হয়ে ফেলে দিতে হয়। Plan-এ SCAN দেখা যাচ্ছে। Cursor query primary key-তে SEARCH করে সরাসরি সঠিক জায়গায় যায়।

এই মেশিনে মাপা (২০ বারের গড়; সংখ্যা মেশিনভেদে বদলায়, ধরনটি নয়):

• offset, পাতা ১: প্রায় ০.০১৬ ms
• offset, পাতা ৯,৫০০: প্রায় ৩.৬ ms, কয়েকশো গুণ ধীর
• cursor, একই গভীরতা: প্রায় ০.০১৯ ms

মেমরিতে থাকা ২,০০,০০০ row-এর SQLite ব্যথা লুকিয়ে রাখে। লক্ষ লক্ষ row, join ও disk read-সহ আসল database-এ ফারাক সেকেন্ডে পৌঁছায়। Offset-এর খরচ যত গভীরে যাবেন তত বাড়ে।

Cursor pagination-এর দাম

• "পাতা ৪৭"-এ লাফ নেই। পরের (ও বানালে আগের) পাতায় যাওয়া যায়, যেকোনো পাতায় নয়। Feed ও infinite scroll-এ ঠিক আছে। পাতা-নম্বর চাওয়া admin table-এ offset বেশি মানানসই হতে পারে।
• স্থিতিশীল, অনন্য ক্রম দরকার। created_at দিয়ে সাজালে দুই row-এর মান এক হলে শুধু created_at-এর cursor row এড়িয়ে যেতে বা পুনরাবৃত্তি করতে পারে। Tie-breaker যোগ করুন: (created_at, id) দিয়ে সাজান ও দুটোই তুলনা করুন। (created_at, id) < (?, ?)-এর মতো row-value তুলনা PostgreSQL ও সাম্প্রতিক SQLite সমর্থন করে; আপনার database যাচাই করুন।
• সাজানোর column-এ index থাকতে হবে, নইলে cursor query-ও ধীর।
• সস্তা মোট সংখ্যা নেই। বড় table-এ COUNT(*) নিজেই ব্যয়বহুল। অনেক API সঠিক মোট বাদ দেয় বা আনুমানিক দেয়।

Cursor-কে অস্বচ্ছ করুন

199996 সরাসরি না দেখিয়ে cursor অস্বচ্ছ string হিসেবে ফেরত দিন (যেমন মানগুলোর base64)। তখন client নিজে cursor বানায় না, আর আপনি পরে ভেতরের গঠন বদলাতে পারেন। অন্ধভাবে বিশ্বাস করবেন না: যাচাই করুন, সংবেদনশীল কিছু থাকলে sign করুন। উদাহরণের মতো parameter ব্যবহার করুন, কখনো সরাসরি SQL-এ বসাবেন না।

ভালো response আকৃতি

{
  "data": [ ... ২০টি item ... ],
  "next_cursor": "MTk5OTk1",
  "has_more": true
}

Client পরের পাতার জন্য next_cursor ফেরত পাঠায়। next_cursor null হলে আর কিছু নেই। কোডে এটি তখন, যখন পাতায় limit-এর চেয়ে কম row আসে।

Test

test_pagination.py নামে সংরক্ষণ করুন:

import unittest

import pagination as p


class PageTests(unittest.TestCase):
    def test_cursor_walks_everything_once(self):
        seen, cur = [], None
        while True:
            ids, cur = p.cursor_page(5000, cur)
            seen += ids
            if cur is None:
                break
        self.assertEqual(len(seen), len(set(seen)))
        self.assertEqual(seen, sorted(seen, reverse=True))

    def test_last_page_has_no_cursor(self):
        _, cur = p.cursor_page(5, 3)
        self.assertIsNone(cur)


if __name__ == "__main__":
    unittest.main()

$ python3 -m unittest
Ran 2 tests in 0.224s

OK

প্রথম test cursor ধরে ২,০০,০০০ row-ই হাঁটে এবং যাচাই করে প্রতিটি id ঠিক একবার, ক্রমানুসারে এসেছে।

কোনটি ব্যবহার করবেন?

• Cursor: feed, timeline, log, notification, "আরও দেখুন", বড় বা দ্রুত বদলানো table, যেসব public API-তে client সব scrape করতে পারে।
• Offset: ছোট table, পাতা-নম্বরসহ admin পর্দা, যে data কদাচিৎ বদলায়।
• সবসময় সর্বোচ্চ limit (যেমন ১০০) ঠিক করুন, যাতে client এক request-এ দশ লক্ষ row চাইতে না পারে।

সাধারণ ভুল

• বিশাল table-এ OFFSET।
• ORDER BY ছাড়া pagination। তখন ক্রম অনির্ধারিত, পাতা মিলে যেতে পারে।
• Tie-breaker ছাড়া অ-অনন্য column দিয়ে সাজানো।
• সাজানোর column-এ index না থাকা।
• পাতার আকারে সীমা না থাকা।
• Cursor-এর SQL string জোড়া দিয়ে বানানো (injection ঝুঁকি)।

মূল কথা: Offset সহজ, কিন্তু data বদলালে পুনরাবৃত্তি ও ফাঁক দেয় এবং যত গভীরে যান তত ধীর হয়। Cursor (keyset) pagination index-যুক্ত, অনন্য ক্রম ব্যবহার করে শেষ দেখা row-এর ঠিক পর থেকে শুরু করে, তাই সঠিক ও দ্রুত থাকে।

---

Backend সিরিজ, পর্ব ৩ (নির্ভরযোগ্য API): 5 নম্বর (মোট 5)। আগের লেখা: API versioning: ব্যবহারকারী না ভেঙে breaking change আনুন.