Model

Incremental or full recompute

The factor c/c′ is the reciprocal of the merge penalty. The factor (1 − F/(S·c)) is a discount for the fixed cost. At small scale incremental is strictly worse.

S c = Δ S c^{'} + F ⟹ incremental wins when Δ < (1 - \frac{F}{S c}) \cdot \frac{c}{c ^{'}}

$S$: State size; the state size (rows)
$c$: Scan cost; the per-row cost on a sequential scan
$c^{'}$: Merge cost; the per-row cost of a random-access merge into existing state
$Δ$: Changed fraction; the changed fraction
$F$: Fixed overhead; offset tracking, state storage, metadata commits, capture infrastructure, people

Trade-off: Precompute vs. compute-on-read

How it behaves

One input on the horizontal axis, the others held fixed.

full rebuildincremental merge

Data table

Run time by changed fraction (500M rows, 2 µs scan, 40 µs merge, F = 0)
Changed fraction Δ	series	Run time
0.001	full rebuild	1,000 s
0.001	full rebuild	1,000 s
0.001	full rebuild	1,000 s
0.001	full rebuild	1,000 s
0.001	full rebuild	1,000 s
0.001	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.002	full rebuild	1,000 s
0.003	full rebuild	1,000 s
0.003	full rebuild	1,000 s
0.003	full rebuild	1,000 s
0.003	full rebuild	1,000 s
0.003	full rebuild	1,000 s
0.004	full rebuild	1,000 s
0.004	full rebuild	1,000 s
0.004	full rebuild	1,000 s
0.005	full rebuild	1,000 s
0.005	full rebuild	1,000 s
0.006	full rebuild	1,000 s
0.006	full rebuild	1,000 s
0.006	full rebuild	1,000 s
0.007	full rebuild	1,000 s
0.008	full rebuild	1,000 s
0.008	full rebuild	1,000 s
0.009	full rebuild	1,000 s
0.01	full rebuild	1,000 s
0.01	full rebuild	1,000 s
0.011	full rebuild	1,000 s
0.012	full rebuild	1,000 s
0.013	full rebuild	1,000 s
0.014	full rebuild	1,000 s
0.015	full rebuild	1,000 s
0.016	full rebuild	1,000 s
0.018	full rebuild	1,000 s
0.019	full rebuild	1,000 s
0.021	full rebuild	1,000 s
0.022	full rebuild	1,000 s
0.024	full rebuild	1,000 s
0.026	full rebuild	1,000 s
0.028	full rebuild	1,000 s
0.031	full rebuild	1,000 s
0.033	full rebuild	1,000 s
0.036	full rebuild	1,000 s
0.039	full rebuild	1,000 s
0.042	full rebuild	1,000 s
0.045	full rebuild	1,000 s
0.049	full rebuild	1,000 s
0.053	full rebuild	1,000 s
0.057	full rebuild	1,000 s
0.061	full rebuild	1,000 s
0.066	full rebuild	1,000 s
0.072	full rebuild	1,000 s
0.078	full rebuild	1,000 s
0.084	full rebuild	1,000 s
0.091	full rebuild	1,000 s
0.098	full rebuild	1,000 s
0.106	full rebuild	1,000 s
0.114	full rebuild	1,000 s
0.124	full rebuild	1,000 s
0.133	full rebuild	1,000 s
0.144	full rebuild	1,000 s
0.156	full rebuild	1,000 s
0.169	full rebuild	1,000 s
0.182	full rebuild	1,000 s
0.197	full rebuild	1,000 s
0.213	full rebuild	1,000 s
0.23	full rebuild	1,000 s
0.249	full rebuild	1,000 s
0.269	full rebuild	1,000 s
0.29	full rebuild	1,000 s
0.314	full rebuild	1,000 s
0.339	full rebuild	1,000 s
0.366	full rebuild	1,000 s
0.396	full rebuild	1,000 s
0.428	full rebuild	1,000 s
0.463	full rebuild	1,000 s
0.5	full rebuild	1,000 s
0.001	incremental merge	20 s
0.001	incremental merge	21.6 s
0.001	incremental merge	23.4 s
0.001	incremental merge	25.2 s
0.001	incremental merge	27.3 s
0.001	incremental merge	29.5 s
0.002	incremental merge	31.9 s
0.002	incremental merge	34.5 s
0.002	incremental merge	37.2 s
0.002	incremental merge	40.2 s
0.002	incremental merge	43.5 s
0.002	incremental merge	47 s
0.003	incremental merge	50.8 s
0.003	incremental merge	54.9 s
0.003	incremental merge	59.3 s
0.003	incremental merge	64.1 s
0.003	incremental merge	69.3 s
0.004	incremental merge	74.9 s
0.004	incremental merge	81 s
0.004	incremental merge	87.5 s
0.005	incremental merge	94.6 s
0.005	incremental merge	102 s
0.006	incremental merge	110 s
0.006	incremental merge	119 s
0.006	incremental merge	129 s
0.007	incremental merge	139 s
0.008	incremental merge	151 s
0.008	incremental merge	163 s
0.009	incremental merge	176 s
0.01	incremental merge	190 s
0.01	incremental merge	206 s
0.011	incremental merge	222 s
0.012	incremental merge	240 s
0.013	incremental merge	260 s
0.014	incremental merge	281 s
0.015	incremental merge	303 s
0.016	incremental merge	328 s
0.018	incremental merge	354 s
0.019	incremental merge	383 s
0.021	incremental merge	414 s
0.022	incremental merge	447 s
0.024	incremental merge	483 s
0.026	incremental merge	522 s
0.028	incremental merge	565 s
0.031	incremental merge	610 s
0.033	incremental merge	659 s
0.036	incremental merge	713 s
0.039	incremental merge	770 s
0.042	incremental merge	833 s
0.045	incremental merge	900 s
0.049	incremental merge	972 s
0.053	incremental merge	1,050 s
0.057	incremental merge	1,140 s
0.061	incremental merge	1,230 s
0.066	incremental merge	1,330 s
0.072	incremental merge	1,430 s
0.078	incremental merge	1,550 s
0.084	incremental merge	1,680 s
0.091	incremental merge	1,810 s
0.098	incremental merge	1,960 s
0.106	incremental merge	2,110 s
0.114	incremental merge	2,290 s
0.124	incremental merge	2,470 s
0.133	incremental merge	2,670 s
0.144	incremental merge	2,890 s
0.156	incremental merge	3,120 s
0.169	incremental merge	3,370 s
0.182	incremental merge	3,640 s
0.197	incremental merge	3,940 s
0.213	incremental merge	4,250 s
0.23	incremental merge	4,600 s
0.249	incremental merge	4,970 s
0.269	incremental merge	5,370 s
0.29	incremental merge	5,810 s
0.314	incremental merge	6,270 s
0.339	incremental merge	6,780 s
0.366	incremental merge	7,330 s
0.396	incremental merge	7,920 s
0.428	incremental merge	8,560 s
0.463	incremental merge	9,250 s
0.5	incremental merge	10,000 s

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Change Data Capture & Incremental Processing
What does it cost to know what changed, and is that cheaper than not needing to know?
$Δ < (1 - F / (S \cdot c)) \cdot (c / c^{'})$
Read it in place →