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

Offen
#2,442 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
4/5
Geschätzter Aufwand
1-2 Tage
Anfängerfreundlichkeit
22/100
Issue-Typ
Bug
Klarheit
Größtenteils klar
Aktivitätsstatus
Aktiv
Tech-Stack
react, typescript

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

  • 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).

Vorherrschende Sprache
TypeScript
Sterne
4k
Forks
286
Ø Merge
1 T. 1 Std.
Gemergte PRs (30 T.)
104

Entwicklungsumgebung

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus TanStack/db

Alle Issues in TanStack/db

Ähnliche Issues

Weitere Issues zu TypeScript

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.