public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v8 4/8] Propagate changes to indisclustered to child/parents 11+ messages / 4 participants [nested] [flat]
* [PATCH v8 4/8] Propagate changes to indisclustered to child/parents @ 2020-10-07 03:11 Justin Pryzby <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Justin Pryzby @ 2020-10-07 03:11 UTC (permalink / raw) --- src/backend/commands/cluster.c | 109 ++++++++++++++++---------- src/backend/commands/indexcmds.c | 2 + src/test/regress/expected/cluster.out | 46 +++++++++++ src/test/regress/sql/cluster.sql | 11 +++ 4 files changed, 125 insertions(+), 43 deletions(-) diff --git a/src/backend/commands/cluster.c b/src/backend/commands/cluster.c index cb4fc350c6..5c08f0642e 100644 --- a/src/backend/commands/cluster.c +++ b/src/backend/commands/cluster.c @@ -74,6 +74,7 @@ static void rebuild_relation(Relation OldHeap, Oid indexOid, bool verbose); static void copy_table_data(Oid OIDNewHeap, Oid OIDOldHeap, Oid OIDOldIndex, bool verbose, bool *pSwapToastByContent, TransactionId *pFreezeXid, MultiXactId *pCutoffMulti); +static void set_indisclustered(Oid indexOid, bool isclustered, Relation pg_index); static List *get_tables_to_cluster(MemoryContext cluster_context); static List *get_tables_to_cluster_partitioned(MemoryContext cluster_context, Oid indexOid); @@ -516,66 +517,88 @@ check_index_is_clusterable(Relation OldHeap, Oid indexOid, bool recheck, LOCKMOD index_close(OldIndex, NoLock); } +/* + * Helper for mark_index_clustered + * Mark a single index as clustered or not. + * pg_index is passed by caller to avoid repeatedly re-opening it. + */ +static void +set_indisclustered(Oid indexOid, bool isclustered, Relation pg_index) +{ + HeapTuple indexTuple; + Form_pg_index indexForm; + + indexTuple = SearchSysCacheCopy1(INDEXRELID, + ObjectIdGetDatum(indexOid)); + if (!HeapTupleIsValid(indexTuple)) + elog(ERROR, "cache lookup failed for index %u", indexOid); + indexForm = (Form_pg_index) GETSTRUCT(indexTuple); + + /* this was checked earlier, but let's be real sure */ + if (isclustered && !indexForm->indisvalid) + elog(ERROR, "cannot cluster on invalid index %u", indexOid); + + indexForm->indisclustered = isclustered; + CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); + heap_freetuple(indexTuple); +} + /* * mark_index_clustered: mark the specified index as the one clustered on * - * With indexOid == InvalidOid, will mark all indexes of rel not-clustered. + * With indexOid == InvalidOid, mark all indexes of rel not-clustered. + * Otherwise, mark children of the clustered index as clustered, and parents of + * other indexes as unclustered. + * We wish to maintain the following properties: + * 1) Only one index on a relation can be marked clustered at once + * 2) If a partitioned index is clustered, then all its children must be + * clustered. */ void mark_index_clustered(Relation rel, Oid indexOid, bool is_internal) { - HeapTuple indexTuple; - Form_pg_index indexForm; - Relation pg_index; - ListCell *index; - - /* - * If the index is already marked clustered, no need to do anything. - */ - if (OidIsValid(indexOid)) - { - if (get_index_isclustered(indexOid)) - return; - } + ListCell *lc, *lc2; + List *indexes; + Relation pg_index = table_open(IndexRelationId, RowExclusiveLock); + List *inh = find_all_inheritors(RelationGetRelid(rel), ShareRowExclusiveLock, NULL); /* * Check each index of the relation and set/clear the bit as needed. + * Iterate over the relation's children rather than the index's children + * since we need to unset cluster for indexes on intermediate children, + * too. */ - pg_index = table_open(IndexRelationId, RowExclusiveLock); - - foreach(index, RelationGetIndexList(rel)) + foreach(lc, inh) { - Oid thisIndexOid = lfirst_oid(index); - - indexTuple = SearchSysCacheCopy1(INDEXRELID, - ObjectIdGetDatum(thisIndexOid)); - if (!HeapTupleIsValid(indexTuple)) - elog(ERROR, "cache lookup failed for index %u", thisIndexOid); - indexForm = (Form_pg_index) GETSTRUCT(indexTuple); + Oid inhrelid = lfirst_oid(lc); + Relation thisrel = table_open(inhrelid, ShareRowExclusiveLock); - /* - * Unset the bit if set. We know it's wrong because we checked this - * earlier. - */ - if (indexForm->indisclustered) + indexes = RelationGetIndexList(thisrel); + foreach (lc2, indexes) { - indexForm->indisclustered = false; - CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); - } - else if (thisIndexOid == indexOid) - { - /* this was checked earlier, but let's be real sure */ - if (!indexForm->indisvalid) - elog(ERROR, "cannot cluster on invalid index %u", indexOid); - indexForm->indisclustered = true; - CatalogTupleUpdate(pg_index, &indexTuple->t_self, indexTuple); - } + bool isclustered; + Oid thisIndexOid = lfirst_oid(lc2); + List *parentoids = get_rel_relispartition(thisIndexOid) ? + get_partition_ancestors(thisIndexOid) : NIL; - InvokeObjectPostAlterHookArg(IndexRelationId, thisIndexOid, 0, - InvalidOid, is_internal); + /* + * A child of the clustered index must be set clustered; + * indexes which are not children of the clustered index are + * set unclustered + */ + isclustered = (thisIndexOid == indexOid) || + list_member_oid(parentoids, indexOid); + Assert(OidIsValid(indexOid) || !isclustered); + set_indisclustered(thisIndexOid, isclustered, pg_index); + + InvokeObjectPostAlterHookArg(IndexRelationId, thisIndexOid, 0, + InvalidOid, is_internal); + } - heap_freetuple(indexTuple); + list_free(indexes); + table_close(thisrel, ShareRowExclusiveLock); } + list_free(inh); table_close(pg_index, RowExclusiveLock); } diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c index 127ba7835d..4ca1ffbfa4 100644 --- a/src/backend/commands/indexcmds.c +++ b/src/backend/commands/indexcmds.c @@ -25,6 +25,7 @@ #include "catalog/catalog.h" #include "catalog/index.h" #include "catalog/indexing.h" +#include "catalog/partition.h" #include "catalog/pg_am.h" #include "catalog/pg_constraint.h" #include "catalog/pg_inherits.h" @@ -32,6 +33,7 @@ #include "catalog/pg_opfamily.h" #include "catalog/pg_tablespace.h" #include "catalog/pg_type.h" +#include "commands/cluster.h" #include "commands/comment.h" #include "commands/dbcommands.h" #include "commands/defrem.h" diff --git a/src/test/regress/expected/cluster.out b/src/test/regress/expected/cluster.out index c74cfa88cc..1d436dfaae 100644 --- a/src/test/regress/expected/cluster.out +++ b/src/test/regress/expected/cluster.out @@ -495,6 +495,52 @@ Indexes: "clstrpart_idx" btree (a) CLUSTER Number of partitions: 3 (Use \d+ to list them.) +-- Test that it recurses to grandchildren: +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) CLUSTER + +ALTER TABLE clstrpart SET WITHOUT CLUSTER; +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) + +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +\d clstrpart33 + Table "public.clstrpart33" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart3 DEFAULT +Indexes: + "clstrpart33_a_idx" btree (a) CLUSTER + +-- Check that only one child is marked clustered after marking clustered on a different parent +CREATE INDEX clstrpart1_idx_2 ON clstrpart1(a); +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +ALTER TABLE clstrpart1 CLUSTER ON clstrpart1_idx_2; +\d clstrpart1 + Partitioned table "public.clstrpart1" + Column | Type | Collation | Nullable | Default +--------+---------+-----------+----------+--------- + a | integer | | | +Partition of: clstrpart FOR VALUES FROM (1) TO (10) +Partition key: RANGE (a) +Indexes: + "clstrpart1_a_idx" btree (a) + "clstrpart1_idx_2" btree (a) CLUSTER +Number of partitions: 2 (Use \d+ to list them.) + -- Test CLUSTER with external tuplesorting create table clstr_4 as select * from tenk1; create index cluster_sort on clstr_4 (hundred, thousand, tenthous); diff --git a/src/test/regress/sql/cluster.sql b/src/test/regress/sql/cluster.sql index 9bcc77695c..0ded2be1ca 100644 --- a/src/test/regress/sql/cluster.sql +++ b/src/test/regress/sql/cluster.sql @@ -220,6 +220,17 @@ CLUSTER clstrpart1 USING clstrpart1_a_idx; -- partition which is itself partitio CLUSTER clstrpart12 USING clstrpart12_a_idx; -- partition which is itself partitioned, no childs CLUSTER clstrpart2 USING clstrpart2_a_idx; -- leaf \d clstrpart +-- Test that it recurses to grandchildren: +\d clstrpart33 +ALTER TABLE clstrpart SET WITHOUT CLUSTER; +\d clstrpart33 +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +\d clstrpart33 +-- Check that only one child is marked clustered after marking clustered on a different parent +CREATE INDEX clstrpart1_idx_2 ON clstrpart1(a); +ALTER TABLE clstrpart CLUSTER ON clstrpart_idx; +ALTER TABLE clstrpart1 CLUSTER ON clstrpart1_idx_2; +\d clstrpart1 -- Test CLUSTER with external tuplesorting -- 2.17.0 --O5XBE6gyVG5Rl6Rj Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v8-0005-Invalidate-parent-indexes.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2024-11-18 10:13 Heikki Linnakangas <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Heikki Linnakangas @ 2024-11-18 10:13 UTC (permalink / raw) To: Jeff Davis <[email protected]>; pgsql-hackers On 18/11/2024 02:01, Jeff Davis wrote: > > TupleHashEntryData is the size of a hash bucket, and it's currently 24 > bytes. The size of the structure is important for HashAgg and other > callers that can build up large hashtables of small tuples. Waste in > this structure is even worse when the hash table is sparse, because the > space is consumed whether the bucket is occupied or not. > > The attached patch series brings it down to 12. There are several > unappealing hacks, so ideally we'd find something cleaner, but halving > the bucket size seems quite desirable if it can be done in an > acceptable way. Makes sense. > 0001: This patch makes the structure private, so that it's easier to > control the way the structure is accessed. Seems pretty uncontroversial. You removed the typedef for struct TupleHashEntryData, which is a bit unusual for our usual source style. Was there a reason for that? > 0002: Removes the "additional" pointer, instead storing it right after > the tuple, which is already stored in a separate chunk. Hack: this > crams the "additional" pointer after the MinimalTuple in the same chunk > of memory to avoid adding additional palloc()s. Hmm, it would seem more straightforward to store it in the beginning, i.e. have something like this: struct { void *additional; MinimalTupleData mtup; } ; Come to think of it, how important is it that we use MinimalTuple here at all? Some other representation could be faster to deal with in TupleHashTableMatch() anyway. > 0003: simplehash: allow the caller to decide which entries are empty vs > in-use rather than requiring a separate "status" field. This may limit > other possible status values in the future (i.e. adding on to the > enum), but I'm not sure what those other stutus values might be. +1. I've wanted to have this in the past. > 0004: Removes the "status" field from TupleHashEntryData, using > firstTuple==NULL to mean "empty", otherwise "in use". Hack: need an > additional "special" pointer value to mean "input slot" now that NULL > means "empty". +1 > 0005: Pack TupleHashEntryData. IIUC, this is fine even on machines that > can't do unaligned access, so long as we are accessing the fields > through the struct, and not taking the address of individual members. Seems OK. I wonder if the compiler understands that the elements are still 4-byte aligned, or if it forces byte-per-byte access? Playing with godbolt a little, it seems like GCC at least understands it, but clang does not. On architectures with non-strict alignment, it doesn't matter as a simple load/store instruction is the fastest option anyway. -- Heikki Linnakangas Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2024-11-18 20:22 Jeff Davis <[email protected]> parent: Heikki Linnakangas <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Jeff Davis @ 2024-11-18 20:22 UTC (permalink / raw) To: Heikki Linnakangas <[email protected]>; pgsql-hackers On Mon, 2024-11-18 at 12:13 +0200, Heikki Linnakangas wrote: > Seems pretty uncontroversial. You removed the typedef for struct > TupleHashEntryData, which is a bit unusual for our usual source > style. > Was there a reason for that? If it's private to a file and I don't intend to use it a lot, I do it to cut down typedefs.list bloat. I'll go ahead and add the typedef back to match the style, though. > > Hmm, it would seem more straightforward to store it in the beginning, > i.e. have something like this: > > struct { > void *additional; > MinimalTupleData mtup; > } ; That was my first approach, but it requires an additional memcpy, because ExecCopySlotMinimalTuple() does it's own palloc. I used repalloc() because it will often have space at the end of the chunk anyway, and not need to memcpy(). Maybe that's not significant but it did seem detectable in some perf tests. But perhaps we can go further and get rid of the "additional" pointer and inline the pergroup data and the grouping key tuple into the same palloc chunk? That would cut out a palloc and the 8 wasted bytes on the pointer. > Come to think of it, how important is it that we use MinimalTuple > here > at all? Some other representation could be faster to deal with in > TupleHashTableMatch() anyway. What did you have in mind? That sounds like a good idea orthogonal to reducing the bucket size. Alternatively, MinimalTuple is not very "minimal", and perhaps we can just make it better. > > > 0004: Removes the "status" field from TupleHashEntryData, using > > firstTuple==NULL to mean "empty", otherwise "in use". Hack: need an > > additional "special" pointer value to mean "input slot" now that > > NULL > > means "empty". > > +1 For the FIRSTTUPLE_INPUTSLOT marker, do you think it's cleaner to use what I did: const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1; or something like: static MinimalTupleData dummy = {0}; const static MinimalTuple FIRSTTUPLE_INPUTSLOT = &dummy; ? > > On architectures with non-strict alignment, it doesn't matter as a > simple load/store instruction is the fastest option anyway. My intuition is that the cost of dereferencing that pointer (to memory which is not expected to be in cache) is going to be way higher than the cost of a couple extra instructions to do the unaligned access. Regards, Jeff Davis ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2024-11-18 23:30 Heikki Linnakangas <[email protected]> parent: Jeff Davis <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Heikki Linnakangas @ 2024-11-18 23:30 UTC (permalink / raw) To: Jeff Davis <[email protected]>; pgsql-hackers On 18/11/2024 22:22, Jeff Davis wrote: > On Mon, 2024-11-18 at 12:13 +0200, Heikki Linnakangas wrote: >> Hmm, it would seem more straightforward to store it in the beginning, >> i.e. have something like this: >> >> struct { >> void *additional; >> MinimalTupleData mtup; >> } ; > > That was my first approach, but it requires an additional memcpy, > because ExecCopySlotMinimalTuple() does it's own palloc. I used > repalloc() because it will often have space at the end of the chunk > anyway, and not need to memcpy(). Maybe that's not significant but it > did seem detectable in some perf tests. > > But perhaps we can go further and get rid of the "additional" pointer > and inline the pergroup data and the grouping key tuple into the same > palloc chunk? That would cut out a palloc and the 8 wasted bytes on the > pointer. Sounds like a good idea. Needs some changes to the TupleTableSlotOps interface to avoid the memcpy I presume. >> Come to think of it, how important is it that we use MinimalTuple >> here >> at all? Some other representation could be faster to deal with in >> TupleHashTableMatch() anyway. > > What did you have in mind? That sounds like a good idea orthogonal to > reducing the bucket size. Queries that have a only a small number of groups might might benefit from storing a plain Datum/isnull array instead of a MinimalTuple. That would take more memory when you have a lot of groups though. > Alternatively, MinimalTuple is not very "minimal", and perhaps we can > just make it better. Yeah. It tries to be compatible with HeapTuple, but perhaps we should give up on that and pack it more tightly instead. >>> 0004: Removes the "status" field from TupleHashEntryData, using >>> firstTuple==NULL to mean "empty", otherwise "in use". Hack: need an >>> additional "special" pointer value to mean "input slot" now that >>> NULL >>> means "empty". >> >> +1 > > For the FIRSTTUPLE_INPUTSLOT marker, do you think it's cleaner to use > what I did: > > const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1; > > or something like: > > static MinimalTupleData dummy = {0}; > const static MinimalTuple FIRSTTUPLE_INPUTSLOT = &dummy; > > ? I think I'd do "(MinimalTuple) 0x1" myself, but no strong opinion. -- Heikki Linnakangas Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2024-11-21 20:37 Jeff Davis <[email protected]> parent: Heikki Linnakangas <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Jeff Davis @ 2024-11-21 20:37 UTC (permalink / raw) To: Heikki Linnakangas <[email protected]>; pgsql-hackers New patch series attached. * a few cleanup patches, but 0001 and 0004 can affect initial hash table sizing * also pack AggStatePerGroupData (to 10 bytes) * put additional data in the same chunk as firstTuple to avoid an extra pointer an an extra allocation On Tue, 2024-11-19 at 01:30 +0200, Heikki Linnakangas wrote: > Sounds like a good idea. Needs some changes to the TupleTableSlotOps > interface to avoid the memcpy I presume. Neither firstTuple nor the additional data have a size known at compile time, so it can't be represented by a struct. It seems best to keep firstTuple at the beginning so that it matches the SH_KEY_TYPE, and then just repalloc() to make room at the end for the additional data, which avoids the memcpy unless it crosses a power-of-two boundary. > > > Queries that have a only a small number of groups might might benefit > from storing a plain Datum/isnull array instead of a MinimalTuple. > That > would take more memory when you have a lot of groups though. The current MinimalTuple representation is pretty wasteful for small grouping keys, so I don't think it would be hard to beat. > > Alternatively, MinimalTuple is not very "minimal", and perhaps we > > can > > just make it better. > > Yeah. It tries to be compatible with HeapTuple, but perhaps we should > give up on that and pack it more tightly instead. From the perspective of HashAgg, that seems worthwhile. In my current patch set, depending on the grouping key and aggregates, the chunk size for the combination of the firstTuple with the additional data can be just above 32 bytes, which pushes the chunk size to 64 bytes. If we cut down the mintuple overhead a bit, more cases would fit in 32 bytes. And I think we can: 32 bytes seems reasonable to hold a lot of common cases where there's a small grouping key and a small pergroup state. Regards, Jeff Davis Attachments: [text/x-patch] v2-0001-ExecInitAgg-update-aggstate-numaggs-and-numtrans-.patch (1.5K, ../../[email protected]/2-v2-0001-ExecInitAgg-update-aggstate-numaggs-and-numtrans-.patch) download | inline diff: From 95a2becb251415af6f82d6df871b66e8a429768b Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 20 Nov 2024 12:33:11 -0800 Subject: [PATCH v2 1/8] ExecInitAgg: update aggstate->numaggs and ->numtrans earlier. Functions hash_agg_entry_size() and build_hash_tables() and are relying on those to make accurate estimates. --- src/backend/executor/nodeAgg.c | 11 ++--------- 1 file changed, 2 insertions(+), 9 deletions(-) diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 53ead77ece..300163538a 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -3379,8 +3379,8 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) max_aggno = Max(max_aggno, aggref->aggno); max_transno = Max(max_transno, aggref->aggtransno); } - numaggs = max_aggno + 1; - numtrans = max_transno + 1; + aggstate->numaggs = numaggs = max_aggno + 1; + aggstate->numtrans = numtrans = max_transno + 1; /* * For each phase, prepare grouping set data and fmgr lookup data for @@ -3943,13 +3943,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) ReleaseSysCache(aggTuple); } - /* - * Update aggstate->numaggs to be the number of unique aggregates found. - * Also set numstates to the number of unique transition states found. - */ - aggstate->numaggs = numaggs; - aggstate->numtrans = numtrans; - /* * Last, check whether any more aggregates got added onto the node while * we processed the expressions for the aggregate arguments (including not -- 2.34.1 [text/x-patch] v2-0002-Add-missing-typedefs.list-entry-for-AggStatePerGr.patch (1.2K, ../../[email protected]/3-v2-0002-Add-missing-typedefs.list-entry-for-AggStatePerGr.patch) download | inline diff: From 8e31098ffd338ad9e3d4797f11baed386b1bd714 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Thu, 21 Nov 2024 12:06:53 -0800 Subject: [PATCH v2 2/8] Add missing typedefs.list entry for AggStatePerGroupData. --- src/include/executor/nodeAgg.h | 2 +- src/tools/pgindent/typedefs.list | 1 + 2 files changed, 2 insertions(+), 1 deletion(-) diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h index 684779a6a3..db633fd672 100644 --- a/src/include/executor/nodeAgg.h +++ b/src/include/executor/nodeAgg.h @@ -264,7 +264,7 @@ typedef struct AggStatePerGroupData * NULL and not auto-replace it with a later input value. Only the first * non-NULL input will be auto-substituted. */ -} AggStatePerGroupData; +} AggStatePerGroupData; /* * AggStatePerPhaseData - per-grouping-set-phase state diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 08521d51a9..d52bdd2ff1 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -47,6 +47,7 @@ AggSplit AggState AggStatePerAgg AggStatePerGroup +AggStatePerGroupData AggStatePerHash AggStatePerPhase AggStatePerTrans -- 2.34.1 [text/x-patch] v2-0003-Remove-unused-TupleHashTableData-entrysize.patch (1.6K, ../../[email protected]/4-v2-0003-Remove-unused-TupleHashTableData-entrysize.patch) download | inline diff: From b372446f046736c40f7f10762623144d8a06aa9f Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 20 Nov 2024 12:59:16 -0800 Subject: [PATCH v2 3/8] Remove unused TupleHashTableData->entrysize. --- src/backend/executor/execGrouping.c | 1 - src/include/nodes/execnodes.h | 1 - 2 files changed, 2 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 774e4de882..467dbdc4cc 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -187,7 +187,6 @@ BuildTupleHashTableExt(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; - hashtable->entrysize = entrysize; hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_funcs = NULL; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 182a6956bb..0e6ec6d3a6 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -835,7 +835,6 @@ typedef struct TupleHashTableData Oid *tab_collations; /* collations for hash and comparison */ MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ - Size entrysize; /* actual size to make each hash entry */ TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ TupleTableSlot *inputslot; /* current input tuple's slot */ -- 2.34.1 [text/x-patch] v2-0004-nodeSetOp.c-missing-additionalsize-for-BuildTuple.patch (1.0K, ../../[email protected]/5-v2-0004-nodeSetOp.c-missing-additionalsize-for-BuildTuple.patch) download | inline diff: From c61d82728dd1454ffa62487e41d1c2bc9ee11564 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 20 Nov 2024 12:50:53 -0800 Subject: [PATCH v2 4/8] nodeSetOp.c: missing additionalsize for BuildTupleHashTable(). This can affect the calculations for 'nbuckets'. Also, furure work for HashAgg will rely on the correct 'additionalsize'. --- src/backend/executor/nodeSetOp.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index a8ac68b482..4e58a571b7 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -134,7 +134,7 @@ build_hash_table(SetOpState *setopstate) setopstate->hashfunctions, node->dupCollations, node->numGroups, - 0, + sizeof(SetOpStatePerGroupData), setopstate->ps.state->es_query_cxt, setopstate->tableContext, econtext->ecxt_per_tuple_memory, -- 2.34.1 [text/x-patch] v2-0005-TupleHashTable-store-additional-data-along-with-t.patch (12.0K, ../../[email protected]/6-v2-0005-TupleHashTable-store-additional-data-along-with-t.patch) download | inline diff: From 6a764dfb883a4153d22fc73901fc2ddbf80e2083 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Thu, 14 Nov 2024 11:47:51 -0800 Subject: [PATCH v2 5/8] TupleHashTable: store additional data along with tuple. Previously, the caller needed to allocate the memory and the TupleHashTable would store a pointer to it. That wastes space for the palloc overhead as well as the size of the pointer itself. Now, the TupleHashTable relies on the caller to correctly specify the additionalsize, and allocates that amount of space. The caller can then request a pointer into that space. --- src/backend/executor/execGrouping.c | 59 ++++++++++++++++++++++++++++- src/backend/executor/nodeAgg.c | 20 ++++------ src/backend/executor/nodeSetOp.c | 19 ++++------ src/backend/executor/nodeSubplan.c | 2 +- src/include/executor/executor.h | 3 ++ src/include/nodes/execnodes.h | 10 +---- 6 files changed, 78 insertions(+), 35 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 467dbdc4cc..d4a3b3280e 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -20,6 +20,13 @@ #include "miscadmin.h" #include "utils/lsyscache.h" +typedef struct TupleHashEntryData +{ + MinimalTuple firstTuple; /* copy of first tuple in this group */ + uint32 status; /* hash status */ + uint32 hash; /* hash value (cached) */ +} TupleHashEntryData; + static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, const MinimalTuple tuple); @@ -187,6 +194,7 @@ BuildTupleHashTableExt(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; + hashtable->additionalsize = additionalsize; hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_funcs = NULL; @@ -287,6 +295,15 @@ ResetTupleHashTable(TupleHashTable hashtable) tuplehash_reset(hashtable->hashtab); } +/* + * Return size of the hash bucket. Useful for estimating memory usage. + */ +size_t +TupleHashEntrySize(void) +{ + return sizeof(TupleHashEntryData); +} + /* * Find or create a hashtable entry for the tuple group containing the * given tuple. The tuple must be the same type as the hashtable entries. @@ -353,6 +370,26 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot) return hash; } +MinimalTuple +TupleHashEntryGetTuple(TupleHashEntry entry) +{ + return entry->firstTuple; +} + +/* + * Get a pointer into the additional space allocated for this entry. The + * amount of space available is the additionalsize specified to + * BuildTupleHashTable(). If additionalsize was specified as zero, no + * additional space is available and this function should not be called. + */ +void * +TupleHashEntryGetAdditional(TupleHashEntry entry) +{ + Assert(GetMemoryChunkSpace(entry->firstTuple) > MAXALIGN(entry->firstTuple->t_len)); + + return (char *) entry->firstTuple + MAXALIGN(entry->firstTuple->t_len); +} + /* * A variant of LookupTupleHashEntry for callers that have already computed * the hash value. @@ -513,13 +550,31 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, } else { + MinimalTuple firstTuple; + size_t totalsize; /* including alignment and additionalsize */ + /* created new entry */ *isnew = true; /* zero caller data */ - entry->additional = NULL; MemoryContextSwitchTo(hashtable->tablecxt); + /* Copy the first tuple into the table context */ - entry->firstTuple = ExecCopySlotMinimalTuple(slot); + firstTuple = ExecCopySlotMinimalTuple(slot); + + /* + * Allocate additional space right after the MinimalTuple of size + * additionalsize. The caller can get a pointer to this data with + * TupleHashEntryGetAdditional(), and store arbitrary data there. + * + * This avoids the need to store an extra pointer or allocate an + * additional chunk, which would waste memory. + */ + totalsize = MAXALIGN(firstTuple->t_len) + hashtable->additionalsize; + firstTuple = repalloc(firstTuple, totalsize); + memset((char *) firstTuple + firstTuple->t_len, 0, + totalsize - firstTuple->t_len); + + entry->firstTuple = firstTuple; } } else diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 300163538a..bb20006e9e 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -1713,7 +1713,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) transitionChunkSize = 0; return - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + tupleChunkSize + pergroupChunkSize + transitionChunkSize; @@ -1954,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) if (aggstate->hash_ngroups_current > 0) { aggstate->hashentrysize = - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + (hashkey_mem / (double) aggstate->hash_ngroups_current); } } @@ -2055,11 +2055,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable, if (aggstate->numtrans == 0) return; - pergroup = (AggStatePerGroup) - MemoryContextAlloc(hashtable->tablecxt, - sizeof(AggStatePerGroupData) * aggstate->numtrans); - - entry->additional = pergroup; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Initialize aggregates for new tuple group, lookup_hash_entries() @@ -2123,7 +2119,7 @@ lookup_hash_entries(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, hashtable, entry); - pergroup[setno] = entry->additional; + pergroup[setno] = TupleHashEntryGetAdditional(entry); } else { @@ -2681,7 +2677,7 @@ agg_refill_hash_table(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, perhash->hashtable, entry); - aggstate->hash_pergroup[batch->setno] = entry->additional; + aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(entry); advance_aggregates(aggstate); } else @@ -2773,7 +2769,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) ExprContext *econtext; AggStatePerAgg peragg; AggStatePerGroup pergroup; - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *firstSlot; TupleTableSlot *result; AggStatePerHash perhash; @@ -2845,7 +2841,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) * Transform representative tuple back into one with the right * columns. */ - ExecStoreMinimalTuple(entry->firstTuple, hashslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashslot, false); slot_getallattrs(hashslot); ExecClearTuple(firstSlot); @@ -2861,7 +2857,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) } ExecStoreVirtualTuple(firstSlot); - pergroup = (AggStatePerGroup) entry->additional; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Use the representative input tuple for any references to diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index 4e58a571b7..efbc455cee 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -364,7 +364,7 @@ setop_fill_hash_table(SetOpState *setopstate) { TupleTableSlot *outerslot; int flag; - TupleHashEntryData *entry; + TupleHashEntry entry; bool isnew; outerslot = ExecProcNode(outerPlan); @@ -385,15 +385,10 @@ setop_fill_hash_table(SetOpState *setopstate) /* If new tuple group, initialize counts */ if (isnew) - { - entry->additional = (SetOpStatePerGroup) - MemoryContextAlloc(setopstate->hashtable->tablecxt, - sizeof(SetOpStatePerGroupData)); - initialize_counts((SetOpStatePerGroup) entry->additional); - } + initialize_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry)); /* Advance the counts */ - advance_counts((SetOpStatePerGroup) entry->additional, flag); + advance_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry), flag); } else { @@ -406,7 +401,7 @@ setop_fill_hash_table(SetOpState *setopstate) /* Advance the counts if entry is already present */ if (entry) - advance_counts((SetOpStatePerGroup) entry->additional, flag); + advance_counts((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry), flag); } /* Must reset expression context after each hashtable lookup */ @@ -424,7 +419,7 @@ setop_fill_hash_table(SetOpState *setopstate) static TupleTableSlot * setop_retrieve_hash_table(SetOpState *setopstate) { - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *resultTupleSlot; /* @@ -454,12 +449,12 @@ setop_retrieve_hash_table(SetOpState *setopstate) * See if we should emit any copies of this tuple, and if so return * the first copy. */ - set_output_count(setopstate, (SetOpStatePerGroup) entry->additional); + set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(entry)); if (setopstate->numOutput > 0) { setopstate->numOutput--; - return ExecStoreMinimalTuple(entry->firstTuple, + return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), resultTupleSlot, false); } diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index 236222d72a..63aff24251 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -746,7 +746,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot, { CHECK_FOR_INTERRUPTS(); - ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false); if (!execTuplesUnequal(slot, hashtable->tableslot, numCols, keyColIdx, eqfunctions, diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index 69c3ebff00..d26968ecf7 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -154,9 +154,12 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, bool *isnew, uint32 *hash); extern uint32 TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot); +extern size_t TupleHashEntrySize(void); extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 hash); +extern MinimalTuple TupleHashEntryGetTuple(TupleHashEntry entry); +extern void *TupleHashEntryGetAdditional(TupleHashEntry entry); extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, ExprState *eqcomp, diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 0e6ec6d3a6..68b8b28803 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -806,17 +806,10 @@ typedef struct ExecAuxRowMark * tab_eq_func respectively. * ---------------------------------------------------------------- */ +typedef struct TupleHashEntryData TupleHashEntryData; typedef struct TupleHashEntryData *TupleHashEntry; typedef struct TupleHashTableData *TupleHashTable; -typedef struct TupleHashEntryData -{ - MinimalTuple firstTuple; /* copy of first tuple in this group */ - void *additional; /* user data */ - uint32 status; /* hash status */ - uint32 hash; /* hash value (cached) */ -} TupleHashEntryData; - /* define parameters necessary to generate the tuple hash table interface */ #define SH_PREFIX tuplehash #define SH_ELEMENT_TYPE TupleHashEntryData @@ -835,6 +828,7 @@ typedef struct TupleHashTableData Oid *tab_collations; /* collations for hash and comparison */ MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ + Size additionalsize; /* size of additional data */ TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ TupleTableSlot *inputslot; /* current input tuple's slot */ -- 2.34.1 [text/x-patch] v2-0006-simplehash-don-t-require-a-status-field.patch (7.1K, ../../[email protected]/7-v2-0006-simplehash-don-t-require-a-status-field.patch) download | inline diff: From 5c67d3943a9e02b933d8e18771b0fee797a8856f Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 12:21:04 -0800 Subject: [PATCH v2 6/8] simplehash: don't require a "status" field. Callers may define SH_ENTRY_IS_EMPTY(), SH_ENTRY_SET_EMPTY(), and SH_ENTRY_SET_IN_USE() as an alternative, which can allow for a more compact entry size. That reduces the memory overhead, especially when the hash table is sparse. --- src/include/lib/simplehash.h | 68 ++++++++++++++++++++++++------------ 1 file changed, 45 insertions(+), 23 deletions(-) diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h index 3e1b1f9461..213d8c372e 100644 --- a/src/include/lib/simplehash.h +++ b/src/include/lib/simplehash.h @@ -50,9 +50,18 @@ * - SH_HASH_KEY(table, key) - generate hash for the key * - SH_STORE_HASH - if defined the hash is stored in the elements * - SH_GET_HASH(tb, a) - return the field to store the hash in + * - SH_ENTRY_IS_EMPTY(tb, a) - return true if the entry is empty + * - SH_ENTRY_SET_EMPTY(tb, a) - set entry to empty + * - SH_ENTRY_SET_IN_USE(tb, a) - set entry to "in use" * * The element type is required to contain a "status" member that can store - * the range of values defined in the SH_STATUS enum. + * the range of values defined in the SH_STATUS enum. Alternatively, + * callers may define all of SH_ENTRY_IS_EMPTY, SH_ENTRY_SET_EMPTY, + * SH_ENTRY_SET_IN_USE to allow for a more compact entry size. For example, + * if the SH_ELEMENT_TYPE contains a pointer, the caller may decide that + * the entry is empty if the pointer is NULL and "in use" if the pointer is + * non-NULL. NB: if the entire entry is zero, then SH_ENTRY_IS_EMPTY() + * *must* evaluate to true. * * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because * the hash table implementation needs to compare hashes to move elements @@ -277,6 +286,18 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb); #define SH_GROW_MIN_FILLFACTOR 0.1 #endif +#ifndef SH_ENTRY_IS_EMPTY +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->status == SH_STATUS_EMPTY) +#endif + +#ifndef SH_ENTRY_SET_EMPTY +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->status = SH_STATUS_EMPTY; } while (0) +#endif + +#ifndef SH_ENTRY_SET_IN_USE +#define SH_ENTRY_SET_IN_USE(tb, a) do { (a)->status = SH_STATUS_IN_USE; } while (0) +#endif + #ifdef SH_STORE_HASH #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) #else @@ -540,7 +561,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) uint32 hash; uint32 optimal; - if (oldentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, oldentry)) { startelem = i; break; @@ -562,7 +583,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { SH_ELEMENT_TYPE *oldentry = &olddata[copyelem]; - if (oldentry->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, oldentry)) { uint32 hash; uint32 startelem2; @@ -578,7 +599,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { newentry = &newdata[curelem]; - if (newentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, newentry)) { break; } @@ -649,14 +670,14 @@ restart: SH_ELEMENT_TYPE *entry = &data[curelem]; /* any empty bucket can directly be used */ - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { tb->members++; entry->SH_KEY = key; #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -671,7 +692,7 @@ restart: if (SH_COMPARE_KEYS(tb, hash, key, entry)) { - Assert(entry->status == SH_STATUS_IN_USE); + Assert(!SH_ENTRY_IS_EMPTY(tb, entry)); *found = true; return entry; } @@ -695,7 +716,7 @@ restart: emptyelem = SH_NEXT(tb, emptyelem, startelem); emptyentry = &data[emptyelem]; - if (emptyentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, emptyentry)) { lastentry = emptyentry; break; @@ -744,7 +765,7 @@ restart: #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -806,13 +827,11 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { return NULL; } - Assert(entry->status == SH_STATUS_IN_USE); - if (SH_COMPARE_KEYS(tb, hash, key, entry)) return entry; @@ -864,10 +883,10 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) return false; - if (entry->status == SH_STATUS_IN_USE && + if (!SH_ENTRY_IS_EMPTY(tb, entry) && SH_COMPARE_KEYS(tb, hash, key, entry)) { SH_ELEMENT_TYPE *lastentry = entry; @@ -890,9 +909,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -902,7 +921,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -953,9 +972,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -965,7 +984,7 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -993,7 +1012,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) { SH_ELEMENT_TYPE *entry = &tb->data[i]; - if (entry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { startelem = i; break; @@ -1055,7 +1074,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask)) iter->done = true; - if (elem->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, elem)) { return elem; } @@ -1091,7 +1110,7 @@ SH_STAT(SH_TYPE * tb) elem = &tb->data[i]; - if (elem->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, elem)) continue; hash = SH_ENTRY_HASH(tb, elem); @@ -1149,6 +1168,9 @@ SH_STAT(SH_TYPE * tb) #undef SH_KEY #undef SH_ELEMENT_TYPE #undef SH_HASH_KEY +#undef SH_ENTRY_IS_EMPTY +#undef SH_ENTRY_SET_EMPTY +#undef SH_ENTRY_SET_IN_USE #undef SH_SCOPE #undef SH_DECLARE #undef SH_DEFINE -- 2.34.1 [text/x-patch] v2-0007-TupleHashTable-reduce-overhead-by-removing-status.patch (4.9K, ../../[email protected]/8-v2-0007-TupleHashTable-reduce-overhead-by-removing-status.patch) download | inline diff: From cdd20115968128571134eebe94e00a8b0adb18e0 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 13:03:32 -0800 Subject: [PATCH v2 7/8] TupleHashTable: reduce overhead by removing "status" field. Make use of new simplehash API introduced in commit 1234567890. Because NULL now means that the entry is empty, use a unique dummy pointer to refer to the inputslot instead. It also makes the code more readable. --- src/backend/executor/execGrouping.c | 33 +++++++++++++++++++---------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index d4a3b3280e..81ccd0e6d0 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -23,7 +23,6 @@ typedef struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ - uint32 status; /* hash status */ uint32 hash; /* hash value (cached) */ } TupleHashEntryData; @@ -34,6 +33,14 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta TupleTableSlot *slot, bool *isnew, uint32 hash); +/* + * Create a dummy pointer used to mean the input slot. The pointer will only + * be used for comparison and never dereferenced, and must not be equal to a + * valid pointer. Distinct from NULL, because NULL means that the hash entry + * itself is empty. + */ +const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1; + /* * Define parameters for tuple hash table code generation. The interface is * *also* declared in execnodes.h (to generate the types, which are externally @@ -48,6 +55,9 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta #define SH_SCOPE extern #define SH_STORE_HASH #define SH_GET_HASH(tb, a) a->hash +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->firstTuple == NULL) +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->firstTuple = NULL; } while (0) +#define SH_ENTRY_SET_IN_USE(tb, a) Assert((a)->firstTuple != NULL) #define SH_DEFINE #include "lib/simplehash.h" @@ -335,7 +345,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->in_hash_funcs = hashtable->tab_hash_funcs; hashtable->cur_eq_func = hashtable->tab_eq_func; - local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + local_hash = TupleHashTableHash_internal(hashtable->hashtab, FIRSTTUPLE_INPUTSLOT); entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash); if (hash != NULL) @@ -363,7 +373,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot) /* Need to run the hash functions in short-lived context */ oldContext = MemoryContextSwitchTo(hashtable->tempcxt); - hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + hash = TupleHashTableHash_internal(hashtable->hashtab, + FIRSTTUPLE_INPUTSLOT); MemoryContextSwitchTo(oldContext); @@ -444,7 +455,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->cur_eq_func = eqcomp; /* Search the hash table */ - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; entry = tuplehash_lookup(hashtable->hashtab, key); MemoryContextSwitchTo(oldContext); @@ -452,9 +463,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, } /* - * If tuple is NULL, use the input slot instead. This convention avoids the - * need to materialize virtual input tuples unless they actually need to get - * copied into the table. + * If tuple is FIRSTTUPLE_INPUTSLOT, use the input slot instead. This + * convention avoids the need to materialize virtual input tuples unless they + * actually need to get copied into the table. * * Also, the caller must select an appropriate memory context for running * the hash functions. (dynahash.c doesn't change CurrentMemoryContext.) @@ -471,7 +482,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb, FmgrInfo *hashfunctions; int i; - if (tuple == NULL) + if (tuple == FIRSTTUPLE_INPUTSLOT) { /* Process the current input tuple for the table */ slot = hashtable->inputslot; @@ -537,7 +548,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, bool found; MinimalTuple key; - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; if (isnew) { @@ -602,10 +613,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction * could be supported too, but is not currently required. */ - Assert(tuple1 != NULL); + Assert(tuple1 && tuple1 != FIRSTTUPLE_INPUTSLOT); slot1 = hashtable->tableslot; ExecStoreMinimalTuple(tuple1, slot1, false); - Assert(tuple2 == NULL); + Assert(tuple2 == FIRSTTUPLE_INPUTSLOT); slot2 = hashtable->inputslot; /* For crosstype comparisons, the inputslot must be first */ -- 2.34.1 [text/x-patch] v2-0008-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch (1.6K, ../../[email protected]/9-v2-0008-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch) download | inline diff: From 6a1ef8eb846d76c77958050e8aafc50d528064b1 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 18:52:06 -0800 Subject: [PATCH v2 8/8] Pack TupleHashEntryData and AggStatePerGroupData. --- src/backend/executor/execGrouping.c | 6 +++++- src/include/executor/nodeAgg.h | 6 +++++- 2 files changed, 10 insertions(+), 2 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 81ccd0e6d0..d28d420fd8 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -24,7 +24,11 @@ typedef struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ uint32 hash; /* hash value (cached) */ -} TupleHashEntryData; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif +TupleHashEntryData; static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h index db633fd672..c11b3a31fb 100644 --- a/src/include/executor/nodeAgg.h +++ b/src/include/executor/nodeAgg.h @@ -264,7 +264,11 @@ typedef struct AggStatePerGroupData * NULL and not auto-replace it with a later input value. Only the first * non-NULL input will be auto-substituted. */ -} AggStatePerGroupData; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif +AggStatePerGroupData; /* * AggStatePerPhaseData - per-grouping-set-phase state -- 2.34.1 ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-01-07 23:32 Jeff Davis <[email protected]> parent: Jeff Davis <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Jeff Davis @ 2025-01-07 23:32 UTC (permalink / raw) To: Heikki Linnakangas <[email protected]>; pgsql-hackers On Thu, 2024-11-21 at 12:37 -0800, Jeff Davis wrote: > > New patch series attached. I committed the earlier cleanup patches and rebased the rest. Attached. 0001 is not quite as clean as I'd like it to be; suggestions welcome. It does save a pointer per entry, though, which is substantial. Regards, Jeff Davis Attachments: [text/x-patch] v3-0001-TupleHashTable-store-additional-data-along-with-t.patch (12.1K, ../../[email protected]/2-v3-0001-TupleHashTable-store-additional-data-along-with-t.patch) download | inline diff: From 399f0e175c23f275b54efd4ec8eaa58b1a7d96c8 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Thu, 14 Nov 2024 11:47:51 -0800 Subject: [PATCH v3 1/4] TupleHashTable: store additional data along with tuple. Previously, the caller needed to allocate the memory and the TupleHashTable would store a pointer to it. That wastes space for the palloc overhead as well as the size of the pointer itself. Now, the TupleHashTable relies on the caller to correctly specify the additionalsize, and allocates that amount of space. The caller can then request a pointer into that space. --- src/backend/executor/execGrouping.c | 59 ++++++++++++++++++++++++++++- src/backend/executor/nodeAgg.c | 20 ++++------ src/backend/executor/nodeSetOp.c | 17 +++++---- src/backend/executor/nodeSubplan.c | 2 +- src/include/executor/executor.h | 3 ++ src/include/nodes/execnodes.h | 10 +---- 6 files changed, 80 insertions(+), 31 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 33b124fbb0a..29bd3162ad5 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -20,6 +20,13 @@ #include "miscadmin.h" #include "utils/lsyscache.h" +typedef struct TupleHashEntryData +{ + MinimalTuple firstTuple; /* copy of first tuple in this group */ + uint32 status; /* hash status */ + uint32 hash; /* hash value (cached) */ +} TupleHashEntryData; + static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, const MinimalTuple tuple); @@ -196,6 +203,7 @@ BuildTupleHashTable(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; + hashtable->additionalsize = additionalsize; hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_expr = NULL; @@ -273,6 +281,15 @@ ResetTupleHashTable(TupleHashTable hashtable) tuplehash_reset(hashtable->hashtab); } +/* + * Return size of the hash bucket. Useful for estimating memory usage. + */ +size_t +TupleHashEntrySize(void) +{ + return sizeof(TupleHashEntryData); +} + /* * Find or create a hashtable entry for the tuple group containing the * given tuple. The tuple must be the same type as the hashtable entries. @@ -339,6 +356,26 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot) return hash; } +MinimalTuple +TupleHashEntryGetTuple(TupleHashEntry entry) +{ + return entry->firstTuple; +} + +/* + * Get a pointer into the additional space allocated for this entry. The + * amount of space available is the additionalsize specified to + * BuildTupleHashTable(). If additionalsize was specified as zero, no + * additional space is available and this function should not be called. + */ +void * +TupleHashEntryGetAdditional(TupleHashEntry entry) +{ + Assert(GetMemoryChunkSpace(entry->firstTuple) > MAXALIGN(entry->firstTuple->t_len)); + + return (char *) entry->firstTuple + MAXALIGN(entry->firstTuple->t_len); +} + /* * A variant of LookupTupleHashEntry for callers that have already computed * the hash value. @@ -477,13 +514,31 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, } else { + MinimalTuple firstTuple; + size_t totalsize; /* including alignment and additionalsize */ + /* created new entry */ *isnew = true; /* zero caller data */ - entry->additional = NULL; MemoryContextSwitchTo(hashtable->tablecxt); + /* Copy the first tuple into the table context */ - entry->firstTuple = ExecCopySlotMinimalTuple(slot); + firstTuple = ExecCopySlotMinimalTuple(slot); + + /* + * Allocate additional space right after the MinimalTuple of size + * additionalsize. The caller can get a pointer to this data with + * TupleHashEntryGetAdditional(), and store arbitrary data there. + * + * This avoids the need to store an extra pointer or allocate an + * additional chunk, which would waste memory. + */ + totalsize = MAXALIGN(firstTuple->t_len) + hashtable->additionalsize; + firstTuple = repalloc(firstTuple, totalsize); + memset((char *) firstTuple + firstTuple->t_len, 0, + totalsize - firstTuple->t_len); + + entry->firstTuple = firstTuple; } } else diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 3005b5c0e3b..19640752967 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -1713,7 +1713,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) transitionChunkSize = 0; return - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + tupleChunkSize + pergroupChunkSize + transitionChunkSize; @@ -1954,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) if (aggstate->hash_ngroups_current > 0) { aggstate->hashentrysize = - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + (hashkey_mem / (double) aggstate->hash_ngroups_current); } } @@ -2055,11 +2055,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable, if (aggstate->numtrans == 0) return; - pergroup = (AggStatePerGroup) - MemoryContextAlloc(hashtable->tablecxt, - sizeof(AggStatePerGroupData) * aggstate->numtrans); - - entry->additional = pergroup; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Initialize aggregates for new tuple group, lookup_hash_entries() @@ -2123,7 +2119,7 @@ lookup_hash_entries(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, hashtable, entry); - pergroup[setno] = entry->additional; + pergroup[setno] = TupleHashEntryGetAdditional(entry); } else { @@ -2681,7 +2677,7 @@ agg_refill_hash_table(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, perhash->hashtable, entry); - aggstate->hash_pergroup[batch->setno] = entry->additional; + aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(entry); advance_aggregates(aggstate); } else @@ -2773,7 +2769,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) ExprContext *econtext; AggStatePerAgg peragg; AggStatePerGroup pergroup; - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *firstSlot; TupleTableSlot *result; AggStatePerHash perhash; @@ -2845,7 +2841,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) * Transform representative tuple back into one with the right * columns. */ - ExecStoreMinimalTuple(entry->firstTuple, hashslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashslot, false); slot_getallattrs(hashslot); ExecClearTuple(firstSlot); @@ -2861,7 +2857,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) } ExecStoreVirtualTuple(firstSlot); - pergroup = (AggStatePerGroup) entry->additional; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Use the representative input tuple for any references to diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index 5b7ff9c3748..2a50d56fc87 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -425,6 +425,7 @@ setop_fill_hash_table(SetOpState *setopstate) { TupleTableSlot *outerslot; TupleHashEntryData *entry; + SetOpStatePerGroup pergroup; bool isnew; outerslot = ExecProcNode(outerPlan); @@ -437,16 +438,16 @@ setop_fill_hash_table(SetOpState *setopstate) outerslot, &isnew, NULL); + pergroup = TupleHashEntryGetAdditional(entry); /* If new tuple group, initialize counts to zero */ if (isnew) { - entry->additional = (SetOpStatePerGroup) - MemoryContextAllocZero(setopstate->hashtable->tablecxt, - sizeof(SetOpStatePerGroupData)); + pergroup->numLeft = 0; + pergroup->numRight = 0; } /* Advance the counts */ - ((SetOpStatePerGroup) entry->additional)->numLeft++; + pergroup->numLeft++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -478,7 +479,7 @@ setop_fill_hash_table(SetOpState *setopstate) /* Advance the counts if entry is already present */ if (entry) - ((SetOpStatePerGroup) entry->additional)->numRight++; + ((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry))->numRight++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -496,7 +497,7 @@ setop_fill_hash_table(SetOpState *setopstate) static TupleTableSlot * setop_retrieve_hash_table(SetOpState *setopstate) { - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *resultTupleSlot; /* @@ -526,12 +527,12 @@ setop_retrieve_hash_table(SetOpState *setopstate) * See if we should emit any copies of this tuple, and if so return * the first copy. */ - set_output_count(setopstate, (SetOpStatePerGroup) entry->additional); + set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(entry)); if (setopstate->numOutput > 0) { setopstate->numOutput--; - return ExecStoreMinimalTuple(entry->firstTuple, + return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), resultTupleSlot, false); } diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index 49767ed6a52..f7f6fc2da0b 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -753,7 +753,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot, { CHECK_FOR_INTERRUPTS(); - ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false); if (!execTuplesUnequal(slot, hashtable->tableslot, numCols, keyColIdx, eqfunctions, diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index f8a8d03e533..a49c32072e3 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -148,9 +148,12 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, bool *isnew, uint32 *hash); extern uint32 TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot); +extern size_t TupleHashEntrySize(void); extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 hash); +extern MinimalTuple TupleHashEntryGetTuple(TupleHashEntry entry); +extern void *TupleHashEntryGetAdditional(TupleHashEntry entry); extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, ExprState *eqcomp, diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index b3f7aa299f5..7d5871d6fac 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -806,17 +806,10 @@ typedef struct ExecAuxRowMark * point to tab_hash_expr and tab_eq_func respectively. * ---------------------------------------------------------------- */ +typedef struct TupleHashEntryData TupleHashEntryData; typedef struct TupleHashEntryData *TupleHashEntry; typedef struct TupleHashTableData *TupleHashTable; -typedef struct TupleHashEntryData -{ - MinimalTuple firstTuple; /* copy of first tuple in this group */ - void *additional; /* user data */ - uint32 status; /* hash status */ - uint32 hash; /* hash value (cached) */ -} TupleHashEntryData; - /* define parameters necessary to generate the tuple hash table interface */ #define SH_PREFIX tuplehash #define SH_ELEMENT_TYPE TupleHashEntryData @@ -835,6 +828,7 @@ typedef struct TupleHashTableData Oid *tab_collations; /* collations for hash and comparison */ MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ + Size additionalsize; /* size of additional data */ TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ TupleTableSlot *inputslot; /* current input tuple's slot */ -- 2.34.1 [text/x-patch] v3-0002-simplehash-don-t-require-a-status-field.patch (7.1K, ../../[email protected]/3-v3-0002-simplehash-don-t-require-a-status-field.patch) download | inline diff: From 1d3ee5d04adf729cff93544cf9a9b768d47fa805 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 12:21:04 -0800 Subject: [PATCH v3 2/4] simplehash: don't require a "status" field. Callers may define SH_ENTRY_IS_EMPTY(), SH_ENTRY_SET_EMPTY(), and SH_ENTRY_SET_IN_USE() as an alternative, which can allow for a more compact entry size. That reduces the memory overhead, especially when the hash table is sparse. --- src/include/lib/simplehash.h | 68 ++++++++++++++++++++++++------------ 1 file changed, 45 insertions(+), 23 deletions(-) diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h index 327274c2340..0b9b0cdfde0 100644 --- a/src/include/lib/simplehash.h +++ b/src/include/lib/simplehash.h @@ -50,9 +50,18 @@ * - SH_HASH_KEY(table, key) - generate hash for the key * - SH_STORE_HASH - if defined the hash is stored in the elements * - SH_GET_HASH(tb, a) - return the field to store the hash in + * - SH_ENTRY_IS_EMPTY(tb, a) - return true if the entry is empty + * - SH_ENTRY_SET_EMPTY(tb, a) - set entry to empty + * - SH_ENTRY_SET_IN_USE(tb, a) - set entry to "in use" * * The element type is required to contain a "status" member that can store - * the range of values defined in the SH_STATUS enum. + * the range of values defined in the SH_STATUS enum. Alternatively, + * callers may define all of SH_ENTRY_IS_EMPTY, SH_ENTRY_SET_EMPTY, + * SH_ENTRY_SET_IN_USE to allow for a more compact entry size. For example, + * if the SH_ELEMENT_TYPE contains a pointer, the caller may decide that + * the entry is empty if the pointer is NULL and "in use" if the pointer is + * non-NULL. NB: if the entire entry is zero, then SH_ENTRY_IS_EMPTY() + * *must* evaluate to true. * * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because * the hash table implementation needs to compare hashes to move elements @@ -277,6 +286,18 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb); #define SH_GROW_MIN_FILLFACTOR 0.1 #endif +#ifndef SH_ENTRY_IS_EMPTY +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->status == SH_STATUS_EMPTY) +#endif + +#ifndef SH_ENTRY_SET_EMPTY +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->status = SH_STATUS_EMPTY; } while (0) +#endif + +#ifndef SH_ENTRY_SET_IN_USE +#define SH_ENTRY_SET_IN_USE(tb, a) do { (a)->status = SH_STATUS_IN_USE; } while (0) +#endif + #ifdef SH_STORE_HASH #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) #else @@ -540,7 +561,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) uint32 hash; uint32 optimal; - if (oldentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, oldentry)) { startelem = i; break; @@ -562,7 +583,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { SH_ELEMENT_TYPE *oldentry = &olddata[copyelem]; - if (oldentry->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, oldentry)) { uint32 hash; uint32 startelem2; @@ -578,7 +599,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { newentry = &newdata[curelem]; - if (newentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, newentry)) { break; } @@ -649,14 +670,14 @@ restart: SH_ELEMENT_TYPE *entry = &data[curelem]; /* any empty bucket can directly be used */ - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { tb->members++; entry->SH_KEY = key; #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -671,7 +692,7 @@ restart: if (SH_COMPARE_KEYS(tb, hash, key, entry)) { - Assert(entry->status == SH_STATUS_IN_USE); + Assert(!SH_ENTRY_IS_EMPTY(tb, entry)); *found = true; return entry; } @@ -695,7 +716,7 @@ restart: emptyelem = SH_NEXT(tb, emptyelem, startelem); emptyentry = &data[emptyelem]; - if (emptyentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, emptyentry)) { lastentry = emptyentry; break; @@ -744,7 +765,7 @@ restart: #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -806,13 +827,11 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { return NULL; } - Assert(entry->status == SH_STATUS_IN_USE); - if (SH_COMPARE_KEYS(tb, hash, key, entry)) return entry; @@ -864,10 +883,10 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) return false; - if (entry->status == SH_STATUS_IN_USE && + if (!SH_ENTRY_IS_EMPTY(tb, entry) && SH_COMPARE_KEYS(tb, hash, key, entry)) { SH_ELEMENT_TYPE *lastentry = entry; @@ -890,9 +909,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -902,7 +921,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -953,9 +972,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -965,7 +984,7 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -993,7 +1012,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) { SH_ELEMENT_TYPE *entry = &tb->data[i]; - if (entry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { startelem = i; break; @@ -1055,7 +1074,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask)) iter->done = true; - if (elem->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, elem)) { return elem; } @@ -1091,7 +1110,7 @@ SH_STAT(SH_TYPE * tb) elem = &tb->data[i]; - if (elem->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, elem)) continue; hash = SH_ENTRY_HASH(tb, elem); @@ -1149,6 +1168,9 @@ SH_STAT(SH_TYPE * tb) #undef SH_KEY #undef SH_ELEMENT_TYPE #undef SH_HASH_KEY +#undef SH_ENTRY_IS_EMPTY +#undef SH_ENTRY_SET_EMPTY +#undef SH_ENTRY_SET_IN_USE #undef SH_SCOPE #undef SH_DECLARE #undef SH_DEFINE -- 2.34.1 [text/x-patch] v3-0003-TupleHashTable-reduce-overhead-by-removing-status.patch (4.9K, ../../[email protected]/4-v3-0003-TupleHashTable-reduce-overhead-by-removing-status.patch) download | inline diff: From 393dfcb784bed5c162fe5c9d5b1bb287288312cf Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 13:03:32 -0800 Subject: [PATCH v3 3/4] TupleHashTable: reduce overhead by removing "status" field. Make use of new simplehash API introduced in commit 1234567890. Because NULL now means that the entry is empty, use a unique dummy pointer to refer to the inputslot instead. It also makes the code more readable. --- src/backend/executor/execGrouping.c | 33 +++++++++++++++++++---------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 29bd3162ad5..43165375946 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -23,7 +23,6 @@ typedef struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ - uint32 status; /* hash status */ uint32 hash; /* hash value (cached) */ } TupleHashEntryData; @@ -34,6 +33,14 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta TupleTableSlot *slot, bool *isnew, uint32 hash); +/* + * Create a dummy pointer used to mean the input slot. The pointer will only + * be used for comparison and never dereferenced, and must not be equal to a + * valid pointer. Distinct from NULL, because NULL means that the hash entry + * itself is empty. + */ +const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1; + /* * Define parameters for tuple hash table code generation. The interface is * *also* declared in execnodes.h (to generate the types, which are externally @@ -48,6 +55,9 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta #define SH_SCOPE extern #define SH_STORE_HASH #define SH_GET_HASH(tb, a) a->hash +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->firstTuple == NULL) +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->firstTuple = NULL; } while (0) +#define SH_ENTRY_SET_IN_USE(tb, a) Assert((a)->firstTuple != NULL) #define SH_DEFINE #include "lib/simplehash.h" @@ -321,7 +331,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->in_hash_expr = hashtable->tab_hash_expr; hashtable->cur_eq_func = hashtable->tab_eq_func; - local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + local_hash = TupleHashTableHash_internal(hashtable->hashtab, FIRSTTUPLE_INPUTSLOT); entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash); if (hash != NULL) @@ -349,7 +359,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot) /* Need to run the hash functions in short-lived context */ oldContext = MemoryContextSwitchTo(hashtable->tempcxt); - hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + hash = TupleHashTableHash_internal(hashtable->hashtab, + FIRSTTUPLE_INPUTSLOT); MemoryContextSwitchTo(oldContext); @@ -430,7 +441,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->cur_eq_func = eqcomp; /* Search the hash table */ - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; entry = tuplehash_lookup(hashtable->hashtab, key); MemoryContextSwitchTo(oldContext); @@ -438,9 +449,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, } /* - * If tuple is NULL, use the input slot instead. This convention avoids the - * need to materialize virtual input tuples unless they actually need to get - * copied into the table. + * If tuple is FIRSTTUPLE_INPUTSLOT, use the input slot instead. This + * convention avoids the need to materialize virtual input tuples unless they + * actually need to get copied into the table. * * Also, the caller must select an appropriate memory context for running * the hash functions. @@ -454,7 +465,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb, TupleTableSlot *slot; bool isnull; - if (tuple == NULL) + if (tuple == FIRSTTUPLE_INPUTSLOT) { /* Process the current input tuple for the table */ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot; @@ -501,7 +512,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, bool found; MinimalTuple key; - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; if (isnew) { @@ -566,10 +577,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction * could be supported too, but is not currently required. */ - Assert(tuple1 != NULL); + Assert(tuple1 && tuple1 != FIRSTTUPLE_INPUTSLOT); slot1 = hashtable->tableslot; ExecStoreMinimalTuple(tuple1, slot1, false); - Assert(tuple2 == NULL); + Assert(tuple2 == FIRSTTUPLE_INPUTSLOT); slot2 = hashtable->inputslot; /* For crosstype comparisons, the inputslot must be first */ -- 2.34.1 [text/x-patch] v3-0004-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch (1.6K, ../../[email protected]/5-v3-0004-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch) download | inline diff: From 160b8bee7c56305fc881dbe8187c13eebce7bf92 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 18:52:06 -0800 Subject: [PATCH v3 4/4] Pack TupleHashEntryData and AggStatePerGroupData. --- src/backend/executor/execGrouping.c | 6 +++++- src/include/executor/nodeAgg.h | 6 +++++- 2 files changed, 10 insertions(+), 2 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 43165375946..70f79abe86b 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -24,7 +24,11 @@ typedef struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ uint32 hash; /* hash value (cached) */ -} TupleHashEntryData; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif +TupleHashEntryData; static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h index 34b82d0f5d1..d519b2a57a4 100644 --- a/src/include/executor/nodeAgg.h +++ b/src/include/executor/nodeAgg.h @@ -264,7 +264,11 @@ typedef struct AggStatePerGroupData * NULL and not auto-replace it with a later input value. Only the first * non-NULL input will be auto-substituted. */ -} AggStatePerGroupData; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif +AggStatePerGroupData; /* * AggStatePerPhaseData - per-grouping-set-phase state -- 2.34.1 ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-01-12 01:54 David Rowley <[email protected]> parent: Jeff Davis <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: David Rowley @ 2025-01-12 01:54 UTC (permalink / raw) To: Jeff Davis <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; pgsql-hackers On Wed, 8 Jan 2025 at 12:32, Jeff Davis <[email protected]> wrote: > I committed the earlier cleanup patches and rebased the rest. Attached. While I do understand the desire to reduce Hash Agg's memory usage, has this really been through enough performance testing to be getting committed? I looked at the changes e0ece2a98 made to LookupTupleHashEntry_internal() and saw that you're doing repalloc() on the memory for the MinimalTuple just after the ExecCopySlotMinimalTuple() pallocs that memory. Some of these tuples might be quite big and I see your test case has a single INT4 GROUP BY, in which case the tuple is narrow. Remember this code is also used for set operations, where the tuples to compare might be quite wide. Since AllocSet rounds non-external chunks up to the next power-of-2, many repallocs() won't require a new chunk as there's likely to be space in the existing chunk, but I still seem to be able to measure this even when the memcpy() to populate the new chunk from the old one isn't needed. For example: create table a (a text not null); insert into a select repeat(md5(a::text),10) from generate_Series(1,1000) a; vacuum freeze analyze a; groupbya.sql: select a,count(*) from a group by a; psql -c "select pg_prewarm('a');" postgres > /dev/null && for i in {1..3}; do pgbench -n -f groupbya.sql -T 10 -M prepared postgres | grep tps; done Before (34c6e6524): tps = 1197.271513 (without initial connection time) tps = 1201.798286 (without initial connection time) tps = 1189.191958 (without initial connection time) After (e0ece2a98): tps = 1036.424401 (without initial connection time) tps = 1094.528577 (without initial connection time) tps = 1067.820026 (without initial connection time) 12% slower. Or if I craft the tuple so that the repalloc() needs to switch from a 256 byte to 512 byte chunk, I get: create table b (b text not null); insert into b select left(repeat(md5(b::text),8),236) from generate_Series(1,1000) b; vacuum freeze analyze b; groupbyb.sql: select b,count(*) from b group by b; psql -c "select pg_prewarm('b');" postgres && for i in {1..3}; do pgbench -n -f groupbyb.sql -T 10 -M prepared postgres | grep tps; done Before (34c6e6524) tps = 1258.542072 (without initial connection time) tps = 1260.423425 (without initial connection time) tps = 1244.229721 (without initial connection time) After (e0ece2a98): tps = 1088.773442 (without initial connection time) tps = 1068.253603 (without initial connection time) tps = 1121.814669 (without initial connection time) 14% slower. While I understand that this likely helps for when the hashtable size is larger than L3 and also when HashAgg is spilling to disk. I don't think that making that faster at the expense of slowing down workloads that fit into memory does not seem like a nice trade-off. I wonder if there's some other better way of doing this. Would it be worth having some function like ExecCopySlotMinimalTuple() that accepts an additional parameter so that the palloc allocates N more bytes at the end? Maybe it's worth hunting around to see if there's any other executor nodes that could benefit from that infrastructure. The other problem you've created by doing the repalloc() is that, if you still want the patch you posted in [1] then the repalloc() can't be done since bump context don't allow it. It would be quite nice if there were some way to have both of these optimisations in a way that didn't need any repalloc(). David [1] https://postgr.es/m/[email protected] ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-02-08 01:13 Jeff Davis <[email protected]> parent: David Rowley <[email protected]> 0 siblings, 1 reply; 11+ messages in thread From: Jeff Davis @ 2025-02-08 01:13 UTC (permalink / raw) To: David Rowley <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; pgsql-hackers On Sun, 2025-01-12 at 14:54 +1300, David Rowley wrote: > I wonder if there's some other better way of doing this. Would it be > worth having some function like ExecCopySlotMinimalTuple() that > accepts an additional parameter so that the palloc allocates N more > bytes at the end? Attached a new series that implements this idea. I also added in the change to use the Bump allocator for the tablecxt. In my simple test, the whole patch series reduces HashAgg memory usage by more than 40% and increases speed by a few percent. In your test, patch 0003 seemed to have a regression, but then 0007 made up for it (and maybe a hair faster). I investigated, but the profile was a bit misleading so I'm not clear on why 0003 came out slower. I can investigate further, but the primary purpose of this patch series is reducing memory usage, so as long as the overall series has no regression then I think it's fine. Regards, Jeff Davis Attachments: [text/x-patch] v6-0001-Create-accessor-functions-for-TupleHashEntry.patch (10.8K, ../../[email protected]/2-v6-0001-Create-accessor-functions-for-TupleHashEntry.patch) download | inline diff: From 9c01b9ac8e1f51d19f4a83521fe1ed98782701f2 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Mon, 13 Jan 2025 14:37:02 -0800 Subject: [PATCH v6 1/7] Create accessor functions for TupleHashEntry. --- src/backend/executor/execGrouping.c | 49 +++++++++++++++++++++++++++-- src/backend/executor/nodeAgg.c | 20 +++++------- src/backend/executor/nodeSetOp.c | 17 +++++----- src/backend/executor/nodeSubplan.c | 2 +- src/include/executor/executor.h | 3 ++ src/include/nodes/execnodes.h | 11 ++----- 6 files changed, 71 insertions(+), 31 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 33b124fbb0a..6763c35457c 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -20,6 +20,14 @@ #include "miscadmin.h" #include "utils/lsyscache.h" +struct TupleHashEntryData +{ + MinimalTuple firstTuple; /* copy of first tuple in this group */ + void *additional; /* user data */ + uint32 status; /* hash status */ + uint32 hash; /* hash value (cached) */ +}; + static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, const MinimalTuple tuple); @@ -196,6 +204,7 @@ BuildTupleHashTable(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; + hashtable->additionalsize = additionalsize; hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_expr = NULL; @@ -273,6 +282,37 @@ ResetTupleHashTable(TupleHashTable hashtable) tuplehash_reset(hashtable->hashtab); } +/* + * Return size of the hash bucket. Useful for estimating memory usage. + */ +size_t +TupleHashEntrySize(void) +{ + return sizeof(TupleHashEntryData); +} + +/* + * Return tuple from hash entry. + */ +MinimalTuple +TupleHashEntryGetTuple(TupleHashEntry entry) +{ + return entry->firstTuple; +} + +/* + * Get a pointer into the additional space allocated for this entry. The + * amount of space available is the additionalsize specified to + * BuildTupleHashTable(). If additionalsize was specified as zero, no + * additional space is available and this function should not be called. + */ +void * +TupleHashEntryGetAdditional(TupleHashEntry entry) +{ + Assert(entry->additional != NULL); + return entry->additional; +} + /* * Find or create a hashtable entry for the tuple group containing the * given tuple. The tuple must be the same type as the hashtable entries. @@ -479,11 +519,16 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, { /* created new entry */ *isnew = true; - /* zero caller data */ - entry->additional = NULL; + MemoryContextSwitchTo(hashtable->tablecxt); + /* Copy the first tuple into the table context */ entry->firstTuple = ExecCopySlotMinimalTuple(slot); + + if (hashtable->additionalsize > 0) + entry->additional = palloc0(hashtable->additionalsize); + else + entry->additional = NULL; } } else diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 3005b5c0e3b..19640752967 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -1713,7 +1713,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) transitionChunkSize = 0; return - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + tupleChunkSize + pergroupChunkSize + transitionChunkSize; @@ -1954,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) if (aggstate->hash_ngroups_current > 0) { aggstate->hashentrysize = - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + (hashkey_mem / (double) aggstate->hash_ngroups_current); } } @@ -2055,11 +2055,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable, if (aggstate->numtrans == 0) return; - pergroup = (AggStatePerGroup) - MemoryContextAlloc(hashtable->tablecxt, - sizeof(AggStatePerGroupData) * aggstate->numtrans); - - entry->additional = pergroup; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Initialize aggregates for new tuple group, lookup_hash_entries() @@ -2123,7 +2119,7 @@ lookup_hash_entries(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, hashtable, entry); - pergroup[setno] = entry->additional; + pergroup[setno] = TupleHashEntryGetAdditional(entry); } else { @@ -2681,7 +2677,7 @@ agg_refill_hash_table(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, perhash->hashtable, entry); - aggstate->hash_pergroup[batch->setno] = entry->additional; + aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(entry); advance_aggregates(aggstate); } else @@ -2773,7 +2769,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) ExprContext *econtext; AggStatePerAgg peragg; AggStatePerGroup pergroup; - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *firstSlot; TupleTableSlot *result; AggStatePerHash perhash; @@ -2845,7 +2841,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) * Transform representative tuple back into one with the right * columns. */ - ExecStoreMinimalTuple(entry->firstTuple, hashslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashslot, false); slot_getallattrs(hashslot); ExecClearTuple(firstSlot); @@ -2861,7 +2857,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) } ExecStoreVirtualTuple(firstSlot); - pergroup = (AggStatePerGroup) entry->additional; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(entry); /* * Use the representative input tuple for any references to diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index 5b7ff9c3748..2a50d56fc87 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -425,6 +425,7 @@ setop_fill_hash_table(SetOpState *setopstate) { TupleTableSlot *outerslot; TupleHashEntryData *entry; + SetOpStatePerGroup pergroup; bool isnew; outerslot = ExecProcNode(outerPlan); @@ -437,16 +438,16 @@ setop_fill_hash_table(SetOpState *setopstate) outerslot, &isnew, NULL); + pergroup = TupleHashEntryGetAdditional(entry); /* If new tuple group, initialize counts to zero */ if (isnew) { - entry->additional = (SetOpStatePerGroup) - MemoryContextAllocZero(setopstate->hashtable->tablecxt, - sizeof(SetOpStatePerGroupData)); + pergroup->numLeft = 0; + pergroup->numRight = 0; } /* Advance the counts */ - ((SetOpStatePerGroup) entry->additional)->numLeft++; + pergroup->numLeft++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -478,7 +479,7 @@ setop_fill_hash_table(SetOpState *setopstate) /* Advance the counts if entry is already present */ if (entry) - ((SetOpStatePerGroup) entry->additional)->numRight++; + ((SetOpStatePerGroup) TupleHashEntryGetAdditional(entry))->numRight++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -496,7 +497,7 @@ setop_fill_hash_table(SetOpState *setopstate) static TupleTableSlot * setop_retrieve_hash_table(SetOpState *setopstate) { - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *resultTupleSlot; /* @@ -526,12 +527,12 @@ setop_retrieve_hash_table(SetOpState *setopstate) * See if we should emit any copies of this tuple, and if so return * the first copy. */ - set_output_count(setopstate, (SetOpStatePerGroup) entry->additional); + set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(entry)); if (setopstate->numOutput > 0) { setopstate->numOutput--; - return ExecStoreMinimalTuple(entry->firstTuple, + return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), resultTupleSlot, false); } diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index 49767ed6a52..f7f6fc2da0b 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -753,7 +753,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot, { CHECK_FOR_INTERRUPTS(); - ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false); if (!execTuplesUnequal(slot, hashtable->tableslot, numCols, keyColIdx, eqfunctions, diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index 30e2a82346f..26d1877b1f3 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -148,6 +148,9 @@ extern TupleHashEntry LookupTupleHashEntry(TupleHashTable hashtable, bool *isnew, uint32 *hash); extern uint32 TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot); +extern size_t TupleHashEntrySize(void); +extern MinimalTuple TupleHashEntryGetTuple(TupleHashEntry entry); +extern void *TupleHashEntryGetAdditional(TupleHashEntry entry); extern TupleHashEntry LookupTupleHashEntryHash(TupleHashTable hashtable, TupleTableSlot *slot, bool *isnew, uint32 hash); diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index e2d1dc1e067..d46ce9b4996 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -831,17 +831,11 @@ typedef struct ExecAuxRowMark * point to tab_hash_expr and tab_eq_func respectively. * ---------------------------------------------------------------- */ +struct TupleHashEntryData; +typedef struct TupleHashEntryData TupleHashEntryData; typedef struct TupleHashEntryData *TupleHashEntry; typedef struct TupleHashTableData *TupleHashTable; -typedef struct TupleHashEntryData -{ - MinimalTuple firstTuple; /* copy of first tuple in this group */ - void *additional; /* user data */ - uint32 status; /* hash status */ - uint32 hash; /* hash value (cached) */ -} TupleHashEntryData; - /* define parameters necessary to generate the tuple hash table interface */ #define SH_PREFIX tuplehash #define SH_ELEMENT_TYPE TupleHashEntryData @@ -860,6 +854,7 @@ typedef struct TupleHashTableData Oid *tab_collations; /* collations for hash and comparison */ MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ + Size additionalsize; /* size of additional data */ TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ TupleTableSlot *inputslot; /* current input tuple's slot */ -- 2.34.1 [text/x-patch] v6-0002-Add-ExecCopySlotMinimalTupleExtra.patch (10.9K, ../../[email protected]/3-v6-0002-Add-ExecCopySlotMinimalTupleExtra.patch) download | inline diff: From 5db233e1fd02636b25399fa4db521fd464d3c504 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 7 Feb 2025 13:14:50 -0800 Subject: [PATCH v6 2/7] Add ExecCopySlotMinimalTupleExtra(). Allows an "extra" argument that allocates extra memory at the end of the MinimalTuple. This is important for callers that need to store additional data, but do not want to perform an additional allocation. --- src/backend/access/common/heaptuple.c | 43 ++++++++++++++++++---- src/backend/executor/execTuples.c | 24 ++++++------ src/backend/executor/nodeGatherMerge.c | 2 +- src/backend/utils/sort/tuplesortvariants.c | 2 +- src/backend/utils/sort/tuplestore.c | 6 +-- src/include/access/htup_details.h | 7 ++-- src/include/executor/tuptable.h | 19 +++++++++- 7 files changed, 74 insertions(+), 29 deletions(-) diff --git a/src/backend/access/common/heaptuple.c b/src/backend/access/common/heaptuple.c index b43cb9ccff4..36df2b31f2d 100644 --- a/src/backend/access/common/heaptuple.c +++ b/src/backend/access/common/heaptuple.c @@ -1452,7 +1452,8 @@ heap_freetuple(HeapTuple htup) MinimalTuple heap_form_minimal_tuple(TupleDesc tupleDescriptor, const Datum *values, - const bool *isnull) + const bool *isnull, + Size extra) { MinimalTuple tuple; /* return tuple */ Size len, @@ -1497,7 +1498,10 @@ heap_form_minimal_tuple(TupleDesc tupleDescriptor, /* * Allocate and zero the space needed. */ - tuple = (MinimalTuple) palloc0(len); + if (extra == 0) + tuple = (MinimalTuple) palloc0(len); + else + tuple = (MinimalTuple) palloc0(MAXALIGN(len) + extra); /* * And fill in the information. @@ -1533,12 +1537,23 @@ heap_free_minimal_tuple(MinimalTuple mtup) * The result is allocated in the current memory context. */ MinimalTuple -heap_copy_minimal_tuple(MinimalTuple mtup) +heap_copy_minimal_tuple(MinimalTuple mtup, Size extra) { MinimalTuple result; - result = (MinimalTuple) palloc(mtup->t_len); - memcpy(result, mtup, mtup->t_len); + if (extra == 0) + { + result = (MinimalTuple) palloc(mtup->t_len); + memcpy(result, mtup, mtup->t_len); + } + else + { + Size totalsize = MAXALIGN(mtup->t_len) + extra; + + result = (MinimalTuple) palloc(totalsize); + memcpy(result, mtup, mtup->t_len); + memset((char *) result + mtup->t_len, 0, totalsize - mtup->t_len); + } return result; } @@ -1574,15 +1589,27 @@ heap_tuple_from_minimal_tuple(MinimalTuple mtup) * The result is allocated in the current memory context. */ MinimalTuple -minimal_tuple_from_heap_tuple(HeapTuple htup) +minimal_tuple_from_heap_tuple(HeapTuple htup, Size extra) { MinimalTuple result; uint32 len; Assert(htup->t_len > MINIMAL_TUPLE_OFFSET); len = htup->t_len - MINIMAL_TUPLE_OFFSET; - result = (MinimalTuple) palloc(len); - memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len); + if (extra == 0) + { + result = (MinimalTuple) palloc(len); + memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len); + } + else + { + Size totalsize = MAXALIGN(len) + extra; + + result = (MinimalTuple) palloc(totalsize); + memcpy(result, (char *) htup->t_data + MINIMAL_TUPLE_OFFSET, len); + memset((char *) result + len, 0, totalsize - len); + } + result->t_len = len; return result; } diff --git a/src/backend/executor/execTuples.c b/src/backend/executor/execTuples.c index 7de490462d4..8e02d68824f 100644 --- a/src/backend/executor/execTuples.c +++ b/src/backend/executor/execTuples.c @@ -298,13 +298,14 @@ tts_virtual_copy_heap_tuple(TupleTableSlot *slot) } static MinimalTuple -tts_virtual_copy_minimal_tuple(TupleTableSlot *slot) +tts_virtual_copy_minimal_tuple(TupleTableSlot *slot, Size extra) { Assert(!TTS_EMPTY(slot)); return heap_form_minimal_tuple(slot->tts_tupleDescriptor, slot->tts_values, - slot->tts_isnull); + slot->tts_isnull, + extra); } @@ -472,14 +473,14 @@ tts_heap_copy_heap_tuple(TupleTableSlot *slot) } static MinimalTuple -tts_heap_copy_minimal_tuple(TupleTableSlot *slot) +tts_heap_copy_minimal_tuple(TupleTableSlot *slot, Size extra) { HeapTupleTableSlot *hslot = (HeapTupleTableSlot *) slot; if (!hslot->tuple) tts_heap_materialize(slot); - return minimal_tuple_from_heap_tuple(hslot->tuple); + return minimal_tuple_from_heap_tuple(hslot->tuple, extra); } static void @@ -607,7 +608,8 @@ tts_minimal_materialize(TupleTableSlot *slot) { mslot->mintuple = heap_form_minimal_tuple(slot->tts_tupleDescriptor, slot->tts_values, - slot->tts_isnull); + slot->tts_isnull, + 0); } else { @@ -617,7 +619,7 @@ tts_minimal_materialize(TupleTableSlot *slot) * TTS_FLAG_SHOULDFREE set). Copy the minimal tuple into the given * slot's memory context. */ - mslot->mintuple = heap_copy_minimal_tuple(mslot->mintuple); + mslot->mintuple = heap_copy_minimal_tuple(mslot->mintuple, 0); } slot->tts_flags |= TTS_FLAG_SHOULDFREE; @@ -666,14 +668,14 @@ tts_minimal_copy_heap_tuple(TupleTableSlot *slot) } static MinimalTuple -tts_minimal_copy_minimal_tuple(TupleTableSlot *slot) +tts_minimal_copy_minimal_tuple(TupleTableSlot *slot, Size extra) { MinimalTupleTableSlot *mslot = (MinimalTupleTableSlot *) slot; if (!mslot->mintuple) tts_minimal_materialize(slot); - return heap_copy_minimal_tuple(mslot->mintuple); + return heap_copy_minimal_tuple(mslot->mintuple, extra); } static void @@ -926,7 +928,7 @@ tts_buffer_heap_copy_heap_tuple(TupleTableSlot *slot) } static MinimalTuple -tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot) +tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot, Size extra) { BufferHeapTupleTableSlot *bslot = (BufferHeapTupleTableSlot *) slot; @@ -935,7 +937,7 @@ tts_buffer_heap_copy_minimal_tuple(TupleTableSlot *slot) if (!bslot->base.tuple) tts_buffer_heap_materialize(slot); - return minimal_tuple_from_heap_tuple(bslot->base.tuple); + return minimal_tuple_from_heap_tuple(bslot->base.tuple, extra); } static inline void @@ -1895,7 +1897,7 @@ ExecFetchSlotMinimalTuple(TupleTableSlot *slot, { if (shouldFree) *shouldFree = true; - return slot->tts_ops->copy_minimal_tuple(slot); + return slot->tts_ops->copy_minimal_tuple(slot, 0); } } diff --git a/src/backend/executor/nodeGatherMerge.c b/src/backend/executor/nodeGatherMerge.c index 01a6e3a8553..15f84597067 100644 --- a/src/backend/executor/nodeGatherMerge.c +++ b/src/backend/executor/nodeGatherMerge.c @@ -735,7 +735,7 @@ gm_readnext_tuple(GatherMergeState *gm_state, int nreader, bool nowait, * Since we'll be buffering these across multiple calls, we need to make a * copy. */ - return tup ? heap_copy_minimal_tuple(tup) : NULL; + return tup ? heap_copy_minimal_tuple(tup, 0) : NULL; } /* diff --git a/src/backend/utils/sort/tuplesortvariants.c b/src/backend/utils/sort/tuplesortvariants.c index 913c4ef455e..03bd3e0d2f1 100644 --- a/src/backend/utils/sort/tuplesortvariants.c +++ b/src/backend/utils/sort/tuplesortvariants.c @@ -892,7 +892,7 @@ tuplesort_gettupleslot(Tuplesortstate *state, bool forward, bool copy, *abbrev = stup.datum1; if (copy) - stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple); + stup.tuple = heap_copy_minimal_tuple((MinimalTuple) stup.tuple, 0); ExecStoreMinimalTuple((MinimalTuple) stup.tuple, slot, copy); return true; diff --git a/src/backend/utils/sort/tuplestore.c b/src/backend/utils/sort/tuplestore.c index d61b601053c..c9aecab8d66 100644 --- a/src/backend/utils/sort/tuplestore.c +++ b/src/backend/utils/sort/tuplestore.c @@ -787,7 +787,7 @@ tuplestore_putvalues(Tuplestorestate *state, TupleDesc tdesc, MinimalTuple tuple; MemoryContext oldcxt = MemoryContextSwitchTo(state->context); - tuple = heap_form_minimal_tuple(tdesc, values, isnull); + tuple = heap_form_minimal_tuple(tdesc, values, isnull, 0); USEMEM(state, GetMemoryChunkSpace(tuple)); tuplestore_puttuple_common(state, tuple); @@ -1139,7 +1139,7 @@ tuplestore_gettupleslot(Tuplestorestate *state, bool forward, { if (copy && !should_free) { - tuple = heap_copy_minimal_tuple(tuple); + tuple = heap_copy_minimal_tuple(tuple, 0); should_free = true; } ExecStoreMinimalTuple(tuple, slot, should_free); @@ -1590,7 +1590,7 @@ copytup_heap(Tuplestorestate *state, void *tup) { MinimalTuple tuple; - tuple = minimal_tuple_from_heap_tuple((HeapTuple) tup); + tuple = minimal_tuple_from_heap_tuple((HeapTuple) tup, 0); USEMEM(state, GetMemoryChunkSpace(tuple)); return tuple; } diff --git a/src/include/access/htup_details.h b/src/include/access/htup_details.h index 6cd4b95bfdb..aa957cf3b01 100644 --- a/src/include/access/htup_details.h +++ b/src/include/access/htup_details.h @@ -839,11 +839,12 @@ extern void heap_deform_tuple(HeapTuple tuple, TupleDesc tupleDesc, Datum *values, bool *isnull); extern void heap_freetuple(HeapTuple htup); extern MinimalTuple heap_form_minimal_tuple(TupleDesc tupleDescriptor, - const Datum *values, const bool *isnull); + const Datum *values, const bool *isnull, + Size extra); extern void heap_free_minimal_tuple(MinimalTuple mtup); -extern MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup); +extern MinimalTuple heap_copy_minimal_tuple(MinimalTuple mtup, Size extra); extern HeapTuple heap_tuple_from_minimal_tuple(MinimalTuple mtup); -extern MinimalTuple minimal_tuple_from_heap_tuple(HeapTuple htup); +extern MinimalTuple minimal_tuple_from_heap_tuple(HeapTuple htup, Size extra); extern size_t varsize_any(void *p); extern HeapTuple heap_expand_tuple(HeapTuple sourceTuple, TupleDesc tupleDesc); extern MinimalTuple minimal_expand_tuple(HeapTuple sourceTuple, TupleDesc tupleDesc); diff --git a/src/include/executor/tuptable.h b/src/include/executor/tuptable.h index a044d78e4d0..b901fef41f0 100644 --- a/src/include/executor/tuptable.h +++ b/src/include/executor/tuptable.h @@ -218,8 +218,12 @@ struct TupleTableSlotOps * meaningful "system columns" in the copy. The copy is not be "owned" by * the slot i.e. the caller has to take responsibility to free memory * consumed by the slot. + * + * The copy has "extra" bytes (maxaligned and zeroed) available at the + * end, which is useful so that some callers may store extra data along + * with the minimal tuple without the need for an additional allocation. */ - MinimalTuple (*copy_minimal_tuple) (TupleTableSlot *slot); + MinimalTuple (*copy_minimal_tuple) (TupleTableSlot *slot, Size extra); }; /* @@ -491,7 +495,18 @@ ExecCopySlotHeapTuple(TupleTableSlot *slot) static inline MinimalTuple ExecCopySlotMinimalTuple(TupleTableSlot *slot) { - return slot->tts_ops->copy_minimal_tuple(slot); + return slot->tts_ops->copy_minimal_tuple(slot, 0); +} + +/* + * ExecCopySlotMinimalTupleExtra - return MinimalTuple allocated in caller's + * context, with extra bytes (maxaligned and zeroed) after the end of the + * tuple. + */ +static inline MinimalTuple +ExecCopySlotMinimalTupleExtra(TupleTableSlot *slot, Size extra) +{ + return slot->tts_ops->copy_minimal_tuple(slot, extra); } /* -- 2.34.1 [text/x-patch] v6-0003-Store-additional-data-after-mintuple.patch (2.4K, ../../[email protected]/4-v6-0003-Store-additional-data-after-mintuple.patch) download | inline diff: From 449563fcdbaad76fa0841cdb82ce4e4f55d75163 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Tue, 14 Jan 2025 16:17:00 -0800 Subject: [PATCH v6 3/7] Store additional data after mintuple --- src/backend/executor/execGrouping.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 6763c35457c..90833216e3b 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -23,7 +23,6 @@ struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ - void *additional; /* user data */ uint32 status; /* hash status */ uint32 hash; /* hash value (cached) */ }; @@ -302,15 +301,16 @@ TupleHashEntryGetTuple(TupleHashEntry entry) /* * Get a pointer into the additional space allocated for this entry. The - * amount of space available is the additionalsize specified to - * BuildTupleHashTable(). If additionalsize was specified as zero, no + * memory will be maxaligned and zeroed. + * + * The amount of space available is the additionalsize requested in the call + * to BuildTupleHashTable(). If additionalsize was specified as zero, no * additional space is available and this function should not be called. */ void * TupleHashEntryGetAdditional(TupleHashEntry entry) { - Assert(entry->additional != NULL); - return entry->additional; + return (char *) entry->firstTuple + MAXALIGN(entry->firstTuple->t_len); } /* @@ -522,13 +522,17 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, MemoryContextSwitchTo(hashtable->tablecxt); - /* Copy the first tuple into the table context */ - entry->firstTuple = ExecCopySlotMinimalTuple(slot); - - if (hashtable->additionalsize > 0) - entry->additional = palloc0(hashtable->additionalsize); - else - entry->additional = NULL; + /* + * Copy the first tuple into the table context, and request + * additionalsize extra bytes at the end of the allocation. + * + * The caller can get a pointer to this data with + * TupleHashEntryGetAdditional(), and store arbitrary data there. + * This avoids the need to store an extra pointer or allocate an + * additional chunk, which would waste memory. + */ + entry->firstTuple = ExecCopySlotMinimalTupleExtra(slot, + hashtable->additionalsize); } } else -- 2.34.1 [text/x-patch] v6-0004-simplehash-don-t-require-a-status-field.patch (7.1K, ../../[email protected]/5-v6-0004-simplehash-don-t-require-a-status-field.patch) download | inline diff: From 2c2506f14adc51625b577ececef36b6feb159a22 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 12:21:04 -0800 Subject: [PATCH v6 4/7] simplehash: don't require a "status" field. Callers may define SH_ENTRY_IS_EMPTY(), SH_ENTRY_SET_EMPTY(), and SH_ENTRY_SET_IN_USE() as an alternative, which can allow for a more compact entry size. That reduces the memory overhead, especially when the hash table is sparse. --- src/include/lib/simplehash.h | 68 ++++++++++++++++++++++++------------ 1 file changed, 45 insertions(+), 23 deletions(-) diff --git a/src/include/lib/simplehash.h b/src/include/lib/simplehash.h index 327274c2340..0b9b0cdfde0 100644 --- a/src/include/lib/simplehash.h +++ b/src/include/lib/simplehash.h @@ -50,9 +50,18 @@ * - SH_HASH_KEY(table, key) - generate hash for the key * - SH_STORE_HASH - if defined the hash is stored in the elements * - SH_GET_HASH(tb, a) - return the field to store the hash in + * - SH_ENTRY_IS_EMPTY(tb, a) - return true if the entry is empty + * - SH_ENTRY_SET_EMPTY(tb, a) - set entry to empty + * - SH_ENTRY_SET_IN_USE(tb, a) - set entry to "in use" * * The element type is required to contain a "status" member that can store - * the range of values defined in the SH_STATUS enum. + * the range of values defined in the SH_STATUS enum. Alternatively, + * callers may define all of SH_ENTRY_IS_EMPTY, SH_ENTRY_SET_EMPTY, + * SH_ENTRY_SET_IN_USE to allow for a more compact entry size. For example, + * if the SH_ELEMENT_TYPE contains a pointer, the caller may decide that + * the entry is empty if the pointer is NULL and "in use" if the pointer is + * non-NULL. NB: if the entire entry is zero, then SH_ENTRY_IS_EMPTY() + * *must* evaluate to true. * * While SH_STORE_HASH (and subsequently SH_GET_HASH) are optional, because * the hash table implementation needs to compare hashes to move elements @@ -277,6 +286,18 @@ SH_SCOPE void SH_STAT(SH_TYPE * tb); #define SH_GROW_MIN_FILLFACTOR 0.1 #endif +#ifndef SH_ENTRY_IS_EMPTY +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->status == SH_STATUS_EMPTY) +#endif + +#ifndef SH_ENTRY_SET_EMPTY +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->status = SH_STATUS_EMPTY; } while (0) +#endif + +#ifndef SH_ENTRY_SET_IN_USE +#define SH_ENTRY_SET_IN_USE(tb, a) do { (a)->status = SH_STATUS_IN_USE; } while (0) +#endif + #ifdef SH_STORE_HASH #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey)) #else @@ -540,7 +561,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) uint32 hash; uint32 optimal; - if (oldentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, oldentry)) { startelem = i; break; @@ -562,7 +583,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { SH_ELEMENT_TYPE *oldentry = &olddata[copyelem]; - if (oldentry->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, oldentry)) { uint32 hash; uint32 startelem2; @@ -578,7 +599,7 @@ SH_GROW(SH_TYPE * tb, uint64 newsize) { newentry = &newdata[curelem]; - if (newentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, newentry)) { break; } @@ -649,14 +670,14 @@ restart: SH_ELEMENT_TYPE *entry = &data[curelem]; /* any empty bucket can directly be used */ - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { tb->members++; entry->SH_KEY = key; #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -671,7 +692,7 @@ restart: if (SH_COMPARE_KEYS(tb, hash, key, entry)) { - Assert(entry->status == SH_STATUS_IN_USE); + Assert(!SH_ENTRY_IS_EMPTY(tb, entry)); *found = true; return entry; } @@ -695,7 +716,7 @@ restart: emptyelem = SH_NEXT(tb, emptyelem, startelem); emptyentry = &data[emptyelem]; - if (emptyentry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, emptyentry)) { lastentry = emptyentry; break; @@ -744,7 +765,7 @@ restart: #ifdef SH_STORE_HASH SH_GET_HASH(tb, entry) = hash; #endif - entry->status = SH_STATUS_IN_USE; + SH_ENTRY_SET_IN_USE(tb, entry); *found = false; return entry; } @@ -806,13 +827,11 @@ SH_LOOKUP_HASH_INTERNAL(SH_TYPE * tb, SH_KEY_TYPE key, uint32 hash) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { return NULL; } - Assert(entry->status == SH_STATUS_IN_USE); - if (SH_COMPARE_KEYS(tb, hash, key, entry)) return entry; @@ -864,10 +883,10 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) { SH_ELEMENT_TYPE *entry = &tb->data[curelem]; - if (entry->status == SH_STATUS_EMPTY) + if (SH_ENTRY_IS_EMPTY(tb, entry)) return false; - if (entry->status == SH_STATUS_IN_USE && + if (!SH_ENTRY_IS_EMPTY(tb, entry) && SH_COMPARE_KEYS(tb, hash, key, entry)) { SH_ELEMENT_TYPE *lastentry = entry; @@ -890,9 +909,9 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -902,7 +921,7 @@ SH_DELETE(SH_TYPE * tb, SH_KEY_TYPE key) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -953,9 +972,9 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) curelem = SH_NEXT(tb, curelem, startelem); curentry = &tb->data[curelem]; - if (curentry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, curentry)) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -965,7 +984,7 @@ SH_DELETE_ITEM(SH_TYPE * tb, SH_ELEMENT_TYPE * entry) /* current is at optimal position, done */ if (curoptimal == curelem) { - lastentry->status = SH_STATUS_EMPTY; + SH_ENTRY_SET_EMPTY(tb, lastentry); break; } @@ -993,7 +1012,7 @@ SH_START_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) { SH_ELEMENT_TYPE *entry = &tb->data[i]; - if (entry->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, entry)) { startelem = i; break; @@ -1055,7 +1074,7 @@ SH_ITERATE(SH_TYPE * tb, SH_ITERATOR * iter) if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask)) iter->done = true; - if (elem->status == SH_STATUS_IN_USE) + if (!SH_ENTRY_IS_EMPTY(tb, elem)) { return elem; } @@ -1091,7 +1110,7 @@ SH_STAT(SH_TYPE * tb) elem = &tb->data[i]; - if (elem->status != SH_STATUS_IN_USE) + if (SH_ENTRY_IS_EMPTY(tb, elem)) continue; hash = SH_ENTRY_HASH(tb, elem); @@ -1149,6 +1168,9 @@ SH_STAT(SH_TYPE * tb) #undef SH_KEY #undef SH_ELEMENT_TYPE #undef SH_HASH_KEY +#undef SH_ENTRY_IS_EMPTY +#undef SH_ENTRY_SET_EMPTY +#undef SH_ENTRY_SET_IN_USE #undef SH_SCOPE #undef SH_DECLARE #undef SH_DEFINE -- 2.34.1 [text/x-patch] v6-0005-TupleHashTable-reduce-overhead-by-removing-status.patch (4.9K, ../../[email protected]/6-v6-0005-TupleHashTable-reduce-overhead-by-removing-status.patch) download | inline diff: From c7bcdc8493137b15b3b8f7b9f9bbfe8b5e640e9e Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 13:03:32 -0800 Subject: [PATCH v6 5/7] TupleHashTable: reduce overhead by removing "status" field. Make use of new simplehash API introduced in commit 1234567890. Because NULL now means that the entry is empty, use a unique dummy pointer to refer to the inputslot instead. It also makes the code more readable. --- src/backend/executor/execGrouping.c | 33 +++++++++++++++++++---------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 90833216e3b..7f41b03324f 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -23,7 +23,6 @@ struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ - uint32 status; /* hash status */ uint32 hash; /* hash value (cached) */ }; @@ -34,6 +33,14 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta TupleTableSlot *slot, bool *isnew, uint32 hash); +/* + * Create a dummy pointer used to mean the input slot. The pointer will only + * be used for comparison and never dereferenced, and must not be equal to a + * valid pointer. Distinct from NULL, because NULL means that the hash entry + * itself is empty. + */ +const static MinimalTuple FIRSTTUPLE_INPUTSLOT = (MinimalTuple) 0x1; + /* * Define parameters for tuple hash table code generation. The interface is * *also* declared in execnodes.h (to generate the types, which are externally @@ -48,6 +55,9 @@ static inline TupleHashEntry LookupTupleHashEntry_internal(TupleHashTable hashta #define SH_SCOPE extern #define SH_STORE_HASH #define SH_GET_HASH(tb, a) a->hash +#define SH_ENTRY_IS_EMPTY(tb, a) ((a)->firstTuple == NULL) +#define SH_ENTRY_SET_EMPTY(tb, a) do { (a)->firstTuple = NULL; } while (0) +#define SH_ENTRY_SET_IN_USE(tb, a) Assert((a)->firstTuple != NULL) #define SH_DEFINE #include "lib/simplehash.h" @@ -344,7 +354,7 @@ LookupTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->in_hash_expr = hashtable->tab_hash_expr; hashtable->cur_eq_func = hashtable->tab_eq_func; - local_hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + local_hash = TupleHashTableHash_internal(hashtable->hashtab, FIRSTTUPLE_INPUTSLOT); entry = LookupTupleHashEntry_internal(hashtable, slot, isnew, local_hash); if (hash != NULL) @@ -372,7 +382,8 @@ TupleHashTableHash(TupleHashTable hashtable, TupleTableSlot *slot) /* Need to run the hash functions in short-lived context */ oldContext = MemoryContextSwitchTo(hashtable->tempcxt); - hash = TupleHashTableHash_internal(hashtable->hashtab, NULL); + hash = TupleHashTableHash_internal(hashtable->hashtab, + FIRSTTUPLE_INPUTSLOT); MemoryContextSwitchTo(oldContext); @@ -433,7 +444,7 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, hashtable->cur_eq_func = eqcomp; /* Search the hash table */ - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; entry = tuplehash_lookup(hashtable->hashtab, key); MemoryContextSwitchTo(oldContext); @@ -441,9 +452,9 @@ FindTupleHashEntry(TupleHashTable hashtable, TupleTableSlot *slot, } /* - * If tuple is NULL, use the input slot instead. This convention avoids the - * need to materialize virtual input tuples unless they actually need to get - * copied into the table. + * If tuple is FIRSTTUPLE_INPUTSLOT, use the input slot instead. This + * convention avoids the need to materialize virtual input tuples unless they + * actually need to get copied into the table. * * Also, the caller must select an appropriate memory context for running * the hash functions. @@ -457,7 +468,7 @@ TupleHashTableHash_internal(struct tuplehash_hash *tb, TupleTableSlot *slot; bool isnull; - if (tuple == NULL) + if (tuple == FIRSTTUPLE_INPUTSLOT) { /* Process the current input tuple for the table */ hashtable->exprcontext->ecxt_innertuple = hashtable->inputslot; @@ -504,7 +515,7 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, bool found; MinimalTuple key; - key = NULL; /* flag to reference inputslot */ + key = FIRSTTUPLE_INPUTSLOT; if (isnew) { @@ -560,10 +571,10 @@ TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const * LookupTupleHashEntry's dummy TupleHashEntryData. The other direction * could be supported too, but is not currently required. */ - Assert(tuple1 != NULL); + Assert(tuple1 && tuple1 != FIRSTTUPLE_INPUTSLOT); slot1 = hashtable->tableslot; ExecStoreMinimalTuple(tuple1, slot1, false); - Assert(tuple2 == NULL); + Assert(tuple2 == FIRSTTUPLE_INPUTSLOT); slot2 = hashtable->inputslot; /* For crosstype comparisons, the inputslot must be first */ -- 2.34.1 [text/x-patch] v6-0006-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch (1.5K, ../../[email protected]/7-v6-0006-Pack-TupleHashEntryData-and-AggStatePerGroupData.patch) download | inline diff: From 64b049cd850c2e9c60574def618967eb7f0c0343 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Fri, 15 Nov 2024 18:52:06 -0800 Subject: [PATCH v6 6/7] Pack TupleHashEntryData and AggStatePerGroupData. --- src/backend/executor/execGrouping.c | 6 +++++- src/include/executor/nodeAgg.h | 6 +++++- 2 files changed, 10 insertions(+), 2 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 7f41b03324f..cea28ce4bd7 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -24,7 +24,11 @@ struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ uint32 hash; /* hash value (cached) */ -}; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif + ; static int TupleHashTableMatch(struct tuplehash_hash *tb, const MinimalTuple tuple1, const MinimalTuple tuple2); static inline uint32 TupleHashTableHash_internal(struct tuplehash_hash *tb, diff --git a/src/include/executor/nodeAgg.h b/src/include/executor/nodeAgg.h index 34b82d0f5d1..cb756a912a6 100644 --- a/src/include/executor/nodeAgg.h +++ b/src/include/executor/nodeAgg.h @@ -264,7 +264,11 @@ typedef struct AggStatePerGroupData * NULL and not auto-replace it with a later input value. Only the first * non-NULL input will be auto-substituted. */ -} AggStatePerGroupData; +} +#ifdef pg_attribute_packed + pg_attribute_packed() +#endif +AggStatePerGroupData; /* * AggStatePerPhaseData - per-grouping-set-phase state -- 2.34.1 [text/x-patch] v6-0007-HashAgg-use-Bump-allocator-for-hash-TupleHashTabl.patch (10.9K, ../../[email protected]/8-v6-0007-HashAgg-use-Bump-allocator-for-hash-TupleHashTabl.patch) download | inline diff: From 7e324de479998b8b773185db946e8788bc6a9201 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 8 Jan 2025 11:46:35 -0800 Subject: [PATCH v6 7/7] HashAgg: use Bump allocator for hash TupleHashTable entries. The entries aren't freed until the entire hash table is destroyed, so use the Bump allocator to improve allocation speed, avoid wasting space on the chunk header, and avoid wasting space due to the power-of-two allocations. Discussion: https://postgr.es/m/CAApHDvqv1aNB4cM36FzRwivXrEvBO_LsG_eQ3nqDXTjECaatOQ@mail.gmail.com Reviewed-by: David Rowley --- src/backend/executor/nodeAgg.c | 110 +++++++++++++++++---- src/include/nodes/execnodes.h | 5 +- src/test/regress/expected/groupingsets.out | 2 +- src/test/regress/sql/groupingsets.sql | 2 +- 4 files changed, 97 insertions(+), 22 deletions(-) diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 19640752967..d5bed9ec48e 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -405,6 +405,7 @@ static void build_hash_tables(AggState *aggstate); static void build_hash_table(AggState *aggstate, int setno, long nbuckets); static void hashagg_recompile_expressions(AggState *aggstate, bool minslot, bool nullcheck); +static void hash_create_memory(AggState *aggstate); static long hash_choose_num_buckets(double hashentrysize, long ngroups, Size memory); static int hash_choose_num_partitions(double input_groups, @@ -1503,7 +1504,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets) { AggStatePerHash perhash = &aggstate->perhash[setno]; MemoryContext metacxt = aggstate->hash_metacxt; - MemoryContext hashcxt = aggstate->hashcontext->ecxt_per_tuple_memory; + MemoryContext tablecxt = aggstate->hash_tablecxt; MemoryContext tmpcxt = aggstate->tmpcontext->ecxt_per_tuple_memory; Size additionalsize; @@ -1529,7 +1530,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets) nbuckets, additionalsize, metacxt, - hashcxt, + tablecxt, tmpcxt, DO_AGGSPLIT_SKIPFINAL(aggstate->aggsplit)); } @@ -1700,15 +1701,24 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) tupleWidth); Size pergroupSize = numTrans * sizeof(AggStatePerGroupData); - tupleChunkSize = CHUNKHDRSZ + tupleSize; - - if (pergroupSize > 0) - pergroupChunkSize = CHUNKHDRSZ + pergroupSize; - else - pergroupChunkSize = 0; + /* + * Entries use the Bump allocator, so the chunk sizes are the same as the + * requested sizes. + */ + tupleChunkSize = tupleSize; + pergroupChunkSize = pergroupSize; + /* + * Transition values use AllocSet, which has a chunk header and also uses + * power-of-two allocations. + */ if (transitionSpace > 0) - transitionChunkSize = CHUNKHDRSZ + transitionSpace; + { + Size pow2 = (Size) 1 << my_log2(transitionSpace); + + /* use Max to protect against overflow */ + transitionChunkSize = Max(CHUNKHDRSZ + pow2, transitionSpace); + } else transitionChunkSize = 0; @@ -1858,15 +1868,18 @@ hash_agg_check_limits(AggState *aggstate) uint64 ngroups = aggstate->hash_ngroups_current; Size meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true); - Size hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, - true); + Size entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt, + true); + Size tval_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, + true); + Size total_mem = meta_mem + entry_mem + tval_mem; /* * Don't spill unless there's at least one group in the hash table so we * can be sure to make progress even in edge cases. */ if (aggstate->hash_ngroups_current > 0 && - (meta_mem + hashkey_mem > aggstate->hash_mem_limit || + (total_mem > aggstate->hash_mem_limit || ngroups > aggstate->hash_ngroups_limit)) { hash_agg_enter_spill_mode(aggstate); @@ -1917,6 +1930,7 @@ static void hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) { Size meta_mem; + Size entry_mem; Size hashkey_mem; Size buffer_mem; Size total_mem; @@ -1928,7 +1942,10 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) /* memory for the hash table itself */ meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true); - /* memory for the group keys and transition states */ + /* memory for hash entries */ + entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt, true); + + /* memory for byref transition states */ hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, true); /* memory for read/write tape buffers, if spilled */ @@ -1937,7 +1954,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) buffer_mem += HASHAGG_READ_BUFFER_SIZE; /* update peak mem */ - total_mem = meta_mem + hashkey_mem + buffer_mem; + total_mem = meta_mem + entry_mem + hashkey_mem + buffer_mem; if (total_mem > aggstate->hash_mem_peak) aggstate->hash_mem_peak = total_mem; @@ -1959,6 +1976,58 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) } } +/* + * Create memory contexts used for hash aggregation. + */ +static void +hash_create_memory(AggState *aggstate) +{ + Size minContextSize = ALLOCSET_DEFAULT_MINSIZE; + Size initBlockSize = ALLOCSET_DEFAULT_INITSIZE; + Size maxBlockSize = ALLOCSET_DEFAULT_MAXSIZE; + + /* + * The hashcontext's per-tuple memory will be used for byref transition + * values and returned by AggCheckCallContext(). + */ + aggstate->hashcontext = CreateWorkExprContext(aggstate->ss.ps.state); + + /* + * The meta context will be used for the bucket array of + * TupleHashEntryData (or arrays, in the case of grouping sets). As the + * hash table grows, the bucket array will double in size and the old one + * will be freed, so an AllocSet is appropriate. For large bucket arrays, + * the large allocation path will be used, so it's not worth worrying + * about wasting space due to power-of-two allocations. + */ + aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt, + "HashAgg meta context", + ALLOCSET_DEFAULT_SIZES); + + /* + * The hash entries themselves, which include the grouping key + * (firstTuple) and pergroup data, are stored in the table context. The + * bump allocator can be used because the entries are not freed until the + * entire hash table is reset. The bump allocator is faster for + * allocations and avoids wasting space on the chunk header or + * power-of-two allocations. + * + * Like CreateWorkExprContext(), use smaller sizings for smaller work_mem, + * to avoid large jumps in memory usage. + */ + while (16 * maxBlockSize > work_mem * 1024L) + maxBlockSize >>= 1; + + if (maxBlockSize < ALLOCSET_DEFAULT_INITSIZE) + maxBlockSize = ALLOCSET_DEFAULT_INITSIZE; + + aggstate->hash_tablecxt = BumpContextCreate(aggstate->ss.ps.state->es_query_cxt, + "HashAgg table context", + minContextSize, initBlockSize, + maxBlockSize); + +} + /* * Choose a reasonable number of buckets for the initial hash table size. */ @@ -2618,6 +2687,7 @@ agg_refill_hash_table(AggState *aggstate) /* free memory and reset hash tables */ ReScanExprContext(aggstate->hashcontext); + MemoryContextReset(aggstate->hash_tablecxt); for (int setno = 0; setno < aggstate->num_hashes; setno++) ResetTupleHashTable(aggstate->perhash[setno].hashtable); @@ -3285,7 +3355,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) } if (use_hashing) - aggstate->hashcontext = CreateWorkExprContext(estate); + hash_create_memory(aggstate); ExecAssignExprContext(estate, &aggstate->ss.ps); @@ -3580,9 +3650,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) Plan *outerplan = outerPlan(node); uint64 totalGroups = 0; - aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt, - "HashAgg meta context", - ALLOCSET_DEFAULT_SIZES); aggstate->hash_spill_rslot = ExecInitExtraTupleSlot(estate, scanDesc, &TTSOpsMinimalTuple); aggstate->hash_spill_wslot = ExecInitExtraTupleSlot(estate, scanDesc, @@ -4327,6 +4394,12 @@ ExecEndAgg(AggState *node) MemoryContextDelete(node->hash_metacxt); node->hash_metacxt = NULL; } + if (node->hash_tablecxt != NULL) + { + MemoryContextDelete(node->hash_tablecxt); + node->hash_tablecxt = NULL; + } + for (transno = 0; transno < node->numtrans; transno++) { @@ -4443,6 +4516,7 @@ ExecReScanAgg(AggState *node) node->hash_ngroups_current = 0; ReScanExprContext(node->hashcontext); + MemoryContextReset(node->hash_tablecxt); /* Rebuild an empty hash table */ build_hash_tables(node); node->table_filled = false; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index d46ce9b4996..999d06aa570 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2558,7 +2558,8 @@ typedef struct AggState /* these fields are used in AGG_HASHED and AGG_MIXED modes: */ bool table_filled; /* hash table filled yet? */ int num_hashes; - MemoryContext hash_metacxt; /* memory for hash table itself */ + MemoryContext hash_metacxt; /* memory for hash table bucket array */ + MemoryContext hash_tablecxt; /* memory for hash table entries */ struct LogicalTapeSet *hash_tapeset; /* tape set for hash spill tapes */ struct HashAggSpill *hash_spills; /* HashAggSpill for each grouping set, * exists only during first pass */ @@ -2584,7 +2585,7 @@ typedef struct AggState * per-group pointers */ /* support for evaluation of agg input expressions: */ -#define FIELDNO_AGGSTATE_ALL_PERGROUPS 53 +#define FIELDNO_AGGSTATE_ALL_PERGROUPS 54 AggStatePerGroup *all_pergroups; /* array of first ->pergroups, than * ->hash_pergroup */ SharedAggInfo *shared_info; /* one entry per worker */ diff --git a/src/test/regress/expected/groupingsets.out b/src/test/regress/expected/groupingsets.out index d7c9b44605d..0e86e31fe90 100644 --- a/src/test/regress/expected/groupingsets.out +++ b/src/test/regress/expected/groupingsets.out @@ -1711,7 +1711,7 @@ explain (costs off) -> Seq Scan on tenk1 (9 rows) -set work_mem = '384kB'; +set work_mem = '256kB'; explain (costs off) select unique1, count(two), count(four), count(ten), diff --git a/src/test/regress/sql/groupingsets.sql b/src/test/regress/sql/groupingsets.sql index 21cd3121940..10f3c36d5c6 100644 --- a/src/test/regress/sql/groupingsets.sql +++ b/src/test/regress/sql/groupingsets.sql @@ -467,7 +467,7 @@ explain (costs off) count(*) from tenk1 group by grouping sets (unique1,hundred,ten,four,two); -set work_mem = '384kB'; +set work_mem = '256kB'; explain (costs off) select unique1, count(two), count(four), count(ten), -- 2.34.1 ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-02-13 01:01 Jeff Davis <[email protected]> parent: Jeff Davis <[email protected]> 0 siblings, 2 replies; 11+ messages in thread From: Jeff Davis @ 2025-02-13 01:01 UTC (permalink / raw) To: David Rowley <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; pgsql-hackers On Fri, 2025-02-07 at 17:13 -0800, Jeff Davis wrote: > On Sun, 2025-01-12 at 14:54 +1300, David Rowley wrote: > > I wonder if there's some other better way of doing this. Would it > > be > > worth having some function like ExecCopySlotMinimalTuple() that > > accepts an additional parameter so that the palloc allocates N more > > bytes at the end? > > Attached a new series that implements this idea. Attached a new patchset that doesn't change the API for ExecCopySlotMinimalTuple(). Instead, I'm using ExecFetchSlotMinimalTuple(), which avoids the extra memcpy if the slot is TTSOpsMinimalTuple, which is what HashAgg uses. I separated out the change to use ExecFetchSlotMinimalTuple() into 0004 to illustrate the performance impact. DATA: create table a (a text not null); insert into a select repeat(md5(a::text),10) from generate_Series(1,1000) a; vacuum freeze analyze a; create table b (b text not null); insert into b select repeat(md5(b::text),10) from generate_Series(1001,2000) b; vacuum freeze analyze b; QUERY: select a,count(*) from a group by a; master: tps = 2054.742658 (without initial connection time) 0001: tps = 2068.620429 (without initial connection time) 0002: tps = 2027.046422 (without initial connection time) 0003: tps = 1951.392904 (without initial connection time) 0004: tps = 2071.690037 (without initial connection time) QUERY: select * from a except select * from b; master: tps = 1720.168862 (without initial connection time) 0001: tps = 1703.040810 (without initial connection time) 0002: tps = 1687.191715 (without initial connection time) 0003: tps = 1579.975535 (without initial connection time) 0004: tps = 1616.741447 (without initial connection time) So the GROUP BY query has no regression (because there's no additional copy) and the EXCEPT query has about a 6% regression. The v6 series doesn't have that regression for set operations, but it requires the somewhat-messy ExecCopySlotMinimalTupleExtra() API. If you think you'll use that in nodeMemoize, then the API change is worth it. If not, it feels a bit like a hack. Another thing I did in the v7 series is I stored the additional data before the firstTuple. It seems cleaner to store the fixed-length data first -- I could do the same thing if we go with ExecCopySlotMinimalTupleExtra(). In any case, it seems like we have agreement to switch to the Bump context, so I'll do another round of tests to see if there are any downsides, then clean it up and commit v7-0001. Regards, Jeff Davis Attachments: [text/x-patch] v7-0001-HashAgg-use-Bump-allocator-for-hash-TupleHashTabl.patch (10.9K, ../../[email protected]/2-v7-0001-HashAgg-use-Bump-allocator-for-hash-TupleHashTabl.patch) download | inline diff: From b0023cde3798a481c7a7f1f453be3d037ef4c2f5 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 8 Jan 2025 11:46:35 -0800 Subject: [PATCH v7 1/4] HashAgg: use Bump allocator for hash TupleHashTable entries. The entries aren't freed until the entire hash table is destroyed, so use the Bump allocator to improve allocation speed, avoid wasting space on the chunk header, and avoid wasting space due to the power-of-two allocations. Discussion: https://postgr.es/m/CAApHDvqv1aNB4cM36FzRwivXrEvBO_LsG_eQ3nqDXTjECaatOQ@mail.gmail.com Reviewed-by: David Rowley --- src/backend/executor/nodeAgg.c | 110 +++++++++++++++++---- src/include/nodes/execnodes.h | 5 +- src/test/regress/expected/groupingsets.out | 2 +- src/test/regress/sql/groupingsets.sql | 2 +- 4 files changed, 97 insertions(+), 22 deletions(-) diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index ae9cc256b8c..340a2010101 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -406,6 +406,7 @@ static void build_hash_tables(AggState *aggstate); static void build_hash_table(AggState *aggstate, int setno, long nbuckets); static void hashagg_recompile_expressions(AggState *aggstate, bool minslot, bool nullcheck); +static void hash_create_memory(AggState *aggstate); static long hash_choose_num_buckets(double hashentrysize, long ngroups, Size memory); static int hash_choose_num_partitions(double input_groups, @@ -1512,7 +1513,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets) { AggStatePerHash perhash = &aggstate->perhash[setno]; MemoryContext metacxt = aggstate->hash_metacxt; - MemoryContext hashcxt = aggstate->hashcontext->ecxt_per_tuple_memory; + MemoryContext tablecxt = aggstate->hash_tablecxt; MemoryContext tmpcxt = aggstate->tmpcontext->ecxt_per_tuple_memory; Size additionalsize; @@ -1538,7 +1539,7 @@ build_hash_table(AggState *aggstate, int setno, long nbuckets) nbuckets, additionalsize, metacxt, - hashcxt, + tablecxt, tmpcxt, DO_AGGSPLIT_SKIPFINAL(aggstate->aggsplit)); } @@ -1709,15 +1710,24 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) tupleWidth); Size pergroupSize = numTrans * sizeof(AggStatePerGroupData); - tupleChunkSize = CHUNKHDRSZ + tupleSize; - - if (pergroupSize > 0) - pergroupChunkSize = CHUNKHDRSZ + pergroupSize; - else - pergroupChunkSize = 0; + /* + * Entries use the Bump allocator, so the chunk sizes are the same as the + * requested sizes. + */ + tupleChunkSize = tupleSize; + pergroupChunkSize = pergroupSize; + /* + * Transition values use AllocSet, which has a chunk header and also uses + * power-of-two allocations. + */ if (transitionSpace > 0) - transitionChunkSize = CHUNKHDRSZ + transitionSpace; + { + Size pow2 = (Size) 1 << my_log2(transitionSpace); + + /* use Max to protect against overflow */ + transitionChunkSize = Max(CHUNKHDRSZ + pow2, transitionSpace); + } else transitionChunkSize = 0; @@ -1867,8 +1877,11 @@ hash_agg_check_limits(AggState *aggstate) uint64 ngroups = aggstate->hash_ngroups_current; Size meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true); - Size hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, - true); + Size entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt, + true); + Size tval_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, + true); + Size total_mem = meta_mem + entry_mem + tval_mem; bool do_spill = false; #ifdef USE_INJECTION_POINTS @@ -1887,7 +1900,7 @@ hash_agg_check_limits(AggState *aggstate) * can be sure to make progress even in edge cases. */ if (aggstate->hash_ngroups_current > 0 && - (meta_mem + hashkey_mem > aggstate->hash_mem_limit || + (total_mem > aggstate->hash_mem_limit || ngroups > aggstate->hash_ngroups_limit)) { do_spill = true; @@ -1942,6 +1955,7 @@ static void hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) { Size meta_mem; + Size entry_mem; Size hashkey_mem; Size buffer_mem; Size total_mem; @@ -1953,7 +1967,10 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) /* memory for the hash table itself */ meta_mem = MemoryContextMemAllocated(aggstate->hash_metacxt, true); - /* memory for the group keys and transition states */ + /* memory for hash entries */ + entry_mem = MemoryContextMemAllocated(aggstate->hash_tablecxt, true); + + /* memory for byref transition states */ hashkey_mem = MemoryContextMemAllocated(aggstate->hashcontext->ecxt_per_tuple_memory, true); /* memory for read/write tape buffers, if spilled */ @@ -1962,7 +1979,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) buffer_mem += HASHAGG_READ_BUFFER_SIZE; /* update peak mem */ - total_mem = meta_mem + hashkey_mem + buffer_mem; + total_mem = meta_mem + entry_mem + hashkey_mem + buffer_mem; if (total_mem > aggstate->hash_mem_peak) aggstate->hash_mem_peak = total_mem; @@ -1984,6 +2001,58 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) } } +/* + * Create memory contexts used for hash aggregation. + */ +static void +hash_create_memory(AggState *aggstate) +{ + Size minContextSize = ALLOCSET_DEFAULT_MINSIZE; + Size initBlockSize = ALLOCSET_DEFAULT_INITSIZE; + Size maxBlockSize = ALLOCSET_DEFAULT_MAXSIZE; + + /* + * The hashcontext's per-tuple memory will be used for byref transition + * values and returned by AggCheckCallContext(). + */ + aggstate->hashcontext = CreateWorkExprContext(aggstate->ss.ps.state); + + /* + * The meta context will be used for the bucket array of + * TupleHashEntryData (or arrays, in the case of grouping sets). As the + * hash table grows, the bucket array will double in size and the old one + * will be freed, so an AllocSet is appropriate. For large bucket arrays, + * the large allocation path will be used, so it's not worth worrying + * about wasting space due to power-of-two allocations. + */ + aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt, + "HashAgg meta context", + ALLOCSET_DEFAULT_SIZES); + + /* + * The hash entries themselves, which include the grouping key + * (firstTuple) and pergroup data, are stored in the table context. The + * bump allocator can be used because the entries are not freed until the + * entire hash table is reset. The bump allocator is faster for + * allocations and avoids wasting space on the chunk header or + * power-of-two allocations. + * + * Like CreateWorkExprContext(), use smaller sizings for smaller work_mem, + * to avoid large jumps in memory usage. + */ + while (16 * maxBlockSize > work_mem * 1024L) + maxBlockSize >>= 1; + + if (maxBlockSize < ALLOCSET_DEFAULT_INITSIZE) + maxBlockSize = ALLOCSET_DEFAULT_INITSIZE; + + aggstate->hash_tablecxt = BumpContextCreate(aggstate->ss.ps.state->es_query_cxt, + "HashAgg table context", + minContextSize, initBlockSize, + maxBlockSize); + +} + /* * Choose a reasonable number of buckets for the initial hash table size. */ @@ -2647,6 +2716,7 @@ agg_refill_hash_table(AggState *aggstate) /* free memory and reset hash tables */ ReScanExprContext(aggstate->hashcontext); + MemoryContextReset(aggstate->hash_tablecxt); for (int setno = 0; setno < aggstate->num_hashes; setno++) ResetTupleHashTable(aggstate->perhash[setno].hashtable); @@ -3331,7 +3401,7 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) } if (use_hashing) - aggstate->hashcontext = CreateWorkExprContext(estate); + hash_create_memory(aggstate); ExecAssignExprContext(estate, &aggstate->ss.ps); @@ -3626,9 +3696,6 @@ ExecInitAgg(Agg *node, EState *estate, int eflags) Plan *outerplan = outerPlan(node); uint64 totalGroups = 0; - aggstate->hash_metacxt = AllocSetContextCreate(aggstate->ss.ps.state->es_query_cxt, - "HashAgg meta context", - ALLOCSET_DEFAULT_SIZES); aggstate->hash_spill_rslot = ExecInitExtraTupleSlot(estate, scanDesc, &TTSOpsMinimalTuple); aggstate->hash_spill_wslot = ExecInitExtraTupleSlot(estate, scanDesc, @@ -4373,6 +4440,12 @@ ExecEndAgg(AggState *node) MemoryContextDelete(node->hash_metacxt); node->hash_metacxt = NULL; } + if (node->hash_tablecxt != NULL) + { + MemoryContextDelete(node->hash_tablecxt); + node->hash_tablecxt = NULL; + } + for (transno = 0; transno < node->numtrans; transno++) { @@ -4489,6 +4562,7 @@ ExecReScanAgg(AggState *node) node->hash_ngroups_current = 0; ReScanExprContext(node->hashcontext); + MemoryContextReset(node->hash_tablecxt); /* Rebuild an empty hash table */ build_hash_tables(node); node->table_filled = false; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index e2d1dc1e067..1aacad936af 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2563,7 +2563,8 @@ typedef struct AggState /* these fields are used in AGG_HASHED and AGG_MIXED modes: */ bool table_filled; /* hash table filled yet? */ int num_hashes; - MemoryContext hash_metacxt; /* memory for hash table itself */ + MemoryContext hash_metacxt; /* memory for hash table bucket array */ + MemoryContext hash_tablecxt; /* memory for hash table entries */ struct LogicalTapeSet *hash_tapeset; /* tape set for hash spill tapes */ struct HashAggSpill *hash_spills; /* HashAggSpill for each grouping set, * exists only during first pass */ @@ -2589,7 +2590,7 @@ typedef struct AggState * per-group pointers */ /* support for evaluation of agg input expressions: */ -#define FIELDNO_AGGSTATE_ALL_PERGROUPS 53 +#define FIELDNO_AGGSTATE_ALL_PERGROUPS 54 AggStatePerGroup *all_pergroups; /* array of first ->pergroups, than * ->hash_pergroup */ SharedAggInfo *shared_info; /* one entry per worker */ diff --git a/src/test/regress/expected/groupingsets.out b/src/test/regress/expected/groupingsets.out index d7c9b44605d..0e86e31fe90 100644 --- a/src/test/regress/expected/groupingsets.out +++ b/src/test/regress/expected/groupingsets.out @@ -1711,7 +1711,7 @@ explain (costs off) -> Seq Scan on tenk1 (9 rows) -set work_mem = '384kB'; +set work_mem = '256kB'; explain (costs off) select unique1, count(two), count(four), count(ten), diff --git a/src/test/regress/sql/groupingsets.sql b/src/test/regress/sql/groupingsets.sql index 21cd3121940..10f3c36d5c6 100644 --- a/src/test/regress/sql/groupingsets.sql +++ b/src/test/regress/sql/groupingsets.sql @@ -467,7 +467,7 @@ explain (costs off) count(*) from tenk1 group by grouping sets (unique1,hundred,ten,four,two); -set work_mem = '384kB'; +set work_mem = '256kB'; explain (costs off) select unique1, count(two), count(four), count(ten), -- 2.34.1 [text/x-patch] v7-0002-Refactor-accessors-for-TupleHashEntryData.patch (11.8K, ../../[email protected]/3-v7-0002-Refactor-accessors-for-TupleHashEntryData.patch) download | inline diff: From d76e51114cb4e50fd36905ffcb446652fa64a62c Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Mon, 13 Jan 2025 14:37:02 -0800 Subject: [PATCH v7 2/4] Refactor: accessors for TupleHashEntryData. Previously, callers were accessing fields directly, making it more difficult to optimize. A subsequent patch will combine firstTuple and the additionalsize into a single allocation. Discussion: https://postgr.es/m/817d244237878cebdff0bc363718feaf49a1ea7d.camel%40j-davis.com --- src/backend/executor/execGrouping.c | 7 ++++-- src/backend/executor/nodeAgg.c | 32 +++++++++++++--------------- src/backend/executor/nodeSetOp.c | 23 +++++++++++--------- src/backend/executor/nodeSubplan.c | 2 +- src/include/executor/executor.h | 33 +++++++++++++++++++++++++++++ src/include/nodes/execnodes.h | 1 + 6 files changed, 68 insertions(+), 30 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 33b124fbb0a..450fe74bec5 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -196,6 +196,7 @@ BuildTupleHashTable(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; + hashtable->additionalsize = additionalsize; hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_expr = NULL; @@ -479,11 +480,13 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, { /* created new entry */ *isnew = true; - /* zero caller data */ - entry->additional = NULL; + MemoryContextSwitchTo(hashtable->tablecxt); + /* Copy the first tuple into the table context */ entry->firstTuple = ExecCopySlotMinimalTuple(slot); + + entry->additional = palloc0(hashtable->additionalsize); } } else diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c index 340a2010101..af0b7b27383 100644 --- a/src/backend/executor/nodeAgg.c +++ b/src/backend/executor/nodeAgg.c @@ -1494,7 +1494,7 @@ build_hash_tables(AggState *aggstate) #ifdef USE_INJECTION_POINTS if (IS_INJECTION_POINT_ATTACHED("hash-aggregate-oversize-table")) { - nbuckets = memory / sizeof(TupleHashEntryData); + nbuckets = memory / TupleHashEntrySize(); INJECTION_POINT_CACHED("hash-aggregate-oversize-table"); } #endif @@ -1732,7 +1732,7 @@ hash_agg_entry_size(int numTrans, Size tupleWidth, Size transitionSpace) transitionChunkSize = 0; return - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + tupleChunkSize + pergroupChunkSize + transitionChunkSize; @@ -1996,7 +1996,7 @@ hash_agg_update_metrics(AggState *aggstate, bool from_tape, int npartitions) if (aggstate->hash_ngroups_current > 0) { aggstate->hashentrysize = - sizeof(TupleHashEntryData) + + TupleHashEntrySize() + (hashkey_mem / (double) aggstate->hash_ngroups_current); } } @@ -2149,11 +2149,7 @@ initialize_hash_entry(AggState *aggstate, TupleHashTable hashtable, if (aggstate->numtrans == 0) return; - pergroup = (AggStatePerGroup) - MemoryContextAlloc(hashtable->tablecxt, - sizeof(AggStatePerGroupData) * aggstate->numtrans); - - entry->additional = pergroup; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry); /* * Initialize aggregates for new tuple group, lookup_hash_entries() @@ -2217,7 +2213,7 @@ lookup_hash_entries(AggState *aggstate) { if (isnew) initialize_hash_entry(aggstate, hashtable, entry); - pergroup[setno] = entry->additional; + pergroup[setno] = TupleHashEntryGetAdditional(hashtable, entry); } else { @@ -2750,6 +2746,7 @@ agg_refill_hash_table(AggState *aggstate) INJECTION_POINT("hash-aggregate-process-batch"); for (;;) { + TupleHashTable hashtable = perhash->hashtable; TupleTableSlot *spillslot = aggstate->hash_spill_rslot; TupleTableSlot *hashslot = perhash->hashslot; TupleHashEntry entry; @@ -2770,14 +2767,14 @@ agg_refill_hash_table(AggState *aggstate) prepare_hash_slot(perhash, aggstate->tmpcontext->ecxt_outertuple, hashslot); - entry = LookupTupleHashEntryHash(perhash->hashtable, hashslot, + entry = LookupTupleHashEntryHash(hashtable, hashslot, p_isnew, hash); if (entry != NULL) { if (isnew) - initialize_hash_entry(aggstate, perhash->hashtable, entry); - aggstate->hash_pergroup[batch->setno] = entry->additional; + initialize_hash_entry(aggstate, hashtable, entry); + aggstate->hash_pergroup[batch->setno] = TupleHashEntryGetAdditional(hashtable, entry); advance_aggregates(aggstate); } else @@ -2869,7 +2866,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) ExprContext *econtext; AggStatePerAgg peragg; AggStatePerGroup pergroup; - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *firstSlot; TupleTableSlot *result; AggStatePerHash perhash; @@ -2895,6 +2892,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) */ for (;;) { + TupleHashTable hashtable = perhash->hashtable; TupleTableSlot *hashslot = perhash->hashslot; int i; @@ -2903,7 +2901,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) /* * Find the next entry in the hash table */ - entry = ScanTupleHashTable(perhash->hashtable, &perhash->hashiter); + entry = ScanTupleHashTable(hashtable, &perhash->hashiter); if (entry == NULL) { int nextset = aggstate->current_set + 1; @@ -2918,7 +2916,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) perhash = &aggstate->perhash[aggstate->current_set]; - ResetTupleHashIterator(perhash->hashtable, &perhash->hashiter); + ResetTupleHashIterator(hashtable, &perhash->hashiter); continue; } @@ -2941,7 +2939,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) * Transform representative tuple back into one with the right * columns. */ - ExecStoreMinimalTuple(entry->firstTuple, hashslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashslot, false); slot_getallattrs(hashslot); ExecClearTuple(firstSlot); @@ -2957,7 +2955,7 @@ agg_retrieve_hash_table_in_memory(AggState *aggstate) } ExecStoreVirtualTuple(firstSlot); - pergroup = (AggStatePerGroup) entry->additional; + pergroup = (AggStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry); /* * Use the representative input tuple for any references to diff --git a/src/backend/executor/nodeSetOp.c b/src/backend/executor/nodeSetOp.c index 5b7ff9c3748..cbdc717850c 100644 --- a/src/backend/executor/nodeSetOp.c +++ b/src/backend/executor/nodeSetOp.c @@ -424,7 +424,9 @@ setop_fill_hash_table(SetOpState *setopstate) for (;;) { TupleTableSlot *outerslot; + TupleHashTable hashtable = setopstate->hashtable; TupleHashEntryData *entry; + SetOpStatePerGroup pergroup; bool isnew; outerslot = ExecProcNode(outerPlan); @@ -433,20 +435,20 @@ setop_fill_hash_table(SetOpState *setopstate) have_tuples = true; /* Find or build hashtable entry for this tuple's group */ - entry = LookupTupleHashEntry(setopstate->hashtable, + entry = LookupTupleHashEntry(hashtable, outerslot, &isnew, NULL); + pergroup = TupleHashEntryGetAdditional(hashtable, entry); /* If new tuple group, initialize counts to zero */ if (isnew) { - entry->additional = (SetOpStatePerGroup) - MemoryContextAllocZero(setopstate->hashtable->tablecxt, - sizeof(SetOpStatePerGroupData)); + pergroup->numLeft = 0; + pergroup->numRight = 0; } /* Advance the counts */ - ((SetOpStatePerGroup) entry->additional)->numLeft++; + pergroup->numLeft++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -464,6 +466,7 @@ setop_fill_hash_table(SetOpState *setopstate) */ for (;;) { + TupleHashTable hashtable = setopstate->hashtable; TupleTableSlot *innerslot; TupleHashEntryData *entry; @@ -472,13 +475,13 @@ setop_fill_hash_table(SetOpState *setopstate) break; /* For tuples not seen previously, do not make hashtable entry */ - entry = LookupTupleHashEntry(setopstate->hashtable, + entry = LookupTupleHashEntry(hashtable, innerslot, NULL, NULL); /* Advance the counts if entry is already present */ if (entry) - ((SetOpStatePerGroup) entry->additional)->numRight++; + ((SetOpStatePerGroup) TupleHashEntryGetAdditional(hashtable, entry))->numRight++; /* Must reset expression context after each hashtable lookup */ ResetExprContext(econtext); @@ -496,7 +499,7 @@ setop_fill_hash_table(SetOpState *setopstate) static TupleTableSlot * setop_retrieve_hash_table(SetOpState *setopstate) { - TupleHashEntryData *entry; + TupleHashEntry entry; TupleTableSlot *resultTupleSlot; /* @@ -526,12 +529,12 @@ setop_retrieve_hash_table(SetOpState *setopstate) * See if we should emit any copies of this tuple, and if so return * the first copy. */ - set_output_count(setopstate, (SetOpStatePerGroup) entry->additional); + set_output_count(setopstate, (SetOpStatePerGroup) TupleHashEntryGetAdditional(setopstate->hashtable, entry)); if (setopstate->numOutput > 0) { setopstate->numOutput--; - return ExecStoreMinimalTuple(entry->firstTuple, + return ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), resultTupleSlot, false); } diff --git a/src/backend/executor/nodeSubplan.c b/src/backend/executor/nodeSubplan.c index 49767ed6a52..f7f6fc2da0b 100644 --- a/src/backend/executor/nodeSubplan.c +++ b/src/backend/executor/nodeSubplan.c @@ -753,7 +753,7 @@ findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot, { CHECK_FOR_INTERRUPTS(); - ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false); + ExecStoreMinimalTuple(TupleHashEntryGetTuple(entry), hashtable->tableslot, false); if (!execTuplesUnequal(slot, hashtable->tableslot, numCols, keyColIdx, eqfunctions, diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index 30e2a82346f..ee93b479c92 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -157,6 +157,39 @@ extern TupleHashEntry FindTupleHashEntry(TupleHashTable hashtable, ExprState *hashexpr); extern void ResetTupleHashTable(TupleHashTable hashtable); +#ifndef FRONTEND +/* + * Return size of the hash bucket. Useful for estimating memory usage. + */ +static inline size_t +TupleHashEntrySize(void) +{ + return sizeof(TupleHashEntryData); +} + +/* + * Return tuple from hash entry. + */ +static inline MinimalTuple +TupleHashEntryGetTuple(TupleHashEntry entry) +{ + return entry->firstTuple; +} + +/* + * Get a pointer into the additional space allocated for this entry. The + * amount of space available is the additionalsize specified to + * BuildTupleHashTable(). If additionalsize was specified as zero, no + * additional space is available and this function should not be called. + */ +static inline void * +TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry) +{ + Assert(entry->additional != NULL); + return entry->additional; +} +#endif + /* * prototypes from functions in execJunk.c */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 1aacad936af..11aa110cf9c 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -860,6 +860,7 @@ typedef struct TupleHashTableData Oid *tab_collations; /* collations for hash and comparison */ MemoryContext tablecxt; /* memory context containing table */ MemoryContext tempcxt; /* context for function evaluations */ + Size additionalsize; /* size of additional data */ TupleTableSlot *tableslot; /* slot for referencing table entries */ /* The following fields are set transiently for each table search: */ TupleTableSlot *inputslot; /* current input tuple's slot */ -- 2.34.1 [text/x-patch] v7-0003-Combine-firstTuple-and-additionalsize-into-a-sing.patch (4.1K, ../../[email protected]/4-v7-0003-Combine-firstTuple-and-additionalsize-into-a-sing.patch) download | inline diff: From 3e21d4328af39e52df0e1ec49a8234a328506f75 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Tue, 14 Jan 2025 16:17:00 -0800 Subject: [PATCH v7 3/4] Combine firstTuple and additionalsize into a single allocation. Saves space in TupleHashEntryData by removing the "additional" pointer. TupleHashEntryData is required for each bucket, whether occupied or not, so that space is more valuable than other hash table allocations. Discussion: https://postgr.es/m/817d244237878cebdff0bc363718feaf49a1ea7d.camel%40j-davis.com --- src/backend/executor/execGrouping.c | 33 +++++++++++++++++++++++------ src/include/executor/executor.h | 9 ++++---- src/include/nodes/execnodes.h | 1 - 3 files changed, 31 insertions(+), 12 deletions(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 450fe74bec5..76b16101dbd 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -196,7 +196,7 @@ BuildTupleHashTable(PlanState *parent, hashtable->tab_collations = collations; hashtable->tablecxt = tablecxt; hashtable->tempcxt = tempcxt; - hashtable->additionalsize = additionalsize; + hashtable->additionalsize = MAXALIGN(additionalsize); hashtable->tableslot = NULL; /* will be made on first lookup */ hashtable->inputslot = NULL; hashtable->in_hash_expr = NULL; @@ -478,15 +478,34 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, } else { + char *data; + MinimalTuple tmpTuple; + Size totalsize; + /* created new entry */ *isnew = true; - MemoryContextSwitchTo(hashtable->tablecxt); - - /* Copy the first tuple into the table context */ - entry->firstTuple = ExecCopySlotMinimalTuple(slot); - - entry->additional = palloc0(hashtable->additionalsize); + /* get minimal tuple in temp context */ + MemoryContextSwitchTo(hashtable->tempcxt); + tmpTuple = ExecCopySlotMinimalTuple(slot); + + /* + * Allocate space for additionalsize followed by the MinimalTuple + * in the table context, and copy the tuple. A single allocation + * avoids the need to store two pointers in TupleHashEntryData. + */ + totalsize = hashtable->additionalsize + tmpTuple->t_len; + data = MemoryContextAlloc(hashtable->tablecxt, totalsize); + memset(data, 0, hashtable->additionalsize); + + /* + * firstTuple points in the middle of the allocated space. The + * additional data pointer can be computed by subtracting + * additionalsize from firstTuple. + */ + data += hashtable->additionalsize; + entry->firstTuple = (MinimalTuple) data; + memcpy(entry->firstTuple, tmpTuple, tmpTuple->t_len); } } else diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h index ee93b479c92..344c5f8a54b 100644 --- a/src/include/executor/executor.h +++ b/src/include/executor/executor.h @@ -178,15 +178,16 @@ TupleHashEntryGetTuple(TupleHashEntry entry) /* * Get a pointer into the additional space allocated for this entry. The - * amount of space available is the additionalsize specified to - * BuildTupleHashTable(). If additionalsize was specified as zero, no + * memory will be maxaligned and zeroed. + * + * The amount of space available is the additionalsize requested in the call + * to BuildTupleHashTable(). If additionalsize was specified as zero, no * additional space is available and this function should not be called. */ static inline void * TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry) { - Assert(entry->additional != NULL); - return entry->additional; + return (char *) entry->firstTuple - hashtable->additionalsize; } #endif diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 11aa110cf9c..a875335cb09 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -837,7 +837,6 @@ typedef struct TupleHashTableData *TupleHashTable; typedef struct TupleHashEntryData { MinimalTuple firstTuple; /* copy of first tuple in this group */ - void *additional; /* user data */ uint32 status; /* hash status */ uint32 hash; /* hash value (cached) */ } TupleHashEntryData; -- 2.34.1 [text/x-patch] v7-0004-Use-ExecFetchSlotMinimalTuple.patch (1.0K, ../../[email protected]/5-v7-0004-Use-ExecFetchSlotMinimalTuple.patch) download | inline diff: From c8f534aa7954fa30ee3271a1cf157652f086b559 Mon Sep 17 00:00:00 2001 From: Jeff Davis <[email protected]> Date: Wed, 12 Feb 2025 13:05:26 -0800 Subject: [PATCH v7 4/4] Use ExecFetchSlotMinimalTuple(). --- src/backend/executor/execGrouping.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/backend/executor/execGrouping.c b/src/backend/executor/execGrouping.c index 76b16101dbd..3712bcdf6f5 100644 --- a/src/backend/executor/execGrouping.c +++ b/src/backend/executor/execGrouping.c @@ -481,13 +481,14 @@ LookupTupleHashEntry_internal(TupleHashTable hashtable, TupleTableSlot *slot, char *data; MinimalTuple tmpTuple; Size totalsize; + bool shouldFree; /* created new entry */ *isnew = true; /* get minimal tuple in temp context */ MemoryContextSwitchTo(hashtable->tempcxt); - tmpTuple = ExecCopySlotMinimalTuple(slot); + tmpTuple = ExecFetchSlotMinimalTuple(slot, &shouldFree); /* * Allocate space for additionalsize followed by the MinimalTuple -- 2.34.1 ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-02-18 05:49 Jeff Davis <[email protected]> parent: Jeff Davis <[email protected]> 1 sibling, 0 replies; 11+ messages in thread From: Jeff Davis @ 2025-02-18 05:49 UTC (permalink / raw) To: David Rowley <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; pgsql-hackers On Wed, 2025-02-12 at 17:01 -0800, Jeff Davis wrote: > In any case, it seems like we have agreement to switch to the Bump > context, so I'll do another round of tests to see if there are any > downsides, then clean it up and commit v7-0001. Results for v7-0001 (switch to Bump Allocator for table entries). Setup: SET work_mem='10GB'; SET max_parallel_workers=0; SET max_parallel_workers_per_gather=0; -- T1: group size avg ~ 1.5 create table t1(i int8, j numeric); insert into t1 select random(1,10000000),sqrt(g) from generate_series(1,10000000) g; vacuum freeze analyze t1; checkpoint; -- T100: group size avg ~100 create table t100(i int8, j numeric); insert into t100 select random(1,100000),sqrt(g) from generate_series(1,10000000) g; vacuum freeze analyze t100; checkpoint; Q1: explain analyze select i, count(j) from THETABLE group by i; t1 t100 master: 776MB / 4085ms 14MB / 1375ms patch: 632MB / 4192ms 10MB / 1375ms Q2: explain analyze select i, count(j), max(j), sum(j) from THETABLE group by i; t1 t100 master: 3280MB / 7817ms 54MB / 4194ms patch: 3048MB / 8103ms 54MB / 4492ms While it's a memory reduction in all cases, and a ~20% memory reduction for by-value types; there appears to be some slowdown for by-reference types -- 7% for Q2 when the group size is 100. I profiled it and it seems to be spending more time in advance_aggregates. Since I didn't change that code, the only explanation I have for that is that with everything in one memory context, the by-reference values end up near enough to the group key and pergroup state to benefit from caching effects. I'm not sure that explanation makes sense though, because even in the old code where they are both in the same memory context, why would we expect the transition values to be close to the grouping key or pergroup state? Regards, Jeff Davis ^ permalink raw reply [nested|flat] 11+ messages in thread
* Re: Reduce TupleHashEntryData struct size by half @ 2025-02-28 04:09 David Rowley <[email protected]> parent: Jeff Davis <[email protected]> 1 sibling, 0 replies; 11+ messages in thread From: David Rowley @ 2025-02-28 04:09 UTC (permalink / raw) To: Jeff Davis <[email protected]>; +Cc: Heikki Linnakangas <[email protected]>; pgsql-hackers On Thu, 13 Feb 2025 at 14:01, Jeff Davis <[email protected]> wrote: > Attached a new patchset that doesn't change the API for > ExecCopySlotMinimalTuple(). Instead, I'm using > ExecFetchSlotMinimalTuple(), which avoids the extra memcpy if the slot > is TTSOpsMinimalTuple, which is what HashAgg uses. I separated out the > change to use ExecFetchSlotMinimalTuple() into 0004 to illustrate the > performance impact. Some review comments: * my_log2() takes a "long" parameter type but transitionSpace is a "Size". These types aren't the same width on all platforms we support. Maybe pg_nextpower2_size_t() is a better option. * Should the following have MAXALIGN(tupleSize) on the right side of the expression? tupleChunkSize = tupleSize I understand this was missing before, but both bump.c does consume at least MAXALIGN(<req_size>) in BumpAlloc(). * while (16 * maxBlockSize > work_mem * 1024L) The 1024L predates the change made in 041e8b95. "1024L" needs to be replaced with "(Size) 1024" Maybe you could just replace the while loop and the subsequent "if" check with: /* * Like CreateWorkExprContext(), use smaller sizings for smaller work_mem, * to avoid large jumps in memory usage. */ maxBlockSize = pg_prevpower2_size_t(work_mem * (Size) 1024 / 16); /* But no bigger than ALLOCSET_DEFAULT_MAXSIZE */ maxBlockSize = Min(maxBlockSize, ALLOCSET_DEFAULT_MAXSIZE); /* and no smaller than ALLOCSET_DEFAULT_INITSIZE */ maxBlockSize = Max(maxBlockSize, ALLOCSET_DEFAULT_INITSIZE); I believe that gives the same result without the looping. * In hash_create_memory(), can you get rid of the minContextSize and initBlockSize variables? * Is it worth an Assert() theck additionalsize > 0? * The amount of space available is the additionalsize requested in the call * to BuildTupleHashTable(). If additionalsize was specified as zero, no * additional space is available and this function should not be called. */ static inline void * TupleHashEntryGetAdditional(TupleHashTable hashtable, TupleHashEntry entry) { return (char *) entry->firstTuple - hashtable->additionalsize; } Benchmarks: I was also experimenting with the performance of this using the following test case: create table c (a int not null); insert into c select a from generate_Series(1,1000) a; vacuum freeze analyze c; Query: select a,count(*) from c group by a; Average TPS over 10x 10 second runs with -M prepared master: 3653.9853988 v7-0001: 3741.815979 v7-0001+0002: 3737.4313064 v7-0001+0002+0003: 3834.6271706 v7-0001+0002+0004+0004: 3912.1158887 I also tried out changing hash_agg_check_limits() so that it no longer calls MemoryContextMemAllocated and instead uses ->mem_allocated directly and with all the other patches got: v7-0001+0002+0004+0004+extra: 4049.0732381 We probably shouldn't do exactly that as it be better not to access that internal field from outside the memory context code. A static inline function in memutils.h that handles the non-recursive callers might be nice. I've attached my results of running your test in graph form. I also see a small regression for these small scale tests. I wondering if it's worth mocking up some code to see what the performance would be like without the additional memcpy() that's new to LookupTupleHashEntry_internal(). How about hacking something up that adds an additionalsize field to TupleDesc and then set that field to your additional size and have heap_form_minimal_tuple() allocate that much extra memory? David Attachments: [image/png] zen4_7945hx_test.png (60.2K, ../../CAApHDvpN4v3t_sdz4dvrv1Fx_ZPw=twSnxuTEytRYP7LFz5K9A@mail.gmail.com/2-zen4_7945hx_test.png) download | view image ^ permalink raw reply [nested|flat] 11+ messages in thread
end of thread, other threads:[~2025-02-28 04:09 UTC | newest] Thread overview: 11+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-10-07 03:11 [PATCH v8 4/8] Propagate changes to indisclustered to child/parents Justin Pryzby <[email protected]> 2024-11-18 10:13 Re: Reduce TupleHashEntryData struct size by half Heikki Linnakangas <[email protected]> 2024-11-18 20:22 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2024-11-18 23:30 ` Re: Reduce TupleHashEntryData struct size by half Heikki Linnakangas <[email protected]> 2024-11-21 20:37 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2025-01-07 23:32 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2025-01-12 01:54 ` Re: Reduce TupleHashEntryData struct size by half David Rowley <[email protected]> 2025-02-08 01:13 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2025-02-13 01:01 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2025-02-18 05:49 ` Re: Reduce TupleHashEntryData struct size by half Jeff Davis <[email protected]> 2025-02-28 04:09 ` Re: Reduce TupleHashEntryData struct size by half David Rowley <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox