| From: | William Bernbaum <wbernbaum(at)dwdev(dot)com> |
|---|---|
| To: | "pgsql-hackers(at)lists(dot)postgresql(dot)org" <pgsql-hackers(at)lists(dot)postgresql(dot)org> |
| Subject: | Price hashed aggregation for hash tables that exceed CPU cache capacity |
| Date: | 2026-09-01 13:15:14 |
| Message-ID: | PH0PR18MB444308903D2F293CEA42B1CCA6A82@PH0PR18MB4443.namprd18.prod.outlook.com |
| Views: | Whole Thread | Raw Message | Download mbox | Resend email |
| Thread: | |
| Lists: | pgsql-hackers |
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]
| Attachment | Content-Type | Size |
|---|---|---|
| 0001-Price-hashed-aggregation-for-hash-tables-that-exceed.patch | application/octet-stream | 9.2 KB |
| cal_bias.sql | application/octet-stream | 11.6 KB |
| unique_attrib.sql | application/octet-stream | 5.0 KB |
| From | Date | Subject | |
|---|---|---|---|
| Next Message | vignesh C | 2026-09-01 13:43:42 | Re: Logical replication row filter loses unchanged toasted columns |
| Previous Message | Nazir Bilal Yavuz | 2026-09-01 13:05:44 | Re: [PATCH] Speed up pg_waldump TAP test and fix some GitHub CI Windows flakiness |