Background
MaintainedPopulationStrategy (added in PR #404) lets a single synopsis/summary serve multiple queries by materializing one intermediate result and deriving the others from it. Examples:
topk(5, x) and topk(10, x) are computed as a single topk(10, x), with the top-5 derived from the top-10.
quantile(0.5, a) and quantile(0.9, a) are computed from the same KLL summary.
quantile(0.5, a) and quantile(0.9, b) are not shared, because the underlying data differs.
Problem
On closer inspection this strategy looks like a special case of Common Subexpression Elimination (CSE) applied after the sketch strategy has rewritten queries into synopsis pipelines, rather than a genuinely distinct strategy:
# Quantiles
Original: data -> calc p50 ; data -> calc p90
After sketch strategy: data -> KLL -> get p50 ; data -> KLL -> get p90
After sketch + CSE: data -> KLL -> {get p50, get p90}
For quantiles this is plain CSE — the KLL node is literally identical, so both queries collapse onto it.
# TopK
Original: data -> calc top10 ; data -> calc top5
After sketch strategy: data -> CMS(k=10) -> get top10 ; data -> CMS(k=5) -> get top5
After sketch + "updated CSE": data -> CMS(k=10) -> {get top10, get top5}
For topk the nodes are not identical (k=5 vs k=10), so plain CSE won't merge them. It needs a rule that knows CMS(k=5) can be satisfied by CMS(k=10).
Also worth noting: MaintainedPopulation is acknowledged (by its author) to be a poor name.
Proposal
Remove MaintainedPopulationStrategy and express its behavior through finer-grained CSE variants. A rough split (names are not settled):
Syntactic CSE — find and eliminate nodes that are literally identical (e.g. the KLL quantile case above).
Semantic / sketch-based / synopsis-based CSE — merge nodes that are not identical but where one can serve the other (e.g. CMS(k=5) satisfied by CMS(k=10)).
The key claim: the sharing/merging decision should be made at the CSE (rewrite) stage where the sharing opportunity is structural, not deferred to the cost model.
Open questions
Correct set and naming of the CSE variants.
Optimization-strategy dependencies in ASAPPlanner (e.g. sketch strategy must run before CSE for these rewrites to be visible) need to be studied and made explicit.
Background
MaintainedPopulationStrategy (added in PR #404) lets a single synopsis/summary serve multiple queries by materializing one intermediate result and deriving the others from it. Examples:
topk(5, x) and topk(10, x) are computed as a single topk(10, x), with the top-5 derived from the top-10.
quantile(0.5, a) and quantile(0.9, a) are computed from the same KLL summary.
quantile(0.5, a) and quantile(0.9, b) are not shared, because the underlying data differs.
Problem
On closer inspection this strategy looks like a special case of Common Subexpression Elimination (CSE) applied after the sketch strategy has rewritten queries into synopsis pipelines, rather than a genuinely distinct strategy:
For quantiles this is plain CSE — the KLL node is literally identical, so both queries collapse onto it.
For topk the nodes are not identical (k=5 vs k=10), so plain CSE won't merge them. It needs a rule that knows CMS(k=5) can be satisfied by CMS(k=10).
Also worth noting: MaintainedPopulation is acknowledged (by its author) to be a poor name.
Proposal
Remove MaintainedPopulationStrategy and express its behavior through finer-grained CSE variants. A rough split (names are not settled):
Syntactic CSE — find and eliminate nodes that are literally identical (e.g. the KLL quantile case above).
Semantic / sketch-based / synopsis-based CSE — merge nodes that are not identical but where one can serve the other (e.g. CMS(k=5) satisfied by CMS(k=10)).
The key claim: the sharing/merging decision should be made at the CSE (rewrite) stage where the sharing opportunity is structural, not deferred to the cost model.
Open questions
Correct set and naming of the CSE variants.
Optimization-strategy dependencies in ASAPPlanner (e.g. sketch strategy must run before CSE for these rewrites to be visible) need to be studied and made explicit.