From Offset to Keyset Pagination: Cutting a 45-Minute Push Notification Job to 2 Minutes

I maintain the push notification backend for a service with roughly 900,000 registered users. Once a day it walks the entire user table, filters people by how long ago they last logged in, collects their FCM tokens, and hands the set off to a send worker.

For a long time the walk was the slow part. Not the sending — the walking. The whole collection phase averaged 45 minutes.

The fix was replacing offset pagination with keyset pagination, which is a well-known trick. What was less well-known to me is that keyset pagination has a failure mode offset pagination doesn't have, and I shipped a version with two of them in it before I understood what I'd done. That part is the more useful half of this post.

Stack: NestJS 11, TypeORM 0.3.x, SQL Server 2019, BullMQ for job orchestration.

On the numbers in this post: the job-level timings (45 minutes, 2 minutes) and the token counts are what I measured in production. The per-query page counts are derived from a row-width model that I show my work for, not captured from a profiler run on the day. I'll flag which is which as I go, because a page-count model you can check beats a millisecond figure you can't reproduce.

The starting point

The original implementation used skip() / take():

// notification.service.ts — original
async getUserTokensForNotification(offset: number, limit: number): Promise<User[]> {
  return this.users
    .createQueryBuilder('user')
    .select(['user.push_token', 'user.logindate'])
    .orderBy('user.id', 'ASC')
    .skip(offset)
    .take(limit)
    .getMany();
}

// collection loop
const BATCH_SIZE = 1000;
for (let page = 0; page < totalPages; page++) {
  const users = await this.getUserTokensForNotification(page * BATCH_SIZE, BATCH_SIZE);
  collect(users);
}

On SQL Server this compiles to OFFSET ... ROWS FETCH NEXT ... ROWS ONLY:

SELECT push_token, logindate
FROM dbo.users
ORDER BY id
OFFSET 500000 ROWS FETCH NEXT 1000 ROWS ONLY;

If you want to see exactly what your version of TypeORM emits, turn on logging: ['query'] in the data source options. I'd recommend doing that before trusting anything you read about generated SQL, including this post.

Two separate problems, not one

The first is the one everyone talks about. OFFSET doesn't skip work — it does the work and throws it away. The engine reads rows in order, discards the first N, returns the next batch. OFFSET 500000 reads half a million rows to hand you a thousand. Cost grows linearly with depth.

The second problem was mine: I was ordering by id, a UUID.

A random UUID is a poor choice for the key you order by, for two independent reasons. As a clustering key it means every insert lands at a random point in the B-tree, which causes page splits and leaves the leaf pages partially full — so the table occupies more pages than its data actually needs, and every scan pays for that. And as a cursor key it's disqualifying, because keyset pagination needs key > @last to correspond to "further along in the scan," which requires the key to be monotonically increasing. A UUID isn't.

Luckily the table already had a seq column — an IDENTITY integer left over from the legacy system. That column is what made the rest of this possible.

What it costs, in a unit that doesn't drift

I'm going to reason in logical reads rather than milliseconds. Elapsed time depends on buffer pool state, concurrent load, and hardware, so it's the number people argue about. Logical reads is the count of 8 KB pages the engine touched, and it falls out of the table's physical layout — you can derive it and check my arithmetic.

Here's the model. Substitute your own numbers:

• ~940,000 rows (the table predates the current product and holds some rows that aren't active accounts, which is why it's larger than the user count above)
• Clustered on the UUID primary key, so ORDER BY id is an ordered scan of the clustered index
• A wide legacy row (30-odd columns, plenty of nvarchar) plus the split-induced slack described above puts it around 10 rows per 8 KB page — call it ~94,000 leaf pages for the table An offset query has to read (offset + batch) / 10 pages before it can return anything:

Query	Rows read to answer	Pages ≈
OFFSET 0 ROWS FETCH NEXT 1000	1,000	~100
OFFSET 100000 ROWS FETCH NEXT 1000	101,000	~10,100
OFFSET 500000 ROWS FETCH NEXT 1000	501,000	~50,100
OFFSET 900000 ROWS FETCH NEXT 1000	901,000	~90,100

The last query does about 900× the page reads of the first one to return the same 1,000 rows. At 8 KB a page, that's roughly 700 MB moving through the buffer pool to produce one batch.

You can confirm the shape on your own instance in about a minute: SET STATISTICS IO ON, run the same query at four depths, watch the logical reads figure climb in step with the offset. That's the property that matters, and it doesn't depend on my hardware or yours.

I never instrumented the 45-minute collection phase finely enough to say what fraction was query time and what fraction was everything else. Take the 45 minutes as a job-level measurement, not as a claim about where every second went.

The correctness problem nobody notices until it bites

Offset pagination assumes the result set holds still while you page through it. It doesn't.

If someone registers mid-run, rows after their insert position shift, and the row that sat on a page boundary gets served twice. If an account is deleted, a row gets skipped. On a table taking writes continuously for 45 minutes, "some users got two pushes, some got none" isn't hypothetical — it was a recurring complaint.

This is the argument I'd lead with if I were making the case to a product manager. The performance number is easier to sell; the correctness bug is the one that costs you trust.

Keyset pagination

Instead of counting rows to skip, you remember where you stopped and seek straight there:

SELECT TOP (1001) seq, push_token, logindate
FROM dbo.users
WHERE seq > @lastSeq
ORDER BY seq;

With the right index, seq > @lastSeq is a seek predicate. The engine descends the B-tree once and reads forward. Depth stops mattering.

The index

My first version had a single-column index on seq. That's the minimum, not the target:

CREATE UNIQUE NONCLUSTERED INDEX IX_users_seq
  ON dbo.users (seq ASC)
  INCLUDE (push_token, logindate);

UNIQUE is not decoration. WHERE seq > @lastSeq is only correct if seq is unique. If two rows share a value and one of them lands on a page boundary, the next query's strict > steps straight over its twin. Uniqueness is a precondition of the technique, not an optimization on top of it.

INCLUDE keeps the query covering. Without it, every row costs a key lookup back into the clustered index, and 940,000 key lookups is not free.

With that index, the same model says a page costs about 55 reads: the leaf row holds seq, push_token, logindate and the 16-byte clustering key — on the order of 400 bytes, so roughly 19 rows per page, so ~53 leaf pages for 1,001 rows, plus a couple for the descent.

The number isn't the point. Flatness is the point. Page 900 costs what page 1 costs, because the seek always descends once and reads forward the same distance.

The entity

@Entity('users')
export class User {
  @PrimaryGeneratedColumn('uuid')
  id: string;

  // @Column() alone does NOT make this auto-increment.
  // @Generated('increment') maps to IDENTITY on SQL Server.
  // SQL Server allows exactly one IDENTITY column per table — fine here,
  // since the PK is a UUID and doesn't use it.
  @Column({ type: 'int' })
  @Generated('increment')
  @Index('IX_users_seq', { unique: true })
  seq: number;

  @Column({ type: 'nvarchar', length: 255, nullable: true })
  push_token: string | null;

  // Legacy column: locale-formatted text, not a datetime.
  // Values look like '2025-10-30오후 5:28:28'.
  @Column({ type: 'nvarchar', length: 50, nullable: true })
  logindate: string | null;
}

The page fetcher

export interface CursorPage<T> {
  items: T[];
  nextCursor: number | null;
}

private async fetchPage(
  cursor: number | null,
  maxSeq: number,
  limit: number,
): Promise<CursorPage<User>> {
  const qb = this.users
    .createQueryBuilder('user')
    .select(['user.seq', 'user.push_token', 'user.logindate'])
    .where('user.seq <= :maxSeq', { maxSeq })   // snapshot boundary, explained below
    .orderBy('user.seq', 'ASC')
    .limit(limit + 1);                          // N+1 trick, explained below

  // `!== null`, not a truthy check. If seq 0 ever exists, `if (cursor)`
  // silently restarts the scan from the beginning.
  if (cursor !== null) {
    qb.andWhere('user.seq > :cursor', { cursor });
  }

  const rows = await qb.getMany();
  const hasMore = rows.length > limit;
  if (hasMore) rows.pop();

  return {
    items: rows,
    // Derived from the raw page, before any application-side filtering.
    // This one line is the subject of the next section.
    nextCursor: hasMore ? rows[rows.length - 1].seq : null,
  };
}

Two choices worth explaining.

limit() over take(). They're interchangeable here and stop being interchangeable the moment you add a join: take() wraps the query so the limit applies to entities, limit() applies it to raw rows and will truncate a joined entity halfway through. This query has no joins, so limit() is fine — but if you paste this into something with a leftJoinAndSelect, use take(). Check the emitted SQL for your driver and version rather than trusting either of us.

Fetching limit + 1. One extra row tells you whether a next page exists without a separate COUNT(*), which on a 940K-row table is not a query you want to run once per page. Pop the extra before returning.

The plan shape

You don't need my numbers for this part, just the operator names. Before, at a deep offset:

|--Top(OFFSET:(900000), ROWS:(1000))
     |--Clustered Index Scan(OBJECT:([users].[PK_users]), ORDERED FORWARD)

After:

|--Top(TOP EXPRESSION:((1001)))
     |--Index Seek(OBJECT:([users].[IX_users_seq]),
                   SEEK:([seq] > @lastSeq), ORDERED FORWARD)

Clustered Index Scan under a Top with an OFFSET expression is the thing you're trying to get rid of. Index Seek with a seek predicate on your cursor column is the thing you're trying to get. If your plan still says Scan after the refactor, your index doesn't match your ORDER BY, and nothing else in this post will help.

Then I broke it

Here's the part I actually want to write about.

The business rule was "users who last logged in between 10 and 30 days ago." The logindate column is nvarchar holding a mix of Korean locale strings like '2025-10-30오후 5:28:28' and ISO-ish timestamps. Parsing that in T-SQL looked painful, so I punted and filtered in memory after fetching:

let lastSeq = 0;

while (true) {
  let usersInPage = await qb
    .where('user.seq > :lastSeq', { lastSeq })
    .orderBy('user.seq', 'ASC')
    .take(10000)
    .getMany();

  if (usersInPage.length === 0) break;

  // typically drops ~80% of the page
  usersInPage = filterByLoginDate(usersInPage, { minDays: 10, maxDays: 30 });

  for (const user of usersInPage) {
    tokens.add(user.push_token);
  }

  if (usersInPage.length > 0) {
    lastSeq = usersInPage[usersInPage.length - 1].seq;
  }
}

Those last four lines contain two different bugs. They look like one bug. They aren't, and conflating them is what kept me stuck for an afternoon.

Bug 1: the cursor lags behind the scan

usersInPage gets reassigned to the filtered array, so the cursor comes from the last row that survived the filter rather than the last row the database actually returned.

page 1:  fetch seq 1 .. 10,000        (10,000 rows)
         filter → ~1,875 rows, last one around seq 2,000
         cursor = ~2,000

page 2:  fetch seq 2,001 .. 12,000    ← 2,001–10,000 already processed
         filter → ~1,875 rows, last one around seq 4,000
         cursor = ~4,000
...

The cursor never moves backward. It advances by roughly 2,000 per iteration instead of 10,000. So the loop does terminate — I called it an infinite loop at the time and that was wrong, and the distinction matters because it points at the wrong fix.

What it actually does is roughly 5–6× the database work, since it takes that many more pages to cross the table.

Here's the part I got wrong twice, so it's worth spelling out. This is what the log looked like:

[Job abc123] 1,875 records matched (Total: 1,068,158)
[Job abc123] 1,875 records matched (Total: 1,070,033)
[Job abc123] 1,875 records matched (Total: 1,071,908)
...
[Job abc123] 1,875 records matched (Total: 1,096,283)

My first instinct was that a per-page count pinned at exactly 1,875 had to mean the same query running over and over. It doesn't. If the cursor advances 2,000 while the window is 10,000, consecutive windows overlap by 80% — most of the rows in page N+1 were also in page N, so their match counts are nearly identical by construction. A near-constant per-page count is not evidence of a frozen loop. It's the signature of a cursor that's advancing too slowly.

The real tell was the cumulative total: the counter passed 1,096,283 while the job's actual output was 65,679 unique tokens. That's a factor of about 16, and working out what the 16 was made of took me longer than it should have, because it isn't one thing.

About 5–6× of it is the bug: with the windows overlapping, most matching rows get counted once per window they appear in. The remaining ~3× isn't a bug at all — the counter counts matched rows, and multiple rows can carry the same push token, so the Set collapses them. Multiply the two and you land on 16. I spent an afternoon treating a single ratio as a single phenomenon when it was two stacked on each other, which is also why my first estimate of how much extra work the job was doing came out about three times too high.

The Set kept the token list correct, so nobody got a duplicate push. This was a resource and observability bug, not a delivery bug, and it was the counter rather than any user-visible failure that made me look.

Bug 2: the loop that really does hang

if (usersInPage.length > 0) is a guard I added to avoid indexing into an empty array. It looks defensive. It's a landmine.

When a page filters down to zero rows, the cursor isn't updated at all. Not "advanced too little" — not advanced. The next iteration issues a byte-for-byte identical query, gets the same page back, filters it to zero again, and repeats forever.

I want to be precise about this one: it never fired on me. I found it by reading the guard while fixing bug 1, not by watching it happen. It requires one condition — a full page where every row fails the filter — and whether your data ever produces that page depends entirely on how seq and login dates are distributed in your table. A contiguous block of never-activated accounts or a legacy bulk import does it. In this job the filter drops about 80% of every page, so a run of five bad pages in a row was never far away.

The failure signature would be a cursor value that stops changing while fetch counts stay constant and match counts sit at zero, with no error and no crash — the job just stops making progress until someone notices the queue isn't draining.

That's what makes it worse than bug 1, which at least announces itself with an absurd counter. Which brings me to the one operational habit I'd take from this: log your cursor value, not just your counts. A frozen cursor is unambiguous. A count, as I demonstrated to myself twice, is not.

The fix

The cursor is a position in the database's scan order. It is not a fact about your filtered result set, and it has to be derived before any application logic touches the page.

This is the intermediate version — it still filters in memory, because at this point I was fixing the traversal and nothing else. The next section removes the filter entirely.

async collectTokens(job: Job): Promise<Set<string>> {
  const BATCH = 10_000;
  const tokens = new Set<string>();

  // Snapshot boundary — see below
  const row = await this.users
    .createQueryBuilder('u')
    .select('MAX(u.seq)', 'max')
    .getRawOne<{ max: number | null }>();

  const maxSeq = row?.max;
  if (maxSeq == null) return tokens;

  // BullMQ progress is `number | object`, so narrow before trusting it.
  const saved = job.progress as { cursor?: number | null } | number | undefined;
  let cursor: number | null =
    typeof saved === 'object' && saved !== null ? saved.cursor ?? null : null;

  let fetched = 0;

  while (true) {
    const page = await this.fetchPage(cursor, maxSeq, BATCH);
    if (page.items.length === 0) break;

    fetched += page.items.length;

    // Filtering happens on page.items. page.nextCursor was already fixed
    // inside fetchPage and nothing here can affect it.
    for (const user of this.filterByLoginDate(page.items, { minDays: 10, maxDays: 30 })) {
      if (user.push_token) tokens.add(user.push_token);
    }

    // Cheap invariant that catches both bugs above on the first bad iteration
    if (page.nextCursor !== null && cursor !== null && page.nextCursor <= cursor) {
      throw new Error(`Cursor did not advance: ${cursor} -> ${page.nextCursor}`);
    }

    cursor = page.nextCursor;
    await job.updateProgress({ cursor, fetched, matched: tokens.size });

    if (cursor === null) break;
    await delay(100); // pacing: this job shares an instance with live traffic
  }

  this.logger.log(`collected ${tokens.size} tokens from ${fetched} rows`);
  return tokens;
}

Healthy output:

[collect] cursor 10000  → 10,000 fetched, 1,875 matched
[collect] cursor 20000  → 10,000 fetched, 2,134 matched
[collect] cursor 30000  → 10,000 fetched, 1,956 matched
...
[collect] cursor 940231 →  6,234 fetched, 1,103 matched
[collect] pagination complete — 65,679 unique tokens

The cursor climbs monotonically to the snapshot boundary, and the final count matches what the equivalent single SQL query returns. That last check is the one that actually proves the loop is right — everything else just proves it didn't crash.

On the defensive check: my first attempt was a MAX_ITERATIONS cap. I'd now argue that's the wrong guard. It fires late, needs tuning per dataset, and tells you nothing about why. The monotonicity assertion fires on the first bad iteration and prints the two values involved. Assert the invariant, not the symptom.

Pushing the filter into SQL, properly

In-memory filtering was the root cause, so the real fix was getting rid of it. My first attempt:

AND DATEDIFF(DAY, TRY_CONVERT(date, LEFT(user.logindate, 10), 23), GETDATE())
    BETWEEN 10 AND 30

This works, and it's what I shipped first. It's also non-sargable: the column is wrapped in functions, so SQL Server can never use an index on logindate to satisfy it. It performs acceptably here only because the seq range predicate has already cut the candidate set to 10,000 rows before this expression is evaluated. That's a property of the access path, not of the predicate.

"Push it into SQL" is good advice that quietly assumes you're pushing something the optimizer can use. Two changes make that true.

First, materialize the parsed value:

-- style 23 (yyyy-mm-dd) makes the conversion deterministic,
-- which is what allows PERSISTED and an index on it.
-- TRY_CONVERT yields NULL for rows that don't parse, instead of failing the query.
ALTER TABLE dbo.users
  ADD last_login_at AS TRY_CONVERT(date, LEFT(logindate, 10), 23) PERSISTED;

CREATE NONCLUSTERED INDEX IX_users_last_login_at
  ON dbo.users (last_login_at)
  INCLUDE (seq, push_token);

Without an explicit style, string-to-date conversion is non-deterministic — it depends on session language settings — and SQL Server refuses to persist or index it. The error message doesn't make the reason obvious.

Adding a PERSISTED computed column to a large table is a size-of-data operation under a schema-modify lock, and there's no online path for it — ALTER TABLE ... ADD takes no ONLINE option, and ALTER COLUMN ... ADD PERSISTED is explicitly excluded from online ALTER COLUMN. So it's a maintenance window, or the long way round: a nullable regular column, a batched backfill, dual writes, and a cutover.

Second, compute the boundaries in the application and compare against the bare column:

const today = startOfDay(new Date());
const from = subDays(today, 30);
const to = subDays(today, 10);

qb.andWhere('user.last_login_at BETWEEN :from AND :to', { from, to });

Now the predicate is sargable, the index is usable, and the optimizer gets to choose between seeking on seq and seeking on last_login_at depending on selectivity. That last part is the real payoff: you've given it an option it didn't have.

One thing to check on the way out: the parameter type. last_login_at is date, and a driver that sends a JavaScript Date as datetime2 will make SQL Server convert the column rather than the parameter, because datetime2 has the higher precedence — which puts you right back where you started. Send 'yyyy-MM-dd' strings or pin the parameter type explicitly, and confirm it in the actual plan rather than assuming.

Making it safe to run in production

Pin a snapshot boundary. Keyset pagination is often described as immune to concurrent writes. Not quite. It's immune to shifting, because the cursor is anchored to a value rather than a position — an insert or delete below the cursor changes nothing. But an insert above the cursor is always in your path, so a long-running job keeps picking up users who registered after it started, and if registrations ever outpace your scan the job never ends. Read MAX(seq) once at the start and add seq <= @maxSeq.

Checkpoint and resume. This is the underrated advantage over offset pagination. The entire state of the scan is one integer, so a job that dies at 80% can resume at 80%. With offset pagination, mid-job resumption isn't just inconvenient, it's incorrect: the offsets no longer point where they did.

Don't reach for WITH (NOLOCK). The reflex when a scan is slow is to add a nolock hint and move on. Read-uncommitted against a table taking concurrent writes can return rows twice or miss them entirely during page splits — precisely the class of bug you switched to keyset pagination to eliminate. If blocking is the problem, look at READ_COMMITTED_SNAPSHOT instead.

Keep PII out of the working set. The original query selected cell_phone, because the legacy dedup key was a phone number. Once dedup moved to push tokens, that column had no business in the query, the logs, or the job payload. Select what you need, and mask what leaks into logs.

The await delay(100) between pages is deliberate pacing, not caution left over from debugging: this job shares an instance with live traffic, and at a 10,000-row batch it costs under 10 seconds across the whole run. On a dedicated replica, drop it.

Results

Metric	Offset	Keyset
Pages read, first batch (modelled)	~100	~55
Pages read, batch at 500K (modelled)	~50,100	~55
Pages read, batch at 900K (modelled)	~90,100	~55
Cost growth with depth	linear	flat
Access path	clustered index scan	covering index seek
Token collection, wall clock (measured)	~45 min	~2 min

The row I'd point at is the third one, and not because the ratio is large. The offset column has a slope and the keyset column doesn't. Everything else follows from that: the job stopped getting slower as the user table grew, which is the actual thing I wanted.

The duplicate-and-missing-notification complaints stopped too, which is the part I'd have led with if I'd understood the problem properly at the time.

When offset is still the right call

Keyset pagination isn't strictly better; it's better at one shape of problem. Use it for sequential full-table traversal: batch jobs, exports, infinite scroll, anything on a table taking concurrent writes, anything large enough that deep pages hurt.

Stick with offset when you need to jump to page 47 directly, when you need a total page count, when the dataset is small enough that none of this matters, or when you're sorting by a column that isn't unique and can't be made unique with a tiebreaker. Admin back-office screens are usually all four at once. I still use skip()/take() there and don't feel bad about it.

Takeaways

• OFFSET reads and discards; cost grows linearly with depth. WHERE key > @cursor seeks; cost is flat.
• Your cursor column must be unique, immutable, indexed, and match your ORDER BY exactly. A random UUID fails on monotonicity.
• The cursor is a database scan position. Derive it from the raw page, before filtering or mapping or anything else your code does to the rows.
• if (filtered.length > 0) { cursor = ... } is not a null guard. It's a loop that stops making progress the moment a page filters to empty.
• A near-constant per-page count means overlapping windows, not a frozen loop. Log the cursor value and you don't have to guess.
• Assert that the cursor advances. Three lines, catches the entire class on the first bad iteration.
• Pin MAX(seq) at job start so concurrent inserts can't extend the run indefinitely.
• Pushing a filter into SQL only helps if the predicate is sargable. A function wrapped around a column isn't. Part 2 covers the other half of this refactor: moving deduplication from phone numbers to push tokens, and why FCM's token lifecycle makes that harder than it sounds.