Masalah I/O pada Offset-based Pagination di Skala Jutaan Baris

Pola pagination konvensional menggunakan klausa LIMIT dan OFFSET. Pola ini bekerja baik pada dataset kecil, namun mengalami degradasi performa eksponensial seiring bertambahnya kedalaman halaman.

Kueri offset bekerja dengan membaca seluruh baris dari awal indeks atau tabel, kemudian membuang baris sejumlah offset yang ditentukan:

-- Mengambil 20 baris di halaman 50.000
SELECT id, title, created_at 
FROM records 
ORDER BY created_at DESC 
LIMIT 20 OFFSET 1000000;

Database engine (MySQL atau PostgreSQL) harus memindai 1.000.020 baris, memuat datanya ke dalam buffer memory, lalu membuang 1.000.000 baris pertama hanya untuk menyajikan 20 baris terakhir. Operasi ini memiliki kompleksitas $O(N + K)$, dengan $N$ adalah offset dan $K$ adalah limit. Dampaknya:

  • Tingginya disk I/O akibat random read pada disk page.
  • Buffer pool thrashing yang mengusir cache data aktif lainnya.
  • Latensi kueri meningkat linier dari beberapa milidetik ke hitungan detik atau timeout.

Struktur Composite Index Sargable untuk Keyset Pagination

Cursor pagination (keyset pagination) menggantikan OFFSET dengan predikat filter berbasis nilai baris terakhir dari halaman sebelumnya. Kompleksitasnya adalah $O(\log M + K)$ konstan, di mana pencarian awal titik data pada B-Tree terjadi secara instan.

-- Keyset query
SELECT id, title, created_at 
FROM records 
WHERE (created_at, id) < ('2024-03-01 10:15:30', 458921) 
ORDER BY created_at DESC, id DESC 
LIMIT 20;

Kueri ini memerlukan indeks komposit sargable yang cocok dengan urutan pengurutan (ordering). Kolom id berfungsi sebagai tie-breaker penjamin sifat deterministik karena kolom waktu seperti created_at rentan memiliki duplikasi nilai pada trafik transaksi tinggi.

Skema migrasi database:

// MySQL & PostgreSQL via Laravel Migration
Schema::table('records', function (Blueprint $table) {
    $table->index(['created_at', 'id'], 'idx_records_created_at_id');
});

Aturan penyusunan indeks:

  • Urutan kolom pada indeks harus identik dengan klausa ORDER BY.
  • Arah pengurutan (ASC/DESC) harus konsisten di seluruh kolom yang terlibat pada kueri multi-kolom di PostgreSQL untuk memastikan Index Scan satu arah (bukan Backward Index Scan yang mahal).

Analisis Query Execution: Keyset vs Offset (EXPLAIN ANALYZE)

Pengujian pada tabel PostgreSQL berisi 5.000.000 baris menunjukkan perbedaan alokasi resource eksekusi kueri.

1. Offset Query Plan

EXPLAIN ANALYZE
SELECT * FROM records ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 1000000;

-- Hasil:
-- Limit  (cost=145220.12..145223.02 rows=20 width=128) (actual time=812.431..812.445 rows=20 loops=1)
--   ->  Index Scan using idx_records_created_at_id on records  (cost=0.43..726100.58 rows=5000000 width=128) (actual time=0.048..764.120 rows=1000020 loops=1)
-- Planning Time: 0.121 ms
-- Execution Time: 812.480 ms

Database membaca 1.000.020 baris riil dari indeks sebelum membuangnya.

2. Keyset Query Plan

EXPLAIN ANALYZE
SELECT * FROM records 
WHERE (created_at, id) < ('2024-03-01 10:15:30', 458921)
ORDER BY created_at DESC, id DESC 
LIMIT 20;

-- Hasil:
-- Limit  (cost=0.43..3.35 rows=20 width=128) (actual time=0.038..0.052 rows=20 loops=1)
--   ->  Index Scan using idx_records_created_at_id on records  (cost=0.43..345210.20 rows=2350100 width=128) (actual time=0.037..0.049 rows=20 loops=1)
--         Index Cond: (ROW(created_at, id) < ROW('2024-03-01 10:15:30'::timestamp, 458921))
-- Planning Time: 0.145 ms
-- Execution Time: 0.075 ms

Pola keyset langsung melompat ke node indeks yang ditargetkan tanpa scanning baris redundan. Eksekusi terpangkas dari ratusan milidetik menjadi di bawah satu milidetik.

Implementasi Backend: cursorPaginate() pada Controller Laravel

Laravel menyediakan metode cursorPaginate() yang mengenkripsi parameter keyset ke dalam string base64 cursor yang aman digunakan pada HTTP query string.

namespace App\Http\Controllers;

use App\Models\Record;
use Illuminate\Http\Request;
use Inertia\Inertia;
use Inertia\Response;

class RecordController extends Controller
{
    public function index(Request $request): Response
    {
        $records = Record::query()
            ->select(['id', 'title', 'status', 'created_at'])
            ->orderByDesc('created_at')
            ->orderByDesc('id')
            ->cursorPaginate(25)
            ->withQueryString();

        return Inertia::render('Records/Index', [
            'records' => $records,
        ]);
    }
}

Payload yang dikirim ke Inertia berisi array data dan pointer cursor:

{
  "data": [...],
  "path": "https://example.com/records",
  "per_page": 25,
  "next_cursor": "eyJjcmVhdGVkX2F0IjoiMjAyNC0wMy0wMSAxMDoxNTozMCIsImlkIjo0NTg5MjF9",
  "next_page_url": "https://example.com/records?cursor=eyJjcmVhdGVkX2F0IjoiMjAyNC0wMy0wMSAxMDoxNTozMCIsImlkIjo0NTg5MjF9",
  "prev_cursor": null,
  "prev_page_url": null
}

Implementasi Frontend: Infinite Scroll dengan Inertia Merge Props

Pengambilan data berulang pada infinite scroll berisiko me-replace state lokal atau menyebabkan re-render penuh pada DOM tree. Untuk mempertahankan state lama dan menggabungkan data baru, gunakan fitur partial reload Inertia dikombinasikan dengan preserve scroll.

Komponen Vue 3 dengan Intersection Observer

<script setup>
import { ref, onMounted, onUnmounted } from 'vue';
import { router } from '@inertiajs/vue3';

const props = defineProps({
  records: Object
});

const items = ref([...props.records.data]);
const nextUrl = ref(props.records.next_page_url);
const loadTrigger = ref(null);
const isLoading = ref(false);

const loadMore = () => {
  if (!nextUrl.value || isLoading.value) return;

  isLoading.value = true;
  router.get(
    nextUrl.value,
    {},
    {
      preserveState: true,
      preserveScroll: true,
      only: ['records'],
      onSuccess: (page) => {
        items.value.push(...page.props.records.data);
        nextUrl.value = page.props.records.next_page_url;
        isLoading.value = false;
      },
      onError: () => {
        isLoading.value = false;
      }
    }
  );
};

let observer;
onMounted(() => {
  observer = new IntersectionObserver(([entry]) => {
    if (entry.isIntersecting) {
      loadMore();
    }
  }, { threshold: 0.1 });

  if (loadTrigger.value) {
    observer.observe(loadTrigger.value);
  }
});

onUnmounted(() => {
  if (observer) observer.disconnect();
});
</script>

<template>
  <div class="container mx-auto py-6">
    <div class="divide-y divide-gray-200 border rounded-lg bg-white">
      <div v-for="record in items" :key="record.id" class="p-4 flex justify-between">
        <span class="font-medium">{{ record.title }}</span>
        <span class="text-sm text-gray-500">{{ record.created_at }}</span>
      </div>
    </div>

    <div ref="loadTrigger" class="py-4 text-center text-sm text-gray-400">
      <span v-if="isLoading">Memuat data...</span>
      <span v-else-if="!nextUrl">Semua data telah ditampilkan.</span>
    </div>
  </div>
</template>

Batasan Teknis Cursor Pagination

Penggunaan keyset pagination memerlukan kompromi fungsionalitas tertentu:

  • Tidak Ada Lompatan Acak (No Arbitrary Page Jumps): User tidak dapat melompat langsung ke halaman 50. Navigasi hanya mendukung next dan previous.
  • Ketergantungan Strict Ordering: Kueri harus memiliki predikat ORDER BY yang terikat langsung ke indeks. Pengurutan dinamis berdasarkan banyak kolom dinamis sulit dioptimasi tanpa composite index terpisah untuk tiap permutasi kolom.
  • Inkonsistensi Total Records: cursorPaginate() tidak mengeksekusi kueri COUNT(*) secara default demi performa. Antarmuka tidak dapat menampilkan total halaman atau total records tanpa kueri agregasi terpisah.