Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Join — where it appears

Combining two collections by pairing each element of one with the elements of the other that share a key. Its cost depends on the method and on the sizes involved, and the size of its result is a sum of products of counts that a uniform estimate can misjudge badly.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

1×10×10³10⁴the key side, as a multiple of memoryblock transfersblock nested looppartitioned hash joinsort–merge joinB = 64, M = 512 (M/B = 8)the other relation: 16,384 rows

Two ways to join, and the ratio that decides

The same join costs 260 transfers one way and 1,040 the other; at eight times the memory the same two costs are 2,880 and 1,280, the other way round. Neither number is a property of how large the tables are. The quantity that decides is how the smaller of them compares to memory, and a rule of thumb phrased in rows is a rule about somebody's machine.

applied · Transfer 1×2×5×10×20×50×00.40.811.2skew of the join columnratio, logarithmicestimate off byregret, decided partregret, whole planR 4,000, S 40,000, T 2,000 rows, B = 64, M = 4,096 (M/B = 64)every order writes the same output

The join order is a guess

Three tables, two orders, and an estimate of the first intermediate result that assumes the join column is uniform. When the column is skewed the estimate is out by seventy-two times, and the plan chosen on it costs 1.49 times the better one — which sounds tolerable until the shared output is taken away, and the part of the cost the order actually decided turns out to be 43.9 times worse.

applied · Transfer 1×2×5×10×20×50×100×200×00.250.50.7511.251.51.752skew of the join columnregret of the decided part, logarithmicuniform estimate4 counters a side16 counters a side64 counters a side256 counters a sideR 4,000, S 40,000, T 2,000 rows · 64-record blocks, 4,096 in memoryMisra–Gries on each side of the join column

The skew a few counters cannot repair

A join order chosen on the textbook estimate costs 243.9 times the better order at a Zipf exponent of two, and two counters a side are enough to fix it. At an exponent of one half the estimate is out by less than a factor of two, the plan it picks costs 1.37 times the better one, and no number of counters up to 256 changes that. The easy case is the extreme one, and the reason the moderate one is hard is a series that stops converging at exactly one half.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Block transferQuery planCardinality estimateEstimatorHeavy hitterIndependence assumptionMisra–GriesRegretRelative errorZipf distributionCost modelDenominator

All concepts