Designing Efficient Pagination for Large Datasets

// ❌ Offset pagination — simple but performance degrades
interface OffsetPaginationParams {
  page: number;
  pageSize: number;
}
 
interface PaginatedResponse<T> {
  data: T[];
  page: number;
  pageSize: number;
  totalCount: number;
  totalPages: number;
}
 
async function getOrdersOffset(
  params: OffsetPaginationParams
): Promise<PaginatedResponse<Order>> {
  const offset = (params.page - 1) * params.pageSize;
 
  // This query gets slower as offset increases
  const [data, countResult] = await Promise.all([
    db.query(
      `SELECT * FROM orders
       ORDER BY created_at DESC
       LIMIT $1 OFFSET $2`,
      [params.pageSize, offset]
    ),
    db.query("SELECT COUNT(*) FROM orders"),
  ]);
 
  return {
    data: data.rows,
    page: params.page,
    pageSize: params.pageSize,
    totalCount: parseInt(countResult.rows[0].count),
    totalPages: Math.ceil(
      parseInt(countResult.rows[0].count) / params.pageSize
    ),
  };
}
 
// Page 1: OFFSET 0 → fast (scans 20 rows)
// Page 1000: OFFSET 20000 → slow (scans 20020 rows, discards 20000)
// Page 50000: OFFSET 1000000 → very slow (scans 1000020 rows)

interface CursorPaginationParams {
  cursor?: string;
  limit: number;
  direction: "forward" | "backward";
}
 
interface CursorPaginatedResponse<T> {
  data: T[];
  nextCursor: string | null;
  previousCursor: string | null;
  hasMore: boolean;
}
 
function encodeCursor(id: string, createdAt: Date): string {
  const payload = JSON.stringify({ id, createdAt: createdAt.toISOString() });
  return Buffer.from(payload).toString("base64url");
}
 
function decodeCursor(cursor: string): { id: string; createdAt: Date } {
  const payload = JSON.parse(
    Buffer.from(cursor, "base64url").toString("utf-8")
  );
  return {
    id: payload.id,
    createdAt: new Date(payload.createdAt),
  };
}
 
async function getOrdersCursor(
  params: CursorPaginationParams
): Promise<CursorPaginatedResponse<Order>> {
  const limit = params.limit + 1; // Fetch one extra to detect hasMore
  let query: string;
  let values: unknown[];
 
  if (params.cursor) {
    const { id, createdAt } = decodeCursor(params.cursor);
 
    // Keyset condition — uses index, no scanning
    query = `
      SELECT * FROM orders
      WHERE (created_at, id) < ($2, $3)
      ORDER BY created_at DESC, id DESC
      LIMIT $1`;
    values = [limit, createdAt, id];
  } else {
    query = `
      SELECT * FROM orders
      ORDER BY created_at DESC, id DESC
      LIMIT $1`;
    values = [limit];
  }
 
  const result = await db.query(query, values);
  const hasMore = result.rows.length > params.limit;
  const data = hasMore
    ? result.rows.slice(0, params.limit)
    : result.rows;
 
  const lastItem = data[data.length - 1];
  const firstItem = data[0];
 
  return {
    data,
    nextCursor: hasMore && lastItem
      ? encodeCursor(lastItem.id, lastItem.created_at)
      : null,
    previousCursor: firstItem
      ? encodeCursor(firstItem.id, firstItem.created_at)
      : null,
    hasMore,
  };
}

// ✅ Consistent performance at any depth
// Page 1: WHERE (created_at, id) < (now, max_id) → index seek
// Page 1000: WHERE (created_at, id) < (some_date, some_id) → same index seek
// Page 50000: same performance — always reads exactly limit+1 rows

interface SortableColumn {
  name: string;
  direction: "asc" | "desc";
}
 
function buildKeysetQuery(
  table: string,
  sort: SortableColumn[],
  cursor: Record<string, unknown> | null,
  limit: number
): { query: string; values: unknown[] } {
  const orderClause = sort
    .map(s => `${s.name} ${s.direction.toUpperCase()}`)
    .join(", ");
 
  if (!cursor) {
    return {
      query: `SELECT * FROM ${table} ORDER BY ${orderClause} LIMIT $1`,
      values: [limit + 1],
    };
  }
 
  // Build compound comparison for cursor position
  // (a, b, c) < ($1, $2, $3) for DESC ordering
  const columns = sort.map(s => s.name);
  const placeholders = sort.map((_, i) => `$${i + 2}`);
  const comparison = sort[0].direction === "desc" ? "<" : ">";
 
  const whereClause =
    `(${columns.join(", ")}) ${comparison} (${placeholders.join(", ")})`;
 
  const values = [
    limit + 1,
    ...sort.map(s => cursor[s.name]),
  ];
 
  return {
    query: `SELECT * FROM ${table}
            WHERE ${whereClause}
            ORDER BY ${orderClause}
            LIMIT $1`,
    values,
  };
}

interface PaginationStrategy {
  name: string;
  performance: string;
  randomAccess: boolean;
  stableResults: boolean;
  bestFor: string[];
  avoidFor: string[];
}
 
const strategies: PaginationStrategy[] = [
  {
    name: "Offset",
    performance: "Degrades linearly with page depth",
    randomAccess: true,
    stableResults: false,
    bestFor: [
      "Small datasets (< 100K rows)",
      "Admin interfaces with page numbers",
      "Rarely accessed deep pages",
    ],
    avoidFor: [
      "Large datasets with deep pagination",
      "High-concurrency write tables",
      "Real-time feeds with frequent inserts",
    ],
  },
  {
    name: "Cursor (keyset)",
    performance: "Constant regardless of depth",
    randomAccess: false,
    stableResults: true,
    bestFor: [
      "Infinite scroll / load more UIs",
      "Large datasets with sequential access",
      "Real-time feeds and timelines",
      "APIs consumed by mobile clients",
    ],
    avoidFor: [
      "UIs requiring 'jump to page N'",
      "Sorting by non-indexed columns",
    ],
  },
];

-- For cursor pagination: compound index matching sort order
CREATE INDEX idx_orders_cursor
  ON orders (created_at DESC, id DESC);
 
-- For filtered cursor pagination
CREATE INDEX idx_orders_user_cursor
  ON orders (user_id, created_at DESC, id DESC);
 
-- Check if your index is being used
EXPLAIN ANALYZE
SELECT * FROM orders
WHERE (created_at, id) < ('2023-06-01', 'abc-123')
ORDER BY created_at DESC, id DESC
LIMIT 21;
 
-- Should show: Index Scan using idx_orders_cursor
-- NOT: Seq Scan or Sort

// Validate pagination query plans
async function validatePaginationQuery(
  query: string,
  values: unknown[]
): Promise<{ usesIndex: boolean; estimatedCost: number }> {
  const plan = await db.query(
    `EXPLAIN (FORMAT JSON) ${query}`,
    values
  );
 
  const planNode = plan.rows[0]["QUERY PLAN"][0].Plan;
 
  const usesIndex =
    planNode["Node Type"] === "Index Scan" ||
    planNode["Node Type"] === "Index Only Scan";
 
  return {
    usesIndex,
    estimatedCost: planNode["Total Cost"],
  };
}