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

Generated by: LCOV version 1.16