PaperlayerView exact revision on arXiv

Source-linked AI summary

Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering

Mihail Stoian

arXiv:2610.10282v2cs.DScs.DB

TL;DR

Exact min-sum subset convolution has a direct 3^n evaluation baseline, and earlier exact algorithms had magnitude-bounded inputs. This paper reduces the problem to min-plus matrix products; instantiating the reduction gives sub-3^n convolution algorithms and matching bounds for C_out join ordering.

  • Problem

    Direct evaluation examines 3^n ordered disjoint pairs, and earlier min-sum algorithms required integer values strictly bounded in magnitude by M.

    Source: §1 · p. 1

  • Method

    A deterministic reduction converts min-sum subset convolution to min-plus matrix products, with a sub-3^n bound when those products have a fixed subcubic exponent.

    Source: §1 · pp. 1–2

  • Results

    Expected O*(2.9987^n) Las Vegas and O*(2.9997^n) deterministic algorithms solve min-sum subset convolution on integer inputs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The same bounds apply to C_out join ordering when cardinality estimates are computable in poly(n, β) time, for ordinary undirected query graphs with or without cross products.

    Source: §1 · p. 2, §5 · p. 8

    The stated bounds assume a fixed rational δ and binary-encoded integer inputs, with polynomial dependence on their bit length.

    Source: §1 · p. 2, §3 · p. 4

Abstract

from arXiv · show

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $\beta$-bit integer entries can be computed in $D^{3-\delta}\operatorname{poly}(\beta,\log D)$ time for a fixed rational $0<\delta<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-\delta})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,\beta)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

1 Introduction

The paper reduces exact min-sum subset convolution to min-plus matrix multiplication, targeting the direct 3^n enumeration barrier. With subcubic min-plus products, it obtains sub-3^n bounds and transfers them to C_out join ordering.

1 Introduction

  • Direct evaluation examines 3^n ordered disjoint pairs, while earlier min-sum algorithms relied on integer values bounded in magnitude by M.Stoian conjectured that exact min-sum subset convolution could not run in O((3 − ε)^n polylog M) time for any constant ε > 0.Source: §1 · p. 1
  • Earlier exact C_out optimization had running time O*(2^n W), retaining linear dependence on the largest cardinality W.Stoian and Kipf formalized the connection between join ordering and subset convolution.Source: §1 · p. 1
  • A deterministic reduction from min-sum subset convolution to min-plus matrix products yields truly sub-3^n algorithms without a polynomial bound on input magnitudes.The algorithm has only polynomial dependence on the binary encoding length of the integer inputs.Source: §1 · p. 1
  • Expected O*(2.9987^n) Las Vegas and O*(2.9997^n) deterministic algorithms solve min-sum subset convolution on integer inputs.The reduction uses subcubic min-plus matrix product algorithms.Source: §1 · pp. 1–2
  • Join ordering under C_out has the same bounds when each cardinality estimate is computable in poly(n, β) time, with or without cross products for ordinary undirected query graphs.This result applies the subset-convolution algorithm to the join-ordering connection.Source: §1 · pp. 1–2

2 Restricted Matrix Products

The section partitions candidate evaluations using restrictions of the universe, then encodes compatible splits as min-plus matrix products. A family of such restrictions covers every candidate, while blocked products yield the stated update cost.

2 Restricted Matrix Products

  • Each candidate split is represented as an ordered ternary partition (A, B, C), where C contains elements outside the output set.For a fixed output set S, C is fixed while elements of S are divided between A and B.Source: §2 · p. 2
  • A restriction (X, Y, Z) permits X in either child, Y in the right child or outside, and Z in the left child or outside.Compatibility excludes X∩C, Y∩A, and Z∩B.Source: §2 · p. 3
  • For each restriction, F[U,T]=f(U∪T) and G[T,V]=g((X\T)∪V) encode operands for a min-plus product.The product entry is the minimum f(A)+g(B) over compatible candidates whose union is X∪U∪V.Source: §2 · p. 3
  • Taking minima across the restricted products updates h(S) with precisely the splits compatible with each restriction.The product output is the minimum cost among those splits and supplies an update to h(S).Source: §2 · p. 3
  • If m=min{|X|,|Y|,|Z|}, all updates from one restriction take 2^(n−δm) poly(n, β) time under the theorem’s assumption.The matrices are tiled into blocks of length 2^m; replacing +∞ with H=4W+1 and mapping sums exceeding 2W back to +∞ preserves valid updates.Source: §2 · pp. 3–4

3 A Deterministic Covering Lemma

The section constructs deterministic families of restrictions that cover every ordered ternary partition. A weighted greedy set-cover procedure provides the construction, including restrictions with empty parts.

3 A Deterministic Covering Lemma

  • For every r≥1, a complete family of restrictions can be constructed deterministically in 2^O(r) bit operations.Completeness means every ordered partition (A, B, C) of the block is compatible with some family member.Source: §3 · pp. 4–5
  • The construction’s constants may depend on the fixed rational δ.For fixed rational δ, the rounded weights and integer-root comparisons can be computed with 2^O(r) bit operations.Source: §3 · pp. 4–5
  • Each candidate belongs to exactly 2^r restriction-coverage sets, enabling the proof to bound the greedy cover’s total weight.The method uses q=2^−δ and rounds q^k upward to a multiple of 2^−r, keeping the rounded weight between q^k and 2q^k.Source: §3 · pp. 4–5
  • The construction applies weighted greedy set cover to restrictions, repeatedly selecting one that minimizes its weight per newly covered candidate.It continues until all candidates are covered; the proof accounts for extreme partitions with empty parts.Source: §3 · p. 5

4 Truly Sub-3n Min-Sum Subset Convolution

The algorithm partitions the universe into blocks and builds min-plus products over restrictions of those blocks. Aggregating the products over a complete family of restrictions returns the exact min-sum subset convolution.

4 Truly Sub-3n Min-Sum Subset Convolution

  • The blockwise construction concatenates one local-family member per block, and the resulting family can be enumerated without materializing its Cartesian product.The universe is partitioned into blocks of size at most ⌈√n⌉.Source: §4 · p. 6
  • For each restriction σ, the algorithm forms matrices from f and g values and computes their min-plus product over subset indices.The matrices use f(U ∪ T) and g((Xσ \ T) ∪ V) as entries.Source: §4 · p. 6
  • Each product entry gives the minimum cost among compatible splits of the same output set, supplying an update to h.The output set is S = Xσ ∪ U ∪ V.Source: §4 · p. 6
  • Completeness ensures every disjoint pair is considered, so the minimum updates return exactly the convolution table.Repeated candidates do not affect the result because minimum is idempotent.Source: §4 · p. 6
  • The covers take 2^O(√n) poly(n) construction time, and exact matrix products preserve exactness; Las Vegas products yield the corresponding expected bound.The weighted summation accounts for all restriction shapes, including empty parts.Source: §4 · p. 7

5 Application: Join Ordering

The paper applies its subset-convolution algorithm to the layer-wise dynamic program for join ordering under Cout. The resulting running-time bounds match the convolution bounds, including when cross products are forbidden in ordinary undirected query graphs.

5 Application: Join Ordering

  • LeDP applies the subset-convolution algorithm to Stoian and Kipf's layer-wise dynamic program, changing DPconv's convolution computation.The objective charges each internal plan node with leaf set S according to c(S).Source: §5 · p. 7
  • The dynamic program computes OPT(S) using the minimum over proper nonempty subsets A of OPT(A) + OPT(S \ A).The recurrence is implemented layer by layer, with values for sets of size below k retained at each stage.Source: §5 · p. 7
  • The dynamic-programming layer construction reproduces the recurrence by induction on k.Each proper nonempty child of S has size less than k, while the empty set has infinite value in f_k.Source: §5 · pp. 7–8
  • For ordinary undirected query graphs, retaining only connected sets forbids cross products without excluding any cross-product-free binary plan.Connectivity testing over all subsets takes 2^n poly(n) time.Source: §5 · p. 8
  • Applying Corollary 2 to the n −1 convolution calls gives expected O*(2.9987^n) Las Vegas time and O*(2.9997^n) deterministic time.Optimal-plan reconstruction takes 2^n poly(n, β) time.Source: §5 · p. 8

A Instantiating the Min-Plus Primitive

The appendix establishes bit-complexity bounds for Alman and Vassilevska Williams's min-plus algorithms on β-bit integer inputs. These bounds instantiate the reduction and yield the stated convolution exponents.

A Instantiating the Min-Plus Primitive

Loading 2610.10282v2…