Skip to content
Source
Sign inSign up
TanStack/db

Paginated live query evaluates materialize includes for rows outside the page #2137

Send to my agent
ClosedJaime02(GitHub profile, opens in a new tab) opened this issue 1 comment
  • I've validated the bug against the latest version of DB packages

Describe the bug

A live query with orderBy().limit().offset() and a materialize() include in select returns only limit rows, but it evaluates the include for rows that never reach the result:

  1. Without .distinct(): the include runs for every row up to offset + limit, so the cost grows with the page number.
  2. With .distinct(): the index-backed lazy window is disabled, so the include runs for every row in the source collection, on every page, page 0 included.

Paginating in a subquery and selecting the include on the outer query returns the same rows at roughly the cost of the query without includes. The engine could presumably do the same: apply limit/offset (and distinct over the non-include columns) before evaluating includes.

This is different from #1634, which was closed after no includes-specific amplification was found. Here the amplification is that includes are evaluated for rows that are discarded by limit/offset.

Impact

In a real app (Electric collections, useLiveQuery, ~8k parent rows, six nested includes two levels deep, every join column indexed), each page change blocked the main thread:

nextnextlastfirst
flat query + .distinct()5472ms5292ms5452ms5471ms
flat query, no .distinct()335ms401ms5050ms487ms
subquery workaround310ms475ms479ms272ms

To Reproduce

Self-contained, local-only collections, all join columns indexed. bun install && bun bench.ts:

import {
  BasicIndex,
  createCollection,
  createLiveQueryCollection,
  eq,
  localOnlyCollectionOptions,
  materialize,
  type InitialQueryBuilder,
} from "@tanstack/db";

const PARENTS = 8_000;
const CHILDREN_PER_PARENT = 3;
const PAGE_SIZE = 10;
const PAGES = [0, 100, 400, 799];

const parents = createCollection(
  localOnlyCollectionOptions({
    id: "parents",
    getKey: (row: { id: number }) => row.id,
    initialData: Array.from({ length: PARENTS }, (_, i) => ({ id: i + 1 })),
    defaultIndexType: BasicIndex,
  }),
);
parents.createIndex((row) => row.id);

const children = createCollection(
  localOnlyCollectionOptions({
    id: "children",
    getKey: (row: { id: number; parentId: number }) => row.id,
    initialData: Array.from({ length: PARENTS * CHILDREN_PER_PARENT }, (_, i) => ({
      id: i + 1,
      parentId: 1 + Math.floor(i / CHILDREN_PER_PARENT),
    })),
    defaultIndexType: BasicIndex,
  }),
);
children.createIndex((row) => row.parentId);

const pageOfParents = (q: InitialQueryBuilder, page: number) =>
  q
    .from({ parent: parents })
    .orderBy(({ parent }) => parent.id, "desc")
    .limit(PAGE_SIZE)
    .offset(page * PAGE_SIZE);

const withChildren = (q: InitialQueryBuilder) => (refs: { parent: { id: number } }) => ({
  ...refs.parent,
  children: materialize(
    q.from({ child: children }).where(({ child }) => eq(child.parentId, refs.parent.id)),
  ),
});

const queries = {
  "no include": (q: InitialQueryBuilder, page: number) => pageOfParents(q, page),

  include: (q: InitialQueryBuilder, page: number) => pageOfParents(q, page).select(withChildren(q)),

  "include + distinct": (q: InitialQueryBuilder, page: number) =>
    pageOfParents(q, page).select(withChildren(q)).distinct(),

  workaround: (q: InitialQueryBuilder, page: number) =>
    q
      .from({ parent: pageOfParents(q, page) })
      .orderBy(({ parent }) => parent.id, "desc")
      .select(withChildren(q)),
};

async function median(query: (q: InitialQueryBuilder, page: number) => any, page: number) {
  const runs: Array<{ ms: number; ids: string }> = [];
  for (let i = 0; i < 3; i++) {
    const start = performance.now();
    const live = createLiveQueryCollection({ query: (q) => query(q, page), startSync: true });
    const rows = await live.toArrayWhenReady();
    runs.push({ ms: performance.now() - start, ids: rows.map((row: any) => row.id).join() });
    await live.cleanup();
  }
  return runs.sort((a, b) => a.ms - b.ms)[1];
}

const table: Record<string, Record<string, string>> = {};
for (const [name, query] of Object.entries(queries)) {
  table[name] = {};
  for (const page of PAGES) {
    const { ms, ids } = await median(query, page);
    const { ids: expected } = await median(queries["no include"], page);
    table[name][`page ${page}`] = `${Math.round(ms)}ms${ids === expected ? "" : " WRONG ROWS"}`;
  }
}

console.log(`${PARENTS} parents × ${CHILDREN_PER_PARENT} children, ${PAGE_SIZE} rows per page`);
console.table(table);

All four queries return the same 10 rows (checked in the script):

8000 parents × 3 children, 10 rows per page
┌────────────────────┬────────┬──────────┬──────────┬──────────┐
│                    │ page 0 │ page 100 │ page 400 │ page 799 │
├────────────────────┼────────┼──────────┼──────────┼──────────┤
│         no include │ 2ms    │ 12ms     │ 34ms     │ 42ms     │
│            include │ 6ms    │ 98ms     │ 317ms    │ 642ms    │
│ include + distinct │ 814ms  │ 936ms    │ 866ms    │ 800ms    │
│         workaround │ 4ms    │ 11ms     │ 40ms     │ 62ms     │
└────────────────────┴────────┴──────────┴──────────┴──────────┘

With one include the gap is ~10–20x. With the six nested includes from the app it becomes seconds per page change.

Expected behavior

include and include + distinct cost about the same as workaround on every page: includes are evaluated only for the rows inside the limit/offset window.

Versions

  • @tanstack/db 0.13.0, @tanstack/react-db 0.5.8
  • Bun 1.4.0, Windows 11 (the app numbers are from Chrome)
  1. 🎉 The PR fixing this issue (#2156) has been released!

    Thank you for reporting!

Sign in to join this conversation.