Price hashed aggregation for hash tables that exceed CPU cache capacity

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

Browse pgsql-hackers by date

  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