Price hashed aggregation for hash tables that exceed CPU cache capacity

Started by William Bernbaum3 months ago2 messageshackers
Jump to latest
#1William Bernbaum
wbernbaum@dwdev.com

Hey hackers,

In CF 7201 [1]CF 7201, skipping NULL keys when uniqueifying a semijoin's RHS [/messages/by-id/PH0PR18MB44436F7F588A50C0EB92383DA6AF2@PH0PR18MB4443.namprd18.prod.outlook.com] 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]CF 7208, Plan an inner join as a semijoin under eager deduplication [/messages/by-id/PH0PR18MB444315CD3E17255AB4A629BEA6AD2@PH0PR18MB4443.namprd18.prod.outlook.com]
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 [/messages/by-id/PH0PR18MB44436F7F588A50C0EB92383DA6AF2@PH0PR18MB4443.namprd18.prod.outlook.com]
[/messages/by-id/PH0PR18MB44436F7F588A50C0EB92383DA6AF2@PH0PR18MB4443.namprd18.prod.outlook.com]

[2]: CF 7208, Plan an inner join as a semijoin under eager deduplication [/messages/by-id/PH0PR18MB444315CD3E17255AB4A629BEA6AD2@PH0PR18MB4443.namprd18.prod.outlook.com]
[/messages/by-id/PH0PR18MB444315CD3E17255AB4A629BEA6AD2@PH0PR18MB4443.namprd18.prod.outlook.com]

Attachments:

t253633_1
0001-Price-hashed-aggregation-for-hash-tables-that-exceed.patchapplication/octet-stream; name=0001-Price-hashed-aggregation-for-hash-tables-that-exceed.patchDownload+87-0
cal_bias.sqlapplication/octet-stream; name=cal_bias.sqlDownload
unique_attrib.sqlapplication/octet-stream; name=unique_attrib.sqlDownload
#2Ethan Tran
ethantran@quwin.dev
In reply to: William Bernbaum (#1)
Review: Price hashed aggregation for hash tables that exceed CPU cache capacity

Hi Will,

This is a review of CF 7244 [1]CF 7244, 2026-09-01,Price hashed aggregation for hash tables that exceed CPU cache capacity /messages/by-id/PH0PR18MB444308903D2F293CEA42B1CCA6A82@PH0PR18MB4443.namprd18.prod.outlook.com.

Contents & Purpose

==================

The patch adds a CPU-cache residency penalty to hashed and mixed aggregation, according to the effective_cpu_cache_size setting. The intention is to improve hash-versus-sort decisions when the hash table exceeds the cpu cache capacity.

The changes include configuration registration, sample configuration, and user documentation. There are no new regression tests.

Initial Run

==================

The patch applies cleanly to HEAD. I found every test passes and compilation works smoothly.

Performance

==================

The intended semijoin case shows a useful improvement. After running unique_attrib.sql, With serial execution and work_mem=256MB, my median measured execution time decreased from 1,272 ms with the penalty disabled to 998 ms at 8MB.

However, I may have found a regression with a wide aggregate argument:

SELECT sum(n)
FROM (
SELECT k, sum(octet_length(p)) AS n
FROM d
GROUP BY k
) q;
With 400,000 rows, 200,000 integer groups, and a 512-byte p, the penalty changes the plan from HashAggregate to Sort + GroupAggregate. One paired series slowed from 137 ms to 169 ms and a second slowed from 118 ms to 160 ms. Forcing hash prevented this slowdown.

The new calculation uses input_width=520, but the wide aggregate argument is consumed rather than retained in each hash entry. The added cost implies approximately 109 MiB of modeled residency, while EXPLAIN reports about 16 MiB of peak hash memory.

The input-width heuristic already exists in spill costing, but the new cache penalty makes it cause an additional plan-selection regression. Could the calculation estimate the retained grouping tuple and transition state more closely?

Nitpicking & Conclusion

==================

One suggestion would be for tests which deliberately activate the penalty. At the default work_mem=4MB and hash_mem_multiplier=2, the memory cap prevents the default 8MB cache setting from adding a charge, so passing default tests does not establish coverage of the new calculation.

The existing cost_agg() comment still says sorted and hashed aggregation have exactly equal total CPU cost. The new “per input tuple” wording also might be misleading because hash_entry_cost already includes multiplication by the input row count.

The intended workload benefits, but I recommend another revision addressing the residency estimate and adding focused regression coverage.

- Ethan

[1]: CF 7244, 2026-09-01,Price hashed aggregation for hash tables that exceed CPU cache capacity /messages/by-id/PH0PR18MB444308903D2F293CEA42B1CCA6A82@PH0PR18MB4443.namprd18.prod.outlook.com
/messages/by-id/PH0PR18MB444308903D2F293CEA42B1CCA6A82@PH0PR18MB4443.namprd18.prod.outlook.com