Root Cause: Mengapa OFFSET Melambat pada Dataset Masif

Pola pagination standar menggunakan SQL LIMIT x OFFSET y mengalami degradasi performa eksponensial seiring bertambahnya nilai offset. Masalah ini berakar dari cara storage engine memproses query. Saat mengeksekusi:

SELECT id, title, created_at 
FROM articles 
ORDER BY created_at DESC 
LIMIT 20 OFFSET 500000;

Database tidak langsung melompat ke baris nomor 500.001. Database membaca 500.020 baris dari disk atau memory buffer, mengurutkannya, lalu membuang (discard) 500.000 baris pertama hanya untuk mengembalikan 20 baris terakhir. Kompleksitas I/O dan CPU operasi ini adalah O(N) terhadap nilai offset. Pola ini memicu memory churn tinggi, cache eviction pada buffer pool, dan disk read berlebih.

Perbandingan Eksekusi Melalui EXPLAIN ANALYZE

Rencana eksekusi OFFSET pada PostgreSQL menunjukkan pola bottleneck tersebut:

-- Pola OFFSET pada dataset 1 juta baris
EXPLAIN ANALYZE
SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 500000;

-- Output:
Limit  (cost=42512.30..42514.00 rows=20 width=40) (actual time=142.312..142.318 rows=20 loops=1)
  ->  Index Scan using idx_articles_created_at_id on articles (cost=0.42..85024.18 rows=1000000 width=40) (actual time=0.035..118.520 rows=500020 loops=1)
Execution Time: 142.350 ms

Eksekusi membaca 500.020 baris riil (actual rows=500020) sebelum membuangnya. Waktu eksekusi mencapai ratusan milidetik. Sebaliknya, keyset pagination mengeliminasi pembacaan baris yang tidak dibutuhkan melalui filter penunjuk (cursor).

Perancangan Keyset dan Composite Index

Keyset pagination (cursor pagination) memanfaatkan nilai kolom dari baris terakhir yang diambil sebagai batas pencarian baris berikutnya. Kompleksitas operasi berubah menjadi O(1) atau O(log N) bergantung pada kedalaman B-Tree index.

Penanganan Duplikasi Timestamp via Tie-Breaker

Menggunakan satu kolom pengurutan seperti created_at memicu anomali hilangnya data jika terdapat baris dengan timestamp identik. Kolom penanda unik (umumnya primary key id) wajib disertakan sebagai tie-breaker untuk menjamin urutan deterministik.

Penyusunan Composite Index

Buat composite index yang urutannya presisi dengan klausa ORDER BY pada skema SQL:

CREATE INDEX idx_articles_created_at_id ON articles (created_at DESC, id DESC);

Dengan index ini, query pagination menggunakan filter tuple comparison:

SELECT id, title, created_at
FROM articles
WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 20;

Hasil EXPLAIN ANALYZE pada keyset pagination:

Index Scan using idx_articles_created_at_id on articles (cost=0.42..4.85 rows=20 width=40) (actual time=0.028..0.045 rows=20 loops=1)
  Index Cond: (ROW(created_at, id) < ROW('2024-03-01 10:00:00'::timestamp, 450123))
Execution Time: 0.065 ms

Query langsung mengarahkan pointer B-Tree ke lokasi record tanpa membaca 500.000 row sebelumnya. Waktu eksekusi terpangkas secara signifikan dari 142 ms menjadi di bawah 0.1 ms.

Implementasi pada Go Fiber

Contoh berikut mendemonstrasikan parsing cursor Base64, context forwarding via c.UserContext() untuk memastikan pembatalan query saat client disconnect, serta eksekusi SQL tuple-comparison.

Definisi Tipe Data dan Handler Cursor

package main

import (
	"context"
	"database/sql"
	"encoding/base64"
	"fmt"
	"strconv"
	"strings"
	"time"

	"github.com/gofiber/fiber/v2"
	_ "github.com/jackc/pgx/v5/stdlib"
)

type Article struct {
	ID        int64     `json:"id"`
	Title     string    `json:"title"`
	CreatedAt time.Time `json:"created_at"`
}

type PaginatedResponse struct {
	Data       []Article `json:"data"`
	NextCursor string    `json:"next_cursor,omitempty"`
	HasMore    bool      `json:"has_more"`
}

func encodeCursor(t time.Time, id int64) string {
	raw := fmt.Sprintf("%s,%d", t.Format(time.RFC3339Nano), id)
	return base64.RawURLEncoding.EncodeToString([]byte(raw))
}

func decodeCursor(cursorStr string) (time.Time, int64, error) {
	bytes, err := base64.RawURLEncoding.DecodeString(cursorStr)
	if err != nil {
		return time.Time{}, 0, err
	}
	parts := strings.Split(string(bytes), ",")
	if len(parts) != 2 {
		return time.Time{}, 0, fmt.Errorf("invalid cursor format")
	}
	t, err := time.Parse(time.RFC3339Nano, parts[0])
	if err != nil {
		return time.Time{}, 0, err
	}
	id, err := strconv.ParseInt(parts[1], 10, 64)
	if err != nil {
		return time.Time{}, 0, err
	}
	return t, id, nil
}

Handler Endpoint Go Fiber

func GetArticlesHandler(db *sql.DB) fiber.Handler {
	return func(c *fiber.Ctx) error {
		limit := c.QueryInt("limit", 20)
		if limit <= 0 || limit > 100 {
			limit = 20
		}

		cursorParam := c.Query("cursor", "")
		ctx := c.UserContext() // Meneruskan fiber request context ke driver SQL

		var rows *sql.Rows
		var err error

		// Mengambil limit + 1 untuk mendeteksi ketersediaan halaman berikutnya
		fetchLimit := limit + 1

		if cursorParam == "" {
			query := `
				SELECT id, title, created_at 
				FROM articles 
				ORDER BY created_at DESC, id DESC 
				LIMIT $1`
			rows, err = db.QueryContext(ctx, query, fetchLimit)
		} else {
			lastTime, lastID, decodeErr := decodeCursor(cursorParam)
			if decodeErr != nil {
				return c.Status(fiber.StatusBadRequest).JSON(fiber.Map{
					"error": "Format cursor tidak valid",
				})
			}

			// Menggunakan tuple comparison (PostgreSQL row constructor)
			query := `
				SELECT id, title, created_at 
				FROM articles 
				WHERE (created_at, id) < ($1, $2)
				ORDER BY created_at DESC, id DESC 
				LIMIT $3`
			rows, err = db.QueryContext(ctx, query, lastTime, lastID, fetchLimit)
		}

		if err != nil {
			return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{
				"error": "Gagal mengambil data",
			})
		}
		defer rows.Close()

		articles := make([]Article, 0, limit)
		for rows.Next() {
			var a Article
			if err := rows.Scan(&a.ID, &a.Title, &a.CreatedAt); err != nil {
				return c.Status(fiber.StatusInternalServerError).JSON(fiber.Map{
					"error": "Gagal membaca baris data",
				})
			}
			articles = append(articles, a)
		}

		hasMore := false
		var nextCursor string

		if len(articles) > limit {
			hasMore = true
			articles = articles[:limit] // Potong elemen ke-(limit+1)
			lastItem := articles[len(articles)-1]
			nextCursor = encodeCursor(lastItem.CreatedAt, lastItem.ID)
		}

		return c.JSON(PaginatedResponse{
			Data:       articles,
			NextCursor: nextCursor,
			HasMore:    hasMore,
		})
	}
}

Alternatif Tuple Comparison untuk Database Non-Row Constructor

PostgreSQL menangani perbandingan tuple (created_at, id) < ($1, $2) secara native melalui B-Tree index. Jika menggunakan mesin database SQL lain yang memiliki optimasi terbatas pada row-value constructor, ubah klausa WHERE menjadi bentuk aljabar boolean eksplisit:

WHERE created_at < $1 OR (created_at = $1 AND id < $2)
Catatan: Penulisan ekspresi boolean di atas setara secara logika dengan tuple comparison, namun verifikasi rencana query menggunakan EXPLAIN untuk memastikan database planner tidak beralih menggunakan Bitmap Or Scan yang kurang efisien dibanding Index Scan tunggal.

Trade-off dan Limitasi Keyset Pagination

  • Tidak mendukung direct page jump: Klien tidak dapat langsung melompat ke halaman 15 tanpa mengambil data halaman 1 sampai 14 secara sekuensial. Keyset pagination ideal untuk infinite scroll atau tombol antarmuka Next/Previous.
  • Ketergantungan stabilitas index: Kolom yang digunakan dalam keyset tidak boleh sering diperbarui (immutable atau append-mostly direkomendasikan). Menggunakan kolom yang terus berubah nilainya dapat menyebabkan record bergeser posisi dan terlewat dari pagination.
  • Navigasi dua arah (Bidirectional): Untuk berpindah ke halaman sebelumnya (prev), ubah arah operator (>) dan balikkan urutan sorting (ASC), kemudian urutkan kembali hasil query di level memori aplikasi sebelum mengirimkan response ke client.