LCOV - code coverage report
Current view: top level - src/backend/statistics - extended_stats.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17devel Lines: 727 788 92.3 %
Date: 2023-12-11 16:10:55 Functions: 32 33 97.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * extended_stats.c
       4             :  *    POSTGRES extended statistics
       5             :  *
       6             :  * Generic code supporting statistics objects created via CREATE STATISTICS.
       7             :  *
       8             :  *
       9             :  * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
      10             :  * Portions Copyright (c) 1994, Regents of the University of California
      11             :  *
      12             :  * IDENTIFICATION
      13             :  *    src/backend/statistics/extended_stats.c
      14             :  *
      15             :  *-------------------------------------------------------------------------
      16             :  */
      17             : #include "postgres.h"
      18             : 
      19             : #include "access/detoast.h"
      20             : #include "access/genam.h"
      21             : #include "access/htup_details.h"
      22             : #include "access/table.h"
      23             : #include "catalog/indexing.h"
      24             : #include "catalog/pg_collation.h"
      25             : #include "catalog/pg_statistic_ext.h"
      26             : #include "catalog/pg_statistic_ext_data.h"
      27             : #include "executor/executor.h"
      28             : #include "commands/defrem.h"
      29             : #include "commands/progress.h"
      30             : #include "miscadmin.h"
      31             : #include "nodes/nodeFuncs.h"
      32             : #include "optimizer/clauses.h"
      33             : #include "optimizer/optimizer.h"
      34             : #include "parser/parsetree.h"
      35             : #include "pgstat.h"
      36             : #include "postmaster/autovacuum.h"
      37             : #include "statistics/extended_stats_internal.h"
      38             : #include "statistics/statistics.h"
      39             : #include "utils/acl.h"
      40             : #include "utils/array.h"
      41             : #include "utils/attoptcache.h"
      42             : #include "utils/builtins.h"
      43             : #include "utils/datum.h"
      44             : #include "utils/fmgroids.h"
      45             : #include "utils/lsyscache.h"
      46             : #include "utils/memutils.h"
      47             : #include "utils/rel.h"
      48             : #include "utils/selfuncs.h"
      49             : #include "utils/syscache.h"
      50             : #include "utils/typcache.h"
      51             : 
      52             : /*
      53             :  * To avoid consuming too much memory during analysis and/or too much space
      54             :  * in the resulting pg_statistic rows, we ignore varlena datums that are wider
      55             :  * than WIDTH_THRESHOLD (after detoasting!).  This is legitimate for MCV
      56             :  * and distinct-value calculations since a wide value is unlikely to be
      57             :  * duplicated at all, much less be a most-common value.  For the same reason,
      58             :  * ignoring wide values will not affect our estimates of histogram bin
      59             :  * boundaries very much.
      60             :  */
      61             : #define WIDTH_THRESHOLD  1024
      62             : 
      63             : /*
      64             :  * Used internally to refer to an individual statistics object, i.e.,
      65             :  * a pg_statistic_ext entry.
      66             :  */
      67             : typedef struct StatExtEntry
      68             : {
      69             :     Oid         statOid;        /* OID of pg_statistic_ext entry */
      70             :     char       *schema;         /* statistics object's schema */
      71             :     char       *name;           /* statistics object's name */
      72             :     Bitmapset  *columns;        /* attribute numbers covered by the object */
      73             :     List       *types;          /* 'char' list of enabled statistics kinds */
      74             :     int         stattarget;     /* statistics target (-1 for default) */
      75             :     List       *exprs;          /* expressions */
      76             : } StatExtEntry;
      77             : 
      78             : 
      79             : static List *fetch_statentries_for_relation(Relation pg_statext, Oid relid);
      80             : static VacAttrStats **lookup_var_attr_stats(Relation rel, Bitmapset *attrs, List *exprs,
      81             :                                             int nvacatts, VacAttrStats **vacatts);
      82             : static void statext_store(Oid statOid, bool inh,
      83             :                           MVNDistinct *ndistinct, MVDependencies *dependencies,
      84             :                           MCVList *mcv, Datum exprs, VacAttrStats **stats);
      85             : static int  statext_compute_stattarget(int stattarget,
      86             :                                        int nattrs, VacAttrStats **stats);
      87             : 
      88             : /* Information needed to analyze a single simple expression. */
      89             : typedef struct AnlExprData
      90             : {
      91             :     Node       *expr;           /* expression to analyze */
      92             :     VacAttrStats *vacattrstat;  /* statistics attrs to analyze */
      93             : } AnlExprData;
      94             : 
      95             : static void compute_expr_stats(Relation onerel, double totalrows,
      96             :                                AnlExprData *exprdata, int nexprs,
      97             :                                HeapTuple *rows, int numrows);
      98             : static Datum serialize_expr_stats(AnlExprData *exprdata, int nexprs);
      99             : static Datum expr_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull);
     100             : static AnlExprData *build_expr_data(List *exprs, int stattarget);
     101             : 
     102             : static StatsBuildData *make_build_data(Relation rel, StatExtEntry *stat,
     103             :                                        int numrows, HeapTuple *rows,
     104             :                                        VacAttrStats **stats, int stattarget);
     105             : 
     106             : 
     107             : /*
     108             :  * Compute requested extended stats, using the rows sampled for the plain
     109             :  * (single-column) stats.
     110             :  *
     111             :  * This fetches a list of stats types from pg_statistic_ext, computes the
     112             :  * requested stats, and serializes them back into the catalog.
     113             :  */
     114             : void
     115        7802 : BuildRelationExtStatistics(Relation onerel, bool inh, double totalrows,
     116             :                            int numrows, HeapTuple *rows,
     117             :                            int natts, VacAttrStats **vacattrstats)
     118             : {
     119             :     Relation    pg_stext;
     120             :     ListCell   *lc;
     121             :     List       *statslist;
     122             :     MemoryContext cxt;
     123             :     MemoryContext oldcxt;
     124             :     int64       ext_cnt;
     125             : 
     126             :     /* Do nothing if there are no columns to analyze. */
     127        7802 :     if (!natts)
     128           6 :         return;
     129             : 
     130             :     /* the list of stats has to be allocated outside the memory context */
     131        7796 :     pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
     132        7796 :     statslist = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
     133             : 
     134             :     /* memory context for building each statistics object */
     135        7796 :     cxt = AllocSetContextCreate(CurrentMemoryContext,
     136             :                                 "BuildRelationExtStatistics",
     137             :                                 ALLOCSET_DEFAULT_SIZES);
     138        7796 :     oldcxt = MemoryContextSwitchTo(cxt);
     139             : 
     140             :     /* report this phase */
     141        7796 :     if (statslist != NIL)
     142             :     {
     143         270 :         const int   index[] = {
     144             :             PROGRESS_ANALYZE_PHASE,
     145             :             PROGRESS_ANALYZE_EXT_STATS_TOTAL
     146             :         };
     147         540 :         const int64 val[] = {
     148             :             PROGRESS_ANALYZE_PHASE_COMPUTE_EXT_STATS,
     149         270 :             list_length(statslist)
     150             :         };
     151             : 
     152         270 :         pgstat_progress_update_multi_param(2, index, val);
     153             :     }
     154             : 
     155        7796 :     ext_cnt = 0;
     156        8162 :     foreach(lc, statslist)
     157             :     {
     158         366 :         StatExtEntry *stat = (StatExtEntry *) lfirst(lc);
     159         366 :         MVNDistinct *ndistinct = NULL;
     160         366 :         MVDependencies *dependencies = NULL;
     161         366 :         MCVList    *mcv = NULL;
     162         366 :         Datum       exprstats = (Datum) 0;
     163             :         VacAttrStats **stats;
     164             :         ListCell   *lc2;
     165             :         int         stattarget;
     166             :         StatsBuildData *data;
     167             : 
     168             :         /*
     169             :          * Check if we can build these stats based on the column analyzed. If
     170             :          * not, report this fact (except in autovacuum) and move on.
     171             :          */
     172         366 :         stats = lookup_var_attr_stats(onerel, stat->columns, stat->exprs,
     173             :                                       natts, vacattrstats);
     174         366 :         if (!stats)
     175             :         {
     176          12 :             if (!IsAutoVacuumWorkerProcess())
     177          12 :                 ereport(WARNING,
     178             :                         (errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
     179             :                          errmsg("statistics object \"%s.%s\" could not be computed for relation \"%s.%s\"",
     180             :                                 stat->schema, stat->name,
     181             :                                 get_namespace_name(onerel->rd_rel->relnamespace),
     182             :                                 RelationGetRelationName(onerel)),
     183             :                          errtable(onerel)));
     184          12 :             continue;
     185             :         }
     186             : 
     187             :         /* compute statistics target for this statistics object */
     188         354 :         stattarget = statext_compute_stattarget(stat->stattarget,
     189         354 :                                                 bms_num_members(stat->columns),
     190             :                                                 stats);
     191             : 
     192             :         /*
     193             :          * Don't rebuild statistics objects with statistics target set to 0
     194             :          * (we just leave the existing values around, just like we do for
     195             :          * regular per-column statistics).
     196             :          */
     197         354 :         if (stattarget == 0)
     198           6 :             continue;
     199             : 
     200             :         /* evaluate expressions (if the statistics object has any) */
     201         348 :         data = make_build_data(onerel, stat, numrows, rows, stats, stattarget);
     202             : 
     203             :         /* compute statistic of each requested type */
     204         954 :         foreach(lc2, stat->types)
     205             :         {
     206         606 :             char        t = (char) lfirst_int(lc2);
     207             : 
     208         606 :             if (t == STATS_EXT_NDISTINCT)
     209         156 :                 ndistinct = statext_ndistinct_build(totalrows, data);
     210         450 :             else if (t == STATS_EXT_DEPENDENCIES)
     211         120 :                 dependencies = statext_dependencies_build(data);
     212         330 :             else if (t == STATS_EXT_MCV)
     213         180 :                 mcv = statext_mcv_build(data, totalrows, stattarget);
     214         150 :             else if (t == STATS_EXT_EXPRESSIONS)
     215             :             {
     216             :                 AnlExprData *exprdata;
     217             :                 int         nexprs;
     218             : 
     219             :                 /* should not happen, thanks to checks when defining stats */
     220         150 :                 if (!stat->exprs)
     221           0 :                     elog(ERROR, "requested expression stats, but there are no expressions");
     222             : 
     223         150 :                 exprdata = build_expr_data(stat->exprs, stattarget);
     224         150 :                 nexprs = list_length(stat->exprs);
     225             : 
     226         150 :                 compute_expr_stats(onerel, totalrows,
     227             :                                    exprdata, nexprs,
     228             :                                    rows, numrows);
     229             : 
     230         150 :                 exprstats = serialize_expr_stats(exprdata, nexprs);
     231             :             }
     232             :         }
     233             : 
     234             :         /* store the statistics in the catalog */
     235         348 :         statext_store(stat->statOid, inh,
     236             :                       ndistinct, dependencies, mcv, exprstats, stats);
     237             : 
     238             :         /* for reporting progress */
     239         348 :         pgstat_progress_update_param(PROGRESS_ANALYZE_EXT_STATS_COMPUTED,
     240             :                                      ++ext_cnt);
     241             : 
     242             :         /* free the data used for building this statistics object */
     243         348 :         MemoryContextReset(cxt);
     244             :     }
     245             : 
     246        7796 :     MemoryContextSwitchTo(oldcxt);
     247        7796 :     MemoryContextDelete(cxt);
     248             : 
     249        7796 :     list_free(statslist);
     250             : 
     251        7796 :     table_close(pg_stext, RowExclusiveLock);
     252             : }
     253             : 
     254             : /*
     255             :  * ComputeExtStatisticsRows
     256             :  *      Compute number of rows required by extended statistics on a table.
     257             :  *
     258             :  * Computes number of rows we need to sample to build extended statistics on a
     259             :  * table. This only looks at statistics we can actually build - for example
     260             :  * when analyzing only some of the columns, this will skip statistics objects
     261             :  * that would require additional columns.
     262             :  *
     263             :  * See statext_compute_stattarget for details about how we compute the
     264             :  * statistics target for a statistics object (from the object target,
     265             :  * attribute targets and default statistics target).
     266             :  */
     267             : int
     268       11154 : ComputeExtStatisticsRows(Relation onerel,
     269             :                          int natts, VacAttrStats **vacattrstats)
     270             : {
     271             :     Relation    pg_stext;
     272             :     ListCell   *lc;
     273             :     List       *lstats;
     274             :     MemoryContext cxt;
     275             :     MemoryContext oldcxt;
     276       11154 :     int         result = 0;
     277             : 
     278             :     /* If there are no columns to analyze, just return 0. */
     279       11154 :     if (!natts)
     280           6 :         return 0;
     281             : 
     282       11148 :     cxt = AllocSetContextCreate(CurrentMemoryContext,
     283             :                                 "ComputeExtStatisticsRows",
     284             :                                 ALLOCSET_DEFAULT_SIZES);
     285       11148 :     oldcxt = MemoryContextSwitchTo(cxt);
     286             : 
     287       11148 :     pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
     288       11148 :     lstats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
     289             : 
     290       11514 :     foreach(lc, lstats)
     291             :     {
     292         366 :         StatExtEntry *stat = (StatExtEntry *) lfirst(lc);
     293             :         int         stattarget;
     294             :         VacAttrStats **stats;
     295         366 :         int         nattrs = bms_num_members(stat->columns);
     296             : 
     297             :         /*
     298             :          * Check if we can build this statistics object based on the columns
     299             :          * analyzed. If not, ignore it (don't report anything, we'll do that
     300             :          * during the actual build BuildRelationExtStatistics).
     301             :          */
     302         366 :         stats = lookup_var_attr_stats(onerel, stat->columns, stat->exprs,
     303             :                                       natts, vacattrstats);
     304             : 
     305         366 :         if (!stats)
     306          12 :             continue;
     307             : 
     308             :         /*
     309             :          * Compute statistics target, based on what's set for the statistic
     310             :          * object itself, and for its attributes.
     311             :          */
     312         354 :         stattarget = statext_compute_stattarget(stat->stattarget,
     313             :                                                 nattrs, stats);
     314             : 
     315             :         /* Use the largest value for all statistics objects. */
     316         354 :         if (stattarget > result)
     317         252 :             result = stattarget;
     318             :     }
     319             : 
     320       11148 :     table_close(pg_stext, RowExclusiveLock);
     321             : 
     322       11148 :     MemoryContextSwitchTo(oldcxt);
     323       11148 :     MemoryContextDelete(cxt);
     324             : 
     325             :     /* compute sample size based on the statistics target */
     326       11148 :     return (300 * result);
     327             : }
     328             : 
     329             : /*
     330             :  * statext_compute_stattarget
     331             :  *      compute statistics target for an extended statistic
     332             :  *
     333             :  * When computing target for extended statistics objects, we consider three
     334             :  * places where the target may be set - the statistics object itself,
     335             :  * attributes the statistics object is defined on, and then the default
     336             :  * statistics target.
     337             :  *
     338             :  * First we look at what's set for the statistics object itself, using the
     339             :  * ALTER STATISTICS ... SET STATISTICS command. If we find a valid value
     340             :  * there (i.e. not -1) we're done. Otherwise we look at targets set for any
     341             :  * of the attributes the statistic is defined on, and if there are columns
     342             :  * with defined target, we use the maximum value. We do this mostly for
     343             :  * backwards compatibility, because this is what we did before having
     344             :  * statistics target for extended statistics.
     345             :  *
     346             :  * And finally, if we still don't have a statistics target, we use the value
     347             :  * set in default_statistics_target.
     348             :  */
     349             : static int
     350         708 : statext_compute_stattarget(int stattarget, int nattrs, VacAttrStats **stats)
     351             : {
     352             :     int         i;
     353             : 
     354             :     /*
     355             :      * If there's statistics target set for the statistics object, use it. It
     356             :      * may be set to 0 which disables building of that statistic.
     357             :      */
     358         708 :     if (stattarget >= 0)
     359          12 :         return stattarget;
     360             : 
     361             :     /*
     362             :      * The target for the statistics object is set to -1, in which case we
     363             :      * look at the maximum target set for any of the attributes the object is
     364             :      * defined on.
     365             :      */
     366        1920 :     for (i = 0; i < nattrs; i++)
     367             :     {
     368             :         /* keep the maximum statistics target */
     369        1224 :         if (stats[i]->attstattarget > stattarget)
     370         528 :             stattarget = stats[i]->attstattarget;
     371             :     }
     372             : 
     373             :     /*
     374             :      * If the value is still negative (so neither the statistics object nor
     375             :      * any of the columns have custom statistics target set), use the global
     376             :      * default target.
     377             :      */
     378         696 :     if (stattarget < 0)
     379         168 :         stattarget = default_statistics_target;
     380             : 
     381             :     /* As this point we should have a valid statistics target. */
     382             :     Assert((stattarget >= 0) && (stattarget <= MAX_STATISTICS_TARGET));
     383             : 
     384         696 :     return stattarget;
     385             : }
     386             : 
     387             : /*
     388             :  * statext_is_kind_built
     389             :  *      Is this stat kind built in the given pg_statistic_ext_data tuple?
     390             :  */
     391             : bool
     392        7344 : statext_is_kind_built(HeapTuple htup, char type)
     393             : {
     394             :     AttrNumber  attnum;
     395             : 
     396        7344 :     switch (type)
     397             :     {
     398        1836 :         case STATS_EXT_NDISTINCT:
     399        1836 :             attnum = Anum_pg_statistic_ext_data_stxdndistinct;
     400        1836 :             break;
     401             : 
     402        1836 :         case STATS_EXT_DEPENDENCIES:
     403        1836 :             attnum = Anum_pg_statistic_ext_data_stxddependencies;
     404        1836 :             break;
     405             : 
     406        1836 :         case STATS_EXT_MCV:
     407        1836 :             attnum = Anum_pg_statistic_ext_data_stxdmcv;
     408        1836 :             break;
     409             : 
     410        1836 :         case STATS_EXT_EXPRESSIONS:
     411        1836 :             attnum = Anum_pg_statistic_ext_data_stxdexpr;
     412        1836 :             break;
     413             : 
     414           0 :         default:
     415           0 :             elog(ERROR, "unexpected statistics type requested: %d", type);
     416             :     }
     417             : 
     418        7344 :     return !heap_attisnull(htup, attnum, NULL);
     419             : }
     420             : 
     421             : /*
     422             :  * Return a list (of StatExtEntry) of statistics objects for the given relation.
     423             :  */
     424             : static List *
     425       18944 : fetch_statentries_for_relation(Relation pg_statext, Oid relid)
     426             : {
     427             :     SysScanDesc scan;
     428             :     ScanKeyData skey;
     429             :     HeapTuple   htup;
     430       18944 :     List       *result = NIL;
     431             : 
     432             :     /*
     433             :      * Prepare to scan pg_statistic_ext for entries having stxrelid = this
     434             :      * rel.
     435             :      */
     436       18944 :     ScanKeyInit(&skey,
     437             :                 Anum_pg_statistic_ext_stxrelid,
     438             :                 BTEqualStrategyNumber, F_OIDEQ,
     439             :                 ObjectIdGetDatum(relid));
     440             : 
     441       18944 :     scan = systable_beginscan(pg_statext, StatisticExtRelidIndexId, true,
     442             :                               NULL, 1, &skey);
     443             : 
     444       19676 :     while (HeapTupleIsValid(htup = systable_getnext(scan)))
     445             :     {
     446             :         StatExtEntry *entry;
     447             :         Datum       datum;
     448             :         bool        isnull;
     449             :         int         i;
     450             :         ArrayType  *arr;
     451             :         char       *enabled;
     452             :         Form_pg_statistic_ext staForm;
     453         732 :         List       *exprs = NIL;
     454             : 
     455         732 :         entry = palloc0(sizeof(StatExtEntry));
     456         732 :         staForm = (Form_pg_statistic_ext) GETSTRUCT(htup);
     457         732 :         entry->statOid = staForm->oid;
     458         732 :         entry->schema = get_namespace_name(staForm->stxnamespace);
     459         732 :         entry->name = pstrdup(NameStr(staForm->stxname));
     460         732 :         entry->stattarget = staForm->stxstattarget;
     461        2028 :         for (i = 0; i < staForm->stxkeys.dim1; i++)
     462             :         {
     463        1296 :             entry->columns = bms_add_member(entry->columns,
     464        1296 :                                             staForm->stxkeys.values[i]);
     465             :         }
     466             : 
     467             :         /* decode the stxkind char array into a list of chars */
     468         732 :         datum = SysCacheGetAttrNotNull(STATEXTOID, htup,
     469             :                                        Anum_pg_statistic_ext_stxkind);
     470         732 :         arr = DatumGetArrayTypeP(datum);
     471         732 :         if (ARR_NDIM(arr) != 1 ||
     472         732 :             ARR_HASNULL(arr) ||
     473         732 :             ARR_ELEMTYPE(arr) != CHAROID)
     474           0 :             elog(ERROR, "stxkind is not a 1-D char array");
     475         732 :         enabled = (char *) ARR_DATA_PTR(arr);
     476        2052 :         for (i = 0; i < ARR_DIMS(arr)[0]; i++)
     477             :         {
     478             :             Assert((enabled[i] == STATS_EXT_NDISTINCT) ||
     479             :                    (enabled[i] == STATS_EXT_DEPENDENCIES) ||
     480             :                    (enabled[i] == STATS_EXT_MCV) ||
     481             :                    (enabled[i] == STATS_EXT_EXPRESSIONS));
     482        1320 :             entry->types = lappend_int(entry->types, (int) enabled[i]);
     483             :         }
     484             : 
     485             :         /* decode expression (if any) */
     486         732 :         datum = SysCacheGetAttr(STATEXTOID, htup,
     487             :                                 Anum_pg_statistic_ext_stxexprs, &isnull);
     488             : 
     489         732 :         if (!isnull)
     490             :         {
     491             :             char       *exprsString;
     492             : 
     493         300 :             exprsString = TextDatumGetCString(datum);
     494         300 :             exprs = (List *) stringToNode(exprsString);
     495             : 
     496         300 :             pfree(exprsString);
     497             : 
     498             :             /*
     499             :              * Run the expressions through eval_const_expressions. This is not
     500             :              * just an optimization, but is necessary, because the planner
     501             :              * will be comparing them to similarly-processed qual clauses, and
     502             :              * may fail to detect valid matches without this.  We must not use
     503             :              * canonicalize_qual, however, since these aren't qual
     504             :              * expressions.
     505             :              */
     506         300 :             exprs = (List *) eval_const_expressions(NULL, (Node *) exprs);
     507             : 
     508             :             /* May as well fix opfuncids too */
     509         300 :             fix_opfuncids((Node *) exprs);
     510             :         }
     511             : 
     512         732 :         entry->exprs = exprs;
     513             : 
     514         732 :         result = lappend(result, entry);
     515             :     }
     516             : 
     517       18944 :     systable_endscan(scan);
     518             : 
     519       18944 :     return result;
     520             : }
     521             : 
     522             : /*
     523             :  * examine_attribute -- pre-analysis of a single column
     524             :  *
     525             :  * Determine whether the column is analyzable; if so, create and initialize
     526             :  * a VacAttrStats struct for it.  If not, return NULL.
     527             :  */
     528             : static VacAttrStats *
     529         576 : examine_attribute(Node *expr)
     530             : {
     531             :     HeapTuple   typtuple;
     532             :     VacAttrStats *stats;
     533             :     int         i;
     534             :     bool        ok;
     535             : 
     536             :     /*
     537             :      * Create the VacAttrStats struct.
     538             :      */
     539         576 :     stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));
     540         576 :     stats->attstattarget = -1;
     541             : 
     542             :     /*
     543             :      * When analyzing an expression, believe the expression tree's type not
     544             :      * the column datatype --- the latter might be the opckeytype storage type
     545             :      * of the opclass, which is not interesting for our purposes.  (Note: if
     546             :      * we did anything with non-expression statistics columns, we'd need to
     547             :      * figure out where to get the correct type info from, but for now that's
     548             :      * not a problem.)  It's not clear whether anyone will care about the
     549             :      * typmod, but we store that too just in case.
     550             :      */
     551         576 :     stats->attrtypid = exprType(expr);
     552         576 :     stats->attrtypmod = exprTypmod(expr);
     553         576 :     stats->attrcollid = exprCollation(expr);
     554             : 
     555         576 :     typtuple = SearchSysCacheCopy1(TYPEOID,
     556             :                                    ObjectIdGetDatum(stats->attrtypid));
     557         576 :     if (!HeapTupleIsValid(typtuple))
     558           0 :         elog(ERROR, "cache lookup failed for type %u", stats->attrtypid);
     559         576 :     stats->attrtype = (Form_pg_type) GETSTRUCT(typtuple);
     560             : 
     561             :     /*
     562             :      * We don't actually analyze individual attributes, so no need to set the
     563             :      * memory context.
     564             :      */
     565         576 :     stats->anl_context = NULL;
     566         576 :     stats->tupattnum = InvalidAttrNumber;
     567             : 
     568             :     /*
     569             :      * The fields describing the stats->stavalues[n] element types default to
     570             :      * the type of the data being analyzed, but the type-specific typanalyze
     571             :      * function can change them if it wants to store something else.
     572             :      */
     573        3456 :     for (i = 0; i < STATISTIC_NUM_SLOTS; i++)
     574             :     {
     575        2880 :         stats->statypid[i] = stats->attrtypid;
     576        2880 :         stats->statyplen[i] = stats->attrtype->typlen;
     577        2880 :         stats->statypbyval[i] = stats->attrtype->typbyval;
     578        2880 :         stats->statypalign[i] = stats->attrtype->typalign;
     579             :     }
     580             : 
     581             :     /*
     582             :      * Call the type-specific typanalyze function.  If none is specified, use
     583             :      * std_typanalyze().
     584             :      */
     585         576 :     if (OidIsValid(stats->attrtype->typanalyze))
     586           0 :         ok = DatumGetBool(OidFunctionCall1(stats->attrtype->typanalyze,
     587             :                                            PointerGetDatum(stats)));
     588             :     else
     589         576 :         ok = std_typanalyze(stats);
     590             : 
     591         576 :     if (!ok || stats->compute_stats == NULL || stats->minrows <= 0)
     592             :     {
     593           0 :         heap_freetuple(typtuple);
     594           0 :         pfree(stats);
     595           0 :         return NULL;
     596             :     }
     597             : 
     598         576 :     return stats;
     599             : }
     600             : 
     601             : /*
     602             :  * examine_expression -- pre-analysis of a single expression
     603             :  *
     604             :  * Determine whether the expression is analyzable; if so, create and initialize
     605             :  * a VacAttrStats struct for it.  If not, return NULL.
     606             :  */
     607             : static VacAttrStats *
     608         576 : examine_expression(Node *expr, int stattarget)
     609             : {
     610             :     HeapTuple   typtuple;
     611             :     VacAttrStats *stats;
     612             :     int         i;
     613             :     bool        ok;
     614             : 
     615             :     Assert(expr != NULL);
     616             : 
     617             :     /*
     618             :      * Create the VacAttrStats struct.
     619             :      */
     620         576 :     stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));
     621             : 
     622             :     /*
     623             :      * We can't have statistics target specified for the expression, so we
     624             :      * could use either the default_statistics_target, or the target computed
     625             :      * for the extended statistics. The second option seems more reasonable.
     626             :      */
     627         576 :     stats->attstattarget = stattarget;
     628             : 
     629             :     /*
     630             :      * When analyzing an expression, believe the expression tree's type.
     631             :      */
     632         576 :     stats->attrtypid = exprType(expr);
     633         576 :     stats->attrtypmod = exprTypmod(expr);
     634             : 
     635             :     /*
     636             :      * We don't allow collation to be specified in CREATE STATISTICS, so we
     637             :      * have to use the collation specified for the expression. It's possible
     638             :      * to specify the collation in the expression "(col COLLATE "en_US")" in
     639             :      * which case exprCollation() does the right thing.
     640             :      */
     641         576 :     stats->attrcollid = exprCollation(expr);
     642             : 
     643         576 :     typtuple = SearchSysCacheCopy1(TYPEOID,
     644             :                                    ObjectIdGetDatum(stats->attrtypid));
     645         576 :     if (!HeapTupleIsValid(typtuple))
     646           0 :         elog(ERROR, "cache lookup failed for type %u", stats->attrtypid);
     647             : 
     648         576 :     stats->attrtype = (Form_pg_type) GETSTRUCT(typtuple);
     649         576 :     stats->anl_context = CurrentMemoryContext;   /* XXX should be using
     650             :                                                  * something else? */
     651         576 :     stats->tupattnum = InvalidAttrNumber;
     652             : 
     653             :     /*
     654             :      * The fields describing the stats->stavalues[n] element types default to
     655             :      * the type of the data being analyzed, but the type-specific typanalyze
     656             :      * function can change them if it wants to store something else.
     657             :      */
     658        3456 :     for (i = 0; i < STATISTIC_NUM_SLOTS; i++)
     659             :     {
     660        2880 :         stats->statypid[i] = stats->attrtypid;
     661        2880 :         stats->statyplen[i] = stats->attrtype->typlen;
     662        2880 :         stats->statypbyval[i] = stats->attrtype->typbyval;
     663        2880 :         stats->statypalign[i] = stats->attrtype->typalign;
     664             :     }
     665             : 
     666             :     /*
     667             :      * Call the type-specific typanalyze function.  If none is specified, use
     668             :      * std_typanalyze().
     669             :      */
     670         576 :     if (OidIsValid(stats->attrtype->typanalyze))
     671           0 :         ok = DatumGetBool(OidFunctionCall1(stats->attrtype->typanalyze,
     672             :                                            PointerGetDatum(stats)));
     673             :     else
     674         576 :         ok = std_typanalyze(stats);
     675             : 
     676         576 :     if (!ok || stats->compute_stats == NULL || stats->minrows <= 0)
     677             :     {
     678           0 :         heap_freetuple(typtuple);
     679           0 :         pfree(stats);
     680           0 :         return NULL;
     681             :     }
     682             : 
     683         576 :     return stats;
     684             : }
     685             : 
     686             : /*
     687             :  * Using 'vacatts' of size 'nvacatts' as input data, return a newly-built
     688             :  * VacAttrStats array which includes only the items corresponding to
     689             :  * attributes indicated by 'attrs'.  If we don't have all of the per-column
     690             :  * stats available to compute the extended stats, then we return NULL to
     691             :  * indicate to the caller that the stats should not be built.
     692             :  */
     693             : static VacAttrStats **
     694         732 : lookup_var_attr_stats(Relation rel, Bitmapset *attrs, List *exprs,
     695             :                       int nvacatts, VacAttrStats **vacatts)
     696             : {
     697         732 :     int         i = 0;
     698         732 :     int         x = -1;
     699             :     int         natts;
     700             :     VacAttrStats **stats;
     701             :     ListCell   *lc;
     702             : 
     703         732 :     natts = bms_num_members(attrs) + list_length(exprs);
     704             : 
     705         732 :     stats = (VacAttrStats **) palloc(natts * sizeof(VacAttrStats *));
     706             : 
     707             :     /* lookup VacAttrStats info for the requested columns (same attnum) */
     708        1992 :     while ((x = bms_next_member(attrs, x)) >= 0)
     709             :     {
     710             :         int         j;
     711             : 
     712        1284 :         stats[i] = NULL;
     713        4080 :         for (j = 0; j < nvacatts; j++)
     714             :         {
     715        4056 :             if (x == vacatts[j]->tupattnum)
     716             :             {
     717        1260 :                 stats[i] = vacatts[j];
     718        1260 :                 break;
     719             :             }
     720             :         }
     721             : 
     722        1284 :         if (!stats[i])
     723             :         {
     724             :             /*
     725             :              * Looks like stats were not gathered for one of the columns
     726             :              * required. We'll be unable to build the extended stats without
     727             :              * this column.
     728             :              */
     729          24 :             pfree(stats);
     730          24 :             return NULL;
     731             :         }
     732             : 
     733        1260 :         i++;
     734             :     }
     735             : 
     736             :     /* also add info for expressions */
     737        1284 :     foreach(lc, exprs)
     738             :     {
     739         576 :         Node       *expr = (Node *) lfirst(lc);
     740             : 
     741         576 :         stats[i] = examine_attribute(expr);
     742             : 
     743             :         /*
     744             :          * XXX We need tuple descriptor later, and we just grab it from
     745             :          * stats[0]->tupDesc (see e.g. statext_mcv_build). But as coded
     746             :          * examine_attribute does not set that, so just grab it from the first
     747             :          * vacatts element.
     748             :          */
     749         576 :         stats[i]->tupDesc = vacatts[0]->tupDesc;
     750             : 
     751         576 :         i++;
     752             :     }
     753             : 
     754         708 :     return stats;
     755             : }
     756             : 
     757             : /*
     758             :  * statext_store
     759             :  *  Serializes the statistics and stores them into the pg_statistic_ext_data
     760             :  *  tuple.
     761             :  */
     762             : static void
     763         348 : statext_store(Oid statOid, bool inh,
     764             :               MVNDistinct *ndistinct, MVDependencies *dependencies,
     765             :               MCVList *mcv, Datum exprs, VacAttrStats **stats)
     766             : {
     767             :     Relation    pg_stextdata;
     768             :     HeapTuple   stup;
     769             :     Datum       values[Natts_pg_statistic_ext_data];
     770             :     bool        nulls[Natts_pg_statistic_ext_data];
     771             : 
     772         348 :     pg_stextdata = table_open(StatisticExtDataRelationId, RowExclusiveLock);
     773             : 
     774         348 :     memset(nulls, true, sizeof(nulls));
     775         348 :     memset(values, 0, sizeof(values));
     776             : 
     777             :     /* basic info */
     778         348 :     values[Anum_pg_statistic_ext_data_stxoid - 1] = ObjectIdGetDatum(statOid);
     779         348 :     nulls[Anum_pg_statistic_ext_data_stxoid - 1] = false;
     780             : 
     781         348 :     values[Anum_pg_statistic_ext_data_stxdinherit - 1] = BoolGetDatum(inh);
     782         348 :     nulls[Anum_pg_statistic_ext_data_stxdinherit - 1] = false;
     783             : 
     784             :     /*
     785             :      * Construct a new pg_statistic_ext_data tuple, replacing the calculated
     786             :      * stats.
     787             :      */
     788         348 :     if (ndistinct != NULL)
     789             :     {
     790         156 :         bytea      *data = statext_ndistinct_serialize(ndistinct);
     791             : 
     792         156 :         nulls[Anum_pg_statistic_ext_data_stxdndistinct - 1] = (data == NULL);
     793         156 :         values[Anum_pg_statistic_ext_data_stxdndistinct - 1] = PointerGetDatum(data);
     794             :     }
     795             : 
     796         348 :     if (dependencies != NULL)
     797             :     {
     798         102 :         bytea      *data = statext_dependencies_serialize(dependencies);
     799             : 
     800         102 :         nulls[Anum_pg_statistic_ext_data_stxddependencies - 1] = (data == NULL);
     801         102 :         values[Anum_pg_statistic_ext_data_stxddependencies - 1] = PointerGetDatum(data);
     802             :     }
     803         348 :     if (mcv != NULL)
     804             :     {
     805         180 :         bytea      *data = statext_mcv_serialize(mcv, stats);
     806             : 
     807         180 :         nulls[Anum_pg_statistic_ext_data_stxdmcv - 1] = (data == NULL);
     808         180 :         values[Anum_pg_statistic_ext_data_stxdmcv - 1] = PointerGetDatum(data);
     809             :     }
     810         348 :     if (exprs != (Datum) 0)
     811             :     {
     812         150 :         nulls[Anum_pg_statistic_ext_data_stxdexpr - 1] = false;
     813         150 :         values[Anum_pg_statistic_ext_data_stxdexpr - 1] = exprs;
     814             :     }
     815             : 
     816             :     /*
     817             :      * Delete the old tuple if it exists, and insert a new one. It's easier
     818             :      * than trying to update or insert, based on various conditions.
     819             :      */
     820         348 :     RemoveStatisticsDataById(statOid, inh);
     821             : 
     822             :     /* form and insert a new tuple */
     823         348 :     stup = heap_form_tuple(RelationGetDescr(pg_stextdata), values, nulls);
     824         348 :     CatalogTupleInsert(pg_stextdata, stup);
     825             : 
     826         348 :     heap_freetuple(stup);
     827             : 
     828         348 :     table_close(pg_stextdata, RowExclusiveLock);
     829         348 : }
     830             : 
     831             : /* initialize multi-dimensional sort */
     832             : MultiSortSupport
     833        1260 : multi_sort_init(int ndims)
     834             : {
     835             :     MultiSortSupport mss;
     836             : 
     837             :     Assert(ndims >= 2);
     838             : 
     839        1260 :     mss = (MultiSortSupport) palloc0(offsetof(MultiSortSupportData, ssup)
     840        1260 :                                      + sizeof(SortSupportData) * ndims);
     841             : 
     842        1260 :     mss->ndims = ndims;
     843             : 
     844        1260 :     return mss;
     845             : }
     846             : 
     847             : /*
     848             :  * Prepare sort support info using the given sort operator and collation
     849             :  * at the position 'sortdim'
     850             :  */
     851             : void
     852        2994 : multi_sort_add_dimension(MultiSortSupport mss, int sortdim,
     853             :                          Oid oper, Oid collation)
     854             : {
     855        2994 :     SortSupport ssup = &mss->ssup[sortdim];
     856             : 
     857        2994 :     ssup->ssup_cxt = CurrentMemoryContext;
     858        2994 :     ssup->ssup_collation = collation;
     859        2994 :     ssup->ssup_nulls_first = false;
     860             : 
     861        2994 :     PrepareSortSupportFromOrderingOp(oper, ssup);
     862        2994 : }
     863             : 
     864             : /* compare all the dimensions in the selected order */
     865             : int
     866    15215334 : multi_sort_compare(const void *a, const void *b, void *arg)
     867             : {
     868    15215334 :     MultiSortSupport mss = (MultiSortSupport) arg;
     869    15215334 :     SortItem   *ia = (SortItem *) a;
     870    15215334 :     SortItem   *ib = (SortItem *) b;
     871             :     int         i;
     872             : 
     873    27545556 :     for (i = 0; i < mss->ndims; i++)
     874             :     {
     875             :         int         compare;
     876             : 
     877    23966712 :         compare = ApplySortComparator(ia->values[i], ia->isnull[i],
     878    23966712 :                                       ib->values[i], ib->isnull[i],
     879    23966712 :                                       &mss->ssup[i]);
     880             : 
     881    23966712 :         if (compare != 0)
     882    11636490 :             return compare;
     883             :     }
     884             : 
     885             :     /* equal by default */
     886     3578844 :     return 0;
     887             : }
     888             : 
     889             : /* compare selected dimension */
     890             : int
     891     1472580 : multi_sort_compare_dim(int dim, const SortItem *a, const SortItem *b,
     892             :                        MultiSortSupport mss)
     893             : {
     894     2945160 :     return ApplySortComparator(a->values[dim], a->isnull[dim],
     895     1472580 :                                b->values[dim], b->isnull[dim],
     896     1472580 :                                &mss->ssup[dim]);
     897             : }
     898             : 
     899             : int
     900     1504218 : multi_sort_compare_dims(int start, int end,
     901             :                         const SortItem *a, const SortItem *b,
     902             :                         MultiSortSupport mss)
     903             : {
     904             :     int         dim;
     905             : 
     906     3403332 :     for (dim = start; dim <= end; dim++)
     907             :     {
     908     1930752 :         int         r = ApplySortComparator(a->values[dim], a->isnull[dim],
     909     1930752 :                                             b->values[dim], b->isnull[dim],
     910     1930752 :                                             &mss->ssup[dim]);
     911             : 
     912     1930752 :         if (r != 0)
     913       31638 :             return r;
     914             :     }
     915             : 
     916     1472580 :     return 0;
     917             : }
     918             : 
     919             : int
     920      187380 : compare_scalars_simple(const void *a, const void *b, void *arg)
     921             : {
     922      187380 :     return compare_datums_simple(*(Datum *) a,
     923             :                                  *(Datum *) b,
     924             :                                  (SortSupport) arg);
     925             : }
     926             : 
     927             : int
     928      211068 : compare_datums_simple(Datum a, Datum b, SortSupport ssup)
     929             : {
     930      211068 :     return ApplySortComparator(a, false, b, false, ssup);
     931             : }
     932             : 
     933             : /*
     934             :  * build_attnums_array
     935             :  *      Transforms a bitmap into an array of AttrNumber values.
     936             :  *
     937             :  * This is used for extended statistics only, so all the attributes must be
     938             :  * user-defined. That means offsetting by FirstLowInvalidHeapAttributeNumber
     939             :  * is not necessary here (and when querying the bitmap).
     940             :  */
     941             : AttrNumber *
     942           0 : build_attnums_array(Bitmapset *attrs, int nexprs, int *numattrs)
     943             : {
     944             :     int         i,
     945             :                 j;
     946             :     AttrNumber *attnums;
     947           0 :     int         num = bms_num_members(attrs);
     948             : 
     949           0 :     if (numattrs)
     950           0 :         *numattrs = num;
     951             : 
     952             :     /* build attnums from the bitmapset */
     953           0 :     attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * num);
     954           0 :     i = 0;
     955           0 :     j = -1;
     956           0 :     while ((j = bms_next_member(attrs, j)) >= 0)
     957             :     {
     958           0 :         int         attnum = (j - nexprs);
     959             : 
     960             :         /*
     961             :          * Make sure the bitmap contains only user-defined attributes. As
     962             :          * bitmaps can't contain negative values, this can be violated in two
     963             :          * ways. Firstly, the bitmap might contain 0 as a member, and secondly
     964             :          * the integer value might be larger than MaxAttrNumber.
     965             :          */
     966             :         Assert(AttributeNumberIsValid(attnum));
     967             :         Assert(attnum <= MaxAttrNumber);
     968             :         Assert(attnum >= (-nexprs));
     969             : 
     970           0 :         attnums[i++] = (AttrNumber) attnum;
     971             : 
     972             :         /* protect against overflows */
     973             :         Assert(i <= num);
     974             :     }
     975             : 
     976           0 :     return attnums;
     977             : }
     978             : 
     979             : /*
     980             :  * build_sorted_items
     981             :  *      build a sorted array of SortItem with values from rows
     982             :  *
     983             :  * Note: All the memory is allocated in a single chunk, so that the caller
     984             :  * can simply pfree the return value to release all of it.
     985             :  */
     986             : SortItem *
     987         756 : build_sorted_items(StatsBuildData *data, int *nitems,
     988             :                    MultiSortSupport mss,
     989             :                    int numattrs, AttrNumber *attnums)
     990             : {
     991             :     int         i,
     992             :                 j,
     993             :                 len,
     994             :                 nrows;
     995         756 :     int         nvalues = data->numrows * numattrs;
     996             : 
     997             :     SortItem   *items;
     998             :     Datum      *values;
     999             :     bool       *isnull;
    1000             :     char       *ptr;
    1001             :     int        *typlen;
    1002             : 
    1003             :     /* Compute the total amount of memory we need (both items and values). */
    1004         756 :     len = data->numrows * sizeof(SortItem) + nvalues * (sizeof(Datum) + sizeof(bool));
    1005             : 
    1006             :     /* Allocate the memory and split it into the pieces. */
    1007         756 :     ptr = palloc0(len);
    1008             : 
    1009             :     /* items to sort */
    1010         756 :     items = (SortItem *) ptr;
    1011         756 :     ptr += data->numrows * sizeof(SortItem);
    1012             : 
    1013             :     /* values and null flags */
    1014         756 :     values = (Datum *) ptr;
    1015         756 :     ptr += nvalues * sizeof(Datum);
    1016             : 
    1017         756 :     isnull = (bool *) ptr;
    1018         756 :     ptr += nvalues * sizeof(bool);
    1019             : 
    1020             :     /* make sure we consumed the whole buffer exactly */
    1021             :     Assert((ptr - (char *) items) == len);
    1022             : 
    1023             :     /* fix the pointers to Datum and bool arrays */
    1024         756 :     nrows = 0;
    1025     1964568 :     for (i = 0; i < data->numrows; i++)
    1026             :     {
    1027     1963812 :         items[nrows].values = &values[nrows * numattrs];
    1028     1963812 :         items[nrows].isnull = &isnull[nrows * numattrs];
    1029             : 
    1030     1963812 :         nrows++;
    1031             :     }
    1032             : 
    1033             :     /* build a local cache of typlen for all attributes */
    1034         756 :     typlen = (int *) palloc(sizeof(int) * data->nattnums);
    1035        2850 :     for (i = 0; i < data->nattnums; i++)
    1036        2094 :         typlen[i] = get_typlen(data->stats[i]->attrtypid);
    1037             : 
    1038         756 :     nrows = 0;
    1039     1964568 :     for (i = 0; i < data->numrows; i++)
    1040             :     {
    1041     1963812 :         bool        toowide = false;
    1042             : 
    1043             :         /* load the values/null flags from sample rows */
    1044     6768012 :         for (j = 0; j < numattrs; j++)
    1045             :         {
    1046             :             Datum       value;
    1047             :             bool        isnull;
    1048             :             int         attlen;
    1049     4804200 :             AttrNumber  attnum = attnums[j];
    1050             : 
    1051             :             int         idx;
    1052             : 
    1053             :             /* match attnum to the pre-calculated data */
    1054     9493128 :             for (idx = 0; idx < data->nattnums; idx++)
    1055             :             {
    1056     9493128 :                 if (attnum == data->attnums[idx])
    1057     4804200 :                     break;
    1058             :             }
    1059             : 
    1060             :             Assert(idx < data->nattnums);
    1061             : 
    1062     4804200 :             value = data->values[idx][i];
    1063     4804200 :             isnull = data->nulls[idx][i];
    1064     4804200 :             attlen = typlen[idx];
    1065             : 
    1066             :             /*
    1067             :              * If this is a varlena value, check if it's too wide and if yes
    1068             :              * then skip the whole item. Otherwise detoast the value.
    1069             :              *
    1070             :              * XXX It may happen that we've already detoasted some preceding
    1071             :              * values for the current item. We don't bother to cleanup those
    1072             :              * on the assumption that those are small (below WIDTH_THRESHOLD)
    1073             :              * and will be discarded at the end of analyze.
    1074             :              */
    1075     4804200 :             if ((!isnull) && (attlen == -1))
    1076             :             {
    1077     1480200 :                 if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
    1078             :                 {
    1079           0 :                     toowide = true;
    1080           0 :                     break;
    1081             :                 }
    1082             : 
    1083     1480200 :                 value = PointerGetDatum(PG_DETOAST_DATUM(value));
    1084             :             }
    1085             : 
    1086     4804200 :             items[nrows].values[j] = value;
    1087     4804200 :             items[nrows].isnull[j] = isnull;
    1088             :         }
    1089             : 
    1090     1963812 :         if (toowide)
    1091           0 :             continue;
    1092             : 
    1093     1963812 :         nrows++;
    1094             :     }
    1095             : 
    1096             :     /* store the actual number of items (ignoring the too-wide ones) */
    1097         756 :     *nitems = nrows;
    1098             : 
    1099             :     /* all items were too wide */
    1100         756 :     if (nrows == 0)
    1101             :     {
    1102             :         /* everything is allocated as a single chunk */
    1103           0 :         pfree(items);
    1104           0 :         return NULL;
    1105             :     }
    1106             : 
    1107             :     /* do the sort, using the multi-sort */
    1108         756 :     qsort_interruptible(items, nrows, sizeof(SortItem),
    1109             :                         multi_sort_compare, mss);
    1110             : 
    1111         756 :     return items;
    1112             : }
    1113             : 
    1114             : /*
    1115             :  * has_stats_of_kind
    1116             :  *      Check whether the list contains statistic of a given kind
    1117             :  */
    1118             : bool
    1119        3648 : has_stats_of_kind(List *stats, char requiredkind)
    1120             : {
    1121             :     ListCell   *l;
    1122             : 
    1123        6114 :     foreach(l, stats)
    1124             :     {
    1125        4284 :         StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
    1126             : 
    1127        4284 :         if (stat->kind == requiredkind)
    1128        1818 :             return true;
    1129             :     }
    1130             : 
    1131        1830 :     return false;
    1132             : }
    1133             : 
    1134             : /*
    1135             :  * stat_find_expression
    1136             :  *      Search for an expression in statistics object's list of expressions.
    1137             :  *
    1138             :  * Returns the index of the expression in the statistics object's list of
    1139             :  * expressions, or -1 if not found.
    1140             :  */
    1141             : static int
    1142         516 : stat_find_expression(StatisticExtInfo *stat, Node *expr)
    1143             : {
    1144             :     ListCell   *lc;
    1145             :     int         idx;
    1146             : 
    1147         516 :     idx = 0;
    1148         996 :     foreach(lc, stat->exprs)
    1149             :     {
    1150         972 :         Node       *stat_expr = (Node *) lfirst(lc);
    1151             : 
    1152         972 :         if (equal(stat_expr, expr))
    1153         492 :             return idx;
    1154         480 :         idx++;
    1155             :     }
    1156             : 
    1157             :     /* Expression not found */
    1158          24 :     return -1;
    1159             : }
    1160             : 
    1161             : /*
    1162             :  * stat_covers_expressions
    1163             :  *      Test whether a statistics object covers all expressions in a list.
    1164             :  *
    1165             :  * Returns true if all expressions are covered.  If expr_idxs is non-NULL, it
    1166             :  * is populated with the indexes of the expressions found.
    1167             :  */
    1168             : static bool
    1169        2388 : stat_covers_expressions(StatisticExtInfo *stat, List *exprs,
    1170             :                         Bitmapset **expr_idxs)
    1171             : {
    1172             :     ListCell   *lc;
    1173             : 
    1174        2880 :     foreach(lc, exprs)
    1175             :     {
    1176         516 :         Node       *expr = (Node *) lfirst(lc);
    1177             :         int         expr_idx;
    1178             : 
    1179         516 :         expr_idx = stat_find_expression(stat, expr);
    1180         516 :         if (expr_idx == -1)
    1181          24 :             return false;
    1182             : 
    1183         492 :         if (expr_idxs != NULL)
    1184         246 :             *expr_idxs = bms_add_member(*expr_idxs, expr_idx);
    1185             :     }
    1186             : 
    1187             :     /* If we reach here, all expressions are covered */
    1188        2364 :     return true;
    1189             : }
    1190             : 
    1191             : /*
    1192             :  * choose_best_statistics
    1193             :  *      Look for and return statistics with the specified 'requiredkind' which
    1194             :  *      have keys that match at least two of the given attnums.  Return NULL if
    1195             :  *      there's no match.
    1196             :  *
    1197             :  * The current selection criteria is very simple - we choose the statistics
    1198             :  * object referencing the most attributes in covered (and still unestimated
    1199             :  * clauses), breaking ties in favor of objects with fewer keys overall.
    1200             :  *
    1201             :  * The clause_attnums is an array of bitmaps, storing attnums for individual
    1202             :  * clauses. A NULL element means the clause is either incompatible or already
    1203             :  * estimated.
    1204             :  *
    1205             :  * XXX If multiple statistics objects tie on both criteria, then which object
    1206             :  * is chosen depends on the order that they appear in the stats list. Perhaps
    1207             :  * further tiebreakers are needed.
    1208             :  */
    1209             : StatisticExtInfo *
    1210         978 : choose_best_statistics(List *stats, char requiredkind, bool inh,
    1211             :                        Bitmapset **clause_attnums, List **clause_exprs,
    1212             :                        int nclauses)
    1213             : {
    1214             :     ListCell   *lc;
    1215         978 :     StatisticExtInfo *best_match = NULL;
    1216         978 :     int         best_num_matched = 2;   /* goal #1: maximize */
    1217         978 :     int         best_match_keys = (STATS_MAX_DIMENSIONS + 1);   /* goal #2: minimize */
    1218             : 
    1219        2550 :     foreach(lc, stats)
    1220             :     {
    1221             :         int         i;
    1222        1572 :         StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
    1223        1572 :         Bitmapset  *matched_attnums = NULL;
    1224        1572 :         Bitmapset  *matched_exprs = NULL;
    1225             :         int         num_matched;
    1226             :         int         numkeys;
    1227             : 
    1228             :         /* skip statistics that are not of the correct type */
    1229        1572 :         if (info->kind != requiredkind)
    1230         468 :             continue;
    1231             : 
    1232             :         /* skip statistics with mismatching inheritance flag */
    1233        1104 :         if (info->inherit != inh)
    1234          24 :             continue;
    1235             : 
    1236             :         /*
    1237             :          * Collect attributes and expressions in remaining (unestimated)
    1238             :          * clauses fully covered by this statistic object.
    1239             :          *
    1240             :          * We know already estimated clauses have both clause_attnums and
    1241             :          * clause_exprs set to NULL. We leave the pointers NULL if already
    1242             :          * estimated, or we reset them to NULL after estimating the clause.
    1243             :          */
    1244        3864 :         for (i = 0; i < nclauses; i++)
    1245             :         {
    1246        2784 :             Bitmapset  *expr_idxs = NULL;
    1247             : 
    1248             :             /* ignore incompatible/estimated clauses */
    1249        2784 :             if (!clause_attnums[i] && !clause_exprs[i])
    1250        1572 :                 continue;
    1251             : 
    1252             :             /* ignore clauses that are not covered by this object */
    1253        1422 :             if (!bms_is_subset(clause_attnums[i], info->keys) ||
    1254        1230 :                 !stat_covers_expressions(info, clause_exprs[i], &expr_idxs))
    1255         210 :                 continue;
    1256             : 
    1257             :             /* record attnums and indexes of expressions covered */
    1258        1212 :             matched_attnums = bms_add_members(matched_attnums, clause_attnums[i]);
    1259        1212 :             matched_exprs = bms_add_members(matched_exprs, expr_idxs);
    1260             :         }
    1261             : 
    1262        1080 :         num_matched = bms_num_members(matched_attnums) + bms_num_members(matched_exprs);
    1263             : 
    1264        1080 :         bms_free(matched_attnums);
    1265        1080 :         bms_free(matched_exprs);
    1266             : 
    1267             :         /*
    1268             :          * save the actual number of keys in the stats so that we can choose
    1269             :          * the narrowest stats with the most matching keys.
    1270             :          */
    1271        1080 :         numkeys = bms_num_members(info->keys) + list_length(info->exprs);
    1272             : 
    1273             :         /*
    1274             :          * Use this object when it increases the number of matched attributes
    1275             :          * and expressions or when it matches the same number of attributes
    1276             :          * and expressions but these stats have fewer keys than any previous
    1277             :          * match.
    1278             :          */
    1279        1080 :         if (num_matched > best_num_matched ||
    1280         282 :             (num_matched == best_num_matched && numkeys < best_match_keys))
    1281             :         {
    1282         480 :             best_match = info;
    1283         480 :             best_num_matched = num_matched;
    1284         480 :             best_match_keys = numkeys;
    1285             :         }
    1286             :     }
    1287             : 
    1288         978 :     return best_match;
    1289             : }
    1290             : 
    1291             : /*
    1292             :  * statext_is_compatible_clause_internal
    1293             :  *      Determines if the clause is compatible with MCV lists.
    1294             :  *
    1295             :  * To be compatible, the given clause must be a combination of supported
    1296             :  * clauses built from Vars or sub-expressions (where a sub-expression is
    1297             :  * something that exactly matches an expression found in statistics objects).
    1298             :  * This function recursively examines the clause and extracts any
    1299             :  * sub-expressions that will need to be matched against statistics.
    1300             :  *
    1301             :  * Currently, we only support the following types of clauses:
    1302             :  *
    1303             :  * (a) OpExprs of the form (Var/Expr op Const), or (Const op Var/Expr), where
    1304             :  * the op is one of ("=", "<", ">", ">=", "<=")
    1305             :  *
    1306             :  * (b) (Var/Expr IS [NOT] NULL)
    1307             :  *
    1308             :  * (c) combinations using AND/OR/NOT
    1309             :  *
    1310             :  * (d) ScalarArrayOpExprs of the form (Var/Expr op ANY (Const)) or
    1311             :  * (Var/Expr op ALL (Const))
    1312             :  *
    1313             :  * In the future, the range of supported clauses may be expanded to more
    1314             :  * complex cases, for example (Var op Var).
    1315             :  *
    1316             :  * Arguments:
    1317             :  * clause: (sub)clause to be inspected (bare clause, not a RestrictInfo)
    1318             :  * relid: rel that all Vars in clause must belong to
    1319             :  * *attnums: input/output parameter collecting attribute numbers of all
    1320             :  *      mentioned Vars.  Note that we do not offset the attribute numbers,
    1321             :  *      so we can't cope with system columns.
    1322             :  * *exprs: input/output parameter collecting primitive subclauses within
    1323             :  *      the clause tree
    1324             :  *
    1325             :  * Returns false if there is something we definitively can't handle.
    1326             :  * On true return, we can proceed to match the *exprs against statistics.
    1327             :  */
    1328             : static bool
    1329        2364 : statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
    1330             :                                       Index relid, Bitmapset **attnums,
    1331             :                                       List **exprs)
    1332             : {
    1333             :     /* Look inside any binary-compatible relabeling (as in examine_variable) */
    1334        2364 :     if (IsA(clause, RelabelType))
    1335           0 :         clause = (Node *) ((RelabelType *) clause)->arg;
    1336             : 
    1337             :     /* plain Var references (boolean Vars or recursive checks) */
    1338        2364 :     if (IsA(clause, Var))
    1339             :     {
    1340        1068 :         Var        *var = (Var *) clause;
    1341             : 
    1342             :         /* Ensure var is from the correct relation */
    1343        1068 :         if (var->varno != relid)
    1344           0 :             return false;
    1345             : 
    1346             :         /* we also better ensure the Var is from the current level */
    1347        1068 :         if (var->varlevelsup > 0)
    1348           0 :             return false;
    1349             : 
    1350             :         /*
    1351             :          * Also reject system attributes and whole-row Vars (we don't allow
    1352             :          * stats on those).
    1353             :          */
    1354        1068 :         if (!AttrNumberIsForUserDefinedAttr(var->varattno))
    1355           0 :             return false;
    1356             : 
    1357             :         /* OK, record the attnum for later permissions checks. */
    1358        1068 :         *attnums = bms_add_member(*attnums, var->varattno);
    1359             : 
    1360        1068 :         return true;
    1361             :     }
    1362             : 
    1363             :     /* (Var/Expr op Const) or (Const op Var/Expr) */
    1364        1296 :     if (is_opclause(clause))
    1365             :     {
    1366         936 :         RangeTblEntry *rte = root->simple_rte_array[relid];
    1367         936 :         OpExpr     *expr = (OpExpr *) clause;
    1368             :         Node       *clause_expr;
    1369             : 
    1370             :         /* Only expressions with two arguments are considered compatible. */
    1371         936 :         if (list_length(expr->args) != 2)
    1372           0 :             return false;
    1373             : 
    1374             :         /* Check if the expression has the right shape */
    1375         936 :         if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
    1376           0 :             return false;
    1377             : 
    1378             :         /*
    1379             :          * If it's not one of the supported operators ("=", "<", ">", etc.),
    1380             :          * just ignore the clause, as it's not compatible with MCV lists.
    1381             :          *
    1382             :          * This uses the function for estimating selectivity, not the operator
    1383             :          * directly (a bit awkward, but well ...).
    1384             :          */
    1385         936 :         switch (get_oprrest(expr->opno))
    1386             :         {
    1387         936 :             case F_EQSEL:
    1388             :             case F_NEQSEL:
    1389             :             case F_SCALARLTSEL:
    1390             :             case F_SCALARLESEL:
    1391             :             case F_SCALARGTSEL:
    1392             :             case F_SCALARGESEL:
    1393             :                 /* supported, will continue with inspection of the Var/Expr */
    1394         936 :                 break;
    1395             : 
    1396           0 :             default:
    1397             :                 /* other estimators are considered unknown/unsupported */
    1398           0 :                 return false;
    1399             :         }
    1400             : 
    1401             :         /*
    1402             :          * If there are any securityQuals on the RTE from security barrier
    1403             :          * views or RLS policies, then the user may not have access to all the
    1404             :          * table's data, and we must check that the operator is leak-proof.
    1405             :          *
    1406             :          * If the operator is leaky, then we must ignore this clause for the
    1407             :          * purposes of estimating with MCV lists, otherwise the operator might
    1408             :          * reveal values from the MCV list that the user doesn't have
    1409             :          * permission to see.
    1410             :          */
    1411         936 :         if (rte->securityQuals != NIL &&
    1412           0 :             !get_func_leakproof(get_opcode(expr->opno)))
    1413           0 :             return false;
    1414             : 
    1415             :         /* Check (Var op Const) or (Const op Var) clauses by recursing. */
    1416         936 :         if (IsA(clause_expr, Var))
    1417         744 :             return statext_is_compatible_clause_internal(root, clause_expr,
    1418             :                                                          relid, attnums, exprs);
    1419             : 
    1420             :         /* Otherwise we have (Expr op Const) or (Const op Expr). */
    1421         192 :         *exprs = lappend(*exprs, clause_expr);
    1422         192 :         return true;
    1423             :     }
    1424             : 
    1425             :     /* Var/Expr IN Array */
    1426         360 :     if (IsA(clause, ScalarArrayOpExpr))
    1427             :     {
    1428         216 :         RangeTblEntry *rte = root->simple_rte_array[relid];
    1429         216 :         ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
    1430             :         Node       *clause_expr;
    1431             :         bool        expronleft;
    1432             : 
    1433             :         /* Only expressions with two arguments are considered compatible. */
    1434         216 :         if (list_length(expr->args) != 2)
    1435           0 :             return false;
    1436             : 
    1437             :         /* Check if the expression has the right shape (one Var, one Const) */
    1438         216 :         if (!examine_opclause_args(expr->args, &clause_expr, NULL, &expronleft))
    1439           0 :             return false;
    1440             : 
    1441             :         /* We only support Var on left, Const on right */
    1442         216 :         if (!expronleft)
    1443           6 :             return false;
    1444             : 
    1445             :         /*
    1446             :          * If it's not one of the supported operators ("=", "<", ">", etc.),
    1447             :          * just ignore the clause, as it's not compatible with MCV lists.
    1448             :          *
    1449             :          * This uses the function for estimating selectivity, not the operator
    1450             :          * directly (a bit awkward, but well ...).
    1451             :          */
    1452         210 :         switch (get_oprrest(expr->opno))
    1453             :         {
    1454         210 :             case F_EQSEL:
    1455             :             case F_NEQSEL:
    1456             :             case F_SCALARLTSEL:
    1457             :             case F_SCALARLESEL:
    1458             :             case F_SCALARGTSEL:
    1459             :             case F_SCALARGESEL:
    1460             :                 /* supported, will continue with inspection of the Var/Expr */
    1461         210 :                 break;
    1462             : 
    1463           0 :             default:
    1464             :                 /* other estimators are considered unknown/unsupported */
    1465           0 :                 return false;
    1466             :         }
    1467             : 
    1468             :         /*
    1469             :          * If there are any securityQuals on the RTE from security barrier
    1470             :          * views or RLS policies, then the user may not have access to all the
    1471             :          * table's data, and we must check that the operator is leak-proof.
    1472             :          *
    1473             :          * If the operator is leaky, then we must ignore this clause for the
    1474             :          * purposes of estimating with MCV lists, otherwise the operator might
    1475             :          * reveal values from the MCV list that the user doesn't have
    1476             :          * permission to see.
    1477             :          */
    1478         210 :         if (rte->securityQuals != NIL &&
    1479           0 :             !get_func_leakproof(get_opcode(expr->opno)))
    1480           0 :             return false;
    1481             : 
    1482             :         /* Check Var IN Array clauses by recursing. */
    1483         210 :         if (IsA(clause_expr, Var))
    1484         156 :             return statext_is_compatible_clause_internal(root, clause_expr,
    1485             :                                                          relid, attnums, exprs);
    1486             : 
    1487             :         /* Otherwise we have Expr IN Array. */
    1488          54 :         *exprs = lappend(*exprs, clause_expr);
    1489          54 :         return true;
    1490             :     }
    1491             : 
    1492             :     /* AND/OR/NOT clause */
    1493         288 :     if (is_andclause(clause) ||
    1494         276 :         is_orclause(clause) ||
    1495         132 :         is_notclause(clause))
    1496             :     {
    1497             :         /*
    1498             :          * AND/OR/NOT-clauses are supported if all sub-clauses are supported
    1499             :          *
    1500             :          * Perhaps we could improve this by handling mixed cases, when some of
    1501             :          * the clauses are supported and some are not. Selectivity for the
    1502             :          * supported subclauses would be computed using extended statistics,
    1503             :          * and the remaining clauses would be estimated using the traditional
    1504             :          * algorithm (product of selectivities).
    1505             :          *
    1506             :          * It however seems overly complex, and in a way we already do that
    1507             :          * because if we reject the whole clause as unsupported here, it will
    1508             :          * be eventually passed to clauselist_selectivity() which does exactly
    1509             :          * this (split into supported/unsupported clauses etc).
    1510             :          */
    1511          42 :         BoolExpr   *expr = (BoolExpr *) clause;
    1512             :         ListCell   *lc;
    1513             : 
    1514          96 :         foreach(lc, expr->args)
    1515             :         {
    1516             :             /*
    1517             :              * If we find an incompatible clause in the arguments, treat the
    1518             :              * whole clause as incompatible.
    1519             :              */
    1520          54 :             if (!statext_is_compatible_clause_internal(root,
    1521          54 :                                                        (Node *) lfirst(lc),
    1522             :                                                        relid, attnums, exprs))
    1523           0 :                 return false;
    1524             :         }
    1525             : 
    1526          42 :         return true;
    1527             :     }
    1528             : 
    1529             :     /* Var/Expr IS NULL */
    1530         102 :     if (IsA(clause, NullTest))
    1531             :     {
    1532          96 :         NullTest   *nt = (NullTest *) clause;
    1533             : 
    1534             :         /* Check Var IS NULL clauses by recursing. */
    1535          96 :         if (IsA(nt->arg, Var))
    1536          90 :             return statext_is_compatible_clause_internal(root, (Node *) (nt->arg),
    1537             :                                                          relid, attnums, exprs);
    1538             : 
    1539             :         /* Otherwise we have Expr IS NULL. */
    1540           6 :         *exprs = lappend(*exprs, nt->arg);
    1541           6 :         return true;
    1542             :     }
    1543             : 
    1544             :     /*
    1545             :      * Treat any other expressions as bare expressions to be matched against
    1546             :      * expressions in statistics objects.
    1547             :      */
    1548           6 :     *exprs = lappend(*exprs, clause);
    1549           6 :     return true;
    1550             : }
    1551             : 
    1552             : /*
    1553             :  * statext_is_compatible_clause
    1554             :  *      Determines if the clause is compatible with MCV lists.
    1555             :  *
    1556             :  * See statext_is_compatible_clause_internal, above, for the basic rules.
    1557             :  * This layer deals with RestrictInfo superstructure and applies permissions
    1558             :  * checks to verify that it's okay to examine all mentioned Vars.
    1559             :  *
    1560             :  * Arguments:
    1561             :  * clause: clause to be inspected (in RestrictInfo form)
    1562             :  * relid: rel that all Vars in clause must belong to
    1563             :  * *attnums: input/output parameter collecting attribute numbers of all
    1564             :  *      mentioned Vars.  Note that we do not offset the attribute numbers,
    1565             :  *      so we can't cope with system columns.
    1566             :  * *exprs: input/output parameter collecting primitive subclauses within
    1567             :  *      the clause tree
    1568             :  *
    1569             :  * Returns false if there is something we definitively can't handle.
    1570             :  * On true return, we can proceed to match the *exprs against statistics.
    1571             :  */
    1572             : static bool
    1573        1374 : statext_is_compatible_clause(PlannerInfo *root, Node *clause, Index relid,
    1574             :                              Bitmapset **attnums, List **exprs)
    1575             : {
    1576        1374 :     RangeTblEntry *rte = root->simple_rte_array[relid];
    1577        1374 :     RelOptInfo *rel = root->simple_rel_array[relid];
    1578             :     RestrictInfo *rinfo;
    1579             :     int         clause_relid;
    1580             :     Oid         userid;
    1581             : 
    1582             :     /*
    1583             :      * Special-case handling for bare BoolExpr AND clauses, because the
    1584             :      * restrictinfo machinery doesn't build RestrictInfos on top of AND
    1585             :      * clauses.
    1586             :      */
    1587        1374 :     if (is_andclause(clause))
    1588             :     {
    1589          48 :         BoolExpr   *expr = (BoolExpr *) clause;
    1590             :         ListCell   *lc;
    1591             : 
    1592             :         /*
    1593             :          * Check that each sub-clause is compatible.  We expect these to be
    1594             :          * RestrictInfos.
    1595             :          */
    1596         162 :         foreach(lc, expr->args)
    1597             :         {
    1598         114 :             if (!statext_is_compatible_clause(root, (Node *) lfirst(lc),
    1599             :                                               relid, attnums, exprs))
    1600           0 :                 return false;
    1601             :         }
    1602             : 
    1603          48 :         return true;
    1604             :     }
    1605             : 
    1606             :     /* Otherwise it must be a RestrictInfo. */
    1607        1326 :     if (!IsA(clause, RestrictInfo))
    1608           0 :         return false;
    1609        1326 :     rinfo = (RestrictInfo *) clause;
    1610             : 
    1611             :     /* Pseudoconstants are not really interesting here. */
    1612        1326 :     if (rinfo->pseudoconstant)
    1613           6 :         return false;
    1614             : 
    1615             :     /* Clauses referencing other varnos are incompatible. */
    1616        1320 :     if (!bms_get_singleton_member(rinfo->clause_relids, &clause_relid) ||
    1617        1320 :         clause_relid != relid)
    1618           0 :         return false;
    1619             : 
    1620             :     /* Check the clause and determine what attributes it references. */
    1621        1320 :     if (!statext_is_compatible_clause_internal(root, (Node *) rinfo->clause,
    1622             :                                                relid, attnums, exprs))
    1623           6 :         return false;
    1624             : 
    1625             :     /*
    1626             :      * Check that the user has permission to read all required attributes.
    1627             :      */
    1628        1314 :     userid = OidIsValid(rel->userid) ? rel->userid : GetUserId();
    1629             : 
    1630             :     /* Table-level SELECT privilege is sufficient for all columns */
    1631        1314 :     if (pg_class_aclcheck(rte->relid, userid, ACL_SELECT) != ACLCHECK_OK)
    1632             :     {
    1633          36 :         Bitmapset  *clause_attnums = NULL;
    1634          36 :         int         attnum = -1;
    1635             : 
    1636             :         /*
    1637             :          * We have to check per-column privileges.  *attnums has the attnums
    1638             :          * for individual Vars we saw, but there may also be Vars within
    1639             :          * subexpressions in *exprs.  We can use pull_varattnos() to extract
    1640             :          * those, but there's an impedance mismatch: attnums returned by
    1641             :          * pull_varattnos() are offset by FirstLowInvalidHeapAttributeNumber,
    1642             :          * while attnums within *attnums aren't.  Convert *attnums to the
    1643             :          * offset style so we can combine the results.
    1644             :          */
    1645          66 :         while ((attnum = bms_next_member(*attnums, attnum)) >= 0)
    1646             :         {
    1647          30 :             clause_attnums =
    1648          30 :                 bms_add_member(clause_attnums,
    1649             :                                attnum - FirstLowInvalidHeapAttributeNumber);
    1650             :         }
    1651             : 
    1652             :         /* Now merge attnums from *exprs into clause_attnums */
    1653          36 :         if (*exprs != NIL)
    1654           6 :             pull_varattnos((Node *) *exprs, relid, &clause_attnums);
    1655             : 
    1656          36 :         attnum = -1;
    1657          36 :         while ((attnum = bms_next_member(clause_attnums, attnum)) >= 0)
    1658             :         {
    1659             :             /* Undo the offset */
    1660          36 :             AttrNumber  attno = attnum + FirstLowInvalidHeapAttributeNumber;
    1661             : 
    1662          36 :             if (attno == InvalidAttrNumber)
    1663             :             {
    1664             :                 /* Whole-row reference, so must have access to all columns */
    1665           6 :                 if (pg_attribute_aclcheck_all(rte->relid, userid, ACL_SELECT,
    1666             :                                               ACLMASK_ALL) != ACLCHECK_OK)
    1667          36 :                     return false;
    1668             :             }
    1669             :             else
    1670             :             {
    1671          30 :                 if (pg_attribute_aclcheck(rte->relid, attno, userid,
    1672             :                                           ACL_SELECT) != ACLCHECK_OK)
    1673          30 :                     return false;
    1674             :             }
    1675             :         }
    1676             :     }
    1677             : 
    1678             :     /* If we reach here, the clause is OK */
    1679        1278 :     return true;
    1680             : }
    1681             : 
    1682             : /*
    1683             :  * statext_mcv_clauselist_selectivity
    1684             :  *      Estimate clauses using the best multi-column statistics.
    1685             :  *
    1686             :  * Applies available extended (multi-column) statistics on a table. There may
    1687             :  * be multiple applicable statistics (with respect to the clauses), in which
    1688             :  * case we use greedy approach. In each round we select the best statistic on
    1689             :  * a table (measured by the number of attributes extracted from the clauses
    1690             :  * and covered by it), and compute the selectivity for the supplied clauses.
    1691             :  * We repeat this process with the remaining clauses (if any), until none of
    1692             :  * the available statistics can be used.
    1693             :  *
    1694             :  * One of the main challenges with using MCV lists is how to extrapolate the
    1695             :  * estimate to the data not covered by the MCV list. To do that, we compute
    1696             :  * not only the "MCV selectivity" (selectivities for MCV items matching the
    1697             :  * supplied clauses), but also the following related selectivities:
    1698             :  *
    1699             :  * - simple selectivity:  Computed without extended statistics, i.e. as if the
    1700             :  * columns/clauses were independent.
    1701             :  *
    1702             :  * - base selectivity:  Similar to simple selectivity, but is computed using
    1703             :  * the extended statistic by adding up the base frequencies (that we compute
    1704             :  * and store for each MCV item) of matching MCV items.
    1705             :  *
    1706             :  * - total selectivity: Selectivity covered by the whole MCV list.
    1707             :  *
    1708             :  * These are passed to mcv_combine_selectivities() which combines them to
    1709             :  * produce a selectivity estimate that makes use of both per-column statistics
    1710             :  * and the multi-column MCV statistics.
    1711             :  *
    1712             :  * 'estimatedclauses' is an input/output parameter.  We set bits for the
    1713             :  * 0-based 'clauses' indexes we estimate for and also skip clause items that
    1714             :  * already have a bit set.
    1715             :  */
    1716             : static Selectivity
    1717        1878 : statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
    1718             :                                    JoinType jointype, SpecialJoinInfo *sjinfo,
    1719             :                                    RelOptInfo *rel, Bitmapset **estimatedclauses,
    1720             :                                    bool is_or)
    1721             : {
    1722             :     ListCell   *l;
    1723             :     Bitmapset **list_attnums;   /* attnums extracted from the clause */
    1724             :     List      **list_exprs;     /* expressions matched to any statistic */
    1725             :     int         listidx;
    1726        1878 :     Selectivity sel = (is_or) ? 0.0 : 1.0;
    1727        1878 :     RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
    1728             : 
    1729             :     /* check if there's any stats that might be useful for us. */
    1730        1878 :     if (!has_stats_of_kind(rel->statlist, STATS_EXT_MCV))
    1731        1380 :         return sel;
    1732             : 
    1733         498 :     list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) *
    1734         498 :                                          list_length(clauses));
    1735             : 
    1736             :     /* expressions extracted from complex expressions */
    1737         498 :     list_exprs = (List **) palloc(sizeof(Node *) * list_length(clauses));
    1738             : 
    1739             :     /*
    1740             :      * Pre-process the clauses list to extract the attnums and expressions
    1741             :      * seen in each item.  We need to determine if there are any clauses which
    1742             :      * will be useful for selectivity estimations with extended stats.  Along
    1743             :      * the way we'll record all of the attnums and expressions for each clause
    1744             :      * in lists which we'll reference later so we don't need to repeat the
    1745             :      * same work again.
    1746             :      *
    1747             :      * We also skip clauses that we already estimated using different types of
    1748             :      * statistics (we treat them as incompatible).
    1749             :      */
    1750         498 :     listidx = 0;
    1751        1758 :     foreach(l, clauses)
    1752             :     {
    1753        1260 :         Node       *clause = (Node *) lfirst(l);
    1754        1260 :         Bitmapset  *attnums = NULL;
    1755        1260 :         List       *exprs = NIL;
    1756             : 
    1757        2520 :         if (!bms_is_member(listidx, *estimatedclauses) &&
    1758        1260 :             statext_is_compatible_clause(root, clause, rel->relid, &attnums, &exprs))
    1759             :         {
    1760        1212 :             list_attnums[listidx] = attnums;
    1761        1212 :             list_exprs[listidx] = exprs;
    1762             :         }
    1763             :         else
    1764             :         {
    1765          48 :             list_attnums[listidx] = NULL;
    1766          48 :             list_exprs[listidx] = NIL;
    1767             :         }
    1768             : 
    1769        1260 :         listidx++;
    1770             :     }
    1771             : 
    1772             :     /* apply as many extended statistics as possible */
    1773             :     while (true)
    1774         480 :     {
    1775             :         StatisticExtInfo *stat;
    1776             :         List       *stat_clauses;
    1777             :         Bitmapset  *simple_clauses;
    1778             : 
    1779             :         /* find the best suited statistics object for these attnums */
    1780         978 :         stat = choose_best_statistics(rel->statlist, STATS_EXT_MCV, rte->inh,
    1781             :                                       list_attnums, list_exprs,
    1782             :                                       list_length(clauses));
    1783             : 
    1784             :         /*
    1785             :          * if no (additional) matching stats could be found then we've nothing
    1786             :          * to do
    1787             :          */
    1788         978 :         if (!stat)
    1789         498 :             break;
    1790             : 
    1791             :         /* Ensure choose_best_statistics produced an expected stats type. */
    1792             :         Assert(stat->kind == STATS_EXT_MCV);
    1793             : 
    1794             :         /* now filter the clauses to be estimated using the selected MCV */
    1795         480 :         stat_clauses = NIL;
    1796             : 
    1797             :         /* record which clauses are simple (single column or expression) */
    1798         480 :         simple_clauses = NULL;
    1799             : 
    1800         480 :         listidx = -1;
    1801        1728 :         foreach(l, clauses)
    1802             :         {
    1803             :             /* Increment the index before we decide if to skip the clause. */
    1804        1248 :             listidx++;
    1805             : 
    1806             :             /*
    1807             :              * Ignore clauses from which we did not extract any attnums or
    1808             :              * expressions (this needs to be consistent with what we do in
    1809             :              * choose_best_statistics).
    1810             :              *
    1811             :              * This also eliminates already estimated clauses - both those
    1812             :              * estimated before and during applying extended statistics.
    1813             :              *
    1814             :              * XXX This check is needed because both bms_is_subset and
    1815             :              * stat_covers_expressions return true for empty attnums and
    1816             :              * expressions.
    1817             :              */
    1818        1248 :             if (!list_attnums[listidx] && !list_exprs[listidx])
    1819          36 :                 continue;
    1820             : 
    1821             :             /*
    1822             :              * The clause was not estimated yet, and we've extracted either
    1823             :              * attnums or expressions from it. Ignore it if it's not fully
    1824             :              * covered by the chosen statistics object.
    1825             :              *
    1826             :              * We need to check both attributes and expressions, and reject if
    1827             :              * either is not covered.
    1828             :              */
    1829        1212 :             if (!bms_is_subset(list_attnums[listidx], stat->keys) ||
    1830        1158 :                 !stat_covers_expressions(stat, list_exprs[listidx], NULL))
    1831          60 :                 continue;
    1832             : 
    1833             :             /*
    1834             :              * Now we know the clause is compatible (we have either attnums or
    1835             :              * expressions extracted from it), and was not estimated yet.
    1836             :              */
    1837             : 
    1838             :             /* record simple clauses (single column or expression) */
    1839        1398 :             if ((list_attnums[listidx] == NULL &&
    1840         246 :                  list_length(list_exprs[listidx]) == 1) ||
    1841        1812 :                 (list_exprs[listidx] == NIL &&
    1842         906 :                  bms_membership(list_attnums[listidx]) == BMS_SINGLETON))
    1843        1092 :                 simple_clauses = bms_add_member(simple_clauses,
    1844             :                                                 list_length(stat_clauses));
    1845             : 
    1846             :             /* add clause to list and mark it as estimated */
    1847        1152 :             stat_clauses = lappend(stat_clauses, (Node *) lfirst(l));
    1848        1152 :             *estimatedclauses = bms_add_member(*estimatedclauses, listidx);
    1849             : 
    1850             :             /*
    1851             :              * Reset the pointers, so that choose_best_statistics knows this
    1852             :              * clause was estimated and does not consider it again.
    1853             :              */
    1854        1152 :             bms_free(list_attnums[listidx]);
    1855        1152 :             list_attnums[listidx] = NULL;
    1856             : 
    1857        1152 :             list_free(list_exprs[listidx]);
    1858        1152 :             list_exprs[listidx] = NULL;
    1859             :         }
    1860             : 
    1861         480 :         if (is_or)
    1862             :         {
    1863          96 :             bool       *or_matches = NULL;
    1864          96 :             Selectivity simple_or_sel = 0.0,
    1865          96 :                         stat_sel = 0.0;
    1866             :             MCVList    *mcv_list;
    1867             : 
    1868             :             /* Load the MCV list stored in the statistics object */
    1869          96 :             mcv_list = statext_mcv_load(stat->statOid, rte->inh);
    1870             : 
    1871             :             /*
    1872             :              * Compute the selectivity of the ORed list of clauses covered by
    1873             :              * this statistics object by estimating each in turn and combining
    1874             :              * them using the formula P(A OR B) = P(A) + P(B) - P(A AND B).
    1875             :              * This allows us to use the multivariate MCV stats to better
    1876             :              * estimate the individual terms and their overlap.
    1877             :              *
    1878             :              * Each time we iterate this formula, the clause "A" above is
    1879             :              * equal to all the clauses processed so far, combined with "OR".
    1880             :              */
    1881          96 :             listidx = 0;
    1882         336 :             foreach(l, stat_clauses)
    1883             :             {
    1884         240 :                 Node       *clause = (Node *) lfirst(l);
    1885             :                 Selectivity simple_sel,
    1886             :                             overlap_simple_sel,
    1887             :                             mcv_sel,
    1888             :                             mcv_basesel,
    1889             :                             overlap_mcvsel,
    1890             :                             overlap_basesel,
    1891             :                             mcv_totalsel,
    1892             :                             clause_sel,
    1893             :                             overlap_sel;
    1894             : 
    1895             :                 /*
    1896             :                  * "Simple" selectivity of the next clause and its overlap
    1897             :                  * with any of the previous clauses.  These are our initial
    1898             :                  * estimates of P(B) and P(A AND B), assuming independence of
    1899             :                  * columns/clauses.
    1900             :                  */
    1901         240 :                 simple_sel = clause_selectivity_ext(root, clause, varRelid,
    1902             :                                                     jointype, sjinfo, false);
    1903             : 
    1904         240 :                 overlap_simple_sel = simple_or_sel * simple_sel;
    1905             : 
    1906             :                 /*
    1907             :                  * New "simple" selectivity of all clauses seen so far,
    1908             :                  * assuming independence.
    1909             :                  */
    1910         240 :                 simple_or_sel += simple_sel - overlap_simple_sel;
    1911         240 :                 CLAMP_PROBABILITY(simple_or_sel);
    1912             : 
    1913             :                 /*
    1914             :                  * Multi-column estimate of this clause using MCV statistics,
    1915             :                  * along with base and total selectivities, and corresponding
    1916             :                  * selectivities for the overlap term P(A AND B).
    1917             :                  */
    1918         240 :                 mcv_sel = mcv_clause_selectivity_or(root, stat, mcv_list,
    1919             :                                                     clause, &or_matches,
    1920             :                                                     &mcv_basesel,
    1921             :                                                     &overlap_mcvsel,
    1922             :                                                     &overlap_basesel,
    1923             :                                                     &mcv_totalsel);
    1924             : 
    1925             :                 /*
    1926             :                  * Combine the simple and multi-column estimates.
    1927             :                  *
    1928             :                  * If this clause is a simple single-column clause, then we
    1929             :                  * just use the simple selectivity estimate for it, since the
    1930             :                  * multi-column statistics are unlikely to improve on that
    1931             :                  * (and in fact could make it worse).  For the overlap, we
    1932             :                  * always make use of the multi-column statistics.
    1933             :                  */
    1934         240 :                 if (bms_is_member(listidx, simple_clauses))
    1935         192 :                     clause_sel = simple_sel;
    1936             :                 else
    1937          48 :                     clause_sel = mcv_combine_selectivities(simple_sel,
    1938             :                                                            mcv_sel,
    1939             :                                                            mcv_basesel,
    1940             :                                                            mcv_totalsel);
    1941             : 
    1942         240 :                 overlap_sel = mcv_combine_selectivities(overlap_simple_sel,
    1943             :                                                         overlap_mcvsel,
    1944             :                                                         overlap_basesel,
    1945             :                                                         mcv_totalsel);
    1946             : 
    1947             :                 /* Factor these into the result for this statistics object */
    1948         240 :                 stat_sel += clause_sel - overlap_sel;
    1949         240 :                 CLAMP_PROBABILITY(stat_sel);
    1950             : 
    1951         240 :                 listidx++;
    1952             :             }
    1953             : 
    1954             :             /*
    1955             :              * Factor the result for this statistics object into the overall
    1956             :              * result.  We treat the results from each separate statistics
    1957             :              * object as independent of one another.
    1958             :              */
    1959          96 :             sel = sel + stat_sel - sel * stat_sel;
    1960             :         }
    1961             :         else                    /* Implicitly-ANDed list of clauses */
    1962             :         {
    1963             :             Selectivity simple_sel,
    1964             :                         mcv_sel,
    1965             :                         mcv_basesel,
    1966             :                         mcv_totalsel,
    1967             :                         stat_sel;
    1968             : 
    1969             :             /*
    1970             :              * "Simple" selectivity, i.e. without any extended statistics,
    1971             :              * essentially assuming independence of the columns/clauses.
    1972             :              */
    1973         384 :             simple_sel = clauselist_selectivity_ext(root, stat_clauses,
    1974             :                                                     varRelid, jointype,
    1975             :                                                     sjinfo, false);
    1976             : 
    1977             :             /*
    1978             :              * Multi-column estimate using MCV statistics, along with base and
    1979             :              * total selectivities.
    1980             :              */
    1981         384 :             mcv_sel = mcv_clauselist_selectivity(root, stat, stat_clauses,
    1982             :                                                  varRelid, jointype, sjinfo,
    1983             :                                                  rel, &mcv_basesel,
    1984             :                                                  &mcv_totalsel);
    1985             : 
    1986             :             /* Combine the simple and multi-column estimates. */
    1987         384 :             stat_sel = mcv_combine_selectivities(simple_sel,
    1988             :                                                  mcv_sel,
    1989             :                                                  mcv_basesel,
    1990             :                                                  mcv_totalsel);
    1991             : 
    1992             :             /* Factor this into the overall result */
    1993         384 :             sel *= stat_sel;
    1994             :         }
    1995             :     }
    1996             : 
    1997         498 :     return sel;
    1998             : }
    1999             : 
    2000             : /*
    2001             :  * statext_clauselist_selectivity
    2002             :  *      Estimate clauses using the best multi-column statistics.
    2003             :  */
    2004             : Selectivity
    2005        1878 : statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
    2006             :                                JoinType jointype, SpecialJoinInfo *sjinfo,
    2007             :                                RelOptInfo *rel, Bitmapset **estimatedclauses,
    2008             :                                bool is_or)
    2009             : {
    2010             :     Selectivity sel;
    2011             : 
    2012             :     /* First, try estimating clauses using a multivariate MCV list. */
    2013        1878 :     sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
    2014             :                                              sjinfo, rel, estimatedclauses, is_or);
    2015             : 
    2016             :     /*
    2017             :      * Functional dependencies only work for clauses connected by AND, so for
    2018             :      * OR clauses we're done.
    2019             :      */
    2020        1878 :     if (is_or)
    2021         108 :         return sel;
    2022             : 
    2023             :     /*
    2024             :      * Then, apply functional dependencies on the remaining clauses by calling
    2025             :      * dependencies_clauselist_selectivity.  Pass 'estimatedclauses' so the
    2026             :      * function can properly skip clauses already estimated above.
    2027             :      *
    2028             :      * The reasoning for applying dependencies last is that the more complex
    2029             :      * stats can track more complex correlations between the attributes, and
    2030             :      * so may be considered more reliable.
    2031             :      *
    2032             :      * For example, MCV list can give us an exact selectivity for values in
    2033             :      * two columns, while functional dependencies can only provide information
    2034             :      * about the overall strength of the dependency.
    2035             :      */
    2036        1770 :     sel *= dependencies_clauselist_selectivity(root, clauses, varRelid,
    2037             :                                                jointype, sjinfo, rel,
    2038             :                                                estimatedclauses);
    2039             : 
    2040        1770 :     return sel;
    2041             : }
    2042             : 
    2043             : /*
    2044             :  * examine_opclause_args
    2045             :  *      Split an operator expression's arguments into Expr and Const parts.
    2046             :  *
    2047             :  * Attempts to match the arguments to either (Expr op Const) or (Const op
    2048             :  * Expr), possibly with a RelabelType on top. When the expression matches this
    2049             :  * form, returns true, otherwise returns false.
    2050             :  *
    2051             :  * Optionally returns pointers to the extracted Expr/Const nodes, when passed
    2052             :  * non-null pointers (exprp, cstp and expronleftp). The expronleftp flag
    2053             :  * specifies on which side of the operator we found the expression node.
    2054             :  */
    2055             : bool
    2056        2232 : examine_opclause_args(List *args, Node **exprp, Const **cstp,
    2057             :                       bool *expronleftp)
    2058             : {
    2059             :     Node       *expr;
    2060             :     Const      *cst;
    2061             :     bool        expronleft;
    2062             :     Node       *leftop,
    2063             :                *rightop;
    2064             : 
    2065             :     /* enforced by statext_is_compatible_clause_internal */
    2066             :     Assert(list_length(args) == 2);
    2067             : 
    2068        2232 :     leftop = linitial(args);
    2069        2232 :     rightop = lsecond(args);
    2070             : 
    2071             :     /* strip RelabelType from either side of the expression */
    2072        2232 :     if (IsA(leftop, RelabelType))
    2073         324 :         leftop = (Node *) ((RelabelType *) leftop)->arg;
    2074             : 
    2075        2232 :     if (IsA(rightop, RelabelType))
    2076          60 :         rightop = (Node *) ((RelabelType *) rightop)->arg;
    2077             : 
    2078        2232 :     if (IsA(rightop, Const))
    2079             :     {
    2080        2070 :         expr = (Node *) leftop;
    2081        2070 :         cst = (Const *) rightop;
    2082        2070 :         expronleft = true;
    2083             :     }
    2084         162 :     else if (IsA(leftop, Const))
    2085             :     {
    2086         162 :         expr = (Node *) rightop;
    2087         162 :         cst = (Const *) leftop;
    2088         162 :         expronleft = false;
    2089             :     }
    2090             :     else
    2091           0 :         return false;
    2092             : 
    2093             :     /* return pointers to the extracted parts if requested */
    2094        2232 :     if (exprp)
    2095        2232 :         *exprp = expr;
    2096             : 
    2097        2232 :     if (cstp)
    2098        1080 :         *cstp = cst;
    2099             : 
    2100        2232 :     if (expronleftp)
    2101        1296 :         *expronleftp = expronleft;
    2102             : 
    2103        2232 :     return true;
    2104             : }
    2105             : 
    2106             : 
    2107             : /*
    2108             :  * Compute statistics about expressions of a relation.
    2109             :  */
    2110             : static void
    2111         150 : compute_expr_stats(Relation onerel, double totalrows,
    2112             :                    AnlExprData *exprdata, int nexprs,
    2113             :                    HeapTuple *rows, int numrows)
    2114             : {
    2115             :     MemoryContext expr_context,
    2116             :                 old_context;
    2117             :     int         ind,
    2118             :                 i;
    2119             : 
    2120         150 :     expr_context = AllocSetContextCreate(CurrentMemoryContext,
    2121             :                                          "Analyze Expression",
    2122             :                                          ALLOCSET_DEFAULT_SIZES);
    2123         150 :     old_context = MemoryContextSwitchTo(expr_context);
    2124             : 
    2125         438 :     for (ind = 0; ind < nexprs; ind++)
    2126             :     {
    2127         288 :         AnlExprData *thisdata = &exprdata[ind];
    2128         288 :         VacAttrStats *stats = thisdata->vacattrstat;
    2129         288 :         Node       *expr = thisdata->expr;
    2130             :         TupleTableSlot *slot;
    2131             :         EState     *estate;
    2132             :         ExprContext *econtext;
    2133             :         Datum      *exprvals;
    2134             :         bool       *exprnulls;
    2135             :         ExprState  *exprstate;
    2136             :         int         tcnt;
    2137             : 
    2138             :         /* Are we still in the main context? */
    2139             :         Assert(CurrentMemoryContext == expr_context);
    2140             : 
    2141             :         /*
    2142             :          * Need an EState for evaluation of expressions.  Create it in the
    2143             :          * per-expression context to be sure it gets cleaned up at the bottom
    2144             :          * of the loop.
    2145             :          */
    2146         288 :         estate = CreateExecutorState();
    2147         288 :         econtext = GetPerTupleExprContext(estate);
    2148             : 
    2149             :         /* Set up expression evaluation state */
    2150         288 :         exprstate = ExecPrepareExpr((Expr *) expr, estate);
    2151             : 
    2152             :         /* Need a slot to hold the current heap tuple, too */
    2153         288 :         slot = MakeSingleTupleTableSlot(RelationGetDescr(onerel),
    2154             :                                         &TTSOpsHeapTuple);
    2155             : 
    2156             :         /* Arrange for econtext's scan tuple to be the tuple under test */
    2157         288 :         econtext->ecxt_scantuple = slot;
    2158             : 
    2159             :         /* Compute and save expression values */
    2160         288 :         exprvals = (Datum *) palloc(numrows * sizeof(Datum));
    2161         288 :         exprnulls = (bool *) palloc(numrows * sizeof(bool));
    2162             : 
    2163         288 :         tcnt = 0;
    2164      399882 :         for (i = 0; i < numrows; i++)
    2165             :         {
    2166             :             Datum       datum;
    2167             :             bool        isnull;
    2168             : 
    2169             :             /*
    2170             :              * Reset the per-tuple context each time, to reclaim any cruft
    2171             :              * left behind by evaluating the statistics expressions.
    2172             :              */
    2173      399594 :             ResetExprContext(econtext);
    2174             : 
    2175             :             /* Set up for expression evaluation */
    2176      399594 :             ExecStoreHeapTuple(rows[i], slot, false);
    2177             : 
    2178             :             /*
    2179             :              * Evaluate the expression. We do this in the per-tuple context so
    2180             :              * as not to leak memory, and then copy the result into the
    2181             :              * context created at the beginning of this function.
    2182             :              */
    2183      399594 :             datum = ExecEvalExprSwitchContext(exprstate,
    2184      399594 :                                               GetPerTupleExprContext(estate),
    2185             :                                               &isnull);
    2186      399594 :             if (isnull)
    2187             :             {
    2188           0 :                 exprvals[tcnt] = (Datum) 0;
    2189           0 :                 exprnulls[tcnt] = true;
    2190             :             }
    2191             :             else
    2192             :             {
    2193             :                 /* Make sure we copy the data into the context. */
    2194             :                 Assert(CurrentMemoryContext == expr_context);
    2195             : 
    2196      799188 :                 exprvals[tcnt] = datumCopy(datum,
    2197      399594 :                                            stats->attrtype->typbyval,
    2198      399594 :                                            stats->attrtype->typlen);
    2199      399594 :                 exprnulls[tcnt] = false;
    2200             :             }
    2201             : 
    2202      399594 :             tcnt++;
    2203             :         }
    2204             : 
    2205             :         /*
    2206             :          * Now we can compute the statistics for the expression columns.
    2207             :          *
    2208             :          * XXX Unlike compute_index_stats we don't need to switch and reset
    2209             :          * memory contexts here, because we're only computing stats for a
    2210             :          * single expression (and not iterating over many indexes), so we just
    2211             :          * do it in expr_context. Note that compute_stats copies the result
    2212             :          * into stats->anl_context, so it does not disappear.
    2213             :          */
    2214         288 :         if (tcnt > 0)
    2215             :         {
    2216             :             AttributeOpts *aopt =
    2217         288 :                 get_attribute_options(onerel->rd_id, stats->tupattnum);
    2218             : 
    2219         288 :             stats->exprvals = exprvals;
    2220         288 :             stats->exprnulls = exprnulls;
    2221         288 :             stats->rowstride = 1;
    2222         288 :             stats->compute_stats(stats,
    2223             :                                  expr_fetch_func,
    2224             :                                  tcnt,
    2225             :                                  tcnt);
    2226             : 
    2227             :             /*
    2228             :              * If the n_distinct option is specified, it overrides the above
    2229             :              * computation.
    2230             :              */
    2231         288 :             if (aopt != NULL && aopt->n_distinct != 0.0)
    2232           0 :                 stats->stadistinct = aopt->n_distinct;
    2233             :         }
    2234             : 
    2235             :         /* And clean up */
    2236         288 :         MemoryContextSwitchTo(expr_context);
    2237             : 
    2238         288 :         ExecDropSingleTupleTableSlot(slot);
    2239         288 :         FreeExecutorState(estate);
    2240         288 :         MemoryContextReset(expr_context);
    2241             :     }
    2242             : 
    2243         150 :     MemoryContextSwitchTo(old_context);
    2244         150 :     MemoryContextDelete(expr_context);
    2245         150 : }
    2246             : 
    2247             : 
    2248             : /*
    2249             :  * Fetch function for analyzing statistics object expressions.
    2250             :  *
    2251             :  * We have not bothered to construct tuples from the data, instead the data
    2252             :  * is just in Datum arrays.
    2253             :  */
    2254             : static Datum
    2255      399594 : expr_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
    2256             : {
    2257             :     int         i;
    2258             : 
    2259             :     /* exprvals and exprnulls are already offset for proper column */
    2260      399594 :     i = rownum * stats->rowstride;
    2261      399594 :     *isNull = stats->exprnulls[i];
    2262      399594 :     return stats->exprvals[i];
    2263             : }
    2264             : 
    2265             : /*
    2266             :  * Build analyze data for a list of expressions. As this is not tied
    2267             :  * directly to a relation (table or index), we have to fake some of
    2268             :  * the fields in examine_expression().
    2269             :  */
    2270             : static AnlExprData *
    2271         150 : build_expr_data(List *exprs, int stattarget)
    2272             : {
    2273             :     int         idx;
    2274         150 :     int         nexprs = list_length(exprs);
    2275             :     AnlExprData *exprdata;
    2276             :     ListCell   *lc;
    2277             : 
    2278         150 :     exprdata = (AnlExprData *) palloc0(nexprs * sizeof(AnlExprData));
    2279             : 
    2280         150 :     idx = 0;
    2281         438 :     foreach(lc, exprs)
    2282             :     {
    2283         288 :         Node       *expr = (Node *) lfirst(lc);
    2284         288 :         AnlExprData *thisdata = &exprdata[idx];
    2285             : 
    2286         288 :         thisdata->expr = expr;
    2287         288 :         thisdata->vacattrstat = examine_expression(expr, stattarget);
    2288         288 :         idx++;
    2289             :     }
    2290             : 
    2291         150 :     return exprdata;
    2292             : }
    2293             : 
    2294             : /* form an array of pg_statistic rows (per update_attstats) */
    2295             : static Datum
    2296         150 : serialize_expr_stats(AnlExprData *exprdata, int nexprs)
    2297             : {
    2298             :     int         exprno;
    2299             :     Oid         typOid;
    2300             :     Relation    sd;
    2301             : 
    2302         150 :     ArrayBuildState *astate = NULL;
    2303             : 
    2304         150 :     sd = table_open(StatisticRelationId, RowExclusiveLock);
    2305             : 
    2306             :     /* lookup OID of composite type for pg_statistic */
    2307         150 :     typOid = get_rel_type_id(StatisticRelationId);
    2308         150 :     if (!OidIsValid(typOid))
    2309           0 :         ereport(ERROR,
    2310             :                 (errcode(ERRCODE_WRONG_OBJECT_TYPE),
    2311             :                  errmsg("relation \"%s\" does not have a composite type",
    2312             :                         "pg_statistic")));
    2313             : 
    2314         438 :     for (exprno = 0; exprno < nexprs; exprno++)
    2315             :     {
    2316             :         int         i,
    2317             :                     k;
    2318         288 :         VacAttrStats *stats = exprdata[exprno].vacattrstat;
    2319             : 
    2320             :         Datum       values[Natts_pg_statistic];
    2321             :         bool        nulls[Natts_pg_statistic];
    2322             :         HeapTuple   stup;
    2323             : 
    2324         288 :         if (!stats->stats_valid)
    2325             :         {
    2326           0 :             astate = accumArrayResult(astate,
    2327             :                                       (Datum) 0,
    2328             :                                       true,
    2329             :                                       typOid,
    2330             :                                       CurrentMemoryContext);
    2331           0 :             continue;
    2332             :         }
    2333             : 
    2334             :         /*
    2335             :          * Construct a new pg_statistic tuple
    2336             :          */
    2337        9216 :         for (i = 0; i < Natts_pg_statistic; ++i)
    2338             :         {
    2339        8928 :             nulls[i] = false;
    2340             :         }
    2341             : 
    2342         288 :         values[Anum_pg_statistic_starelid - 1] = ObjectIdGetDatum(InvalidOid);
    2343         288 :         values[Anum_pg_statistic_staattnum - 1] = Int16GetDatum(InvalidAttrNumber);
    2344         288 :         values[Anum_pg_statistic_stainherit - 1] = BoolGetDatum(false);
    2345         288 :         values[Anum_pg_statistic_stanullfrac - 1] = Float4GetDatum(stats->stanullfrac);
    2346         288 :         values[Anum_pg_statistic_stawidth - 1] = Int32GetDatum(stats->stawidth);
    2347         288 :         values[Anum_pg_statistic_stadistinct - 1] = Float4GetDatum(stats->stadistinct);
    2348         288 :         i = Anum_pg_statistic_stakind1 - 1;
    2349        1728 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2350             :         {
    2351        1440 :             values[i++] = Int16GetDatum(stats->stakind[k]); /* stakindN */
    2352             :         }
    2353         288 :         i = Anum_pg_statistic_staop1 - 1;
    2354        1728 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2355             :         {
    2356        1440 :             values[i++] = ObjectIdGetDatum(stats->staop[k]); /* staopN */
    2357             :         }
    2358         288 :         i = Anum_pg_statistic_stacoll1 - 1;
    2359        1728 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2360             :         {
    2361        1440 :             values[i++] = ObjectIdGetDatum(stats->stacoll[k]);   /* stacollN */
    2362             :         }
    2363         288 :         i = Anum_pg_statistic_stanumbers1 - 1;
    2364        1728 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2365             :         {
    2366        1440 :             int         nnum = stats->numnumbers[k];
    2367             : 
    2368        1440 :             if (nnum > 0)
    2369             :             {
    2370             :                 int         n;
    2371         564 :                 Datum      *numdatums = (Datum *) palloc(nnum * sizeof(Datum));
    2372             :                 ArrayType  *arry;
    2373             : 
    2374        4938 :                 for (n = 0; n < nnum; n++)
    2375        4374 :                     numdatums[n] = Float4GetDatum(stats->stanumbers[k][n]);
    2376         564 :                 arry = construct_array_builtin(numdatums, nnum, FLOAT4OID);
    2377         564 :                 values[i++] = PointerGetDatum(arry);    /* stanumbersN */
    2378             :             }
    2379             :             else
    2380             :             {
    2381         876 :                 nulls[i] = true;
    2382         876 :                 values[i++] = (Datum) 0;
    2383             :             }
    2384             :         }
    2385         288 :         i = Anum_pg_statistic_stavalues1 - 1;
    2386        1728 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2387             :         {
    2388        1440 :             if (stats->numvalues[k] > 0)
    2389             :             {
    2390             :                 ArrayType  *arry;
    2391             : 
    2392         306 :                 arry = construct_array(stats->stavalues[k],
    2393             :                                        stats->numvalues[k],
    2394             :                                        stats->statypid[k],
    2395         306 :                                        stats->statyplen[k],
    2396         306 :                                        stats->statypbyval[k],
    2397         306 :                                        stats->statypalign[k]);
    2398         306 :                 values[i++] = PointerGetDatum(arry);    /* stavaluesN */
    2399             :             }
    2400             :             else
    2401             :             {
    2402        1134 :                 nulls[i] = true;
    2403        1134 :                 values[i++] = (Datum) 0;
    2404             :             }
    2405             :         }
    2406             : 
    2407         288 :         stup = heap_form_tuple(RelationGetDescr(sd), values, nulls);
    2408             : 
    2409         288 :         astate = accumArrayResult(astate,
    2410             :                                   heap_copy_tuple_as_datum(stup, RelationGetDescr(sd)),
    2411             :                                   false,
    2412             :                                   typOid,
    2413             :                                   CurrentMemoryContext);
    2414             :     }
    2415             : 
    2416         150 :     table_close(sd, RowExclusiveLock);
    2417             : 
    2418         150 :     return makeArrayResult(astate, CurrentMemoryContext);
    2419             : }
    2420             : 
    2421             : /*
    2422             :  * Loads pg_statistic record from expression statistics for expression
    2423             :  * identified by the supplied index.
    2424             :  */
    2425             : HeapTuple
    2426        1644 : statext_expressions_load(Oid stxoid, bool inh, int idx)
    2427             : {
    2428             :     bool        isnull;
    2429             :     Datum       value;
    2430             :     HeapTuple   htup;
    2431             :     ExpandedArrayHeader *eah;
    2432             :     HeapTupleHeader td;
    2433             :     HeapTupleData tmptup;
    2434             :     HeapTuple   tup;
    2435             : 
    2436        1644 :     htup = SearchSysCache2(STATEXTDATASTXOID,
    2437             :                            ObjectIdGetDatum(stxoid), BoolGetDatum(inh));
    2438        1644 :     if (!HeapTupleIsValid(htup))
    2439           0 :         elog(ERROR, "cache lookup failed for statistics object %u", stxoid);
    2440             : 
    2441        1644 :     value = SysCacheGetAttr(STATEXTDATASTXOID, htup,
    2442             :                             Anum_pg_statistic_ext_data_stxdexpr, &isnull);
    2443        1644 :     if (isnull)
    2444           0 :         elog(ERROR,
    2445             :              "requested statistics kind \"%c\" is not yet built for statistics object %u",
    2446             :              STATS_EXT_DEPENDENCIES, stxoid);
    2447             : 
    2448        1644 :     eah = DatumGetExpandedArray(value);
    2449             : 
    2450        1644 :     deconstruct_expanded_array(eah);
    2451             : 
    2452        1644 :     td = DatumGetHeapTupleHeader(eah->dvalues[idx]);
    2453             : 
    2454             :     /* Build a temporary HeapTuple control structure */
    2455        1644 :     tmptup.t_len = HeapTupleHeaderGetDatumLength(td);
    2456        1644 :     ItemPointerSetInvalid(&(tmptup.t_self));
    2457        1644 :     tmptup.t_tableOid = InvalidOid;
    2458        1644 :     tmptup.t_data = td;
    2459             : 
    2460        1644 :     tup = heap_copytuple(&tmptup);
    2461             : 
    2462        1644 :     ReleaseSysCache(htup);
    2463             : 
    2464        1644 :     return tup;
    2465             : }
    2466             : 
    2467             : /*
    2468             :  * Evaluate the expressions, so that we can use the results to build
    2469             :  * all the requested statistics types. This matters especially for
    2470             :  * expensive expressions, of course.
    2471             :  */
    2472             : static StatsBuildData *
    2473         348 : make_build_data(Relation rel, StatExtEntry *stat, int numrows, HeapTuple *rows,
    2474             :                 VacAttrStats **stats, int stattarget)
    2475             : {
    2476             :     /* evaluated expressions */
    2477             :     StatsBuildData *result;
    2478             :     char       *ptr;
    2479             :     Size        len;
    2480             : 
    2481             :     int         i;
    2482             :     int         k;
    2483             :     int         idx;
    2484             :     TupleTableSlot *slot;
    2485             :     EState     *estate;
    2486             :     ExprContext *econtext;
    2487         348 :     List       *exprstates = NIL;
    2488         348 :     int         nkeys = bms_num_members(stat->columns) + list_length(stat->exprs);
    2489             :     ListCell   *lc;
    2490             : 
    2491             :     /* allocate everything as a single chunk, so we can free it easily */
    2492         348 :     len = MAXALIGN(sizeof(StatsBuildData));
    2493         348 :     len += MAXALIGN(sizeof(AttrNumber) * nkeys);    /* attnums */
    2494         348 :     len += MAXALIGN(sizeof(VacAttrStats *) * nkeys);    /* stats */
    2495             : 
    2496             :     /* values */
    2497         348 :     len += MAXALIGN(sizeof(Datum *) * nkeys);
    2498         348 :     len += nkeys * MAXALIGN(sizeof(Datum) * numrows);
    2499             : 
    2500             :     /* nulls */
    2501         348 :     len += MAXALIGN(sizeof(bool *) * nkeys);
    2502         348 :     len += nkeys * MAXALIGN(sizeof(bool) * numrows);
    2503             : 
    2504         348 :     ptr = palloc(len);
    2505             : 
    2506             :     /* set the pointers */
    2507         348 :     result = (StatsBuildData *) ptr;
    2508         348 :     ptr += MAXALIGN(sizeof(StatsBuildData));
    2509             : 
    2510             :     /* attnums */
    2511         348 :     result->attnums = (AttrNumber *) ptr;
    2512         348 :     ptr += MAXALIGN(sizeof(AttrNumber) * nkeys);
    2513             : 
    2514             :     /* stats */
    2515         348 :     result->stats = (VacAttrStats **) ptr;
    2516         348 :     ptr += MAXALIGN(sizeof(VacAttrStats *) * nkeys);
    2517             : 
    2518             :     /* values */
    2519         348 :     result->values = (Datum **) ptr;
    2520         348 :     ptr += MAXALIGN(sizeof(Datum *) * nkeys);
    2521             : 
    2522             :     /* nulls */
    2523         348 :     result->nulls = (bool **) ptr;
    2524         348 :     ptr += MAXALIGN(sizeof(bool *) * nkeys);
    2525             : 
    2526        1248 :     for (i = 0; i < nkeys; i++)
    2527             :     {
    2528         900 :         result->values[i] = (Datum *) ptr;
    2529         900 :         ptr += MAXALIGN(sizeof(Datum) * numrows);
    2530             : 
    2531         900 :         result->nulls[i] = (bool *) ptr;
    2532         900 :         ptr += MAXALIGN(sizeof(bool) * numrows);
    2533             :     }
    2534             : 
    2535             :     Assert((ptr - (char *) result) == len);
    2536             : 
    2537             :     /* we have it allocated, so let's fill the values */
    2538         348 :     result->nattnums = nkeys;
    2539         348 :     result->numrows = numrows;
    2540             : 
    2541             :     /* fill the attribute info - first attributes, then expressions */
    2542         348 :     idx = 0;
    2543         348 :     k = -1;
    2544         960 :     while ((k = bms_next_member(stat->columns, k)) >= 0)
    2545             :     {
    2546         612 :         result->attnums[idx] = k;
    2547         612 :         result->stats[idx] = stats[idx];
    2548             : 
    2549         612 :         idx++;
    2550             :     }
    2551             : 
    2552         348 :     k = -1;
    2553         636 :     foreach(lc, stat->exprs)
    2554             :     {
    2555         288 :         Node       *expr = (Node *) lfirst(lc);
    2556             : 
    2557         288 :         result->attnums[idx] = k;
    2558         288 :         result->stats[idx] = examine_expression(expr, stattarget);
    2559             : 
    2560         288 :         idx++;
    2561         288 :         k--;
    2562             :     }
    2563             : 
    2564             :     /* first extract values for all the regular attributes */
    2565      738966 :     for (i = 0; i < numrows; i++)
    2566             :     {
    2567      738618 :         idx = 0;
    2568      738618 :         k = -1;
    2569     2432454 :         while ((k = bms_next_member(stat->columns, k)) >= 0)
    2570             :         {
    2571     3387672 :             result->values[idx][i] = heap_getattr(rows[i], k,
    2572     1693836 :                                                   result->stats[idx]->tupDesc,
    2573     1693836 :                                                   &result->nulls[idx][i]);
    2574             : 
    2575     1693836 :             idx++;
    2576             :         }
    2577             :     }
    2578             : 
    2579             :     /* Need an EState for evaluation expressions. */
    2580         348 :     estate = CreateExecutorState();
    2581         348 :     econtext = GetPerTupleExprContext(estate);
    2582             : 
    2583             :     /* Need a slot to hold the current heap tuple, too */
    2584         348 :     slot = MakeSingleTupleTableSlot(RelationGetDescr(rel),
    2585             :                                     &TTSOpsHeapTuple);
    2586             : 
    2587             :     /* Arrange for econtext's scan tuple to be the tuple under test */
    2588         348 :     econtext->ecxt_scantuple = slot;
    2589             : 
    2590             :     /* Set up expression evaluation state */
    2591         348 :     exprstates = ExecPrepareExprList(stat->exprs, estate);
    2592             : 
    2593      738966 :     for (i = 0; i < numrows; i++)
    2594             :     {
    2595             :         /*
    2596             :          * Reset the per-tuple context each time, to reclaim any cruft left
    2597             :          * behind by evaluating the statistics object expressions.
    2598             :          */
    2599      738618 :         ResetExprContext(econtext);
    2600             : 
    2601             :         /* Set up for expression evaluation */
    2602      738618 :         ExecStoreHeapTuple(rows[i], slot, false);
    2603             : 
    2604      738618 :         idx = bms_num_members(stat->columns);
    2605     1138212 :         foreach(lc, exprstates)
    2606             :         {
    2607             :             Datum       datum;
    2608             :             bool        isnull;
    2609      399594 :             ExprState  *exprstate = (ExprState *) lfirst(lc);
    2610             : 
    2611             :             /*
    2612             :              * XXX This probably leaks memory. Maybe we should use
    2613             :              * ExecEvalExprSwitchContext but then we need to copy the result
    2614             :              * somewhere else.
    2615             :              */
    2616      399594 :             datum = ExecEvalExpr(exprstate,
    2617      399594 :                                  GetPerTupleExprContext(estate),
    2618             :                                  &isnull);
    2619      399594 :             if (isnull)
    2620             :             {
    2621           0 :                 result->values[idx][i] = (Datum) 0;
    2622           0 :                 result->nulls[idx][i] = true;
    2623             :             }
    2624             :             else
    2625             :             {
    2626      399594 :                 result->values[idx][i] = (Datum) datum;
    2627      399594 :                 result->nulls[idx][i] = false;
    2628             :             }
    2629             : 
    2630      399594 :             idx++;
    2631             :         }
    2632             :     }
    2633             : 
    2634         348 :     ExecDropSingleTupleTableSlot(slot);
    2635         348 :     FreeExecutorState(estate);
    2636             : 
    2637         348 :     return result;
    2638             : }

Generated by: LCOV version 1.14