($INBOX_DIR/description missing)help / color / mirror / Atom feed
[PATCH 1/2] Introduce RelInfoList structure. 5+ messages / 1 participants [nested] [flat]
* [PATCH 1/2] Introduce RelInfoList structure. @ 2020-01-16 15:02 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2020-01-16 15:02 UTC (permalink / raw) This patch puts join_rel_list and join_rel_hash fields of PlannerInfo structure into a new structure RelInfoList. It also adjusts add_join_rel() and find_join_rel() functions so they only call add_rel_info() and find_rel_inf() respectively. Thus it'll be easier to add a new list and accessor functions that we'll need for grouped relation. --- contrib/postgres_fdw/postgres_fdw.c | 3 +- src/backend/nodes/outfuncs.c | 11 ++ src/backend/optimizer/geqo/geqo_eval.c | 12 +- src/backend/optimizer/plan/planmain.c | 3 +- src/backend/optimizer/util/relnode.c | 161 +++++++++++++++---------- src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 28 +++-- 7 files changed, 140 insertions(+), 79 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 2175dff824..07c70843e8 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -5251,7 +5251,8 @@ foreign_join_ok(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, */ Assert(fpinfo->relation_index == 0); /* shouldn't be set yet */ fpinfo->relation_index = - list_length(root->parse->rtable) + list_length(root->join_rel_list); + list_length(root->parse->rtable) + + list_length(root->join_rel_list->items); return true; } diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..e90b47a7a5 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -2288,6 +2288,14 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node) WRITE_NODE_FIELD(partitioned_child_rels); } +static void +_outRelInfoList(StringInfo str, const RelInfoList *node) +{ + WRITE_NODE_TYPE("RELOPTINFOLIST"); + + WRITE_NODE_FIELD(items); +} + static void _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) { @@ -4077,6 +4085,9 @@ outNode(StringInfo str, const void *obj) case T_RelOptInfo: _outRelOptInfo(str, obj); break; + case T_RelInfoList: + _outRelInfoList(str, obj); + break; case T_IndexOptInfo: _outIndexOptInfo(str, obj); break; diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 6d897936d7..5f3209ac67 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -92,11 +92,11 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * * join_rel_level[] shouldn't be in use, so just Assert it isn't. */ - savelength = list_length(root->join_rel_list); - savehash = root->join_rel_hash; + savelength = list_length(root->join_rel_list->items); + savehash = root->join_rel_list->hash; Assert(root->join_rel_level == NULL); - root->join_rel_hash = NULL; + root->join_rel_list->hash = NULL; /* construct the best path for the given combination of relations */ joinrel = gimme_tree(root, tour, num_gene); @@ -121,9 +121,9 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * Restore join_rel_list to its former state, and put back original * hashtable if any. */ - root->join_rel_list = list_truncate(root->join_rel_list, - savelength); - root->join_rel_hash = savehash; + root->join_rel_list->items = list_truncate(root->join_rel_list->items, + savelength); + root->join_rel_list->hash = savehash; /* release all the memory acquired within gimme_tree */ MemoryContextSwitchTo(oldcxt); diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..5fa33ec200 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -65,8 +65,7 @@ query_planner(PlannerInfo *root, * NOTE: append_rel_list was set up by subquery_planner, so do not touch * here. */ - root->join_rel_list = NIL; - root->join_rel_hash = NULL; + root->join_rel_list = makeNode(RelInfoList); root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 374f93890b..ccd2a8bd33 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -31,11 +31,15 @@ #include "utils/hsearch.h" -typedef struct JoinHashEntry +/* + * An entry of a hash table that we use to make lookup for RelOptInfo + * structures more efficient. + */ +typedef struct RelInfoEntry { - Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; -} JoinHashEntry; + Relids relids; /* hash key --- MUST BE FIRST */ + void *data; +} RelInfoEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); @@ -379,11 +383,11 @@ find_base_rel(PlannerInfo *root, int relid) } /* - * build_join_rel_hash - * Construct the auxiliary hash table for join relations. + * build_rel_hash + * Construct the auxiliary hash table for relation specific data. */ static void -build_join_rel_hash(PlannerInfo *root) +build_rel_hash(RelInfoList *list) { HTAB *hashtab; HASHCTL hash_ctl; @@ -392,47 +396,50 @@ build_join_rel_hash(PlannerInfo *root) /* Create the hash table */ MemSet(&hash_ctl, 0, sizeof(hash_ctl)); hash_ctl.keysize = sizeof(Relids); - hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.entrysize = sizeof(RelInfoEntry); hash_ctl.hash = bitmap_hash; hash_ctl.match = bitmap_match; hash_ctl.hcxt = CurrentMemoryContext; - hashtab = hash_create("JoinRelHashTable", + hashtab = hash_create("RelHashTable", 256L, &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); - JoinHashEntry *hentry; + void *item = lfirst(l); + RelInfoEntry *hentry; bool found; + Relids relids; - hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), - HASH_ENTER, - &found); + Assert(IsA(item, RelOptInfo)); + relids = ((RelOptInfo *) item)->relids; + + hentry = (RelInfoEntry *) hash_search(hashtab, + &relids, + HASH_ENTER, + &found); Assert(!found); - hentry->join_rel = rel; + hentry->data = item; } - root->join_rel_hash = hashtab; + list->hash = hashtab; } /* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a set of RT indexes), - * or NULL if none exists. This is for join relations. + * find_rel_info + * Find a base or join relation entry. */ -RelOptInfo * -find_join_rel(PlannerInfo *root, Relids relids) +static void * +find_rel_info(RelInfoList *list, Relids relids) { /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ - if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) - build_join_rel_hash(root); + if (!list->hash && list_length(list->items) > 32) + build_rel_hash(list); /* * Use either hashtable lookup or linear search, as appropriate. @@ -442,34 +449,90 @@ find_join_rel(PlannerInfo *root, Relids relids) * so would force relids out of a register and thus probably slow down the * list-search case. */ - if (root->join_rel_hash) + if (list->hash) { Relids hashkey = relids; - JoinHashEntry *hentry; + RelInfoEntry *hentry; - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &hashkey, - HASH_FIND, - NULL); + hentry = (RelInfoEntry *) hash_search(list->hash, + &hashkey, + HASH_FIND, + NULL); if (hentry) - return hentry->join_rel; + return hentry->data; } else { ListCell *l; - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + void *item = lfirst(l); + Relids item_relids; - if (bms_equal(rel->relids, relids)) - return rel; + Assert(IsA(item, RelOptInfo)); + item_relids = ((RelOptInfo *) item)->relids; + + if (bms_equal(item_relids, relids)) + return item; } } return NULL; } +/* + * find_join_rel + * Returns relation entry corresponding to 'relids' (a set of RT indexes), + * or NULL if none exists. This is for join relations. + */ +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) +{ + return (RelOptInfo *) find_rel_info(root->join_rel_list, relids); +} + +/* + * add_rel_info + * Add relation specific info to a list, and also add it to the auxiliary + * hashtable if there is one. + */ +static void +add_rel_info(RelInfoList *list, void *data) +{ + Assert(IsA(data, RelOptInfo)); + + /* GEQO requires us to append the new joinrel to the end of the list! */ + list->items = lappend(list->items, data); + + /* store it into the auxiliary hashtable if there is one. */ + if (list->hash) + { + Relids relids; + RelInfoEntry *hentry; + bool found; + + relids = ((RelOptInfo *) data)->relids; + hentry = (RelInfoEntry *) hash_search(list->hash, + &relids, + HASH_ENTER, + &found); + Assert(!found); + hentry->data = data; + } +} + +/* + * add_join_rel + * Add given join relation to the list of join relations in the given + * PlannerInfo. + */ +static void +add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +{ + add_rel_info(root->join_rel_list, joinrel); +} + /* * set_foreign_rel_properties * Set up foreign-join fields if outer and inner relation are foreign @@ -520,32 +583,6 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, } } -/* - * add_join_rel - * Add given join relation to the list of join relations in the given - * PlannerInfo. Also add it to the auxiliary hashtable if there is one. - */ -static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) -{ - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); - - /* store it into the auxiliary hashtable if there is one. */ - if (root->join_rel_hash) - { - JoinHashEntry *hentry; - bool found; - - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), - HASH_ENTER, - &found); - Assert(!found); - hentry->join_rel = joinrel; - } -} - /* * build_join_rel * Returns relation entry corresponding to the union of two given rels, diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..316c1ecbb9 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -220,6 +220,7 @@ typedef enum NodeTag T_PlannerInfo, T_PlannerGlobal, T_RelOptInfo, + T_RelInfoList, T_IndexOptInfo, T_ForeignKeyOptInfo, T_ParamPathInfo, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..aca7993af3 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -236,15 +236,9 @@ struct PlannerInfo /* * join_rel_list is a list of all join-relation RelOptInfos we have - * considered in this planning run. For small problems we just scan the - * list to do lookups, but when there are many join relations we build a - * hash table for faster lookups. The hash table is present and valid - * when join_rel_hash is not NULL. Note that we still maintain the list - * even when using the hash table for lookups; this simplifies life for - * GEQO. + * considered in this planning run. */ - List *join_rel_list; /* list of join-relation RelOptInfos */ - struct HTAB *join_rel_hash; /* optional hashtable for join relations */ + struct RelInfoList *join_rel_list; /* list of join-relation RelOptInfos */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] @@ -748,6 +742,24 @@ typedef struct RelOptInfo ((rel)->part_scheme && (rel)->boundinfo && (rel)->nparts > 0 && \ (rel)->part_rels && (rel)->partexprs && (rel)->nullable_partexprs) +/* + * RelInfoList + * A list to store relation specific info and to retrieve it by relids. + * + * For small problems we just scan the list to do lookups, but when there are + * many relations we build a hash table for faster lookups. The hash table is + * present and valid when rel_hash is not NULL. Note that we still maintain + * the list even when using the hash table for lookups; this simplifies life + * for GEQO. + */ +typedef struct RelInfoList +{ + NodeTag type; + + List *items; + struct HTAB *hash; +} RelInfoList; + /* * IndexOptInfo * Per-index information for planning/optimization -- 2.20.1 --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=v15-0002-Aggregate-push-down-basic-functionality.patch ^ permalink raw reply [nested|flat] 5+ messages in thread
* [PATCH 1/3] Introduce RelInfoList structure. @ 2020-05-18 12:28 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2020-05-18 12:28 UTC (permalink / raw) This patch puts join_rel_list and join_rel_hash fields of PlannerInfo structure into a new structure RelInfoList. It also adjusts add_join_rel() and find_join_rel() functions so they only call add_rel_info() and find_rel_info() respectively. fetch_upper_rel() now uses the new API and the hash table as well because the list stored in root->upper_rels[UPPERREL_PARTIAL_GROUP_AGG] will contain many relations as soon as the aggregate push-down feature is added. --- contrib/postgres_fdw/postgres_fdw.c | 3 +- src/backend/nodes/outfuncs.c | 11 ++ src/backend/optimizer/geqo/geqo_eval.c | 12 +- src/backend/optimizer/plan/planmain.c | 3 +- src/backend/optimizer/util/relnode.c | 182 +++++++++++++++---------- src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 30 ++-- 7 files changed, 149 insertions(+), 93 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 9fc53cad68..a46834a377 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -5251,7 +5251,8 @@ foreign_join_ok(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, */ Assert(fpinfo->relation_index == 0); /* shouldn't be set yet */ fpinfo->relation_index = - list_length(root->parse->rtable) + list_length(root->join_rel_list); + list_length(root->parse->rtable) + + list_length(root->join_rel_list->items); return true; } diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index ebf3ce37aa..7ba92c6f28 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -2314,6 +2314,14 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node) WRITE_NODE_FIELD(partitioned_child_rels); } +static void +_outRelInfoList(StringInfo str, const RelInfoList *node) +{ + WRITE_NODE_TYPE("RELOPTINFOLIST"); + + WRITE_NODE_FIELD(items); +} + static void _outIndexOptInfo(StringInfo str, const IndexOptInfo *node) { @@ -4111,6 +4119,9 @@ outNode(StringInfo str, const void *obj) case T_RelOptInfo: _outRelOptInfo(str, obj); break; + case T_RelInfoList: + _outRelInfoList(str, obj); + break; case T_IndexOptInfo: _outIndexOptInfo(str, obj); break; diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index ff33acc7b6..6b04ab3c2a 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -92,11 +92,11 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * * join_rel_level[] shouldn't be in use, so just Assert it isn't. */ - savelength = list_length(root->join_rel_list); - savehash = root->join_rel_hash; + savelength = list_length(root->join_rel_list->items); + savehash = root->join_rel_list->hash; Assert(root->join_rel_level == NULL); - root->join_rel_hash = NULL; + root->join_rel_list->hash = NULL; /* construct the best path for the given combination of relations */ joinrel = gimme_tree(root, tour, num_gene); @@ -121,9 +121,9 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * Restore join_rel_list to its former state, and put back original * hashtable if any. */ - root->join_rel_list = list_truncate(root->join_rel_list, - savelength); - root->join_rel_hash = savehash; + root->join_rel_list->items = list_truncate(root->join_rel_list->items, + savelength); + root->join_rel_list->hash = savehash; /* release all the memory acquired within gimme_tree */ MemoryContextSwitchTo(oldcxt); diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..5fa33ec200 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -65,8 +65,7 @@ query_planner(PlannerInfo *root, * NOTE: append_rel_list was set up by subquery_planner, so do not touch * here. */ - root->join_rel_list = NIL; - root->join_rel_hash = NULL; + root->join_rel_list = makeNode(RelInfoList); root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index a203e6f1ff..a95e6364ae 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -32,11 +32,15 @@ #include "utils/lsyscache.h" -typedef struct JoinHashEntry +/* + * An entry of a hash table that we use to make lookup for RelOptInfo + * structures more efficient. + */ +typedef struct RelInfoEntry { - Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; -} JoinHashEntry; + Relids relids; /* hash key --- MUST BE FIRST */ + void *data; +} RelInfoEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); @@ -390,11 +394,11 @@ find_base_rel(PlannerInfo *root, int relid) } /* - * build_join_rel_hash - * Construct the auxiliary hash table for join relations. + * build_rel_hash + * Construct the auxiliary hash table for relation specific data. */ static void -build_join_rel_hash(PlannerInfo *root) +build_rel_hash(RelInfoList *list) { HTAB *hashtab; HASHCTL hash_ctl; @@ -403,47 +407,53 @@ build_join_rel_hash(PlannerInfo *root) /* Create the hash table */ MemSet(&hash_ctl, 0, sizeof(hash_ctl)); hash_ctl.keysize = sizeof(Relids); - hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.entrysize = sizeof(RelInfoEntry); hash_ctl.hash = bitmap_hash; hash_ctl.match = bitmap_match; hash_ctl.hcxt = CurrentMemoryContext; - hashtab = hash_create("JoinRelHashTable", + hashtab = hash_create("RelHashTable", 256L, &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); - JoinHashEntry *hentry; + void *item = lfirst(l); + RelInfoEntry *hentry; bool found; + Relids relids; + + Assert(IsA(item, RelOptInfo)); + relids = ((RelOptInfo *) item)->relids; - hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), - HASH_ENTER, - &found); + hentry = (RelInfoEntry *) hash_search(hashtab, + &relids, + HASH_ENTER, + &found); Assert(!found); - hentry->join_rel = rel; + hentry->data = item; } - root->join_rel_hash = hashtab; + list->hash = hashtab; } /* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a set of RT indexes), - * or NULL if none exists. This is for join relations. + * find_rel_info + * Find a base or join relation entry. */ -RelOptInfo * -find_join_rel(PlannerInfo *root, Relids relids) +static void * +find_rel_info(RelInfoList *list, Relids relids) { + if (list == NULL) + return NULL; + /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ - if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) - build_join_rel_hash(root); + if (!list->hash && list_length(list->items) > 32) + build_rel_hash(list); /* * Use either hashtable lookup or linear search, as appropriate. @@ -453,34 +463,90 @@ find_join_rel(PlannerInfo *root, Relids relids) * so would force relids out of a register and thus probably slow down the * list-search case. */ - if (root->join_rel_hash) + if (list->hash) { Relids hashkey = relids; - JoinHashEntry *hentry; + RelInfoEntry *hentry; - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &hashkey, - HASH_FIND, - NULL); + hentry = (RelInfoEntry *) hash_search(list->hash, + &hashkey, + HASH_FIND, + NULL); if (hentry) - return hentry->join_rel; + return hentry->data; } else { ListCell *l; - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + void *item = lfirst(l); + Relids item_relids = NULL; + + Assert(IsA(item, RelOptInfo)); - if (bms_equal(rel->relids, relids)) - return rel; + item_relids = ((RelOptInfo *) item)->relids; + if (bms_equal(item_relids, relids)) + return item; } } return NULL; } +/* + * find_join_rel + * Returns relation entry corresponding to 'relids' (a set of RT indexes), + * or NULL if none exists. This is for join relations. + */ +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) +{ + return (RelOptInfo *) find_rel_info(root->join_rel_list, relids); +} + +/* + * add_rel_info + * Add relation specific info to a list, and also add it to the auxiliary + * hashtable if there is one. + */ +static void +add_rel_info(RelInfoList *list, void *data) +{ + Assert(IsA(data, RelOptInfo)); + + /* GEQO requires us to append the new joinrel to the end of the list! */ + list->items = lappend(list->items, data); + + /* store it into the auxiliary hashtable if there is one. */ + if (list->hash) + { + Relids relids; + RelInfoEntry *hentry; + bool found; + + relids = ((RelOptInfo *) data)->relids; + hentry = (RelInfoEntry *) hash_search(list->hash, + &relids, + HASH_ENTER, + &found); + Assert(!found); + hentry->data = data; + } +} + +/* + * add_join_rel + * Add given join relation to the list of join relations in the given + * PlannerInfo. + */ +static void +add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +{ + add_rel_info(root->join_rel_list, joinrel); +} + /* * set_foreign_rel_properties * Set up foreign-join fields if outer and inner relation are foreign @@ -531,32 +597,6 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, } } -/* - * add_join_rel - * Add given join relation to the list of join relations in the given - * PlannerInfo. Also add it to the auxiliary hashtable if there is one. - */ -static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) -{ - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); - - /* store it into the auxiliary hashtable if there is one. */ - if (root->join_rel_hash) - { - JoinHashEntry *hentry; - bool found; - - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), - HASH_ENTER, - &found); - Assert(!found); - hentry->join_rel = joinrel; - } -} - /* * build_join_rel * Returns relation entry corresponding to the union of two given rels, @@ -1191,22 +1231,14 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) { + RelInfoList *list = &root->upper_rels[kind]; RelOptInfo *upperrel; - ListCell *lc; - - /* - * For the moment, our indexing data structure is just a List for each - * relation kind. If we ever get so many of one kind that this stops - * working well, we can improve it. No code outside this function should - * assume anything about how to find a particular upperrel. - */ /* If we already made this upperrel for the query, return it */ - foreach(lc, root->upper_rels[kind]) + if (list) { - upperrel = (RelOptInfo *) lfirst(lc); - - if (bms_equal(upperrel->relids, relids)) + upperrel = find_rel_info(list, relids); + if (upperrel) return upperrel; } @@ -1225,7 +1257,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) upperrel->cheapest_unique_path = NULL; upperrel->cheapest_parameterized_paths = NIL; - root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); + add_rel_info(&root->upper_rels[kind], upperrel); return upperrel; } diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 381d84b4e4..be5ab273f0 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -222,6 +222,7 @@ typedef enum NodeTag T_PlannerInfo, T_PlannerGlobal, T_RelOptInfo, + T_RelInfoList, T_IndexOptInfo, T_ForeignKeyOptInfo, T_ParamPathInfo, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 485d1b06c9..44374de796 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -93,6 +93,23 @@ typedef enum InheritanceKind INHKIND_PARTITIONED } InheritanceKind; +/* + * Hashed list to store relation specific info and to retrieve it by relids. + * + * For small problems we just scan the list to do lookups, but when there are + * many relations we build a hash table for faster lookups. The hash table is + * present and valid when rel_hash is not NULL. Note that we still maintain + * the list even when using the hash table for lookups; this simplifies life + * for GEQO. + */ +typedef struct RelInfoList +{ + NodeTag type; + + List *items; + struct HTAB *hash; +} RelInfoList; + /*---------- * PlannerGlobal * Global information for planning/optimization @@ -236,15 +253,9 @@ struct PlannerInfo /* * join_rel_list is a list of all join-relation RelOptInfos we have - * considered in this planning run. For small problems we just scan the - * list to do lookups, but when there are many join relations we build a - * hash table for faster lookups. The hash table is present and valid - * when join_rel_hash is not NULL. Note that we still maintain the list - * even when using the hash table for lookups; this simplifies life for - * GEQO. + * considered in this planning run. */ - List *join_rel_list; /* list of join-relation RelOptInfos */ - struct HTAB *join_rel_hash; /* optional hashtable for join relations */ + struct RelInfoList *join_rel_list; /* list of join-relation RelOptInfos */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] @@ -308,7 +319,8 @@ struct PlannerInfo List *initial_rels; /* RelOptInfos we are now trying to join */ /* Use fetch_upper_rel() to get any particular upper rel */ - List *upper_rels[UPPERREL_FINAL + 1]; /* upper-rel RelOptInfos */ + RelInfoList upper_rels[UPPERREL_FINAL + 1]; /* upper-rel RelOptInfos */ + /* Result tlists chosen by grouping_planner for upper-stage processing */ struct PathTarget *upper_targets[UPPERREL_FINAL + 1]; -- 2.20.1 --=-=-= Content-Type: text/x-diff Content-Disposition: attachment; filename=v16-0002-Aggregate-push-down-basic-functionality.patch ^ permalink raw reply [nested|flat] 5+ messages in thread
* [PATCH 1/3] Introduce RelInfoList structure. @ 2022-11-04 14:02 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2022-11-04 14:02 UTC (permalink / raw) This patch puts join_rel_list and join_rel_hash fields of PlannerInfo structure into a new structure RelInfoList. It also adjusts add_join_rel() and find_join_rel() functions so they only call add_rel_info() and find_rel_info() respectively. fetch_upper_rel() now uses the new API and the hash table as well because the list stored in root->upper_rels[UPPERREL_PARTIAL_GROUP_AGG] will contain many relations as soon as the aggregate push-down feature is added. --- contrib/postgres_fdw/postgres_fdw.c | 3 +- src/backend/optimizer/geqo/geqo_eval.c | 12 +- src/backend/optimizer/plan/planmain.c | 3 +- src/backend/optimizer/util/relnode.c | 170 ++++++++++++++----------- src/include/nodes/pathnodes.h | 31 +++-- 5 files changed, 126 insertions(+), 93 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 8d7500abfb..bb1125e57c 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -5777,7 +5777,8 @@ foreign_join_ok(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, */ Assert(fpinfo->relation_index == 0); /* shouldn't be set yet */ fpinfo->relation_index = - list_length(root->parse->rtable) + list_length(root->join_rel_list); + list_length(root->parse->rtable) + + list_length(root->join_rel_list->items); return true; } diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 004481d608..7ad0baaa0f 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -92,11 +92,11 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * * join_rel_level[] shouldn't be in use, so just Assert it isn't. */ - savelength = list_length(root->join_rel_list); - savehash = root->join_rel_hash; + savelength = list_length(root->join_rel_list->items); + savehash = root->join_rel_list->hash; Assert(root->join_rel_level == NULL); - root->join_rel_hash = NULL; + root->join_rel_list->hash = NULL; /* construct the best path for the given combination of relations */ joinrel = gimme_tree(root, tour, num_gene); @@ -121,9 +121,9 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * Restore join_rel_list to its former state, and put back original * hashtable if any. */ - root->join_rel_list = list_truncate(root->join_rel_list, - savelength); - root->join_rel_hash = savehash; + root->join_rel_list->items = list_truncate(root->join_rel_list->items, + savelength); + root->join_rel_list->hash = savehash; /* release all the memory acquired within gimme_tree */ MemoryContextSwitchTo(oldcxt); diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 63deed27c9..55de28f073 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -65,8 +65,7 @@ query_planner(PlannerInfo *root, * NOTE: append_rel_list was set up by subquery_planner, so do not touch * here. */ - root->join_rel_list = NIL; - root->join_rel_hash = NULL; + root->join_rel_list = makeNode(RelInfoList); root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 1786a3dadd..c75d2d1f19 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -32,11 +32,15 @@ #include "utils/lsyscache.h" -typedef struct JoinHashEntry +/* + * An entry of a hash table that we use to make lookup for RelOptInfo + * structures more efficient. + */ +typedef struct RelInfoEntry { - Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; -} JoinHashEntry; + Relids relids; /* hash key --- MUST BE FIRST */ + void *data; +} RelInfoEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); @@ -389,11 +393,11 @@ find_base_rel(PlannerInfo *root, int relid) } /* - * build_join_rel_hash - * Construct the auxiliary hash table for join relations. + * build_rel_hash + * Construct the auxiliary hash table for relation specific data. */ static void -build_join_rel_hash(PlannerInfo *root) +build_rel_hash(RelInfoList *list) { HTAB *hashtab; HASHCTL hash_ctl; @@ -401,47 +405,49 @@ build_join_rel_hash(PlannerInfo *root) /* Create the hash table */ hash_ctl.keysize = sizeof(Relids); - hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.entrysize = sizeof(RelInfoEntry); hash_ctl.hash = bitmap_hash; hash_ctl.match = bitmap_match; hash_ctl.hcxt = CurrentMemoryContext; - hashtab = hash_create("JoinRelHashTable", + hashtab = hash_create("RelHashTable", 256L, &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); - JoinHashEntry *hentry; + RelOptInfo *rel = lfirst_node(RelOptInfo, l); + RelInfoEntry *hentry; bool found; - hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), - HASH_ENTER, - &found); + hentry = (RelInfoEntry *) hash_search(hashtab, + &rel->relids, + HASH_ENTER, + &found); Assert(!found); - hentry->join_rel = rel; + hentry->data = rel; } - root->join_rel_hash = hashtab; + list->hash = hashtab; } /* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a set of RT indexes), - * or NULL if none exists. This is for join relations. + * find_rel_info + * Find a base or join relation entry. */ -RelOptInfo * -find_join_rel(PlannerInfo *root, Relids relids) +static void * +find_rel_info(RelInfoList *list, Relids relids) { + if (list == NULL) + return NULL; + /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ - if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) - build_join_rel_hash(root); + if (!list->hash && list_length(list->items) > 32) + build_rel_hash(list); /* * Use either hashtable lookup or linear search, as appropriate. @@ -451,34 +457,82 @@ find_join_rel(PlannerInfo *root, Relids relids) * so would force relids out of a register and thus probably slow down the * list-search case. */ - if (root->join_rel_hash) + if (list->hash) { Relids hashkey = relids; - JoinHashEntry *hentry; + RelInfoEntry *hentry; - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &hashkey, - HASH_FIND, - NULL); + hentry = (RelInfoEntry *) hash_search(list->hash, + &hashkey, + HASH_FIND, + NULL); if (hentry) - return hentry->join_rel; + return hentry->data; } else { ListCell *l; - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + RelOptInfo *item = lfirst_node(RelOptInfo, l); - if (bms_equal(rel->relids, relids)) - return rel; + if (bms_equal(item->relids, relids)) + return item; } } return NULL; } +/* + * find_join_rel + * Returns relation entry corresponding to 'relids' (a set of RT indexes), + * or NULL if none exists. This is for join relations. + */ +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) +{ + return (RelOptInfo *) find_rel_info(root->join_rel_list, relids); +} + +/* + * add_rel_info + * Add relation specific info to a list, and also add it to the auxiliary + * hashtable if there is one. + */ +static void +add_rel_info(RelInfoList *list, RelOptInfo *rel) +{ + /* GEQO requires us to append the new joinrel to the end of the list! */ + list->items = lappend(list->items, rel); + + /* store it into the auxiliary hashtable if there is one. */ + if (list->hash) + { + RelInfoEntry *hentry; + bool found; + + hentry = (RelInfoEntry *) hash_search(list->hash, + &rel->relids, + HASH_ENTER, + &found); + Assert(!found); + hentry->data = rel; + } +} + +/* + * add_join_rel + * Add given join relation to the list of join relations in the given + * PlannerInfo. + */ +static void +add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +{ + add_rel_info(root->join_rel_list, joinrel); +} + /* * set_foreign_rel_properties * Set up foreign-join fields if outer and inner relation are foreign @@ -529,32 +583,6 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, } } -/* - * add_join_rel - * Add given join relation to the list of join relations in the given - * PlannerInfo. Also add it to the auxiliary hashtable if there is one. - */ -static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) -{ - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); - - /* store it into the auxiliary hashtable if there is one. */ - if (root->join_rel_hash) - { - JoinHashEntry *hentry; - bool found; - - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), - HASH_ENTER, - &found); - Assert(!found); - hentry->join_rel = joinrel; - } -} - /* * build_join_rel * Returns relation entry corresponding to the union of two given rels, @@ -1223,22 +1251,14 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) { + RelInfoList *list = &root->upper_rels[kind]; RelOptInfo *upperrel; - ListCell *lc; - - /* - * For the moment, our indexing data structure is just a List for each - * relation kind. If we ever get so many of one kind that this stops - * working well, we can improve it. No code outside this function should - * assume anything about how to find a particular upperrel. - */ /* If we already made this upperrel for the query, return it */ - foreach(lc, root->upper_rels[kind]) + if (list) { - upperrel = (RelOptInfo *) lfirst(lc); - - if (bms_equal(upperrel->relids, relids)) + upperrel = find_rel_info(list, relids); + if (upperrel) return upperrel; } @@ -1257,7 +1277,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) upperrel->cheapest_unique_path = NULL; upperrel->cheapest_parameterized_paths = NIL; - root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); + add_rel_info(&root->upper_rels[kind], upperrel); return upperrel; } diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 09342d128d..0ca7d5ab51 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -80,6 +80,25 @@ typedef enum UpperRelationKind /* NB: UPPERREL_FINAL must be last enum entry; it's used to size arrays */ } UpperRelationKind; +/* + * Hashed list to store relation specific info and to retrieve it by relids. + * + * For small problems we just scan the list to do lookups, but when there are + * many relations we build a hash table for faster lookups. The hash table is + * present and valid when rel_hash is not NULL. Note that we still maintain + * the list even when using the hash table for lookups; this simplifies life + * for GEQO. + */ +typedef struct RelInfoList +{ + pg_node_attr(no_copy_equal, no_read) + + NodeTag type; + + List *items; + struct HTAB *hash pg_node_attr(read_write_ignore); +} RelInfoList; + /*---------- * PlannerGlobal * Global information for planning/optimization @@ -260,15 +279,9 @@ struct PlannerInfo /* * join_rel_list is a list of all join-relation RelOptInfos we have - * considered in this planning run. For small problems we just scan the - * list to do lookups, but when there are many join relations we build a - * hash table for faster lookups. The hash table is present and valid - * when join_rel_hash is not NULL. Note that we still maintain the list - * even when using the hash table for lookups; this simplifies life for - * GEQO. + * considered in this planning run. */ - List *join_rel_list; - struct HTAB *join_rel_hash pg_node_attr(read_write_ignore); + struct RelInfoList *join_rel_list; /* list of join-relation RelOptInfos */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] @@ -395,7 +408,7 @@ struct PlannerInfo * Upper-rel RelOptInfos. Use fetch_upper_rel() to get any particular * upper rel. */ - List *upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); + RelInfoList upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore);; /* Result tlists chosen by grouping_planner for upper-stage processing */ struct PathTarget *upper_targets[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); -- 2.31.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=v20-0002-Aggregate-push-down-basic-functionality.patch ^ permalink raw reply [nested|flat] 5+ messages in thread
* [PATCH 1/3] Introduce RelInfoList structure. @ 2022-11-17 09:41 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2022-11-17 09:41 UTC (permalink / raw) This patch puts join_rel_list and join_rel_hash fields of PlannerInfo structure into a new structure RelInfoList. It also adjusts add_join_rel() and find_join_rel() functions so they only call add_rel_info() and find_rel_info() respectively. fetch_upper_rel() now uses the new API and the hash table as well because the list stored in root->upper_rels[UPPERREL_PARTIAL_GROUP_AGG] will contain many relations as soon as the aggregate push-down feature is added. --- contrib/postgres_fdw/postgres_fdw.c | 3 +- src/backend/optimizer/geqo/geqo_eval.c | 12 +- src/backend/optimizer/plan/planmain.c | 3 +- src/backend/optimizer/util/relnode.c | 170 ++++++++++++++----------- src/include/nodes/pathnodes.h | 31 +++-- 5 files changed, 126 insertions(+), 93 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 8d7500abfb..bb1125e57c 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -5777,7 +5777,8 @@ foreign_join_ok(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, */ Assert(fpinfo->relation_index == 0); /* shouldn't be set yet */ fpinfo->relation_index = - list_length(root->parse->rtable) + list_length(root->join_rel_list); + list_length(root->parse->rtable) + + list_length(root->join_rel_list->items); return true; } diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 004481d608..7ad0baaa0f 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -92,11 +92,11 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * * join_rel_level[] shouldn't be in use, so just Assert it isn't. */ - savelength = list_length(root->join_rel_list); - savehash = root->join_rel_hash; + savelength = list_length(root->join_rel_list->items); + savehash = root->join_rel_list->hash; Assert(root->join_rel_level == NULL); - root->join_rel_hash = NULL; + root->join_rel_list->hash = NULL; /* construct the best path for the given combination of relations */ joinrel = gimme_tree(root, tour, num_gene); @@ -121,9 +121,9 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * Restore join_rel_list to its former state, and put back original * hashtable if any. */ - root->join_rel_list = list_truncate(root->join_rel_list, - savelength); - root->join_rel_hash = savehash; + root->join_rel_list->items = list_truncate(root->join_rel_list->items, + savelength); + root->join_rel_list->hash = savehash; /* release all the memory acquired within gimme_tree */ MemoryContextSwitchTo(oldcxt); diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 63deed27c9..55de28f073 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -65,8 +65,7 @@ query_planner(PlannerInfo *root, * NOTE: append_rel_list was set up by subquery_planner, so do not touch * here. */ - root->join_rel_list = NIL; - root->join_rel_hash = NULL; + root->join_rel_list = makeNode(RelInfoList); root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index d7b4434e7f..94720865f4 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -32,11 +32,15 @@ #include "utils/lsyscache.h" -typedef struct JoinHashEntry +/* + * An entry of a hash table that we use to make lookup for RelOptInfo + * structures more efficient. + */ +typedef struct RelInfoEntry { - Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; -} JoinHashEntry; + Relids relids; /* hash key --- MUST BE FIRST */ + void *data; +} RelInfoEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); @@ -376,11 +380,11 @@ find_base_rel(PlannerInfo *root, int relid) } /* - * build_join_rel_hash - * Construct the auxiliary hash table for join relations. + * build_rel_hash + * Construct the auxiliary hash table for relation specific data. */ static void -build_join_rel_hash(PlannerInfo *root) +build_rel_hash(RelInfoList *list) { HTAB *hashtab; HASHCTL hash_ctl; @@ -388,47 +392,49 @@ build_join_rel_hash(PlannerInfo *root) /* Create the hash table */ hash_ctl.keysize = sizeof(Relids); - hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.entrysize = sizeof(RelInfoEntry); hash_ctl.hash = bitmap_hash; hash_ctl.match = bitmap_match; hash_ctl.hcxt = CurrentMemoryContext; - hashtab = hash_create("JoinRelHashTable", + hashtab = hash_create("RelHashTable", 256L, &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); - JoinHashEntry *hentry; + RelOptInfo *rel = lfirst_node(RelOptInfo, l); + RelInfoEntry *hentry; bool found; - hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), - HASH_ENTER, - &found); + hentry = (RelInfoEntry *) hash_search(hashtab, + &rel->relids, + HASH_ENTER, + &found); Assert(!found); - hentry->join_rel = rel; + hentry->data = rel; } - root->join_rel_hash = hashtab; + list->hash = hashtab; } /* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a set of RT indexes), - * or NULL if none exists. This is for join relations. + * find_rel_info + * Find a base or join relation entry. */ -RelOptInfo * -find_join_rel(PlannerInfo *root, Relids relids) +static void * +find_rel_info(RelInfoList *list, Relids relids) { + if (list == NULL) + return NULL; + /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ - if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) - build_join_rel_hash(root); + if (!list->hash && list_length(list->items) > 32) + build_rel_hash(list); /* * Use either hashtable lookup or linear search, as appropriate. @@ -438,34 +444,82 @@ find_join_rel(PlannerInfo *root, Relids relids) * so would force relids out of a register and thus probably slow down the * list-search case. */ - if (root->join_rel_hash) + if (list->hash) { Relids hashkey = relids; - JoinHashEntry *hentry; + RelInfoEntry *hentry; - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &hashkey, - HASH_FIND, - NULL); + hentry = (RelInfoEntry *) hash_search(list->hash, + &hashkey, + HASH_FIND, + NULL); if (hentry) - return hentry->join_rel; + return hentry->data; } else { ListCell *l; - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + RelOptInfo *item = lfirst_node(RelOptInfo, l); - if (bms_equal(rel->relids, relids)) - return rel; + if (bms_equal(item->relids, relids)) + return item; } } return NULL; } +/* + * find_join_rel + * Returns relation entry corresponding to 'relids' (a set of RT indexes), + * or NULL if none exists. This is for join relations. + */ +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) +{ + return (RelOptInfo *) find_rel_info(root->join_rel_list, relids); +} + +/* + * add_rel_info + * Add relation specific info to a list, and also add it to the auxiliary + * hashtable if there is one. + */ +static void +add_rel_info(RelInfoList *list, RelOptInfo *rel) +{ + /* GEQO requires us to append the new joinrel to the end of the list! */ + list->items = lappend(list->items, rel); + + /* store it into the auxiliary hashtable if there is one. */ + if (list->hash) + { + RelInfoEntry *hentry; + bool found; + + hentry = (RelInfoEntry *) hash_search(list->hash, + &rel->relids, + HASH_ENTER, + &found); + Assert(!found); + hentry->data = rel; + } +} + +/* + * add_join_rel + * Add given join relation to the list of join relations in the given + * PlannerInfo. + */ +static void +add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +{ + add_rel_info(root->join_rel_list, joinrel); +} + /* * set_foreign_rel_properties * Set up foreign-join fields if outer and inner relation are foreign @@ -516,32 +570,6 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, } } -/* - * add_join_rel - * Add given join relation to the list of join relations in the given - * PlannerInfo. Also add it to the auxiliary hashtable if there is one. - */ -static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) -{ - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); - - /* store it into the auxiliary hashtable if there is one. */ - if (root->join_rel_hash) - { - JoinHashEntry *hentry; - bool found; - - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), - HASH_ENTER, - &found); - Assert(!found); - hentry->join_rel = joinrel; - } -} - /* * build_join_rel * Returns relation entry corresponding to the union of two given rels, @@ -1210,22 +1238,14 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) { + RelInfoList *list = &root->upper_rels[kind]; RelOptInfo *upperrel; - ListCell *lc; - - /* - * For the moment, our indexing data structure is just a List for each - * relation kind. If we ever get so many of one kind that this stops - * working well, we can improve it. No code outside this function should - * assume anything about how to find a particular upperrel. - */ /* If we already made this upperrel for the query, return it */ - foreach(lc, root->upper_rels[kind]) + if (list) { - upperrel = (RelOptInfo *) lfirst(lc); - - if (bms_equal(upperrel->relids, relids)) + upperrel = find_rel_info(list, relids); + if (upperrel) return upperrel; } @@ -1244,7 +1264,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) upperrel->cheapest_unique_path = NULL; upperrel->cheapest_parameterized_paths = NIL; - root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); + add_rel_info(&root->upper_rels[kind], upperrel); return upperrel; } diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index a544b313d3..869854e235 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -80,6 +80,25 @@ typedef enum UpperRelationKind /* NB: UPPERREL_FINAL must be last enum entry; it's used to size arrays */ } UpperRelationKind; +/* + * Hashed list to store relation specific info and to retrieve it by relids. + * + * For small problems we just scan the list to do lookups, but when there are + * many relations we build a hash table for faster lookups. The hash table is + * present and valid when rel_hash is not NULL. Note that we still maintain + * the list even when using the hash table for lookups; this simplifies life + * for GEQO. + */ +typedef struct RelInfoList +{ + pg_node_attr(no_copy_equal, no_read) + + NodeTag type; + + List *items; + struct HTAB *hash pg_node_attr(read_write_ignore); +} RelInfoList; + /*---------- * PlannerGlobal * Global information for planning/optimization @@ -260,15 +279,9 @@ struct PlannerInfo /* * join_rel_list is a list of all join-relation RelOptInfos we have - * considered in this planning run. For small problems we just scan the - * list to do lookups, but when there are many join relations we build a - * hash table for faster lookups. The hash table is present and valid - * when join_rel_hash is not NULL. Note that we still maintain the list - * even when using the hash table for lookups; this simplifies life for - * GEQO. + * considered in this planning run. */ - List *join_rel_list; - struct HTAB *join_rel_hash pg_node_attr(read_write_ignore); + struct RelInfoList *join_rel_list; /* list of join-relation RelOptInfos */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] @@ -395,7 +408,7 @@ struct PlannerInfo * Upper-rel RelOptInfos. Use fetch_upper_rel() to get any particular * upper rel. */ - List *upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); + RelInfoList upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore);; /* Result tlists chosen by grouping_planner for upper-stage processing */ struct PathTarget *upper_targets[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); -- 2.31.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=v22-0002-Aggregate-push-down-basic-functionality.patch ^ permalink raw reply [nested|flat] 5+ messages in thread
* [PATCH 1/3] Introduce RelInfoList structure. @ 2023-01-04 13:41 Antonin Houska <[email protected]> 0 siblings, 0 replies; 5+ messages in thread From: Antonin Houska @ 2023-01-04 13:41 UTC (permalink / raw) This patch puts join_rel_list and join_rel_hash fields of PlannerInfo structure into a new structure RelInfoList. It also adjusts add_join_rel() and find_join_rel() functions so they only call add_rel_info() and find_rel_info() respectively. fetch_upper_rel() now uses the new API and the hash table as well because the list stored in root->upper_rels[UPPERREL_PARTIAL_GROUP_AGG] will contain many relations as soon as the aggregate push-down feature is added. --- contrib/postgres_fdw/postgres_fdw.c | 3 +- src/backend/optimizer/geqo/geqo_eval.c | 12 +- src/backend/optimizer/plan/planmain.c | 3 +- src/backend/optimizer/util/relnode.c | 170 ++++++++++++++----------- src/include/nodes/pathnodes.h | 31 +++-- 5 files changed, 126 insertions(+), 93 deletions(-) diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c index 332b4a5cde..231ee967b0 100644 --- a/contrib/postgres_fdw/postgres_fdw.c +++ b/contrib/postgres_fdw/postgres_fdw.c @@ -5960,7 +5960,8 @@ foreign_join_ok(PlannerInfo *root, RelOptInfo *joinrel, JoinType jointype, */ Assert(fpinfo->relation_index == 0); /* shouldn't be set yet */ fpinfo->relation_index = - list_length(root->parse->rtable) + list_length(root->join_rel_list); + list_length(root->parse->rtable) + + list_length(root->join_rel_list->items); return true; } diff --git a/src/backend/optimizer/geqo/geqo_eval.c b/src/backend/optimizer/geqo/geqo_eval.c index 6d5d1a7eb2..1df62b71a9 100644 --- a/src/backend/optimizer/geqo/geqo_eval.c +++ b/src/backend/optimizer/geqo/geqo_eval.c @@ -92,11 +92,11 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * * join_rel_level[] shouldn't be in use, so just Assert it isn't. */ - savelength = list_length(root->join_rel_list); - savehash = root->join_rel_hash; + savelength = list_length(root->join_rel_list->items); + savehash = root->join_rel_list->hash; Assert(root->join_rel_level == NULL); - root->join_rel_hash = NULL; + root->join_rel_list->hash = NULL; /* construct the best path for the given combination of relations */ joinrel = gimme_tree(root, tour, num_gene); @@ -121,9 +121,9 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene) * Restore join_rel_list to its former state, and put back original * hashtable if any. */ - root->join_rel_list = list_truncate(root->join_rel_list, - savelength); - root->join_rel_hash = savehash; + root->join_rel_list->items = list_truncate(root->join_rel_list->items, + savelength); + root->join_rel_list->hash = savehash; /* release all the memory acquired within gimme_tree */ MemoryContextSwitchTo(oldcxt); diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 4c17407e5d..b4bfbe6e32 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -65,8 +65,7 @@ query_planner(PlannerInfo *root, * NOTE: append_rel_list was set up by subquery_planner, so do not touch * here. */ - root->join_rel_list = NIL; - root->join_rel_hash = NULL; + root->join_rel_list = makeNode(RelInfoList); root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 75bc20c7c9..f8ccd1a5db 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -33,11 +33,15 @@ #include "utils/lsyscache.h" -typedef struct JoinHashEntry +/* + * An entry of a hash table that we use to make lookup for RelOptInfo + * structures more efficient. + */ +typedef struct RelInfoEntry { - Relids join_relids; /* hash key --- MUST BE FIRST */ - RelOptInfo *join_rel; -} JoinHashEntry; + Relids relids; /* hash key --- MUST BE FIRST */ + void *data; +} RelInfoEntry; static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *input_rel); @@ -395,11 +399,11 @@ find_base_rel(PlannerInfo *root, int relid) } /* - * build_join_rel_hash - * Construct the auxiliary hash table for join relations. + * build_rel_hash + * Construct the auxiliary hash table for relation specific data. */ static void -build_join_rel_hash(PlannerInfo *root) +build_rel_hash(RelInfoList *list) { HTAB *hashtab; HASHCTL hash_ctl; @@ -407,47 +411,49 @@ build_join_rel_hash(PlannerInfo *root) /* Create the hash table */ hash_ctl.keysize = sizeof(Relids); - hash_ctl.entrysize = sizeof(JoinHashEntry); + hash_ctl.entrysize = sizeof(RelInfoEntry); hash_ctl.hash = bitmap_hash; hash_ctl.match = bitmap_match; hash_ctl.hcxt = CurrentMemoryContext; - hashtab = hash_create("JoinRelHashTable", + hashtab = hash_create("RelHashTable", 256L, &hash_ctl, HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT); /* Insert all the already-existing joinrels */ - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); - JoinHashEntry *hentry; + RelOptInfo *rel = lfirst_node(RelOptInfo, l); + RelInfoEntry *hentry; bool found; - hentry = (JoinHashEntry *) hash_search(hashtab, - &(rel->relids), - HASH_ENTER, - &found); + hentry = (RelInfoEntry *) hash_search(hashtab, + &rel->relids, + HASH_ENTER, + &found); Assert(!found); - hentry->join_rel = rel; + hentry->data = rel; } - root->join_rel_hash = hashtab; + list->hash = hashtab; } /* - * find_join_rel - * Returns relation entry corresponding to 'relids' (a set of RT indexes), - * or NULL if none exists. This is for join relations. + * find_rel_info + * Find a base or join relation entry. */ -RelOptInfo * -find_join_rel(PlannerInfo *root, Relids relids) +static void * +find_rel_info(RelInfoList *list, Relids relids) { + if (list == NULL) + return NULL; + /* * Switch to using hash lookup when list grows "too long". The threshold * is arbitrary and is known only here. */ - if (!root->join_rel_hash && list_length(root->join_rel_list) > 32) - build_join_rel_hash(root); + if (!list->hash && list_length(list->items) > 32) + build_rel_hash(list); /* * Use either hashtable lookup or linear search, as appropriate. @@ -457,34 +463,82 @@ find_join_rel(PlannerInfo *root, Relids relids) * so would force relids out of a register and thus probably slow down the * list-search case. */ - if (root->join_rel_hash) + if (list->hash) { Relids hashkey = relids; - JoinHashEntry *hentry; + RelInfoEntry *hentry; - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &hashkey, - HASH_FIND, - NULL); + hentry = (RelInfoEntry *) hash_search(list->hash, + &hashkey, + HASH_FIND, + NULL); if (hentry) - return hentry->join_rel; + return hentry->data; } else { ListCell *l; - foreach(l, root->join_rel_list) + foreach(l, list->items) { - RelOptInfo *rel = (RelOptInfo *) lfirst(l); + RelOptInfo *item = lfirst_node(RelOptInfo, l); - if (bms_equal(rel->relids, relids)) - return rel; + if (bms_equal(item->relids, relids)) + return item; } } return NULL; } +/* + * find_join_rel + * Returns relation entry corresponding to 'relids' (a set of RT indexes), + * or NULL if none exists. This is for join relations. + */ +RelOptInfo * +find_join_rel(PlannerInfo *root, Relids relids) +{ + return (RelOptInfo *) find_rel_info(root->join_rel_list, relids); +} + +/* + * add_rel_info + * Add relation specific info to a list, and also add it to the auxiliary + * hashtable if there is one. + */ +static void +add_rel_info(RelInfoList *list, RelOptInfo *rel) +{ + /* GEQO requires us to append the new joinrel to the end of the list! */ + list->items = lappend(list->items, rel); + + /* store it into the auxiliary hashtable if there is one. */ + if (list->hash) + { + RelInfoEntry *hentry; + bool found; + + hentry = (RelInfoEntry *) hash_search(list->hash, + &rel->relids, + HASH_ENTER, + &found); + Assert(!found); + hentry->data = rel; + } +} + +/* + * add_join_rel + * Add given join relation to the list of join relations in the given + * PlannerInfo. + */ +static void +add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) +{ + add_rel_info(root->join_rel_list, joinrel); +} + /* * set_foreign_rel_properties * Set up foreign-join fields if outer and inner relation are foreign @@ -535,32 +589,6 @@ set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel, } } -/* - * add_join_rel - * Add given join relation to the list of join relations in the given - * PlannerInfo. Also add it to the auxiliary hashtable if there is one. - */ -static void -add_join_rel(PlannerInfo *root, RelOptInfo *joinrel) -{ - /* GEQO requires us to append the new joinrel to the end of the list! */ - root->join_rel_list = lappend(root->join_rel_list, joinrel); - - /* store it into the auxiliary hashtable if there is one. */ - if (root->join_rel_hash) - { - JoinHashEntry *hentry; - bool found; - - hentry = (JoinHashEntry *) hash_search(root->join_rel_hash, - &(joinrel->relids), - HASH_ENTER, - &found); - Assert(!found); - hentry->join_rel = joinrel; - } -} - /* * build_join_rel * Returns relation entry corresponding to the union of two given rels, @@ -1229,22 +1257,14 @@ subbuild_joinrel_joinlist(RelOptInfo *joinrel, RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) { + RelInfoList *list = &root->upper_rels[kind]; RelOptInfo *upperrel; - ListCell *lc; - - /* - * For the moment, our indexing data structure is just a List for each - * relation kind. If we ever get so many of one kind that this stops - * working well, we can improve it. No code outside this function should - * assume anything about how to find a particular upperrel. - */ /* If we already made this upperrel for the query, return it */ - foreach(lc, root->upper_rels[kind]) + if (list) { - upperrel = (RelOptInfo *) lfirst(lc); - - if (bms_equal(upperrel->relids, relids)) + upperrel = find_rel_info(list, relids); + if (upperrel) return upperrel; } @@ -1263,7 +1283,7 @@ fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids) upperrel->cheapest_unique_path = NULL; upperrel->cheapest_parameterized_paths = NIL; - root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel); + add_rel_info(&root->upper_rels[kind], upperrel); return upperrel; } diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 1827e50647..9790c058f9 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -80,6 +80,25 @@ typedef enum UpperRelationKind /* NB: UPPERREL_FINAL must be last enum entry; it's used to size arrays */ } UpperRelationKind; +/* + * Hashed list to store relation specific info and to retrieve it by relids. + * + * For small problems we just scan the list to do lookups, but when there are + * many relations we build a hash table for faster lookups. The hash table is + * present and valid when rel_hash is not NULL. Note that we still maintain + * the list even when using the hash table for lookups; this simplifies life + * for GEQO. + */ +typedef struct RelInfoList +{ + pg_node_attr(no_copy_equal, no_read) + + NodeTag type; + + List *items; + struct HTAB *hash pg_node_attr(read_write_ignore); +} RelInfoList; + /*---------- * PlannerGlobal * Global information for planning/optimization @@ -266,15 +285,9 @@ struct PlannerInfo /* * join_rel_list is a list of all join-relation RelOptInfos we have - * considered in this planning run. For small problems we just scan the - * list to do lookups, but when there are many join relations we build a - * hash table for faster lookups. The hash table is present and valid - * when join_rel_hash is not NULL. Note that we still maintain the list - * even when using the hash table for lookups; this simplifies life for - * GEQO. + * considered in this planning run. */ - List *join_rel_list; - struct HTAB *join_rel_hash pg_node_attr(read_write_ignore); + struct RelInfoList *join_rel_list; /* list of join-relation RelOptInfos */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] @@ -401,7 +414,7 @@ struct PlannerInfo * Upper-rel RelOptInfos. Use fetch_upper_rel() to get any particular * upper rel. */ - List *upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); + RelInfoList upper_rels[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore);; /* Result tlists chosen by grouping_planner for upper-stage processing */ struct PathTarget *upper_targets[UPPERREL_FINAL + 1] pg_node_attr(read_write_ignore); -- 2.31.1 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=v23-0002-Aggregate-push-down-basic-functionality.patch ^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2023-01-04 13:41 UTC | newest] Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-01-16 15:02 [PATCH 1/2] Introduce RelInfoList structure. Antonin Houska <[email protected]> 2020-05-18 12:28 [PATCH 1/3] Introduce RelInfoList structure. Antonin Houska <[email protected]> 2022-11-04 14:02 [PATCH 1/3] Introduce RelInfoList structure. Antonin Houska <[email protected]> 2022-11-17 09:41 [PATCH 1/3] Introduce RelInfoList structure. Antonin Houska <[email protected]> 2023-01-04 13:41 [PATCH 1/3] Introduce RelInfoList structure. Antonin Houska <[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