From d7cb6da9fbff4dcb4145a8152f20bf80f1ce7a05 Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Fri, 25 Apr 2025 16:01:15 -0400 Subject: [PATCH] Start trying to get a proper treewalk oraganized. See various XXX things in this commit. There's a bunch of stuff that isn't right here. But I think it's closer to being right than the old thing, since I believe we need several coordinated pgpa subsystems to concurrently walk the tree. --- contrib/pg_plan_advice/meson.build | 2 + contrib/pg_plan_advice/pg_plan_advice.c | 92 ++------ contrib/pg_plan_advice/pgpa_join.c | 291 ++++++++++++++---------- contrib/pg_plan_advice/pgpa_join.h | 20 +- contrib/pg_plan_advice/pgpa_walker.c | 90 ++++++++ src/tools/pgindent/typedefs.list | 3 + 6 files changed, 295 insertions(+), 203 deletions(-) create mode 100644 contrib/pg_plan_advice/pgpa_walker.c diff --git a/contrib/pg_plan_advice/meson.build b/contrib/pg_plan_advice/meson.build index 8caca010ac..4f330cb4bf 100644 --- a/contrib/pg_plan_advice/meson.build +++ b/contrib/pg_plan_advice/meson.build @@ -1,7 +1,9 @@ # Copyright (c) 2022-2024, PostgreSQL Global Development Group pg_plan_advice_sources = files( + 'pg_plan_advice.c', 'pgpa_join.c', + 'pgpa_walker.c', ) if host_system == 'windows' diff --git a/contrib/pg_plan_advice/pg_plan_advice.c b/contrib/pg_plan_advice/pg_plan_advice.c index ad7db88acb..293ba7f915 100644 --- a/contrib/pg_plan_advice/pg_plan_advice.c +++ b/contrib/pg_plan_advice/pg_plan_advice.c @@ -12,37 +12,15 @@ #include "postgres.h" #include "funcapi.h" -#include "pg_plan_advice.h" -#include "tcop/tcopprot.h" -#include "utils/builtins.h" - -static const struct config_enum_entry loglevel_options[] = { - {"disabled", -1, false}, - {"debug5", DEBUG5, false}, - {"debug4", DEBUG4, false}, - {"debug3", DEBUG3, false}, - {"debug2", DEBUG2, false}, - {"debug1", DEBUG1, false}, - {"debug", DEBUG2, true}, - {"log", LOG, false}, - {"info", INFO, true}, - {"notice", NOTICE, false}, - {"warning", WARNING, false}, - {"error", ERROR, false}, - {NULL, 0, false} -}; +#include "pgpa_join.h" PG_MODULE_MAGIC; -/* GUC variables */ -static int pg_plan_advice_log_level = -1; /* disabled */ - -PG_FUNCTION_INFO_V1(pg_get_advice); - /* Saved hook values */ static ExecutorStart_hook_type prev_ExecutorStart = NULL; -static void pg_plan_advice_ExecutorStart(QueryDesc *queryDesc, int eflags); +static bool pg_plan_advice_ExecutorStart(QueryDesc *queryDesc, int eflags); +static void pgpa_check_plan(PlannedStmt *pstmt, Plan *plan); /* * Initialize this module @@ -50,73 +28,29 @@ static void pg_plan_advice_ExecutorStart(QueryDesc *queryDesc, int eflags); void _PG_init(void) { - /* Define custom GUC variables. */ - DefineCustomEnumVariable("pg_plan_advice.log_level", - "Generate advice for each executed plan and log it at the given level.", - NULL, - &pg_plan_advice_log_level, - -1, - loglevel_options, - PGC_USERSET, - 0, - NULL, - NULL, - NULL); - - MarkGUCPrefixReserved("pg_plan_advice"); - - /* Install hooks. */ prev_ExecutorStart = ExecutorStart_hook; ExecutorStart_hook = pg_plan_advice_ExecutorStart; } -static void +static bool pg_plan_advice_ExecutorStart(QueryDesc *queryDesc, int eflags) { - if (pg_plan_advice_log_level != -1) - { - StringInfoData buf; + PlannedStmt *pstmt = queryDesc->plannedstmt; - initStringInfo(&buf); - append_advice_from_plan(&buf, queryDesc->plannedstmt); - if (buf.len > 0) - ereport(pg_plan_advice_log_level, - errmsg("plan advice: %s", buf.data)); - } + pgpa_check_plan(pstmt, pstmt->planTree); if (prev_ExecutorStart) - prev_ExecutorStart(queryDesc, eflags); + return prev_ExecutorStart(queryDesc, eflags); else - standard_ExecutorStart(queryDesc, eflags); + return standard_ExecutorStart(queryDesc, eflags); } -/* - * Generate and advice for a single query and return it via a text column. - */ -Datum -pg_get_advice(PG_FUNCTION_ARGS) +static void +pgpa_check_plan(PlannedStmt *pstmt, Plan *plan) { - char *query = text_to_cstring(PG_GETARG_TEXT_PP(0)); - List *raw_parsetree_list; - StringInfoData result; - - initStringInfo(&result); - - raw_parsetree_list = pg_parse_query(query); - foreach_node(RawStmt, parsetree, raw_parsetree_list) + if (pgpa_get_join_class(plan) == PGPA_UNROLLED_JOIN) { - List *stmt_list; - - stmt_list = pg_analyze_and_rewrite_fixedparams(parsetree, query, - NULL, 0, NULL); - stmt_list = pg_plan_queries(stmt_list, query, CURSOR_OPT_PARALLEL_OK, - NULL); - - foreach_node(PlannedStmt, stmt, stmt_list) - { - append_advice_from_plan(&result, stmt); - } + (void) pgpa_make_unrolled_join(pstmt, plan); + return; } - - PG_RETURN_TEXT_P(cstring_to_text(result.data)); } diff --git a/contrib/pg_plan_advice/pgpa_join.c b/contrib/pg_plan_advice/pgpa_join.c index 7ed543bbd3..513b83d703 100644 --- a/contrib/pg_plan_advice/pgpa_join.c +++ b/contrib/pg_plan_advice/pgpa_join.c @@ -2,12 +2,22 @@ #include "pgpa_join.h" +/* + * Temporary object used when unrolling a join tree. + */ +struct pgpa_join_unroller +{ + unsigned nallocated; + unsigned nused; + Plan *outer_subplan; + pgpa_join_strategy *strategy; + Plan **inner_subplans; + pgpa_join_unroller **inner_unroller; +}; + static pgpa_join_strategy pgpa_decompose_join(Plan *plan, Plan **realinner, Plan **realouter); -static void pgpa_fill_join_member(PlannedStmt *pstmt, pgpa_join_member * m); -static pgpa_clumped_join *pgpa_make_clumped_join_from_elided(ElidedNode *n); -static unsigned pgpa_get_single_rti(Plan *plan); /* * Should a given plan node be represented by a pgpa_unrolled_join, a @@ -42,74 +52,190 @@ pgpa_get_join_class(Plan *plan) return PGPA_NON_JOIN; } -pgpa_unrolled_join * -pgpa_make_unrolled_join(PlannedStmt *pstmt, Plan *plan) +/* + * Create an initially-empty object for unrolling joins. + * + * See comments for pgpa_unrolled_join and pgpa_clumped_join in pgpa_join.h + * for a discussion of clumped and unrolled joins. This function creates a + * helper object that can later be used to create a pgpa_unrolled_join, after + * first calling pgpa_unroll_join one or more times. + */ +pgpa_join_unroller * +pgpa_create_join_unroller(void) { - unsigned nallocated = 4; - unsigned nused = 0; - unsigned i; - Plan **subplans; - pgpa_join_strategy *strategy; - pgpa_unrolled_join *ujoin; + pgpa_join_unroller *join_unroller; - subplans = palloc_array(Plan *, nallocated); - strategy = palloc_array(pgpa_join_strategy, nallocated); + join_unroller = palloc0_object(pgpa_join_unroller); + join_unroller->nallocated = 4; + join_unroller->strategy = + palloc_array(pgpa_join_strategy, join_unroller->nallocated); + join_unroller->inner_subplans = + palloc_array(Plan *, join_unroller->nallocated); + join_unroller->inner_unroller = + palloc_array(pgpa_join_unroller *, join_unroller->nallocated); + + return join_unroller; +} + +/* + * Unroll one level of an unrollable join tree. + */ +void +pgpa_unroll_join(PlannedStmt *pstmt, Plan *plan, + pgpa_join_unroller *join_unroller, + pgpa_join_unroller **outer_join_unroller, + pgpa_join_unroller **inner_join_unroller) +{ + pgpa_join_strategy strategy; + Plan *realinner, + *realouter; + int n; + + Assert(join_unroller != NULL); /* - * Repeatedly descend to the outer child of the current join until we find - * something that is not an unrollable join. + * We need to pass the join_unroller object down through plan nodes that + * pgpa_decompose_join() regards as part of the join strategy. + * + * XXX. Gather and Gather Merge are going to be a problem here. */ - while (pgpa_get_join_class(plan) == PGPA_UNROLLED_JOIN) + if (IsA(plan, Material) || IsA(plan, Memoize) || IsA(plan, Hash)) { - if (nallocated == nused) - { - nallocated *= 2; - subplans = repalloc_array(subplans, Plan *, nallocated); - strategy = repalloc_array(strategy, pgpa_join_strategy, - nallocated); - } - - strategy[nused] = - pgpa_decompose_join(plan, &plan, &subplans[nused]); - ++nused; + *outer_join_unroller = join_unroller; + return; } /* - * This function should only be called with an unrollable join, so the - * loop above should have iterated at least once. + * Since we've already handled nodes that require pass-through treatment, + * this should be an unrollable join. */ - Assert(nused > 0); + Assert(pgpa_get_join_class(plan) == PGPA_UNROLLED_JOIN); + strategy = pgpa_decompose_join(plan, &realinner, &realouter); + + /* If our workspace is full, expand it. */ + if (join_unroller->nused >= join_unroller->nallocated) + { + join_unroller->nallocated *= 2; + join_unroller->strategy = + repalloc_array(join_unroller->strategy, + pgpa_join_strategy, + join_unroller->nallocated); + join_unroller->inner_subplans = + repalloc_array(join_unroller->inner_subplans, + Plan *, + join_unroller->nallocated); + join_unroller->inner_unroller = + repalloc_array(join_unroller->inner_unroller, + pgpa_join_unroller *, + join_unroller->nallocated); + } + + /* + * Since we're flattening outer-deep join trees, it follows that if the + * outer side is still an unrollable join, it should be unrolled into this + * same object. Otherwise, we've reached the limit of what we can unroll + * into this object and must remember the outer side as the final outer + * subplan. + */ + if (pgpa_get_join_class(realouter) == PGPA_UNROLLED_JOIN) + *outer_join_unroller = join_unroller; + else + join_unroller->outer_subplan = realouter; + + /* + * Store the inner subplan. If it's an unrollable join, it needs to be + * flattened in turn, but into a new unroller object, not this one. + */ + n = join_unroller->nused++; + join_unroller->strategy[n] = strategy; + join_unroller->inner_subplans[n] = realinner; + if (pgpa_get_join_class(realinner) == PGPA_UNROLLED_JOIN) + *inner_join_unroller = pgpa_create_join_unroller(); + else + *inner_join_unroller = NULL; + join_unroller->inner_unroller[n] = *inner_join_unroller; +} + +/* + * Use the data we've accumulated in a pgpa_join_unroller object to construct + * a pgpa_unrolled_join. + */ +pgpa_unrolled_join * +pgpa_build_unrolled_join(PlannedStmt *pstmt, + pgpa_join_unroller *join_unroller) +{ + pgpa_unrolled_join *ujoin; + int i; + + /* + * We shouldn't have gone even so far as to create a join unroller unless + * we found at least one unrollable join. + */ + Assert(join_unroller->nused > 0); /* Allocate result structures. */ ujoin = palloc0_object(pgpa_unrolled_join); - ujoin->outer.plan = plan; - ujoin->strategy = palloc0_array(pgpa_join_strategy, nused); - ujoin->inner = palloc0_array(pgpa_join_member, nused); + ujoin->outer.plan = join_unroller->outer_subplan; + ujoin->strategy = palloc0_array(pgpa_join_strategy, join_unroller->nused); + ujoin->inner = palloc0_array(pgpa_join_member, join_unroller->nused); /* * We want the joins from the deepest part of the plan tree to appear - * first in the result object, and the loop above produces exactly the - * reverse, so we need to flip both arrays when constructing the final - * result. + * first in the result object, but the join unroller adds them in exactly + * the reverse of that order, so we need to flip the order of the arrays + * when constructing the final result. */ - for (i = 0; i < nused; ++i) + for (i = 0; i < join_unroller->nused; ++i) { - ujoin->strategy[i] = strategy[nused - i - 1]; - ujoin->inner[i].plan = subplans[nused - i - 1]; - } + int k = join_unroller->nused - i - 1; - /* - * Basic structure is now in place, but so far each pgpa_join_member only - * has a Plan pointer. Let's go back through them and complete the - * remaining details. - */ - pgpa_fill_join_member(pstmt, &ujoin->outer); - for (i = 0; i < nused; ++i) - pgpa_fill_join_member(pstmt, &ujoin->inner[i]); + /* Copy strategy and Plan pointer. */ + ujoin->strategy[i] = join_unroller->strategy[k]; + ujoin->inner[i].plan = join_unroller->inner_subplans[k]; + + /* + * If there is a nested pgpa_join_unroller, we need to convert it + * to a pgpa_unrolled_join and store the result. + */ + if (join_unroller->inner_unroller[i] != NULL) + ujoin->inner[i].unrolled_join = + pgpa_build_unrolled_join(pstmt, + join_unroller->inner_unroller[k]); + + /* + * XXX. What about rti, clumped join, and elided node ? + */ + } return ujoin; } +/* + * Free memory allocated for pgpa_join_unroller. + */ +void +pgpa_destroy_join_unroller(pgpa_join_unroller *join_unroller) +{ + pfree(join_unroller->strategy); + pfree(join_unroller->inner_subplans); + pfree(join_unroller->inner_unroller); + pfree(join_unroller); +} + +/* + * Identify the join strategy used by a join and the "real" inner and outer + * plans. + * + * For example, a Hash Join always has a Hash node on the inner side, but + * for all intents and purposes the real inner input is the Hash node's child, + * not the Hash node itself. + * + * Neither a Merge Join or a Nested Loop has any mandatory subnodes the way + * a Hash Join does, but the join planning code does consider add additional + * nodes such as Materialize. When such nodes are present, we regard them as + * an aspect of the join strategy, not an input to the join. The true inner + * or outer node is whatever lies beneath any such node. + */ static pgpa_join_strategy pgpa_decompose_join(Plan *plan, Plan **realinner, Plan **realouter) { @@ -143,6 +269,8 @@ pgpa_decompose_join(Plan *plan, Plan **realinner, Plan **realouter) strategy = JSTRAT_NESTLOOP_PLAIN; break; case T_HashJoin: + Assert(IsA(innerplan, Hash)); + innerplan = innerplan->lefttree; strategy = JSTRAT_HASHJOIN; break; default: @@ -153,70 +281,3 @@ pgpa_decompose_join(Plan *plan, Plan **realinner, Plan **realouter) *realouter = outerplan; return strategy; } - -static void -pgpa_fill_join_member(PlannedStmt *pstmt, pgpa_join_member * m) -{ - /* - * It's possible that more than one node was elided here; if so, we care - * about the uppermost one, which will be last in the list. - */ - foreach_node(ElidedNode, n, pstmt->elidedNodes) - { - if (n->plan_node_id == m->plan->plan_node_id) - m->elided_node = n; - } - - /* - * If we found an elided node, use that to complete the state for this - * join member. - */ - if (m->elided_node != NULL) - { - switch (bms_membership(m->elided_node->relids)) - { - case BMS_MULTIPLE: - m->clump_join = - pgpa_make_clumped_join_from_elided(m->elided_node); - break; - case BMS_SINGLETON: - m->rti = bms_singleton_member(m->elided_node->relids); - break; - case BMS_EMPTY_SET: - elog(ERROR, "no RTIs for elided node"); - break; - } - return; - } - - /* - * Otherwise, classify the Plan node and proceed accordingly. - */ - switch (pgpa_get_join_class(m->plan)) - { - case PGPA_NON_JOIN: - m->rti = pgpa_get_single_rti(m->plan); - break; - case PGPA_CLUMPED_JOIN: - m->clump_join = pgpa_make_clumped_join(m->plan); - break; - case PGPA_UNROLLED_JOIN: - m->unrolled_join = pgpa_make_unrolled_join(pstmt, m->plan); - break; - } -} - -static pgpa_clumped_join * -pgpa_make_clumped_join_from_elided(ElidedNode *n) -{ - /* XXX FIXME */ - return NULL; -} - -/* XXX might not belong in this file */ -static unsigned -pgpa_get_single_rti(Plan *plan) -{ - /* XXX */ - return 0; -} diff --git a/contrib/pg_plan_advice/pgpa_join.h b/contrib/pg_plan_advice/pgpa_join.h index b8d7168402..4303741be1 100644 --- a/contrib/pg_plan_advice/pgpa_join.h +++ b/contrib/pg_plan_advice/pgpa_join.h @@ -14,6 +14,7 @@ #include "nodes/plannodes.h" +typedef struct pgpa_join_unroller pgpa_join_unroller; typedef struct pgpa_unrolled_join pgpa_unrolled_join; /* @@ -91,9 +92,9 @@ typedef enum */ typedef struct { - Plan *plan; + Plan *plan; ElidedNode *elided_node; - Index rti; + Index rti; pgpa_clumped_join *clump_join; pgpa_unrolled_join *unrolled_join; } pgpa_join_member; @@ -133,13 +134,14 @@ typedef enum extern pgpa_join_class pgpa_get_join_class(Plan *plan); extern pgpa_clumped_join *pgpa_make_clumped_join(Plan *plan); -extern pgpa_unrolled_join *pgpa_make_unrolled_join(PlannedStmt *pstmt, - Plan *plan); -typedef bool (*pgpa_unrolled_join_walker_callback) (pgpa_join_member *member, - void *context); -extern bool pgpa_unrolled_join_walker(pgpa_unrolled_join *join, - pgpa_unrolled_join_walker_callback cb, - void *context); +extern pgpa_join_unroller *pgpa_create_join_unroller(void); +extern void pgpa_unroll_join(PlannedStmt *pstmt, Plan *plan, + pgpa_join_unroller *join_unroller, + pgpa_join_unroller **outer_join_unroller, + pgpa_join_unroller **inner_join_unroller); +extern pgpa_unrolled_join *pgpa_build_unrolled_join(PlannedStmt *pstmt, + pgpa_join_unroller *join_unroller); +extern void pgpa_destroy_join_unroller(pgpa_join_unroller *join_unroller); #endif diff --git a/contrib/pg_plan_advice/pgpa_walker.c b/contrib/pg_plan_advice/pgpa_walker.c new file mode 100644 index 0000000000..9fc21f8ad0 --- /dev/null +++ b/contrib/pg_plan_advice/pgpa_walker.c @@ -0,0 +1,90 @@ +#include "postgres.h" + +#include "pgpa_join.h" + +#include "nodes/plannodes.h" + +typedef struct pgpa_plan_walker_context +{ + PlannedStmt *pstmt; + List *unrolled_joins; +} pgpa_plan_walker_context; + +extern void +pgpa_plan_walker(pgpa_plan_walker_context *context, Plan *plan, + pgpa_join_unroller *join_unroller); + +void +pgpa_plan_walker(pgpa_plan_walker_context *context, Plan *plan, + pgpa_join_unroller *join_unroller) +{ + pgpa_join_unroller *outer_join_unroller = NULL; + pgpa_join_unroller *inner_join_unroller = NULL; + bool join_unroller_toplevel = false; + ListCell *lc; + List *extraplans = NIL; + + if (join_unroller == NULL && + pgpa_get_join_class(plan) == PGPA_CLUMPED_JOIN) + { + join_unroller = pgpa_create_join_unroller(); + join_unroller_toplevel = true; + } + if (join_unroller != NULL) + pgpa_unroll_join(context->pstmt, plan, join_unroller, + &outer_join_unroller, &inner_join_unroller); + + /* XXX I don't know how this is supposed to handle elided nodes. */ + + if (plan->lefttree != NULL) + pgpa_plan_walker(context, plan->lefttree, outer_join_unroller); + if (plan->righttree != NULL) + pgpa_plan_walker(context, plan->righttree, inner_join_unroller); + + if (join_unroller_toplevel) + { + pgpa_unrolled_join *ujoin; + + ujoin = pgpa_build_unrolled_join(context->pstmt, join_unroller); + context->unrolled_joins = lappend(context->unrolled_joins, ujoin); + pgpa_destroy_join_unroller(join_unroller); + } + + foreach(lc, plan->initPlan) + { + Plan *subplan = lfirst(lc); + + pgpa_plan_walker(context, subplan, NULL); + } + + switch (nodeTag(plan)) + { + case T_Append: + extraplans = ((Append *) plan)->appendplans; + break; + case T_MergeAppend: + extraplans = ((MergeAppend *) plan)->mergeplans; + break; + case T_BitmapAnd: + extraplans = ((BitmapAnd *) plan)->bitmapplans; + break; + case T_BitmapOr: + extraplans = ((BitmapOr *) plan)->bitmapplans; + break; + case T_SubqueryScan: + pgpa_plan_walker(context, ((SubqueryScan *) plan)->subplan, NULL); + break; + case T_CustomScan: + extraplans = ((CustomScan *) plan)->custom_plans; + break; + default: + break; + } + + foreach(lc, extraplans) + { + Plan *subplan = lfirst(lc); + + pgpa_plan_walker(context, subplan, NULL); + } +} diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index af72139dab..0e5026884c 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -4311,7 +4311,10 @@ ExplainOptionHandler overexplain_options SubPlanRTInfo ElidedNode +pgpa_join_class pgpa_join_clump_strategy +pgpa_join_member pgpa_join_strategy pgpa_clumped_join pgpa_unrolled_join +pgpa_join_unroller -- 2.39.5