Why Traditional Limit‑Offset Fails on Billion‑Row Tables and How to Fix It

Why LIMIT‑OFFSET Fails on Billion‑Row Tables

When a table grows to hundreds of millions or billions of rows, the classic LIMIT … OFFSET … pattern becomes a performance bottleneck. MySQL (and similar engines) execute the query in four steps:

Filter rows that satisfy the WHERE clause, producing a temporary result set.

Sort the temporary set (by ORDER BY or the clustered index).

Skip OFFSET rows and return the next LIMIT rows.

Release temporary resources.

With small tables (<10⁵ rows) the cost is negligible, but on a 1.2 billion‑row user_behavior table (InnoDB, primary key id, filter status=1, order create_time DESC) the latency grows exponentially:

Page   Offset   Time(ms)   CPU%
1      0        12         5%
100    990      28         8%
1,000  9,990    156        22%
10,000 99,990   1,280      75%
100,000 999,990 18,600    98%

Three core pain points emerge:

Massive temporary result set – the engine must materialise hundreds of MB or GB before it can skip rows, causing memory pressure and possible OOM.

Expensive sorting – without a suitable index MySQL performs a full‑table scan + filesort; even with an index, a large OFFSET forces the index scan to traverse many entries.

Long‑tail deep pagination – latency grows non‑linearly; beyond page 10 000 the query can take seconds, exhausting connections.

MongoDB’s skip()+limit() suffers the same issue because skip() must walk the cursor to the target position.

Optimization Evolution

1. Basic Index Tuning (Million‑Row Scale)

Creating a composite index that matches the filter and sort columns eliminates the filesort and reduces the temporary set size.

CREATE INDEX idx_status_create_time ON user_behavior (status, create_time DESC);

Benchmark after adding the index:

Page   Offset   Before(ms)   After(ms)   Improvement
1      0        12           8           33%
1,000  9,990    156          42          73%
10,000 99,990   1,280        310         76%

Even with the index, page 100 000 still costs ~4 s, so deeper pagination still fails.

Practical safeguard: limit the maximum page number at the API layer.

// Limit page number to 1,000
if req.Page > 1000 {
    req.Page = 1000
}

2. Seek (Keyset) Pagination (Ten‑Million‑Row Scale)

Seek pagination replaces OFFSET with an “anchor” – the values of the last row of the previous page. The query filters directly on the anchor, e.g. for descending order:

WHERE create_time < :anchorTime
   OR (create_time = :anchorTime AND id < :anchorId)

Execution flow:

First page: no anchor, fetch pageSize rows ordered by create_time DESC, id DESC and record the last row’s create_time and id.

Subsequent pages: use the recorded values as the anchor in the WHERE clause.

Repeat, always using the last row of the previous page as the new anchor.

Go implementation (MySQL):

type UserBehaviorPageReq struct {
    PageSize      int64 `form:"page_size" binding:"required,min=1,max=100"`
    LastCreateTime int64 `form:"last_create_time" binding:"omitempty,min=0"`
    LastId        int64 `form:"last_id" binding:"omitempty,min=0"`
}

func QueryUserBehaviorBySeek(req *UserBehaviorPageReq) (*UserBehaviorPageResp, error) {
    db := gorm.Open(mysql.Open(dsn), &gorm.Config{})
    tx := db.Model(&UserBehavior{}).Where("status = ?", 1)
    if req.LastCreateTime != 0 || req.LastId != 0 {
        tx = tx.Where("create_time < ? OR (create_time = ? AND id < ?)",
            req.LastCreateTime, req.LastCreateTime, req.LastId)
    }
    var behaviors []UserBehavior
    err := tx.Order("create_time DESC, id DESC").Limit(int(req.PageSize)).Find(&behaviors).Error
    if err != nil { return nil, err }
    // Build response with next anchor …
    return &UserBehaviorPageResp{List: behaviors, …}, nil
}

Performance on the same 1.2 billion‑row dataset:

Page   Anchor (time,id)          Time(ms)   CPU%
1      (0,0)                    9          6%
1,000  (1714588800,10000)      11         7%
10,000 (1714502400,100000)    13         8%
100,000(1713638400,1000000)  15         9%

Latency stays under 15 ms even for the 100 000‑th page.

Applicability & limitations:

Works for tens of millions to billions when deep pagination is required.

Cannot jump to an arbitrary page number because each page depends on the previous anchor.

Anchor fields must be unique; duplicate timestamps need a secondary key (e.g., id).

Complex filter conditions not covered by the index degrade performance.

3. Cursor Pagination (Billion‑Row & Complex Scenarios)

Cursor pagination builds on Seek by encoding the anchor (and optional extra filter fields) into an opaque string that the client returns on the next request. This enables stateless pagination, reverse navigation, and richer condition support.

Cursor structure (JSON) and Base64 encoding:

{"status":1,"create_time":1714588800,"id":10000,"sort_direction":"desc"}

Encoded cursor (URL‑safe): MTcxNDU4ODgwMCwxMDAwMCxkZXNj Go implementation (encoding/decoding and query):

type Cursor struct {
    Status        int64  `json:"status"`
    CreateTime    int64  `json:"create_time"`
    Id            int64  `json:"id"`
    SortDirection string `json:"sort_direction"`
}

func EncodeCursor(c *Cursor) (string, error) {
    b, err := json.Marshal(c)
    if err != nil { return "", err }
    return base64.URLEncoding.EncodeToString(b), nil
}

func DecodeCursor(s string) (*Cursor, error) {
    if s == "" { return nil, nil }
    b, err := base64.URLEncoding.DecodeString(s)
    if err != nil { return nil, fmt.Errorf("invalid cursor: %v", err) }
    var c Cursor
    if err := json.Unmarshal(b, &c); err != nil { return nil, fmt.Errorf("invalid cursor format: %v", err) }
    if c.SortDirection != "desc" && c.SortDirection != "asc" { c.SortDirection = "desc" }
    return &c, nil
}

func QueryUserBehaviorByCursor(req *CursorPageReq) (*CursorPageResp, error) {
    db := gorm.Open(mysql.Open(dsn), &gorm.Config{})
    tx := db.Model(&UserBehavior{}).Where("status = ? AND type = ?", 1, req.Type)
    cursor, _ := DecodeCursor(req.Cursor)
    if cursor != nil {
        if cursor.SortDirection == "desc" {
            tx = tx.Where("create_time < ? OR (create_time = ? AND id < ?)",
                cursor.CreateTime, cursor.CreateTime, cursor.Id)
        } else {
            tx = tx.Where("create_time > ? OR (create_time = ? AND id > ?)",
                cursor.CreateTime, cursor.CreateTime, cursor.Id)
        }
    }
    sortStr := "create_time desc, id desc"
    if cursor != nil { sortStr = fmt.Sprintf("create_time %s, id %s", cursor.SortDirection, cursor.SortDirection) }
    var behaviors []UserBehavior
    if err := tx.Order(sortStr).Limit(req.PageSize).Find(&behaviors).Error; err != nil { return nil, err }
    // Build next/prev cursors, hasMore/hasPrev flags …
    return &CursorPageResp{List: behaviors, …}, nil
}

Performance on the 1.2 billion‑row table (including an extra type=2 filter):

Scenario                     Cursor (decoded)                                 Time(ms)   CPU%
First page                   –                                                10        7%
Page 100 000 (deep)          {"status":1,"create_time":1713638400,"id":1000000,"sort_direction":"desc"} 14   8%
Reverse page (prev)          {"status":1,"create_time":1713638400,"id":1000000,"sort_direction":"asc"} 12   7%
Complex filter (type=2)      same as above                                    16        9%

Advantages over plain Seek:

Stateless – the client carries all needed state.

Supports reverse pagination.

Can embed additional filter fields (e.g., type) for multi‑criteria queries.

Opaque encoding improves security.

Extensible for future sorting keys.

Limitations and work‑arounds:

Direct jump to an arbitrary page still impossible; typical mitigation is to guide users to “recent pages” or estimate a timestamp from total count.

Encoding/decoding adds a tiny CPU cost; keep the cursor payload minimal or cache decoded cursors for hot queries.

4. Sharding‑Aware Parallel Merge (Beyond One‑Billion Rows)

When a single table can no longer hold the data, horizontal sharding splits the dataset (e.g., monthly partitions). Global pagination must:

Query each relevant shard in parallel, asking each for the top N rows (where N = pageSize).

Merge‑sort the per‑shard results in the application layer.

Return the final page and generate a cursor for the next request.

Go implementation (simplified):

func QueryShardedUserBehavior(req *CursorPageReq, start, end time.Time) (*CursorPageResp, error) {
    tables := getShardTables(start, end)
    var wg sync.WaitGroup
    var mu sync.Mutex
    var all [][]UserBehavior
    errCh := make(chan error, 1)
    cursor, _ := DecodeCursor(req.Cursor)
    for _, tbl := range tables {
        wg.Add(1)
        go func(t string) {
            defer wg.Done()
            rows, err := queryShardTable(t, req, cursor)
            if err != nil { select { case errCh <- err: default {} }; return }
            mu.Lock(); all = append(all, rows); mu.Unlock()
        }(tbl)
    }
    wg.Wait()
    select { case err := <-errCh: return nil, err; default: {} }
    merged := mergeSort(all)
    return &CursorPageResp{List: merged[:req.PageSize]}, nil
}

func mergeSort(lists [][]UserBehavior) []UserBehavior {
    var all []UserBehavior
    for _, lst := range lists { all = append(all, lst...) }
    sort.Slice(all, func(i, j int) bool {
        if all[i].CreateTime.Unix() == all[j].CreateTime.Unix() {
            return all[i].Id > all[j].Id
        }
        return all[i].CreateTime.Unix() > all[j].CreateTime.Unix()
    })
    return all
}

This approach keeps per‑shard latency low, avoids a full‑table scan across all shards, and scales horizontally.

Takeaways

The progression from plain LIMIT‑OFFSET to composite index tuning, then to Seek pagination, Cursor pagination, and finally sharding‑aware parallel‑merge demonstrates a systematic method for handling pagination at different data scales:

For million‑row tables, a well‑designed composite index can reduce latency by up to 76%.

For tens of millions to billions, Seek pagination provides stable <10 ms latency regardless of page depth.

When stateless navigation, reverse paging, or multi‑field filters are required, Cursor pagination adds negligible overhead while offering flexibility.

In sharded environments, parallel per‑shard queries combined with an in‑process merge sort deliver consistent performance without sacrificing scalability.

Choosing the appropriate technique depends on data volume, required pagination features, and write‑load considerations (e.g., index maintenance cost). The presented benchmarks and code snippets give concrete guidance for implementing each solution in Go with MySQL (or analogous NoSQL stores such as MongoDB).