One shared-producer rule: cover every reader's need, derive each reader (top-k, summary size, panes, ranks, …) #954

Problem, by example

Several Pass 2 rules do the same thing. Readers need one computation at different values of something, so one producer is built that covers every reader's need, and each reader derives its own result from it. Each rule implements this separately. The descriptions below come from reading the code on main, not from a planner run.

Example 1: exact top-k reuse (memo/rules/topk.rs, topk_reuse_candidates in asap_aware_cse.rs)

topk(3, sum_over_time(m[2m]))     # needs k = 3
topk(10, sum_over_time(m[2m]))    # needs k = 10

One producer, Limit(10) over Sort of the exact input, is added through append_producer (CandidateOrigin::TopKReuse). Each reader derives Limit(k) ▸ Project from it.

Example 2: summary capability (summary_capability_pass2_candidates in asap_aware_cse.rs; in the memo, memo/rules/state_configurations.rs with shared_size / state_size_configurations)

SELECT percentile_cont(0.9) …   -- needs KLL for ε = 0.01
SELECT percentile_cont(0.5) …   -- needs a smaller KLL, ε = 0.05

One build is sized "with each parameter's largest value among them" (size_for_all_readers). Each reader keeps its own SummaryEstimate, and guarantees are composed again.

Example 3: window composition (memo/rules/state_configurations.rs, "compatible readers at finite shared sizes and pane horizons")

sum_over_time(m[2m])    # every 1m: needs window 2m, step 1m
sum_over_time(m[1m])    # every 1m: needs window 1m, step 1m

One PaneChain is built over a shared grid and the longest window. Each reader derives SummaryMerge { newest_panes: n } from it.

These cases, and more below, have the same shape, but each has its own candidate generation, interning and documentation. The design doc of #509 lists them as unrelated rules. A new case needs a new implementation.

Prior work

Efficient and Extensible Algorithms for Multi Query Optimization (SIGMOD 2000), §2.1, subsumption derivations. For selections that do not subsume each other, "we create a single new node representing the disjunction of all the selection conditions" and derive each selection from it. For aggregates with different group-bys, it creates a node grouped by both and derives each by a further group-by. §3.2 keeps such a node only if sharing it pays off. This issue applies the same idea to every parameter a reader can differ in.

Proposal: one shared-producer rule

Terms

• Need: what one reader requires of the computation, such as its k, its sketch size, its window and step, or its columns, predicate and time window.
• Covering need: the smallest need that satisfies every reader at once, such as the largest k, each size parameter's strictest value, the finest common grid with the longest window, or the union of columns and windows. If none exists (different inputs, partitions or families), the readers cannot share.
• Derivation: how one reader obtains its own result from the covering producer, such as Limit(k) ▸ Project, its SummaryEstimate, SummaryMerge(newest_panes), or Filter ▸ Project. This is the paper's term.

/// One kind of producer that several readers can share.
trait SharedProducer {
    /// What one reader requires of the producer.
    type Need;
    /// The smallest need that satisfies all of `needs`; `None` when they
    /// cannot share one producer.
    fn covering(needs: &[Self::Need]) -> Option<Self::Need>;
    /// The reader whose need is `need`, derived from the covering `producer`.
    fn derive(producer: &Rc<OperatorNode>, need: &Self::Need) -> Rc<OperatorNode>;
}

The rule:

1. Group readers by kind and by the parts of their computation that must be equal (input, partition, update).
2. For each group, compute the covering need and add one producer at it as a memo group (append_producer).
3. Give each reader one more candidate, its derivation from that producer. The originals stay, so plan selection decides and partial sharing comes from each reader's own choice.

Whether a trait or two plain functions per kind is simpler should be settled in the PR. The requirement is one candidate-generation path, not a new public API.

Cases

Three related things are not members:

• Rollup and filtered reads (Reuse a finer aggregate through a compensating filter and a rollup of values or states (view matching) #950): a different kind of rule. They create no producer and read a result another reader already computes.
• Raw-data horizon (Retained raw data as concrete state groups per lookback: offsets, @ and a retention limit #955): a Stage 3 cost item, the retained raw data of a source priced once. It is not a producer node.
• Maintained population (Offer maintained-population top-k candidates in Pass 1 #681): a Pass 1 computation candidate for current-series top-k. It is one way to compute a query class, and its shared max_k cache is incidental. It is not a sharing rule.

Scope and acceptance

First version: the implemented cases (summary capability, exact top-k reuse, window composition, percentile ranks, and identical expression as the trivial case) go through one candidate-generation path. The #509 design doc's rule table lists them as one rule with this case table.

Later members, each its own change: shared scan (#951), different group-bys.

Acceptance:

• No behavior change: the same candidates as on main for the existing tests (reuse_rules, sharing_issue_regressions [Bug] Identical exact query-time aggregates are not shared across queries #922/[Bug] A nested shorter window of an exact sum does not reuse the newest panes of the longer window's chain #924/[Bug] The same query at a longer repeat interval recomputes instead of reusing the shorter-interval result #925, sql_two_percentiles, operator_sharing, tumbling_pane_merge, the logical-asap-optimization lib tests);
• the same selected plans and costs on those workloads;
• one code path for the five implemented cases.

Related

#680 (top-k reuse), #922 (percentile ranks), #950 (finer-aggregate reuse), #951 (shared scan), #955 (raw horizon; Stage 3 cost), #681 (maintained population; a Pass 1 candidate), the design doc of #509.