Lazy join demand reads rows its subscription already sent, then discards all of them

Aperta
#2,442 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
1-2 giorni
Idoneità per principianti
22/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
react, typescript

Direzione di ricerca

Start in packages/db/src/collection/subscription.ts at requestSnapshot (around line 1335), where currentStateAsChanges is read and the sentKeys filter drops rows. The repro script in the issue (packages/db/repro.ts) shows the wasted reads: live.size should stay 1000 while the read count falls. Done means the repro reads 0 rows and the subscription, join and subset test suites still pass, with the sentKeys subset question answered.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

  • I've validated the bug against the latest version of DB packages (main at 21c52a07e, @tanstack/db 1.0.0-rc.1.5)

This is a performance issue, not a correctness bug: the rows a live query publishes are correct.

Describe the bug

When a lazy join's lazy source has already sent its rows to its subscription before the demand that selects them is set, the demand still reads those rows from the source and then discards every one of them as already sent.

It can happen when several Collections change before their live queries run. I have reproduced it with an optimistic transaction that writes several Collections (the repro below), which already runs the live query once at the end of the transaction, and with the sync transactions of several Collections committed inside one withPublicationContext call (#2440).

The path, on main:

  1. The join's demand changes, and SubsetDemandController.setDemand (query/live/subset-demand-controller.ts:68) starts a segment, which calls subscription.requestSnapshot (:330).
  2. CollectionSubscription.requestSnapshot (collection/subscription.ts:1335) reads the matching rows from the Collection (currentStateAsChanges, :1418 to :1432).
  3. The filter at :1446 drops every row whose key is in sentKeys. Here that is all of them: the rows' change events already reached the subscription and added their keys to sentKeys.

To Reproduce

Save this as packages/db/repro.ts and run pnpm exec tsx repro.ts in packages/db:

import {
  BTreeIndex,
  createCollection,
  createLiveQueryCollection,
  createTransaction,
  eq,
} from './src/index.js'

type Row = { id: number; fk0?: number; fk1?: number; fk2?: number }

const sources = [`fact`, `d0`, `d1`, `d2`].map((name) =>
  createCollection<Row, number>({
    id: name,
    getKey: (row) => row.id,
    autoIndex: `eager`,
    defaultIndexType: BTreeIndex,
    startSync: true,
    sync: { sync: ({ markReady }) => markReady() },
  }),
)
const [fact, d0, d1, d2] = sources as [any, any, any, any]

// Count the rows that reads of the source Collections return
let rowsRead = 0
for (const source of sources as Array<any>) {
  const read = source.currentStateAsChanges.bind(source)
  source.currentStateAsChanges = (options: unknown) => {
    const rows = read(options)
    rowsRead += rows?.length ?? 0
    return rows
  }
}

const live = createLiveQueryCollection({
  startSync: true,
  query: (q) =>
    q
      .from({ fact })
      .join({ d0 }, ({ fact, d0 }) => eq(fact.fk0, d0.id), `inner`)
      .join({ d1 }, ({ fact, d1 }) => eq(fact.fk1, d1.id), `inner`)
      .join({ d2 }, ({ fact, d2 }) => eq(fact.fk2, d2.id), `inner`)
      .select(({ fact }) => ({ id: fact.id })),
})
await live.preload()
rowsRead = 0

const transaction = createTransaction({ mutationFn: async () => {}, autoCommit: false })
transaction.mutate(() => {
  for (const dimension of [d0, d1, d2])
    for (let id = 0; id < 100; id++) dimension.insert({ id })
  for (let id = 0; id < 1000; id++)
    fact.insert({ id, fk0: id % 100, fk1: id % 100, fk2: id % 100 })
})
console.log(`live query rows: ${live.size}, source rows read: ${rowsRead}`)
transaction.rollback()

It prints live query rows: 1000, source rows read: 3000. With inner joins the compiler made fact the lazy side, as all the Collections were empty at compile time (getActiveAndLazySources, query/compiler/joins.ts:758), and each of the three joins reads its 1,000 rows once. With left joins (drop the `inner` arguments) each dimension is the lazy side and the reads return 300 rows. Every row read is discarded.

Expected behavior

A demand whose rows the subscription has already sent selects no rows, so it should not have to read them.

Measured cost

With the benchmark in #2440 (scripts/bench/multi-collection-sync.ts, production bundle, 10,000 fact rows joined to 1, 3 or 7 dimensions of 1,000 rows), these reads are most of why committing inside one withPublicationContext call is slower than committing one at a time with inner joins when the fact Collection commits last: 0.84× to 1.03× as fast across 12 measurements. Committed one at a time, the demand is set while the fact Collection is still empty, so its reads return nothing.

What I tried

Skipping the read when every current row of the Collection is in sentKeys, and no truncate replay or stale publication is open:

private hasSentEveryCurrentRow(): boolean {
  if (this.isBufferingForTruncate || this.stalePublishedRows.size > 0)
    return false
  if (this.sentKeys.size !== this.collection.size) return false
  for (const key of this.sentKeys)
    if (!this.collection.has(key)) return false
  return true
}

requestSnapshot then uses an empty snapshot instead of calling currentStateAsChanges, after it has started the subset demand. The repro then reads 0 rows. In the benchmark above, the inner-join, fact-last case went from 0.84–1.03× to 0.82–1.08× (mean 0.97×), and the full @tanstack/db suite showed no new failures.

I have not opened a PR for it, because:

  • Removing its first guard, or its loop over sentKeys, makes no test in the subscription, truncate, join, subset and replay suites fail that does not also fail without either change (load-subset-replay-refinement-oracle.test.ts fails intermittently on my Windows machine, with or without the check). Removing the whole check, so that the read is always skipped, fails 494 of their tests. So nothing shows whether the guard or the loop is needed, and I could not tell whether sentKeys is always a subset of the current keys.
  • The loop is O(sent keys). From reading the code, once every row is sent, each later demand change, such as one new dimension row on a large fact Collection, would walk every sent key where it now does one index lookup. I have not measured this.

Is skipping this read the right place for a fix, or would you rather avoid the demand reaching requestSnapshot for keys whose rows were already sent? If sentKeys is guaranteed to be a subset of the current keys, the check could be O(1).

Lingua principale
TypeScript
Stelle
4k
Fork
286
Merge medio
1g 1h
PR unite (30g)
104

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di TanStack/db

Tutte le issue di TanStack/db

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.