Lazy-join demand tap hands setDemand the full key set on every emission, O(keys) per update

未關閉
#2,405 0 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視

維護者通常 1 天內回覆

還沒有人認領這個 Issue。

評估

難度
4/5
預估耗時
3-5 天
新手友好度
54/100
Issue 類型
缺陷
描述清晰度
描述清楚
活躍度
活躍
技術堆疊
typescript

研究方向

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.

由索引模型根據 Issue 內容生成。

描述

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:

  1. The tap tracks, per key the batch touched, whether it was demanded before the batch, and rebuilds its key Set only when some touched key's demand differs afterwards. Otherwise it passes the same Set object as last time. A batch that retracts and re-inserts a key leaves demand as it was.
  2. setDemand remembers the Set it was last handed and returns changed: false when 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 different Set with 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.

主要語言
TypeScript
星號
4k
分支
286
平均合併
1 天 8 小時
30 天內合併 PR
105

環境準備

從這裡開始

  1. 先讀完整個 Issue,再讀專案的貢獻指南。
  2. 在 Issue 下留言說明你要接手 —— 這能避免兩個人做同樣的事。
  3. Fork 儲存庫,在一個分支上完成修改。
  4. 送出 Pull Request,並在描述裡引用這個 Issue 編號。

TanStack/db 的其他 Issue

查看 TanStack/db 的全部 Issue

相似的 Issue

更多 TypeScript Issue

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。