Joining prepared row fragments: unfinished work adds

4 October 2026. Scope assessment of the incremental shared-table construction.

The readiness construction leaves a compiled row prefix and at most two raw bands. Its immediate composition question has a simple positive answer: two independently prepared row fragments can be joined in constant local work, preserving both operands and the established query bound. Repeating that operation can accumulate unfinished work. These statements are accounting consequences, not a new lower-bound theorem or an optimality result.

Exact operation

Fix public width n and common k with k^2 2^(k2+2k)<=n. Prepare each nonempty fragment A_i of r_i complete rows and n columns independently by the previous loader, stopping at a whole-row snapshot. Each fragment pays for its own unary headers, universal tree and all temporary history. Trees in different preparations need not share any input-dependent node. A leaf retains its own snapshot and table references.

A valid Join(L,R) means vertical row concatenation, preserving left-to-right order. Widths and parameters agree, and the resulting row count is at most n; these are interface promises, not assertions that a constant-time operation validates arbitrary dimensions. Join allocates one immutable binary node pointing to its operands. It has a finite tag, bounded local access and constant allocation. Both operands remain usable.

In constraint terms this joins y_L=A_L x and y_R=A_R x, sharing x and keeping their output variables disjoint. It does not implement arbitrary conjunction with overlapping outputs or matrix multiplication. The final query is u^T A v, where u has one coordinate per concatenated row and v has n coordinates. Query preparation is independent and costs O(R+n) for total row count R.

Consider a queried root with f nonempty leaf occurrences in its unfolded join tree. Write $$R=\sum_{i=1}^f r_i\le n,\qquad 0\le\rho_i\le\min(r_i,2k),$$ where rho_i is the number of rows still raw at leaf i. If a physical leaf is reused, its occurrences count separately because concatenation repeats its rows.

Query accounting

An explicit immutable depth-first stack visits leaves from left to right. Every binary node is entered and left a bounded number of times. A binary tree with f nonempty leaves has f-1 internal occurrences, even if its depth is large. Thus traversal takes O(f) work and at most O(f) new records. The controller does not use an uncharged recursive stack or pointer identity.

Keep the current u cursor across leaf visits and retain the original v root. At a leaf, restore its compiled-band order by charged list reversal and apply the earlier block traversal. Its compiled rows contribute O(r_i n/k) work. The raw rows are restored to chronological order and scanned against the next u coordinates and the retained v list, costing O(n rho_i). Whole-row endpoints ensure that the next leaf starts at the correct u coordinate; no numerical row-offset calculation or scan from the beginning of u is needed. Query lists and public rulers are prepared once. There is no full query-header rescan per leaf; repeated k-ruler traversals inside block queries are included in the compiled-row cost.

The XOR accumulator therefore equals the contribution of all visited rows. At completion it is u^T A v, with all operands intact. Including query loading, traversal, normalization, raw work and output gives $$T_Q,H_Q=O\!\left(\frac{Rn}{k}+n\sum_i\rho_i+n+f\right). \tag{1}$$ H_Q counts all query allocations. The raw contribution $$D=n\sum_i\rho_i$$ is an additive obligation carried by the joined handle. Constant-time Join postpones that obligation; it does not cancel it.

For a fixed number of fragments and R=n, (1) is O(n^2/k+nk+n), the earlier bound. Thus two-fragment joining preserves the O(n^2/sqrt(log n)) specialization. More generally, sum_i rho_i=O(n/k) suffices for O(n^2/k) total query time. A convenient stronger condition is f=O(n/k^2).

This is not uniform closure under arbitrary fragmentation. With n separately prepared singleton rows, no leaf has a successor band to complete its pending work. All rows are raw. The stated scan evaluator takes Theta(n^2) steps, for example when every u coordinate is one. Rebalancing the join tree changes stack depth but does not change D. This is a limitation of this evaluator and invariant, not a proof that another representation or query algorithm cannot do better.

Storage, history and model scope

Each distinct preparation costs O(n+r_i n) primitives and historical records. For one expression of nonempty fragments, f<=R, so even charging repeated leaves again gives O(Rn) preparation. No common size-dependent table is supplied for free. Building that expression needs f-1 joins.

Across an arbitrary persistent operation history, however, the correct count is $$H=O\!\left(\sum_{\text{distinct preparations}}(n+r_i n) +J+\sum_{\text{executed queries}}T_Q\right), \tag{2}$$ where J includes every actual join, even if its result is no longer current. A final root’s size does not bound all prior allocation. Explicit pointer encodings carry an additional logarithmic factor in the total heap size.

For R=n the combined boundary width is b=2n, coefficient input including independently paid headers is Theta(n^2), and the established named CNF encoding has size Theta(n^2 log n). For general R<=n, the boundary has n+R variables and coefficient input is Theta(nR), since f<=R. These are representation-specific upper bounds, outside the earlier n^2+n linear-bit storage budget. No unrestricted SAT conclusion follows.

The existing local compiler applies to the bounded Join operation and a client that charges every query step. It does not turn the growing query cost into constant-time observation or a strict real-time raw-input recognizer. Any scaffold-to-PEG recognition consequence still has one reversal. The finite-quotient characterization of constant Apply plus constant Query is not being extended here.

What this settles

The two-fragment row-join checkpoint is closed positively. The useful distinction is between cheap persistent composition and a uniform bound on the unfinished work carried by arbitrarily many compositions. The latter does not follow from the former.

This note is a written, independently reviewed accounting argument using the prior construction. It imports no additional mathematical theorem, makes no novelty claim, and has not been formally verified. No new finite experiment is needed for the tree traversal and additive estimates. It does not justify automatically pursuing a tighter exponent or another general lower bound. A stronger composition target would need a specified operation interface and a representation invariant with broader explanatory value.