Lazy-join demand tap hands setDemand the full key set on every emission, O(keys) per update
Los mantenedores suelen responder en 1 día
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 4/5
- Tiempo estimado
- 3-5 días
- Aptitud para principiantes
- 54/100
- Tipo de issue
- Error
- Claridad
- Bien especificado
- Estado de actividad
- Activo
- Stack tecnológico
- typescript
- Área
- backend, performance
Línea de trabajo
Start with activePipelineWithLoading in packages/db/src/query/compiler/joins.ts and SubsetDemandController.setDemand in packages/db/src/query/live/subset-demand-controller.ts. Trace how demand weights and failed segments are handled, then run the provided production-mode repro to compare leftJoin and fullJoin costs before and after the change. Done means unchanged demand avoids rebuilding and serializing the full key set while failed loads still retry and the reported update cost approaches the fullJoin reference.
Escrito por el modelo de indexación a partir del texto del issue.
Descripción
What happens
A leftJoin (or any join with a lazy side) compiles a tap on the active side that tracks the demanded join keys and calls setDemand with the whole set after every batch (packages/db/src/query/compiler/joins.ts, activePipelineWithLoading). SubsetDemandController.setDemand then canonicalizes every key (canonicalizeKeys → serializeEquality per key) and compares the set with the previous one before concluding nothing changed. A single-row update of the driving side retracts and re-inserts one key, so the set is the same, but the whole set is rebuilt, serialized and compared again. The cost of one update grows with the number of rows the join has seen, and a long-lived join over a large collection pays it on every change.
CPU per single-row update of the driving side (process.cpuUsage, 1,000 updates after warm-up, NODE_ENV=production, 1.0.0-rc.1.4, Node 26). fullJoin has no lazy side and is the reference for "the join without the tap":
| Rows | leftJoin |
fullJoin |
|---|---|---|
| 1,000 | 137 µs | 87 µs |
| 10,000 | 793 µs | 88 µs |
A fullJoin costs the same at both sizes; the leftJoin costs 9× more at 10,000 rows than at 1,000. In our app a chain of three left joins over about 2,000 rows pays it on every single-row update: 0.8 ms of a 5.7 ms update in a CPU profile.
Repro
// NODE_ENV=production node repro-join.mjs left|full [rows]
// CPU per single-row update on the driving side of one join; the joined side is a lazy source
// under leftJoin and not under fullJoin.
import { createCollection, createLiveQueryCollection, eq, localOnlyCollectionOptions } from '@tanstack/db'
const [variant = 'left', rowCount = '10000'] = process.argv.slice(2)
const N = Number(rowCount)
const table = (id, rows) =>
createCollection(localOnlyCollectionOptions({ id, getKey: (r) => r.id, initialData: rows }))
const orders = table('orders', Array.from({ length: N }, (_, i) => ({ id: i, customerId: i % (N / 2), rev: 0 })))
const customers = table('customers', Array.from({ length: N / 2 }, (_, i) => ({ id: i, name: `c${i}` })))
const view = createLiveQueryCollection({
query: (q) => {
const from = q.from({ o: orders })
const on = ({ o, c }) => eq(o.customerId, c.id)
return (variant === 'left' ? from.leftJoin({ c: customers }, on) : from.fullJoin({ c: customers }, on))
.select(({ o, c }) => ({ id: o.id, rev: o.rev, name: c.name }))
},
getKey: (r) => r.id,
})
await view.preload()
let seen = 0
view.subscribeChanges(() => { seen = view.size })
const flush = () => new Promise((r) => setImmediate(r))
for (let k = 0; k < 200; k++) { orders.update((k * 37) % N, (d) => { d.rev += 1 }); await flush() }
const iterations = 1000
const cpu0 = process.cpuUsage()
for (let k = 0; k < iterations; k++) {
orders.update((k * 37) % N, (d) => { d.rev += 1 })
await flush()
await flush()
}
const cpu = process.cpuUsage(cpu0)
console.log(JSON.stringify({ variant, rows: N, seen, cpuUsPerUpdate: Math.round((cpu.user + cpu.system) / iterations) }))
Proposal
Two small changes that keep every decision in the controller:
- The tap tracks, per key the batch touched, whether it was demanded before the batch, and rebuilds its key
Setonly when some touched key's demand differs afterwards. Otherwise it passes the sameSetobject as last time. A batch that retracts and re-inserts a key leaves demand as it was. setDemandremembers theSetit was last handed and returnschanged: falsewhen it receives that same object again, before canonicalizing, unless a failed segment still holds the plan's demand. That keeps the retry a failed load gets on the next emission today, and the equal-set path for a differentSetwith the same keys.
No change in what is requested, replaced or released: setDemand runs its existing logic exactly when the demanded set may differ or a load failed.
--- a/packages/db/src/query/compiler/joins.ts
+++ b/packages/db/src/query/compiler/joins.ts
@@ -401,6 +401,9 @@
string,
{ key: unknown; weight: number }
>()
+ // The demanded keys, rebuilt only when demand changed; the controller
+ // recognizes the same Set as unchanged demand.
+ let demandKeys: Set<unknown> | undefined
const activePipeline =
activeSource === `main` ? mainPipeline : joinedPipeline
@@ -418,12 +421,18 @@
[key: string, value: JoinInputValue]
> = activePipeline.pipe(
tap((data) => {
+ // Demand before the batch, per touched key: a batch that retracts
+ // and re-inserts a key leaves demand as it was.
+ const touched = new Map<string, boolean>()
for (const [
[joinKey, [, , joinValue]],
weight,
] of data.getInner()) {
if (joinValue == null) continue
const previous = demandWeights.get(joinKey)
+ if (!touched.has(joinKey)) {
+ touched.set(joinKey, (previous?.weight ?? 0) > 0)
+ }
const nextWeight = (previous?.weight ?? 0) + weight
if (nextWeight === 0) {
demandWeights.delete(joinKey)
@@ -435,14 +444,26 @@
}
}
- const keys = new Set(
- [...demandWeights.values()]
- .filter(({ weight }) => weight > 0)
- .map(({ key }) => key),
- )
+ let demandChanged = false
+ for (const [joinKey, wasDemanded] of touched) {
+ if (wasDemanded !== (demandWeights.get(joinKey)?.weight ?? 0) > 0) {
+ demandChanged = true
+ break
+ }
+ }
+ if (demandChanged || demandKeys === undefined) {
+ demandKeys = new Set(
+ [...demandWeights.values()]
+ .filter(({ weight }) => weight > 0)
+ .map(({ key }) => key),
+ )
+ }
for (let index = 0; index < lazyTargets.length; index++) {
const target = lazyTargets[index]!
- callbacks[target.sourceId]?.setDemand?.(demandPlans[index]!, keys)
+ callbacks[target.sourceId]?.setDemand?.(
+ demandPlans[index]!,
+ demandKeys,
+ )
}
}),
)
--- a/packages/db/src/query/live/subset-demand-controller.ts
+++ b/packages/db/src/query/live/subset-demand-controller.ts
@@ -23,6 +23,9 @@
type DemandState = {
keys: Map<string, unknown>
segments: Array<DemandSegment>
+ // The Set the last call passed: a caller passes it again while its demand
+ // is unchanged.
+ rawKeys: Set<unknown>
}
export type DemandUpdate = {
@@ -70,8 +73,17 @@
plan: LazyDemandPlan,
keys: Set<unknown>,
): DemandUpdate {
+ const previous = this.states.get(plan.id)
+ // The same Set as last time is unchanged demand, so there is nothing to
+ // canonicalize, unless a failed load holds the plan's demand.
+ if (
+ previous &&
+ previous.rawKeys === keys &&
+ !previous.segments.some((segment) => segment.state === `failed`)
+ ) {
+ return { changed: false, empty: keys.size === 0, ready: true }
+ }
const nextKeys = canonicalizeKeys(keys, this.valueIdentity)
- const previous = this.states.get(plan.id)
const hasFailedCoverage = previous?.segments.some(
(segment) =>
segment.state === `failed` && intersects(segment.keys, nextKeys),
@@ -81,6 +93,7 @@
equalKeySets(previous.keys, nextKeys) &&
!hasFailedCoverage
) {
+ previous.rawKeys = keys
return { changed: false, empty: nextKeys.size === 0, ready: true }
}
@@ -99,7 +112,7 @@
segment.state === `failed` &&
equalKeySets(segment.keys, nextKeys),
)
- const state: DemandState = { keys: nextKeys, segments }
+ const state: DemandState = { keys: nextKeys, segments, rawKeys: keys }
this.states.set(plan.id, state)
// A key the plan no longer needs shows no request error.
for (const key of previous?.keys.keys() ?? [])
Against main (858c8f0b); both files are unchanged since 1.0.0-rc.1.4. With it, the repro's leftJoin costs what the fullJoin does:
| Rows | leftJoin today |
leftJoin with this change |
fullJoin |
|---|---|---|---|
| 1,000 | 137 µs | 99 µs | 87 µs |
| 10,000 | 793 µs | 88 µs | 88 µs |
Happy to send this as a PR.
- Lenguaje dominante
- TypeScript
- Estrellas
- 4k
- Forks
- 286
- Merge medio
- 1 d 8 h
- PR fusionados (30 d)
- 105
Preparar el entorno
- Sin Dockerfile ni archivo de Docker Compose
- Tiene una plantilla de pull request
- Leer la guía de contribución
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de TanStack/db
-
extractSimpleComparisons returns value: null when the right side of a comparison isn't a literalAbierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 82/100
Los mantenedores suelen responder en 1 día
-
`avg`, `min`, `max` and `sum` treat `null` values as `0`Posiblemente ocupada @oyobbeb la tomó hace 11 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 76/100
Los mantenedores suelen responder en 1 día
-
`Collection.currentStateAsChanges` JSDoc examples don’t match `CurrentStateAsChangesOptions`Posiblemente ocupada Un pull request vinculado a esta issue está abierto o ya se fusionó. Abierto
Dificultad 1/5 1-3 horas Aptitud para principiantes 88/100
Los mantenedores suelen responder en 1 día
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
Los mantenedores suelen responder en 1 día
-
Two @tanstack/db tests time out under CPU load because a cold module import counts against the 5 s default timeoutPosiblemente ocupada @jp-knj la tomó hace 23 días. Abierto
Dificultad 2/5 1-3 horas Aptitud para principiantes 82/100
Los mantenedores suelen responder en 1 día
Todos los issues de TanStack/db
Issues similares
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
fb55/htmlparser2#2579 ·
Los mantenedores suelen responder en 1 día
-
bug good first issue needs-review
Dificultad 1/5 1-3 horas Aptitud para principiantes 83/100
Los mantenedores suelen responder en 1 día
-
Add Module DB RulesAbiertodocumentation public
Dificultad 1/5 1-3 horas Aptitud para principiantes 68/100
midnightntwrk/umbradb#65 ·
Los mantenedores suelen responder en 2 días
-
area/channels kind/bug priority/medium
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
nanocoai/nanoclaw#4501 · 1 comentario ·
Los mantenedores suelen responder en 1 día
-
Docker images: plain X.Y.Z tag (e.g. 7.2.3) is never updated after the initial release buildAbiertoneeds verification
Dificultad 2/5 1-3 horas Aptitud para principiantes 74/100
Los mantenedores suelen responder en 13 días