| 1 |
/*------------------------------------------------------------------------- |
| 2 |
* |
| 3 |
* equivclass.c |
| 4 |
* Routines for managing EquivalenceClasses |
| 5 |
* |
| 6 |
* See src/backend/optimizer/README for discussion of EquivalenceClasses. |
| 7 |
* |
| 8 |
* |
| 9 |
* Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group |
| 10 |
* Portions Copyright (c) 1994, Regents of the University of California |
| 11 |
* |
| 12 |
* IDENTIFICATION |
| 13 |
* src/backend/optimizer/path/equivclass.c |
| 14 |
* |
| 15 |
*------------------------------------------------------------------------- |
| 16 |
*/ |
| 17 |
#include "postgres.h" |
| 18 |
|
| 19 |
#include <limits.h> |
| 20 |
|
| 21 |
#include "access/stratnum.h" |
| 22 |
#include "catalog/pg_type.h" |
| 23 |
#include "common/hashfn.h" |
| 24 |
#include "nodes/makefuncs.h" |
| 25 |
#include "nodes/nodeFuncs.h" |
| 26 |
#include "optimizer/appendinfo.h" |
| 27 |
#include "optimizer/clauses.h" |
| 28 |
#include "optimizer/optimizer.h" |
| 29 |
#include "optimizer/pathnode.h" |
| 30 |
#include "optimizer/paths.h" |
| 31 |
#include "optimizer/planmain.h" |
| 32 |
#include "optimizer/restrictinfo.h" |
| 33 |
#include "rewrite/rewriteManip.h" |
| 34 |
#include "utils/lsyscache.h" |
| 35 |
|
| 36 |
|
| 37 |
static EquivalenceMember *make_eq_member(EquivalenceClass *ec, |
| 38 |
Expr *expr, Relids relids, |
| 39 |
JoinDomain *jdomain, |
| 40 |
EquivalenceMember *parent, |
| 41 |
Oid datatype); |
| 42 |
static EquivalenceMember *add_eq_member(EquivalenceClass *ec, |
| 43 |
Expr *expr, Relids relids, |
| 44 |
JoinDomain *jdomain, |
| 45 |
Oid datatype); |
| 46 |
static EquivalenceMember *add_child_eq_member(PlannerInfo *root, |
| 47 |
EquivalenceClass *ec, |
| 48 |
int ec_index, Expr *expr, |
| 49 |
Relids relids, |
| 50 |
JoinDomain *jdomain, |
| 51 |
EquivalenceMember *parent_em, |
| 52 |
Oid datatype, |
| 53 |
Index child_relid); |
| 54 |
static void generate_base_implied_equalities_const(PlannerInfo *root, |
| 55 |
EquivalenceClass *ec); |
| 56 |
static void generate_base_implied_equalities_no_const(PlannerInfo *root, |
| 57 |
EquivalenceClass *ec); |
| 58 |
static void generate_base_implied_equalities_broken(PlannerInfo *root, |
| 59 |
EquivalenceClass *ec); |
| 60 |
static List *generate_join_implied_equalities_normal(PlannerInfo *root, |
| 61 |
EquivalenceClass *ec, |
| 62 |
Relids join_relids, |
| 63 |
Relids outer_relids, |
| 64 |
Relids inner_relids); |
| 65 |
static List *generate_join_implied_equalities_broken(PlannerInfo *root, |
| 66 |
EquivalenceClass *ec, |
| 67 |
Relids nominal_join_relids, |
| 68 |
Relids outer_relids, |
| 69 |
Relids nominal_inner_relids, |
| 70 |
RelOptInfo *inner_rel); |
| 71 |
static Oid select_equality_operator(EquivalenceClass *ec, |
| 72 |
Oid lefttype, Oid righttype); |
| 73 |
static RestrictInfo *create_join_clause(PlannerInfo *root, |
| 74 |
EquivalenceClass *ec, Oid opno, |
| 75 |
EquivalenceMember *leftem, |
| 76 |
EquivalenceMember *rightem, |
| 77 |
EquivalenceClass *parent_ec); |
| 78 |
static bool reconsider_outer_join_clause(PlannerInfo *root, |
| 79 |
OuterJoinClauseInfo *ojcinfo, |
| 80 |
bool outer_on_left); |
| 81 |
static bool reconsider_full_join_clause(PlannerInfo *root, |
| 82 |
OuterJoinClauseInfo *ojcinfo); |
| 83 |
static JoinDomain *find_join_domain(PlannerInfo *root, Relids relids); |
| 84 |
static Bitmapset *get_eclass_indexes_for_relids(PlannerInfo *root, |
| 85 |
Relids relids); |
| 86 |
static Bitmapset *get_common_eclass_indexes(PlannerInfo *root, Relids relids1, |
| 87 |
Relids relids2); |
| 88 |
static void ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec); |
| 89 |
static void ec_add_derived_clauses(EquivalenceClass *ec, List *clauses); |
| 90 |
static void ec_add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause); |
| 91 |
static void ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo); |
| 92 |
static RestrictInfo *ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, |
| 93 |
EquivalenceMember *leftem, |
| 94 |
EquivalenceMember *rightem, |
| 95 |
EquivalenceClass *parent_ec); |
| 96 |
static RestrictInfo *ec_search_derived_clause_for_ems(PlannerInfo *root, |
| 97 |
EquivalenceClass *ec, |
| 98 |
EquivalenceMember *leftem, |
| 99 |
EquivalenceMember *rightem, |
| 100 |
EquivalenceClass *parent_ec); |
| 101 |
|
| 102 |
/* |
| 103 |
* Hash key identifying a derived clause. |
| 104 |
* |
| 105 |
* This structure should not be filled manually. Use fill_ec_derives_key() to |
| 106 |
* set it up in canonical form. |
| 107 |
*/ |
| 108 |
typedef struct |
| 109 |
{ |
| 110 |
EquivalenceMember *em1; |
| 111 |
EquivalenceMember *em2; |
| 112 |
EquivalenceClass *parent_ec; |
| 113 |
} ECDerivesKey; |
| 114 |
|
| 115 |
/* Hash table entry in ec_derives_hash. */ |
| 116 |
typedef struct |
| 117 |
{ |
| 118 |
uint32 status; |
| 119 |
ECDerivesKey key; |
| 120 |
RestrictInfo *rinfo; |
| 121 |
} ECDerivesEntry; |
| 122 |
|
| 123 |
/* Threshold for switching from list to hash table */ |
| 124 |
#define EC_DERIVES_HASH_THRESHOLD 32 |
| 125 |
|
| 126 |
#define SH_PREFIX derives |
| 127 |
#define SH_ELEMENT_TYPE ECDerivesEntry |
| 128 |
#define SH_KEY_TYPE ECDerivesKey |
| 129 |
#define SH_KEY key |
| 130 |
#define SH_HASH_KEY(tb, key) \ |
| 131 |
hash_bytes((const unsigned char *) &(key), sizeof(ECDerivesKey)) |
| 132 |
#define SH_EQUAL(tb, a, b) \ |
| 133 |
((a).em1 == (b).em1 && (a).em2 == (b).em2 && (a).parent_ec == (b).parent_ec) |
| 134 |
#define SH_SCOPE static inline |
| 135 |
#define SH_DECLARE |
| 136 |
#define SH_DEFINE |
| 137 |
#include "lib/simplehash.h" |
| 138 |
|
| 139 |
/* |
| 140 |
* process_equivalence |
| 141 |
* The given clause has a mergejoinable operator and is not an outer-join |
| 142 |
* qualification, so its two sides can be considered equal |
| 143 |
* anywhere they are both computable; moreover that equality can be |
| 144 |
* extended transitively. Record this knowledge in the EquivalenceClass |
| 145 |
* data structure, if applicable. Returns true if successful, false if not |
| 146 |
* (in which case caller should treat the clause as ordinary, not an |
| 147 |
* equivalence). |
| 148 |
* |
| 149 |
* In some cases, although we cannot convert a clause into EquivalenceClass |
| 150 |
* knowledge, we can still modify it to a more useful form than the original. |
| 151 |
* Then, *p_restrictinfo will be replaced by a new RestrictInfo, which is what |
| 152 |
* the caller should use for further processing. |
| 153 |
* |
| 154 |
* jdomain is the join domain within which the given clause was found. |
| 155 |
* This limits the applicability of deductions from the EquivalenceClass, |
| 156 |
* as described in optimizer/README. |
| 157 |
* |
| 158 |
* We reject proposed equivalence clauses if they contain leaky functions |
| 159 |
* and have security_level above zero. The EC evaluation rules require us to |
| 160 |
* apply certain tests at certain joining levels, and we can't tolerate |
| 161 |
* delaying any test on security_level grounds. By rejecting candidate clauses |
| 162 |
* that might require security delays, we ensure it's safe to apply an EC |
| 163 |
* clause as soon as it's supposed to be applied. |
| 164 |
* |
| 165 |
* On success return, we have also initialized the clause's left_ec/right_ec |
| 166 |
* fields to point to the EquivalenceClass representing it. This saves lookup |
| 167 |
* effort later. |
| 168 |
* |
| 169 |
* Note: constructing merged EquivalenceClasses is a standard UNION-FIND |
| 170 |
* problem, for which there exist better data structures than simple lists. |
| 171 |
* If this code ever proves to be a bottleneck then it could be sped up --- |
| 172 |
* but for now, simple is beautiful. |
| 173 |
* |
| 174 |
* Note: this is only called during planner startup, not during GEQO |
| 175 |
* exploration, so we need not worry about whether we're in the right |
| 176 |
* memory context. |
| 177 |
*/ |
| 178 |
bool |
| 179 |
process_equivalence(PlannerInfo *root, |
| 180 |
RestrictInfo **p_restrictinfo, |
| 181 |
JoinDomain *jdomain) |
| 182 |
{ |
| 183 |
RestrictInfo *restrictinfo = *p_restrictinfo; |
| 184 |
Expr *clause = restrictinfo->clause; |
| 185 |
Oid opno, |
| 186 |
collation, |
| 187 |
item1_type, |
| 188 |
item2_type; |
| 189 |
Expr *item1; |
| 190 |
Expr *item2; |
| 191 |
Relids item1_relids, |
| 192 |
item2_relids; |
| 193 |
List *opfamilies; |
| 194 |
EquivalenceClass *ec1, |
| 195 |
*ec2; |
| 196 |
EquivalenceMember *em1, |
| 197 |
*em2; |
| 198 |
ListCell *lc1; |
| 199 |
int ec2_idx; |
| 200 |
|
| 201 |
/* Should not already be marked as having generated an eclass */ |
| 202 |
Assert(restrictinfo->left_ec == NULL); |
| 203 |
Assert(restrictinfo->right_ec == NULL); |
| 204 |
|
| 205 |
/* Reject if it is potentially postponable by security considerations */ |
| 206 |
if (restrictinfo->security_level > 0 && !restrictinfo->leakproof) |
| 207 |
return false; |
| 208 |
|
| 209 |
/* Extract info from given clause */ |
| 210 |
Assert(is_opclause(clause)); |
| 211 |
opno = ((OpExpr *) clause)->opno; |
| 212 |
collation = ((OpExpr *) clause)->inputcollid; |
| 213 |
item1 = (Expr *) get_leftop(clause); |
| 214 |
item2 = (Expr *) get_rightop(clause); |
| 215 |
item1_relids = restrictinfo->left_relids; |
| 216 |
item2_relids = restrictinfo->right_relids; |
| 217 |
|
| 218 |
/* |
| 219 |
* Ensure both input expressions expose the desired collation (their types |
| 220 |
* should be OK already); see comments for canonicalize_ec_expression. |
| 221 |
*/ |
| 222 |
item1 = canonicalize_ec_expression(item1, |
| 223 |
exprType((Node *) item1), |
| 224 |
collation); |
| 225 |
item2 = canonicalize_ec_expression(item2, |
| 226 |
exprType((Node *) item2), |
| 227 |
collation); |
| 228 |
|
| 229 |
/* |
| 230 |
* Clauses of the form X=X cannot be translated into EquivalenceClasses. |
| 231 |
* We'd either end up with a single-entry EC, losing the knowledge that |
| 232 |
* the clause was present at all, or else make an EC with duplicate |
| 233 |
* entries, causing other issues. |
| 234 |
*/ |
| 235 |
if (equal(item1, item2)) |
| 236 |
{ |
| 237 |
/* |
| 238 |
* If the operator is strict, then the clause can be treated as just |
| 239 |
* "X IS NOT NULL". (Since we know we are considering a top-level |
| 240 |
* qual, we can ignore the difference between FALSE and NULL results.) |
| 241 |
* It's worth making the conversion because we'll typically get a much |
| 242 |
* better selectivity estimate than we would for X=X. |
| 243 |
* |
| 244 |
* If the operator is not strict, we can't be sure what it will do |
| 245 |
* with NULLs, so don't attempt to optimize it. |
| 246 |
*/ |
| 247 |
set_opfuncid((OpExpr *) clause); |
| 248 |
if (func_strict(((OpExpr *) clause)->opfuncid)) |
| 249 |
{ |
| 250 |
NullTest *ntest = makeNode(NullTest); |
| 251 |
|
| 252 |
ntest->arg = item1; |
| 253 |
ntest->nulltesttype = IS_NOT_NULL; |
| 254 |
ntest->argisrow = false; /* correct even if composite arg */ |
| 255 |
ntest->location = -1; |
| 256 |
|
| 257 |
*p_restrictinfo = |
| 258 |
make_restrictinfo(root, |
| 259 |
(Expr *) ntest, |
| 260 |
restrictinfo->is_pushed_down, |
| 261 |
restrictinfo->has_clone, |
| 262 |
restrictinfo->is_clone, |
| 263 |
restrictinfo->pseudoconstant, |
| 264 |
restrictinfo->security_level, |
| 265 |
NULL, |
| 266 |
restrictinfo->incompatible_relids, |
| 267 |
restrictinfo->outer_relids); |
| 268 |
} |
| 269 |
return false; |
| 270 |
} |
| 271 |
|
| 272 |
/* |
| 273 |
* We use the declared input types of the operator, not exprType() of the |
| 274 |
* inputs, as the nominal datatypes for opfamily lookup. This presumes |
| 275 |
* that btree operators are always registered with amoplefttype and |
| 276 |
* amoprighttype equal to their declared input types. We will need this |
| 277 |
* info anyway to build EquivalenceMember nodes, and by extracting it now |
| 278 |
* we can use type comparisons to short-circuit some equal() tests. |
| 279 |
*/ |
| 280 |
op_input_types(opno, &item1_type, &item2_type); |
| 281 |
|
| 282 |
opfamilies = restrictinfo->mergeopfamilies; |
| 283 |
|
| 284 |
/* |
| 285 |
* Sweep through the existing EquivalenceClasses looking for matches to |
| 286 |
* item1 and item2. These are the possible outcomes: |
| 287 |
* |
| 288 |
* 1. We find both in the same EC. The equivalence is already known, so |
| 289 |
* there's nothing to do. |
| 290 |
* |
| 291 |
* 2. We find both in different ECs. Merge the two ECs together. |
| 292 |
* |
| 293 |
* 3. We find just one. Add the other to its EC. |
| 294 |
* |
| 295 |
* 4. We find neither. Make a new, two-entry EC. |
| 296 |
* |
| 297 |
* Note: since all ECs are built through this process or the similar |
| 298 |
* search in get_eclass_for_sort_expr(), it's impossible that we'd match |
| 299 |
* an item in more than one existing nonvolatile EC. So it's okay to stop |
| 300 |
* at the first match. |
| 301 |
*/ |
| 302 |
ec1 = ec2 = NULL; |
| 303 |
em1 = em2 = NULL; |
| 304 |
ec2_idx = -1; |
| 305 |
foreach(lc1, root->eq_classes) |
| 306 |
{ |
| 307 |
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1); |
| 308 |
ListCell *lc2; |
| 309 |
|
| 310 |
/* Never match to a volatile EC */ |
| 311 |
if (cur_ec->ec_has_volatile) |
| 312 |
continue; |
| 313 |
|
| 314 |
/* |
| 315 |
* The collation has to match; check this first since it's cheaper |
| 316 |
* than the opfamily comparison. |
| 317 |
*/ |
| 318 |
if (collation != cur_ec->ec_collation) |
| 319 |
continue; |
| 320 |
|
| 321 |
/* |
| 322 |
* A "match" requires matching sets of btree opfamilies. Use of |
| 323 |
* equal() for this test has implications discussed in the comments |
| 324 |
* for get_mergejoin_opfamilies(). |
| 325 |
*/ |
| 326 |
if (!equal(opfamilies, cur_ec->ec_opfamilies)) |
| 327 |
continue; |
| 328 |
|
| 329 |
/* We don't expect any children yet */ |
| 330 |
Assert(cur_ec->ec_childmembers == NULL); |
| 331 |
|
| 332 |
foreach(lc2, cur_ec->ec_members) |
| 333 |
{ |
| 334 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2); |
| 335 |
|
| 336 |
/* Child members should not exist in ec_members */ |
| 337 |
Assert(!cur_em->em_is_child); |
| 338 |
|
| 339 |
/* |
| 340 |
* Match constants only within the same JoinDomain (see |
| 341 |
* optimizer/README). |
| 342 |
*/ |
| 343 |
if (cur_em->em_is_const && cur_em->em_jdomain != jdomain) |
| 344 |
continue; |
| 345 |
|
| 346 |
if (!ec1 && |
| 347 |
item1_type == cur_em->em_datatype && |
| 348 |
equal(item1, cur_em->em_expr)) |
| 349 |
{ |
| 350 |
ec1 = cur_ec; |
| 351 |
em1 = cur_em; |
| 352 |
if (ec2) |
| 353 |
break; |
| 354 |
} |
| 355 |
|
| 356 |
if (!ec2 && |
| 357 |
item2_type == cur_em->em_datatype && |
| 358 |
equal(item2, cur_em->em_expr)) |
| 359 |
{ |
| 360 |
ec2 = cur_ec; |
| 361 |
ec2_idx = foreach_current_index(lc1); |
| 362 |
em2 = cur_em; |
| 363 |
if (ec1) |
| 364 |
break; |
| 365 |
} |
| 366 |
} |
| 367 |
|
| 368 |
if (ec1 && ec2) |
| 369 |
break; |
| 370 |
} |
| 371 |
|
| 372 |
/* Sweep finished, what did we find? */ |
| 373 |
|
| 374 |
if (ec1 && ec2) |
| 375 |
{ |
| 376 |
/* If case 1, nothing to do, except add to sources */ |
| 377 |
if (ec1 == ec2) |
| 378 |
{ |
| 379 |
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo); |
| 380 |
ec1->ec_min_security = Min(ec1->ec_min_security, |
| 381 |
restrictinfo->security_level); |
| 382 |
ec1->ec_max_security = Max(ec1->ec_max_security, |
| 383 |
restrictinfo->security_level); |
| 384 |
/* mark the RI as associated with this eclass */ |
| 385 |
restrictinfo->left_ec = ec1; |
| 386 |
restrictinfo->right_ec = ec1; |
| 387 |
/* mark the RI as usable with this pair of EMs */ |
| 388 |
restrictinfo->left_em = em1; |
| 389 |
restrictinfo->right_em = em2; |
| 390 |
return true; |
| 391 |
} |
| 392 |
|
| 393 |
/* |
| 394 |
* Case 2: need to merge ec1 and ec2. This should never happen after |
| 395 |
* the ECs have reached canonical state; otherwise, pathkeys could be |
| 396 |
* rendered non-canonical by the merge, and relation eclass indexes |
| 397 |
* would get broken by removal of an eq_classes list entry. |
| 398 |
*/ |
| 399 |
if (root->ec_merging_done) |
| 400 |
elog(ERROR, "too late to merge equivalence classes"); |
| 401 |
|
| 402 |
/* |
| 403 |
* We add ec2's items to ec1, then set ec2's ec_merged link to point |
| 404 |
* to ec1 and remove ec2 from the eq_classes list. We cannot simply |
| 405 |
* delete ec2 because that could leave dangling pointers in existing |
| 406 |
* PathKeys. We leave it behind with a link so that the merged EC can |
| 407 |
* be found. |
| 408 |
*/ |
| 409 |
ec1->ec_members = list_concat(ec1->ec_members, ec2->ec_members); |
| 410 |
ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources); |
| 411 |
|
| 412 |
/* |
| 413 |
* Appends ec2's derived clauses to ec1->ec_derives_list and adds them |
| 414 |
* to ec1->ec_derives_hash if present. |
| 415 |
*/ |
| 416 |
ec_add_derived_clauses(ec1, ec2->ec_derives_list); |
| 417 |
ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids); |
| 418 |
ec1->ec_has_const |= ec2->ec_has_const; |
| 419 |
/* can't need to set has_volatile */ |
| 420 |
ec1->ec_min_security = Min(ec1->ec_min_security, |
| 421 |
ec2->ec_min_security); |
| 422 |
ec1->ec_max_security = Max(ec1->ec_max_security, |
| 423 |
ec2->ec_max_security); |
| 424 |
ec2->ec_merged = ec1; |
| 425 |
root->eq_classes = list_delete_nth_cell(root->eq_classes, ec2_idx); |
| 426 |
/* just to avoid debugging confusion w/ dangling pointers: */ |
| 427 |
ec2->ec_members = NIL; |
| 428 |
ec2->ec_sources = NIL; |
| 429 |
ec_clear_derived_clauses(ec2); |
| 430 |
ec2->ec_relids = NULL; |
| 431 |
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo); |
| 432 |
ec1->ec_min_security = Min(ec1->ec_min_security, |
| 433 |
restrictinfo->security_level); |
| 434 |
ec1->ec_max_security = Max(ec1->ec_max_security, |
| 435 |
restrictinfo->security_level); |
| 436 |
/* mark the RI as associated with this eclass */ |
| 437 |
restrictinfo->left_ec = ec1; |
| 438 |
restrictinfo->right_ec = ec1; |
| 439 |
/* mark the RI as usable with this pair of EMs */ |
| 440 |
restrictinfo->left_em = em1; |
| 441 |
restrictinfo->right_em = em2; |
| 442 |
} |
| 443 |
else if (ec1) |
| 444 |
{ |
| 445 |
/* Case 3: add item2 to ec1 */ |
| 446 |
em2 = add_eq_member(ec1, item2, item2_relids, |
| 447 |
jdomain, item2_type); |
| 448 |
ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo); |
| 449 |
ec1->ec_min_security = Min(ec1->ec_min_security, |
| 450 |
restrictinfo->security_level); |
| 451 |
ec1->ec_max_security = Max(ec1->ec_max_security, |
| 452 |
restrictinfo->security_level); |
| 453 |
/* mark the RI as associated with this eclass */ |
| 454 |
restrictinfo->left_ec = ec1; |
| 455 |
restrictinfo->right_ec = ec1; |
| 456 |
/* mark the RI as usable with this pair of EMs */ |
| 457 |
restrictinfo->left_em = em1; |
| 458 |
restrictinfo->right_em = em2; |
| 459 |
} |
| 460 |
else if (ec2) |
| 461 |
{ |
| 462 |
/* Case 3: add item1 to ec2 */ |
| 463 |
em1 = add_eq_member(ec2, item1, item1_relids, |
| 464 |
jdomain, item1_type); |
| 465 |
ec2->ec_sources = lappend(ec2->ec_sources, restrictinfo); |
| 466 |
ec2->ec_min_security = Min(ec2->ec_min_security, |
| 467 |
restrictinfo->security_level); |
| 468 |
ec2->ec_max_security = Max(ec2->ec_max_security, |
| 469 |
restrictinfo->security_level); |
| 470 |
/* mark the RI as associated with this eclass */ |
| 471 |
restrictinfo->left_ec = ec2; |
| 472 |
restrictinfo->right_ec = ec2; |
| 473 |
/* mark the RI as usable with this pair of EMs */ |
| 474 |
restrictinfo->left_em = em1; |
| 475 |
restrictinfo->right_em = em2; |
| 476 |
} |
| 477 |
else |
| 478 |
{ |
| 479 |
/* Case 4: make a new, two-entry EC */ |
| 480 |
EquivalenceClass *ec = makeNode(EquivalenceClass); |
| 481 |
|
| 482 |
ec->ec_opfamilies = opfamilies; |
| 483 |
ec->ec_collation = collation; |
| 484 |
ec->ec_childmembers_size = 0; |
| 485 |
ec->ec_members = NIL; |
| 486 |
ec->ec_childmembers = NULL; |
| 487 |
ec->ec_sources = list_make1(restrictinfo); |
| 488 |
ec->ec_derives_list = NIL; |
| 489 |
ec->ec_derives_hash = NULL; |
| 490 |
ec->ec_relids = NULL; |
| 491 |
ec->ec_has_const = false; |
| 492 |
ec->ec_has_volatile = false; |
| 493 |
ec->ec_broken = false; |
| 494 |
ec->ec_sortref = 0; |
| 495 |
ec->ec_min_security = restrictinfo->security_level; |
| 496 |
ec->ec_max_security = restrictinfo->security_level; |
| 497 |
ec->ec_merged = NULL; |
| 498 |
em1 = add_eq_member(ec, item1, item1_relids, |
| 499 |
jdomain, item1_type); |
| 500 |
em2 = add_eq_member(ec, item2, item2_relids, |
| 501 |
jdomain, item2_type); |
| 502 |
|
| 503 |
root->eq_classes = lappend(root->eq_classes, ec); |
| 504 |
|
| 505 |
/* mark the RI as associated with this eclass */ |
| 506 |
restrictinfo->left_ec = ec; |
| 507 |
restrictinfo->right_ec = ec; |
| 508 |
/* mark the RI as usable with this pair of EMs */ |
| 509 |
restrictinfo->left_em = em1; |
| 510 |
restrictinfo->right_em = em2; |
| 511 |
} |
| 512 |
|
| 513 |
return true; |
| 514 |
} |
| 515 |
|
| 516 |
/* |
| 517 |
* canonicalize_ec_expression |
| 518 |
* |
| 519 |
* This function ensures that the expression exposes the expected type and |
| 520 |
* collation, so that it will be equal() to other equivalence-class expressions |
| 521 |
* that it ought to be equal() to. |
| 522 |
* |
| 523 |
* The rule for datatypes is that the exposed type should match what it would |
| 524 |
* be for an input to an operator of the EC's opfamilies; which is usually |
| 525 |
* the declared input type of the operator, but in the case of polymorphic |
| 526 |
* operators no relabeling is wanted (compare the behavior of parse_coerce.c). |
| 527 |
* Expressions coming in from quals will generally have the right type |
| 528 |
* already, but expressions coming from indexkeys may not (because they are |
| 529 |
* represented without any explicit relabel in pg_index), and the same problem |
| 530 |
* occurs for sort expressions (because the parser is likewise cavalier about |
| 531 |
* putting relabels on them). Such cases will be binary-compatible with the |
| 532 |
* real operators, so adding a RelabelType is sufficient. |
| 533 |
* |
| 534 |
* Also, the expression's exposed collation must match the EC's collation. |
| 535 |
* This is important because in comparisons like "foo < bar COLLATE baz", |
| 536 |
* only one of the expressions has the correct exposed collation as we receive |
| 537 |
* it from the parser. Forcing both of them to have it ensures that all |
| 538 |
* variant spellings of such a construct behave the same. Again, we can |
| 539 |
* stick on a RelabelType to force the right exposed collation. (It might |
| 540 |
* work to not label the collation at all in EC members, but this is risky |
| 541 |
* since some parts of the system expect exprCollation() to deliver the |
| 542 |
* right answer for a sort key.) |
| 543 |
*/ |
| 544 |
Expr * |
| 545 |
canonicalize_ec_expression(Expr *expr, Oid req_type, Oid req_collation) |
| 546 |
{ |
| 547 |
Oid expr_type = exprType((Node *) expr); |
| 548 |
|
| 549 |
/* |
| 550 |
* For a polymorphic-input-type opclass, just keep the same exposed type. |
| 551 |
* RECORD opclasses work like polymorphic-type ones for this purpose. |
| 552 |
*/ |
| 553 |
if (IsPolymorphicType(req_type) || req_type == RECORDOID) |
| 554 |
req_type = expr_type; |
| 555 |
|
| 556 |
/* |
| 557 |
* No work if the expression exposes the right type/collation already. |
| 558 |
*/ |
| 559 |
if (expr_type != req_type || |
| 560 |
exprCollation((Node *) expr) != req_collation) |
| 561 |
{ |
| 562 |
/* |
| 563 |
* If we have to change the type of the expression, set typmod to -1, |
| 564 |
* since the new type may not have the same typmod interpretation. |
| 565 |
* When we only have to change collation, preserve the exposed typmod. |
| 566 |
*/ |
| 567 |
int32 req_typmod; |
| 568 |
|
| 569 |
if (expr_type != req_type) |
| 570 |
req_typmod = -1; |
| 571 |
else |
| 572 |
req_typmod = exprTypmod((Node *) expr); |
| 573 |
|
| 574 |
/* |
| 575 |
* Use applyRelabelType so that we preserve const-flatness. This is |
| 576 |
* important since eval_const_expressions has already been applied. |
| 577 |
*/ |
| 578 |
expr = (Expr *) applyRelabelType((Node *) expr, |
| 579 |
req_type, req_typmod, req_collation, |
| 580 |
COERCE_IMPLICIT_CAST, -1, false); |
| 581 |
} |
| 582 |
|
| 583 |
return expr; |
| 584 |
} |
| 585 |
|
| 586 |
/* |
| 587 |
* make_eq_member |
| 588 |
* Build a new EquivalenceMember without adding it to an EC. If 'parent' |
| 589 |
* is NULL, the result will be a parent member, otherwise a child member. |
| 590 |
*/ |
| 591 |
static EquivalenceMember * |
| 592 |
make_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, |
| 593 |
JoinDomain *jdomain, EquivalenceMember *parent, Oid datatype) |
| 594 |
{ |
| 595 |
EquivalenceMember *em = makeNode(EquivalenceMember); |
| 596 |
|
| 597 |
em->em_expr = expr; |
| 598 |
em->em_relids = relids; |
| 599 |
em->em_is_const = false; |
| 600 |
em->em_is_child = (parent != NULL); |
| 601 |
em->em_datatype = datatype; |
| 602 |
em->em_jdomain = jdomain; |
| 603 |
em->em_parent = parent; |
| 604 |
|
| 605 |
if (bms_is_empty(relids)) |
| 606 |
{ |
| 607 |
/* |
| 608 |
* No Vars, assume it's a pseudoconstant. This is correct for entries |
| 609 |
* generated from process_equivalence(), because a WHERE clause can't |
| 610 |
* contain aggregates or SRFs, and non-volatility was checked before |
| 611 |
* process_equivalence() ever got called. But |
| 612 |
* get_eclass_for_sort_expr() has to work harder. We put the tests |
| 613 |
* there not here to save cycles in the equivalence case. |
| 614 |
*/ |
| 615 |
Assert(!parent); |
| 616 |
em->em_is_const = true; |
| 617 |
ec->ec_has_const = true; |
| 618 |
/* it can't affect ec_relids */ |
| 619 |
} |
| 620 |
|
| 621 |
return em; |
| 622 |
} |
| 623 |
|
| 624 |
/* |
| 625 |
* add_eq_member - build a new non-child EquivalenceMember and add it to 'ec'. |
| 626 |
*/ |
| 627 |
static EquivalenceMember * |
| 628 |
add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids, |
| 629 |
JoinDomain *jdomain, Oid datatype) |
| 630 |
{ |
| 631 |
EquivalenceMember *em = make_eq_member(ec, expr, relids, jdomain, |
| 632 |
NULL, datatype); |
| 633 |
|
| 634 |
/* add to the members list */ |
| 635 |
ec->ec_members = lappend(ec->ec_members, em); |
| 636 |
|
| 637 |
/* record the relids for parent members */ |
| 638 |
ec->ec_relids = bms_add_members(ec->ec_relids, relids); |
| 639 |
|
| 640 |
return em; |
| 641 |
} |
| 642 |
|
| 643 |
/* |
| 644 |
* add_child_eq_member |
| 645 |
* Create an em_is_child=true EquivalenceMember and add it to 'ec'. |
| 646 |
* |
| 647 |
* 'root' is the PlannerInfo that 'ec' belongs to. |
| 648 |
* 'ec' is the EquivalenceClass to add the child member to. |
| 649 |
* 'ec_index' the index of 'ec' within root->eq_classes, or -1 if maintaining |
| 650 |
* the RelOptInfo.eclass_indexes isn't needed. |
| 651 |
* 'expr' is the em_expr for the new member. |
| 652 |
* 'relids' is the 'em_relids' for the new member. |
| 653 |
* 'jdomain' is the 'em_jdomain' for the new member. |
| 654 |
* 'parent_em' is the parent member of the child to create. |
| 655 |
* 'datatype' is the em_datatype of the new member. |
| 656 |
* 'child_relid' defines which element of ec_childmembers to add this member |
| 657 |
* to. This is generally a RELOPT_OTHER_MEMBER_REL, but for set operations |
| 658 |
* can be a RELOPT_BASEREL representing the set-op children. |
| 659 |
*/ |
| 660 |
static EquivalenceMember * |
| 661 |
add_child_eq_member(PlannerInfo *root, EquivalenceClass *ec, int ec_index, |
| 662 |
Expr *expr, Relids relids, JoinDomain *jdomain, |
| 663 |
EquivalenceMember *parent_em, Oid datatype, |
| 664 |
Index child_relid) |
| 665 |
{ |
| 666 |
EquivalenceMember *em; |
| 667 |
|
| 668 |
Assert(parent_em != NULL); |
| 669 |
|
| 670 |
/* |
| 671 |
* Allocate the array to store child members; an array of Lists indexed by |
| 672 |
* relid, or expand the existing one, if necessary. |
| 673 |
*/ |
| 674 |
if (unlikely(ec->ec_childmembers_size < root->simple_rel_array_size)) |
| 675 |
{ |
| 676 |
if (ec->ec_childmembers == NULL) |
| 677 |
ec->ec_childmembers = palloc0_array(List *, root->simple_rel_array_size); |
| 678 |
else |
| 679 |
ec->ec_childmembers = repalloc0_array(ec->ec_childmembers, List *, |
| 680 |
ec->ec_childmembers_size, |
| 681 |
root->simple_rel_array_size); |
| 682 |
|
| 683 |
ec->ec_childmembers_size = root->simple_rel_array_size; |
| 684 |
} |
| 685 |
|
| 686 |
em = make_eq_member(ec, expr, relids, jdomain, parent_em, datatype); |
| 687 |
|
| 688 |
/* add member to the ec_childmembers List for the given child_relid */ |
| 689 |
ec->ec_childmembers[child_relid] = lappend(ec->ec_childmembers[child_relid], em); |
| 690 |
|
| 691 |
/* Record this EC index for the child rel */ |
| 692 |
if (ec_index >= 0) |
| 693 |
{ |
| 694 |
RelOptInfo *child_rel = root->simple_rel_array[child_relid]; |
| 695 |
|
| 696 |
child_rel->eclass_indexes = |
| 697 |
bms_add_member(child_rel->eclass_indexes, ec_index); |
| 698 |
} |
| 699 |
|
| 700 |
return em; |
| 701 |
} |
| 702 |
|
| 703 |
|
| 704 |
/* |
| 705 |
* get_eclass_for_sort_expr |
| 706 |
* Given an expression and opfamily/collation info, find an existing |
| 707 |
* equivalence class it is a member of; if none, optionally build a new |
| 708 |
* single-member EquivalenceClass for it. |
| 709 |
* |
| 710 |
* sortref is the SortGroupRef of the originating SortGroupClause, if any, |
| 711 |
* or zero if not. (It should never be zero if the expression is volatile!) |
| 712 |
* |
| 713 |
* If rel is not NULL, it identifies a specific relation we're considering |
| 714 |
* a path for, and indicates that child EC members for that relation can be |
| 715 |
* considered. Otherwise child members are ignored. (Note: since child EC |
| 716 |
* members aren't guaranteed unique, a non-NULL value means that there could |
| 717 |
* be more than one EC that matches the expression; if so it's order-dependent |
| 718 |
* which one you get. This is annoying but it only happens in corner cases, |
| 719 |
* so for now we live with just reporting the first match. See also |
| 720 |
* generate_implied_equalities_for_column and match_pathkeys_to_index.) |
| 721 |
* |
| 722 |
* If create_it is true, we'll build a new EquivalenceClass when there is no |
| 723 |
* match. If create_it is false, we just return NULL when no match. |
| 724 |
* |
| 725 |
* This can be used safely both before and after EquivalenceClass merging; |
| 726 |
* since it never causes merging it does not invalidate any existing ECs |
| 727 |
* or PathKeys. However, ECs added after path generation has begun are |
| 728 |
* of limited usefulness, so usually it's best to create them beforehand. |
| 729 |
* |
| 730 |
* Note: opfamilies must be chosen consistently with the way |
| 731 |
* process_equivalence() would do; that is, generated from a mergejoinable |
| 732 |
* equality operator. Else we might fail to detect valid equivalences, |
| 733 |
* generating poor (but not incorrect) plans. |
| 734 |
*/ |
| 735 |
EquivalenceClass * |
| 736 |
get_eclass_for_sort_expr(PlannerInfo *root, |
| 737 |
Expr *expr, |
| 738 |
List *opfamilies, |
| 739 |
Oid opcintype, |
| 740 |
Oid collation, |
| 741 |
Index sortref, |
| 742 |
Relids rel, |
| 743 |
bool create_it) |
| 744 |
{ |
| 745 |
JoinDomain *jdomain; |
| 746 |
Relids expr_relids; |
| 747 |
EquivalenceClass *newec; |
| 748 |
EquivalenceMember *newem; |
| 749 |
ListCell *lc1; |
| 750 |
MemoryContext oldcontext; |
| 751 |
|
| 752 |
/* |
| 753 |
* Ensure the expression exposes the correct type and collation. |
| 754 |
*/ |
| 755 |
expr = canonicalize_ec_expression(expr, opcintype, collation); |
| 756 |
|
| 757 |
/* |
| 758 |
* Since SortGroupClause nodes are top-level expressions (GROUP BY, ORDER |
| 759 |
* BY, etc), they can be presumed to belong to the top JoinDomain. |
| 760 |
*/ |
| 761 |
jdomain = linitial_node(JoinDomain, root->join_domains); |
| 762 |
|
| 763 |
/* |
| 764 |
* Scan through the existing EquivalenceClasses for a match |
| 765 |
*/ |
| 766 |
foreach(lc1, root->eq_classes) |
| 767 |
{ |
| 768 |
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1); |
| 769 |
EquivalenceMemberIterator it; |
| 770 |
EquivalenceMember *cur_em; |
| 771 |
|
| 772 |
/* |
| 773 |
* Never match to a volatile EC, except when we are looking at another |
| 774 |
* reference to the same volatile SortGroupClause. |
| 775 |
*/ |
| 776 |
if (cur_ec->ec_has_volatile && |
| 777 |
(sortref == 0 || sortref != cur_ec->ec_sortref)) |
| 778 |
continue; |
| 779 |
|
| 780 |
if (collation != cur_ec->ec_collation) |
| 781 |
continue; |
| 782 |
if (!equal(opfamilies, cur_ec->ec_opfamilies)) |
| 783 |
continue; |
| 784 |
|
| 785 |
setup_eclass_member_iterator(&it, cur_ec, rel); |
| 786 |
while ((cur_em = eclass_member_iterator_next(&it)) != NULL) |
| 787 |
{ |
| 788 |
/* |
| 789 |
* Ignore child members unless they match the request. |
| 790 |
*/ |
| 791 |
if (cur_em->em_is_child && |
| 792 |
!bms_equal(cur_em->em_relids, rel)) |
| 793 |
continue; |
| 794 |
|
| 795 |
/* |
| 796 |
* Match constants only within the same JoinDomain (see |
| 797 |
* optimizer/README). |
| 798 |
*/ |
| 799 |
if (cur_em->em_is_const && cur_em->em_jdomain != jdomain) |
| 800 |
continue; |
| 801 |
|
| 802 |
if (opcintype == cur_em->em_datatype && |
| 803 |
equal(expr, cur_em->em_expr)) |
| 804 |
return cur_ec; /* Match! */ |
| 805 |
} |
| 806 |
} |
| 807 |
|
| 808 |
/* No match; does caller want a NULL result? */ |
| 809 |
if (!create_it) |
| 810 |
return NULL; |
| 811 |
|
| 812 |
/* |
| 813 |
* OK, build a new single-member EC |
| 814 |
* |
| 815 |
* Here, we must be sure that we construct the EC in the right context. |
| 816 |
*/ |
| 817 |
oldcontext = MemoryContextSwitchTo(root->planner_cxt); |
| 818 |
|
| 819 |
newec = makeNode(EquivalenceClass); |
| 820 |
newec->ec_opfamilies = list_copy(opfamilies); |
| 821 |
newec->ec_collation = collation; |
| 822 |
newec->ec_childmembers_size = 0; |
| 823 |
newec->ec_members = NIL; |
| 824 |
newec->ec_childmembers = NULL; |
| 825 |
newec->ec_sources = NIL; |
| 826 |
newec->ec_derives_list = NIL; |
| 827 |
newec->ec_derives_hash = NULL; |
| 828 |
newec->ec_relids = NULL; |
| 829 |
newec->ec_has_const = false; |
| 830 |
newec->ec_has_volatile = contain_volatile_functions((Node *) expr); |
| 831 |
newec->ec_broken = false; |
| 832 |
newec->ec_sortref = sortref; |
| 833 |
newec->ec_min_security = UINT_MAX; |
| 834 |
newec->ec_max_security = 0; |
| 835 |
newec->ec_merged = NULL; |
| 836 |
|
| 837 |
if (newec->ec_has_volatile && sortref == 0) /* should not happen */ |
| 838 |
elog(ERROR, "volatile EquivalenceClass has no sortref"); |
| 839 |
|
| 840 |
/* |
| 841 |
* Get the precise set of relids appearing in the expression. |
| 842 |
*/ |
| 843 |
expr_relids = pull_varnos(root, (Node *) expr); |
| 844 |
|
| 845 |
newem = add_eq_member(newec, copyObject(expr), expr_relids, |
| 846 |
jdomain, opcintype); |
| 847 |
|
| 848 |
/* |
| 849 |
* add_eq_member doesn't check for volatile functions, set-returning |
| 850 |
* functions, aggregates, or window functions, but such could appear in |
| 851 |
* sort expressions; so we have to check whether its const-marking was |
| 852 |
* correct. |
| 853 |
*/ |
| 854 |
if (newec->ec_has_const) |
| 855 |
{ |
| 856 |
if (newec->ec_has_volatile || |
| 857 |
expression_returns_set((Node *) expr) || |
| 858 |
contain_agg_clause((Node *) expr) || |
| 859 |
contain_window_function((Node *) expr)) |
| 860 |
{ |
| 861 |
newec->ec_has_const = false; |
| 862 |
newem->em_is_const = false; |
| 863 |
} |
| 864 |
} |
| 865 |
|
| 866 |
root->eq_classes = lappend(root->eq_classes, newec); |
| 867 |
|
| 868 |
/* |
| 869 |
* If EC merging is already complete, we have to mop up by adding the new |
| 870 |
* EC to the eclass_indexes of the relation(s) mentioned in it. |
| 871 |
*/ |
| 872 |
if (root->ec_merging_done) |
| 873 |
{ |
| 874 |
int ec_index = list_length(root->eq_classes) - 1; |
| 875 |
int i = -1; |
| 876 |
|
| 877 |
while ((i = bms_next_member(newec->ec_relids, i)) > 0) |
| 878 |
{ |
| 879 |
RelOptInfo *rel = root->simple_rel_array[i]; |
| 880 |
|
| 881 |
/* ignore the RTE_GROUP RTE */ |
| 882 |
if (i == root->group_rtindex) |
| 883 |
continue; |
| 884 |
|
| 885 |
if (rel == NULL) /* must be an outer join */ |
| 886 |
{ |
| 887 |
Assert(bms_is_member(i, root->outer_join_rels)); |
| 888 |
continue; |
| 889 |
} |
| 890 |
|
| 891 |
Assert(rel->reloptkind == RELOPT_BASEREL); |
| 892 |
|
| 893 |
rel->eclass_indexes = bms_add_member(rel->eclass_indexes, |
| 894 |
ec_index); |
| 895 |
} |
| 896 |
} |
| 897 |
|
| 898 |
MemoryContextSwitchTo(oldcontext); |
| 899 |
|
| 900 |
return newec; |
| 901 |
} |
| 902 |
|
| 903 |
/* |
| 904 |
* find_ec_member_matching_expr |
| 905 |
* Locate an EquivalenceClass member matching the given expr, if any; |
| 906 |
* return NULL if no match. |
| 907 |
* |
| 908 |
* "Matching" is defined as "equal after stripping RelabelTypes". |
| 909 |
* This is used for identifying sort expressions, and we need to allow |
| 910 |
* binary-compatible relabeling for some cases involving binary-compatible |
| 911 |
* sort operators. |
| 912 |
* |
| 913 |
* Child EC members are ignored unless they belong to given 'relids'. |
| 914 |
*/ |
| 915 |
EquivalenceMember * |
| 916 |
find_ec_member_matching_expr(EquivalenceClass *ec, |
| 917 |
Expr *expr, |
| 918 |
Relids relids) |
| 919 |
{ |
| 920 |
EquivalenceMemberIterator it; |
| 921 |
EquivalenceMember *em; |
| 922 |
|
| 923 |
/* We ignore binary-compatible relabeling on both ends */ |
| 924 |
while (expr && IsA(expr, RelabelType)) |
| 925 |
expr = ((RelabelType *) expr)->arg; |
| 926 |
|
| 927 |
setup_eclass_member_iterator(&it, ec, relids); |
| 928 |
while ((em = eclass_member_iterator_next(&it)) != NULL) |
| 929 |
{ |
| 930 |
Expr *emexpr; |
| 931 |
|
| 932 |
/* |
| 933 |
* We shouldn't be trying to sort by an equivalence class that |
| 934 |
* contains a constant, so no need to consider such cases any further. |
| 935 |
*/ |
| 936 |
if (em->em_is_const) |
| 937 |
continue; |
| 938 |
|
| 939 |
/* |
| 940 |
* Ignore child members unless they belong to the requested rel. |
| 941 |
*/ |
| 942 |
if (em->em_is_child && |
| 943 |
!bms_is_subset(em->em_relids, relids)) |
| 944 |
continue; |
| 945 |
|
| 946 |
/* |
| 947 |
* Match if same expression (after stripping relabel). |
| 948 |
*/ |
| 949 |
emexpr = em->em_expr; |
| 950 |
while (emexpr && IsA(emexpr, RelabelType)) |
| 951 |
emexpr = ((RelabelType *) emexpr)->arg; |
| 952 |
|
| 953 |
if (equal(emexpr, expr)) |
| 954 |
return em; |
| 955 |
} |
| 956 |
|
| 957 |
return NULL; |
| 958 |
} |
| 959 |
|
| 960 |
/* |
| 961 |
* find_computable_ec_member |
| 962 |
* Locate an EquivalenceClass member that can be computed from the |
| 963 |
* expressions appearing in "exprs"; return NULL if no match. |
| 964 |
* |
| 965 |
* "exprs" can be either a list of bare expression trees, or a list of |
| 966 |
* TargetEntry nodes. Typically it will contain Vars and possibly Aggrefs |
| 967 |
* and WindowFuncs; however, when considering an appendrel member the list |
| 968 |
* could contain arbitrary expressions. We consider an EC member to be |
| 969 |
* computable if all the Vars, PlaceHolderVars, Aggrefs, and WindowFuncs |
| 970 |
* it needs are present in "exprs". |
| 971 |
* |
| 972 |
* There is some subtlety in that definition: for example, if an EC member is |
| 973 |
* Var_A + 1 while what is in "exprs" is Var_A + 2, it's still computable. |
| 974 |
* This works because in the final plan tree, the EC member's expression will |
| 975 |
* be computed as part of the same plan node targetlist that is currently |
| 976 |
* represented by "exprs". So if we have Var_A available for the existing |
| 977 |
* tlist member, it must be OK to use it in the EC expression too. |
| 978 |
* |
| 979 |
* Unlike find_ec_member_matching_expr, there's no special provision here |
| 980 |
* for binary-compatible relabeling. This is intentional: if we have to |
| 981 |
* compute an expression in this way, setrefs.c is going to insist on exact |
| 982 |
* matches of Vars to the source tlist. |
| 983 |
* |
| 984 |
* Child EC members are ignored unless they belong to given 'relids'. |
| 985 |
* Also, non-parallel-safe expressions are ignored if 'require_parallel_safe'. |
| 986 |
* |
| 987 |
* Note: some callers pass root == NULL for notational reasons. This is OK |
| 988 |
* when require_parallel_safe is false. |
| 989 |
*/ |
| 990 |
EquivalenceMember * |
| 991 |
find_computable_ec_member(PlannerInfo *root, |
| 992 |
EquivalenceClass *ec, |
| 993 |
List *exprs, |
| 994 |
Relids relids, |
| 995 |
bool require_parallel_safe) |
| 996 |
{ |
| 997 |
List *exprvars; |
| 998 |
EquivalenceMemberIterator it; |
| 999 |
EquivalenceMember *em; |
| 1000 |
|
| 1001 |
/* |
| 1002 |
* Pull out the Vars and quasi-Vars present in "exprs". In the typical |
| 1003 |
* non-appendrel case, this is just another representation of the same |
| 1004 |
* list. However, it does remove the distinction between the case of a |
| 1005 |
* list of plain expressions and a list of TargetEntrys. |
| 1006 |
*/ |
| 1007 |
exprvars = pull_var_clause((Node *) exprs, |
| 1008 |
PVC_INCLUDE_AGGREGATES | |
| 1009 |
PVC_INCLUDE_WINDOWFUNCS | |
| 1010 |
PVC_INCLUDE_PLACEHOLDERS | |
| 1011 |
PVC_INCLUDE_CONVERTROWTYPES); |
| 1012 |
|
| 1013 |
setup_eclass_member_iterator(&it, ec, relids); |
| 1014 |
while ((em = eclass_member_iterator_next(&it)) != NULL) |
| 1015 |
{ |
| 1016 |
List *emvars; |
| 1017 |
ListCell *lc2; |
| 1018 |
|
| 1019 |
/* |
| 1020 |
* We shouldn't be trying to sort by an equivalence class that |
| 1021 |
* contains a constant, so no need to consider such cases any further. |
| 1022 |
*/ |
| 1023 |
if (em->em_is_const) |
| 1024 |
continue; |
| 1025 |
|
| 1026 |
/* |
| 1027 |
* Ignore child members unless they belong to the requested rel. |
| 1028 |
*/ |
| 1029 |
if (em->em_is_child && |
| 1030 |
!bms_is_subset(em->em_relids, relids)) |
| 1031 |
continue; |
| 1032 |
|
| 1033 |
/* |
| 1034 |
* Match if all Vars and quasi-Vars are present in "exprs". |
| 1035 |
*/ |
| 1036 |
emvars = pull_var_clause((Node *) em->em_expr, |
| 1037 |
PVC_INCLUDE_AGGREGATES | |
| 1038 |
PVC_INCLUDE_WINDOWFUNCS | |
| 1039 |
PVC_INCLUDE_PLACEHOLDERS); |
| 1040 |
foreach(lc2, emvars) |
| 1041 |
{ |
| 1042 |
if (!list_member(exprvars, lfirst(lc2))) |
| 1043 |
break; |
| 1044 |
} |
| 1045 |
list_free(emvars); |
| 1046 |
if (lc2) |
| 1047 |
continue; /* we hit a non-available Var */ |
| 1048 |
|
| 1049 |
/* |
| 1050 |
* If requested, reject expressions that are not parallel-safe. We |
| 1051 |
* check this last because it's a rather expensive test. |
| 1052 |
*/ |
| 1053 |
if (require_parallel_safe && |
| 1054 |
!is_parallel_safe(root, (Node *) em->em_expr)) |
| 1055 |
continue; |
| 1056 |
|
| 1057 |
return em; /* found usable expression */ |
| 1058 |
} |
| 1059 |
|
| 1060 |
return NULL; |
| 1061 |
} |
| 1062 |
|
| 1063 |
/* |
| 1064 |
* relation_can_be_sorted_early |
| 1065 |
* Can this relation be sorted on this EC before the final output step? |
| 1066 |
* |
| 1067 |
* To succeed, we must find an EC member that prepare_sort_from_pathkeys knows |
| 1068 |
* how to sort on, given the rel's reltarget as input. There are also a few |
| 1069 |
* additional constraints based on the fact that the desired sort will be done |
| 1070 |
* "early", within the scan/join part of the plan. Also, non-parallel-safe |
| 1071 |
* expressions are ignored if 'require_parallel_safe'. |
| 1072 |
* |
| 1073 |
* At some point we might want to return the identified EquivalenceMember, |
| 1074 |
* but for now, callers only want to know if there is one. |
| 1075 |
*/ |
| 1076 |
bool |
| 1077 |
relation_can_be_sorted_early(PlannerInfo *root, RelOptInfo *rel, |
| 1078 |
EquivalenceClass *ec, bool require_parallel_safe) |
| 1079 |
{ |
| 1080 |
PathTarget *target = rel->reltarget; |
| 1081 |
EquivalenceMember *em; |
| 1082 |
ListCell *lc; |
| 1083 |
|
| 1084 |
/* |
| 1085 |
* Reject volatile ECs immediately; such sorts must always be postponed. |
| 1086 |
*/ |
| 1087 |
if (ec->ec_has_volatile) |
| 1088 |
return false; |
| 1089 |
|
| 1090 |
/* |
| 1091 |
* Try to find an EM directly matching some reltarget member. |
| 1092 |
*/ |
| 1093 |
foreach(lc, target->exprs) |
| 1094 |
{ |
| 1095 |
Expr *targetexpr = (Expr *) lfirst(lc); |
| 1096 |
|
| 1097 |
em = find_ec_member_matching_expr(ec, targetexpr, rel->relids); |
| 1098 |
if (!em) |
| 1099 |
continue; |
| 1100 |
|
| 1101 |
/* |
| 1102 |
* Reject expressions involving set-returning functions, as those |
| 1103 |
* can't be computed early either. (Note: this test and the following |
| 1104 |
* one are effectively checking properties of targetexpr, so there's |
| 1105 |
* no point in asking whether some other EC member would be better.) |
| 1106 |
*/ |
| 1107 |
if (expression_returns_set((Node *) em->em_expr)) |
| 1108 |
continue; |
| 1109 |
|
| 1110 |
/* |
| 1111 |
* If requested, reject expressions that are not parallel-safe. We |
| 1112 |
* check this last because it's a rather expensive test. |
| 1113 |
*/ |
| 1114 |
if (require_parallel_safe && |
| 1115 |
!is_parallel_safe(root, (Node *) em->em_expr)) |
| 1116 |
continue; |
| 1117 |
|
| 1118 |
return true; |
| 1119 |
} |
| 1120 |
|
| 1121 |
/* |
| 1122 |
* Try to find an expression computable from the reltarget. |
| 1123 |
*/ |
| 1124 |
em = find_computable_ec_member(root, ec, target->exprs, rel->relids, |
| 1125 |
require_parallel_safe); |
| 1126 |
if (!em) |
| 1127 |
return false; |
| 1128 |
|
| 1129 |
/* |
| 1130 |
* Reject expressions involving set-returning functions, as those can't be |
| 1131 |
* computed early either. (There's no point in looking for another EC |
| 1132 |
* member in this case; since SRFs can't appear in WHERE, they cannot |
| 1133 |
* belong to multi-member ECs.) |
| 1134 |
*/ |
| 1135 |
if (expression_returns_set((Node *) em->em_expr)) |
| 1136 |
return false; |
| 1137 |
|
| 1138 |
return true; |
| 1139 |
} |
| 1140 |
|
| 1141 |
/* |
| 1142 |
* generate_base_implied_equalities |
| 1143 |
* Generate any restriction clauses that we can deduce from equivalence |
| 1144 |
* classes. |
| 1145 |
* |
| 1146 |
* When an EC contains pseudoconstants, our strategy is to generate |
| 1147 |
* "member = const1" clauses where const1 is the first constant member, for |
| 1148 |
* every other member (including other constants). If we are able to do this |
| 1149 |
* then we don't need any "var = var" comparisons because we've successfully |
| 1150 |
* constrained all the vars at their points of creation. If we fail to |
| 1151 |
* generate any of these clauses due to lack of cross-type operators, we fall |
| 1152 |
* back to the "ec_broken" strategy described below. (XXX if there are |
| 1153 |
* multiple constants of different types, it's possible that we might succeed |
| 1154 |
* in forming all the required clauses if we started from a different const |
| 1155 |
* member; but this seems a sufficiently hokey corner case to not be worth |
| 1156 |
* spending lots of cycles on.) |
| 1157 |
* |
| 1158 |
* For ECs that contain no pseudoconstants, we generate derived clauses |
| 1159 |
* "member1 = member2" for each pair of members belonging to the same base |
| 1160 |
* relation (actually, if there are more than two for the same base relation, |
| 1161 |
* we only need enough clauses to link each to each other). This provides |
| 1162 |
* the base case for the recursion: each row emitted by a base relation scan |
| 1163 |
* will constrain all computable members of the EC to be equal. As each |
| 1164 |
* join path is formed, we'll add additional derived clauses on-the-fly |
| 1165 |
* to maintain this invariant (see generate_join_implied_equalities). |
| 1166 |
* |
| 1167 |
* If the opfamilies used by the EC do not provide complete sets of cross-type |
| 1168 |
* equality operators, it is possible that we will fail to generate a clause |
| 1169 |
* that must be generated to maintain the invariant. (An example: given |
| 1170 |
* "WHERE a.x = b.y AND b.y = a.z", the scheme breaks down if we cannot |
| 1171 |
* generate "a.x = a.z" as a restriction clause for A.) In this case we mark |
| 1172 |
* the EC "ec_broken" and fall back to regurgitating its original source |
| 1173 |
* RestrictInfos at appropriate times. We do not try to retract any derived |
| 1174 |
* clauses already generated from the broken EC, so the resulting plan could |
| 1175 |
* be poor due to bad selectivity estimates caused by redundant clauses. But |
| 1176 |
* the correct solution to that is to fix the opfamilies ... |
| 1177 |
* |
| 1178 |
* Equality clauses derived by this function are passed off to |
| 1179 |
* process_implied_equality (in plan/initsplan.c) to be inserted into the |
| 1180 |
* restrictinfo datastructures. Note that this must be called after initial |
| 1181 |
* scanning of the quals and before Path construction begins. |
| 1182 |
* |
| 1183 |
* We make no attempt to avoid generating duplicate RestrictInfos here: we |
| 1184 |
* don't search existing source or derived clauses in the EC for matches. It |
| 1185 |
* doesn't really seem worth the trouble to do so. |
| 1186 |
*/ |
| 1187 |
void |
| 1188 |
generate_base_implied_equalities(PlannerInfo *root) |
| 1189 |
{ |
| 1190 |
int ec_index; |
| 1191 |
ListCell *lc; |
| 1192 |
|
| 1193 |
/* |
| 1194 |
* At this point, we're done absorbing knowledge of equivalences in the |
| 1195 |
* query, so no further EC merging should happen, and ECs remaining in the |
| 1196 |
* eq_classes list can be considered canonical. (But note that it's still |
| 1197 |
* possible for new single-member ECs to be added through |
| 1198 |
* get_eclass_for_sort_expr().) |
| 1199 |
*/ |
| 1200 |
root->ec_merging_done = true; |
| 1201 |
|
| 1202 |
ec_index = 0; |
| 1203 |
foreach(lc, root->eq_classes) |
| 1204 |
{ |
| 1205 |
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc); |
| 1206 |
bool can_generate_joinclause = false; |
| 1207 |
int i; |
| 1208 |
|
| 1209 |
Assert(ec->ec_merged == NULL); /* else shouldn't be in list */ |
| 1210 |
Assert(!ec->ec_broken); /* not yet anyway... */ |
| 1211 |
|
| 1212 |
/* |
| 1213 |
* Generate implied equalities that are restriction clauses. |
| 1214 |
* Single-member ECs won't generate any deductions, either here or at |
| 1215 |
* the join level. |
| 1216 |
*/ |
| 1217 |
if (list_length(ec->ec_members) > 1) |
| 1218 |
{ |
| 1219 |
if (ec->ec_has_const) |
| 1220 |
generate_base_implied_equalities_const(root, ec); |
| 1221 |
else |
| 1222 |
generate_base_implied_equalities_no_const(root, ec); |
| 1223 |
|
| 1224 |
/* Recover if we failed to generate required derived clauses */ |
| 1225 |
if (ec->ec_broken) |
| 1226 |
generate_base_implied_equalities_broken(root, ec); |
| 1227 |
|
| 1228 |
/* Detect whether this EC might generate join clauses */ |
| 1229 |
can_generate_joinclause = |
| 1230 |
(bms_membership(ec->ec_relids) == BMS_MULTIPLE); |
| 1231 |
} |
| 1232 |
|
| 1233 |
/* |
| 1234 |
* Mark the base rels cited in each eclass (which should all exist by |
| 1235 |
* now) with the eq_classes indexes of all eclasses mentioning them. |
| 1236 |
* This will let us avoid searching in subsequent lookups. While |
| 1237 |
* we're at it, we can mark base rels that have pending eclass joins; |
| 1238 |
* this is a cheap version of has_relevant_eclass_joinclause(). |
| 1239 |
*/ |
| 1240 |
i = -1; |
| 1241 |
while ((i = bms_next_member(ec->ec_relids, i)) > 0) |
| 1242 |
{ |
| 1243 |
RelOptInfo *rel = root->simple_rel_array[i]; |
| 1244 |
|
| 1245 |
/* ignore the RTE_GROUP RTE */ |
| 1246 |
if (i == root->group_rtindex) |
| 1247 |
continue; |
| 1248 |
|
| 1249 |
if (rel == NULL) /* must be an outer join */ |
| 1250 |
{ |
| 1251 |
Assert(bms_is_member(i, root->outer_join_rels)); |
| 1252 |
continue; |
| 1253 |
} |
| 1254 |
|
| 1255 |
Assert(rel->reloptkind == RELOPT_BASEREL); |
| 1256 |
|
| 1257 |
rel->eclass_indexes = bms_add_member(rel->eclass_indexes, |
| 1258 |
ec_index); |
| 1259 |
|
| 1260 |
if (can_generate_joinclause) |
| 1261 |
rel->has_eclass_joins = true; |
| 1262 |
} |
| 1263 |
|
| 1264 |
ec_index++; |
| 1265 |
} |
| 1266 |
} |
| 1267 |
|
| 1268 |
/* |
| 1269 |
* generate_base_implied_equalities when EC contains pseudoconstant(s) |
| 1270 |
*/ |
| 1271 |
static void |
| 1272 |
generate_base_implied_equalities_const(PlannerInfo *root, |
| 1273 |
EquivalenceClass *ec) |
| 1274 |
{ |
| 1275 |
EquivalenceMember *const_em = NULL; |
| 1276 |
ListCell *lc; |
| 1277 |
|
| 1278 |
/* |
| 1279 |
* In the trivial case where we just had one "var = const" clause, push |
| 1280 |
* the original clause back into the main planner machinery. There is |
| 1281 |
* nothing to be gained by doing it differently, and we save the effort to |
| 1282 |
* re-build and re-analyze an equality clause that will be exactly |
| 1283 |
* equivalent to the old one. |
| 1284 |
*/ |
| 1285 |
if (list_length(ec->ec_members) == 2 && |
| 1286 |
list_length(ec->ec_sources) == 1) |
| 1287 |
{ |
| 1288 |
RestrictInfo *restrictinfo = (RestrictInfo *) linitial(ec->ec_sources); |
| 1289 |
|
| 1290 |
distribute_restrictinfo_to_rels(root, restrictinfo); |
| 1291 |
return; |
| 1292 |
} |
| 1293 |
|
| 1294 |
/* We don't expect any children yet */ |
| 1295 |
Assert(ec->ec_childmembers == NULL); |
| 1296 |
|
| 1297 |
/* |
| 1298 |
* Find the constant member to use. We prefer an actual constant to |
| 1299 |
* pseudo-constants (such as Params), because the constraint exclusion |
| 1300 |
* machinery might be able to exclude relations on the basis of generated |
| 1301 |
* "var = const" equalities, but "var = param" won't work for that. |
| 1302 |
*/ |
| 1303 |
foreach(lc, ec->ec_members) |
| 1304 |
{ |
| 1305 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc); |
| 1306 |
|
| 1307 |
if (cur_em->em_is_const) |
| 1308 |
{ |
| 1309 |
const_em = cur_em; |
| 1310 |
if (IsA(cur_em->em_expr, Const)) |
| 1311 |
break; |
| 1312 |
} |
| 1313 |
} |
| 1314 |
Assert(const_em != NULL); |
| 1315 |
|
| 1316 |
/* Generate a derived equality against each other member */ |
| 1317 |
foreach(lc, ec->ec_members) |
| 1318 |
{ |
| 1319 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc); |
| 1320 |
Oid eq_op; |
| 1321 |
RestrictInfo *rinfo; |
| 1322 |
|
| 1323 |
/* Child members should not exist in ec_members */ |
| 1324 |
Assert(!cur_em->em_is_child); |
| 1325 |
if (cur_em == const_em) |
| 1326 |
continue; |
| 1327 |
eq_op = select_equality_operator(ec, |
| 1328 |
cur_em->em_datatype, |
| 1329 |
const_em->em_datatype); |
| 1330 |
if (!OidIsValid(eq_op)) |
| 1331 |
{ |
| 1332 |
/* failed... */ |
| 1333 |
ec->ec_broken = true; |
| 1334 |
break; |
| 1335 |
} |
| 1336 |
|
| 1337 |
/* |
| 1338 |
* We use the constant's em_jdomain as qualscope, so that if the |
| 1339 |
* generated clause is variable-free (i.e, both EMs are consts) it |
| 1340 |
* will be enforced at the join domain level. |
| 1341 |
*/ |
| 1342 |
rinfo = process_implied_equality(root, eq_op, ec->ec_collation, |
| 1343 |
cur_em->em_expr, const_em->em_expr, |
| 1344 |
const_em->em_jdomain->jd_relids, |
| 1345 |
ec->ec_min_security, |
| 1346 |
cur_em->em_is_const); |
| 1347 |
|
| 1348 |
/* |
| 1349 |
* If the clause didn't degenerate to a constant, fill in the correct |
| 1350 |
* markings for a mergejoinable clause, and save it as a derived |
| 1351 |
* clause. (We will not re-use such clauses directly, but selectivity |
| 1352 |
* estimation may consult those later. Note that this use of derived |
| 1353 |
* clauses does not overlap with its use for join clauses, since we |
| 1354 |
* never generate join clauses from an ec_has_const eclass.) |
| 1355 |
*/ |
| 1356 |
if (rinfo && rinfo->mergeopfamilies) |
| 1357 |
{ |
| 1358 |
/* it's not redundant, so don't set parent_ec */ |
| 1359 |
rinfo->left_ec = rinfo->right_ec = ec; |
| 1360 |
rinfo->left_em = cur_em; |
| 1361 |
rinfo->right_em = const_em; |
| 1362 |
ec_add_derived_clause(ec, rinfo); |
| 1363 |
} |
| 1364 |
} |
| 1365 |
} |
| 1366 |
|
| 1367 |
/* |
| 1368 |
* generate_base_implied_equalities when EC contains no pseudoconstants |
| 1369 |
*/ |
| 1370 |
static void |
| 1371 |
generate_base_implied_equalities_no_const(PlannerInfo *root, |
| 1372 |
EquivalenceClass *ec) |
| 1373 |
{ |
| 1374 |
EquivalenceMember **prev_ems; |
| 1375 |
ListCell *lc; |
| 1376 |
|
| 1377 |
/* |
| 1378 |
* We scan the EC members once and track the last-seen member for each |
| 1379 |
* base relation. When we see another member of the same base relation, |
| 1380 |
* we generate "prev_em = cur_em". This results in the minimum number of |
| 1381 |
* derived clauses, but it's possible that it will fail when a different |
| 1382 |
* ordering would succeed. XXX FIXME: use a UNION-FIND algorithm similar |
| 1383 |
* to the way we build merged ECs. (Use a list-of-lists for each rel.) |
| 1384 |
*/ |
| 1385 |
prev_ems = (EquivalenceMember **) |
| 1386 |
palloc0(root->simple_rel_array_size * sizeof(EquivalenceMember *)); |
| 1387 |
|
| 1388 |
/* We don't expect any children yet */ |
| 1389 |
Assert(ec->ec_childmembers == NULL); |
| 1390 |
|
| 1391 |
foreach(lc, ec->ec_members) |
| 1392 |
{ |
| 1393 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc); |
| 1394 |
int relid; |
| 1395 |
|
| 1396 |
/* Child members should not exist in ec_members */ |
| 1397 |
Assert(!cur_em->em_is_child); |
| 1398 |
|
| 1399 |
if (!bms_get_singleton_member(cur_em->em_relids, &relid)) |
| 1400 |
continue; |
| 1401 |
Assert(relid < root->simple_rel_array_size); |
| 1402 |
|
| 1403 |
if (prev_ems[relid] != NULL) |
| 1404 |
{ |
| 1405 |
EquivalenceMember *prev_em = prev_ems[relid]; |
| 1406 |
Oid eq_op; |
| 1407 |
RestrictInfo *rinfo; |
| 1408 |
|
| 1409 |
eq_op = select_equality_operator(ec, |
| 1410 |
prev_em->em_datatype, |
| 1411 |
cur_em->em_datatype); |
| 1412 |
if (!OidIsValid(eq_op)) |
| 1413 |
{ |
| 1414 |
/* failed... */ |
| 1415 |
ec->ec_broken = true; |
| 1416 |
break; |
| 1417 |
} |
| 1418 |
|
| 1419 |
/* |
| 1420 |
* The expressions aren't constants, so the passed qualscope will |
| 1421 |
* never be used to place the generated clause. We just need to |
| 1422 |
* be sure it covers both expressions, which em_relids should do. |
| 1423 |
*/ |
| 1424 |
rinfo = process_implied_equality(root, eq_op, ec->ec_collation, |
| 1425 |
prev_em->em_expr, cur_em->em_expr, |
| 1426 |
cur_em->em_relids, |
| 1427 |
ec->ec_min_security, |
| 1428 |
false); |
| 1429 |
|
| 1430 |
/* |
| 1431 |
* If the clause didn't degenerate to a constant, fill in the |
| 1432 |
* correct markings for a mergejoinable clause. We don't record |
| 1433 |
* it as a derived clause, since we don't currently need to |
| 1434 |
* re-find such clauses, and don't want to clutter the |
| 1435 |
* derived-clause set with non-join clauses. |
| 1436 |
*/ |
| 1437 |
if (rinfo && rinfo->mergeopfamilies) |
| 1438 |
{ |
| 1439 |
/* it's not redundant, so don't set parent_ec */ |
| 1440 |
rinfo->left_ec = rinfo->right_ec = ec; |
| 1441 |
rinfo->left_em = prev_em; |
| 1442 |
rinfo->right_em = cur_em; |
| 1443 |
} |
| 1444 |
} |
| 1445 |
prev_ems[relid] = cur_em; |
| 1446 |
} |
| 1447 |
|
| 1448 |
pfree(prev_ems); |
| 1449 |
|
| 1450 |
/* |
| 1451 |
* We also have to make sure that all the Vars used in the member clauses |
| 1452 |
* will be available at any join node we might try to reference them at. |
| 1453 |
* For the moment we force all the Vars to be available at all join nodes |
| 1454 |
* for this eclass. Perhaps this could be improved by doing some |
| 1455 |
* pre-analysis of which members we prefer to join, but it's no worse than |
| 1456 |
* what happened in the pre-8.3 code. (Note: rebuild_eclass_attr_needed |
| 1457 |
* needs to match this code.) |
| 1458 |
*/ |
| 1459 |
foreach(lc, ec->ec_members) |
| 1460 |
{ |
| 1461 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc); |
| 1462 |
List *vars = pull_var_clause((Node *) cur_em->em_expr, |
| 1463 |
PVC_RECURSE_AGGREGATES | |
| 1464 |
PVC_RECURSE_WINDOWFUNCS | |
| 1465 |
PVC_INCLUDE_PLACEHOLDERS); |
| 1466 |
|
| 1467 |
add_vars_to_targetlist(root, vars, ec->ec_relids); |
| 1468 |
list_free(vars); |
| 1469 |
} |
| 1470 |
} |
| 1471 |
|
| 1472 |
/* |
| 1473 |
* generate_base_implied_equalities cleanup after failure |
| 1474 |
* |
| 1475 |
* What we must do here is push any zero- or one-relation source RestrictInfos |
| 1476 |
* of the EC back into the main restrictinfo datastructures. Multi-relation |
| 1477 |
* clauses will be regurgitated later by generate_join_implied_equalities(). |
| 1478 |
* (We do it this way to maintain continuity with the case that ec_broken |
| 1479 |
* becomes set only after we've gone up a join level or two.) However, for |
| 1480 |
* an EC that contains constants, we can adopt a simpler strategy and just |
| 1481 |
* throw back all the source RestrictInfos immediately; that works because |
| 1482 |
* we know that such an EC can't become broken later. (This rule justifies |
| 1483 |
* ignoring ec_has_const ECs in generate_join_implied_equalities, even when |
| 1484 |
* they are broken.) |
| 1485 |
*/ |
| 1486 |
static void |
| 1487 |
generate_base_implied_equalities_broken(PlannerInfo *root, |
| 1488 |
EquivalenceClass *ec) |
| 1489 |
{ |
| 1490 |
ListCell *lc; |
| 1491 |
|
| 1492 |
foreach(lc, ec->ec_sources) |
| 1493 |
{ |
| 1494 |
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc); |
| 1495 |
|
| 1496 |
if (ec->ec_has_const || |
| 1497 |
bms_membership(restrictinfo->required_relids) != BMS_MULTIPLE) |
| 1498 |
distribute_restrictinfo_to_rels(root, restrictinfo); |
| 1499 |
} |
| 1500 |
} |
| 1501 |
|
| 1502 |
|
| 1503 |
/* |
| 1504 |
* generate_join_implied_equalities |
| 1505 |
* Generate any join clauses that we can deduce from equivalence classes. |
| 1506 |
* |
| 1507 |
* At a join node, we must enforce restriction clauses sufficient to ensure |
| 1508 |
* that all equivalence-class members computable at that node are equal. |
| 1509 |
* Since the set of clauses to enforce can vary depending on which subset |
| 1510 |
* relations are the inputs, we have to compute this afresh for each join |
| 1511 |
* relation pair. Hence a fresh List of RestrictInfo nodes is built and |
| 1512 |
* passed back on each call. |
| 1513 |
* |
| 1514 |
* In addition to its use at join nodes, this can be applied to generate |
| 1515 |
* eclass-based join clauses for use in a parameterized scan of a base rel. |
| 1516 |
* The reason for the asymmetry of specifying the inner rel as a RelOptInfo |
| 1517 |
* and the outer rel by Relids is that this usage occurs before we have |
| 1518 |
* built any join RelOptInfos. |
| 1519 |
* |
| 1520 |
* An annoying special case for parameterized scans is that the inner rel can |
| 1521 |
* be an appendrel child (an "other rel"). In this case we must generate |
| 1522 |
* appropriate clauses using child EC members. add_child_rel_equivalences |
| 1523 |
* must already have been done for the child rel. |
| 1524 |
* |
| 1525 |
* The results are sufficient for use in merge, hash, and plain nestloop join |
| 1526 |
* methods. We do not worry here about selecting clauses that are optimal |
| 1527 |
* for use in a parameterized indexscan. indxpath.c makes its own selections |
| 1528 |
* of clauses to use, and if the ones we pick here are redundant with those, |
| 1529 |
* the extras will be eliminated at createplan time, using the parent_ec |
| 1530 |
* markers that we provide (see is_redundant_derived_clause()). |
| 1531 |
* |
| 1532 |
* Because the same join clauses are likely to be needed multiple times as |
| 1533 |
* we consider different join paths, we avoid generating multiple copies: |
| 1534 |
* whenever we select a particular pair of EquivalenceMembers to join, |
| 1535 |
* we check to see if the pair matches any original clause (in ec_sources) |
| 1536 |
* or previously-built derived clause. This saves memory and allows |
| 1537 |
* re-use of information cached in RestrictInfos. We also avoid generating |
| 1538 |
* commutative duplicates, i.e. if the algorithm selects "a.x = b.y" but |
| 1539 |
* we already have "b.y = a.x", we return the existing clause. |
| 1540 |
* |
| 1541 |
* If we are considering an outer join, sjinfo is the associated OJ info, |
| 1542 |
* otherwise it can be NULL. |
| 1543 |
* |
| 1544 |
* join_relids should always equal bms_union(outer_relids, inner_rel->relids) |
| 1545 |
* plus whatever add_outer_joins_to_relids() would add. We could simplify |
| 1546 |
* this function's API by computing it internally, but most callers have the |
| 1547 |
* value at hand anyway. |
| 1548 |
*/ |
| 1549 |
List * |
| 1550 |
generate_join_implied_equalities(PlannerInfo *root, |
| 1551 |
Relids join_relids, |
| 1552 |
Relids outer_relids, |
| 1553 |
RelOptInfo *inner_rel, |
| 1554 |
SpecialJoinInfo *sjinfo) |
| 1555 |
{ |
| 1556 |
List *result = NIL; |
| 1557 |
Relids inner_relids = inner_rel->relids; |
| 1558 |
Relids nominal_inner_relids; |
| 1559 |
Relids nominal_join_relids; |
| 1560 |
Bitmapset *matching_ecs; |
| 1561 |
int i; |
| 1562 |
|
| 1563 |
/* If inner rel is a child, extra setup work is needed */ |
| 1564 |
if (IS_OTHER_REL(inner_rel)) |
| 1565 |
{ |
| 1566 |
Assert(!bms_is_empty(inner_rel->top_parent_relids)); |
| 1567 |
|
| 1568 |
/* Fetch relid set for the topmost parent rel */ |
| 1569 |
nominal_inner_relids = inner_rel->top_parent_relids; |
| 1570 |
/* ECs will be marked with the parent's relid, not the child's */ |
| 1571 |
nominal_join_relids = bms_union(outer_relids, nominal_inner_relids); |
| 1572 |
nominal_join_relids = add_outer_joins_to_relids(root, |
| 1573 |
nominal_join_relids, |
| 1574 |
sjinfo, |
| 1575 |
NULL); |
| 1576 |
} |
| 1577 |
else |
| 1578 |
{ |
| 1579 |
nominal_inner_relids = inner_relids; |
| 1580 |
nominal_join_relids = join_relids; |
| 1581 |
} |
| 1582 |
|
| 1583 |
/* |
| 1584 |
* Examine all potentially-relevant eclasses. |
| 1585 |
* |
| 1586 |
* If we are considering an outer join, we must include "join" clauses |
| 1587 |
* that mention either input rel plus the outer join's relid; these |
| 1588 |
* represent post-join filter clauses that have to be applied at this |
| 1589 |
* join. We don't have infrastructure that would let us identify such |
| 1590 |
* eclasses cheaply, so just fall back to considering all eclasses |
| 1591 |
* mentioning anything in nominal_join_relids. |
| 1592 |
* |
| 1593 |
* At inner joins, we can be smarter: only consider eclasses mentioning |
| 1594 |
* both input rels. |
| 1595 |
*/ |
| 1596 |
if (sjinfo && sjinfo->ojrelid != 0) |
| 1597 |
matching_ecs = get_eclass_indexes_for_relids(root, nominal_join_relids); |
| 1598 |
else |
| 1599 |
matching_ecs = get_common_eclass_indexes(root, nominal_inner_relids, |
| 1600 |
outer_relids); |
| 1601 |
|
| 1602 |
i = -1; |
| 1603 |
while ((i = bms_next_member(matching_ecs, i)) >= 0) |
| 1604 |
{ |
| 1605 |
EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i); |
| 1606 |
List *sublist = NIL; |
| 1607 |
|
| 1608 |
/* ECs containing consts do not need any further enforcement */ |
| 1609 |
if (ec->ec_has_const) |
| 1610 |
continue; |
| 1611 |
|
| 1612 |
/* Single-member ECs won't generate any deductions */ |
| 1613 |
if (list_length(ec->ec_members) <= 1) |
| 1614 |
continue; |
| 1615 |
|
| 1616 |
/* Sanity check that this eclass overlaps the join */ |
| 1617 |
Assert(bms_overlap(ec->ec_relids, nominal_join_relids)); |
| 1618 |
|
| 1619 |
if (!ec->ec_broken) |
| 1620 |
sublist = generate_join_implied_equalities_normal(root, |
| 1621 |
ec, |
| 1622 |
join_relids, |
| 1623 |
outer_relids, |
| 1624 |
inner_relids); |
| 1625 |
|
| 1626 |
/* Recover if we failed to generate required derived clauses */ |
| 1627 |
if (ec->ec_broken) |
| 1628 |
sublist = generate_join_implied_equalities_broken(root, |
| 1629 |
ec, |
| 1630 |
nominal_join_relids, |
| 1631 |
outer_relids, |
| 1632 |
nominal_inner_relids, |
| 1633 |
inner_rel); |
| 1634 |
|
| 1635 |
result = list_concat(result, sublist); |
| 1636 |
} |
| 1637 |
|
| 1638 |
return result; |
| 1639 |
} |
| 1640 |
|
| 1641 |
/* |
| 1642 |
* generate_join_implied_equalities_for_ecs |
| 1643 |
* As above, but consider only the listed ECs. |
| 1644 |
* |
| 1645 |
* For the sole current caller, we can assume sjinfo == NULL, that is we are |
| 1646 |
* not interested in outer-join filter clauses. This might need to change |
| 1647 |
* in future. |
| 1648 |
*/ |
| 1649 |
List * |
| 1650 |
generate_join_implied_equalities_for_ecs(PlannerInfo *root, |
| 1651 |
List *eclasses, |
| 1652 |
Relids join_relids, |
| 1653 |
Relids outer_relids, |
| 1654 |
RelOptInfo *inner_rel) |
| 1655 |
{ |
| 1656 |
List *result = NIL; |
| 1657 |
Relids inner_relids = inner_rel->relids; |
| 1658 |
Relids nominal_inner_relids; |
| 1659 |
Relids nominal_join_relids; |
| 1660 |
ListCell *lc; |
| 1661 |
|
| 1662 |
/* If inner rel is a child, extra setup work is needed */ |
| 1663 |
if (IS_OTHER_REL(inner_rel)) |
| 1664 |
{ |
| 1665 |
Assert(!bms_is_empty(inner_rel->top_parent_relids)); |
| 1666 |
|
| 1667 |
/* Fetch relid set for the topmost parent rel */ |
| 1668 |
nominal_inner_relids = inner_rel->top_parent_relids; |
| 1669 |
/* ECs will be marked with the parent's relid, not the child's */ |
| 1670 |
nominal_join_relids = bms_union(outer_relids, nominal_inner_relids); |
| 1671 |
} |
| 1672 |
else |
| 1673 |
{ |
| 1674 |
nominal_inner_relids = inner_relids; |
| 1675 |
nominal_join_relids = join_relids; |
| 1676 |
} |
| 1677 |
|
| 1678 |
foreach(lc, eclasses) |
| 1679 |
{ |
| 1680 |
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc); |
| 1681 |
List *sublist = NIL; |
| 1682 |
|
| 1683 |
/* ECs containing consts do not need any further enforcement */ |
| 1684 |
if (ec->ec_has_const) |
| 1685 |
continue; |
| 1686 |
|
| 1687 |
/* Single-member ECs won't generate any deductions */ |
| 1688 |
if (list_length(ec->ec_members) <= 1) |
| 1689 |
continue; |
| 1690 |
|
| 1691 |
/* We can quickly ignore any that don't overlap the join, too */ |
| 1692 |
if (!bms_overlap(ec->ec_relids, nominal_join_relids)) |
| 1693 |
continue; |
| 1694 |
|
| 1695 |
if (!ec->ec_broken) |
| 1696 |
sublist = generate_join_implied_equalities_normal(root, |
| 1697 |
ec, |
| 1698 |
join_relids, |
| 1699 |
outer_relids, |
| 1700 |
inner_relids); |
| 1701 |
|
| 1702 |
/* Recover if we failed to generate required derived clauses */ |
| 1703 |
if (ec->ec_broken) |
| 1704 |
sublist = generate_join_implied_equalities_broken(root, |
| 1705 |
ec, |
| 1706 |
nominal_join_relids, |
| 1707 |
outer_relids, |
| 1708 |
nominal_inner_relids, |
| 1709 |
inner_rel); |
| 1710 |
|
| 1711 |
result = list_concat(result, sublist); |
| 1712 |
} |
| 1713 |
|
| 1714 |
return result; |
| 1715 |
} |
| 1716 |
|
| 1717 |
/* |
| 1718 |
* generate_join_implied_equalities for a still-valid EC |
| 1719 |
*/ |
| 1720 |
static List * |
| 1721 |
generate_join_implied_equalities_normal(PlannerInfo *root, |
| 1722 |
EquivalenceClass *ec, |
| 1723 |
Relids join_relids, |
| 1724 |
Relids outer_relids, |
| 1725 |
Relids inner_relids) |
| 1726 |
{ |
| 1727 |
List *result = NIL; |
| 1728 |
List *new_members = NIL; |
| 1729 |
List *outer_members = NIL; |
| 1730 |
List *inner_members = NIL; |
| 1731 |
EquivalenceMemberIterator it; |
| 1732 |
EquivalenceMember *cur_em; |
| 1733 |
|
| 1734 |
/* |
| 1735 |
* First, scan the EC to identify member values that are computable at the |
| 1736 |
* outer rel, at the inner rel, or at this relation but not in either |
| 1737 |
* input rel. The outer-rel members should already be enforced equal, |
| 1738 |
* likewise for the inner-rel members. We'll need to create clauses to |
| 1739 |
* enforce that any newly computable members are all equal to each other |
| 1740 |
* as well as to at least one input member, plus enforce at least one |
| 1741 |
* outer-rel member equal to at least one inner-rel member. |
| 1742 |
*/ |
| 1743 |
setup_eclass_member_iterator(&it, ec, join_relids); |
| 1744 |
while ((cur_em = eclass_member_iterator_next(&it)) != NULL) |
| 1745 |
{ |
| 1746 |
/* |
| 1747 |
* We don't need to check explicitly for child EC members. This test |
| 1748 |
* against join_relids will cause them to be ignored except when |
| 1749 |
* considering a child inner rel, which is what we want. |
| 1750 |
*/ |
| 1751 |
if (!bms_is_subset(cur_em->em_relids, join_relids)) |
| 1752 |
continue; /* not computable yet, or wrong child */ |
| 1753 |
|
| 1754 |
if (bms_is_subset(cur_em->em_relids, outer_relids)) |
| 1755 |
outer_members = lappend(outer_members, cur_em); |
| 1756 |
else if (bms_is_subset(cur_em->em_relids, inner_relids)) |
| 1757 |
inner_members = lappend(inner_members, cur_em); |
| 1758 |
else |
| 1759 |
new_members = lappend(new_members, cur_em); |
| 1760 |
} |
| 1761 |
|
| 1762 |
/* |
| 1763 |
* First, select the joinclause if needed. We can equate any one outer |
| 1764 |
* member to any one inner member, but we have to find a datatype |
| 1765 |
* combination for which an opfamily member operator exists. If we have |
| 1766 |
* choices, we prefer simple Var members (possibly with RelabelType) since |
| 1767 |
* these are (a) cheapest to compute at runtime and (b) most likely to |
| 1768 |
* have useful statistics. Also, prefer operators that are also |
| 1769 |
* hashjoinable. |
| 1770 |
*/ |
| 1771 |
if (outer_members && inner_members) |
| 1772 |
{ |
| 1773 |
EquivalenceMember *best_outer_em = NULL; |
| 1774 |
EquivalenceMember *best_inner_em = NULL; |
| 1775 |
Oid best_eq_op = InvalidOid; |
| 1776 |
int best_score = -1; |
| 1777 |
RestrictInfo *rinfo; |
| 1778 |
ListCell *lc1; |
| 1779 |
|
| 1780 |
foreach(lc1, outer_members) |
| 1781 |
{ |
| 1782 |
EquivalenceMember *outer_em = (EquivalenceMember *) lfirst(lc1); |
| 1783 |
ListCell *lc2; |
| 1784 |
|
| 1785 |
foreach(lc2, inner_members) |
| 1786 |
{ |
| 1787 |
EquivalenceMember *inner_em = (EquivalenceMember *) lfirst(lc2); |
| 1788 |
Oid eq_op; |
| 1789 |
int score; |
| 1790 |
|
| 1791 |
eq_op = select_equality_operator(ec, |
| 1792 |
outer_em->em_datatype, |
| 1793 |
inner_em->em_datatype); |
| 1794 |
if (!OidIsValid(eq_op)) |
| 1795 |
continue; |
| 1796 |
score = 0; |
| 1797 |
if (IsA(outer_em->em_expr, Var) || |
| 1798 |
(IsA(outer_em->em_expr, RelabelType) && |
| 1799 |
IsA(((RelabelType *) outer_em->em_expr)->arg, Var))) |
| 1800 |
score++; |
| 1801 |
if (IsA(inner_em->em_expr, Var) || |
| 1802 |
(IsA(inner_em->em_expr, RelabelType) && |
| 1803 |
IsA(((RelabelType *) inner_em->em_expr)->arg, Var))) |
| 1804 |
score++; |
| 1805 |
if (op_hashjoinable(eq_op, |
| 1806 |
exprType((Node *) outer_em->em_expr))) |
| 1807 |
score++; |
| 1808 |
if (score > best_score) |
| 1809 |
{ |
| 1810 |
best_outer_em = outer_em; |
| 1811 |
best_inner_em = inner_em; |
| 1812 |
best_eq_op = eq_op; |
| 1813 |
best_score = score; |
| 1814 |
if (best_score == 3) |
| 1815 |
break; /* no need to look further */ |
| 1816 |
} |
| 1817 |
} |
| 1818 |
if (best_score == 3) |
| 1819 |
break; /* no need to look further */ |
| 1820 |
} |
| 1821 |
if (best_score < 0) |
| 1822 |
{ |
| 1823 |
/* failed... */ |
| 1824 |
ec->ec_broken = true; |
| 1825 |
return NIL; |
| 1826 |
} |
| 1827 |
|
| 1828 |
/* |
| 1829 |
* Create clause, setting parent_ec to mark it as redundant with other |
| 1830 |
* joinclauses |
| 1831 |
*/ |
| 1832 |
rinfo = create_join_clause(root, ec, best_eq_op, |
| 1833 |
best_outer_em, best_inner_em, |
| 1834 |
ec); |
| 1835 |
|
| 1836 |
result = lappend(result, rinfo); |
| 1837 |
} |
| 1838 |
|
| 1839 |
/* |
| 1840 |
* Now deal with building restrictions for any expressions that involve |
| 1841 |
* Vars from both sides of the join. We have to equate all of these to |
| 1842 |
* each other as well as to at least one old member (if any). |
| 1843 |
* |
| 1844 |
* XXX as in generate_base_implied_equalities_no_const, we could be a lot |
| 1845 |
* smarter here to avoid unnecessary failures in cross-type situations. |
| 1846 |
* For now, use the same left-to-right method used there. |
| 1847 |
*/ |
| 1848 |
if (new_members) |
| 1849 |
{ |
| 1850 |
List *old_members = list_concat(outer_members, inner_members); |
| 1851 |
EquivalenceMember *prev_em = NULL; |
| 1852 |
RestrictInfo *rinfo; |
| 1853 |
ListCell *lc1; |
| 1854 |
|
| 1855 |
/* For now, arbitrarily take the first old_member as the one to use */ |
| 1856 |
if (old_members) |
| 1857 |
new_members = lappend(new_members, linitial(old_members)); |
| 1858 |
|
| 1859 |
foreach(lc1, new_members) |
| 1860 |
{ |
| 1861 |
cur_em = (EquivalenceMember *) lfirst(lc1); |
| 1862 |
|
| 1863 |
if (prev_em != NULL) |
| 1864 |
{ |
| 1865 |
Oid eq_op; |
| 1866 |
|
| 1867 |
eq_op = select_equality_operator(ec, |
| 1868 |
prev_em->em_datatype, |
| 1869 |
cur_em->em_datatype); |
| 1870 |
if (!OidIsValid(eq_op)) |
| 1871 |
{ |
| 1872 |
/* failed... */ |
| 1873 |
ec->ec_broken = true; |
| 1874 |
return NIL; |
| 1875 |
} |
| 1876 |
/* do NOT set parent_ec, this qual is not redundant! */ |
| 1877 |
rinfo = create_join_clause(root, ec, eq_op, |
| 1878 |
prev_em, cur_em, |
| 1879 |
NULL); |
| 1880 |
|
| 1881 |
result = lappend(result, rinfo); |
| 1882 |
} |
| 1883 |
prev_em = cur_em; |
| 1884 |
} |
| 1885 |
} |
| 1886 |
|
| 1887 |
return result; |
| 1888 |
} |
| 1889 |
|
| 1890 |
/* |
| 1891 |
* generate_join_implied_equalities cleanup after failure |
| 1892 |
* |
| 1893 |
* Return any original RestrictInfos that are enforceable at this join. |
| 1894 |
* |
| 1895 |
* In the case of a child inner relation, we have to translate the |
| 1896 |
* original RestrictInfos from parent to child Vars. |
| 1897 |
*/ |
| 1898 |
static List * |
| 1899 |
generate_join_implied_equalities_broken(PlannerInfo *root, |
| 1900 |
EquivalenceClass *ec, |
| 1901 |
Relids nominal_join_relids, |
| 1902 |
Relids outer_relids, |
| 1903 |
Relids nominal_inner_relids, |
| 1904 |
RelOptInfo *inner_rel) |
| 1905 |
{ |
| 1906 |
List *result = NIL; |
| 1907 |
ListCell *lc; |
| 1908 |
|
| 1909 |
foreach(lc, ec->ec_sources) |
| 1910 |
{ |
| 1911 |
RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc); |
| 1912 |
Relids clause_relids = restrictinfo->required_relids; |
| 1913 |
|
| 1914 |
if (bms_is_subset(clause_relids, nominal_join_relids) && |
| 1915 |
!bms_is_subset(clause_relids, outer_relids) && |
| 1916 |
!bms_is_subset(clause_relids, nominal_inner_relids)) |
| 1917 |
result = lappend(result, restrictinfo); |
| 1918 |
} |
| 1919 |
|
| 1920 |
/* |
| 1921 |
* If we have to translate, just brute-force apply adjust_appendrel_attrs |
| 1922 |
* to all the RestrictInfos at once. This will result in returning |
| 1923 |
* RestrictInfos that are not included in EC's derived clauses, but there |
| 1924 |
* shouldn't be any duplication, and it's a sufficiently narrow corner |
| 1925 |
* case that we shouldn't sweat too much over it anyway. |
| 1926 |
* |
| 1927 |
* Since inner_rel might be an indirect descendant of the baserel |
| 1928 |
* mentioned in the ec_sources clauses, we have to be prepared to apply |
| 1929 |
* multiple levels of Var translation. |
| 1930 |
*/ |
| 1931 |
if (IS_OTHER_REL(inner_rel) && result != NIL) |
| 1932 |
result = (List *) adjust_appendrel_attrs_multilevel(root, |
| 1933 |
(Node *) result, |
| 1934 |
inner_rel, |
| 1935 |
inner_rel->top_parent); |
| 1936 |
|
| 1937 |
return result; |
| 1938 |
} |
| 1939 |
|
| 1940 |
|
| 1941 |
/* |
| 1942 |
* select_equality_operator |
| 1943 |
* Select a suitable equality operator for comparing two EC members |
| 1944 |
* |
| 1945 |
* Returns InvalidOid if no operator can be found for this datatype combination |
| 1946 |
*/ |
| 1947 |
static Oid |
| 1948 |
select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype) |
| 1949 |
{ |
| 1950 |
ListCell *lc; |
| 1951 |
|
| 1952 |
foreach(lc, ec->ec_opfamilies) |
| 1953 |
{ |
| 1954 |
Oid opfamily = lfirst_oid(lc); |
| 1955 |
Oid opno; |
| 1956 |
|
| 1957 |
opno = get_opfamily_member_for_cmptype(opfamily, lefttype, righttype, COMPARE_EQ); |
| 1958 |
if (!OidIsValid(opno)) |
| 1959 |
continue; |
| 1960 |
/* If no barrier quals in query, don't worry about leaky operators */ |
| 1961 |
if (ec->ec_max_security == 0) |
| 1962 |
return opno; |
| 1963 |
/* Otherwise, insist that selected operators be leakproof */ |
| 1964 |
if (get_func_leakproof(get_opcode(opno))) |
| 1965 |
return opno; |
| 1966 |
} |
| 1967 |
return InvalidOid; |
| 1968 |
} |
| 1969 |
|
| 1970 |
|
| 1971 |
/* |
| 1972 |
* create_join_clause |
| 1973 |
* Find or make a RestrictInfo comparing the two given EC members |
| 1974 |
* with the given operator (or, possibly, its commutator, because |
| 1975 |
* the ordering of the operands in the result is not guaranteed). |
| 1976 |
* |
| 1977 |
* parent_ec is either equal to ec (if the clause is a potentially-redundant |
| 1978 |
* join clause) or NULL (if not). We have to treat this as part of the |
| 1979 |
* match requirements --- it's possible that a clause comparing the same two |
| 1980 |
* EMs is a join clause in one join path and a restriction clause in another. |
| 1981 |
*/ |
| 1982 |
static RestrictInfo * |
| 1983 |
create_join_clause(PlannerInfo *root, |
| 1984 |
EquivalenceClass *ec, Oid opno, |
| 1985 |
EquivalenceMember *leftem, |
| 1986 |
EquivalenceMember *rightem, |
| 1987 |
EquivalenceClass *parent_ec) |
| 1988 |
{ |
| 1989 |
RestrictInfo *rinfo; |
| 1990 |
RestrictInfo *parent_rinfo = NULL; |
| 1991 |
MemoryContext oldcontext; |
| 1992 |
|
| 1993 |
rinfo = ec_search_clause_for_ems(root, ec, leftem, rightem, parent_ec); |
| 1994 |
if (rinfo) |
| 1995 |
return rinfo; |
| 1996 |
|
| 1997 |
/* |
| 1998 |
* Not there, so build it, in planner context so we can re-use it. (Not |
| 1999 |
* important in normal planning, but definitely so in GEQO.) |
| 2000 |
*/ |
| 2001 |
oldcontext = MemoryContextSwitchTo(root->planner_cxt); |
| 2002 |
|
| 2003 |
/* |
| 2004 |
* If either EM is a child, recursively create the corresponding |
| 2005 |
* parent-to-parent clause, so that we can duplicate its rinfo_serial. |
| 2006 |
*/ |
| 2007 |
if (leftem->em_is_child || rightem->em_is_child) |
| 2008 |
{ |
| 2009 |
EquivalenceMember *leftp = leftem->em_parent ? leftem->em_parent : leftem; |
| 2010 |
EquivalenceMember *rightp = rightem->em_parent ? rightem->em_parent : rightem; |
| 2011 |
|
| 2012 |
parent_rinfo = create_join_clause(root, ec, opno, |
| 2013 |
leftp, rightp, |
| 2014 |
parent_ec); |
| 2015 |
} |
| 2016 |
|
| 2017 |
rinfo = build_implied_join_equality(root, |
| 2018 |
opno, |
| 2019 |
ec->ec_collation, |
| 2020 |
leftem->em_expr, |
| 2021 |
rightem->em_expr, |
| 2022 |
bms_union(leftem->em_relids, |
| 2023 |
rightem->em_relids), |
| 2024 |
ec->ec_min_security); |
| 2025 |
|
| 2026 |
/* |
| 2027 |
* If either EM is a child, force the clause's clause_relids to include |
| 2028 |
* the relid(s) of the child rel. In normal cases it would already, but |
| 2029 |
* not if we are considering appendrel child relations with pseudoconstant |
| 2030 |
* translated variables (i.e., UNION ALL sub-selects with constant output |
| 2031 |
* items). We must do this so that join_clause_is_movable_into() will |
| 2032 |
* think that the clause should be evaluated at the correct place. |
| 2033 |
*/ |
| 2034 |
if (leftem->em_is_child) |
| 2035 |
rinfo->clause_relids = bms_add_members(rinfo->clause_relids, |
| 2036 |
leftem->em_relids); |
| 2037 |
if (rightem->em_is_child) |
| 2038 |
rinfo->clause_relids = bms_add_members(rinfo->clause_relids, |
| 2039 |
rightem->em_relids); |
| 2040 |
|
| 2041 |
/* If it's a child clause, copy the parent's rinfo_serial */ |
| 2042 |
if (parent_rinfo) |
| 2043 |
rinfo->rinfo_serial = parent_rinfo->rinfo_serial; |
| 2044 |
|
| 2045 |
/* Mark the clause as redundant, or not */ |
| 2046 |
rinfo->parent_ec = parent_ec; |
| 2047 |
|
| 2048 |
/* |
| 2049 |
* We know the correct values for left_ec/right_ec, ie this particular EC, |
| 2050 |
* so we can just set them directly instead of forcing another lookup. |
| 2051 |
*/ |
| 2052 |
rinfo->left_ec = ec; |
| 2053 |
rinfo->right_ec = ec; |
| 2054 |
|
| 2055 |
/* Mark it as usable with these EMs */ |
| 2056 |
rinfo->left_em = leftem; |
| 2057 |
rinfo->right_em = rightem; |
| 2058 |
/* and save it for possible re-use */ |
| 2059 |
ec_add_derived_clause(ec, rinfo); |
| 2060 |
|
| 2061 |
MemoryContextSwitchTo(oldcontext); |
| 2062 |
|
| 2063 |
return rinfo; |
| 2064 |
} |
| 2065 |
|
| 2066 |
|
| 2067 |
/* |
| 2068 |
* reconsider_outer_join_clauses |
| 2069 |
* Re-examine any outer-join clauses that were set aside by |
| 2070 |
* distribute_qual_to_rels(), and see if we can derive any |
| 2071 |
* EquivalenceClasses from them. Then, if they were not made |
| 2072 |
* redundant, push them out into the regular join-clause lists. |
| 2073 |
* |
| 2074 |
* When we have mergejoinable clauses A = B that are outer-join clauses, |
| 2075 |
* we can't blindly combine them with other clauses A = C to deduce B = C, |
| 2076 |
* since in fact the "equality" A = B won't necessarily hold above the |
| 2077 |
* outer join (one of the variables might be NULL instead). Nonetheless |
| 2078 |
* there are cases where we can add qual clauses using transitivity. |
| 2079 |
* |
| 2080 |
* One case that we look for here is an outer-join clause OUTERVAR = INNERVAR |
| 2081 |
* for which there is also an equivalence clause OUTERVAR = CONSTANT. |
| 2082 |
* It is safe and useful to push a clause INNERVAR = CONSTANT into the |
| 2083 |
* evaluation of the inner (nullable) relation, because any inner rows not |
| 2084 |
* meeting this condition will not contribute to the outer-join result anyway. |
| 2085 |
* (Any outer rows they could join to will be eliminated by the pushed-down |
| 2086 |
* equivalence clause.) |
| 2087 |
* |
| 2088 |
* Note that the above rule does not work for full outer joins; nor is it |
| 2089 |
* very interesting to consider cases where the generated equivalence clause |
| 2090 |
* would involve relations outside the outer join, since such clauses couldn't |
| 2091 |
* be pushed into the inner side's scan anyway. So the restriction to |
| 2092 |
* outervar = pseudoconstant is not really giving up anything. |
| 2093 |
* |
| 2094 |
* For full-join cases, we can only do something useful if it's a FULL JOIN |
| 2095 |
* USING and a merged column has an equivalence MERGEDVAR = CONSTANT. |
| 2096 |
* By the time it gets here, the merged column will look like |
| 2097 |
* COALESCE(LEFTVAR, RIGHTVAR) |
| 2098 |
* and we will have a full-join clause LEFTVAR = RIGHTVAR that we can match |
| 2099 |
* the COALESCE expression to. In this situation we can push LEFTVAR = CONSTANT |
| 2100 |
* and RIGHTVAR = CONSTANT into the input relations, since any rows not |
| 2101 |
* meeting these conditions cannot contribute to the join result. |
| 2102 |
* |
| 2103 |
* Again, there isn't any traction to be gained by trying to deal with |
| 2104 |
* clauses comparing a mergedvar to a non-pseudoconstant. So we can make |
| 2105 |
* use of the EquivalenceClasses to search for matching variables that were |
| 2106 |
* equivalenced to constants. The interesting outer-join clauses were |
| 2107 |
* accumulated for us by distribute_qual_to_rels. |
| 2108 |
* |
| 2109 |
* When we find one of these cases, we implement the changes we want by |
| 2110 |
* generating a new equivalence clause INNERVAR = CONSTANT (or LEFTVAR, etc) |
| 2111 |
* and pushing it into the EquivalenceClass structures. This is because we |
| 2112 |
* may already know that INNERVAR is equivalenced to some other var(s), and |
| 2113 |
* we'd like the constant to propagate to them too. Note that it would be |
| 2114 |
* unsafe to merge any existing EC for INNERVAR with the OUTERVAR's EC --- |
| 2115 |
* that could result in propagating constant restrictions from |
| 2116 |
* INNERVAR to OUTERVAR, which would be very wrong. |
| 2117 |
* |
| 2118 |
* It's possible that the INNERVAR is also an OUTERVAR for some other |
| 2119 |
* outer-join clause, in which case the process can be repeated. So we repeat |
| 2120 |
* looping over the lists of clauses until no further deductions can be made. |
| 2121 |
* Whenever we do make a deduction, we remove the generating clause from the |
| 2122 |
* lists, since we don't want to make the same deduction twice. |
| 2123 |
* |
| 2124 |
* If we don't find any match for a set-aside outer join clause, we must |
| 2125 |
* throw it back into the regular joinclause processing by passing it to |
| 2126 |
* distribute_restrictinfo_to_rels(). If we do generate a derived clause, |
| 2127 |
* however, the outer-join clause is redundant. We must still put some |
| 2128 |
* clause into the regular processing, because otherwise the join will be |
| 2129 |
* seen as a clauseless join and avoided during join order searching. |
| 2130 |
* We handle this by generating a constant-TRUE clause that is marked with |
| 2131 |
* the same required_relids etc as the removed outer-join clause, thus |
| 2132 |
* making it a join clause between the correct relations. |
| 2133 |
*/ |
| 2134 |
void |
| 2135 |
reconsider_outer_join_clauses(PlannerInfo *root) |
| 2136 |
{ |
| 2137 |
bool found; |
| 2138 |
ListCell *cell; |
| 2139 |
|
| 2140 |
/* Outer loop repeats until we find no more deductions */ |
| 2141 |
do |
| 2142 |
{ |
| 2143 |
found = false; |
| 2144 |
|
| 2145 |
/* Process the LEFT JOIN clauses */ |
| 2146 |
foreach(cell, root->left_join_clauses) |
| 2147 |
{ |
| 2148 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2149 |
|
| 2150 |
if (reconsider_outer_join_clause(root, ojcinfo, true)) |
| 2151 |
{ |
| 2152 |
RestrictInfo *rinfo = ojcinfo->rinfo; |
| 2153 |
|
| 2154 |
found = true; |
| 2155 |
/* remove it from the list */ |
| 2156 |
root->left_join_clauses = |
| 2157 |
foreach_delete_current(root->left_join_clauses, cell); |
| 2158 |
/* throw back a dummy replacement clause (see notes above) */ |
| 2159 |
rinfo = make_restrictinfo(root, |
| 2160 |
(Expr *) makeBoolConst(true, false), |
| 2161 |
rinfo->is_pushed_down, |
| 2162 |
rinfo->has_clone, |
| 2163 |
rinfo->is_clone, |
| 2164 |
false, /* pseudoconstant */ |
| 2165 |
0, /* security_level */ |
| 2166 |
rinfo->required_relids, |
| 2167 |
rinfo->incompatible_relids, |
| 2168 |
rinfo->outer_relids); |
| 2169 |
distribute_restrictinfo_to_rels(root, rinfo); |
| 2170 |
} |
| 2171 |
} |
| 2172 |
|
| 2173 |
/* Process the RIGHT JOIN clauses */ |
| 2174 |
foreach(cell, root->right_join_clauses) |
| 2175 |
{ |
| 2176 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2177 |
|
| 2178 |
if (reconsider_outer_join_clause(root, ojcinfo, false)) |
| 2179 |
{ |
| 2180 |
RestrictInfo *rinfo = ojcinfo->rinfo; |
| 2181 |
|
| 2182 |
found = true; |
| 2183 |
/* remove it from the list */ |
| 2184 |
root->right_join_clauses = |
| 2185 |
foreach_delete_current(root->right_join_clauses, cell); |
| 2186 |
/* throw back a dummy replacement clause (see notes above) */ |
| 2187 |
rinfo = make_restrictinfo(root, |
| 2188 |
(Expr *) makeBoolConst(true, false), |
| 2189 |
rinfo->is_pushed_down, |
| 2190 |
rinfo->has_clone, |
| 2191 |
rinfo->is_clone, |
| 2192 |
false, /* pseudoconstant */ |
| 2193 |
0, /* security_level */ |
| 2194 |
rinfo->required_relids, |
| 2195 |
rinfo->incompatible_relids, |
| 2196 |
rinfo->outer_relids); |
| 2197 |
distribute_restrictinfo_to_rels(root, rinfo); |
| 2198 |
} |
| 2199 |
} |
| 2200 |
|
| 2201 |
/* Process the FULL JOIN clauses */ |
| 2202 |
foreach(cell, root->full_join_clauses) |
| 2203 |
{ |
| 2204 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2205 |
|
| 2206 |
if (reconsider_full_join_clause(root, ojcinfo)) |
| 2207 |
{ |
| 2208 |
RestrictInfo *rinfo = ojcinfo->rinfo; |
| 2209 |
|
| 2210 |
found = true; |
| 2211 |
/* remove it from the list */ |
| 2212 |
root->full_join_clauses = |
| 2213 |
foreach_delete_current(root->full_join_clauses, cell); |
| 2214 |
/* throw back a dummy replacement clause (see notes above) */ |
| 2215 |
rinfo = make_restrictinfo(root, |
| 2216 |
(Expr *) makeBoolConst(true, false), |
| 2217 |
rinfo->is_pushed_down, |
| 2218 |
rinfo->has_clone, |
| 2219 |
rinfo->is_clone, |
| 2220 |
false, /* pseudoconstant */ |
| 2221 |
0, /* security_level */ |
| 2222 |
rinfo->required_relids, |
| 2223 |
rinfo->incompatible_relids, |
| 2224 |
rinfo->outer_relids); |
| 2225 |
distribute_restrictinfo_to_rels(root, rinfo); |
| 2226 |
} |
| 2227 |
} |
| 2228 |
} while (found); |
| 2229 |
|
| 2230 |
/* Now, any remaining clauses have to be thrown back */ |
| 2231 |
foreach(cell, root->left_join_clauses) |
| 2232 |
{ |
| 2233 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2234 |
|
| 2235 |
distribute_restrictinfo_to_rels(root, ojcinfo->rinfo); |
| 2236 |
} |
| 2237 |
foreach(cell, root->right_join_clauses) |
| 2238 |
{ |
| 2239 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2240 |
|
| 2241 |
distribute_restrictinfo_to_rels(root, ojcinfo->rinfo); |
| 2242 |
} |
| 2243 |
foreach(cell, root->full_join_clauses) |
| 2244 |
{ |
| 2245 |
OuterJoinClauseInfo *ojcinfo = (OuterJoinClauseInfo *) lfirst(cell); |
| 2246 |
|
| 2247 |
distribute_restrictinfo_to_rels(root, ojcinfo->rinfo); |
| 2248 |
} |
| 2249 |
} |
| 2250 |
|
| 2251 |
/* |
| 2252 |
* reconsider_outer_join_clauses for a single LEFT/RIGHT JOIN clause |
| 2253 |
* |
| 2254 |
* Returns true if we were able to propagate a constant through the clause. |
| 2255 |
*/ |
| 2256 |
static bool |
| 2257 |
reconsider_outer_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo, |
| 2258 |
bool outer_on_left) |
| 2259 |
{ |
| 2260 |
RestrictInfo *rinfo = ojcinfo->rinfo; |
| 2261 |
SpecialJoinInfo *sjinfo = ojcinfo->sjinfo; |
| 2262 |
Expr *outervar, |
| 2263 |
*innervar; |
| 2264 |
Oid opno, |
| 2265 |
collation, |
| 2266 |
left_type, |
| 2267 |
right_type, |
| 2268 |
inner_datatype; |
| 2269 |
Relids inner_relids; |
| 2270 |
ListCell *lc1; |
| 2271 |
|
| 2272 |
Assert(is_opclause(rinfo->clause)); |
| 2273 |
opno = ((OpExpr *) rinfo->clause)->opno; |
| 2274 |
collation = ((OpExpr *) rinfo->clause)->inputcollid; |
| 2275 |
|
| 2276 |
/* Extract needed info from the clause */ |
| 2277 |
op_input_types(opno, &left_type, &right_type); |
| 2278 |
if (outer_on_left) |
| 2279 |
{ |
| 2280 |
outervar = (Expr *) get_leftop(rinfo->clause); |
| 2281 |
innervar = (Expr *) get_rightop(rinfo->clause); |
| 2282 |
inner_datatype = right_type; |
| 2283 |
inner_relids = rinfo->right_relids; |
| 2284 |
} |
| 2285 |
else |
| 2286 |
{ |
| 2287 |
outervar = (Expr *) get_rightop(rinfo->clause); |
| 2288 |
innervar = (Expr *) get_leftop(rinfo->clause); |
| 2289 |
inner_datatype = left_type; |
| 2290 |
inner_relids = rinfo->left_relids; |
| 2291 |
} |
| 2292 |
|
| 2293 |
/* Scan EquivalenceClasses for a match to outervar */ |
| 2294 |
foreach(lc1, root->eq_classes) |
| 2295 |
{ |
| 2296 |
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1); |
| 2297 |
bool match; |
| 2298 |
ListCell *lc2; |
| 2299 |
|
| 2300 |
/* We don't expect any children yet */ |
| 2301 |
Assert(cur_ec->ec_childmembers == NULL); |
| 2302 |
|
| 2303 |
/* Ignore EC unless it contains pseudoconstants */ |
| 2304 |
if (!cur_ec->ec_has_const) |
| 2305 |
continue; |
| 2306 |
/* Never match to a volatile EC */ |
| 2307 |
if (cur_ec->ec_has_volatile) |
| 2308 |
continue; |
| 2309 |
/* It has to match the outer-join clause as to semantics, too */ |
| 2310 |
if (collation != cur_ec->ec_collation) |
| 2311 |
continue; |
| 2312 |
if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies)) |
| 2313 |
continue; |
| 2314 |
/* Does it contain a match to outervar? */ |
| 2315 |
match = false; |
| 2316 |
foreach(lc2, cur_ec->ec_members) |
| 2317 |
{ |
| 2318 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2); |
| 2319 |
|
| 2320 |
/* Child members should not exist in ec_members */ |
| 2321 |
Assert(!cur_em->em_is_child); |
| 2322 |
if (equal(outervar, cur_em->em_expr)) |
| 2323 |
{ |
| 2324 |
match = true; |
| 2325 |
break; |
| 2326 |
} |
| 2327 |
} |
| 2328 |
if (!match) |
| 2329 |
continue; /* no match, so ignore this EC */ |
| 2330 |
|
| 2331 |
/* |
| 2332 |
* Yes it does! Try to generate a clause INNERVAR = CONSTANT for each |
| 2333 |
* CONSTANT in the EC. Note that we must succeed with at least one |
| 2334 |
* constant before we can decide to throw away the outer-join clause. |
| 2335 |
*/ |
| 2336 |
match = false; |
| 2337 |
foreach(lc2, cur_ec->ec_members) |
| 2338 |
{ |
| 2339 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2); |
| 2340 |
Oid eq_op; |
| 2341 |
RestrictInfo *newrinfo; |
| 2342 |
JoinDomain *jdomain; |
| 2343 |
|
| 2344 |
if (!cur_em->em_is_const) |
| 2345 |
continue; /* ignore non-const members */ |
| 2346 |
eq_op = select_equality_operator(cur_ec, |
| 2347 |
inner_datatype, |
| 2348 |
cur_em->em_datatype); |
| 2349 |
if (!OidIsValid(eq_op)) |
| 2350 |
continue; /* can't generate equality */ |
| 2351 |
newrinfo = build_implied_join_equality(root, |
| 2352 |
eq_op, |
| 2353 |
cur_ec->ec_collation, |
| 2354 |
innervar, |
| 2355 |
cur_em->em_expr, |
| 2356 |
bms_copy(inner_relids), |
| 2357 |
cur_ec->ec_min_security); |
| 2358 |
/* This equality holds within the OJ's child JoinDomain */ |
| 2359 |
jdomain = find_join_domain(root, sjinfo->syn_righthand); |
| 2360 |
if (process_equivalence(root, &newrinfo, jdomain)) |
| 2361 |
match = true; |
| 2362 |
} |
| 2363 |
|
| 2364 |
/* |
| 2365 |
* If we were able to equate INNERVAR to any constant, report success. |
| 2366 |
* Otherwise, fall out of the search loop, since we know the OUTERVAR |
| 2367 |
* appears in at most one EC. |
| 2368 |
*/ |
| 2369 |
if (match) |
| 2370 |
return true; |
| 2371 |
else |
| 2372 |
break; |
| 2373 |
} |
| 2374 |
|
| 2375 |
return false; /* failed to make any deduction */ |
| 2376 |
} |
| 2377 |
|
| 2378 |
/* |
| 2379 |
* reconsider_outer_join_clauses for a single FULL JOIN clause |
| 2380 |
* |
| 2381 |
* Returns true if we were able to propagate a constant through the clause. |
| 2382 |
*/ |
| 2383 |
static bool |
| 2384 |
reconsider_full_join_clause(PlannerInfo *root, OuterJoinClauseInfo *ojcinfo) |
| 2385 |
{ |
| 2386 |
RestrictInfo *rinfo = ojcinfo->rinfo; |
| 2387 |
SpecialJoinInfo *sjinfo = ojcinfo->sjinfo; |
| 2388 |
Relids fjrelids = bms_make_singleton(sjinfo->ojrelid); |
| 2389 |
Expr *leftvar; |
| 2390 |
Expr *rightvar; |
| 2391 |
Oid opno, |
| 2392 |
collation, |
| 2393 |
left_type, |
| 2394 |
right_type; |
| 2395 |
Relids left_relids, |
| 2396 |
right_relids; |
| 2397 |
ListCell *lc1; |
| 2398 |
|
| 2399 |
/* Extract needed info from the clause */ |
| 2400 |
Assert(is_opclause(rinfo->clause)); |
| 2401 |
opno = ((OpExpr *) rinfo->clause)->opno; |
| 2402 |
collation = ((OpExpr *) rinfo->clause)->inputcollid; |
| 2403 |
op_input_types(opno, &left_type, &right_type); |
| 2404 |
leftvar = (Expr *) get_leftop(rinfo->clause); |
| 2405 |
rightvar = (Expr *) get_rightop(rinfo->clause); |
| 2406 |
left_relids = rinfo->left_relids; |
| 2407 |
right_relids = rinfo->right_relids; |
| 2408 |
|
| 2409 |
foreach(lc1, root->eq_classes) |
| 2410 |
{ |
| 2411 |
EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1); |
| 2412 |
EquivalenceMember *coal_em = NULL; |
| 2413 |
bool match; |
| 2414 |
bool matchleft; |
| 2415 |
bool matchright; |
| 2416 |
ListCell *lc2; |
| 2417 |
int coal_idx = -1; |
| 2418 |
|
| 2419 |
/* We don't expect any children yet */ |
| 2420 |
Assert(cur_ec->ec_childmembers == NULL); |
| 2421 |
|
| 2422 |
/* Ignore EC unless it contains pseudoconstants */ |
| 2423 |
if (!cur_ec->ec_has_const) |
| 2424 |
continue; |
| 2425 |
/* Never match to a volatile EC */ |
| 2426 |
if (cur_ec->ec_has_volatile) |
| 2427 |
continue; |
| 2428 |
/* It has to match the outer-join clause as to semantics, too */ |
| 2429 |
if (collation != cur_ec->ec_collation) |
| 2430 |
continue; |
| 2431 |
if (!equal(rinfo->mergeopfamilies, cur_ec->ec_opfamilies)) |
| 2432 |
continue; |
| 2433 |
|
| 2434 |
/* |
| 2435 |
* Does it contain a COALESCE(leftvar, rightvar) construct? |
| 2436 |
* |
| 2437 |
* We can assume the COALESCE() inputs are in the same order as the |
| 2438 |
* join clause, since both were automatically generated in the cases |
| 2439 |
* we care about. |
| 2440 |
* |
| 2441 |
* XXX currently this may fail to match in cross-type cases because |
| 2442 |
* the COALESCE will contain typecast operations while the join clause |
| 2443 |
* may not (if there is a cross-type mergejoin operator available for |
| 2444 |
* the two column types). Is it OK to strip implicit coercions from |
| 2445 |
* the COALESCE arguments? |
| 2446 |
*/ |
| 2447 |
match = false; |
| 2448 |
foreach(lc2, cur_ec->ec_members) |
| 2449 |
{ |
| 2450 |
coal_em = (EquivalenceMember *) lfirst(lc2); |
| 2451 |
|
| 2452 |
/* Child members should not exist in ec_members */ |
| 2453 |
Assert(!coal_em->em_is_child); |
| 2454 |
if (IsA(coal_em->em_expr, CoalesceExpr)) |
| 2455 |
{ |
| 2456 |
CoalesceExpr *cexpr = (CoalesceExpr *) coal_em->em_expr; |
| 2457 |
Node *cfirst; |
| 2458 |
Node *csecond; |
| 2459 |
|
| 2460 |
if (list_length(cexpr->args) != 2) |
| 2461 |
continue; |
| 2462 |
cfirst = (Node *) linitial(cexpr->args); |
| 2463 |
csecond = (Node *) lsecond(cexpr->args); |
| 2464 |
|
| 2465 |
/* |
| 2466 |
* The COALESCE arguments will be marked as possibly nulled by |
| 2467 |
* the full join, while we wish to generate clauses that apply |
| 2468 |
* to the join's inputs. So we must strip the join from the |
| 2469 |
* nullingrels fields of cfirst/csecond before comparing them |
| 2470 |
* to leftvar/rightvar. (Perhaps with a less hokey |
| 2471 |
* representation for FULL JOIN USING output columns, this |
| 2472 |
* wouldn't be needed?) |
| 2473 |
*/ |
| 2474 |
cfirst = remove_nulling_relids(cfirst, fjrelids, NULL); |
| 2475 |
csecond = remove_nulling_relids(csecond, fjrelids, NULL); |
| 2476 |
|
| 2477 |
if (equal(leftvar, cfirst) && equal(rightvar, csecond)) |
| 2478 |
{ |
| 2479 |
coal_idx = foreach_current_index(lc2); |
| 2480 |
match = true; |
| 2481 |
break; |
| 2482 |
} |
| 2483 |
} |
| 2484 |
} |
| 2485 |
if (!match) |
| 2486 |
continue; /* no match, so ignore this EC */ |
| 2487 |
|
| 2488 |
/* |
| 2489 |
* Yes it does! Try to generate clauses LEFTVAR = CONSTANT and |
| 2490 |
* RIGHTVAR = CONSTANT for each CONSTANT in the EC. Note that we must |
| 2491 |
* succeed with at least one constant for each var before we can |
| 2492 |
* decide to throw away the outer-join clause. |
| 2493 |
*/ |
| 2494 |
matchleft = matchright = false; |
| 2495 |
foreach(lc2, cur_ec->ec_members) |
| 2496 |
{ |
| 2497 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2); |
| 2498 |
Oid eq_op; |
| 2499 |
RestrictInfo *newrinfo; |
| 2500 |
JoinDomain *jdomain; |
| 2501 |
|
| 2502 |
if (!cur_em->em_is_const) |
| 2503 |
continue; /* ignore non-const members */ |
| 2504 |
eq_op = select_equality_operator(cur_ec, |
| 2505 |
left_type, |
| 2506 |
cur_em->em_datatype); |
| 2507 |
if (OidIsValid(eq_op)) |
| 2508 |
{ |
| 2509 |
newrinfo = build_implied_join_equality(root, |
| 2510 |
eq_op, |
| 2511 |
cur_ec->ec_collation, |
| 2512 |
leftvar, |
| 2513 |
cur_em->em_expr, |
| 2514 |
bms_copy(left_relids), |
| 2515 |
cur_ec->ec_min_security); |
| 2516 |
/* This equality holds within the lefthand child JoinDomain */ |
| 2517 |
jdomain = find_join_domain(root, sjinfo->syn_lefthand); |
| 2518 |
if (process_equivalence(root, &newrinfo, jdomain)) |
| 2519 |
matchleft = true; |
| 2520 |
} |
| 2521 |
eq_op = select_equality_operator(cur_ec, |
| 2522 |
right_type, |
| 2523 |
cur_em->em_datatype); |
| 2524 |
if (OidIsValid(eq_op)) |
| 2525 |
{ |
| 2526 |
newrinfo = build_implied_join_equality(root, |
| 2527 |
eq_op, |
| 2528 |
cur_ec->ec_collation, |
| 2529 |
rightvar, |
| 2530 |
cur_em->em_expr, |
| 2531 |
bms_copy(right_relids), |
| 2532 |
cur_ec->ec_min_security); |
| 2533 |
/* This equality holds within the righthand child JoinDomain */ |
| 2534 |
jdomain = find_join_domain(root, sjinfo->syn_righthand); |
| 2535 |
if (process_equivalence(root, &newrinfo, jdomain)) |
| 2536 |
matchright = true; |
| 2537 |
} |
| 2538 |
} |
| 2539 |
|
| 2540 |
/* |
| 2541 |
* If we were able to equate both vars to constants, we're done, and |
| 2542 |
* we can throw away the full-join clause as redundant. Moreover, we |
| 2543 |
* can remove the COALESCE entry from the EC, since the added |
| 2544 |
* restrictions ensure it will always have the expected value. (We |
| 2545 |
* don't bother trying to update ec_relids or ec_sources.) |
| 2546 |
*/ |
| 2547 |
if (matchleft && matchright) |
| 2548 |
{ |
| 2549 |
cur_ec->ec_members = list_delete_nth_cell(cur_ec->ec_members, coal_idx); |
| 2550 |
return true; |
| 2551 |
} |
| 2552 |
|
| 2553 |
/* |
| 2554 |
* Otherwise, fall out of the search loop, since we know the COALESCE |
| 2555 |
* appears in at most one EC (XXX might stop being true if we allow |
| 2556 |
* stripping of coercions above?) |
| 2557 |
*/ |
| 2558 |
break; |
| 2559 |
} |
| 2560 |
|
| 2561 |
return false; /* failed to make any deduction */ |
| 2562 |
} |
| 2563 |
|
| 2564 |
/* |
| 2565 |
* rebuild_eclass_attr_needed |
| 2566 |
* Put back attr_needed bits for Vars/PHVs needed for join eclasses. |
| 2567 |
* |
| 2568 |
* This is used to rebuild attr_needed/ph_needed sets after removal of a |
| 2569 |
* useless outer join. It should match what |
| 2570 |
* generate_base_implied_equalities_no_const did, except that we call |
| 2571 |
* add_vars_to_attr_needed not add_vars_to_targetlist. |
| 2572 |
*/ |
| 2573 |
void |
| 2574 |
rebuild_eclass_attr_needed(PlannerInfo *root) |
| 2575 |
{ |
| 2576 |
ListCell *lc; |
| 2577 |
|
| 2578 |
foreach(lc, root->eq_classes) |
| 2579 |
{ |
| 2580 |
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc); |
| 2581 |
|
| 2582 |
/* |
| 2583 |
* We don't expect any EC child members to exist at this point. Ensure |
| 2584 |
* that's the case, otherwise, we might be getting asked to do |
| 2585 |
* something this function hasn't been coded for. |
| 2586 |
*/ |
| 2587 |
Assert(ec->ec_childmembers == NULL); |
| 2588 |
|
| 2589 |
/* Need do anything only for a multi-member, no-const EC. */ |
| 2590 |
if (list_length(ec->ec_members) > 1 && !ec->ec_has_const) |
| 2591 |
{ |
| 2592 |
ListCell *lc2; |
| 2593 |
|
| 2594 |
foreach(lc2, ec->ec_members) |
| 2595 |
{ |
| 2596 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc2); |
| 2597 |
List *vars = pull_var_clause((Node *) cur_em->em_expr, |
| 2598 |
PVC_RECURSE_AGGREGATES | |
| 2599 |
PVC_RECURSE_WINDOWFUNCS | |
| 2600 |
PVC_INCLUDE_PLACEHOLDERS); |
| 2601 |
|
| 2602 |
add_vars_to_attr_needed(root, vars, ec->ec_relids); |
| 2603 |
list_free(vars); |
| 2604 |
} |
| 2605 |
} |
| 2606 |
} |
| 2607 |
} |
| 2608 |
|
| 2609 |
/* |
| 2610 |
* find_join_domain |
| 2611 |
* Find the highest JoinDomain enclosed within the given relid set. |
| 2612 |
* |
| 2613 |
* (We could avoid this search at the cost of complicating APIs elsewhere, |
| 2614 |
* which doesn't seem worth it.) |
| 2615 |
*/ |
| 2616 |
static JoinDomain * |
| 2617 |
find_join_domain(PlannerInfo *root, Relids relids) |
| 2618 |
{ |
| 2619 |
ListCell *lc; |
| 2620 |
|
| 2621 |
foreach(lc, root->join_domains) |
| 2622 |
{ |
| 2623 |
JoinDomain *jdomain = (JoinDomain *) lfirst(lc); |
| 2624 |
|
| 2625 |
if (bms_is_subset(jdomain->jd_relids, relids)) |
| 2626 |
return jdomain; |
| 2627 |
} |
| 2628 |
elog(ERROR, "failed to find appropriate JoinDomain"); |
| 2629 |
return NULL; /* keep compiler quiet */ |
| 2630 |
} |
| 2631 |
|
| 2632 |
|
| 2633 |
/* |
| 2634 |
* exprs_known_equal |
| 2635 |
* Detect whether two expressions are known equal due to equivalence |
| 2636 |
* relationships. |
| 2637 |
* |
| 2638 |
* If opfamily is given, the expressions must be known equal per the semantics |
| 2639 |
* of that opfamily (note it has to be a btree opfamily, since those are the |
| 2640 |
* only opfamilies equivclass.c deals with). If opfamily is InvalidOid, we'll |
| 2641 |
* return true if they're equal according to any opfamily, which is fuzzy but |
| 2642 |
* OK for estimation purposes. |
| 2643 |
* |
| 2644 |
* Note: does not bother to check for "equal(item1, item2)"; caller must |
| 2645 |
* check that case if it's possible to pass identical items. |
| 2646 |
*/ |
| 2647 |
bool |
| 2648 |
exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2, Oid opfamily) |
| 2649 |
{ |
| 2650 |
ListCell *lc1; |
| 2651 |
|
| 2652 |
foreach(lc1, root->eq_classes) |
| 2653 |
{ |
| 2654 |
EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1); |
| 2655 |
bool item1member = false; |
| 2656 |
bool item2member = false; |
| 2657 |
ListCell *lc2; |
| 2658 |
|
| 2659 |
/* Never match to a volatile EC */ |
| 2660 |
if (ec->ec_has_volatile) |
| 2661 |
continue; |
| 2662 |
|
| 2663 |
/* |
| 2664 |
* It's okay to consider ec_broken ECs here. Brokenness just means we |
| 2665 |
* couldn't derive all the implied clauses we'd have liked to; it does |
| 2666 |
* not invalidate our knowledge that the members are equal. |
| 2667 |
*/ |
| 2668 |
|
| 2669 |
/* Ignore if this EC doesn't use specified opfamily */ |
| 2670 |
if (OidIsValid(opfamily) && |
| 2671 |
!list_member_oid(ec->ec_opfamilies, opfamily)) |
| 2672 |
continue; |
| 2673 |
|
| 2674 |
/* Ignore children here */ |
| 2675 |
foreach(lc2, ec->ec_members) |
| 2676 |
{ |
| 2677 |
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2); |
| 2678 |
|
| 2679 |
/* Child members should not exist in ec_members */ |
| 2680 |
Assert(!em->em_is_child); |
| 2681 |
if (equal(item1, em->em_expr)) |
| 2682 |
item1member = true; |
| 2683 |
else if (equal(item2, em->em_expr)) |
| 2684 |
item2member = true; |
| 2685 |
/* Exit as soon as equality is proven */ |
| 2686 |
if (item1member && item2member) |
| 2687 |
return true; |
| 2688 |
} |
| 2689 |
} |
| 2690 |
return false; |
| 2691 |
} |
| 2692 |
|
| 2693 |
|
| 2694 |
/* |
| 2695 |
* match_eclasses_to_foreign_key_col |
| 2696 |
* See whether a foreign key column match is proven by any eclass. |
| 2697 |
* |
| 2698 |
* If the referenced and referencing Vars of the fkey's colno'th column are |
| 2699 |
* known equal due to any eclass, return that eclass; otherwise return NULL. |
| 2700 |
* (In principle there might be more than one matching eclass if multiple |
| 2701 |
* collations are involved, but since collation doesn't matter for equality, |
| 2702 |
* we ignore that fine point here.) This is much like exprs_known_equal, |
| 2703 |
* except for the format of the input. |
| 2704 |
* |
| 2705 |
* On success, we also set fkinfo->eclass[colno] to the matching eclass, |
| 2706 |
* and set fkinfo->fk_eclass_member[colno] to the eclass member for the |
| 2707 |
* referencing Var. |
| 2708 |
*/ |
| 2709 |
EquivalenceClass * |
| 2710 |
match_eclasses_to_foreign_key_col(PlannerInfo *root, |
| 2711 |
ForeignKeyOptInfo *fkinfo, |
| 2712 |
int colno) |
| 2713 |
{ |
| 2714 |
Index var1varno = fkinfo->con_relid; |
| 2715 |
AttrNumber var1attno = fkinfo->conkey[colno]; |
| 2716 |
Index var2varno = fkinfo->ref_relid; |
| 2717 |
AttrNumber var2attno = fkinfo->confkey[colno]; |
| 2718 |
Oid eqop = fkinfo->conpfeqop[colno]; |
| 2719 |
RelOptInfo *rel1 = root->simple_rel_array[var1varno]; |
| 2720 |
RelOptInfo *rel2 = root->simple_rel_array[var2varno]; |
| 2721 |
List *opfamilies = NIL; /* compute only if needed */ |
| 2722 |
Bitmapset *matching_ecs; |
| 2723 |
int i; |
| 2724 |
|
| 2725 |
/* Consider only eclasses mentioning both relations */ |
| 2726 |
Assert(root->ec_merging_done); |
| 2727 |
Assert(IS_SIMPLE_REL(rel1)); |
| 2728 |
Assert(IS_SIMPLE_REL(rel2)); |
| 2729 |
matching_ecs = bms_intersect(rel1->eclass_indexes, |
| 2730 |
rel2->eclass_indexes); |
| 2731 |
|
| 2732 |
i = -1; |
| 2733 |
while ((i = bms_next_member(matching_ecs, i)) >= 0) |
| 2734 |
{ |
| 2735 |
EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, |
| 2736 |
i); |
| 2737 |
EquivalenceMember *item1_em = NULL; |
| 2738 |
EquivalenceMember *item2_em = NULL; |
| 2739 |
ListCell *lc2; |
| 2740 |
|
| 2741 |
/* Never match to a volatile EC */ |
| 2742 |
if (ec->ec_has_volatile) |
| 2743 |
continue; |
| 2744 |
|
| 2745 |
/* |
| 2746 |
* It's okay to consider "broken" ECs here, see exprs_known_equal. |
| 2747 |
* Ignore children here. |
| 2748 |
*/ |
| 2749 |
foreach(lc2, ec->ec_members) |
| 2750 |
{ |
| 2751 |
EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2); |
| 2752 |
Var *var; |
| 2753 |
|
| 2754 |
/* Child members should not exist in ec_members */ |
| 2755 |
Assert(!em->em_is_child); |
| 2756 |
|
| 2757 |
/* EM must be a Var, possibly with RelabelType */ |
| 2758 |
var = (Var *) em->em_expr; |
| 2759 |
while (var && IsA(var, RelabelType)) |
| 2760 |
var = (Var *) ((RelabelType *) var)->arg; |
| 2761 |
if (!(var && IsA(var, Var))) |
| 2762 |
continue; |
| 2763 |
|
| 2764 |
/* Match? */ |
| 2765 |
if (var->varno == var1varno && var->varattno == var1attno) |
| 2766 |
item1_em = em; |
| 2767 |
else if (var->varno == var2varno && var->varattno == var2attno) |
| 2768 |
item2_em = em; |
| 2769 |
|
| 2770 |
/* Have we found both PK and FK column in this EC? */ |
| 2771 |
if (item1_em && item2_em) |
| 2772 |
{ |
| 2773 |
/* |
| 2774 |
* Succeed if eqop matches EC's opfamilies. We could test |
| 2775 |
* this before scanning the members, but it's probably cheaper |
| 2776 |
* to test for member matches first. |
| 2777 |
*/ |
| 2778 |
if (opfamilies == NIL) /* compute if we didn't already */ |
| 2779 |
opfamilies = get_mergejoin_opfamilies(eqop); |
| 2780 |
if (equal(opfamilies, ec->ec_opfamilies)) |
| 2781 |
{ |
| 2782 |
fkinfo->eclass[colno] = ec; |
| 2783 |
fkinfo->fk_eclass_member[colno] = item2_em; |
| 2784 |
return ec; |
| 2785 |
} |
| 2786 |
/* Otherwise, done with this EC, move on to the next */ |
| 2787 |
break; |
| 2788 |
} |
| 2789 |
} |
| 2790 |
} |
| 2791 |
return NULL; |
| 2792 |
} |
| 2793 |
|
| 2794 |
/* |
| 2795 |
* find_derived_clause_for_ec_member |
| 2796 |
* Search for a previously-derived clause mentioning the given EM. |
| 2797 |
* |
| 2798 |
* The eclass should be an ec_has_const EC, of which the EM is a non-const |
| 2799 |
* member. This should ensure there is just one derived clause mentioning |
| 2800 |
* the EM (and equating it to a constant). |
| 2801 |
* Returns NULL if no such clause can be found. |
| 2802 |
*/ |
| 2803 |
RestrictInfo * |
| 2804 |
find_derived_clause_for_ec_member(PlannerInfo *root, |
| 2805 |
EquivalenceClass *ec, |
| 2806 |
EquivalenceMember *em) |
| 2807 |
{ |
| 2808 |
Assert(ec->ec_has_const); |
| 2809 |
Assert(!em->em_is_const); |
| 2810 |
|
| 2811 |
return ec_search_derived_clause_for_ems(root, ec, em, NULL, NULL); |
| 2812 |
} |
| 2813 |
|
| 2814 |
|
| 2815 |
/* |
| 2816 |
* add_child_rel_equivalences |
| 2817 |
* Search for EC members that reference the root parent of child_rel, and |
| 2818 |
* add transformed members referencing the child_rel. |
| 2819 |
* |
| 2820 |
* Note that this function won't be called at all unless we have at least some |
| 2821 |
* reason to believe that the EC members it generates will be useful. |
| 2822 |
* |
| 2823 |
* parent_rel and child_rel could be derived from appinfo, but since the |
| 2824 |
* caller has already computed them, we might as well just pass them in. |
| 2825 |
* |
| 2826 |
* The passed-in AppendRelInfo is not used when the parent_rel is not a |
| 2827 |
* top-level baserel, since it shows the mapping from the parent_rel but |
| 2828 |
* we need to translate EC expressions that refer to the top-level parent. |
| 2829 |
* Using it is faster than using adjust_appendrel_attrs_multilevel(), though, |
| 2830 |
* so we prefer it when we can. |
| 2831 |
*/ |
| 2832 |
void |
| 2833 |
add_child_rel_equivalences(PlannerInfo *root, |
| 2834 |
AppendRelInfo *appinfo, |
| 2835 |
RelOptInfo *parent_rel, |
| 2836 |
RelOptInfo *child_rel) |
| 2837 |
{ |
| 2838 |
Relids top_parent_relids = child_rel->top_parent_relids; |
| 2839 |
Relids child_relids = child_rel->relids; |
| 2840 |
int i; |
| 2841 |
|
| 2842 |
/* |
| 2843 |
* EC merging should be complete already, so we can use the parent rel's |
| 2844 |
* eclass_indexes to avoid searching all of root->eq_classes. |
| 2845 |
*/ |
| 2846 |
Assert(root->ec_merging_done); |
| 2847 |
Assert(IS_SIMPLE_REL(parent_rel)); |
| 2848 |
|
| 2849 |
i = -1; |
| 2850 |
while ((i = bms_next_member(parent_rel->eclass_indexes, i)) >= 0) |
| 2851 |
{ |
| 2852 |
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); |
| 2853 |
|
| 2854 |
/* |
| 2855 |
* If this EC contains a volatile expression, then generating child |
| 2856 |
* EMs would be downright dangerous, so skip it. We rely on a |
| 2857 |
* volatile EC having only one EM. |
| 2858 |
*/ |
| 2859 |
if (cur_ec->ec_has_volatile) |
| 2860 |
continue; |
| 2861 |
|
| 2862 |
/* Sanity check eclass_indexes only contain ECs for parent_rel */ |
| 2863 |
Assert(bms_is_subset(top_parent_relids, cur_ec->ec_relids)); |
| 2864 |
|
| 2865 |
foreach_node(EquivalenceMember, cur_em, cur_ec->ec_members) |
| 2866 |
{ |
| 2867 |
if (cur_em->em_is_const) |
| 2868 |
continue; /* ignore consts here */ |
| 2869 |
|
| 2870 |
/* Child members should not exist in ec_members */ |
| 2871 |
Assert(!cur_em->em_is_child); |
| 2872 |
|
| 2873 |
/* |
| 2874 |
* Consider only members that reference and can be computed at |
| 2875 |
* child's topmost parent rel. In particular we want to exclude |
| 2876 |
* parent-rel Vars that have nonempty varnullingrels. Translating |
| 2877 |
* those might fail, if the transformed expression wouldn't be a |
| 2878 |
* simple Var; and in any case it wouldn't produce a member that |
| 2879 |
* has any use in creating plans for the child rel. |
| 2880 |
*/ |
| 2881 |
if (bms_is_subset(cur_em->em_relids, top_parent_relids) && |
| 2882 |
!bms_is_empty(cur_em->em_relids)) |
| 2883 |
{ |
| 2884 |
/* OK, generate transformed child version */ |
| 2885 |
Expr *child_expr; |
| 2886 |
Relids new_relids; |
| 2887 |
|
| 2888 |
if (parent_rel->reloptkind == RELOPT_BASEREL) |
| 2889 |
{ |
| 2890 |
/* Simple single-level transformation */ |
| 2891 |
child_expr = (Expr *) |
| 2892 |
adjust_appendrel_attrs(root, |
| 2893 |
(Node *) cur_em->em_expr, |
| 2894 |
1, &appinfo); |
| 2895 |
} |
| 2896 |
else |
| 2897 |
{ |
| 2898 |
/* Must do multi-level transformation */ |
| 2899 |
child_expr = (Expr *) |
| 2900 |
adjust_appendrel_attrs_multilevel(root, |
| 2901 |
(Node *) cur_em->em_expr, |
| 2902 |
child_rel, |
| 2903 |
child_rel->top_parent); |
| 2904 |
} |
| 2905 |
|
| 2906 |
/* |
| 2907 |
* Transform em_relids to match. Note we do *not* do |
| 2908 |
* pull_varnos(child_expr) here, as for example the |
| 2909 |
* transformation might have substituted a constant, but we |
| 2910 |
* don't want the child member to be marked as constant. |
| 2911 |
*/ |
| 2912 |
new_relids = bms_difference(cur_em->em_relids, |
| 2913 |
top_parent_relids); |
| 2914 |
new_relids = bms_add_members(new_relids, child_relids); |
| 2915 |
|
| 2916 |
add_child_eq_member(root, |
| 2917 |
cur_ec, |
| 2918 |
i, |
| 2919 |
child_expr, |
| 2920 |
new_relids, |
| 2921 |
cur_em->em_jdomain, |
| 2922 |
cur_em, |
| 2923 |
cur_em->em_datatype, |
| 2924 |
child_rel->relid); |
| 2925 |
} |
| 2926 |
} |
| 2927 |
} |
| 2928 |
} |
| 2929 |
|
| 2930 |
/* |
| 2931 |
* add_child_join_rel_equivalences |
| 2932 |
* Like add_child_rel_equivalences(), but for joinrels |
| 2933 |
* |
| 2934 |
* Here we find the ECs relevant to the top parent joinrel and add transformed |
| 2935 |
* member expressions that refer to this child joinrel. |
| 2936 |
* |
| 2937 |
* Note that this function won't be called at all unless we have at least some |
| 2938 |
* reason to believe that the EC members it generates will be useful. |
| 2939 |
*/ |
| 2940 |
void |
| 2941 |
add_child_join_rel_equivalences(PlannerInfo *root, |
| 2942 |
int nappinfos, AppendRelInfo **appinfos, |
| 2943 |
RelOptInfo *parent_joinrel, |
| 2944 |
RelOptInfo *child_joinrel) |
| 2945 |
{ |
| 2946 |
Relids top_parent_relids = child_joinrel->top_parent_relids; |
| 2947 |
Relids child_relids = child_joinrel->relids; |
| 2948 |
Bitmapset *matching_ecs; |
| 2949 |
MemoryContext oldcontext; |
| 2950 |
int i; |
| 2951 |
|
| 2952 |
Assert(IS_JOIN_REL(child_joinrel) && IS_JOIN_REL(parent_joinrel)); |
| 2953 |
|
| 2954 |
/* We need consider only ECs that mention the parent joinrel */ |
| 2955 |
matching_ecs = get_eclass_indexes_for_relids(root, top_parent_relids); |
| 2956 |
|
| 2957 |
/* |
| 2958 |
* If we're being called during GEQO join planning, we still have to |
| 2959 |
* create any new EC members in the main planner context, to avoid having |
| 2960 |
* a corrupt EC data structure after the GEQO context is reset. This is |
| 2961 |
* problematic since we'll leak memory across repeated GEQO cycles. For |
| 2962 |
* now, though, bloat is better than crash. If it becomes a real issue |
| 2963 |
* we'll have to do something to avoid generating duplicate EC members. |
| 2964 |
*/ |
| 2965 |
oldcontext = MemoryContextSwitchTo(root->planner_cxt); |
| 2966 |
|
| 2967 |
i = -1; |
| 2968 |
while ((i = bms_next_member(matching_ecs, i)) >= 0) |
| 2969 |
{ |
| 2970 |
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); |
| 2971 |
|
| 2972 |
/* |
| 2973 |
* If this EC contains a volatile expression, then generating child |
| 2974 |
* EMs would be downright dangerous, so skip it. We rely on a |
| 2975 |
* volatile EC having only one EM. |
| 2976 |
*/ |
| 2977 |
if (cur_ec->ec_has_volatile) |
| 2978 |
continue; |
| 2979 |
|
| 2980 |
/* Sanity check on get_eclass_indexes_for_relids result */ |
| 2981 |
Assert(bms_overlap(top_parent_relids, cur_ec->ec_relids)); |
| 2982 |
|
| 2983 |
foreach_node(EquivalenceMember, cur_em, cur_ec->ec_members) |
| 2984 |
{ |
| 2985 |
if (cur_em->em_is_const) |
| 2986 |
continue; /* ignore consts here */ |
| 2987 |
|
| 2988 |
/* Child members should not exist in ec_members */ |
| 2989 |
Assert(!cur_em->em_is_child); |
| 2990 |
|
| 2991 |
/* |
| 2992 |
* We may ignore expressions that reference a single baserel, |
| 2993 |
* because add_child_rel_equivalences should have handled them. |
| 2994 |
*/ |
| 2995 |
if (bms_membership(cur_em->em_relids) != BMS_MULTIPLE) |
| 2996 |
continue; |
| 2997 |
|
| 2998 |
/* Does this member reference child's topmost parent rel? */ |
| 2999 |
if (bms_overlap(cur_em->em_relids, top_parent_relids)) |
| 3000 |
{ |
| 3001 |
/* Yes, generate transformed child version */ |
| 3002 |
Expr *child_expr; |
| 3003 |
Relids new_relids; |
| 3004 |
|
| 3005 |
if (parent_joinrel->reloptkind == RELOPT_JOINREL) |
| 3006 |
{ |
| 3007 |
/* Simple single-level transformation */ |
| 3008 |
child_expr = (Expr *) |
| 3009 |
adjust_appendrel_attrs(root, |
| 3010 |
(Node *) cur_em->em_expr, |
| 3011 |
nappinfos, appinfos); |
| 3012 |
} |
| 3013 |
else |
| 3014 |
{ |
| 3015 |
/* Must do multi-level transformation */ |
| 3016 |
Assert(parent_joinrel->reloptkind == RELOPT_OTHER_JOINREL); |
| 3017 |
child_expr = (Expr *) |
| 3018 |
adjust_appendrel_attrs_multilevel(root, |
| 3019 |
(Node *) cur_em->em_expr, |
| 3020 |
child_joinrel, |
| 3021 |
child_joinrel->top_parent); |
| 3022 |
} |
| 3023 |
|
| 3024 |
/* |
| 3025 |
* Transform em_relids to match. Note we do *not* do |
| 3026 |
* pull_varnos(child_expr) here, as for example the |
| 3027 |
* transformation might have substituted a constant, but we |
| 3028 |
* don't want the child member to be marked as constant. |
| 3029 |
*/ |
| 3030 |
new_relids = bms_difference(cur_em->em_relids, |
| 3031 |
top_parent_relids); |
| 3032 |
new_relids = bms_add_members(new_relids, child_relids); |
| 3033 |
|
| 3034 |
/* |
| 3035 |
* Add new child member to the EquivalenceClass. Because this |
| 3036 |
* is a RELOPT_OTHER_JOINREL which has multiple component |
| 3037 |
* relids, there is no ideal place to store these members in |
| 3038 |
* the class. Ordinarily, child members are stored in the |
| 3039 |
* ec_childmembers[] array element corresponding to their |
| 3040 |
* relid, however, here we have multiple component relids, so |
| 3041 |
* there's no single ec_childmembers[] array element to store |
| 3042 |
* this member. So that we still correctly find this member |
| 3043 |
* in loops iterating over an EquivalenceMemberIterator, we |
| 3044 |
* opt to store the member in the ec_childmembers array in |
| 3045 |
* only the first component relid slot of the array. This |
| 3046 |
* allows the member to be found, providing callers of |
| 3047 |
* setup_eclass_member_iterator() specify all the component |
| 3048 |
* relids for the RELOPT_OTHER_JOINREL, which they do. If we |
| 3049 |
* opted to store the member in each ec_childmembers[] element |
| 3050 |
* for all the component relids, then that would just result |
| 3051 |
* in eclass_member_iterator_next() finding the member |
| 3052 |
* multiple times, which is a waste of effort. |
| 3053 |
*/ |
| 3054 |
add_child_eq_member(root, |
| 3055 |
cur_ec, |
| 3056 |
-1, |
| 3057 |
child_expr, |
| 3058 |
new_relids, |
| 3059 |
cur_em->em_jdomain, |
| 3060 |
cur_em, |
| 3061 |
cur_em->em_datatype, |
| 3062 |
bms_next_member(child_joinrel->relids, -1)); |
| 3063 |
} |
| 3064 |
} |
| 3065 |
} |
| 3066 |
|
| 3067 |
MemoryContextSwitchTo(oldcontext); |
| 3068 |
} |
| 3069 |
|
| 3070 |
/* |
| 3071 |
* add_setop_child_rel_equivalences |
| 3072 |
* Add equivalence members for each non-resjunk target in 'child_tlist' |
| 3073 |
* to the EquivalenceClass in the corresponding setop_pathkey's pk_eclass. |
| 3074 |
* |
| 3075 |
* 'root' is the PlannerInfo belonging to the top-level set operation. |
| 3076 |
* 'child_rel' is the RelOptInfo of the child relation we're adding |
| 3077 |
* EquivalenceMembers for. |
| 3078 |
* 'child_tlist' is the target list for the setop child relation. The target |
| 3079 |
* list expressions are what we add as EquivalenceMembers. |
| 3080 |
* 'setop_pathkeys' is a list of PathKeys which must contain an entry for each |
| 3081 |
* non-resjunk target in 'child_tlist'. |
| 3082 |
*/ |
| 3083 |
void |
| 3084 |
add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel, |
| 3085 |
List *child_tlist, List *setop_pathkeys) |
| 3086 |
{ |
| 3087 |
ListCell *lc; |
| 3088 |
ListCell *lc2 = list_head(setop_pathkeys); |
| 3089 |
|
| 3090 |
foreach(lc, child_tlist) |
| 3091 |
{ |
| 3092 |
TargetEntry *tle = lfirst_node(TargetEntry, lc); |
| 3093 |
EquivalenceMember *parent_em; |
| 3094 |
PathKey *pk; |
| 3095 |
|
| 3096 |
if (tle->resjunk) |
| 3097 |
continue; |
| 3098 |
|
| 3099 |
if (lc2 == NULL) |
| 3100 |
elog(ERROR, "too few pathkeys for set operation"); |
| 3101 |
|
| 3102 |
pk = lfirst_node(PathKey, lc2); |
| 3103 |
parent_em = linitial(pk->pk_eclass->ec_members); |
| 3104 |
|
| 3105 |
/* |
| 3106 |
* We can safely pass the parent member as the first member in the |
| 3107 |
* ec_members list as this is added first in generate_union_paths, |
| 3108 |
* likewise, the JoinDomain can be that of the initial member of the |
| 3109 |
* Pathkey's EquivalenceClass. We pass -1 for ec_index since we |
| 3110 |
* maintain the eclass_indexes for the child_rel after the loop. |
| 3111 |
*/ |
| 3112 |
add_child_eq_member(root, |
| 3113 |
pk->pk_eclass, |
| 3114 |
-1, |
| 3115 |
tle->expr, |
| 3116 |
child_rel->relids, |
| 3117 |
parent_em->em_jdomain, |
| 3118 |
parent_em, |
| 3119 |
exprType((Node *) tle->expr), |
| 3120 |
child_rel->relid); |
| 3121 |
|
| 3122 |
lc2 = lnext(setop_pathkeys, lc2); |
| 3123 |
} |
| 3124 |
|
| 3125 |
/* |
| 3126 |
* transformSetOperationStmt() ensures that the targetlist never contains |
| 3127 |
* any resjunk columns, so all eclasses that exist in 'root' must have |
| 3128 |
* received a new member in the loop above. Add them to the child_rel's |
| 3129 |
* eclass_indexes. |
| 3130 |
*/ |
| 3131 |
child_rel->eclass_indexes = bms_add_range(child_rel->eclass_indexes, 0, |
| 3132 |
list_length(root->eq_classes) - 1); |
| 3133 |
} |
| 3134 |
|
| 3135 |
/* |
| 3136 |
* setup_eclass_member_iterator |
| 3137 |
* Setup an EquivalenceMemberIterator 'it' to iterate over all parent |
| 3138 |
* EquivalenceMembers and child members belonging to the given 'ec'. |
| 3139 |
* |
| 3140 |
* This iterator returns: |
| 3141 |
* - All parent members stored directly in ec_members for 'ec', and; |
| 3142 |
* - Any child member added to the given ec by add_child_eq_member() where |
| 3143 |
* the child_relid specified in the add_child_eq_member() call is a member |
| 3144 |
* of the 'child_relids' parameter. |
| 3145 |
* |
| 3146 |
* Note: |
| 3147 |
* The given 'child_relids' must remain allocated and not be changed for the |
| 3148 |
* lifetime of the iterator. |
| 3149 |
* |
| 3150 |
* Parameters: |
| 3151 |
* 'it' is a pointer to the iterator to set up. Normally stack allocated. |
| 3152 |
* 'ec' is the EquivalenceClass from which to iterate members for. |
| 3153 |
* 'child_relids' is the relids to return child members for. |
| 3154 |
*/ |
| 3155 |
void |
| 3156 |
setup_eclass_member_iterator(EquivalenceMemberIterator *it, |
| 3157 |
EquivalenceClass *ec, Relids child_relids) |
| 3158 |
{ |
| 3159 |
it->ec = ec; |
| 3160 |
/* no need to set this if the class has no child members array set */ |
| 3161 |
it->child_relids = ec->ec_childmembers != NULL ? child_relids : NULL; |
| 3162 |
it->current_relid = -1; |
| 3163 |
it->current_list = ec->ec_members; |
| 3164 |
it->current_cell = list_head(it->current_list); |
| 3165 |
} |
| 3166 |
|
| 3167 |
/* |
| 3168 |
* eclass_member_iterator_next |
| 3169 |
* Get the next EquivalenceMember from the EquivalenceMemberIterator 'it', |
| 3170 |
* as setup by setup_eclass_member_iterator(). NULL is returned if there |
| 3171 |
* are no members left, after which callers must not call |
| 3172 |
* eclass_member_iterator_next() again for the given iterator. |
| 3173 |
*/ |
| 3174 |
EquivalenceMember * |
| 3175 |
eclass_member_iterator_next(EquivalenceMemberIterator *it) |
| 3176 |
{ |
| 3177 |
while (it->current_list != NULL) |
| 3178 |
{ |
| 3179 |
while (it->current_cell != NULL) |
| 3180 |
{ |
| 3181 |
EquivalenceMember *em; |
| 3182 |
|
| 3183 |
nextcell: |
| 3184 |
em = lfirst_node(EquivalenceMember, it->current_cell); |
| 3185 |
it->current_cell = lnext(it->current_list, it->current_cell); |
| 3186 |
return em; |
| 3187 |
} |
| 3188 |
|
| 3189 |
/* Search for the next list to return members from */ |
| 3190 |
while ((it->current_relid = bms_next_member(it->child_relids, it->current_relid)) > 0) |
| 3191 |
{ |
| 3192 |
/* |
| 3193 |
* Be paranoid in case we're given relids above what we've sized |
| 3194 |
* the ec_childmembers array to. |
| 3195 |
*/ |
| 3196 |
if (it->current_relid >= it->ec->ec_childmembers_size) |
| 3197 |
return NULL; |
| 3198 |
|
| 3199 |
it->current_list = it->ec->ec_childmembers[it->current_relid]; |
| 3200 |
|
| 3201 |
/* If there are members in this list, use it. */ |
| 3202 |
if (it->current_list != NIL) |
| 3203 |
{ |
| 3204 |
/* point current_cell to the head of this list */ |
| 3205 |
it->current_cell = list_head(it->current_list); |
| 3206 |
goto nextcell; |
| 3207 |
} |
| 3208 |
} |
| 3209 |
return NULL; |
| 3210 |
} |
| 3211 |
|
| 3212 |
return NULL; |
| 3213 |
} |
| 3214 |
|
| 3215 |
/* |
| 3216 |
* generate_implied_equalities_for_column |
| 3217 |
* Create EC-derived joinclauses usable with a specific column. |
| 3218 |
* |
| 3219 |
* This is used by indxpath.c to extract potentially indexable joinclauses |
| 3220 |
* from ECs, and can be used by foreign data wrappers for similar purposes. |
| 3221 |
* We assume that only expressions in Vars of a single table are of interest, |
| 3222 |
* but the caller provides a callback function to identify exactly which |
| 3223 |
* such expressions it would like to know about. |
| 3224 |
* |
| 3225 |
* We assume that any given table/index column could appear in only one EC. |
| 3226 |
* (This should be true in all but the most pathological cases, and if it |
| 3227 |
* isn't, we stop on the first match anyway.) Therefore, what we return |
| 3228 |
* is a redundant list of clauses equating the table/index column to each of |
| 3229 |
* the other-relation values it is known to be equal to. Any one of |
| 3230 |
* these clauses can be used to create a parameterized path, and there |
| 3231 |
* is no value in using more than one. (But it *is* worthwhile to create |
| 3232 |
* a separate parameterized path for each one, since that leads to different |
| 3233 |
* join orders.) |
| 3234 |
* |
| 3235 |
* The caller can pass a Relids set of rels we aren't interested in joining |
| 3236 |
* to, so as to save the work of creating useless clauses. |
| 3237 |
*/ |
| 3238 |
List * |
| 3239 |
generate_implied_equalities_for_column(PlannerInfo *root, |
| 3240 |
RelOptInfo *rel, |
| 3241 |
ec_matches_callback_type callback, |
| 3242 |
void *callback_arg, |
| 3243 |
Relids prohibited_rels) |
| 3244 |
{ |
| 3245 |
List *result = NIL; |
| 3246 |
bool is_child_rel = (rel->reloptkind == RELOPT_OTHER_MEMBER_REL); |
| 3247 |
Relids parent_relids; |
| 3248 |
int i; |
| 3249 |
|
| 3250 |
/* Should be OK to rely on eclass_indexes */ |
| 3251 |
Assert(root->ec_merging_done); |
| 3252 |
|
| 3253 |
/* Indexes are available only on base or "other" member relations. */ |
| 3254 |
Assert(IS_SIMPLE_REL(rel)); |
| 3255 |
|
| 3256 |
/* If it's a child rel, we'll need to know what its parent(s) are */ |
| 3257 |
if (is_child_rel) |
| 3258 |
parent_relids = find_childrel_parents(root, rel); |
| 3259 |
else |
| 3260 |
parent_relids = NULL; /* not used, but keep compiler quiet */ |
| 3261 |
|
| 3262 |
i = -1; |
| 3263 |
while ((i = bms_next_member(rel->eclass_indexes, i)) >= 0) |
| 3264 |
{ |
| 3265 |
EquivalenceClass *cur_ec = (EquivalenceClass *) list_nth(root->eq_classes, i); |
| 3266 |
EquivalenceMemberIterator it; |
| 3267 |
EquivalenceMember *cur_em; |
| 3268 |
ListCell *lc2; |
| 3269 |
|
| 3270 |
/* Sanity check eclass_indexes only contain ECs for rel */ |
| 3271 |
Assert(is_child_rel || bms_is_subset(rel->relids, cur_ec->ec_relids)); |
| 3272 |
|
| 3273 |
/* |
| 3274 |
* Won't generate joinclauses if const or single-member (the latter |
| 3275 |
* test covers the volatile case too) |
| 3276 |
*/ |
| 3277 |
if (cur_ec->ec_has_const || list_length(cur_ec->ec_members) <= 1) |
| 3278 |
continue; |
| 3279 |
|
| 3280 |
/* |
| 3281 |
* Scan members, looking for a match to the target column. Note that |
| 3282 |
* child EC members are considered, but only when they belong to the |
| 3283 |
* target relation. (Unlike regular members, the same expression |
| 3284 |
* could be a child member of more than one EC. Therefore, it's |
| 3285 |
* potentially order-dependent which EC a child relation's target |
| 3286 |
* column gets matched to. This is annoying but it only happens in |
| 3287 |
* corner cases, so for now we live with just reporting the first |
| 3288 |
* match. See also get_eclass_for_sort_expr.) |
| 3289 |
*/ |
| 3290 |
setup_eclass_member_iterator(&it, cur_ec, rel->relids); |
| 3291 |
while ((cur_em = eclass_member_iterator_next(&it)) != NULL) |
| 3292 |
{ |
| 3293 |
if (bms_equal(cur_em->em_relids, rel->relids) && |
| 3294 |
callback(root, rel, cur_ec, cur_em, callback_arg)) |
| 3295 |
break; |
| 3296 |
} |
| 3297 |
|
| 3298 |
if (!cur_em) |
| 3299 |
continue; |
| 3300 |
|
| 3301 |
/* |
| 3302 |
* Found our match. Scan the other EC members and attempt to generate |
| 3303 |
* joinclauses. Ignore children here. |
| 3304 |
*/ |
| 3305 |
foreach(lc2, cur_ec->ec_members) |
| 3306 |
{ |
| 3307 |
EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2); |
| 3308 |
Oid eq_op; |
| 3309 |
RestrictInfo *rinfo; |
| 3310 |
|
| 3311 |
/* Child members should not exist in ec_members */ |
| 3312 |
Assert(!other_em->em_is_child); |
| 3313 |
|
| 3314 |
/* Make sure it'll be a join to a different rel */ |
| 3315 |
if (other_em == cur_em || |
| 3316 |
bms_overlap(other_em->em_relids, rel->relids)) |
| 3317 |
continue; |
| 3318 |
|
| 3319 |
/* Forget it if caller doesn't want joins to this rel */ |
| 3320 |
if (bms_overlap(other_em->em_relids, prohibited_rels)) |
| 3321 |
continue; |
| 3322 |
|
| 3323 |
/* |
| 3324 |
* Also, if this is a child rel, avoid generating a useless join |
| 3325 |
* to its parent rel(s). |
| 3326 |
*/ |
| 3327 |
if (is_child_rel && |
| 3328 |
bms_overlap(parent_relids, other_em->em_relids)) |
| 3329 |
continue; |
| 3330 |
|
| 3331 |
eq_op = select_equality_operator(cur_ec, |
| 3332 |
cur_em->em_datatype, |
| 3333 |
other_em->em_datatype); |
| 3334 |
if (!OidIsValid(eq_op)) |
| 3335 |
continue; |
| 3336 |
|
| 3337 |
/* set parent_ec to mark as redundant with other joinclauses */ |
| 3338 |
rinfo = create_join_clause(root, cur_ec, eq_op, |
| 3339 |
cur_em, other_em, |
| 3340 |
cur_ec); |
| 3341 |
|
| 3342 |
result = lappend(result, rinfo); |
| 3343 |
} |
| 3344 |
|
| 3345 |
/* |
| 3346 |
* If somehow we failed to create any join clauses, we might as well |
| 3347 |
* keep scanning the ECs for another match. But if we did make any, |
| 3348 |
* we're done, because we don't want to return non-redundant clauses. |
| 3349 |
*/ |
| 3350 |
if (result) |
| 3351 |
break; |
| 3352 |
} |
| 3353 |
|
| 3354 |
return result; |
| 3355 |
} |
| 3356 |
|
| 3357 |
/* |
| 3358 |
* have_relevant_eclass_joinclause |
| 3359 |
* Detect whether there is an EquivalenceClass that could produce |
| 3360 |
* a joinclause involving the two given relations. |
| 3361 |
* |
| 3362 |
* This is essentially a very cut-down version of |
| 3363 |
* generate_join_implied_equalities(). Note it's OK to occasionally say "yes" |
| 3364 |
* incorrectly. Hence we don't bother with details like whether the lack of a |
| 3365 |
* cross-type operator might prevent the clause from actually being generated. |
| 3366 |
* False negatives are not always fatal either: they will discourage, but not |
| 3367 |
* completely prevent, investigation of particular join pathways. |
| 3368 |
*/ |
| 3369 |
bool |
| 3370 |
have_relevant_eclass_joinclause(PlannerInfo *root, |
| 3371 |
RelOptInfo *rel1, RelOptInfo *rel2) |
| 3372 |
{ |
| 3373 |
Bitmapset *matching_ecs; |
| 3374 |
int i; |
| 3375 |
|
| 3376 |
/* |
| 3377 |
* Examine only eclasses mentioning both rel1 and rel2. |
| 3378 |
* |
| 3379 |
* Note that we do not consider the possibility of an eclass generating |
| 3380 |
* "join" clauses that mention just one of the rels plus an outer join |
| 3381 |
* that could be formed from them. Although such clauses must be |
| 3382 |
* correctly enforced when we form the outer join, they don't seem like |
| 3383 |
* sufficient reason to prioritize this join over other ones. The join |
| 3384 |
* ordering rules will force the join to be made when necessary. |
| 3385 |
*/ |
| 3386 |
matching_ecs = get_common_eclass_indexes(root, rel1->relids, |
| 3387 |
rel2->relids); |
| 3388 |
|
| 3389 |
i = -1; |
| 3390 |
while ((i = bms_next_member(matching_ecs, i)) >= 0) |
| 3391 |
{ |
| 3392 |
EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, |
| 3393 |
i); |
| 3394 |
|
| 3395 |
/* |
| 3396 |
* Sanity check that get_common_eclass_indexes gave only ECs |
| 3397 |
* containing both rels. |
| 3398 |
*/ |
| 3399 |
Assert(bms_overlap(rel1->relids, ec->ec_relids)); |
| 3400 |
Assert(bms_overlap(rel2->relids, ec->ec_relids)); |
| 3401 |
|
| 3402 |
/* |
| 3403 |
* Won't generate joinclauses if single-member (this test covers the |
| 3404 |
* volatile case too) |
| 3405 |
*/ |
| 3406 |
if (list_length(ec->ec_members) <= 1) |
| 3407 |
continue; |
| 3408 |
|
| 3409 |
/* |
| 3410 |
* We do not need to examine the individual members of the EC, because |
| 3411 |
* all that we care about is whether each rel overlaps the relids of |
| 3412 |
* at least one member, and get_common_eclass_indexes() and the single |
| 3413 |
* member check above are sufficient to prove that. (As with |
| 3414 |
* have_relevant_joinclause(), it is not necessary that the EC be able |
| 3415 |
* to form a joinclause relating exactly the two given rels, only that |
| 3416 |
* it be able to form a joinclause mentioning both, and this will |
| 3417 |
* surely be true if both of them overlap ec_relids.) |
| 3418 |
* |
| 3419 |
* Note we don't test ec_broken; if we did, we'd need a separate code |
| 3420 |
* path to look through ec_sources. Checking the membership anyway is |
| 3421 |
* OK as a possibly-overoptimistic heuristic. |
| 3422 |
* |
| 3423 |
* We don't test ec_has_const either, even though a const eclass won't |
| 3424 |
* generate real join clauses. This is because if we had "WHERE a.x = |
| 3425 |
* b.y and a.x = 42", it is worth considering a join between a and b, |
| 3426 |
* since the join result is likely to be small even though it'll end |
| 3427 |
* up being an unqualified nestloop. |
| 3428 |
*/ |
| 3429 |
|
| 3430 |
return true; |
| 3431 |
} |
| 3432 |
|
| 3433 |
return false; |
| 3434 |
} |
| 3435 |
|
| 3436 |
|
| 3437 |
/* |
| 3438 |
* has_relevant_eclass_joinclause |
| 3439 |
* Detect whether there is an EquivalenceClass that could produce |
| 3440 |
* a joinclause involving the given relation and anything else. |
| 3441 |
* |
| 3442 |
* This is the same as have_relevant_eclass_joinclause with the other rel |
| 3443 |
* implicitly defined as "everything else in the query". |
| 3444 |
*/ |
| 3445 |
bool |
| 3446 |
has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1) |
| 3447 |
{ |
| 3448 |
Bitmapset *matched_ecs; |
| 3449 |
int i; |
| 3450 |
|
| 3451 |
/* Examine only eclasses mentioning rel1 */ |
| 3452 |
matched_ecs = get_eclass_indexes_for_relids(root, rel1->relids); |
| 3453 |
|
| 3454 |
i = -1; |
| 3455 |
while ((i = bms_next_member(matched_ecs, i)) >= 0) |
| 3456 |
{ |
| 3457 |
EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, |
| 3458 |
i); |
| 3459 |
|
| 3460 |
/* |
| 3461 |
* Won't generate joinclauses if single-member (this test covers the |
| 3462 |
* volatile case too) |
| 3463 |
*/ |
| 3464 |
if (list_length(ec->ec_members) <= 1) |
| 3465 |
continue; |
| 3466 |
|
| 3467 |
/* |
| 3468 |
* Per the comment in have_relevant_eclass_joinclause, it's sufficient |
| 3469 |
* to find an EC that mentions both this rel and some other rel. |
| 3470 |
*/ |
| 3471 |
if (!bms_is_subset(ec->ec_relids, rel1->relids)) |
| 3472 |
return true; |
| 3473 |
} |
| 3474 |
|
| 3475 |
return false; |
| 3476 |
} |
| 3477 |
|
| 3478 |
|
| 3479 |
/* |
| 3480 |
* eclass_useful_for_merging |
| 3481 |
* Detect whether the EC could produce any mergejoinable join clauses |
| 3482 |
* against the specified relation. |
| 3483 |
* |
| 3484 |
* This is just a heuristic test and doesn't have to be exact; it's better |
| 3485 |
* to say "yes" incorrectly than "no". Hence we don't bother with details |
| 3486 |
* like whether the lack of a cross-type operator might prevent the clause |
| 3487 |
* from actually being generated. |
| 3488 |
*/ |
| 3489 |
bool |
| 3490 |
eclass_useful_for_merging(PlannerInfo *root, |
| 3491 |
EquivalenceClass *eclass, |
| 3492 |
RelOptInfo *rel) |
| 3493 |
{ |
| 3494 |
Relids relids; |
| 3495 |
ListCell *lc; |
| 3496 |
|
| 3497 |
Assert(!eclass->ec_merged); |
| 3498 |
|
| 3499 |
/* |
| 3500 |
* Won't generate joinclauses if const or single-member (the latter test |
| 3501 |
* covers the volatile case too) |
| 3502 |
*/ |
| 3503 |
if (eclass->ec_has_const || list_length(eclass->ec_members) <= 1) |
| 3504 |
return false; |
| 3505 |
|
| 3506 |
/* |
| 3507 |
* Note we don't test ec_broken; if we did, we'd need a separate code path |
| 3508 |
* to look through ec_sources. Checking the members anyway is OK as a |
| 3509 |
* possibly-overoptimistic heuristic. |
| 3510 |
*/ |
| 3511 |
|
| 3512 |
/* If specified rel is a child, we must consider the topmost parent rel */ |
| 3513 |
if (IS_OTHER_REL(rel)) |
| 3514 |
{ |
| 3515 |
Assert(!bms_is_empty(rel->top_parent_relids)); |
| 3516 |
relids = rel->top_parent_relids; |
| 3517 |
} |
| 3518 |
else |
| 3519 |
relids = rel->relids; |
| 3520 |
|
| 3521 |
/* If rel already includes all members of eclass, no point in searching */ |
| 3522 |
if (bms_is_subset(eclass->ec_relids, relids)) |
| 3523 |
return false; |
| 3524 |
|
| 3525 |
/* |
| 3526 |
* To join, we need a member not in the given rel. Ignore children here. |
| 3527 |
*/ |
| 3528 |
foreach(lc, eclass->ec_members) |
| 3529 |
{ |
| 3530 |
EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc); |
| 3531 |
|
| 3532 |
/* Child members should not exist in ec_members */ |
| 3533 |
Assert(!cur_em->em_is_child); |
| 3534 |
|
| 3535 |
if (!bms_overlap(cur_em->em_relids, relids)) |
| 3536 |
return true; |
| 3537 |
} |
| 3538 |
|
| 3539 |
return false; |
| 3540 |
} |
| 3541 |
|
| 3542 |
|
| 3543 |
/* |
| 3544 |
* is_redundant_derived_clause |
| 3545 |
* Test whether rinfo is derived from same EC as any clause in clauselist; |
| 3546 |
* if so, it can be presumed to represent a condition that's redundant |
| 3547 |
* with that member of the list. |
| 3548 |
*/ |
| 3549 |
bool |
| 3550 |
is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist) |
| 3551 |
{ |
| 3552 |
EquivalenceClass *parent_ec = rinfo->parent_ec; |
| 3553 |
ListCell *lc; |
| 3554 |
|
| 3555 |
/* Fail if it's not a potentially-redundant clause from some EC */ |
| 3556 |
if (parent_ec == NULL) |
| 3557 |
return false; |
| 3558 |
|
| 3559 |
foreach(lc, clauselist) |
| 3560 |
{ |
| 3561 |
RestrictInfo *otherrinfo = (RestrictInfo *) lfirst(lc); |
| 3562 |
|
| 3563 |
if (otherrinfo->parent_ec == parent_ec) |
| 3564 |
return true; |
| 3565 |
} |
| 3566 |
|
| 3567 |
return false; |
| 3568 |
} |
| 3569 |
|
| 3570 |
/* |
| 3571 |
* is_redundant_with_indexclauses |
| 3572 |
* Test whether rinfo is redundant with any clause in the IndexClause |
| 3573 |
* list. Here, for convenience, we test both simple identity and |
| 3574 |
* whether it is derived from the same EC as any member of the list. |
| 3575 |
*/ |
| 3576 |
bool |
| 3577 |
is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses) |
| 3578 |
{ |
| 3579 |
EquivalenceClass *parent_ec = rinfo->parent_ec; |
| 3580 |
ListCell *lc; |
| 3581 |
|
| 3582 |
foreach(lc, indexclauses) |
| 3583 |
{ |
| 3584 |
IndexClause *iclause = lfirst_node(IndexClause, lc); |
| 3585 |
RestrictInfo *otherrinfo = iclause->rinfo; |
| 3586 |
|
| 3587 |
/* If indexclause is lossy, it won't enforce the condition exactly */ |
| 3588 |
if (iclause->lossy) |
| 3589 |
continue; |
| 3590 |
|
| 3591 |
/* Match if it's same clause (pointer equality should be enough) */ |
| 3592 |
if (rinfo == otherrinfo) |
| 3593 |
return true; |
| 3594 |
/* Match if derived from same EC */ |
| 3595 |
if (parent_ec && otherrinfo->parent_ec == parent_ec) |
| 3596 |
return true; |
| 3597 |
|
| 3598 |
/* |
| 3599 |
* No need to look at the derived clauses in iclause->indexquals; they |
| 3600 |
* couldn't match if the parent clause didn't. |
| 3601 |
*/ |
| 3602 |
} |
| 3603 |
|
| 3604 |
return false; |
| 3605 |
} |
| 3606 |
|
| 3607 |
/* |
| 3608 |
* get_eclass_indexes_for_relids |
| 3609 |
* Build and return a Bitmapset containing the indexes into root's |
| 3610 |
* eq_classes list for all eclasses that mention any of these relids |
| 3611 |
*/ |
| 3612 |
static Bitmapset * |
| 3613 |
get_eclass_indexes_for_relids(PlannerInfo *root, Relids relids) |
| 3614 |
{ |
| 3615 |
Bitmapset *ec_indexes = NULL; |
| 3616 |
int i = -1; |
| 3617 |
|
| 3618 |
/* Should be OK to rely on eclass_indexes */ |
| 3619 |
Assert(root->ec_merging_done); |
| 3620 |
|
| 3621 |
while ((i = bms_next_member(relids, i)) > 0) |
| 3622 |
{ |
| 3623 |
RelOptInfo *rel = root->simple_rel_array[i]; |
| 3624 |
|
| 3625 |
/* ignore the RTE_GROUP RTE */ |
| 3626 |
if (i == root->group_rtindex) |
| 3627 |
continue; |
| 3628 |
|
| 3629 |
if (rel == NULL) /* must be an outer join */ |
| 3630 |
{ |
| 3631 |
Assert(bms_is_member(i, root->outer_join_rels)); |
| 3632 |
continue; |
| 3633 |
} |
| 3634 |
|
| 3635 |
ec_indexes = bms_add_members(ec_indexes, rel->eclass_indexes); |
| 3636 |
} |
| 3637 |
return ec_indexes; |
| 3638 |
} |
| 3639 |
|
| 3640 |
/* |
| 3641 |
* get_common_eclass_indexes |
| 3642 |
* Build and return a Bitmapset containing the indexes into root's |
| 3643 |
* eq_classes list for all eclasses that mention rels in both |
| 3644 |
* relids1 and relids2. |
| 3645 |
*/ |
| 3646 |
static Bitmapset * |
| 3647 |
get_common_eclass_indexes(PlannerInfo *root, Relids relids1, Relids relids2) |
| 3648 |
{ |
| 3649 |
Bitmapset *rel1ecs; |
| 3650 |
Bitmapset *rel2ecs; |
| 3651 |
int relid; |
| 3652 |
|
| 3653 |
rel1ecs = get_eclass_indexes_for_relids(root, relids1); |
| 3654 |
|
| 3655 |
/* |
| 3656 |
* We can get away with just using the relation's eclass_indexes directly |
| 3657 |
* when relids2 is a singleton set. |
| 3658 |
*/ |
| 3659 |
if (bms_get_singleton_member(relids2, &relid)) |
| 3660 |
rel2ecs = root->simple_rel_array[relid]->eclass_indexes; |
| 3661 |
else |
| 3662 |
rel2ecs = get_eclass_indexes_for_relids(root, relids2); |
| 3663 |
|
| 3664 |
/* Calculate and return the common EC indexes, recycling the left input. */ |
| 3665 |
return bms_int_members(rel1ecs, rel2ecs); |
| 3666 |
} |
| 3667 |
|
| 3668 |
/* |
| 3669 |
* ec_build_derives_hash |
| 3670 |
* Construct the auxiliary hash table for derived clause lookups. |
| 3671 |
*/ |
| 3672 |
static void |
| 3673 |
ec_build_derives_hash(PlannerInfo *root, EquivalenceClass *ec) |
| 3674 |
{ |
| 3675 |
Assert(!ec->ec_derives_hash); |
| 3676 |
|
| 3677 |
/* |
| 3678 |
* Create the hash table. |
| 3679 |
* |
| 3680 |
* We pass list_length(ec->ec_derives_list) as the initial size. |
| 3681 |
* Simplehash will divide this by the fillfactor (typically 0.9) and round |
| 3682 |
* up to the next power of two, so this will usually give us at least 64 |
| 3683 |
* buckets around the threshold. That avoids immediate resizing without |
| 3684 |
* hardcoding a specific size. |
| 3685 |
*/ |
| 3686 |
ec->ec_derives_hash = derives_create(root->planner_cxt, |
| 3687 |
list_length(ec->ec_derives_list), |
| 3688 |
NULL); |
| 3689 |
|
| 3690 |
foreach_node(RestrictInfo, rinfo, ec->ec_derives_list) |
| 3691 |
ec_add_clause_to_derives_hash(ec, rinfo); |
| 3692 |
} |
| 3693 |
|
| 3694 |
/* |
| 3695 |
* ec_add_derived_clause |
| 3696 |
* Add a clause to the set of derived clauses for the given |
| 3697 |
* EquivalenceClass. Always appends to ec_derives_list; also adds |
| 3698 |
* to ec_derives_hash if it exists. |
| 3699 |
* |
| 3700 |
* Also asserts expected invariants of derived clauses. |
| 3701 |
*/ |
| 3702 |
static void |
| 3703 |
ec_add_derived_clause(EquivalenceClass *ec, RestrictInfo *clause) |
| 3704 |
{ |
| 3705 |
/* |
| 3706 |
* Constant, if present, is always placed on the RHS; see |
| 3707 |
* generate_base_implied_equalities_const(). LHS is never a constant. |
| 3708 |
*/ |
| 3709 |
Assert(!clause->left_em->em_is_const); |
| 3710 |
|
| 3711 |
/* |
| 3712 |
* Clauses containing a constant are never considered redundant, so |
| 3713 |
* parent_ec is not set. |
| 3714 |
*/ |
| 3715 |
Assert(!clause->parent_ec || !clause->right_em->em_is_const); |
| 3716 |
|
| 3717 |
ec->ec_derives_list = lappend(ec->ec_derives_list, clause); |
| 3718 |
if (ec->ec_derives_hash) |
| 3719 |
ec_add_clause_to_derives_hash(ec, clause); |
| 3720 |
} |
| 3721 |
|
| 3722 |
/* |
| 3723 |
* ec_add_derived_clauses |
| 3724 |
* Add a list of clauses to the set of clauses derived from the given |
| 3725 |
* EquivalenceClass; adding to the list and hash table if needed. |
| 3726 |
* |
| 3727 |
* This function is similar to ec_add_derived_clause() but optimized for adding |
| 3728 |
* multiple clauses at a time to the ec_derives_list. The assertions from |
| 3729 |
* ec_add_derived_clause() are not repeated here, as the input clauses are |
| 3730 |
* assumed to have already been validated. |
| 3731 |
*/ |
| 3732 |
static void |
| 3733 |
ec_add_derived_clauses(EquivalenceClass *ec, List *clauses) |
| 3734 |
{ |
| 3735 |
ec->ec_derives_list = list_concat(ec->ec_derives_list, clauses); |
| 3736 |
if (ec->ec_derives_hash) |
| 3737 |
foreach_node(RestrictInfo, rinfo, clauses) |
| 3738 |
ec_add_clause_to_derives_hash(ec, rinfo); |
| 3739 |
} |
| 3740 |
|
| 3741 |
/* |
| 3742 |
* fill_ec_derives_key |
| 3743 |
* Compute a canonical key for ec_derives_hash lookup or insertion. |
| 3744 |
* |
| 3745 |
* Derived clauses are looked up using a pair of EquivalenceMembers and a |
| 3746 |
* parent EquivalenceClass. To avoid storing or searching for both EM orderings, |
| 3747 |
* we canonicalize the key: |
| 3748 |
* |
| 3749 |
* - For clauses involving two non-constant EMs, em1 is set to the EM with lower |
| 3750 |
* memory address and em2 is set to the other one. |
| 3751 |
* - For clauses involving a constant EM, the caller must pass the non-constant |
| 3752 |
* EM as leftem and NULL as rightem; we then set em1 = NULL and em2 = leftem. |
| 3753 |
*/ |
| 3754 |
static inline void |
| 3755 |
fill_ec_derives_key(ECDerivesKey *key, |
| 3756 |
EquivalenceMember *leftem, |
| 3757 |
EquivalenceMember *rightem, |
| 3758 |
EquivalenceClass *parent_ec) |
| 3759 |
{ |
| 3760 |
Assert(leftem); /* Always required for lookup or insertion */ |
| 3761 |
|
| 3762 |
if (rightem == NULL) |
| 3763 |
{ |
| 3764 |
key->em1 = NULL; |
| 3765 |
key->em2 = leftem; |
| 3766 |
} |
| 3767 |
else if (leftem < rightem) |
| 3768 |
{ |
| 3769 |
key->em1 = leftem; |
| 3770 |
key->em2 = rightem; |
| 3771 |
} |
| 3772 |
else |
| 3773 |
{ |
| 3774 |
key->em1 = rightem; |
| 3775 |
key->em2 = leftem; |
| 3776 |
} |
| 3777 |
key->parent_ec = parent_ec; |
| 3778 |
} |
| 3779 |
|
| 3780 |
/* |
| 3781 |
* ec_add_clause_to_derives_hash |
| 3782 |
* Add a derived clause to ec_derives_hash in the given EquivalenceClass. |
| 3783 |
* |
| 3784 |
* Each clause is associated with a canonicalized key. For constant-containing |
| 3785 |
* clauses, only the non-constant EM is used for lookup; see comments in |
| 3786 |
* fill_ec_derives_key(). |
| 3787 |
*/ |
| 3788 |
static void |
| 3789 |
ec_add_clause_to_derives_hash(EquivalenceClass *ec, RestrictInfo *rinfo) |
| 3790 |
{ |
| 3791 |
ECDerivesKey key; |
| 3792 |
ECDerivesEntry *entry; |
| 3793 |
bool found; |
| 3794 |
|
| 3795 |
/* |
| 3796 |
* Constants are always placed on the RHS; see |
| 3797 |
* generate_base_implied_equalities_const(). |
| 3798 |
*/ |
| 3799 |
Assert(!rinfo->left_em->em_is_const); |
| 3800 |
|
| 3801 |
/* |
| 3802 |
* Clauses containing a constant are never considered redundant, so |
| 3803 |
* parent_ec is not set. |
| 3804 |
*/ |
| 3805 |
Assert(!rinfo->parent_ec || !rinfo->right_em->em_is_const); |
| 3806 |
|
| 3807 |
/* |
| 3808 |
* See fill_ec_derives_key() for details: we use a canonicalized key to |
| 3809 |
* avoid storing both EM orderings. For constant EMs, only the |
| 3810 |
* non-constant EM is included in the key. |
| 3811 |
*/ |
| 3812 |
fill_ec_derives_key(&key, |
| 3813 |
rinfo->left_em, |
| 3814 |
rinfo->right_em->em_is_const ? NULL : rinfo->right_em, |
| 3815 |
rinfo->parent_ec); |
| 3816 |
entry = derives_insert(ec->ec_derives_hash, key, &found); |
| 3817 |
Assert(!found); |
| 3818 |
entry->rinfo = rinfo; |
| 3819 |
} |
| 3820 |
|
| 3821 |
/* |
| 3822 |
* ec_clear_derived_clauses |
| 3823 |
* Reset ec_derives_list and ec_derives_hash. |
| 3824 |
* |
| 3825 |
* We destroy the hash table explicitly, since it may consume significant |
| 3826 |
* space. The list holds the same set of entries and can become equally large |
| 3827 |
* when thousands of partitions are involved, so we free it as well -- even |
| 3828 |
* though we do not typically free lists. |
| 3829 |
*/ |
| 3830 |
void |
| 3831 |
ec_clear_derived_clauses(EquivalenceClass *ec) |
| 3832 |
{ |
| 3833 |
list_free(ec->ec_derives_list); |
| 3834 |
ec->ec_derives_list = NIL; |
| 3835 |
|
| 3836 |
if (ec->ec_derives_hash) |
| 3837 |
{ |
| 3838 |
derives_destroy(ec->ec_derives_hash); |
| 3839 |
ec->ec_derives_hash = NULL; |
| 3840 |
} |
| 3841 |
} |
| 3842 |
|
| 3843 |
/* |
| 3844 |
* ec_search_clause_for_ems |
| 3845 |
* Search for an existing RestrictInfo that equates the given pair |
| 3846 |
* of EquivalenceMembers, either from ec_sources or ec_derives. |
| 3847 |
* |
| 3848 |
* Returns a clause with matching operands in either given order or commuted |
| 3849 |
* order. We used to require matching operator OIDs, but dropped that since any |
| 3850 |
* semantically different operator here would indicate a broken operator family. |
| 3851 |
* |
| 3852 |
* Returns NULL if no matching clause is found. |
| 3853 |
*/ |
| 3854 |
static RestrictInfo * |
| 3855 |
ec_search_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, |
| 3856 |
EquivalenceMember *leftem, EquivalenceMember *rightem, |
| 3857 |
EquivalenceClass *parent_ec) |
| 3858 |
{ |
| 3859 |
/* Check original source clauses */ |
| 3860 |
foreach_node(RestrictInfo, rinfo, ec->ec_sources) |
| 3861 |
{ |
| 3862 |
if (rinfo->left_em == leftem && |
| 3863 |
rinfo->right_em == rightem && |
| 3864 |
rinfo->parent_ec == parent_ec) |
| 3865 |
return rinfo; |
| 3866 |
if (rinfo->left_em == rightem && |
| 3867 |
rinfo->right_em == leftem && |
| 3868 |
rinfo->parent_ec == parent_ec) |
| 3869 |
return rinfo; |
| 3870 |
} |
| 3871 |
|
| 3872 |
/* Not found in ec_sources; search derived clauses */ |
| 3873 |
return ec_search_derived_clause_for_ems(root, ec, leftem, rightem, |
| 3874 |
parent_ec); |
| 3875 |
} |
| 3876 |
|
| 3877 |
/* |
| 3878 |
* ec_search_derived_clause_for_ems |
| 3879 |
* Search for an existing derived clause between two EquivalenceMembers. |
| 3880 |
* |
| 3881 |
* If the number of derived clauses exceeds a threshold, switch to hash table |
| 3882 |
* lookup; otherwise, scan ec_derives_list linearly. |
| 3883 |
* |
| 3884 |
* Clauses involving constants are looked up by passing the non-constant EM |
| 3885 |
* as leftem and setting rightem to NULL. In that case, we expect to find a |
| 3886 |
* clause with a constant on the RHS. |
| 3887 |
* |
| 3888 |
* While searching the list, we compare each given EM with both sides of each |
| 3889 |
* clause. But for hash table lookups, we construct a canonicalized key and |
| 3890 |
* perform a single lookup. |
| 3891 |
*/ |
| 3892 |
static RestrictInfo * |
| 3893 |
ec_search_derived_clause_for_ems(PlannerInfo *root, EquivalenceClass *ec, |
| 3894 |
EquivalenceMember *leftem, |
| 3895 |
EquivalenceMember *rightem, |
| 3896 |
EquivalenceClass *parent_ec) |
| 3897 |
{ |
| 3898 |
/* Switch to using hash lookup when list grows "too long". */ |
| 3899 |
if (!ec->ec_derives_hash && |
| 3900 |
list_length(ec->ec_derives_list) >= EC_DERIVES_HASH_THRESHOLD) |
| 3901 |
ec_build_derives_hash(root, ec); |
| 3902 |
|
| 3903 |
/* Perform hash table lookup if available */ |
| 3904 |
if (ec->ec_derives_hash) |
| 3905 |
{ |
| 3906 |
ECDerivesKey key; |
| 3907 |
RestrictInfo *rinfo; |
| 3908 |
ECDerivesEntry *entry; |
| 3909 |
|
| 3910 |
fill_ec_derives_key(&key, leftem, rightem, parent_ec); |
| 3911 |
entry = derives_lookup(ec->ec_derives_hash, key); |
| 3912 |
if (entry) |
| 3913 |
{ |
| 3914 |
rinfo = entry->rinfo; |
| 3915 |
Assert(rinfo); |
| 3916 |
Assert(rightem || rinfo->right_em->em_is_const); |
| 3917 |
return rinfo; |
| 3918 |
} |
| 3919 |
} |
| 3920 |
else |
| 3921 |
{ |
| 3922 |
/* Fallback to linear search over ec_derives_list */ |
| 3923 |
foreach_node(RestrictInfo, rinfo, ec->ec_derives_list) |
| 3924 |
{ |
| 3925 |
/* Handle special case: lookup by non-const EM alone */ |
| 3926 |
if (!rightem && |
| 3927 |
rinfo->left_em == leftem) |
| 3928 |
{ |
| 3929 |
Assert(rinfo->right_em->em_is_const); |
| 3930 |
return rinfo; |
| 3931 |
} |
| 3932 |
if (rinfo->left_em == leftem && |
| 3933 |
rinfo->right_em == rightem && |
| 3934 |
rinfo->parent_ec == parent_ec) |
| 3935 |
return rinfo; |
| 3936 |
if (rinfo->left_em == rightem && |
| 3937 |
rinfo->right_em == leftem && |
| 3938 |
rinfo->parent_ec == parent_ec) |
| 3939 |
return rinfo; |
| 3940 |
} |
| 3941 |
} |
| 3942 |
|
| 3943 |
return NULL; |
| 3944 |
} |