Your planner parenthesizes a fixed chain of joins with interval DP — when do you abandon the exact search?

## The setting A request arrives that combines a fixed sequence of datasets pairwise. The *order* of the sequence is given; only the **grouping** is yours to choose, and the cost of each pairwise combination depends on the sizes of its two operands. This is exactly the interval-DP shape: `dp[i][j]` is the cheapest way to combine everything from `i` to `j`, the branch is on the top-level operation that splits the chain at `k`, the fill is shortest-interval-first, and the profile is O(n^3) time and O(n^2) space. The question a lead has to answer is not "can I write it" but "should this run on every request, and at what size do I stop." ## Ceiling one: the resource budget Start with honest arithmetic. The innermost line runs once per triple with the split strictly inside, about `n^3/6` times: - 30-item chain: about 4,000 transitions. Microseconds. Free. - 300-item chain: about 4.5 million. Single-digit milliseconds. Fine once per request at modest rates; questionable at thousands of requests per second, where planning would consume a visible share of the fleet. - 3,000-item chain: about 4.5 billion transitions, plus a table of nine million cells — and two tables if you also store the winning split points to reconstruct the plan. That is on the order of a hundred-plus megabytes for one in-flight request, and quadratic space here does **not** compress to a rolling window the way a prefix DP does, because an entry reads arbitrary interior subranges. So the resource rule is a ratio, not a constant: **planning time should be a small fraction of the execution time it is expected to save**, and peak planner memory times concurrency must fit the per-instance ceiling. On a fleet, the second constraint usually bites first, and it bites as an availability incident rather than as a slow query. ## Ceiling two: the quality of the inputs This is the one that separates a principal answer. The DP is exact with respect to `w(i, j)`. But `w(i, j)` is computed from *estimated* intermediate sizes, and those estimates come from statistics that are sampled, stale, and combined under independence assumptions that rarely hold. Estimate error compounds multiplicatively along a chain: by the tenth combination the predicted size may be off by orders of magnitude. The consequence is uncomfortable and worth stating out loud: **an exact optimum over a noisy objective is not obviously better than a good approximation over the same noisy objective.** Beyond some chain length, the difference between the DP's plan and a decent heuristic's plan is smaller than the error bars on the numbers that ranked them. Spending cubic time to resolve a distinction the inputs cannot support is not rigour, it is theatre. That argues for two things a heuristic gets you almost for free: robustness (prefer plans that are merely good across a range of plausible sizes over plans that are optimal for one point estimate) and the option to re-plan with observed sizes once execution has begun. ## Ceiling three: the team A triple loop with a reconstruction table, a threshold, and a fallback path is three code paths where there was one, and every one of them must be understood by whoever is paged at 3am. If the exact method fires on one percent of requests, that one percent is also the least-tested path in the system. A lead should ask whether the measured win on that one percent justifies permanently carrying the branch — sometimes it plainly does, and sometimes the honest answer is that a single well-understood heuristic with predictable behaviour is worth more than a rarely-exercised optimum. ## What the decision actually looks like 1. **Instrument before optimising.** Log the chain-length distribution. If the ninety-ninth percentile is twelve, the cubic bound is irrelevant and you should stop the conversation there. 2. **Set a threshold from the ratio, not from a round number.** Run exact interval DP up to the length where planning stays under a stated fraction of expected execution; above it, use a heuristic ordering. 3. **Cap memory explicitly,** since quadratic space times concurrency is the availability risk, and the table does not compress. 4. **Measure the regret,** not the optimality. Sample requests, compute both plans offline, and compare *actual* execution. If the heuristic's plans cost within a few percent in practice, the exact path is a maintenance liability whatever the theory says. 5. **Attack the inputs before the algorithm.** Better size estimates usually improve plans more than exhaustively searching a space ranked by bad numbers. ## How to defend the call The defensible position is neither "exact is always right" nor "heuristics are good enough." It is: *the exact method is cheap and clearly correct in the size range where our traffic actually lives, so we use it there; beyond that range its cost is real, its advantage is inside the noise of our estimates, and we fall back — and here is the measurement that tells us if that boundary moves.* That answer names the budget, names the uncertainty, names the maintenance cost, and commits to a number that can be revisited with data.