# Constant-Time Chat Pagination in MongoDB Using Sequential Message Indexing

Canonical: https://airs0urce.com/blog/constant-time-chat-pagination-mongodb

Most chat applications start with the same pagination approach: sort messages by date, use `skip()` and `limit()` to grab a page. It works at first. Then your users accumulate thousands of messages per conversation and the endpoint that loads page 200 takes noticeably longer than page 1. This article describes an alternative approach — assigning each message a sequential integer index within its conversation — that gives you O(1) pagination performance regardless of conversation depth.

## The Problem with Conventional Approaches

### Cursor-based pagination with `skip()`/`limit()`

```javascript
db.messages.find({ chatId: "abc" })
  .sort({ createdAt: -1 })
  .skip(page * pageSize)
  .limit(pageSize)
```

MongoDB must scan and discard all `skip` documents before returning results. Loading page 100 of a 15-message page means MongoDB internally iterates through 1,500 documents, throws away 1,485, and returns 15. The deeper the user scrolls, the slower it gets. This is O(n) where n is the offset — linear degradation.

### Cursor-based pagination with `_id` or timestamp

```javascript
db.messages.find({ chatId: "abc", createdAt: { $lt: lastSeenTimestamp } })
  .sort({ createdAt: -1 })
  .limit(pageSize)
```

This avoids the `skip()` problem and is a popular improvement. It performs well for sequential scrolling (get next page, get next page). But it has limitations:

- **No random access.** You can't jump to "page 50" or "30% through the conversation" without scanning forward from the beginning.
- **Timestamps aren't unique.** Two messages sent in the same millisecond can cause missed or duplicated results. You need a tiebreaker (usually `_id`), adding complexity.
- **Bidirectional scrolling is awkward.** Loading messages both above and below a reference point requires two queries with different sort directions and merging results.

## The Solution: Sequential Integer Indexing

The core idea: assign each message between two users a sequential integer `i`, starting at 1. Message 1 is the first message ever sent in the conversation, message 2 is the second, and so on.

### Schema

Each message document in the `chats_messages` collection:

```javascript
{
  _id: ObjectId("..."),
  u1: ObjectId("sender_id"),     // sender
  u2: ObjectId("receiver_id"),   // receiver
  type: "text",
  sub_type: "plain",
  msg: "hey, what's up?",
  cdt: ISODate("2024-01-15T10:30:00Z"),
  i: 42                          // sequential message number within this conversation
}
```

A separate `chats` collection tracks metadata for each conversation pair, including per-user message counters (`umin_total`, `umax_total`) that serve as the source of truth for what the next `i` value should be.

### User ID Normalization

To avoid duplicate chat records (user A chatting with user B vs. user B chatting with user A), the chat record always stores users in a deterministic order — the smaller ObjectId goes in `umin`, the larger in `umax`:

```javascript
// Always stored as: { umin: smallerId, umax: largerId }
if (userId1 > userId2) {
    query = { umin: userId2, umax: userId1 };
} else {
    query = { umin: userId1, umax: userId2 };
}
```

This means each conversation has exactly one chat record. The `umin_total` field tracks how many messages the user with the smaller ID has sent; `umax_total` tracks the other. The sum gives the total messages in the conversation, and the next message gets `i = umin_total + umax_total + 1`.

### Assigning the Index on Write

When a new message is sent:

```javascript
const chatRecord = await this.getRecord(fromUserId, toUserId, {
    _id: 0, umin_total: 1, umax_total: 1
});

let lastMessageIndex = 0;
if (chatRecord) {
    if (chatRecord.umin_total) lastMessageIndex += chatRecord.umin_total;
    if (chatRecord.umax_total) lastMessageIndex += chatRecord.umax_total;
}

const chatMessage = {
    u1: ObjectId(fromUserId),
    u2: ObjectId(toUserId),
    type: type,
    sub_type: subType,
    msg: msg,
    cdt: new Date(),
    i: lastMessageIndex + 1
};

await colChatsMessages.insertOne(chatMessage);
```

After inserting, the sender's total counter is atomically incremented on the chat record via `$inc: { [prefix + '_total']: 1 }`. This keeps the counters in sync for the next message.

### The Compound Index

The single most important piece:

```javascript
db.chats_messages.createIndex({ u1: 1, u2: 1, i: 1 })
```

This compound index covers the exact query pattern used for pagination — filter by the two participants, then range-scan on `i`.

### Querying a Page

The pagination method accepts:

- `offsetMID` — a message ID (or the special values `'first'`/`'last'`) as the reference point
- `addOffset` — a signed integer that shifts the window relative to the reference (negative to go backward)
- `limit` — page size (default 15)

```javascript
// Step 1: Resolve the reference message's sequential index
let offsetMsgNumber = 1;
if (offsetMID) {
    const offsetChatMessage = await colChatsMessages.findOne(
        { _id: new ObjectId(offsetMID) },
        { _id: 0, i: 1 }
    );
    offsetMsgNumber = offsetChatMessage.i;
}

// Step 2: Compute the numeric range
let offsetFrom = offsetMsgNumber + addOffset;
let offsetTo = offsetFrom + limit;

// Step 3: Range query — this is the fast part
const records = await colChatsMessages.find(
    {
        $or: [
            { u1: userId1, u2: userId2 },
            { u1: userId2, u2: userId1 }
        ],
        i: { $gt: offsetFrom, $lt: offsetTo }
    },
    { sort: { i: 1 } }
).toArray();
```

This is the key insight: **pagination becomes simple integer arithmetic.** The query planner uses the `{u1, u2, i}` index to seek directly to the first matching document and scan forward exactly `limit` entries. No skipping. No timestamp comparison ambiguity. No cursor state to maintain between requests.

### Why the `$or` is Necessary

A message from Alice to Bob is stored as `{u1: Alice, u2: Bob}`. A message from Bob to Alice is `{u1: Bob, u2: Alice}`. To get all messages in the conversation, the query must check both directions. The `$or` causes MongoDB to execute two index scans (one for each branch) and merge the results, but both scans are range-bounded by `i`, so the total work is proportional to the page size, not the conversation size.

### Bidirectional Scrolling

Because the index is a simple integer, scrolling in both directions is trivial:

- **Scroll up (older messages):** `addOffset = -15` shifts the window backward
- **Scroll down (newer messages):** `addOffset = 0` or positive value
- **Jump to arbitrary position:** set `addOffset` to any value. Want messages 500-515? Set the offset so `offsetFrom = 499`.

There is no need for a separate "reverse sort" query or cursor management. It's all just arithmetic on `i`.

## Performance Characteristics

| Operation | `skip()`/`limit()` | Timestamp cursor | Sequential `i` index |
| --- | --- | --- | --- |
| First page | O(pageSize) | O(pageSize) | O(pageSize) |
| Page N | O(N * pageSize) | O(pageSize) | O(pageSize) |
| Random access to page N | O(N * pageSize) | O(N * pageSize) | O(pageSize) |
| Bidirectional scroll | Two queries | Two queries, reverse sort | Single query, arithmetic offset |
| Jump to "50% through" | Not practical | Not practical | `i = totalMessages / 2` |

The sequential index approach has **constant time per page** regardless of position in the conversation. MongoDB performs an index seek (O(log n) on the B-tree depth, which is effectively constant for practical collection sizes) followed by a forward scan of exactly `limit` documents.

## Making It Even Faster: Covered Queries

A MongoDB **covered query** is one that can be answered entirely from the index without touching the actual documents on disk. The query planner only reads the B-tree index entries, skipping the document fetch step entirely.

For the current index `{u1: 1, u2: 1, i: 1}`, a query is covered if it only filters on and projects fields that exist in the index — `u1`, `u2`, and `i`. The moment you need `msg`, `type`, `cdt`, or any other field, MongoDB must fetch the full document.

### Adding Fields to the Index

You can extend the index to include frequently needed fields:

```javascript
db.chats_messages.createIndex({
    u1: 1,
    u2: 1,
    i: 1,
    type: 1,
    sub_type: 1,
    msg: 1,
    cdt: 1,
    msg_self: 1
})
```

With this index, the pagination query could return complete message data without ever reading the collection's documents. MongoDB would walk the B-tree, extract the field values from the index entries, and return them directly.

You can verify this with `explain()`:

```javascript
db.chats_messages.find(
    {
        $or: [
            { u1: userId1, u2: userId2 },
            { u1: userId2, u2: userId1 }
        ],
        i: { $gt: 100, $lt: 116 }
    },
    {
        projection: {
            _id: 0, u1: 1, u2: 1, i: 1,
            type: 1, sub_type: 1, msg: 1, cdt: 1, msg_self: 1
        }
    }
).sort({ i: 1 }).explain("executionStats")
```

Look for `"totalDocsExamined": 0` and stage `IXSCAN` without a `FETCH` — that confirms a covered query.

### The Trade-Off: RAM

Indexes live in RAM (or at least MongoDB strongly prefers them to). A lean index like `{u1, u2, i}` stores three small values per message — two 12-byte ObjectIds and a 4-byte integer, roughly 28 bytes of key data plus B-tree overhead per entry. With 100 million messages, this index might consume ~4-5 GB of RAM.

A fat covered-query index that includes `msg` (a variable-length string, potentially hundreds of bytes per message) changes the equation dramatically. If the average message is 100 characters, that's ~100 bytes added per index entry. For 100 million messages:

| Index | Approximate key size per entry | ~RAM for 100M messages |
| --- | --- | --- |
| `{u1, u2, i}` | ~28 bytes | ~4-5 GB |
| `{u1, u2, i, type, sub_type, msg, cdt, msg_self}` | ~250+ bytes | ~30-40 GB |

This is a classic space-time trade-off. The covered index eliminates disk reads for the pagination query, which matters most when:

- Your working set doesn't fit in RAM and MongoDB is doing frequent disk reads
- You're running on storage with high latency (e.g., network-attached storage, spinning disks)
- Query latency SLA is extremely tight

If your dataset fits comfortably in RAM (documents are cached in WiredTiger's cache anyway), the covered query optimization gives diminishing returns — the documents are already in memory, so the "fetch" step is just a pointer dereference, not a disk seek.

### A Practical Middle Ground

Instead of indexing every field, index only the small, fixed-size fields you always project:

```javascript
db.chats_messages.createIndex({
    u1: 1, u2: 1, i: 1,
    type: 1, sub_type: 1, cdt: 1
})
```

This keeps the index reasonably sized (adds ~30 bytes per entry for the three extra short fields) while covering queries that list messages with metadata but lazy-load the actual message body. A chat UI could render the message list frame (timestamps, types, bubble layout) from the covered query, then fetch message text on demand or in a second pass.

## Data Migration

If you're adding sequential indexing to an existing collection, you need a backfill script. The approach is straightforward: iterate through each conversation, sort messages by `_id` (which is monotonically increasing with insertion time), and assign `i` values starting at 1:

```javascript
const cursor = colChats.find({}, { projection: { umax: 1, umin: 1 } });
cursor.addCursorFlag('noCursorTimeout', true);

for await (const chat of cursor) {
    const messageCursor = colChatMessages.find(
        {
            $or: [
                { u1: chat.umax, u2: chat.umin },
                { u2: chat.umax, u1: chat.umin }
            ]
        },
        { sort: { _id: 1 }, projection: { _id: 1 } }
    );

    let i = 1;
    for await (const msg of messageCursor) {
        await colChatMessages.updateOne(
            { _id: msg._id },
            { $set: { i: i } }
        );
        i++;
    }
}
```

**Important notes for production migration:**

- Use `noCursorTimeout` — this will take a while on large collections.
- Run during low-traffic periods. Each `updateOne` modifies a document and updates indexes.
- Monitor replication lag if running on a replica set.
- After backfill, create the `{u1, u2, i}` index (creating before backfill would slow down all those updates).
- The application code must be deployed to assign `i` on new messages *before* or *simultaneously with* the backfill, so no messages are missed.

## Why Individual Message Deletion Is Not Supported (By Design)

A common question when people see this approach: "What happens to the sequence when you delete a message?"

The answer is simple — **individual message deletion is not supported**, and this is a deliberate design decision, not a limitation.

### The Problem with Deletion

If message `i=5` is deleted from a conversation with 10 messages, you have two options, both bad:

**Option A: Leave the gap.** The sequence becomes `1, 2, 3, 4, 6, 7, 8, 9, 10`. Now your pagination arithmetic is broken. A query for `i > 0 AND i < 16` expects 15 messages but returns 14. The client requested a page of 15 — should it know to ask for more? Do you over-fetch and filter? Every query now needs to account for an unknown number of gaps, and you've lost the core property that makes this approach fast: a predictable, gapless sequence where the count of messages between any two `i` values is exactly `i2 - i1 - 1`.

**Option B: Re-number everything after the gap.** Shift messages 6-10 down to 5-9, update the counters, update any client-side caches referencing those message IDs by their old `i` values. For a conversation with 50,000 messages where message 3 is deleted, you're rewriting 49,997 documents and their index entries. This is an O(n) operation that locks the conversation, defeats the purpose of the optimization, and introduces a window where concurrent reads see inconsistent data.

Neither option is acceptable. Gaps break pagination arithmetic. Re-numbering is prohibitively expensive. This means **gapless sequential indexing and individual message deletion are fundamentally incompatible** — you have to choose one.

### What Happens Instead

In our system, the operations that exist are:

**Delete entire conversation** — when a user deletes a chat (unmatch), the chat record is soft-deleted with a `{ deleted: true }` flag. The messages remain in the collection untouched. No sequence numbers are affected. The conversation simply stops appearing in the chat list.

```javascript
await colChats.updateOne(
    { _id: record._id },
    { $set: { deleted: true } }
);
```

**Full account deletion (GDPR/privacy)** — when a user deletes their account entirely, *all* their messages across all conversations are hard-deleted in bulk. There's no need to preserve sequence integrity because the conversations themselves are being destroyed:

```javascript
await colChatsMessages.deleteMany({ $or: [{ u1: userId }, { u2: userId }] });
await colChats.deleteMany({ $or: [{ umin: userId }, { umax: userId }] });
```

This is not a surgical per-message operation — it's a full wipe. The sequence numbers are irrelevant because there is no conversation left to paginate.

Neither operation creates gaps in an otherwise active sequence.

### If You Truly Need Message Deletion

If your product requirements demand individual message deletion (like a "delete for everyone" feature), you have a few approaches that preserve the sequential indexing benefits:

- **Soft delete with a flag.** Add a `deleted: true` field to the message document. The message keeps its `i` value. The pagination query stays unchanged — the message is still fetched but the application layer replaces its content with "This message was deleted" (the WhatsApp approach). The sequence stays gapless. This is the cheapest solution and preserves all performance properties.
- **Soft delete with a filtered projection.** Same as above, but you filter deleted messages in the application layer and request slightly more than `limit` to compensate for potential deleted messages in the range. This works if deletions are rare — if 1 in 1,000 messages is deleted, over-fetching by 1-2% is negligible.

Both approaches keep the sequence intact. The principle is: **the `i` field is an immutable physical position, not a logical display index.** Once assigned, it never changes.

## Concurrency Considerations

A natural question: what happens when two messages are sent in the same conversation at the same instant? Both would read the same `umin_total + umax_total`, compute the same `i`, and insert duplicate sequence numbers.

In practice, this is handled at the chat record level. The `$inc` operation on the chat record's counter is atomic in MongoDB. As long as the read-then-write sequence (read totals, compute `i`, insert message, increment counter) is serialized per conversation — for example, via an application-level lock per chat pair — the sequence numbers stay unique and gapless.

In our implementation, we use a Redis-based distributed lock keyed on the conversation pair to ensure sequential processing of messages within the same chat. The lock hold time is short (just the duration of one insert + one update), so contention is minimal.

## Summary

Sequential integer indexing for chat pagination trades a small amount of write-path complexity (maintaining counters, assigning `i`) for dramatically better read-path performance. The pagination query becomes a bounded range scan on an indexed integer — constant time regardless of conversation depth, trivial bidirectional scrolling, and random access to any position in the conversation.

For most chat applications, the lean `{u1, u2, i}` compound index hits the sweet spot. If you need to squeeze out more performance and can afford the memory, a wider covered-query index eliminates document fetches entirely. Measure your actual working set and access patterns before committing to the fat index — the RAM cost grows linearly with your message volume and average message size.