Subject: Re: allowing extensions to control planner behavior

From: Robert Haas <[email-masked]>
Date: Wed, 18 Sep 2024 11:48:49 -0400

On Tue, Aug 27, 2024 at 4:07 PM Robert Haas <[email-masked]> wrote:
> I think that the beginning of add_paths_to_joinrel() looks like a
> useful spot to get control. You could, for example, have a hook there
> which returns a bitmask indicating which of merge-join, nested-loop,
> and hash join will be allowable for this call; that hook would then
> allow for control over the join method and the join order, and the
> join order control is strong enough that you can implement either of
> the two interpretations above. This idea theorizes that 0001 was wrong
> to make the path mask a per-RelOptInfo value, because there could be
> many calls to add_paths_to_joinrel() for a single RelOptInfo and, in
> this idea, every one of those can enforce a different mask.

Here is an implementation of this idea. I think this is significantly
more elegant than the previous patch. Functionally, it does a better
job allowing for control over join planning than the previous patch,
because you can control both the join method and the join order. It
does not attempt to provide control over scan or appendrel methods; I
could build similar machinery for those cases, but let's talk about
this case, first. As non-for-commit proofs-of-concept, I've included
two sample contrib modules here, one called alphabet_join and one
called hint_via_alias. alphabet_join forces the join to be done in
alphabetical order by table alias. Consider this test query:

SELECT COUNT(*) FROM pgbench_accounts THE
INNER JOIN pgbench_accounts QUICK on THE.aid = QUICK.aid
INNER JOIN pgbench_accounts BROWN on THE.aid = BROWN.aid
INNER JOIN pgbench_accounts FOX on THE.aid = FOX.aid
INNER JOIN pgbench_accounts JUMPED on THE.aid = JUMPED.aid
INNER JOIN pgbench_accounts OVER on THE.aid = OVER.aid
INNER JOIN pgbench_accounts LAZY on THE.aid = LAZY.aid
INNER JOIN pgbench_accounts DOG on THE.aid = DOG.aid;

When you just execute this normally, the join order matches the order
you enter it: THE QUICK BROWN FOX JUMPED OVER LAZY DOG. But if you
load alphabet_join, then the join order becomes BROWN DOG FOX JUMPED
LAZY OVER QUICK THE. It is unlikely that anyone wants their join order
to be determined by strict alphabetical order, but again, this is just
intended to show that the hook works.

hint_via_alias whose table alias starts with mj_, hj_, or nl_ using a
merge-join, hash-join, or nested loop, respectively. Here again, I
don't think that passing hints through the table alias names is
probably the best thing from a UI perspective, but unlike the previous
one which is clearly a toy, I can imagine someone actually trying to
use this one on a real server. If we want anything in contrib at all
it should probably be something much better than this, but again at
this stage I'm just trying to showcase the hook.

> Potentially, such a hook could return additional information, either
> by using more bits of the bitmask or by returning other information
> via some other data type. For instance, I still believe that
> distinguishing between parameterized-nestloops and
> unparameterized-nestloops would be real darn useful, so we could have
> separate bits for each; or you could have a bit to control whether
> foreign-join paths get disabled (or are considered at all), or you
> could have separate bits for merge joins that involve 0, 1, or 2
> sorts. Whether we need or want any or all of that is certainly
> debatable, but the point is that if you did want some of that, or
> something else, it doesn't look difficult to feed that information
> through to the places where you would need it to be available.

I spent a lot of time thinking about what should and should not be in
scope for this hook and decided against both of the ideas above.
They're not necessarily bad ideas but they feel like examples of
arbitrary policy that you could want to implement, and I don't think
it's viable to have every arbitrary policy that someone happens to
favor in the core code. If we want extensions to be able to achieve
these kinds of results, I think we're going to need a hook at either
initial_cost_XXX time that would be free to make arbitrary decisions
about cost and disabled nodes for each possible path we might
generate, or a hook at final_cost_XXX time that could make paths more
disabled (but not less) or more costly (but not less costly unless it
also makes them more disabled). For now, I have not done that, because
I think the hook that I've added to add_paths_to_joinrel is fairly
powerful and significantly cheaper than a hook that has to fire for
every possible generated path. Also, even if we do add that, I bet
it's useful to let this hook pass some state through to that hook, as
a way of avoiding recomputation.

However, although I didn't end up including either of the policies
mentioned above in this patch, I still did end up subdividing the
"merge join" strategy according to whether or not a Materialize node
is used, and the "nested loop" strategy according to whether we use
Materialize, Memoize, or neither. At least according to my reading of
the code, the planner really does consider these to be separate
sub-strategies: it thinks about whether to use a nested loop without a
materialize node, and it thinks about whether to do a nested loop with
a materialize node, and there's separate code for those things. So
this doesn't feel like an arbitrary distinction to me. In contrast,
the parameterized-vs-unparameterized nested loop thing is just a
question of whether the outer path that we happen to choose happens to
satisfy some part of the parameterization of the inner path we happen
to choose; the code neither knows nor cares whether that will occur.
There is also a pragmatic reason to make sure that the hook allows for
control over use of these sub-strategies: pg_hint_plan has Memoize and
NoMemoize hints, and if whatever hook we add here can't replace what
pg_hint_plan is already doing, then it's clearly not up to the mark.

I also spent some time thinking about what behavior this hook does and
does not allow you to control. As noted, it allows you to control the
join method and the join order, including which table ends up on which
side of the join. But, is that good enough to reproduce a very
specific plan, say one that you saw before and liked? Let's imagine
that you've arranged to disable every path in outerrel and innerrel
other than the ones that you want to be chosen, either using some
hackery or some future patch not included here. Now, you want to use
this patch to make sure that those are joined in the way that you want
them to be joined. Can you do that? I think the answer is "mostly".
You'll be able to get the join method you want used, and you'll be
able to get Memoize and/or Materialize nodes if you want them or avoid
them if you don't. Also, join_path_setup_hook will see
JOIN_UNIQUE_INNER or JOIN_UNIQUE_OUTER so if we're thinking of
implementing a semijoin via uniquify+join, the hook will be able to
encourage or discourage that approach if it wants. However, it *won't*
be able to force the uniquification to happen using hashing rather
than sorting or vice versa, or at least not without doing something
pretty kludgy. Also, it won't be able to force a merge join produced
by sort_inner_and_outer() to use the sort keys that it prefers. Merge
joins produced by match_unsorted_outer() are entirely a function of
the input paths, but those produced by sort_inner_and_outer() are not.
Aside from these two cases, I found no other gaps.

AFAICS, the only way to close the gap around unique-ification strategy
would be with some piece of bespoke infrastructure that just does
exactly that. The inability to control the sort order selected by
sort_inner_and_outer() could, I believe, be closed by a hook at
initial or final cost time. As noted above, such a hook is also useful
when you're not trying to arrive at a specific plan, but rather have
some policy around what kind of plan you want to end up with and wish
to penalize plans that don't comply with your policy. So maybe this is
an argument for adding that hook. That said, even without that, this
might be close enough for government work. If the planner chooses the
correct input paths and if it also chooses a merge join, how likely is
it that it will now choose the wrong pathkeys to perform that merge
join? I bet it's quite unlikely, because I think the effect of the
logic we have will probably be to just do the smallest possible amount
of sorting, and that's also probably the answer the user wants. So it
might be OK in practice to just not worry about this. On the other
hand, a leading cause of disasters is people assuming that certain
things would not go wrong and then having those exact things go wrong,
so it's probably unwise to be confident that the attached patch is all
we'll ever need.

Still, I think it's a pretty useful starting point. It is mostly
enough to give you control over join planning, and if combined with
similar work for scan planning, I think it would be enough for
pg_hint_plan. If we also got control over appendrel and agg planning,
then you could do a bunch more cool things.

Comments?

--
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 30 Sep 2024 16:50:40 +0700

> Comments?
Let me share my personal experience on path management in the planner.
The main thing important for extensions is flexibility - I would discuss 
a decision that is not limited by join ordering but could be applied to 
implement an index picking strategy, Memoize/Material choice versus a 
non-cached one, choice of custom paths, etc.

The most flexible way I have found to this moment is a collaboration 
between the get_relation_info_hook and add_path hook. In 
get_relation_info, we have enough context and can add some information 
to RelOptInfo - I added an extra list to this structure where extensions 
can add helpful info. Using extensible nodes, we can tackle interference 
between extensions.
The add_path hook can analyse new and old paths and also look into the 
extensible data inside RelOptInfo. The issue with lots of calls eases by 
quick return on the out-of-scope paths: usually extensions manage some 
specific path type or relation and quick test of RelOptInfo::extra_list 
allow to sort out unnecessary cases.

Being flexible, this approach is less invasive. Now, I use it to 
implement heuristics demanded by clients for cases when the estimator 
predicts only one row - usually, it means that the optimiser 
underestimates cardinality. For example, in-place switch-off of NestLoop 
if it uses too many clauses, or rules to pick up index scan if we have 
alternative scans, each of them predicts only one tuple.

Positive outcomes includes: we don't alter path costs; extension may be 
sure that core doesn't remove path from the list if the extension 
forbids it.

In attachment - hooks for add_path and add_partial_path. As you can see, 
because of differences in these routines hooks also implemented 
differently. Also the compare_path_costs_fuzzily is exported, but it is 
really good stuff for an extension.

-- 
regards, Andrei Lepikhov
From af8f5bd65e33c819723231ce433dcd51438b7ef0 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Thu, 26 Sep 2024 10:34:08 +0200
Subject: [PATCH 1/2] Introduce compare_path_hook.

The add_path function is the only interface to safely add and remove paths in
the pathlist. Postgres core provides a few optimisation hooks that an extension
can use to offer additional paths. However, it is still uncertain whether such
a path will be replaced until the end of the path population process.
This hook allows the extension to control the comparison of a new path with
each pathlist's path and denote the optimiser which path is better.
It doesn't point to the optimiser directly about what exactly to do with the
incoming path and paths, already existed in pathlist.

Tag: optimizer.
caused by: PGPRO-10445, PGPRO-11017.
---
 src/backend/optimizer/util/pathnode.c | 21 +++++++++++----------
 src/include/optimizer/pathnode.h      | 17 +++++++++++++++++
 2 files changed, 28 insertions(+), 10 deletions(-)

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index fc97bf6ee2..ae57932862 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -31,13 +31,6 @@
 #include "utils/memutils.h"
 #include "utils/selfuncs.h"
 
-typedef enum
-{
-	COSTS_EQUAL,				/* path costs are fuzzily equal */
-	COSTS_BETTER1,				/* first path is cheaper than second */
-	COSTS_BETTER2,				/* second path is cheaper than first */
-	COSTS_DIFFERENT,			/* neither path dominates the other on cost */
-} PathCostComparison;
 
 /*
  * STD_FUZZ_FACTOR is the normal fuzz factor for compare_path_costs_fuzzily.
@@ -46,6 +39,9 @@ typedef enum
  */
 #define STD_FUZZ_FACTOR 1.01
 
+/* Hook for plugins to get control over the add_path decision */
+compare_path_hook_type compare_path_hook = NULL;
+
 static List *translate_sub_tlist(List *tlist, int relid);
 static int	append_total_cost_compare(const ListCell *a, const ListCell *b);
 static int	append_startup_cost_compare(const ListCell *a, const ListCell *b);
@@ -178,7 +174,7 @@ compare_fractional_path_costs(Path *path1, Path *path2,
  * (But if total costs are fuzzily equal, we compare startup costs anyway,
  * in hopes of eliminating one path or the other.)
  */
-static PathCostComparison
+PathCostComparison
 compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
 {
 #define CONSIDER_PATH_STARTUP_COST(p)  \
@@ -490,8 +486,13 @@ add_path(RelOptInfo *parent_rel, Path *new_path)
 		/*
 		 * Do a fuzzy cost comparison with standard fuzziness limit.
 		 */
-		costcmp = compare_path_costs_fuzzily(new_path, old_path,
-											 STD_FUZZ_FACTOR);
+
+		if (compare_path_hook)
+			costcmp = (*compare_path_hook) (parent_rel, new_path, old_path,
+											STD_FUZZ_FACTOR);
+		else
+			costcmp = compare_path_costs_fuzzily(new_path, old_path,
+												 STD_FUZZ_FACTOR);
 
 		/*
 		 * If the two paths compare differently for startup and total cost,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 1035e6560c..4b95d85e1a 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -18,11 +18,28 @@
 #include "nodes/pathnodes.h"

+typedef enum
+{
+	COSTS_EQUAL,				/* path costs are fuzzily equal */
+	COSTS_BETTER1,				/* first path is cheaper than second */
+	COSTS_BETTER2,				/* second path is cheaper than first */
+	COSTS_DIFFERENT,			/* neither path dominates the other on cost */
+} PathCostComparison;
+
+/* Hook for plugins to get control when grouping_planner() plans upper rels */
+typedef PathCostComparison (*compare_path_hook_type) (RelOptInfo *parent_rel,
+													  Path *new_path,
+													  Path *old_path,
+													  double fuzz_factor);
+extern PGDLLIMPORT compare_path_hook_type compare_path_hook;
+
 /*
  * prototypes for pathnode.c
  */
 extern int	compare_path_costs(Path *path1, Path *path2,
 							   CostSelector criterion);
+extern PathCostComparison
+compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor);
 extern int	compare_fractional_path_costs(Path *path1, Path *path2,
 										  double fraction);
 extern void set_cheapest(RelOptInfo *parent_rel);
-- 
2.46.2

From f63c93a404554f7e48a01ed14661a119ae10b604 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <[email-masked]>
Date: Mon, 30 Sep 2024 13:32:43 +0700
Subject: [PATCH 2/2] Introduce compare_partial_path_hook.

By analogy of compare_path_hook, let an extension to alter decisions on
accepting new and removing old path. The add_partial_path() routine has
different logic. Hence, the hook also differs from non-partial case.

Also, move hooks and newly exported functions to paths.h. Do we need to
revert it and allow to stay in the pathnode.h?
---
 src/backend/optimizer/util/pathnode.c |  5 +++++
 src/include/optimizer/pathnode.h      | 17 -----------------
 src/include/optimizer/paths.h         | 24 ++++++++++++++++++++++++
 3 files changed, 29 insertions(+), 17 deletions(-)

diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index ae57932862..5f91ead226 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -41,6 +41,7 @@
 
 /* Hook for plugins to get control over the add_path decision */
 compare_path_hook_type compare_path_hook = NULL;
+compare_partial_path_hook_type compare_partial_path_hook = NULL;
 
 static List *translate_sub_tlist(List *tlist, int relid);
 static int	append_total_cost_compare(const ListCell *a, const ListCell *b);
@@ -870,6 +871,10 @@ add_partial_path(RelOptInfo *parent_rel, Path *new_path)
 			}
 		}
 
+		if (compare_partial_path_hook)
+			(*compare_partial_path_hook)(parent_rel, new_path, old_path,
+										 &accept_new, &remove_old);
+
 		/*
 		 * Remove current element from partial_pathlist if dominated by new.
 		 */
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index 4b95d85e1a..1035e6560c 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -18,28 +18,11 @@
 #include "nodes/pathnodes.h"

-typedef enum
-{
-	COSTS_EQUAL,				/* path costs are fuzzily equal */
-	COSTS_BETTER1,				/* first path is cheaper than second */
-	COSTS_BETTER2,				/* second path is cheaper than first */
-	COSTS_DIFFERENT,			/* neither path dominates the other on cost */
-} PathCostComparison;
-
-/* Hook for plugins to get control when grouping_planner() plans upper rels */
-typedef PathCostComparison (*compare_path_hook_type) (RelOptInfo *parent_rel,
-													  Path *new_path,
-													  Path *old_path,
-													  double fuzz_factor);
-extern PGDLLIMPORT compare_path_hook_type compare_path_hook;
-
 /*
  * prototypes for pathnode.c
  */
 extern int	compare_path_costs(Path *path1, Path *path2,
 							   CostSelector criterion);
-extern PathCostComparison
-compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor);
 extern int	compare_fractional_path_costs(Path *path1, Path *path2,
 										  double fraction);
 extern void set_cheapest(RelOptInfo *parent_rel);
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 54869d4401..47ae26033c 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -271,4 +271,28 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root,
 extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel,
 									List *live_childrels);
 
+
+typedef enum
+{
+	COSTS_EQUAL,				/* path costs are fuzzily equal */
+	COSTS_BETTER1,				/* first path is cheaper than second */
+	COSTS_BETTER2,				/* second path is cheaper than first */
+	COSTS_DIFFERENT,			/* neither path dominates the other on cost */
+} PathCostComparison;
+
+extern PathCostComparison compare_path_costs_fuzzily(Path *path1, Path *path2,
+													 double fuzz_factor);
+/* Hook for plugins to get control when grouping_planner() plans upper rels */
+typedef PathCostComparison (*compare_path_hook_type) (RelOptInfo *rel,
+													  Path *new_path,
+													  Path *old_path,
+													  double fuzz_factor);
+typedef void (*compare_partial_path_hook_type) (RelOptInfo *rel,
+												Path *new_path,
+												Path *old_path,
+												bool *accept_new,
+												bool *remove_old);
+extern PGDLLIMPORT compare_path_hook_type compare_path_hook;
+extern PGDLLIMPORT compare_partial_path_hook_type compare_partial_path_hook;
+
 #endif							/* PATHS_H */
-- 
2.46.2

---

From: Robert Haas <[email-masked]>
Date: Thu, 3 Oct 2024 14:35:24 -0400

> really good stuff for an extension.

I agree that this is more flexible, but it also seems like it would be
a lot more expensive. For every add_path() or add_partial_path() call,
you'll have to examine the input path and decide what you want to do
with it. If you want to do something like avoid nested loops with
materialization, you'll need to first check the top-level node, and
then if it's a nested loop, you have to check the inner subpath to see
if it's a Materialize node.

I'm not completely against having something like this; I think there
are cases where something along these lines is the only way to achieve
some desired objective. But I don't think this kind of hook should be
the primary way for extensions to control the planner; it seems too
low-level to me.