Skip to content

Commit a3179ab

Browse files
tglsfdctglsfdc
committed
Recalculate where-needed data accurately after a join removal.
Up to now, remove_rel_from_query() has done a pretty shoddy job of updating our where-needed bitmaps (per-Var attr_needed and per-PlaceHolderVar ph_needed relid sets). It removed direct mentions of the to-be-removed baserel and outer join, which is the minimum amount of effort needed to keep the data structures self-consistent. But it didn't account for the fact that the removed join ON clause probably mentioned Vars of other relations, and those Vars might now not be needed as high up in the join tree as before. It's easy to show cases where this results in failing to remove a lower outer join that could also have been removed. To fix, recalculate the where-needed bitmaps from scratch after each successful join removal. This sounds expensive, but it seems to add only negligible planner runtime. (We cheat a little bit by preserving "relation 0" entries in the bitmaps, allowing us to skip re-scanning the targetlist and HAVING qual.) The submitted test case drew attention because we had successfully optimized away the lower join prior to v16. I suspect that that's somewhat accidental and there are related cases that were never optimized before and now can be. I've not tried to come up with one, though. Perhaps we should back-patch this into v16 and v17 to repair the performance regression. However, since it took a year for anyone to notice the problem, it can't be affecting too many people. Let's let the patch bake awhile in HEAD, and see if we get more complaints. Per bug #18627 from Mikaël Gourlaouen. No back-patch for now. Discussion: https://postgr.es/m/18627-44f950eb6a8416c2@postgresql.org
1 parent 7f7474a commit a3179ab

File tree

9 files changed

+320
-37
lines changed

9 files changed

+320
-37
lines changed

‎src/backend/optimizer/path/equivclass.c

Lines changed: 40 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1293,7 +1293,8 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
12931293
* For the moment we force all the Vars to be available at all join nodes
12941294
* for this eclass. Perhaps this could be improved by doing some
12951295
* pre-analysis of which members we prefer to join, but it's no worse than
1296-
* what happened in the pre-8.3 code.
1296+
* what happened in the pre-8.3 code. (Note: rebuild_eclass_attr_needed
1297+
* needs to match this code.)
12971298
*/
12981299
foreach(lc, ec->ec_members)
12991300
{
@@ -2422,6 +2423,44 @@ reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo)
24222423
return false; /* failed to make any deduction */
24232424
}
24242425

2426+
/*
2427+
* rebuild_eclass_attr_needed
2428+
* Put back attr_needed bits for Vars/PHVs needed for join eclasses.
2429+
*
2430+
* This is used to rebuild attr_needed/ph_needed sets after removal of a
2431+
* useless outer join. It should match what
2432+
* generate_base_implied_equalities_no_const did, except that we call
2433+
* add_vars_to_attr_needed not add_vars_to_targetlist.
2434+
*/
2435+
void
2436+
rebuild_eclass_attr_needed(PlannerInfo *root)
2437+
{
2438+
ListCell *lc;
2439+
2440+
foreach(lc, root->eq_classes)
2441+
{
2442+
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
2443+
2444+
/* Need do anything only for a multi-member, no-const EC. */
2445+
if (list_length(ec->ec_members) > 1 && !ec->ec_has_const)
2446+
{
2447+
ListCell *lc2;
2448+
2449+
foreach(lc2, ec->ec_members)
2450+
{
2451+
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2);
2452+
List *vars = pull_var_clause((Node *) cur_em->em_expr,
2453+
PVC_RECURSE_AGGREGATES |
2454+
PVC_RECURSE_WINDOWFUNCS |
2455+
PVC_INCLUDE_PLACEHOLDERS);
2456+
2457+
add_vars_to_attr_needed(root, vars, ec->ec_relids);
2458+
list_free(vars);
2459+
}
2460+
}
2461+
}
2462+
}
2463+
24252464
/*
24262465
* find_join_domain
24272466
* Find the highest JoinDomain enclosed within the given relid set.

‎src/backend/optimizer/plan/analyzejoins.c

Lines changed: 52 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
#include "optimizer/optimizer.h"
2828
#include "optimizer/pathnode.h"
2929
#include "optimizer/paths.h"
30+
#include "optimizer/placeholder.h"
3031
#include "optimizer/planmain.h"
3132
#include "optimizer/restrictinfo.h"
3233
#include "utils/lsyscache.h"
@@ -341,35 +342,6 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
341342
Assert(ojrelid != 0);
342343
joinrelids = bms_add_member(joinrelids, ojrelid);
343344

344-
/*
345-
* Remove references to the rel from other baserels' attr_needed arrays.
346-
*/
347-
for (rti = 1; rti < root->simple_rel_array_size; rti++)
348-
{
349-
RelOptInfo *otherrel = root->simple_rel_array[rti];
350-
int attroff;
351-
352-
/* there may be empty slots corresponding to non-baserel RTEs */
353-
if (otherrel == NULL)
354-
continue;
355-
356-
Assert(otherrel->relid == rti); /* sanity check on array */
357-
358-
/* no point in processing target rel itself */
359-
if (otherrel == rel)
360-
continue;
361-
362-
for (attroff = otherrel->max_attr - otherrel->min_attr;
363-
attroff >= 0;
364-
attroff--)
365-
{
366-
otherrel->attr_needed[attroff] =
367-
bms_del_member(otherrel->attr_needed[attroff], relid);
368-
otherrel->attr_needed[attroff] =
369-
bms_del_member(otherrel->attr_needed[attroff], ojrelid);
370-
}
371-
}
372-
373345
/*
374346
* Update all_baserels and related relid sets.
375347
*/
@@ -450,9 +422,11 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
450422
phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
451423
phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, ojrelid);
452424
Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
453-
phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
454-
phinfo->ph_needed = bms_del_member(phinfo->ph_needed, ojrelid);
455-
/* ph_needed might or might not become empty */
425+
/* Reduce ph_needed to contain only "relation 0"; see below */
426+
if (bms_is_member(0, phinfo->ph_needed))
427+
phinfo->ph_needed = bms_make_singleton(0);
428+
else
429+
phinfo->ph_needed = NULL;
456430
phv->phrels = bms_del_member(phv->phrels, relid);
457431
phv->phrels = bms_del_member(phv->phrels, ojrelid);
458432
Assert(!bms_is_empty(phv->phrels));
@@ -540,14 +514,59 @@ remove_rel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
540514
*/
541515

542516
/*
543-
* Finally, remove the rel from the baserel array to prevent it from being
517+
* Now remove the rel from the baserel array to prevent it from being
544518
* referenced again. (We can't do this earlier because
545519
* remove_join_clause_from_rels will touch it.)
546520
*/
547521
root->simple_rel_array[relid] = NULL;
548522

549523
/* And nuke the RelOptInfo, just in case there's another access path */
550524
pfree(rel);
525+
526+
/*
527+
* Finally, we must recompute per-Var attr_needed and per-PlaceHolderVar
528+
* ph_needed relid sets. These have to be known accurately, else we may
529+
* fail to remove other now-removable outer joins. And our removal of the
530+
* join clause(s) for this outer join may mean that Vars that were
531+
* formerly needed no longer are. So we have to do this honestly by
532+
* repeating the construction of those relid sets. We can cheat to one
533+
* small extent: we can avoid re-examining the targetlist and HAVING qual
534+
* by preserving "relation 0" bits from the existing relid sets. This is
535+
* safe because we'd never remove such references.
536+
*
537+
* So, start by removing all other bits from attr_needed sets. (We
538+
* already did this above for ph_needed.)
539+
*/
540+
for (rti = 1; rti < root->simple_rel_array_size; rti++)
541+
{
542+
RelOptInfo *otherrel = root->simple_rel_array[rti];
543+
int attroff;
544+
545+
/* there may be empty slots corresponding to non-baserel RTEs */
546+
if (otherrel == NULL)
547+
continue;
548+
549+
Assert(otherrel->relid == rti); /* sanity check on array */
550+
551+
for (attroff = otherrel->max_attr - otherrel->min_attr;
552+
attroff >= 0;
553+
attroff--)
554+
{
555+
if (bms_is_member(0, otherrel->attr_needed[attroff]))
556+
otherrel->attr_needed[attroff] = bms_make_singleton(0);
557+
else
558+
otherrel->attr_needed[attroff] = NULL;
559+
}
560+
}
561+
562+
/*
563+
* Now repeat construction of attr_needed bits coming from all other
564+
* sources.
565+
*/
566+
rebuild_placeholder_attr_needed(root);
567+
rebuild_joinclause_attr_needed(root);
568+
rebuild_eclass_attr_needed(root);
569+
rebuild_lateral_attr_needed(root);
551570
}
552571

553572
/*

‎src/backend/optimizer/plan/initsplan.c

Lines changed: 178 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -274,6 +274,8 @@ build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
274274
* have a single owning relation; we keep their attr_needed info in
275275
* root->placeholder_list instead. Find or create the associated
276276
* PlaceHolderInfo entry, and update its ph_needed.
277+
*
278+
* See also add_vars_to_attr_needed.
277279
*/
278280
void
279281
add_vars_to_targetlist(PlannerInfo *root, List *vars,
@@ -327,6 +329,63 @@ add_vars_to_targetlist(PlannerInfo *root, List *vars,
327329
}
328330
}
329331

332+
/*
333+
* add_vars_to_attr_needed
334+
* This does a subset of what add_vars_to_targetlist does: it just
335+
* updates attr_needed for Vars and ph_needed for PlaceHolderVars.
336+
* We assume the Vars are already in their relations' targetlists.
337+
*
338+
* This is used to rebuild attr_needed/ph_needed sets after removal
339+
* of a useless outer join. The removed join clause might have been
340+
* the only upper-level use of some other relation's Var, in which
341+
* case we can reduce that Var's attr_needed and thereby possibly
342+
* open the door to further join removals. But we can't tell that
343+
* without tedious reconstruction of the attr_needed data.
344+
*
345+
* Note that if a Var's attr_needed is successfully reduced to empty,
346+
* it will still be in the relation's targetlist even though we do
347+
* not really need the scan plan node to emit it. The extra plan
348+
* inefficiency seems tiny enough to not be worth spending planner
349+
* cycles to get rid of it.
350+
*/
351+
void
352+
add_vars_to_attr_needed(PlannerInfo *root, List *vars,
353+
Relids where_needed)
354+
{
355+
ListCell *temp;
356+
357+
Assert(!bms_is_empty(where_needed));
358+
359+
foreach(temp, vars)
360+
{
361+
Node *node = (Node *) lfirst(temp);
362+
363+
if (IsA(node, Var))
364+
{
365+
Var *var = (Var *) node;
366+
RelOptInfo *rel = find_base_rel(root, var->varno);
367+
int attno = var->varattno;
368+
369+
if (bms_is_subset(where_needed, rel->relids))
370+
continue;
371+
Assert(attno >= rel->min_attr && attno <= rel->max_attr);
372+
attno -= rel->min_attr;
373+
rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
374+
where_needed);
375+
}
376+
else if (IsA(node, PlaceHolderVar))
377+
{
378+
PlaceHolderVar *phv = (PlaceHolderVar *) node;
379+
PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
380+
381+
phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
382+
where_needed);
383+
}
384+
else
385+
elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
386+
}
387+
}
388+
330389

331390
/*****************************************************************************
332391
*
@@ -488,10 +547,54 @@ extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
488547
*/
489548
add_vars_to_targetlist(root, newvars, where_needed);
490549

491-
/* Remember the lateral references for create_lateral_join_info */
550+
/*
551+
* Remember the lateral references for rebuild_lateral_attr_needed and
552+
* create_lateral_join_info.
553+
*/
492554
brel->lateral_vars = newvars;
493555
}
494556

557+
/*
558+
* rebuild_lateral_attr_needed
559+
* Put back attr_needed bits for Vars/PHVs needed for lateral references.
560+
*
561+
* This is used to rebuild attr_needed/ph_needed sets after removal of a
562+
* useless outer join. It should match what find_lateral_references did,
563+
* except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
564+
*/
565+
void
566+
rebuild_lateral_attr_needed(PlannerInfo *root)
567+
{
568+
Index rti;
569+
570+
/* We need do nothing if the query contains no LATERAL RTEs */
571+
if (!root->hasLateralRTEs)
572+
return;
573+
574+
/* Examine the same baserels that find_lateral_references did */
575+
for (rti = 1; rti < root->simple_rel_array_size; rti++)
576+
{
577+
RelOptInfo *brel = root->simple_rel_array[rti];
578+
Relids where_needed;
579+
580+
if (brel == NULL)
581+
continue;
582+
if (brel->reloptkind != RELOPT_BASEREL)
583+
continue;
584+
585+
/*
586+
* We don't need to repeat all of extract_lateral_references, since it
587+
* kindly saved the extracted Vars/PHVs in lateral_vars.
588+
*/
589+
if (brel->lateral_vars == NIL)
590+
continue;
591+
592+
where_needed = bms_make_singleton(rti);
593+
594+
add_vars_to_attr_needed(root, brel->lateral_vars, where_needed);
595+
}
596+
}
597+
495598
/*
496599
* create_lateral_join_info
497600
* Fill in the per-base-relation direct_lateral_relids, lateral_relids
@@ -2445,6 +2548,9 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
24452548
* var propagation is ensured by making ojscope include input rels from
24462549
* both sides of the join.
24472550
*
2551+
* See also rebuild_joinclause_attr_needed, which has to partially repeat
2552+
* this work after removal of an outer join.
2553+
*
24482554
* Note: if the clause gets absorbed into an EquivalenceClass then this
24492555
* may be unnecessary, but for now we have to do it to cover the case
24502556
* where the EC becomes ec_broken and we end up reinserting the original
@@ -3014,6 +3120,11 @@ process_implied_equality(PlannerInfo *root,
30143120
* some of the Vars could have missed having that done because they only
30153121
* appeared in single-relation clauses originally. So do it here for
30163122
* safety.
3123+
*
3124+
* See also rebuild_joinclause_attr_needed, which has to partially repeat
3125+
* this work after removal of an outer join. (Since we will put this
3126+
* clause into the joininfo lists, that function needn't do any extra work
3127+
* to find it.)
30173128
*/
30183129
if (bms_membership(relids) == BMS_MULTIPLE)
30193130
{
@@ -3155,6 +3266,72 @@ get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids)
31553266
}
31563267

31573268

3269+
/*
3270+
* rebuild_joinclause_attr_needed
3271+
* Put back attr_needed bits for Vars/PHVs needed for join clauses.
3272+
*
3273+
* This is used to rebuild attr_needed/ph_needed sets after removal of a
3274+
* useless outer join. It should match what distribute_qual_to_rels did,
3275+
* except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
3276+
*/
3277+
void
3278+
rebuild_joinclause_attr_needed(PlannerInfo *root)
3279+
{
3280+
/*
3281+
* We must examine all join clauses, but there's no value in processing
3282+
* any join clause more than once. So it's slightly annoying that we have
3283+
* to find them via the per-base-relation joininfo lists. Avoid duplicate
3284+
* processing by tracking the rinfo_serial numbers of join clauses we've
3285+
* already seen. (This doesn't work for is_clone clauses, so we must
3286+
* waste effort on them.)
3287+
*/
3288+
Bitmapset *seen_serials = NULL;
3289+
Index rti;
3290+
3291+
/* Scan all baserels for join clauses */
3292+
for (rti = 1; rti < root->simple_rel_array_size; rti++)
3293+
{
3294+
RelOptInfo *brel = root->simple_rel_array[rti];
3295+
ListCell *lc;
3296+
3297+
if (brel == NULL)
3298+
continue;
3299+
if (brel->reloptkind != RELOPT_BASEREL)
3300+
continue;
3301+
3302+
foreach(lc, brel->joininfo)
3303+
{
3304+
RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3305+
Relids relids = rinfo->required_relids;
3306+
3307+
if (!rinfo->is_clone) /* else serial number is not unique */
3308+
{
3309+
if (bms_is_member(rinfo->rinfo_serial, seen_serials))
3310+
continue; /* saw it already */
3311+
seen_serials = bms_add_member(seen_serials,
3312+
rinfo->rinfo_serial);
3313+
}
3314+
3315+
if (bms_membership(relids) == BMS_MULTIPLE)
3316+
{
3317+
List *vars = pull_var_clause((Node *) rinfo->clause,
3318+
PVC_RECURSE_AGGREGATES |
3319+
PVC_RECURSE_WINDOWFUNCS |
3320+
PVC_INCLUDE_PLACEHOLDERS);
3321+
Relids where_needed;
3322+
3323+
if (rinfo->is_clone)
3324+
where_needed = bms_intersect(relids, root->all_baserels);
3325+
else
3326+
where_needed = relids;
3327+
add_vars_to_attr_needed(root, vars, where_needed);
3328+
list_free(vars);
3329+
}
3330+
}
3331+
}
3332+
}
3333+
3334+
31583335
/*
31593336
* match_foreign_keys_to_quals
31603337
* Match foreign-key constraints to equivalence classes and join quals

0 commit comments

Comments
 (0)