LCOV - code coverage report
Current view: top level - src/backend/statistics - dependencies.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 442 500 88.4 %
Date: 2023-12-01 20:11:03 Functions: 17 20 85.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.14