Hey hackers, In CF 7201 [1] I mentioned a costing residual which this patch attempts to fix.
cost_agg() charges cpu_operator_cost per grouping column to hash each
input tuple; however, it does not price the table probe. Probe latency rises
by roughly a constant for every doubling of the table beyond the cache.
cost_agg()'s estimate does not model this and biases the planner toward
hashing.
Deduplicating the same 2M-row input two ways. Cost is the estimate for
the dedup subtree:
unpatched cost patched cost measured
HashAggregate 172,240 342,668 1148 ms
Sort + Unique 314,993 314,993 528 ms
Unpatched, hashing is priced at 0.55 of the sort although it measures
2.17x slower. The relative price is off by a factor of 4.0, and the planner
takes the slower plan. Patched, it takes the 528ms one.
The patch charges each input tuple cpu_tuple_cost times a fixed
multiplier for every doubling of the resident table beyond a cache
size threshold. This patch proposes that threshold land as a new GUC,
effective_cpu_cache_size, defaulted to 8MB. 0 reproduces the behavior
on master.
The attached harness sweeps key type, payload width and group count, and
demonstrates that cost_agg() underprices hashing relative to sorting by a
geometric mean factor of 2.8x, deepening as the table grows. Where the
patch reaches, the error averages 1.06x, with individual configurations
landing within about 30% of the measured ratio. The regression suite
passes unchanged at the default (8MB).
NB: The charge applies to the part of the table allowed to stay in memory,
which hash_agg_set_limits() caps at work_mem times hash_mem_multiplier.
At the stock 4MB and 2.0 that cap is 8MB, the same as the default
effective_cpu_cache_size, so estimates do not change until work_mem is raised.
One additional note: The eager deduplication series in CF 7208 [2]
benefits tangibly from this patch. See link below.
Attached: the patch; cal_bias.sql, which costs every configuration
both ways, and unique_attrib.sql, which attributes results.
-Will
[1] CF 7201, skipping NULL keys when uniqueifying a semijoin's RHS
[https://www.postgresql.org/message-id/PH0PR18MB44436F7F588A50C0EB92383DA6AF2%40PH0PR18MB4443.namprd18.prod.outlook.com]
[2] CF 7208, Plan an inner join as a semijoin under eager deduplication
[https://www.postgresql.org/message-id/PH0PR18MB444315CD3E17255AB4A629BEA6AD2%40PH0PR18MB4443.namprd18.prod.outlook.com]
0001-Price-hashed-aggregation-for-hash-tables-that-exceed.patch
Description: 0001-Price-hashed-aggregation-for-hash-tables-that-exceed.patch
cal_bias.sql
Description: cal_bias.sql
unique_attrib.sql
Description: unique_attrib.sql
