Where the grant number comes from
Why is the optimizer's estimation error the memory manager's failure distribution, and what does feedback fix?
A memory grant is computed as
Both factors come from the query optimizer's statistics (summaries of the data, such as row counts and value histograms, that the optimizer uses to guess the size of every intermediate result). So the optimizer's estimation error is the memory manager's failure distribution, in different units.
The error is large and not symmetric
Leis and colleagues (VLDB 2015) compared optimizer estimates with the truth on real join queries. They found that errors grow with the number of joins and reach several orders of magnitude, even when the statistics for each single table are accurate. The reason: predicates are correlated (for example, city = 'Oslo' and country = 'Norway' are not independent), but the estimator multiplies their selectivities as if they were independent. This is the "independence is assumed but false" idea arriving upstream, and here it arrives as an OOM.
The shape of the error dictates the mechanism
Estimates are roughly log-normal around the truth with a heavy right tail. (Log-normal: the logarithm of the error is bell-shaped. The effect is that errors are multiplicative, "10× too low" and "10× too high" are equally likely in log scale, and very large errors in the high direction exist.) So:
- Granting at the estimate fails constantly, because half of the estimates are too low and the tail is fat.
- Granting at a fixed multiple of the estimate wastes constantly, because the multiple must be big enough to cover the tail.
- The tail, not the mean, sizes the grant. This is the principle "variance matters more than the average" in the most expensive place it appears here.
The two errors are not equal
- Under-estimating gives a grant that is too small. The result is spill: slower, but still correct. This holds provided the operator can spill.
- Over-estimating gives a grant that is too large. The result is lost concurrency, and a system that queues queries while it sits idle.
Under-estimation is the cheaper error if and only if everything is spillable. This is the strongest argument for making spill universal, and it is the bridge to Degradation: spill is what makes estimation error survivable, and the quality of your estimator determines how much you need it.
Three mitigations, in order of interest
- Caps. No query may be granted more than some fraction of the pool. This is an isolation device, not an accuracy device: it limits the damage of a bad estimate without making the estimate better.
- Mid-flight adjustment. Decide whether to spill based on the actual accumulated size, not the estimated size. This forces the operator to change its algorithm in the middle of running. That is a real constraint on operator design and is the subject of Degradation.
- Feedback from execution. Record the actual peak footprint and grant from that value the next time the same plan runs. SQL Server's memory grant feedback does exactly this. It adjusts the grant up after a spill and down after a large unused grant, within bounds, and with a stability check to stop it from swinging back and forth on workloads that genuinely vary.
The third mitigation is the same move as the ghost lists of ARC from Residency: the mistake is observable after the fact, so measure it instead of trying to predict it better. Twenty years of research on cardinality estimation bought less than one execution's worth of ground truth.
One-line compression: a memory grant is a cardinality estimate in different units, so the optimizer's error distribution is the memory manager's failure distribution, and one measured execution beats any estimator.