Branch data Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * dependencies.c
4 : : * POSTGRES functional dependencies
5 : : *
6 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : * IDENTIFICATION
10 : : * src/backend/statistics/dependencies.c
11 : : *
12 : : *-------------------------------------------------------------------------
13 : : */
14 : : #include "postgres.h"
15 : :
16 : : #include "access/htup_details.h"
17 : : #include "catalog/pg_statistic_ext.h"
18 : : #include "catalog/pg_statistic_ext_data.h"
19 : : #include "nodes/nodeFuncs.h"
20 : : #include "optimizer/clauses.h"
21 : : #include "optimizer/optimizer.h"
22 : : #include "parser/parsetree.h"
23 : : #include "statistics/extended_stats_internal.h"
24 : : #include "utils/fmgroids.h"
25 : : #include "utils/lsyscache.h"
26 : : #include "utils/memutils.h"
27 : : #include "utils/selfuncs.h"
28 : : #include "utils/syscache.h"
29 : : #include "utils/typcache.h"
30 : :
31 : : /* size of the struct header fields (magic, type, ndeps) */
32 : : #define SizeOfHeader (3 * sizeof(uint32))
33 : :
34 : : /* size of a serialized dependency (degree, natts, atts) */
35 : : #define SizeOfItem(natts) \
36 : : (sizeof(double) + sizeof(AttrNumber) * (1 + (natts)))
37 : :
38 : : /* minimal size of a dependency (with two attributes) */
39 : : #define MinSizeOfItem SizeOfItem(2)
40 : :
41 : : /* minimal size of dependencies, when all deps are minimal */
42 : : #define MinSizeOfItems(ndeps) \
43 : : (SizeOfHeader + (ndeps) * MinSizeOfItem)
44 : :
45 : : /*
46 : : * Internal state for DependencyGenerator of dependencies. Dependencies are similar to
47 : : * k-permutations of n elements, except that the order does not matter for the
48 : : * first (k-1) elements. That is, (a,b=>c) and (b,a=>c) are equivalent.
49 : : */
50 : : typedef struct DependencyGeneratorData
51 : : {
52 : : int k; /* size of the dependency */
53 : : int n; /* number of possible attributes */
54 : : int current; /* next dependency to return (index) */
55 : : AttrNumber ndependencies; /* number of dependencies generated */
56 : : AttrNumber *dependencies; /* array of pre-generated dependencies */
57 : : } DependencyGeneratorData;
58 : :
59 : : typedef DependencyGeneratorData *DependencyGenerator;
60 : :
61 : : static void generate_dependencies_recurse(DependencyGenerator state,
62 : : int index, AttrNumber start, AttrNumber *current);
63 : : static void generate_dependencies(DependencyGenerator state);
64 : : static DependencyGenerator DependencyGenerator_init(int n, int k);
65 : : static void DependencyGenerator_free(DependencyGenerator state);
66 : : static AttrNumber *DependencyGenerator_next(DependencyGenerator state);
67 : : static double dependency_degree(StatsBuildData *data, int k, AttrNumber *dependency);
68 : : static bool dependency_is_fully_matched(MVDependency *dependency,
69 : : Bitmapset *attnums);
70 : : static bool dependency_is_compatible_clause(Node *clause, Index relid,
71 : : AttrNumber *attnum);
72 : : static bool dependency_is_compatible_expression(Node *clause, Index relid,
73 : : List *statlist, Node **expr);
74 : : static MVDependency *find_strongest_dependency(MVDependencies **dependencies,
75 : : int ndependencies, Bitmapset *attnums);
76 : : static Selectivity clauselist_apply_dependencies(PlannerInfo *root, List *clauses,
77 : : int varRelid, JoinType jointype,
78 : : SpecialJoinInfo *sjinfo,
79 : : MVDependency **dependencies,
80 : : int ndependencies,
81 : : AttrNumber *list_attnums,
82 : : Bitmapset **estimatedclauses);
83 : :
84 : : static void
85 : 968 : generate_dependencies_recurse(DependencyGenerator state, int index,
86 : : AttrNumber start, AttrNumber *current)
87 : : {
88 : : /*
89 : : * The generator handles the first (k-1) elements differently from the
90 : : * last element.
91 : : */
92 [ + + ]: 968 : if (index < (state->k - 1))
93 : : {
94 : : AttrNumber i;
95 : :
96 : : /*
97 : : * The first (k-1) values have to be in ascending order, which we
98 : : * generate recursively.
99 : : */
100 : :
101 [ + + ]: 1188 : for (i = start; i < state->n; i++)
102 : : {
103 : 764 : current[index] = i;
104 : 764 : generate_dependencies_recurse(state, (index + 1), (i + 1), current);
105 : : }
106 : : }
107 : : else
108 : : {
109 : : int i;
110 : :
111 : : /*
112 : : * the last element is the implied value, which does not respect the
113 : : * ascending order. We just need to check that the value is not in the
114 : : * first (k-1) elements.
115 : : */
116 : :
117 [ + + ]: 2072 : for (i = 0; i < state->n; i++)
118 : : {
119 : : int j;
120 : 1528 : bool match = false;
121 : :
122 : 1528 : current[index] = i;
123 : :
124 [ + + ]: 2812 : for (j = 0; j < index; j++)
125 : : {
126 [ + + ]: 2048 : if (current[j] == i)
127 : : {
128 : 764 : match = true;
129 : 764 : break;
130 : : }
131 : : }
132 : :
133 : : /*
134 : : * If the value is not found in the first part of the dependency,
135 : : * we're done.
136 : : */
137 [ + + ]: 1528 : if (!match)
138 : : {
139 : 764 : state->dependencies = repalloc_array(state->dependencies,
140 : : AttrNumber,
141 : : state->k * (state->ndependencies + 1));
142 : 764 : memcpy(&state->dependencies[(state->k * state->ndependencies)],
143 : 764 : current, state->k * sizeof(AttrNumber));
144 : 764 : state->ndependencies++;
145 : : }
146 : : }
147 : : }
148 : 968 : }
149 : :
150 : : /* generate all dependencies (k-permutations of n elements) */
151 : : static void
152 : 204 : generate_dependencies(DependencyGenerator state)
153 : : {
154 : 204 : AttrNumber *current = palloc0_array(AttrNumber, state->k);
155 : :
156 : 204 : generate_dependencies_recurse(state, 0, 0, current);
157 : :
158 : 204 : pfree(current);
159 : 204 : }
160 : :
161 : : /*
162 : : * initialize the DependencyGenerator of variations, and prebuild the variations
163 : : *
164 : : * This pre-builds all the variations. We could also generate them in
165 : : * DependencyGenerator_next(), but this seems simpler.
166 : : */
167 : : static DependencyGenerator
168 : 204 : DependencyGenerator_init(int n, int k)
169 : : {
170 : : DependencyGenerator state;
171 : :
172 : : Assert((n >= k) && (k > 0));
173 : :
174 : : /* allocate the DependencyGenerator state */
175 : 204 : state = palloc0_object(DependencyGeneratorData);
176 : 204 : state->dependencies = palloc_array(AttrNumber, k);
177 : :
178 : 204 : state->ndependencies = 0;
179 : 204 : state->current = 0;
180 : 204 : state->k = k;
181 : 204 : state->n = n;
182 : :
183 : : /* now actually pre-generate all the variations */
184 : 204 : generate_dependencies(state);
185 : :
186 : 204 : return state;
187 : : }
188 : :
189 : : /* free the DependencyGenerator state */
190 : : static void
191 : 204 : DependencyGenerator_free(DependencyGenerator state)
192 : : {
193 : 204 : pfree(state->dependencies);
194 : 204 : pfree(state);
195 : 204 : }
196 : :
197 : : /* generate next combination */
198 : : static AttrNumber *
199 : 968 : DependencyGenerator_next(DependencyGenerator state)
200 : : {
201 [ + + ]: 968 : if (state->current == state->ndependencies)
202 : 204 : return NULL;
203 : :
204 : 764 : return &state->dependencies[state->k * state->current++];
205 : : }
206 : :
207 : :
208 : : /*
209 : : * validates functional dependency on the data
210 : : *
211 : : * An actual work horse of detecting functional dependencies. Given a variation
212 : : * of k attributes, it checks that the first (k-1) are sufficient to determine
213 : : * the last one.
214 : : */
215 : : static double
216 : 764 : dependency_degree(StatsBuildData *data, int k, AttrNumber *dependency)
217 : : {
218 : : int i,
219 : : nitems;
220 : : MultiSortSupport mss;
221 : : SortItem *items;
222 : : AttrNumber *attnums_dep;
223 : :
224 : : /* counters valid within a group */
225 : 764 : int group_size = 0;
226 : 764 : int n_violations = 0;
227 : :
228 : : /* total number of rows supporting (consistent with) the dependency */
229 : 764 : int n_supporting_rows = 0;
230 : :
231 : : /* Make sure we have at least two input attributes. */
232 : : Assert(k >= 2);
233 : :
234 : : /* sort info for all attributes columns */
235 : 764 : mss = multi_sort_init(k);
236 : :
237 : : /*
238 : : * Translate the array of indexes to regular attnums for the dependency
239 : : * (we will need this to identify the columns in StatsBuildData).
240 : : */
241 : 764 : attnums_dep = palloc_array(AttrNumber, k);
242 [ + + ]: 2560 : for (i = 0; i < k; i++)
243 : 1796 : attnums_dep[i] = data->attnums[dependency[i]];
244 : :
245 : : /*
246 : : * Verify the dependency (a,b,...)->z, using a rather simple algorithm:
247 : : *
248 : : * (a) sort the data lexicographically
249 : : *
250 : : * (b) split the data into groups by first (k-1) columns
251 : : *
252 : : * (c) for each group count different values in the last column
253 : : *
254 : : * We use the column data types' default sort operators and collations;
255 : : * perhaps at some point it'd be worth using column-specific collations?
256 : : */
257 : :
258 : : /* prepare the sort function for the dimensions */
259 [ + + ]: 2560 : for (i = 0; i < k; i++)
260 : : {
261 : 1796 : VacAttrStats *colstat = data->stats[dependency[i]];
262 : : TypeCacheEntry *type;
263 : :
264 : 1796 : type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR);
265 [ - + ]: 1796 : if (type->lt_opr == InvalidOid) /* shouldn't happen */
266 [ # # ]: 0 : elog(ERROR, "cache lookup failed for ordering operator for type %u",
267 : : colstat->attrtypid);
268 : :
269 : : /* prepare the sort function for this dimension */
270 : 1796 : multi_sort_add_dimension(mss, i, type->lt_opr, colstat->attrcollid);
271 : : }
272 : :
273 : : /*
274 : : * build an array of SortItem(s) sorted using the multi-sort support
275 : : *
276 : : * XXX This relies on all stats entries pointing to the same tuple
277 : : * descriptor. For now that assumption holds, but it might change in the
278 : : * future for example if we support statistics on multiple tables.
279 : : */
280 : 764 : items = build_sorted_items(data, &nitems, mss, k, attnums_dep);
281 : :
282 : : /*
283 : : * Walk through the sorted array, split it into rows according to the
284 : : * first (k-1) columns. If there's a single value in the last column, we
285 : : * count the group as 'supporting' the functional dependency. Otherwise we
286 : : * count it as contradicting.
287 : : */
288 : :
289 : : /* start with the first row forming a group */
290 : 764 : group_size = 1;
291 : :
292 : : /* loop 1 beyond the end of the array so that we count the final group */
293 [ + + ]: 1006818 : for (i = 1; i <= nitems; i++)
294 : : {
295 : : /*
296 : : * Check if the group ended, which may be either because we processed
297 : : * all the items (i==nitems), or because the i-th item is not equal to
298 : : * the preceding one.
299 : : */
300 [ + + + + ]: 2011344 : if (i == nitems ||
301 : 1005290 : multi_sort_compare_dims(0, k - 2, &items[i - 1], &items[i], mss) != 0)
302 : : {
303 : : /*
304 : : * If no violations were found in the group then track the rows of
305 : : * the group as supporting the functional dependency.
306 : : */
307 [ + + ]: 23472 : if (n_violations == 0)
308 : 14896 : n_supporting_rows += group_size;
309 : :
310 : : /* Reset counters for the new group */
311 : 23472 : n_violations = 0;
312 : 23472 : group_size = 1;
313 : 23472 : continue;
314 : : }
315 : : /* first columns match, but the last one does not (so contradicting) */
316 [ + + ]: 982582 : else if (multi_sort_compare_dim(k - 1, &items[i - 1], &items[i], mss) != 0)
317 : 40644 : n_violations++;
318 : :
319 : 982582 : group_size++;
320 : : }
321 : :
322 : : /* Compute the 'degree of validity' as (supporting/total). */
323 : 764 : return (n_supporting_rows * 1.0 / data->numrows);
324 : : }
325 : :
326 : : /*
327 : : * detects functional dependencies between groups of columns
328 : : *
329 : : * Generates all possible subsets of columns (variations) and computes
330 : : * the degree of validity for each one. For example when creating statistics
331 : : * on three columns (a,b,c) there are 9 possible dependencies
332 : : *
333 : : * two columns three columns
334 : : * ----------- -------------
335 : : * (a) -> b (a,b) -> c
336 : : * (a) -> c (a,c) -> b
337 : : * (b) -> a (b,c) -> a
338 : : * (b) -> c
339 : : * (c) -> a
340 : : * (c) -> b
341 : : */
342 : : MVDependencies *
343 : 152 : statext_dependencies_build(StatsBuildData *data)
344 : : {
345 : : int i,
346 : : k;
347 : :
348 : : /* result */
349 : 152 : MVDependencies *dependencies = NULL;
350 : : MemoryContext cxt;
351 : :
352 : : Assert(data->nattnums >= 2);
353 : :
354 : : /* tracks memory allocated by dependency_degree calls */
355 : 152 : cxt = AllocSetContextCreate(CurrentMemoryContext,
356 : : "dependency_degree cxt",
357 : : ALLOCSET_DEFAULT_SIZES);
358 : :
359 : : /*
360 : : * We'll try build functional dependencies starting from the smallest ones
361 : : * covering just 2 columns, to the largest ones, covering all columns
362 : : * included in the statistics object. We start from the smallest ones
363 : : * because we want to be able to skip already implied ones.
364 : : */
365 [ + + ]: 356 : for (k = 2; k <= data->nattnums; k++)
366 : : {
367 : : AttrNumber *dependency; /* array with k elements */
368 : :
369 : : /* prepare a DependencyGenerator of variation */
370 : 204 : DependencyGenerator DependencyGenerator = DependencyGenerator_init(data->nattnums, k);
371 : :
372 : : /* generate all possible variations of k values (out of n) */
373 [ + + ]: 968 : while ((dependency = DependencyGenerator_next(DependencyGenerator)))
374 : : {
375 : : double degree;
376 : : MVDependency *d;
377 : : MemoryContext oldcxt;
378 : :
379 : : /* release memory used by dependency degree calculation */
380 : 764 : oldcxt = MemoryContextSwitchTo(cxt);
381 : :
382 : : /* compute how valid the dependency seems */
383 : 764 : degree = dependency_degree(data, k, dependency);
384 : :
385 : 764 : MemoryContextSwitchTo(oldcxt);
386 : 764 : MemoryContextReset(cxt);
387 : :
388 : : /*
389 : : * if the dependency seems entirely invalid, don't store it
390 : : */
391 [ + + ]: 764 : if (degree == 0.0)
392 : 186 : continue;
393 : :
394 : 578 : d = (MVDependency *) palloc0(offsetof(MVDependency, attributes)
395 : 578 : + k * sizeof(AttrNumber));
396 : :
397 : : /* copy the dependency (and keep the indexes into stxkeys) */
398 : 578 : d->degree = degree;
399 : 578 : d->nattributes = k;
400 [ + + ]: 1954 : for (i = 0; i < k; i++)
401 : 1376 : d->attributes[i] = data->attnums[dependency[i]];
402 : :
403 : : /* initialize the list of dependencies */
404 [ + + ]: 578 : if (dependencies == NULL)
405 : : {
406 : 140 : dependencies = palloc0_object(MVDependencies);
407 : :
408 : 140 : dependencies->magic = STATS_DEPS_MAGIC;
409 : 140 : dependencies->type = STATS_DEPS_TYPE_BASIC;
410 : 140 : dependencies->ndeps = 0;
411 : : }
412 : :
413 : 578 : dependencies->ndeps++;
414 : 578 : dependencies = (MVDependencies *) repalloc(dependencies,
415 : : offsetof(MVDependencies, deps)
416 : 578 : + dependencies->ndeps * sizeof(MVDependency *));
417 : :
418 : 578 : dependencies->deps[dependencies->ndeps - 1] = d;
419 : : }
420 : :
421 : : /*
422 : : * we're done with variations of k elements, so free the
423 : : * DependencyGenerator
424 : : */
425 : 204 : DependencyGenerator_free(DependencyGenerator);
426 : : }
427 : :
428 : 152 : MemoryContextDelete(cxt);
429 : :
430 : 152 : return dependencies;
431 : : }
432 : :
433 : :
434 : : /*
435 : : * Serialize list of dependencies into a bytea value.
436 : : */
437 : : bytea *
438 : 193 : statext_dependencies_serialize(MVDependencies *dependencies)
439 : : {
440 : : bytea *output;
441 : : char *tmp;
442 : : Size len;
443 : :
444 : : /* we need to store ndeps, with a number of attributes for each one */
445 : 193 : len = VARHDRSZ + SizeOfHeader;
446 : :
447 : : /* and also include space for the actual attribute numbers and degrees */
448 [ + + ]: 908 : for (uint32 i = 0; i < dependencies->ndeps; i++)
449 : 715 : len += SizeOfItem(dependencies->deps[i]->nattributes);
450 : :
451 : 193 : output = (bytea *) palloc0(len);
452 : 193 : SET_VARSIZE(output, len);
453 : :
454 : 193 : tmp = VARDATA(output);
455 : :
456 : : /* Store the base struct values (magic, type, ndeps) */
457 : 193 : memcpy(tmp, &dependencies->magic, sizeof(uint32));
458 : 193 : tmp += sizeof(uint32);
459 : 193 : memcpy(tmp, &dependencies->type, sizeof(uint32));
460 : 193 : tmp += sizeof(uint32);
461 : 193 : memcpy(tmp, &dependencies->ndeps, sizeof(uint32));
462 : 193 : tmp += sizeof(uint32);
463 : :
464 : : /* store number of attributes and attribute numbers for each dependency */
465 [ + + ]: 908 : for (uint32 i = 0; i < dependencies->ndeps; i++)
466 : : {
467 : 715 : MVDependency *d = dependencies->deps[i];
468 : :
469 : 715 : memcpy(tmp, &d->degree, sizeof(double));
470 : 715 : tmp += sizeof(double);
471 : :
472 : 715 : memcpy(tmp, &d->nattributes, sizeof(AttrNumber));
473 : 715 : tmp += sizeof(AttrNumber);
474 : :
475 : 715 : memcpy(tmp, d->attributes, sizeof(AttrNumber) * d->nattributes);
476 : 715 : tmp += sizeof(AttrNumber) * d->nattributes;
477 : :
478 : : /* protect against overflow */
479 : : Assert(tmp <= ((char *) output + len));
480 : : }
481 : :
482 : : /* make sure we've produced exactly the right amount of data */
483 : : Assert(tmp == ((char *) output + len));
484 : :
485 : 193 : return output;
486 : : }
487 : :
488 : : /*
489 : : * Reads serialized dependencies into MVDependencies structure.
490 : : */
491 : : MVDependencies *
492 : 1452 : statext_dependencies_deserialize(bytea *data)
493 : : {
494 : : Size min_expected_size;
495 : : MVDependencies *dependencies;
496 : : char *tmp;
497 : :
498 [ - + ]: 1452 : if (data == NULL)
499 : 0 : return NULL;
500 : :
501 [ - + ]: 1452 : if (VARSIZE_ANY_EXHDR(data) < SizeOfHeader)
502 [ # # ]: 0 : elog(ERROR, "invalid MVDependencies size %zu (expected at least %zu)",
503 : : VARSIZE_ANY_EXHDR(data), SizeOfHeader);
504 : :
505 : : /* read the MVDependencies header */
506 : 1452 : dependencies = palloc0_object(MVDependencies);
507 : :
508 : : /* initialize pointer to the data part (skip the varlena header) */
509 : 1452 : tmp = VARDATA_ANY(data);
510 : :
511 : : /* read the header fields and perform basic sanity checks */
512 : 1452 : memcpy(&dependencies->magic, tmp, sizeof(uint32));
513 : 1452 : tmp += sizeof(uint32);
514 : 1452 : memcpy(&dependencies->type, tmp, sizeof(uint32));
515 : 1452 : tmp += sizeof(uint32);
516 : 1452 : memcpy(&dependencies->ndeps, tmp, sizeof(uint32));
517 : 1452 : tmp += sizeof(uint32);
518 : :
519 [ - + ]: 1452 : if (dependencies->magic != STATS_DEPS_MAGIC)
520 [ # # ]: 0 : elog(ERROR, "invalid dependency magic %d (expected %d)",
521 : : dependencies->magic, STATS_DEPS_MAGIC);
522 : :
523 [ - + ]: 1452 : if (dependencies->type != STATS_DEPS_TYPE_BASIC)
524 [ # # ]: 0 : elog(ERROR, "invalid dependency type %d (expected %d)",
525 : : dependencies->type, STATS_DEPS_TYPE_BASIC);
526 : :
527 [ - + ]: 1452 : if (dependencies->ndeps == 0)
528 [ # # ]: 0 : elog(ERROR, "invalid zero-length item array in MVDependencies");
529 : :
530 : : /* what minimum bytea size do we expect for those parameters */
531 : 1452 : min_expected_size = MinSizeOfItems(dependencies->ndeps);
532 : :
533 [ - + ]: 1452 : if (VARSIZE_ANY_EXHDR(data) < min_expected_size)
534 [ # # ]: 0 : elog(ERROR, "invalid dependencies size %zu (expected at least %zu)",
535 : : VARSIZE_ANY_EXHDR(data), min_expected_size);
536 : :
537 : : /* allocate space for the MCV items */
538 : 1452 : dependencies = repalloc(dependencies, offsetof(MVDependencies, deps)
539 : 1452 : + (dependencies->ndeps * sizeof(MVDependency *)));
540 : :
541 [ + + ]: 8435 : for (uint32 i = 0; i < dependencies->ndeps; i++)
542 : : {
543 : : double degree;
544 : : AttrNumber k;
545 : : MVDependency *d;
546 : :
547 : : /* degree of validity */
548 : 6983 : memcpy(°ree, tmp, sizeof(double));
549 : 6983 : tmp += sizeof(double);
550 : :
551 : : /* number of attributes */
552 : 6983 : memcpy(&k, tmp, sizeof(AttrNumber));
553 : 6983 : tmp += sizeof(AttrNumber);
554 : :
555 : : /* is the number of attributes valid? */
556 : : Assert((k >= 2) && (k <= STATS_MAX_DIMENSIONS));
557 : :
558 : : /* now that we know the number of attributes, allocate the dependency */
559 : 6983 : d = (MVDependency *) palloc0(offsetof(MVDependency, attributes)
560 : 6983 : + (k * sizeof(AttrNumber)));
561 : :
562 : 6983 : d->degree = degree;
563 : 6983 : d->nattributes = k;
564 : :
565 : : /* copy attribute numbers */
566 : 6983 : memcpy(d->attributes, tmp, sizeof(AttrNumber) * d->nattributes);
567 : 6983 : tmp += sizeof(AttrNumber) * d->nattributes;
568 : :
569 : 6983 : dependencies->deps[i] = d;
570 : :
571 : : /* still within the bytea */
572 : : Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
573 : : }
574 : :
575 : : /* we should have consumed the whole bytea exactly */
576 : : Assert(tmp == ((char *) data + VARSIZE_ANY(data)));
577 : :
578 : 1452 : return dependencies;
579 : : }
580 : :
581 : : /*
582 : : * Free allocations of a MVDependencies.
583 : : */
584 : : void
585 : 29 : statext_dependencies_free(MVDependencies *dependencies)
586 : : {
587 [ + + ]: 234 : for (uint32 i = 0; i < dependencies->ndeps; i++)
588 : 205 : pfree(dependencies->deps[i]);
589 : 29 : pfree(dependencies);
590 : 29 : }
591 : :
592 : : /*
593 : : * Validate a set of MVDependencies against the extended statistics object
594 : : * definition.
595 : : *
596 : : * Every MVDependencies must be checked to ensure that the attnums in the
597 : : * attributes list correspond to attnums/expressions defined by the
598 : : * extended statistics object.
599 : : *
600 : : * Positive attnums are attributes which must be found in the stxkeys, while
601 : : * negative attnums correspond to an expression number, no attribute number
602 : : * can be below (0 - numexprs).
603 : : */
604 : : bool
605 : 29 : statext_dependencies_validate(const MVDependencies *dependencies,
606 : : const int2vector *stxkeys,
607 : : int numexprs, int elevel)
608 : : {
609 : 29 : int attnum_expr_lowbound = 0 - numexprs;
610 : :
611 : : /* Scan through each dependency entry */
612 [ + + ]: 218 : for (uint32 i = 0; i < dependencies->ndeps; i++)
613 : : {
614 : 197 : const MVDependency *dep = dependencies->deps[i];
615 : :
616 : : /*
617 : : * Cross-check each attribute in a dependency entry with the extended
618 : : * stats object definition.
619 : : */
620 [ + + ]: 685 : for (int j = 0; j < dep->nattributes; j++)
621 : : {
622 : 496 : AttrNumber attnum = dep->attributes[j];
623 : 496 : bool ok = false;
624 : :
625 [ + + ]: 496 : if (attnum > 0)
626 : : {
627 : : /* attribute number in stxkeys */
628 [ + + ]: 404 : for (int k = 0; k < stxkeys->dim1; k++)
629 : : {
630 [ + + ]: 396 : if (attnum == stxkeys->values[k])
631 : : {
632 : 256 : ok = true;
633 : 256 : break;
634 : : }
635 : : }
636 : : }
637 [ + - + - ]: 232 : else if ((attnum < 0) && (attnum >= attnum_expr_lowbound))
638 : : {
639 : : /* attribute number for an expression */
640 : 232 : ok = true;
641 : : }
642 : :
643 [ + + ]: 496 : if (!ok)
644 : : {
645 [ + - ]: 8 : ereport(elevel,
646 : : (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
647 : : errmsg("could not validate \"%s\" object: invalid attribute number %d found",
648 : : "pg_dependencies", attnum)));
649 : 8 : return false;
650 : : }
651 : : }
652 : : }
653 : :
654 : 21 : return true;
655 : : }
656 : :
657 : : /*
658 : : * dependency_is_fully_matched
659 : : * checks that a functional dependency is fully matched given clauses on
660 : : * attributes (assuming the clauses are suitable equality clauses)
661 : : */
662 : : static bool
663 : 5130 : dependency_is_fully_matched(MVDependency *dependency, Bitmapset *attnums)
664 : : {
665 : : int j;
666 : :
667 : : /*
668 : : * Check that the dependency actually is fully covered by clauses. We have
669 : : * to translate all attribute numbers, as those are referenced
670 : : */
671 [ + + ]: 13035 : for (j = 0; j < dependency->nattributes; j++)
672 : : {
673 : 10465 : int attnum = dependency->attributes[j];
674 : :
675 [ + + ]: 10465 : if (!bms_is_member(attnum, attnums))
676 : 2560 : return false;
677 : : }
678 : :
679 : 2570 : return true;
680 : : }
681 : :
682 : : /*
683 : : * statext_dependencies_load
684 : : * Load the functional dependencies for the indicated pg_statistic_ext tuple
685 : : */
686 : : MVDependencies *
687 : 1340 : statext_dependencies_load(Oid mvoid, bool inh)
688 : : {
689 : : MVDependencies *result;
690 : : bool isnull;
691 : : Datum deps;
692 : : HeapTuple htup;
693 : :
694 : 1340 : htup = SearchSysCache2(STATEXTDATASTXOID,
695 : : ObjectIdGetDatum(mvoid),
696 : : BoolGetDatum(inh));
697 [ - + ]: 1340 : if (!HeapTupleIsValid(htup))
698 [ # # ]: 0 : elog(ERROR, "cache lookup failed for statistics object %u", mvoid);
699 : :
700 : 1340 : deps = SysCacheGetAttr(STATEXTDATASTXOID, htup,
701 : : Anum_pg_statistic_ext_data_stxddependencies, &isnull);
702 [ - + ]: 1340 : if (isnull)
703 [ # # ]: 0 : elog(ERROR,
704 : : "requested statistics kind \"%c\" is not yet built for statistics object %u",
705 : : STATS_EXT_DEPENDENCIES, mvoid);
706 : :
707 : 1340 : result = statext_dependencies_deserialize(DatumGetByteaPP(deps));
708 : :
709 : 1340 : ReleaseSysCache(htup);
710 : :
711 : 1340 : return result;
712 : : }
713 : :
714 : : /*
715 : : * dependency_is_compatible_clause
716 : : * Determines if the clause is compatible with functional dependencies
717 : : *
718 : : * Only clauses that have the form of equality to a pseudoconstant, or can be
719 : : * interpreted that way, are currently accepted. Furthermore the variable
720 : : * part of the clause must be a simple Var belonging to the specified
721 : : * relation, whose attribute number we return in *attnum on success.
722 : : */
723 : : static bool
724 : 3300 : dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
725 : : {
726 : : Var *var;
727 : : Node *clause_expr;
728 : :
729 [ + + ]: 3300 : if (IsA(clause, RestrictInfo))
730 : : {
731 : 3200 : RestrictInfo *rinfo = (RestrictInfo *) clause;
732 : :
733 : : /* Pseudoconstants are not interesting (they couldn't contain a Var) */
734 [ + + ]: 3200 : if (rinfo->pseudoconstant)
735 : 5 : return false;
736 : :
737 : : /* Clauses referencing multiple, or no, varnos are incompatible */
738 [ - + ]: 3195 : if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
739 : 0 : return false;
740 : :
741 : 3195 : clause = (Node *) rinfo->clause;
742 : : }
743 : :
744 [ + + ]: 3295 : if (is_opclause(clause))
745 : : {
746 : : /* If it's an opclause, check for Var = Const or Const = Var. */
747 : 1205 : OpExpr *expr = (OpExpr *) clause;
748 : :
749 : : /* Only expressions with two arguments are candidates. */
750 [ - + ]: 1205 : if (list_length(expr->args) != 2)
751 : 0 : return false;
752 : :
753 : : /* Make sure non-selected argument is a pseudoconstant. */
754 [ + - ]: 1205 : if (is_pseudo_constant_clause(lsecond(expr->args)))
755 : 1205 : clause_expr = linitial(expr->args);
756 [ # # ]: 0 : else if (is_pseudo_constant_clause(linitial(expr->args)))
757 : 0 : clause_expr = lsecond(expr->args);
758 : : else
759 : 0 : return false;
760 : :
761 : : /*
762 : : * If it's not an "=" operator, just ignore the clause, as it's not
763 : : * compatible with functional dependencies.
764 : : *
765 : : * This uses the function for estimating selectivity, not the operator
766 : : * directly (a bit awkward, but well ...).
767 : : *
768 : : * XXX this is pretty dubious; probably it'd be better to check btree
769 : : * or hash opclass membership, so as not to be fooled by custom
770 : : * selectivity functions, and to be more consistent with decisions
771 : : * elsewhere in the planner.
772 : : */
773 [ + + ]: 1205 : if (get_oprrest(expr->opno) != F_EQSEL)
774 : 30 : return false;
775 : :
776 : : /* OK to proceed with checking "var" */
777 : : }
778 [ + + ]: 2090 : else if (IsA(clause, ScalarArrayOpExpr))
779 : : {
780 : : /* If it's a scalar array operator, check for Var IN Const. */
781 : 2030 : ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
782 : :
783 : : /*
784 : : * Reject ALL() variant, we only care about ANY/IN.
785 : : *
786 : : * XXX Maybe we should check if all the values are the same, and allow
787 : : * ALL in that case? Doesn't seem very practical, though.
788 : : */
789 [ + + ]: 2030 : if (!expr->useOr)
790 : 30 : return false;
791 : :
792 : : /* Only expressions with two arguments are candidates. */
793 [ - + ]: 2000 : if (list_length(expr->args) != 2)
794 : 0 : return false;
795 : :
796 : : /*
797 : : * We know it's always (Var IN Const), so we assume the var is the
798 : : * first argument, and pseudoconstant is the second one.
799 : : */
800 [ - + ]: 2000 : if (!is_pseudo_constant_clause(lsecond(expr->args)))
801 : 0 : return false;
802 : :
803 : 2000 : clause_expr = linitial(expr->args);
804 : :
805 : : /*
806 : : * If it's not an "=" operator, just ignore the clause, as it's not
807 : : * compatible with functional dependencies. The operator is identified
808 : : * simply by looking at which function it uses to estimate
809 : : * selectivity. That's a bit strange, but it's what other similar
810 : : * places do.
811 : : */
812 [ + + ]: 2000 : if (get_oprrest(expr->opno) != F_EQSEL)
813 : 150 : return false;
814 : :
815 : : /* OK to proceed with checking "var" */
816 : : }
817 [ + - ]: 60 : else if (is_orclause(clause))
818 : : {
819 : 60 : BoolExpr *bool_expr = (BoolExpr *) clause;
820 : : ListCell *lc;
821 : :
822 : : /* start with no attribute number */
823 : 60 : *attnum = InvalidAttrNumber;
824 : :
825 [ + - + + : 125 : foreach(lc, bool_expr->args)
+ + ]
826 : : {
827 : : AttrNumber clause_attnum;
828 : :
829 : : /*
830 : : * Had we found incompatible clause in the arguments, treat the
831 : : * whole clause as incompatible.
832 : : */
833 [ + + ]: 100 : if (!dependency_is_compatible_clause((Node *) lfirst(lc),
834 : : relid, &clause_attnum))
835 : 35 : return false;
836 : :
837 [ + + ]: 70 : if (*attnum == InvalidAttrNumber)
838 : 30 : *attnum = clause_attnum;
839 : :
840 : : /* ensure all the variables are the same (same attnum) */
841 [ + + ]: 70 : if (*attnum != clause_attnum)
842 : 5 : return false;
843 : : }
844 : :
845 : : /* the Var is already checked by the recursive call */
846 : 25 : return true;
847 : : }
848 [ # # ]: 0 : else if (is_notclause(clause))
849 : : {
850 : : /*
851 : : * "NOT x" can be interpreted as "x = false", so get the argument and
852 : : * proceed with seeing if it's a suitable Var.
853 : : */
854 : 0 : clause_expr = (Node *) get_notclausearg(clause);
855 : : }
856 : : else
857 : : {
858 : : /*
859 : : * A boolean expression "x" can be interpreted as "x = true", so
860 : : * proceed with seeing if it's a suitable Var.
861 : : */
862 : 0 : clause_expr = clause;
863 : : }
864 : :
865 : : /*
866 : : * We may ignore any RelabelType node above the operand. (There won't be
867 : : * more than one, since eval_const_expressions has been applied already.)
868 : : */
869 [ - + ]: 3025 : if (IsA(clause_expr, RelabelType))
870 : 0 : clause_expr = (Node *) ((RelabelType *) clause_expr)->arg;
871 : :
872 : : /* We only support plain Vars for now */
873 [ + + ]: 3025 : if (!IsA(clause_expr, Var))
874 : 240 : return false;
875 : :
876 : : /* OK, we know we have a Var */
877 : 2785 : var = (Var *) clause_expr;
878 : :
879 : : /* Ensure Var is from the correct relation */
880 [ - + ]: 2785 : if (var->varno != relid)
881 : 0 : return false;
882 : :
883 : : /* We also better ensure the Var is from the current level */
884 [ - + ]: 2785 : if (var->varlevelsup != 0)
885 : 0 : return false;
886 : :
887 : : /* Also ignore system attributes (we don't allow stats on those) */
888 [ - + ]: 2785 : if (!AttrNumberIsForUserDefinedAttr(var->varattno))
889 : 0 : return false;
890 : :
891 : 2785 : *attnum = var->varattno;
892 : 2785 : return true;
893 : : }
894 : :
895 : : /*
896 : : * find_strongest_dependency
897 : : * find the strongest dependency on the attributes
898 : : *
899 : : * When applying functional dependencies, we start with the strongest
900 : : * dependencies. That is, we select the dependency that:
901 : : *
902 : : * (a) has all attributes covered by equality clauses
903 : : *
904 : : * (b) has the most attributes
905 : : *
906 : : * (c) has the highest degree of validity
907 : : *
908 : : * This guarantees that we eliminate the most redundant conditions first
909 : : * (see the comment in dependencies_clauselist_selectivity).
910 : : */
911 : : static MVDependency *
912 : 2905 : find_strongest_dependency(MVDependencies **dependencies, int ndependencies,
913 : : Bitmapset *attnums)
914 : : {
915 : 2905 : MVDependency *strongest = NULL;
916 : :
917 : : /* number of attnums in clauses */
918 : 2905 : int nattnums = bms_num_members(attnums);
919 : :
920 : : /*
921 : : * Iterate over the MVDependency items and find the strongest one from the
922 : : * fully-matched dependencies. We do the cheap checks first, before
923 : : * matching it against the attnums.
924 : : */
925 [ + + ]: 5840 : for (int i = 0; i < ndependencies; i++)
926 : : {
927 [ + + ]: 16900 : for (uint32 j = 0; j < dependencies[i]->ndeps; j++)
928 : : {
929 : 13965 : MVDependency *dependency = dependencies[i]->deps[j];
930 : :
931 : : /*
932 : : * Skip dependencies referencing more attributes than available
933 : : * clauses, as those can't be fully matched.
934 : : */
935 [ + + ]: 13965 : if (dependency->nattributes > nattnums)
936 : 8835 : continue;
937 : :
938 [ + + ]: 5130 : if (strongest)
939 : : {
940 : : /* skip dependencies on fewer attributes than the strongest. */
941 [ - + ]: 3280 : if (dependency->nattributes < strongest->nattributes)
942 : 0 : continue;
943 : :
944 : : /* also skip weaker dependencies when attribute count matches */
945 [ + + ]: 3280 : if (strongest->nattributes == dependency->nattributes &&
946 [ - + ]: 3045 : strongest->degree > dependency->degree)
947 : 0 : continue;
948 : : }
949 : :
950 : : /*
951 : : * this dependency is stronger, but we must still check that it's
952 : : * fully matched to these attnums. We perform this check last as
953 : : * it's slightly more expensive than the previous checks.
954 : : */
955 [ + + ]: 5130 : if (dependency_is_fully_matched(dependency, attnums))
956 : 2570 : strongest = dependency; /* save new best match */
957 : : }
958 : : }
959 : :
960 : 2905 : return strongest;
961 : : }
962 : :
963 : : /*
964 : : * clauselist_apply_dependencies
965 : : * Apply the specified functional dependencies to a list of clauses and
966 : : * return the estimated selectivity of the clauses that are compatible
967 : : * with any of the given dependencies.
968 : : *
969 : : * This will estimate all not-already-estimated clauses that are compatible
970 : : * with functional dependencies, and which have an attribute mentioned by any
971 : : * of the given dependencies (either as an implying or implied attribute).
972 : : *
973 : : * Given (lists of) clauses on attributes (a,b) and a functional dependency
974 : : * (a=>b), the per-column selectivities P(a) and P(b) are notionally combined
975 : : * using the formula
976 : : *
977 : : * P(a,b) = f * P(a) + (1-f) * P(a) * P(b)
978 : : *
979 : : * where 'f' is the degree of dependency. This reflects the fact that we
980 : : * expect a fraction f of all rows to be consistent with the dependency
981 : : * (a=>b), and so have a selectivity of P(a), while the remaining rows are
982 : : * treated as independent.
983 : : *
984 : : * In practice, we use a slightly modified version of this formula, which uses
985 : : * a selectivity of Min(P(a), P(b)) for the dependent rows, since the result
986 : : * should obviously not exceed either column's individual selectivity. I.e.,
987 : : * we actually combine selectivities using the formula
988 : : *
989 : : * P(a,b) = f * Min(P(a), P(b)) + (1-f) * P(a) * P(b)
990 : : *
991 : : * This can make quite a difference if the specific values matching the
992 : : * clauses are not consistent with the functional dependency.
993 : : */
994 : : static Selectivity
995 : 1330 : clauselist_apply_dependencies(PlannerInfo *root, List *clauses,
996 : : int varRelid, JoinType jointype,
997 : : SpecialJoinInfo *sjinfo,
998 : : MVDependency **dependencies, int ndependencies,
999 : : AttrNumber *list_attnums,
1000 : : Bitmapset **estimatedclauses)
1001 : : {
1002 : : Bitmapset *attnums;
1003 : : int i;
1004 : : int j;
1005 : : int nattrs;
1006 : : Selectivity *attr_sel;
1007 : : int attidx;
1008 : : int listidx;
1009 : : ListCell *l;
1010 : : Selectivity s1;
1011 : :
1012 : : /*
1013 : : * Extract the attnums of all implying and implied attributes from all the
1014 : : * given dependencies. Each of these attributes is expected to have at
1015 : : * least 1 not-already-estimated compatible clause that we will estimate
1016 : : * here.
1017 : : */
1018 : 1330 : attnums = NULL;
1019 [ + + ]: 2905 : for (i = 0; i < ndependencies; i++)
1020 : : {
1021 [ + + ]: 4960 : for (j = 0; j < dependencies[i]->nattributes; j++)
1022 : : {
1023 : 3385 : AttrNumber attnum = dependencies[i]->attributes[j];
1024 : :
1025 : 3385 : attnums = bms_add_member(attnums, attnum);
1026 : : }
1027 : : }
1028 : :
1029 : : /*
1030 : : * Compute per-column selectivity estimates for each of these attributes,
1031 : : * and mark all the corresponding clauses as estimated.
1032 : : */
1033 : 1330 : nattrs = bms_num_members(attnums);
1034 : 1330 : attr_sel = palloc_array(Selectivity, nattrs);
1035 : :
1036 : 1330 : attidx = 0;
1037 : 1330 : i = -1;
1038 [ + + ]: 4245 : while ((i = bms_next_member(attnums, i)) >= 0)
1039 : : {
1040 : 2915 : List *attr_clauses = NIL;
1041 : : Selectivity simple_sel;
1042 : :
1043 : 2915 : listidx = -1;
1044 [ + - + + : 9530 : foreach(l, clauses)
+ + ]
1045 : : {
1046 : 6615 : Node *clause = (Node *) lfirst(l);
1047 : :
1048 : 6615 : listidx++;
1049 [ + + ]: 6615 : if (list_attnums[listidx] == i)
1050 : : {
1051 : 2915 : attr_clauses = lappend(attr_clauses, clause);
1052 : 2915 : *estimatedclauses = bms_add_member(*estimatedclauses, listidx);
1053 : : }
1054 : : }
1055 : :
1056 : 2915 : simple_sel = clauselist_selectivity_ext(root, attr_clauses, varRelid,
1057 : : jointype, sjinfo, false);
1058 : 2915 : attr_sel[attidx++] = simple_sel;
1059 : : }
1060 : :
1061 : : /*
1062 : : * Now combine these selectivities using the dependency information. For
1063 : : * chains of dependencies such as a -> b -> c, the b -> c dependency will
1064 : : * come before the a -> b dependency in the array, so we traverse the
1065 : : * array backwards to ensure such chains are computed in the right order.
1066 : : *
1067 : : * As explained above, pairs of selectivities are combined using the
1068 : : * formula
1069 : : *
1070 : : * P(a,b) = f * Min(P(a), P(b)) + (1-f) * P(a) * P(b)
1071 : : *
1072 : : * to ensure that the combined selectivity is never greater than either
1073 : : * individual selectivity.
1074 : : *
1075 : : * Where multiple dependencies apply (e.g., a -> b -> c), we use
1076 : : * conditional probabilities to compute the overall result as follows:
1077 : : *
1078 : : * P(a,b,c) = P(c|a,b) * P(a,b) = P(c|a,b) * P(b|a) * P(a)
1079 : : *
1080 : : * so we replace the selectivities of all implied attributes with
1081 : : * conditional probabilities, that are conditional on all their implying
1082 : : * attributes. The selectivities of all other non-implied attributes are
1083 : : * left as they are.
1084 : : */
1085 [ + + ]: 2905 : for (i = ndependencies - 1; i >= 0; i--)
1086 : : {
1087 : 1575 : MVDependency *dependency = dependencies[i];
1088 : : AttrNumber attnum;
1089 : : Selectivity s2;
1090 : : double f;
1091 : :
1092 : : /* Selectivity of all the implying attributes */
1093 : 1575 : s1 = 1.0;
1094 [ + + ]: 3385 : for (j = 0; j < dependency->nattributes - 1; j++)
1095 : : {
1096 : 1810 : attnum = dependency->attributes[j];
1097 : 1810 : attidx = bms_member_index(attnums, attnum);
1098 : 1810 : s1 *= attr_sel[attidx];
1099 : : }
1100 : :
1101 : : /* Original selectivity of the implied attribute */
1102 : 1575 : attnum = dependency->attributes[j];
1103 : 1575 : attidx = bms_member_index(attnums, attnum);
1104 : 1575 : s2 = attr_sel[attidx];
1105 : :
1106 : : /*
1107 : : * Replace s2 with the conditional probability s2 given s1, computed
1108 : : * using the formula P(b|a) = P(a,b) / P(a), which simplifies to
1109 : : *
1110 : : * P(b|a) = f * Min(P(a), P(b)) / P(a) + (1-f) * P(b)
1111 : : *
1112 : : * where P(a) = s1, the selectivity of the implying attributes, and
1113 : : * P(b) = s2, the selectivity of the implied attribute.
1114 : : */
1115 : 1575 : f = dependency->degree;
1116 : :
1117 [ + + ]: 1575 : if (s1 <= s2)
1118 : 1485 : attr_sel[attidx] = f + (1 - f) * s2;
1119 : : else
1120 : 90 : attr_sel[attidx] = f * s2 / s1 + (1 - f) * s2;
1121 : : }
1122 : :
1123 : : /*
1124 : : * The overall selectivity of all the clauses on all these attributes is
1125 : : * then the product of all the original (non-implied) probabilities and
1126 : : * the new conditional (implied) probabilities.
1127 : : */
1128 : 1330 : s1 = 1.0;
1129 [ + + ]: 4245 : for (i = 0; i < nattrs; i++)
1130 : 2915 : s1 *= attr_sel[i];
1131 : :
1132 [ - + - + ]: 1330 : CLAMP_PROBABILITY(s1);
1133 : :
1134 : 1330 : pfree(attr_sel);
1135 : 1330 : bms_free(attnums);
1136 : :
1137 : 1330 : return s1;
1138 : : }
1139 : :
1140 : : /*
1141 : : * dependency_is_compatible_expression
1142 : : * Determines if the expression is compatible with functional dependencies
1143 : : *
1144 : : * Similar to dependency_is_compatible_clause, but doesn't enforce that the
1145 : : * expression is a simple Var. On success, return the matching statistics
1146 : : * expression into *expr.
1147 : : */
1148 : : static bool
1149 : 535 : dependency_is_compatible_expression(Node *clause, Index relid, List *statlist, Node **expr)
1150 : : {
1151 : : ListCell *lc,
1152 : : *lc2;
1153 : : Node *clause_expr;
1154 : :
1155 [ + + ]: 535 : if (IsA(clause, RestrictInfo))
1156 : : {
1157 : 460 : RestrictInfo *rinfo = (RestrictInfo *) clause;
1158 : :
1159 : : /* Pseudoconstants are not interesting (they couldn't contain a Var) */
1160 [ + + ]: 460 : if (rinfo->pseudoconstant)
1161 : 5 : return false;
1162 : :
1163 : : /* Clauses referencing multiple, or no, varnos are incompatible */
1164 [ - + ]: 455 : if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
1165 : 0 : return false;
1166 : :
1167 : 455 : clause = (Node *) rinfo->clause;
1168 : : }
1169 : :
1170 [ + + ]: 530 : if (is_opclause(clause))
1171 : : {
1172 : : /* If it's an opclause, check for Var = Const or Const = Var. */
1173 : 170 : OpExpr *expr = (OpExpr *) clause;
1174 : :
1175 : : /* Only expressions with two arguments are candidates. */
1176 [ - + ]: 170 : if (list_length(expr->args) != 2)
1177 : 0 : return false;
1178 : :
1179 : : /* Make sure non-selected argument is a pseudoconstant. */
1180 [ + - ]: 170 : if (is_pseudo_constant_clause(lsecond(expr->args)))
1181 : 170 : clause_expr = linitial(expr->args);
1182 [ # # ]: 0 : else if (is_pseudo_constant_clause(linitial(expr->args)))
1183 : 0 : clause_expr = lsecond(expr->args);
1184 : : else
1185 : 0 : return false;
1186 : :
1187 : : /*
1188 : : * If it's not an "=" operator, just ignore the clause, as it's not
1189 : : * compatible with functional dependencies.
1190 : : *
1191 : : * This uses the function for estimating selectivity, not the operator
1192 : : * directly (a bit awkward, but well ...).
1193 : : *
1194 : : * XXX this is pretty dubious; probably it'd be better to check btree
1195 : : * or hash opclass membership, so as not to be fooled by custom
1196 : : * selectivity functions, and to be more consistent with decisions
1197 : : * elsewhere in the planner.
1198 : : */
1199 [ + + ]: 170 : if (get_oprrest(expr->opno) != F_EQSEL)
1200 : 30 : return false;
1201 : :
1202 : : /* OK to proceed with checking "var" */
1203 : : }
1204 [ + + ]: 360 : else if (IsA(clause, ScalarArrayOpExpr))
1205 : : {
1206 : : /* If it's a scalar array operator, check for Var IN Const. */
1207 : 325 : ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
1208 : :
1209 : : /*
1210 : : * Reject ALL() variant, we only care about ANY/IN.
1211 : : *
1212 : : * FIXME Maybe we should check if all the values are the same, and
1213 : : * allow ALL in that case? Doesn't seem very practical, though.
1214 : : */
1215 [ + + ]: 325 : if (!expr->useOr)
1216 : 30 : return false;
1217 : :
1218 : : /* Only expressions with two arguments are candidates. */
1219 [ - + ]: 295 : if (list_length(expr->args) != 2)
1220 : 0 : return false;
1221 : :
1222 : : /*
1223 : : * We know it's always (Var IN Const), so we assume the var is the
1224 : : * first argument, and pseudoconstant is the second one.
1225 : : */
1226 [ - + ]: 295 : if (!is_pseudo_constant_clause(lsecond(expr->args)))
1227 : 0 : return false;
1228 : :
1229 : 295 : clause_expr = linitial(expr->args);
1230 : :
1231 : : /*
1232 : : * If it's not an "=" operator, just ignore the clause, as it's not
1233 : : * compatible with functional dependencies. The operator is identified
1234 : : * simply by looking at which function it uses to estimate
1235 : : * selectivity. That's a bit strange, but it's what other similar
1236 : : * places do.
1237 : : */
1238 [ + + ]: 295 : if (get_oprrest(expr->opno) != F_EQSEL)
1239 : 150 : return false;
1240 : :
1241 : : /* OK to proceed with checking "var" */
1242 : : }
1243 [ + - ]: 35 : else if (is_orclause(clause))
1244 : : {
1245 : 35 : BoolExpr *bool_expr = (BoolExpr *) clause;
1246 : :
1247 : : /* start with no expression (we'll use the first match) */
1248 : 35 : *expr = NULL;
1249 : :
1250 [ + - + + : 100 : foreach(lc, bool_expr->args)
+ + ]
1251 : : {
1252 : 75 : Node *or_expr = NULL;
1253 : :
1254 : : /*
1255 : : * Had we found incompatible expression in the arguments, treat
1256 : : * the whole expression as incompatible.
1257 : : */
1258 [ + + ]: 75 : if (!dependency_is_compatible_expression((Node *) lfirst(lc), relid,
1259 : : statlist, &or_expr))
1260 : 10 : return false;
1261 : :
1262 [ + + ]: 70 : if (*expr == NULL)
1263 : 30 : *expr = or_expr;
1264 : :
1265 : : /* ensure all the expressions are the same */
1266 [ + + ]: 70 : if (!equal(or_expr, *expr))
1267 : 5 : return false;
1268 : : }
1269 : :
1270 : : /* the expression is already checked by the recursive call */
1271 : 25 : return true;
1272 : : }
1273 [ # # ]: 0 : else if (is_notclause(clause))
1274 : : {
1275 : : /*
1276 : : * "NOT x" can be interpreted as "x = false", so get the argument and
1277 : : * proceed with seeing if it's a suitable Var.
1278 : : */
1279 : 0 : clause_expr = (Node *) get_notclausearg(clause);
1280 : : }
1281 : : else
1282 : : {
1283 : : /*
1284 : : * A boolean expression "x" can be interpreted as "x = true", so
1285 : : * proceed with seeing if it's a suitable Var.
1286 : : */
1287 : 0 : clause_expr = clause;
1288 : : }
1289 : :
1290 : : /*
1291 : : * We may ignore any RelabelType node above the operand. (There won't be
1292 : : * more than one, since eval_const_expressions has been applied already.)
1293 : : */
1294 [ - + ]: 285 : if (IsA(clause_expr, RelabelType))
1295 : 0 : clause_expr = (Node *) ((RelabelType *) clause_expr)->arg;
1296 : :
1297 : : /*
1298 : : * Search for a matching statistics expression.
1299 : : */
1300 [ + - + + : 290 : foreach(lc, statlist)
+ + ]
1301 : : {
1302 : 285 : StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
1303 : :
1304 : : /* ignore stats without dependencies */
1305 [ - + ]: 285 : if (info->kind != STATS_EXT_DEPENDENCIES)
1306 : 0 : continue;
1307 : :
1308 [ + + + - : 465 : foreach(lc2, info->exprs)
+ + ]
1309 : : {
1310 : 460 : Node *stat_expr = (Node *) lfirst(lc2);
1311 : :
1312 [ + + ]: 460 : if (equal(clause_expr, stat_expr))
1313 : : {
1314 : 280 : *expr = stat_expr;
1315 : 280 : return true;
1316 : : }
1317 : : }
1318 : : }
1319 : :
1320 : 5 : return false;
1321 : : }
1322 : :
1323 : : /*
1324 : : * dependencies_clauselist_selectivity
1325 : : * Return the estimated selectivity of (a subset of) the given clauses
1326 : : * using functional dependency statistics, or 1.0 if no useful functional
1327 : : * dependency statistic exists.
1328 : : *
1329 : : * 'estimatedclauses' is an input/output argument that gets a bit set
1330 : : * corresponding to the (zero-based) list index of each clause that is included
1331 : : * in the estimated selectivity.
1332 : : *
1333 : : * Given equality clauses on attributes (a,b) we find the strongest dependency
1334 : : * between them, i.e. either (a=>b) or (b=>a). Assuming (a=>b) is the selected
1335 : : * dependency, we then combine the per-clause selectivities using the formula
1336 : : *
1337 : : * P(a,b) = f * P(a) + (1-f) * P(a) * P(b)
1338 : : *
1339 : : * where 'f' is the degree of the dependency. (Actually we use a slightly
1340 : : * modified version of this formula -- see clauselist_apply_dependencies()).
1341 : : *
1342 : : * With clauses on more than two attributes, the dependencies are applied
1343 : : * recursively, starting with the widest/strongest dependencies. For example
1344 : : * P(a,b,c) is first split like this:
1345 : : *
1346 : : * P(a,b,c) = f * P(a,b) + (1-f) * P(a,b) * P(c)
1347 : : *
1348 : : * assuming (a,b=>c) is the strongest dependency.
1349 : : */
1350 : : Selectivity
1351 : 2040 : dependencies_clauselist_selectivity(PlannerInfo *root,
1352 : : List *clauses,
1353 : : int varRelid,
1354 : : JoinType jointype,
1355 : : SpecialJoinInfo *sjinfo,
1356 : : RelOptInfo *rel,
1357 : : Bitmapset **estimatedclauses)
1358 : : {
1359 : 2040 : Selectivity s1 = 1.0;
1360 : : ListCell *l;
1361 : 2040 : Bitmapset *clauses_attnums = NULL;
1362 : : AttrNumber *list_attnums;
1363 : : int listidx;
1364 : : MVDependencies **func_dependencies;
1365 : : int nfunc_dependencies;
1366 : : int total_ndeps;
1367 : : MVDependency **dependencies;
1368 : : int ndependencies;
1369 : : AttrNumber attnum_offset;
1370 [ + - ]: 2040 : RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
1371 : :
1372 : : /* unique expressions */
1373 : : Node **unique_exprs;
1374 : : int unique_exprs_cnt;
1375 : :
1376 : : /* check if there's any stats that might be useful for us. */
1377 [ + + ]: 2040 : if (!has_stats_of_kind(rel->statlist, STATS_EXT_DEPENDENCIES))
1378 : 550 : return 1.0;
1379 : :
1380 : 1490 : list_attnums = palloc_array(AttrNumber, list_length(clauses));
1381 : :
1382 : : /*
1383 : : * We allocate space as if every clause was a unique expression, although
1384 : : * that's probably overkill. Some will be simple column references that
1385 : : * we'll translate to attnums, and there might be duplicates. But it's
1386 : : * easier and cheaper to just do one allocation than repalloc later.
1387 : : */
1388 : 1490 : unique_exprs = palloc_array(Node *, list_length(clauses));
1389 : 1490 : unique_exprs_cnt = 0;
1390 : :
1391 : : /*
1392 : : * Pre-process the clauses list to extract the attnums seen in each item.
1393 : : * We need to determine if there's any clauses which will be useful for
1394 : : * dependency selectivity estimations. Along the way we'll record all of
1395 : : * the attnums for each clause in a list which we'll reference later so we
1396 : : * don't need to repeat the same work again. We'll also keep track of all
1397 : : * attnums seen.
1398 : : *
1399 : : * We also skip clauses that we already estimated using different types of
1400 : : * statistics (we treat them as incompatible).
1401 : : *
1402 : : * To handle expressions, we assign them negative attnums, as if it was a
1403 : : * system attribute (this is fine, as we only allow extended stats on user
1404 : : * attributes). And then we offset everything by the number of
1405 : : * expressions, so that we can store the values in a bitmapset.
1406 : : */
1407 : 1490 : listidx = 0;
1408 [ + - + + : 4725 : foreach(l, clauses)
+ + ]
1409 : : {
1410 : 3235 : Node *clause = (Node *) lfirst(l);
1411 : : AttrNumber attnum;
1412 : 3235 : Node *expr = NULL;
1413 : :
1414 : : /* ignore clause by default */
1415 : 3235 : list_attnums[listidx] = InvalidAttrNumber;
1416 : :
1417 [ + + ]: 3235 : if (!bms_is_member(listidx, *estimatedclauses))
1418 : : {
1419 : : /*
1420 : : * If it's a simple column reference, just extract the attnum. If
1421 : : * it's an expression, assign a negative attnum as if it was a
1422 : : * system attribute.
1423 : : */
1424 [ + + ]: 3200 : if (dependency_is_compatible_clause(clause, rel->relid, &attnum))
1425 : : {
1426 : 2740 : list_attnums[listidx] = attnum;
1427 : : }
1428 [ + + ]: 460 : else if (dependency_is_compatible_expression(clause, rel->relid,
1429 : : rel->statlist,
1430 : : &expr))
1431 : : {
1432 : : /* special attnum assigned to this expression */
1433 : 235 : attnum = InvalidAttrNumber;
1434 : :
1435 : : Assert(expr != NULL);
1436 : :
1437 : : /* If the expression is duplicate, use the same attnum. */
1438 [ + + ]: 395 : for (int i = 0; i < unique_exprs_cnt; i++)
1439 : : {
1440 [ - + ]: 160 : if (equal(unique_exprs[i], expr))
1441 : : {
1442 : : /* negative attribute number to expression */
1443 : 0 : attnum = -(i + 1);
1444 : 0 : break;
1445 : : }
1446 : : }
1447 : :
1448 : : /* not found in the list, so add it */
1449 [ + - ]: 235 : if (attnum == InvalidAttrNumber)
1450 : : {
1451 : 235 : unique_exprs[unique_exprs_cnt++] = expr;
1452 : :
1453 : : /* after incrementing the value, to get -1, -2, ... */
1454 : 235 : attnum = (-unique_exprs_cnt);
1455 : : }
1456 : :
1457 : : /* remember which attnum was assigned to this clause */
1458 : 235 : list_attnums[listidx] = attnum;
1459 : : }
1460 : : }
1461 : :
1462 : 3235 : listidx++;
1463 : : }
1464 : :
1465 : : Assert(listidx == list_length(clauses));
1466 : :
1467 : : /*
1468 : : * How much we need to offset the attnums? If there are no expressions,
1469 : : * then no offset is needed. Otherwise we need to offset enough for the
1470 : : * lowest value (-unique_exprs_cnt) to become 1.
1471 : : */
1472 [ + + ]: 1490 : if (unique_exprs_cnt > 0)
1473 : 110 : attnum_offset = (unique_exprs_cnt + 1);
1474 : : else
1475 : 1380 : attnum_offset = 0;
1476 : :
1477 : : /*
1478 : : * Now that we know how many expressions there are, we can offset the
1479 : : * values just enough to build the bitmapset.
1480 : : */
1481 [ + + ]: 4725 : for (int i = 0; i < list_length(clauses); i++)
1482 : : {
1483 : : AttrNumber attnum;
1484 : :
1485 : : /* ignore incompatible or already estimated clauses */
1486 [ + + ]: 3235 : if (list_attnums[i] == InvalidAttrNumber)
1487 : 260 : continue;
1488 : :
1489 : : /* make sure the attnum is in the expected range */
1490 : : Assert(list_attnums[i] >= (-unique_exprs_cnt));
1491 : : Assert(list_attnums[i] <= MaxHeapAttributeNumber);
1492 : :
1493 : : /* make sure the attnum is positive (valid AttrNumber) */
1494 : 2975 : attnum = list_attnums[i] + attnum_offset;
1495 : :
1496 : : /*
1497 : : * Either it's a regular attribute, or it's an expression, in which
1498 : : * case we must not have seen it before (expressions are unique).
1499 : : *
1500 : : * XXX Check whether it's a regular attribute has to be done using the
1501 : : * original attnum, while the second check has to use the value with
1502 : : * an offset.
1503 : : */
1504 : : Assert(AttrNumberIsForUserDefinedAttr(list_attnums[i]) ||
1505 : : !bms_is_member(attnum, clauses_attnums));
1506 : :
1507 : : /*
1508 : : * Remember the offset attnum, both for attributes and expressions.
1509 : : * We'll pass list_attnums to clauselist_apply_dependencies, which
1510 : : * uses it to identify clauses in a bitmap. We could also pass the
1511 : : * offset, but this is more convenient.
1512 : : */
1513 : 2975 : list_attnums[i] = attnum;
1514 : :
1515 : 2975 : clauses_attnums = bms_add_member(clauses_attnums, attnum);
1516 : : }
1517 : :
1518 : : /*
1519 : : * If there's not at least two distinct attnums and expressions, then
1520 : : * reject the whole list of clauses. We must return 1.0 so the calling
1521 : : * function's selectivity is unaffected.
1522 : : */
1523 [ + + ]: 1490 : if (bms_membership(clauses_attnums) != BMS_MULTIPLE)
1524 : : {
1525 : 160 : bms_free(clauses_attnums);
1526 : 160 : pfree(list_attnums);
1527 : 160 : return 1.0;
1528 : : }
1529 : :
1530 : : /*
1531 : : * Load all functional dependencies matching at least two parameters. We
1532 : : * can simply consider all dependencies at once, without having to search
1533 : : * for the best statistics object.
1534 : : *
1535 : : * To not waste cycles and memory, we deserialize dependencies only for
1536 : : * statistics that match at least two attributes. The array is allocated
1537 : : * with the assumption that all objects match - we could grow the array to
1538 : : * make it just the right size, but it's likely wasteful anyway thanks to
1539 : : * moving the freed chunks to freelists etc.
1540 : : */
1541 : 1330 : func_dependencies = palloc_array(MVDependencies *, list_length(rel->statlist));
1542 : 1330 : nfunc_dependencies = 0;
1543 : 1330 : total_ndeps = 0;
1544 : :
1545 [ + - + + : 2775 : foreach(l, rel->statlist)
+ + ]
1546 : : {
1547 : 1445 : StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
1548 : : int nmatched;
1549 : : int nexprs;
1550 : : int k;
1551 : : MVDependencies *deps;
1552 : :
1553 : : /* skip statistics that are not of the correct type */
1554 [ + + ]: 1445 : if (stat->kind != STATS_EXT_DEPENDENCIES)
1555 : 90 : continue;
1556 : :
1557 : : /* skip statistics with mismatching stxdinherit value */
1558 [ - + ]: 1355 : if (stat->inherit != rte->inh)
1559 : 0 : continue;
1560 : :
1561 : : /*
1562 : : * Count matching attributes - we have to undo the attnum offsets. The
1563 : : * input attribute numbers are not offset (expressions are not
1564 : : * included in stat->keys, so it's not necessary). But we need to
1565 : : * offset it before checking against clauses_attnums.
1566 : : */
1567 : 1355 : nmatched = 0;
1568 : 1355 : k = -1;
1569 [ + + ]: 5100 : while ((k = bms_next_member(stat->keys, k)) >= 0)
1570 : : {
1571 : 3745 : AttrNumber attnum = (AttrNumber) k;
1572 : :
1573 : : /* skip expressions */
1574 [ - + ]: 3745 : if (!AttrNumberIsForUserDefinedAttr(attnum))
1575 : 0 : continue;
1576 : :
1577 : : /* apply the same offset as above */
1578 : 3745 : attnum += attnum_offset;
1579 : :
1580 [ + + ]: 3745 : if (bms_is_member(attnum, clauses_attnums))
1581 : 2700 : nmatched++;
1582 : : }
1583 : :
1584 : : /* count matching expressions */
1585 : 1355 : nexprs = 0;
1586 [ + + ]: 1570 : for (int i = 0; i < unique_exprs_cnt; i++)
1587 : : {
1588 : : ListCell *lc;
1589 : :
1590 [ + - + + : 860 : foreach(lc, stat->exprs)
+ + ]
1591 : : {
1592 : 645 : Node *stat_expr = (Node *) lfirst(lc);
1593 : :
1594 : : /* try to match it */
1595 [ + + ]: 645 : if (equal(stat_expr, unique_exprs[i]))
1596 : 215 : nexprs++;
1597 : : }
1598 : : }
1599 : :
1600 : : /*
1601 : : * Skip objects matching fewer than two attributes/expressions from
1602 : : * clauses.
1603 : : */
1604 [ + + ]: 1355 : if (nmatched + nexprs < 2)
1605 : 15 : continue;
1606 : :
1607 : 1340 : deps = statext_dependencies_load(stat->statOid, rte->inh);
1608 : :
1609 : : /*
1610 : : * The expressions may be represented by different attnums in the
1611 : : * stats, we need to remap them to be consistent with the clauses.
1612 : : * That will make the later steps (e.g. picking the strongest item and
1613 : : * so on) much simpler and cheaper, because it won't need to care
1614 : : * about the offset at all.
1615 : : *
1616 : : * When we're at it, we can ignore dependencies that are not fully
1617 : : * matched by clauses (i.e. referencing attributes or expressions that
1618 : : * are not in the clauses).
1619 : : *
1620 : : * We have to do this for all statistics, as long as there are any
1621 : : * expressions - we need to shift the attnums in all dependencies.
1622 : : *
1623 : : * XXX Maybe we should do this always, because it also eliminates some
1624 : : * of the dependencies early. It might be cheaper than having to walk
1625 : : * the longer list in find_strongest_dependency later, especially as
1626 : : * we need to do that repeatedly?
1627 : : *
1628 : : * XXX We have to do this even when there are no expressions in
1629 : : * clauses, otherwise find_strongest_dependency may fail for stats
1630 : : * with expressions (due to lookup of negative value in bitmap). So we
1631 : : * need to at least filter out those dependencies. Maybe we could do
1632 : : * it in a cheaper way (if there are no expr clauses, we can just
1633 : : * discard all negative attnums without any lookups).
1634 : : */
1635 [ + + - + ]: 1340 : if (unique_exprs_cnt > 0 || stat->exprs != NIL)
1636 : : {
1637 : 90 : uint32 ndeps = 0;
1638 : :
1639 [ + + ]: 540 : for (uint32 i = 0; i < deps->ndeps; i++)
1640 : : {
1641 : 450 : bool skip = false;
1642 : 450 : MVDependency *dep = deps->deps[i];
1643 : :
1644 [ + + ]: 1255 : for (int j = 0; j < dep->nattributes; j++)
1645 : : {
1646 : : int idx;
1647 : : Node *expr;
1648 : 1025 : AttrNumber unique_attnum = InvalidAttrNumber;
1649 : : AttrNumber attnum;
1650 : :
1651 : : /* undo the per-statistics offset */
1652 : 1025 : attnum = dep->attributes[j];
1653 : :
1654 : : /*
1655 : : * For regular attributes we can simply check if it
1656 : : * matches any clause. If there's no matching clause, we
1657 : : * can just ignore it. We need to offset the attnum
1658 : : * though.
1659 : : */
1660 [ - + ]: 1025 : if (AttrNumberIsForUserDefinedAttr(attnum))
1661 : : {
1662 : 0 : dep->attributes[j] = attnum + attnum_offset;
1663 : :
1664 [ # # ]: 0 : if (!bms_is_member(dep->attributes[j], clauses_attnums))
1665 : : {
1666 : 0 : skip = true;
1667 : 0 : break;
1668 : : }
1669 : :
1670 : 0 : continue;
1671 : : }
1672 : :
1673 : : /*
1674 : : * the attnum should be a valid system attnum (-1, -2,
1675 : : * ...)
1676 : : */
1677 : : Assert(AttributeNumberIsValid(attnum));
1678 : :
1679 : : /*
1680 : : * For expressions, we need to do two translations. First
1681 : : * we have to translate the negative attnum to index in
1682 : : * the list of expressions (in the statistics object).
1683 : : * Then we need to see if there's a matching clause. The
1684 : : * index of the unique expression determines the attnum
1685 : : * (and we offset it).
1686 : : */
1687 : 1025 : idx = -(1 + attnum);
1688 : :
1689 : : /* Is the expression index is valid? */
1690 : : Assert((idx >= 0) && (idx < list_length(stat->exprs)));
1691 : :
1692 : 1025 : expr = (Node *) list_nth(stat->exprs, idx);
1693 : :
1694 : : /* try to find the expression in the unique list */
1695 [ + + ]: 2050 : for (int m = 0; m < unique_exprs_cnt; m++)
1696 : : {
1697 : : /*
1698 : : * found a matching unique expression, use the attnum
1699 : : * (derived from index of the unique expression)
1700 : : */
1701 [ + + ]: 1830 : if (equal(unique_exprs[m], expr))
1702 : : {
1703 : 805 : unique_attnum = -(m + 1) + attnum_offset;
1704 : 805 : break;
1705 : : }
1706 : : }
1707 : :
1708 : : /*
1709 : : * Found no matching expression, so we can simply skip
1710 : : * this dependency, because there's no chance it will be
1711 : : * fully covered.
1712 : : */
1713 [ + + ]: 1025 : if (unique_attnum == InvalidAttrNumber)
1714 : : {
1715 : 220 : skip = true;
1716 : 220 : break;
1717 : : }
1718 : :
1719 : : /* otherwise remap it to the new attnum */
1720 : 805 : dep->attributes[j] = unique_attnum;
1721 : : }
1722 : :
1723 : : /* if found a matching dependency, keep it */
1724 [ + + ]: 450 : if (!skip)
1725 : : {
1726 : : /* maybe we've skipped something earlier, so move it */
1727 [ - + ]: 230 : if (ndeps != i)
1728 : 0 : deps->deps[ndeps] = deps->deps[i];
1729 : :
1730 : 230 : ndeps++;
1731 : : }
1732 : : }
1733 : :
1734 : 90 : deps->ndeps = ndeps;
1735 : : }
1736 : :
1737 : : /*
1738 : : * It's possible we've removed all dependencies, in which case we
1739 : : * don't bother adding it to the list.
1740 : : */
1741 [ + - ]: 1340 : if (deps->ndeps > 0)
1742 : : {
1743 : 1340 : func_dependencies[nfunc_dependencies] = deps;
1744 : 1340 : total_ndeps += deps->ndeps;
1745 : 1340 : nfunc_dependencies++;
1746 : : }
1747 : : }
1748 : :
1749 : : /* if no matching stats could be found then we've nothing to do */
1750 [ - + ]: 1330 : if (nfunc_dependencies == 0)
1751 : : {
1752 : 0 : pfree(func_dependencies);
1753 : 0 : bms_free(clauses_attnums);
1754 : 0 : pfree(list_attnums);
1755 : 0 : pfree(unique_exprs);
1756 : 0 : return 1.0;
1757 : : }
1758 : :
1759 : : /*
1760 : : * Work out which dependencies we can apply, starting with the
1761 : : * widest/strongest ones, and proceeding to smaller/weaker ones.
1762 : : */
1763 : 1330 : dependencies = palloc_array(MVDependency *, total_ndeps);
1764 : 1330 : ndependencies = 0;
1765 : :
1766 : : while (true)
1767 : 1575 : {
1768 : : MVDependency *dependency;
1769 : : AttrNumber attnum;
1770 : :
1771 : : /* the widest/strongest dependency, fully matched by clauses */
1772 : 2905 : dependency = find_strongest_dependency(func_dependencies,
1773 : : nfunc_dependencies,
1774 : : clauses_attnums);
1775 [ + + ]: 2905 : if (!dependency)
1776 : 1330 : break;
1777 : :
1778 : 1575 : dependencies[ndependencies++] = dependency;
1779 : :
1780 : : /* Ignore dependencies using this implied attribute in later loops */
1781 : 1575 : attnum = dependency->attributes[dependency->nattributes - 1];
1782 : 1575 : clauses_attnums = bms_del_member(clauses_attnums, attnum);
1783 : : }
1784 : :
1785 : : /*
1786 : : * If we found applicable dependencies, use them to estimate all
1787 : : * compatible clauses on attributes that they refer to.
1788 : : */
1789 [ + - ]: 1330 : if (ndependencies != 0)
1790 : 1330 : s1 = clauselist_apply_dependencies(root, clauses, varRelid, jointype,
1791 : : sjinfo, dependencies, ndependencies,
1792 : : list_attnums, estimatedclauses);
1793 : :
1794 : : /* free deserialized functional dependencies (and then the array) */
1795 [ + + ]: 2670 : for (int i = 0; i < nfunc_dependencies; i++)
1796 : 1340 : pfree(func_dependencies[i]);
1797 : :
1798 : 1330 : pfree(dependencies);
1799 : 1330 : pfree(func_dependencies);
1800 : 1330 : bms_free(clauses_attnums);
1801 : 1330 : pfree(list_attnums);
1802 : 1330 : pfree(unique_exprs);
1803 : :
1804 : 1330 : return s1;
1805 : : }
|
