LCOV - code coverage report
Current view: top level - src/backend/statistics - extended_stats.c (source / functions) Hit Total Coverage
Test: PostgreSQL 19devel Lines: 722 779 92.7 %
Date: 2025-09-17 23:18:08 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       10834 : 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       10834 :     if (!natts)
     124          18 :         return;
     125             : 
     126             :     /* the list of stats has to be allocated outside the memory context */
     127       10816 :     pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
     128       10816 :     statslist = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
     129             : 
     130             :     /* memory context for building each statistics object */
     131       10816 :     cxt = AllocSetContextCreate(CurrentMemoryContext,
     132             :                                 "BuildRelationExtStatistics",
     133             :                                 ALLOCSET_DEFAULT_SIZES);
     134       10816 :     oldcxt = MemoryContextSwitchTo(cxt);
     135             : 
     136             :     /* report this phase */
     137       10816 :     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       10816 :     ext_cnt = 0;
     152       11232 :     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       10816 :     MemoryContextSwitchTo(oldcxt);
     241       10816 :     MemoryContextDelete(cxt);
     242             : 
     243       10816 :     list_free(statslist);
     244             : 
     245       10816 :     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       16046 : 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       16046 :     int         result = 0;
     271             : 
     272             :     /* If there are no columns to analyze, just return 0. */
     273       16046 :     if (!natts)
     274          72 :         return 0;
     275             : 
     276       15974 :     cxt = AllocSetContextCreate(CurrentMemoryContext,
     277             :                                 "ComputeExtStatisticsRows",
     278             :                                 ALLOCSET_DEFAULT_SIZES);
     279       15974 :     oldcxt = MemoryContextSwitchTo(cxt);
     280             : 
     281       15974 :     pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
     282       15974 :     lstats = fetch_statentries_for_relation(pg_stext, RelationGetRelid(onerel));
     283             : 
     284       16390 :     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       15974 :     table_close(pg_stext, RowExclusiveLock);
     315             : 
     316       15974 :     MemoryContextSwitchTo(oldcxt);
     317       15974 :     MemoryContextDelete(cxt);
     318             : 
     319             :     /* compute sample size based on the statistics target */
     320       15974 :     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       26790 : fetch_statentries_for_relation(Relation pg_statext, Oid relid)
     420             : {
     421             :     SysScanDesc scan;
     422             :     ScanKeyData skey;
     423             :     HeapTuple   htup;
     424       26790 :     List       *result = NIL;
     425             : 
     426             :     /*
     427             :      * Prepare to scan pg_statistic_ext for entries having stxrelid = this
     428             :      * rel.
     429             :      */
     430       26790 :     ScanKeyInit(&skey,
     431             :                 Anum_pg_statistic_ext_stxrelid,
     432             :                 BTEqualStrategyNumber, F_OIDEQ,
     433             :                 ObjectIdGetDatum(relid));
     434             : 
     435       26790 :     scan = systable_beginscan(pg_statext, StatisticExtRelidIndexId, true,
     436             :                               NULL, 1, &skey);
     437             : 
     438       27622 :     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       26790 :     systable_endscan(scan);
     514             : 
     515       26790 :     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             :                 nrows;
     990         846 :     int         nvalues = data->numrows * numattrs;
     991             :     Size        len;
     992             :     SortItem   *items;
     993             :     Datum      *values;
     994             :     bool       *isnull;
     995             :     char       *ptr;
     996             :     int        *typlen;
     997             : 
     998             :     /* Compute the total amount of memory we need (both items and values). */
     999         846 :     len = MAXALIGN(data->numrows * sizeof(SortItem)) +
    1000         846 :         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             :     /* MAXALIGN ensures that the following Datums are suitably aligned */
    1008         846 :     ptr += MAXALIGN(data->numrows * sizeof(SortItem));
    1009             : 
    1010             :     /* values and null flags */
    1011         846 :     values = (Datum *) ptr;
    1012         846 :     ptr += nvalues * sizeof(Datum);
    1013             : 
    1014         846 :     isnull = (bool *) ptr;
    1015         846 :     ptr += nvalues * sizeof(bool);
    1016             : 
    1017             :     /* make sure we consumed the whole buffer exactly */
    1018             :     Assert((ptr - (char *) items) == len);
    1019             : 
    1020             :     /* fix the pointers to Datum and bool arrays */
    1021         846 :     nrows = 0;
    1022     1989204 :     for (i = 0; i < data->numrows; i++)
    1023             :     {
    1024     1988358 :         items[nrows].values = &values[nrows * numattrs];
    1025     1988358 :         items[nrows].isnull = &isnull[nrows * numattrs];
    1026             : 
    1027     1988358 :         nrows++;
    1028             :     }
    1029             : 
    1030             :     /* build a local cache of typlen for all attributes */
    1031         846 :     typlen = (int *) palloc(sizeof(int) * data->nattnums);
    1032        3120 :     for (i = 0; i < data->nattnums; i++)
    1033        2274 :         typlen[i] = get_typlen(data->stats[i]->attrtypid);
    1034             : 
    1035         846 :     nrows = 0;
    1036     1989204 :     for (i = 0; i < data->numrows; i++)
    1037             :     {
    1038     1988358 :         bool        toowide = false;
    1039             : 
    1040             :         /* load the values/null flags from sample rows */
    1041     6841650 :         for (j = 0; j < numattrs; j++)
    1042             :         {
    1043             :             Datum       value;
    1044             :             bool        isnull;
    1045             :             int         attlen;
    1046     4853292 :             AttrNumber  attnum = attnums[j];
    1047             : 
    1048             :             int         idx;
    1049             : 
    1050             :             /* match attnum to the pre-calculated data */
    1051     9566766 :             for (idx = 0; idx < data->nattnums; idx++)
    1052             :             {
    1053     9566766 :                 if (attnum == data->attnums[idx])
    1054     4853292 :                     break;
    1055             :             }
    1056             : 
    1057             :             Assert(idx < data->nattnums);
    1058             : 
    1059     4853292 :             value = data->values[idx][i];
    1060     4853292 :             isnull = data->nulls[idx][i];
    1061     4853292 :             attlen = typlen[idx];
    1062             : 
    1063             :             /*
    1064             :              * If this is a varlena value, check if it's too wide and if yes
    1065             :              * then skip the whole item. Otherwise detoast the value.
    1066             :              *
    1067             :              * XXX It may happen that we've already detoasted some preceding
    1068             :              * values for the current item. We don't bother to cleanup those
    1069             :              * on the assumption that those are small (below WIDTH_THRESHOLD)
    1070             :              * and will be discarded at the end of analyze.
    1071             :              */
    1072     4853292 :             if ((!isnull) && (attlen == -1))
    1073             :             {
    1074     1480308 :                 if (toast_raw_datum_size(value) > WIDTH_THRESHOLD)
    1075             :                 {
    1076           0 :                     toowide = true;
    1077           0 :                     break;
    1078             :                 }
    1079             : 
    1080     1480308 :                 value = PointerGetDatum(PG_DETOAST_DATUM(value));
    1081             :             }
    1082             : 
    1083     4853292 :             items[nrows].values[j] = value;
    1084     4853292 :             items[nrows].isnull[j] = isnull;
    1085             :         }
    1086             : 
    1087     1988358 :         if (toowide)
    1088           0 :             continue;
    1089             : 
    1090     1988358 :         nrows++;
    1091             :     }
    1092             : 
    1093             :     /* store the actual number of items (ignoring the too-wide ones) */
    1094         846 :     *nitems = nrows;
    1095             : 
    1096             :     /* all items were too wide */
    1097         846 :     if (nrows == 0)
    1098             :     {
    1099             :         /* everything is allocated as a single chunk */
    1100           0 :         pfree(items);
    1101           0 :         return NULL;
    1102             :     }
    1103             : 
    1104             :     /* do the sort, using the multi-sort */
    1105         846 :     qsort_interruptible(items, nrows, sizeof(SortItem),
    1106             :                         multi_sort_compare, mss);
    1107             : 
    1108         846 :     return items;
    1109             : }
    1110             : 
    1111             : /*
    1112             :  * has_stats_of_kind
    1113             :  *      Check whether the list contains statistic of a given kind
    1114             :  */
    1115             : bool
    1116        5028 : has_stats_of_kind(List *stats, char requiredkind)
    1117             : {
    1118             :     ListCell   *l;
    1119             : 
    1120        8286 :     foreach(l, stats)
    1121             :     {
    1122        5790 :         StatisticExtInfo *stat = (StatisticExtInfo *) lfirst(l);
    1123             : 
    1124        5790 :         if (stat->kind == requiredkind)
    1125        2532 :             return true;
    1126             :     }
    1127             : 
    1128        2496 :     return false;
    1129             : }
    1130             : 
    1131             : /*
    1132             :  * stat_find_expression
    1133             :  *      Search for an expression in statistics object's list of expressions.
    1134             :  *
    1135             :  * Returns the index of the expression in the statistics object's list of
    1136             :  * expressions, or -1 if not found.
    1137             :  */
    1138             : static int
    1139         594 : stat_find_expression(StatisticExtInfo *stat, Node *expr)
    1140             : {
    1141             :     ListCell   *lc;
    1142             :     int         idx;
    1143             : 
    1144         594 :     idx = 0;
    1145        1074 :     foreach(lc, stat->exprs)
    1146             :     {
    1147         972 :         Node       *stat_expr = (Node *) lfirst(lc);
    1148             : 
    1149         972 :         if (equal(stat_expr, expr))
    1150         492 :             return idx;
    1151         480 :         idx++;
    1152             :     }
    1153             : 
    1154             :     /* Expression not found */
    1155         102 :     return -1;
    1156             : }
    1157             : 
    1158             : /*
    1159             :  * stat_covers_expressions
    1160             :  *      Test whether a statistics object covers all expressions in a list.
    1161             :  *
    1162             :  * Returns true if all expressions are covered.  If expr_idxs is non-NULL, it
    1163             :  * is populated with the indexes of the expressions found.
    1164             :  */
    1165             : static bool
    1166        3114 : stat_covers_expressions(StatisticExtInfo *stat, List *exprs,
    1167             :                         Bitmapset **expr_idxs)
    1168             : {
    1169             :     ListCell   *lc;
    1170             : 
    1171        3606 :     foreach(lc, exprs)
    1172             :     {
    1173         594 :         Node       *expr = (Node *) lfirst(lc);
    1174             :         int         expr_idx;
    1175             : 
    1176         594 :         expr_idx = stat_find_expression(stat, expr);
    1177         594 :         if (expr_idx == -1)
    1178         102 :             return false;
    1179             : 
    1180         492 :         if (expr_idxs != NULL)
    1181         246 :             *expr_idxs = bms_add_member(*expr_idxs, expr_idx);
    1182             :     }
    1183             : 
    1184             :     /* If we reach here, all expressions are covered */
    1185        3012 :     return true;
    1186             : }
    1187             : 
    1188             : /*
    1189             :  * choose_best_statistics
    1190             :  *      Look for and return statistics with the specified 'requiredkind' which
    1191             :  *      have keys that match at least two of the given attnums.  Return NULL if
    1192             :  *      there's no match.
    1193             :  *
    1194             :  * The current selection criteria is very simple - we choose the statistics
    1195             :  * object referencing the most attributes in covered (and still unestimated
    1196             :  * clauses), breaking ties in favor of objects with fewer keys overall.
    1197             :  *
    1198             :  * The clause_attnums is an array of bitmaps, storing attnums for individual
    1199             :  * clauses. A NULL element means the clause is either incompatible or already
    1200             :  * estimated.
    1201             :  *
    1202             :  * XXX If multiple statistics objects tie on both criteria, then which object
    1203             :  * is chosen depends on the order that they appear in the stats list. Perhaps
    1204             :  * further tiebreakers are needed.
    1205             :  */
    1206             : StatisticExtInfo *
    1207        1350 : choose_best_statistics(List *stats, char requiredkind, bool inh,
    1208             :                        Bitmapset **clause_attnums, List **clause_exprs,
    1209             :                        int nclauses)
    1210             : {
    1211             :     ListCell   *lc;
    1212        1350 :     StatisticExtInfo *best_match = NULL;
    1213        1350 :     int         best_num_matched = 2;   /* goal #1: maximize */
    1214        1350 :     int         best_match_keys = (STATS_MAX_DIMENSIONS + 1);   /* goal #2: minimize */
    1215             : 
    1216        3546 :     foreach(lc, stats)
    1217             :     {
    1218             :         int         i;
    1219        2196 :         StatisticExtInfo *info = (StatisticExtInfo *) lfirst(lc);
    1220        2196 :         Bitmapset  *matched_attnums = NULL;
    1221        2196 :         Bitmapset  *matched_exprs = NULL;
    1222             :         int         num_matched;
    1223             :         int         numkeys;
    1224             : 
    1225             :         /* skip statistics that are not of the correct type */
    1226        2196 :         if (info->kind != requiredkind)
    1227         468 :             continue;
    1228             : 
    1229             :         /* skip statistics with mismatching inheritance flag */
    1230        1728 :         if (info->inherit != inh)
    1231          24 :             continue;
    1232             : 
    1233             :         /*
    1234             :          * Collect attributes and expressions in remaining (unestimated)
    1235             :          * clauses fully covered by this statistic object.
    1236             :          *
    1237             :          * We know already estimated clauses have both clause_attnums and
    1238             :          * clause_exprs set to NULL. We leave the pointers NULL if already
    1239             :          * estimated, or we reset them to NULL after estimating the clause.
    1240             :          */
    1241        5796 :         for (i = 0; i < nclauses; i++)
    1242             :         {
    1243        4092 :             Bitmapset  *expr_idxs = NULL;
    1244             : 
    1245             :             /* ignore incompatible/estimated clauses */
    1246        4092 :             if (!clause_attnums[i] && !clause_exprs[i])
    1247        2484 :                 continue;
    1248             : 
    1249             :             /* ignore clauses that are not covered by this object */
    1250        2034 :             if (!bms_is_subset(clause_attnums[i], info->keys) ||
    1251        1704 :                 !stat_covers_expressions(info, clause_exprs[i], &expr_idxs))
    1252         426 :                 continue;
    1253             : 
    1254             :             /* record attnums and indexes of expressions covered */
    1255        1608 :             matched_attnums = bms_add_members(matched_attnums, clause_attnums[i]);
    1256        1608 :             matched_exprs = bms_add_members(matched_exprs, expr_idxs);
    1257             :         }
    1258             : 
    1259        1704 :         num_matched = bms_num_members(matched_attnums) + bms_num_members(matched_exprs);
    1260             : 
    1261        1704 :         bms_free(matched_attnums);
    1262        1704 :         bms_free(matched_exprs);
    1263             : 
    1264             :         /*
    1265             :          * save the actual number of keys in the stats so that we can choose
    1266             :          * the narrowest stats with the most matching keys.
    1267             :          */
    1268        1704 :         numkeys = bms_num_members(info->keys) + list_length(info->exprs);
    1269             : 
    1270             :         /*
    1271             :          * Use this object when it increases the number of matched attributes
    1272             :          * and expressions or when it matches the same number of attributes
    1273             :          * and expressions but these stats have fewer keys than any previous
    1274             :          * match.
    1275             :          */
    1276        1704 :         if (num_matched > best_num_matched ||
    1277         414 :             (num_matched == best_num_matched && numkeys < best_match_keys))
    1278             :         {
    1279         606 :             best_match = info;
    1280         606 :             best_num_matched = num_matched;
    1281         606 :             best_match_keys = numkeys;
    1282             :         }
    1283             :     }
    1284             : 
    1285        1350 :     return best_match;
    1286             : }
    1287             : 
    1288             : /*
    1289             :  * statext_is_compatible_clause_internal
    1290             :  *      Determines if the clause is compatible with MCV lists.
    1291             :  *
    1292             :  * To be compatible, the given clause must be a combination of supported
    1293             :  * clauses built from Vars or sub-expressions (where a sub-expression is
    1294             :  * something that exactly matches an expression found in statistics objects).
    1295             :  * This function recursively examines the clause and extracts any
    1296             :  * sub-expressions that will need to be matched against statistics.
    1297             :  *
    1298             :  * Currently, we only support the following types of clauses:
    1299             :  *
    1300             :  * (a) OpExprs of the form (Var/Expr op Const), or (Const op Var/Expr), where
    1301             :  * the op is one of ("=", "<", ">", ">=", "<=")
    1302             :  *
    1303             :  * (b) (Var/Expr IS [NOT] NULL)
    1304             :  *
    1305             :  * (c) combinations using AND/OR/NOT
    1306             :  *
    1307             :  * (d) ScalarArrayOpExprs of the form (Var/Expr op ANY (Const)) or
    1308             :  * (Var/Expr op ALL (Const))
    1309             :  *
    1310             :  * In the future, the range of supported clauses may be expanded to more
    1311             :  * complex cases, for example (Var op Var).
    1312             :  *
    1313             :  * Arguments:
    1314             :  * clause: (sub)clause to be inspected (bare clause, not a RestrictInfo)
    1315             :  * relid: rel that all Vars in clause must belong to
    1316             :  * *attnums: input/output parameter collecting attribute numbers of all
    1317             :  *      mentioned Vars.  Note that we do not offset the attribute numbers,
    1318             :  *      so we can't cope with system columns.
    1319             :  * *exprs: input/output parameter collecting primitive subclauses within
    1320             :  *      the clause tree
    1321             :  * *leakproof: input/output parameter recording the leakproofness of the
    1322             :  *      clause tree.  This should be true initially, and will be set to false
    1323             :  *      if any operator function used in an OpExpr is not leakproof.
    1324             :  *
    1325             :  * Returns false if there is something we definitively can't handle.
    1326             :  * On true return, we can proceed to match the *exprs against statistics.
    1327             :  */
    1328             : static bool
    1329        3462 : statext_is_compatible_clause_internal(PlannerInfo *root, Node *clause,
    1330             :                                       Index relid, Bitmapset **attnums,
    1331             :                                       List **exprs, bool *leakproof)
    1332             : {
    1333             :     /* Look inside any binary-compatible relabeling (as in examine_variable) */
    1334        3462 :     if (IsA(clause, RelabelType))
    1335           0 :         clause = (Node *) ((RelabelType *) clause)->arg;
    1336             : 
    1337             :     /* plain Var references (boolean Vars or recursive checks) */
    1338        3462 :     if (IsA(clause, Var))
    1339             :     {
    1340        1548 :         Var        *var = (Var *) clause;
    1341             : 
    1342             :         /* Ensure var is from the correct relation */
    1343        1548 :         if (var->varno != relid)
    1344           0 :             return false;
    1345             : 
    1346             :         /* we also better ensure the Var is from the current level */
    1347        1548 :         if (var->varlevelsup > 0)
    1348           0 :             return false;
    1349             : 
    1350             :         /*
    1351             :          * Also reject system attributes and whole-row Vars (we don't allow
    1352             :          * stats on those).
    1353             :          */
    1354        1548 :         if (!AttrNumberIsForUserDefinedAttr(var->varattno))
    1355           0 :             return false;
    1356             : 
    1357             :         /* OK, record the attnum for later permissions checks. */
    1358        1548 :         *attnums = bms_add_member(*attnums, var->varattno);
    1359             : 
    1360        1548 :         return true;
    1361             :     }
    1362             : 
    1363             :     /* (Var/Expr op Const) or (Const op Var/Expr) */
    1364        1914 :     if (is_opclause(clause))
    1365             :     {
    1366        1392 :         OpExpr     *expr = (OpExpr *) clause;
    1367             :         Node       *clause_expr;
    1368             : 
    1369             :         /* Only expressions with two arguments are considered compatible. */
    1370        1392 :         if (list_length(expr->args) != 2)
    1371           0 :             return false;
    1372             : 
    1373             :         /* Check if the expression has the right shape */
    1374        1392 :         if (!examine_opclause_args(expr->args, &clause_expr, NULL, NULL))
    1375           0 :             return false;
    1376             : 
    1377             :         /*
    1378             :          * If it's not one of the supported operators ("=", "<", ">", etc.),
    1379             :          * just ignore the clause, as it's not compatible with MCV lists.
    1380             :          *
    1381             :          * This uses the function for estimating selectivity, not the operator
    1382             :          * directly (a bit awkward, but well ...).
    1383             :          */
    1384        1392 :         switch (get_oprrest(expr->opno))
    1385             :         {
    1386        1392 :             case F_EQSEL:
    1387             :             case F_NEQSEL:
    1388             :             case F_SCALARLTSEL:
    1389             :             case F_SCALARLESEL:
    1390             :             case F_SCALARGTSEL:
    1391             :             case F_SCALARGESEL:
    1392             :                 /* supported, will continue with inspection of the Var/Expr */
    1393        1392 :                 break;
    1394             : 
    1395           0 :             default:
    1396             :                 /* other estimators are considered unknown/unsupported */
    1397           0 :                 return false;
    1398             :         }
    1399             : 
    1400             :         /* Check if the operator is leakproof */
    1401        1392 :         if (*leakproof)
    1402        1380 :             *leakproof = get_func_leakproof(get_opcode(expr->opno));
    1403             : 
    1404             :         /* Check (Var op Const) or (Const op Var) clauses by recursing. */
    1405        1392 :         if (IsA(clause_expr, Var))
    1406        1152 :             return statext_is_compatible_clause_internal(root, clause_expr,
    1407             :                                                          relid, attnums,
    1408             :                                                          exprs, leakproof);
    1409             : 
    1410             :         /* Otherwise we have (Expr op Const) or (Const op Expr). */
    1411         240 :         *exprs = lappend(*exprs, clause_expr);
    1412         240 :         return true;
    1413             :     }
    1414             : 
    1415             :     /* Var/Expr IN Array */
    1416         522 :     if (IsA(clause, ScalarArrayOpExpr))
    1417             :     {
    1418         288 :         ScalarArrayOpExpr *expr = (ScalarArrayOpExpr *) clause;
    1419             :         Node       *clause_expr;
    1420             :         bool        expronleft;
    1421             : 
    1422             :         /* Only expressions with two arguments are considered compatible. */
    1423         288 :         if (list_length(expr->args) != 2)
    1424           0 :             return false;
    1425             : 
    1426             :         /* Check if the expression has the right shape (one Var, one Const) */
    1427         288 :         if (!examine_opclause_args(expr->args, &clause_expr, NULL, &expronleft))
    1428           0 :             return false;
    1429             : 
    1430             :         /* We only support Var on left, Const on right */
    1431         288 :         if (!expronleft)
    1432           6 :             return false;
    1433             : 
    1434             :         /*
    1435             :          * If it's not one of the supported operators ("=", "<", ">", etc.),
    1436             :          * just ignore the clause, as it's not compatible with MCV lists.
    1437             :          *
    1438             :          * This uses the function for estimating selectivity, not the operator
    1439             :          * directly (a bit awkward, but well ...).
    1440             :          */
    1441         282 :         switch (get_oprrest(expr->opno))
    1442             :         {
    1443         282 :             case F_EQSEL:
    1444             :             case F_NEQSEL:
    1445             :             case F_SCALARLTSEL:
    1446             :             case F_SCALARLESEL:
    1447             :             case F_SCALARGTSEL:
    1448             :             case F_SCALARGESEL:
    1449             :                 /* supported, will continue with inspection of the Var/Expr */
    1450         282 :                 break;
    1451             : 
    1452           0 :             default:
    1453             :                 /* other estimators are considered unknown/unsupported */
    1454           0 :                 return false;
    1455             :         }
    1456             : 
    1457             :         /* Check if the operator is leakproof */
    1458         282 :         if (*leakproof)
    1459         282 :             *leakproof = get_func_leakproof(get_opcode(expr->opno));
    1460             : 
    1461             :         /* Check Var IN Array clauses by recursing. */
    1462         282 :         if (IsA(clause_expr, Var))
    1463         228 :             return statext_is_compatible_clause_internal(root, clause_expr,
    1464             :                                                          relid, attnums,
    1465             :                                                          exprs, leakproof);
    1466             : 
    1467             :         /* Otherwise we have Expr IN Array. */
    1468          54 :         *exprs = lappend(*exprs, clause_expr);
    1469          54 :         return true;
    1470             :     }
    1471             : 
    1472             :     /* AND/OR/NOT clause */
    1473         468 :     if (is_andclause(clause) ||
    1474         414 :         is_orclause(clause) ||
    1475         180 :         is_notclause(clause))
    1476             :     {
    1477             :         /*
    1478             :          * AND/OR/NOT-clauses are supported if all sub-clauses are supported
    1479             :          *
    1480             :          * Perhaps we could improve this by handling mixed cases, when some of
    1481             :          * the clauses are supported and some are not. Selectivity for the
    1482             :          * supported subclauses would be computed using extended statistics,
    1483             :          * and the remaining clauses would be estimated using the traditional
    1484             :          * algorithm (product of selectivities).
    1485             :          *
    1486             :          * It however seems overly complex, and in a way we already do that
    1487             :          * because if we reject the whole clause as unsupported here, it will
    1488             :          * be eventually passed to clauselist_selectivity() which does exactly
    1489             :          * this (split into supported/unsupported clauses etc).
    1490             :          */
    1491          84 :         BoolExpr   *expr = (BoolExpr *) clause;
    1492             :         ListCell   *lc;
    1493             : 
    1494         222 :         foreach(lc, expr->args)
    1495             :         {
    1496             :             /*
    1497             :              * If we find an incompatible clause in the arguments, treat the
    1498             :              * whole clause as incompatible.
    1499             :              */
    1500         138 :             if (!statext_is_compatible_clause_internal(root,
    1501         138 :                                                        (Node *) lfirst(lc),
    1502             :                                                        relid, attnums, exprs,
    1503             :                                                        leakproof))
    1504           0 :                 return false;
    1505             :         }
    1506             : 
    1507          84 :         return true;
    1508             :     }
    1509             : 
    1510             :     /* Var/Expr IS NULL */
    1511         150 :     if (IsA(clause, NullTest))
    1512             :     {
    1513         144 :         NullTest   *nt = (NullTest *) clause;
    1514             : 
    1515             :         /* Check Var IS NULL clauses by recursing. */
    1516         144 :         if (IsA(nt->arg, Var))
    1517          90 :             return statext_is_compatible_clause_internal(root,
    1518          90 :                                                          (Node *) (nt->arg),
    1519             :                                                          relid, attnums,
    1520             :                                                          exprs, leakproof);
    1521             : 
    1522             :         /* Otherwise we have Expr IS NULL. */
    1523          54 :         *exprs = lappend(*exprs, nt->arg);
    1524          54 :         return true;
    1525             :     }
    1526             : 
    1527             :     /*
    1528             :      * Treat any other expressions as bare expressions to be matched against
    1529             :      * expressions in statistics objects.
    1530             :      */
    1531           6 :     *exprs = lappend(*exprs, clause);
    1532           6 :     return true;
    1533             : }
    1534             : 
    1535             : /*
    1536             :  * statext_is_compatible_clause
    1537             :  *      Determines if the clause is compatible with MCV lists.
    1538             :  *
    1539             :  * See statext_is_compatible_clause_internal, above, for the basic rules.
    1540             :  * This layer deals with RestrictInfo superstructure and applies permissions
    1541             :  * checks to verify that it's okay to examine all mentioned Vars.
    1542             :  *
    1543             :  * Arguments:
    1544             :  * clause: clause to be inspected (in RestrictInfo form)
    1545             :  * relid: rel that all Vars in clause must belong to
    1546             :  * *attnums: input/output parameter collecting attribute numbers of all
    1547             :  *      mentioned Vars.  Note that we do not offset the attribute numbers,
    1548             :  *      so we can't cope with system columns.
    1549             :  * *exprs: input/output parameter collecting primitive subclauses within
    1550             :  *      the clause tree
    1551             :  *
    1552             :  * Returns false if there is something we definitively can't handle.
    1553             :  * On true return, we can proceed to match the *exprs against statistics.
    1554             :  */
    1555             : static bool
    1556        1908 : statext_is_compatible_clause(PlannerInfo *root, Node *clause, Index relid,
    1557             :                              Bitmapset **attnums, List **exprs)
    1558             : {
    1559             :     RestrictInfo *rinfo;
    1560             :     int         clause_relid;
    1561             :     bool        leakproof;
    1562             : 
    1563             :     /*
    1564             :      * Special-case handling for bare BoolExpr AND clauses, because the
    1565             :      * restrictinfo machinery doesn't build RestrictInfos on top of AND
    1566             :      * clauses.
    1567             :      */
    1568        1908 :     if (is_andclause(clause))
    1569             :     {
    1570          48 :         BoolExpr   *expr = (BoolExpr *) clause;
    1571             :         ListCell   *lc;
    1572             : 
    1573             :         /*
    1574             :          * Check that each sub-clause is compatible.  We expect these to be
    1575             :          * RestrictInfos.
    1576             :          */
    1577         162 :         foreach(lc, expr->args)
    1578             :         {
    1579         114 :             if (!statext_is_compatible_clause(root, (Node *) lfirst(lc),
    1580             :                                               relid, attnums, exprs))
    1581           0 :                 return false;
    1582             :         }
    1583             : 
    1584          48 :         return true;
    1585             :     }
    1586             : 
    1587             :     /* Otherwise it must be a RestrictInfo. */
    1588        1860 :     if (!IsA(clause, RestrictInfo))
    1589           0 :         return false;
    1590        1860 :     rinfo = (RestrictInfo *) clause;
    1591             : 
    1592             :     /* Pseudoconstants are not really interesting here. */
    1593        1860 :     if (rinfo->pseudoconstant)
    1594           6 :         return false;
    1595             : 
    1596             :     /* Clauses referencing other varnos are incompatible. */
    1597        1854 :     if (!bms_get_singleton_member(rinfo->clause_relids, &clause_relid) ||
    1598        1854 :         clause_relid != relid)
    1599           0 :         return false;
    1600             : 
    1601             :     /*
    1602             :      * Check the clause, determine what attributes it references, and whether
    1603             :      * it includes any non-leakproof operators.
    1604             :      */
    1605        1854 :     leakproof = true;
    1606        1854 :     if (!statext_is_compatible_clause_internal(root, (Node *) rinfo->clause,
    1607             :                                                relid, attnums, exprs,
    1608             :                                                &leakproof))
    1609           6 :         return false;
    1610             : 
    1611             :     /*
    1612             :      * If the clause includes any non-leakproof operators, check that the user
    1613             :      * has permission to read all required attributes, otherwise the operators
    1614             :      * might reveal values from the MCV list that the user doesn't have
    1615             :      * permission to see.  We require all rows to be selectable --- there must
    1616             :      * be no securityQuals from security barrier views or RLS policies.  See
    1617             :      * similar code in examine_variable(), examine_simple_variable(), and
    1618             :      * statistic_proc_security_check().
    1619             :      *
    1620             :      * Note that for an inheritance child, the permission checks are performed
    1621             :      * on the inheritance root parent, and whole-table select privilege on the
    1622             :      * parent doesn't guarantee that the user could read all columns of the
    1623             :      * child. Therefore we must check all referenced columns.
    1624             :      */
    1625        1848 :     if (!leakproof)
    1626             :     {
    1627         252 :         Bitmapset  *clause_attnums = NULL;
    1628         252 :         int         attnum = -1;
    1629             : 
    1630             :         /*
    1631             :          * We have to check per-column privileges.  *attnums has the attnums
    1632             :          * for individual Vars we saw, but there may also be Vars within
    1633             :          * subexpressions in *exprs.  We can use pull_varattnos() to extract
    1634             :          * those, but there's an impedance mismatch: attnums returned by
    1635             :          * pull_varattnos() are offset by FirstLowInvalidHeapAttributeNumber,
    1636             :          * while attnums within *attnums aren't.  Convert *attnums to the
    1637             :          * offset style so we can combine the results.
    1638             :          */
    1639         492 :         while ((attnum = bms_next_member(*attnums, attnum)) >= 0)
    1640             :         {
    1641         240 :             clause_attnums =
    1642         240 :                 bms_add_member(clause_attnums,
    1643             :                                attnum - FirstLowInvalidHeapAttributeNumber);
    1644             :         }
    1645             : 
    1646             :         /* Now merge attnums from *exprs into clause_attnums */
    1647         252 :         if (*exprs != NIL)
    1648          48 :             pull_varattnos((Node *) *exprs, relid, &clause_attnums);
    1649             : 
    1650             :         /* Must have permission to read all rows from these columns */
    1651         252 :         if (!all_rows_selectable(root, relid, clause_attnums))
    1652         228 :             return false;
    1653             :     }
    1654             : 
    1655             :     /* If we reach here, the clause is OK */
    1656        1620 :     return true;
    1657             : }
    1658             : 
    1659             : /*
    1660             :  * statext_mcv_clauselist_selectivity
    1661             :  *      Estimate clauses using the best multi-column statistics.
    1662             :  *
    1663             :  * Applies available extended (multi-column) statistics on a table. There may
    1664             :  * be multiple applicable statistics (with respect to the clauses), in which
    1665             :  * case we use greedy approach. In each round we select the best statistic on
    1666             :  * a table (measured by the number of attributes extracted from the clauses
    1667             :  * and covered by it), and compute the selectivity for the supplied clauses.
    1668             :  * We repeat this process with the remaining clauses (if any), until none of
    1669             :  * the available statistics can be used.
    1670             :  *
    1671             :  * One of the main challenges with using MCV lists is how to extrapolate the
    1672             :  * estimate to the data not covered by the MCV list. To do that, we compute
    1673             :  * not only the "MCV selectivity" (selectivities for MCV items matching the
    1674             :  * supplied clauses), but also the following related selectivities:
    1675             :  *
    1676             :  * - simple selectivity:  Computed without extended statistics, i.e. as if the
    1677             :  * columns/clauses were independent.
    1678             :  *
    1679             :  * - base selectivity:  Similar to simple selectivity, but is computed using
    1680             :  * the extended statistic by adding up the base frequencies (that we compute
    1681             :  * and store for each MCV item) of matching MCV items.
    1682             :  *
    1683             :  * - total selectivity: Selectivity covered by the whole MCV list.
    1684             :  *
    1685             :  * These are passed to mcv_combine_selectivities() which combines them to
    1686             :  * produce a selectivity estimate that makes use of both per-column statistics
    1687             :  * and the multi-column MCV statistics.
    1688             :  *
    1689             :  * 'estimatedclauses' is an input/output parameter.  We set bits for the
    1690             :  * 0-based 'clauses' indexes we estimate for and also skip clause items that
    1691             :  * already have a bit set.
    1692             :  */
    1693             : static Selectivity
    1694        2592 : statext_mcv_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
    1695             :                                    JoinType jointype, SpecialJoinInfo *sjinfo,
    1696             :                                    RelOptInfo *rel, Bitmapset **estimatedclauses,
    1697             :                                    bool is_or)
    1698             : {
    1699             :     ListCell   *l;
    1700             :     Bitmapset **list_attnums;   /* attnums extracted from the clause */
    1701             :     List      **list_exprs;     /* expressions matched to any statistic */
    1702             :     int         listidx;
    1703        2592 :     Selectivity sel = (is_or) ? 0.0 : 1.0;
    1704        2592 :     RangeTblEntry *rte = planner_rt_fetch(rel->relid, root);
    1705             : 
    1706             :     /* check if there's any stats that might be useful for us. */
    1707        2592 :     if (!has_stats_of_kind(rel->statlist, STATS_EXT_MCV))
    1708        1848 :         return sel;
    1709             : 
    1710         744 :     list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) *
    1711         744 :                                          list_length(clauses));
    1712             : 
    1713             :     /* expressions extracted from complex expressions */
    1714         744 :     list_exprs = (List **) palloc(sizeof(Node *) * list_length(clauses));
    1715             : 
    1716             :     /*
    1717             :      * Pre-process the clauses list to extract the attnums and expressions
    1718             :      * seen in each item.  We need to determine if there are any clauses which
    1719             :      * will be useful for selectivity estimations with extended stats.  Along
    1720             :      * the way we'll record all of the attnums and expressions for each clause
    1721             :      * in lists which we'll reference later so we don't need to repeat the
    1722             :      * same work again.
    1723             :      *
    1724             :      * We also skip clauses that we already estimated using different types of
    1725             :      * statistics (we treat them as incompatible).
    1726             :      */
    1727         744 :     listidx = 0;
    1728        2538 :     foreach(l, clauses)
    1729             :     {
    1730        1794 :         Node       *clause = (Node *) lfirst(l);
    1731        1794 :         Bitmapset  *attnums = NULL;
    1732        1794 :         List       *exprs = NIL;
    1733             : 
    1734        3588 :         if (!bms_is_member(listidx, *estimatedclauses) &&
    1735        1794 :             statext_is_compatible_clause(root, clause, rel->relid, &attnums, &exprs))
    1736             :         {
    1737        1554 :             list_attnums[listidx] = attnums;
    1738        1554 :             list_exprs[listidx] = exprs;
    1739             :         }
    1740             :         else
    1741             :         {
    1742         240 :             list_attnums[listidx] = NULL;
    1743         240 :             list_exprs[listidx] = NIL;
    1744             :         }
    1745             : 
    1746        1794 :         listidx++;
    1747             :     }
    1748             : 
    1749             :     /* apply as many extended statistics as possible */
    1750             :     while (true)
    1751         606 :     {
    1752             :         StatisticExtInfo *stat;
    1753             :         List       *stat_clauses;
    1754             :         Bitmapset  *simple_clauses;
    1755             : 
    1756             :         /* find the best suited statistics object for these attnums */
    1757        1350 :         stat = choose_best_statistics(rel->statlist, STATS_EXT_MCV, rte->inh,
    1758             :                                       list_attnums, list_exprs,
    1759             :                                       list_length(clauses));
    1760             : 
    1761             :         /*
    1762             :          * if no (additional) matching stats could be found then we've nothing
    1763             :          * to do
    1764             :          */
    1765        1350 :         if (!stat)
    1766         744 :             break;
    1767             : 
    1768             :         /* Ensure choose_best_statistics produced an expected stats type. */
    1769             :         Assert(stat->kind == STATS_EXT_MCV);
    1770             : 
    1771             :         /* now filter the clauses to be estimated using the selected MCV */
    1772         606 :         stat_clauses = NIL;
    1773             : 
    1774             :         /* record which clauses are simple (single column or expression) */
    1775         606 :         simple_clauses = NULL;
    1776             : 
    1777         606 :         listidx = -1;
    1778        2112 :         foreach(l, clauses)
    1779             :         {
    1780             :             /* Increment the index before we decide if to skip the clause. */
    1781        1506 :             listidx++;
    1782             : 
    1783             :             /*
    1784             :              * Ignore clauses from which we did not extract any attnums or
    1785             :              * expressions (this needs to be consistent with what we do in
    1786             :              * choose_best_statistics).
    1787             :              *
    1788             :              * This also eliminates already estimated clauses - both those
    1789             :              * estimated before and during applying extended statistics.
    1790             :              *
    1791             :              * XXX This check is needed because both bms_is_subset and
    1792             :              * stat_covers_expressions return true for empty attnums and
    1793             :              * expressions.
    1794             :              */
    1795        1506 :             if (!list_attnums[listidx] && !list_exprs[listidx])
    1796          36 :                 continue;
    1797             : 
    1798             :             /*
    1799             :              * The clause was not estimated yet, and we've extracted either
    1800             :              * attnums or expressions from it. Ignore it if it's not fully
    1801             :              * covered by the chosen statistics object.
    1802             :              *
    1803             :              * We need to check both attributes and expressions, and reject if
    1804             :              * either is not covered.
    1805             :              */
    1806        1470 :             if (!bms_is_subset(list_attnums[listidx], stat->keys) ||
    1807        1410 :                 !stat_covers_expressions(stat, list_exprs[listidx], NULL))
    1808          66 :                 continue;
    1809             : 
    1810             :             /*
    1811             :              * Now we know the clause is compatible (we have either attnums or
    1812             :              * expressions extracted from it), and was not estimated yet.
    1813             :              */
    1814             : 
    1815             :             /* record simple clauses (single column or expression) */
    1816        1650 :             if ((list_attnums[listidx] == NULL &&
    1817         246 :                  list_length(list_exprs[listidx]) == 1) ||
    1818        2316 :                 (list_exprs[listidx] == NIL &&
    1819        1158 :                  bms_membership(list_attnums[listidx]) == BMS_SINGLETON))
    1820        1344 :                 simple_clauses = bms_add_member(simple_clauses,
    1821             :                                                 list_length(stat_clauses));
    1822             : 
    1823             :             /* add clause to list and mark it as estimated */
    1824        1404 :             stat_clauses = lappend(stat_clauses, (Node *) lfirst(l));
    1825        1404 :             *estimatedclauses = bms_add_member(*estimatedclauses, listidx);
    1826             : 
    1827             :             /*
    1828             :              * Reset the pointers, so that choose_best_statistics knows this
    1829             :              * clause was estimated and does not consider it again.
    1830             :              */
    1831        1404 :             bms_free(list_attnums[listidx]);
    1832        1404 :             list_attnums[listidx] = NULL;
    1833             : 
    1834        1404 :             list_free(list_exprs[listidx]);
    1835        1404 :             list_exprs[listidx] = NULL;
    1836             :         }
    1837             : 
    1838         606 :         if (is_or)
    1839             :         {
    1840          96 :             bool       *or_matches = NULL;
    1841          96 :             Selectivity simple_or_sel = 0.0,
    1842          96 :                         stat_sel = 0.0;
    1843             :             MCVList    *mcv_list;
    1844             : 
    1845             :             /* Load the MCV list stored in the statistics object */
    1846          96 :             mcv_list = statext_mcv_load(stat->statOid, rte->inh);
    1847             : 
    1848             :             /*
    1849             :              * Compute the selectivity of the ORed list of clauses covered by
    1850             :              * this statistics object by estimating each in turn and combining
    1851             :              * them using the formula P(A OR B) = P(A) + P(B) - P(A AND B).
    1852             :              * This allows us to use the multivariate MCV stats to better
    1853             :              * estimate the individual terms and their overlap.
    1854             :              *
    1855             :              * Each time we iterate this formula, the clause "A" above is
    1856             :              * equal to all the clauses processed so far, combined with "OR".
    1857             :              */
    1858          96 :             listidx = 0;
    1859         336 :             foreach(l, stat_clauses)
    1860             :             {
    1861         240 :                 Node       *clause = (Node *) lfirst(l);
    1862             :                 Selectivity simple_sel,
    1863             :                             overlap_simple_sel,
    1864             :                             mcv_sel,
    1865             :                             mcv_basesel,
    1866             :                             overlap_mcvsel,
    1867             :                             overlap_basesel,
    1868             :                             mcv_totalsel,
    1869             :                             clause_sel,
    1870             :                             overlap_sel;
    1871             : 
    1872             :                 /*
    1873             :                  * "Simple" selectivity of the next clause and its overlap
    1874             :                  * with any of the previous clauses.  These are our initial
    1875             :                  * estimates of P(B) and P(A AND B), assuming independence of
    1876             :                  * columns/clauses.
    1877             :                  */
    1878         240 :                 simple_sel = clause_selectivity_ext(root, clause, varRelid,
    1879             :                                                     jointype, sjinfo, false);
    1880             : 
    1881         240 :                 overlap_simple_sel = simple_or_sel * simple_sel;
    1882             : 
    1883             :                 /*
    1884             :                  * New "simple" selectivity of all clauses seen so far,
    1885             :                  * assuming independence.
    1886             :                  */
    1887         240 :                 simple_or_sel += simple_sel - overlap_simple_sel;
    1888         240 :                 CLAMP_PROBABILITY(simple_or_sel);
    1889             : 
    1890             :                 /*
    1891             :                  * Multi-column estimate of this clause using MCV statistics,
    1892             :                  * along with base and total selectivities, and corresponding
    1893             :                  * selectivities for the overlap term P(A AND B).
    1894             :                  */
    1895         240 :                 mcv_sel = mcv_clause_selectivity_or(root, stat, mcv_list,
    1896             :                                                     clause, &or_matches,
    1897             :                                                     &mcv_basesel,
    1898             :                                                     &overlap_mcvsel,
    1899             :                                                     &overlap_basesel,
    1900             :                                                     &mcv_totalsel);
    1901             : 
    1902             :                 /*
    1903             :                  * Combine the simple and multi-column estimates.
    1904             :                  *
    1905             :                  * If this clause is a simple single-column clause, then we
    1906             :                  * just use the simple selectivity estimate for it, since the
    1907             :                  * multi-column statistics are unlikely to improve on that
    1908             :                  * (and in fact could make it worse).  For the overlap, we
    1909             :                  * always make use of the multi-column statistics.
    1910             :                  */
    1911         240 :                 if (bms_is_member(listidx, simple_clauses))
    1912         192 :                     clause_sel = simple_sel;
    1913             :                 else
    1914          48 :                     clause_sel = mcv_combine_selectivities(simple_sel,
    1915             :                                                            mcv_sel,
    1916             :                                                            mcv_basesel,
    1917             :                                                            mcv_totalsel);
    1918             : 
    1919         240 :                 overlap_sel = mcv_combine_selectivities(overlap_simple_sel,
    1920             :                                                         overlap_mcvsel,
    1921             :                                                         overlap_basesel,
    1922             :                                                         mcv_totalsel);
    1923             : 
    1924             :                 /* Factor these into the result for this statistics object */
    1925         240 :                 stat_sel += clause_sel - overlap_sel;
    1926         240 :                 CLAMP_PROBABILITY(stat_sel);
    1927             : 
    1928         240 :                 listidx++;
    1929             :             }
    1930             : 
    1931             :             /*
    1932             :              * Factor the result for this statistics object into the overall
    1933             :              * result.  We treat the results from each separate statistics
    1934             :              * object as independent of one another.
    1935             :              */
    1936          96 :             sel = sel + stat_sel - sel * stat_sel;
    1937             :         }
    1938             :         else                    /* Implicitly-ANDed list of clauses */
    1939             :         {
    1940             :             Selectivity simple_sel,
    1941             :                         mcv_sel,
    1942             :                         mcv_basesel,
    1943             :                         mcv_totalsel,
    1944             :                         stat_sel;
    1945             : 
    1946             :             /*
    1947             :              * "Simple" selectivity, i.e. without any extended statistics,
    1948             :              * essentially assuming independence of the columns/clauses.
    1949             :              */
    1950         510 :             simple_sel = clauselist_selectivity_ext(root, stat_clauses,
    1951             :                                                     varRelid, jointype,
    1952             :                                                     sjinfo, false);
    1953             : 
    1954             :             /*
    1955             :              * Multi-column estimate using MCV statistics, along with base and
    1956             :              * total selectivities.
    1957             :              */
    1958         510 :             mcv_sel = mcv_clauselist_selectivity(root, stat, stat_clauses,
    1959             :                                                  varRelid, jointype, sjinfo,
    1960             :                                                  rel, &mcv_basesel,
    1961             :                                                  &mcv_totalsel);
    1962             : 
    1963             :             /* Combine the simple and multi-column estimates. */
    1964         510 :             stat_sel = mcv_combine_selectivities(simple_sel,
    1965             :                                                  mcv_sel,
    1966             :                                                  mcv_basesel,
    1967             :                                                  mcv_totalsel);
    1968             : 
    1969             :             /* Factor this into the overall result */
    1970         510 :             sel *= stat_sel;
    1971             :         }
    1972             :     }
    1973             : 
    1974         744 :     return sel;
    1975             : }
    1976             : 
    1977             : /*
    1978             :  * statext_clauselist_selectivity
    1979             :  *      Estimate clauses using the best multi-column statistics.
    1980             :  */
    1981             : Selectivity
    1982        2592 : statext_clauselist_selectivity(PlannerInfo *root, List *clauses, int varRelid,
    1983             :                                JoinType jointype, SpecialJoinInfo *sjinfo,
    1984             :                                RelOptInfo *rel, Bitmapset **estimatedclauses,
    1985             :                                bool is_or)
    1986             : {
    1987             :     Selectivity sel;
    1988             : 
    1989             :     /* First, try estimating clauses using a multivariate MCV list. */
    1990        2592 :     sel = statext_mcv_clauselist_selectivity(root, clauses, varRelid, jointype,
    1991             :                                              sjinfo, rel, estimatedclauses, is_or);
    1992             : 
    1993             :     /*
    1994             :      * Functional dependencies only work for clauses connected by AND, so for
    1995             :      * OR clauses we're done.
    1996             :      */
    1997        2592 :     if (is_or)
    1998         156 :         return sel;
    1999             : 
    2000             :     /*
    2001             :      * Then, apply functional dependencies on the remaining clauses by calling
    2002             :      * dependencies_clauselist_selectivity.  Pass 'estimatedclauses' so the
    2003             :      * function can properly skip clauses already estimated above.
    2004             :      *
    2005             :      * The reasoning for applying dependencies last is that the more complex
    2006             :      * stats can track more complex correlations between the attributes, and
    2007             :      * so may be considered more reliable.
    2008             :      *
    2009             :      * For example, MCV list can give us an exact selectivity for values in
    2010             :      * two columns, while functional dependencies can only provide information
    2011             :      * about the overall strength of the dependency.
    2012             :      */
    2013        2436 :     sel *= dependencies_clauselist_selectivity(root, clauses, varRelid,
    2014             :                                                jointype, sjinfo, rel,
    2015             :                                                estimatedclauses);
    2016             : 
    2017        2436 :     return sel;
    2018             : }
    2019             : 
    2020             : /*
    2021             :  * examine_opclause_args
    2022             :  *      Split an operator expression's arguments into Expr and Const parts.
    2023             :  *
    2024             :  * Attempts to match the arguments to either (Expr op Const) or (Const op
    2025             :  * Expr), possibly with a RelabelType on top. When the expression matches this
    2026             :  * form, returns true, otherwise returns false.
    2027             :  *
    2028             :  * Optionally returns pointers to the extracted Expr/Const nodes, when passed
    2029             :  * non-null pointers (exprp, cstp and expronleftp). The expronleftp flag
    2030             :  * specifies on which side of the operator we found the expression node.
    2031             :  */
    2032             : bool
    2033        3018 : examine_opclause_args(List *args, Node **exprp, Const **cstp,
    2034             :                       bool *expronleftp)
    2035             : {
    2036             :     Node       *expr;
    2037             :     Const      *cst;
    2038             :     bool        expronleft;
    2039             :     Node       *leftop,
    2040             :                *rightop;
    2041             : 
    2042             :     /* enforced by statext_is_compatible_clause_internal */
    2043             :     Assert(list_length(args) == 2);
    2044             : 
    2045        3018 :     leftop = linitial(args);
    2046        3018 :     rightop = lsecond(args);
    2047             : 
    2048             :     /* strip RelabelType from either side of the expression */
    2049        3018 :     if (IsA(leftop, RelabelType))
    2050         324 :         leftop = (Node *) ((RelabelType *) leftop)->arg;
    2051             : 
    2052        3018 :     if (IsA(rightop, RelabelType))
    2053          60 :         rightop = (Node *) ((RelabelType *) rightop)->arg;
    2054             : 
    2055        3018 :     if (IsA(rightop, Const))
    2056             :     {
    2057        2856 :         expr = (Node *) leftop;
    2058        2856 :         cst = (Const *) rightop;
    2059        2856 :         expronleft = true;
    2060             :     }
    2061         162 :     else if (IsA(leftop, Const))
    2062             :     {
    2063         162 :         expr = (Node *) rightop;
    2064         162 :         cst = (Const *) leftop;
    2065         162 :         expronleft = false;
    2066             :     }
    2067             :     else
    2068           0 :         return false;
    2069             : 
    2070             :     /* return pointers to the extracted parts if requested */
    2071        3018 :     if (exprp)
    2072        3018 :         *exprp = expr;
    2073             : 
    2074        3018 :     if (cstp)
    2075        1338 :         *cstp = cst;
    2076             : 
    2077        3018 :     if (expronleftp)
    2078        1626 :         *expronleftp = expronleft;
    2079             : 
    2080        3018 :     return true;
    2081             : }
    2082             : 
    2083             : 
    2084             : /*
    2085             :  * Compute statistics about expressions of a relation.
    2086             :  */
    2087             : static void
    2088         156 : compute_expr_stats(Relation onerel, AnlExprData *exprdata, int nexprs,
    2089             :                    HeapTuple *rows, int numrows)
    2090             : {
    2091             :     MemoryContext expr_context,
    2092             :                 old_context;
    2093             :     int         ind,
    2094             :                 i;
    2095             : 
    2096         156 :     expr_context = AllocSetContextCreate(CurrentMemoryContext,
    2097             :                                          "Analyze Expression",
    2098             :                                          ALLOCSET_DEFAULT_SIZES);
    2099         156 :     old_context = MemoryContextSwitchTo(expr_context);
    2100             : 
    2101         456 :     for (ind = 0; ind < nexprs; ind++)
    2102             :     {
    2103         300 :         AnlExprData *thisdata = &exprdata[ind];
    2104         300 :         VacAttrStats *stats = thisdata->vacattrstat;
    2105         300 :         Node       *expr = thisdata->expr;
    2106             :         TupleTableSlot *slot;
    2107             :         EState     *estate;
    2108             :         ExprContext *econtext;
    2109             :         Datum      *exprvals;
    2110             :         bool       *exprnulls;
    2111             :         ExprState  *exprstate;
    2112             :         int         tcnt;
    2113             : 
    2114             :         /* Are we still in the main context? */
    2115             :         Assert(CurrentMemoryContext == expr_context);
    2116             : 
    2117             :         /*
    2118             :          * Need an EState for evaluation of expressions.  Create it in the
    2119             :          * per-expression context to be sure it gets cleaned up at the bottom
    2120             :          * of the loop.
    2121             :          */
    2122         300 :         estate = CreateExecutorState();
    2123         300 :         econtext = GetPerTupleExprContext(estate);
    2124             : 
    2125             :         /* Set up expression evaluation state */
    2126         300 :         exprstate = ExecPrepareExpr((Expr *) expr, estate);
    2127             : 
    2128             :         /* Need a slot to hold the current heap tuple, too */
    2129         300 :         slot = MakeSingleTupleTableSlot(RelationGetDescr(onerel),
    2130             :                                         &TTSOpsHeapTuple);
    2131             : 
    2132             :         /* Arrange for econtext's scan tuple to be the tuple under test */
    2133         300 :         econtext->ecxt_scantuple = slot;
    2134             : 
    2135             :         /* Compute and save expression values */
    2136         300 :         exprvals = (Datum *) palloc(numrows * sizeof(Datum));
    2137         300 :         exprnulls = (bool *) palloc(numrows * sizeof(bool));
    2138             : 
    2139         300 :         tcnt = 0;
    2140      399930 :         for (i = 0; i < numrows; i++)
    2141             :         {
    2142             :             Datum       datum;
    2143             :             bool        isnull;
    2144             : 
    2145             :             /*
    2146             :              * Reset the per-tuple context each time, to reclaim any cruft
    2147             :              * left behind by evaluating the statistics expressions.
    2148             :              */
    2149      399630 :             ResetExprContext(econtext);
    2150             : 
    2151             :             /* Set up for expression evaluation */
    2152      399630 :             ExecStoreHeapTuple(rows[i], slot, false);
    2153             : 
    2154             :             /*
    2155             :              * Evaluate the expression. We do this in the per-tuple context so
    2156             :              * as not to leak memory, and then copy the result into the
    2157             :              * context created at the beginning of this function.
    2158             :              */
    2159      399630 :             datum = ExecEvalExprSwitchContext(exprstate,
    2160      399630 :                                               GetPerTupleExprContext(estate),
    2161             :                                               &isnull);
    2162      399630 :             if (isnull)
    2163             :             {
    2164           0 :                 exprvals[tcnt] = (Datum) 0;
    2165           0 :                 exprnulls[tcnt] = true;
    2166             :             }
    2167             :             else
    2168             :             {
    2169             :                 /* Make sure we copy the data into the context. */
    2170             :                 Assert(CurrentMemoryContext == expr_context);
    2171             : 
    2172      799260 :                 exprvals[tcnt] = datumCopy(datum,
    2173      399630 :                                            stats->attrtype->typbyval,
    2174      399630 :                                            stats->attrtype->typlen);
    2175      399630 :                 exprnulls[tcnt] = false;
    2176             :             }
    2177             : 
    2178      399630 :             tcnt++;
    2179             :         }
    2180             : 
    2181             :         /*
    2182             :          * Now we can compute the statistics for the expression columns.
    2183             :          *
    2184             :          * XXX Unlike compute_index_stats we don't need to switch and reset
    2185             :          * memory contexts here, because we're only computing stats for a
    2186             :          * single expression (and not iterating over many indexes), so we just
    2187             :          * do it in expr_context. Note that compute_stats copies the result
    2188             :          * into stats->anl_context, so it does not disappear.
    2189             :          */
    2190         300 :         if (tcnt > 0)
    2191             :         {
    2192             :             AttributeOpts *aopt =
    2193         300 :                 get_attribute_options(onerel->rd_id, stats->tupattnum);
    2194             : 
    2195         300 :             stats->exprvals = exprvals;
    2196         300 :             stats->exprnulls = exprnulls;
    2197         300 :             stats->rowstride = 1;
    2198         300 :             stats->compute_stats(stats,
    2199             :                                  expr_fetch_func,
    2200             :                                  tcnt,
    2201             :                                  tcnt);
    2202             : 
    2203             :             /*
    2204             :              * If the n_distinct option is specified, it overrides the above
    2205             :              * computation.
    2206             :              */
    2207         300 :             if (aopt != NULL && aopt->n_distinct != 0.0)
    2208           0 :                 stats->stadistinct = aopt->n_distinct;
    2209             :         }
    2210             : 
    2211             :         /* And clean up */
    2212         300 :         MemoryContextSwitchTo(expr_context);
    2213             : 
    2214         300 :         ExecDropSingleTupleTableSlot(slot);
    2215         300 :         FreeExecutorState(estate);
    2216         300 :         MemoryContextReset(expr_context);
    2217             :     }
    2218             : 
    2219         156 :     MemoryContextSwitchTo(old_context);
    2220         156 :     MemoryContextDelete(expr_context);
    2221         156 : }
    2222             : 
    2223             : 
    2224             : /*
    2225             :  * Fetch function for analyzing statistics object expressions.
    2226             :  *
    2227             :  * We have not bothered to construct tuples from the data, instead the data
    2228             :  * is just in Datum arrays.
    2229             :  */
    2230             : static Datum
    2231      399630 : expr_fetch_func(VacAttrStatsP stats, int rownum, bool *isNull)
    2232             : {
    2233             :     int         i;
    2234             : 
    2235             :     /* exprvals and exprnulls are already offset for proper column */
    2236      399630 :     i = rownum * stats->rowstride;
    2237      399630 :     *isNull = stats->exprnulls[i];
    2238      399630 :     return stats->exprvals[i];
    2239             : }
    2240             : 
    2241             : /*
    2242             :  * Build analyze data for a list of expressions. As this is not tied
    2243             :  * directly to a relation (table or index), we have to fake some of
    2244             :  * the fields in examine_expression().
    2245             :  */
    2246             : static AnlExprData *
    2247         156 : build_expr_data(List *exprs, int stattarget)
    2248             : {
    2249             :     int         idx;
    2250         156 :     int         nexprs = list_length(exprs);
    2251             :     AnlExprData *exprdata;
    2252             :     ListCell   *lc;
    2253             : 
    2254         156 :     exprdata = (AnlExprData *) palloc0(nexprs * sizeof(AnlExprData));
    2255             : 
    2256         156 :     idx = 0;
    2257         456 :     foreach(lc, exprs)
    2258             :     {
    2259         300 :         Node       *expr = (Node *) lfirst(lc);
    2260         300 :         AnlExprData *thisdata = &exprdata[idx];
    2261             : 
    2262         300 :         thisdata->expr = expr;
    2263         300 :         thisdata->vacattrstat = examine_expression(expr, stattarget);
    2264         300 :         idx++;
    2265             :     }
    2266             : 
    2267         156 :     return exprdata;
    2268             : }
    2269             : 
    2270             : /* form an array of pg_statistic rows (per update_attstats) */
    2271             : static Datum
    2272         156 : serialize_expr_stats(AnlExprData *exprdata, int nexprs)
    2273             : {
    2274             :     int         exprno;
    2275             :     Oid         typOid;
    2276             :     Relation    sd;
    2277             : 
    2278         156 :     ArrayBuildState *astate = NULL;
    2279             : 
    2280         156 :     sd = table_open(StatisticRelationId, RowExclusiveLock);
    2281             : 
    2282             :     /* lookup OID of composite type for pg_statistic */
    2283         156 :     typOid = get_rel_type_id(StatisticRelationId);
    2284         156 :     if (!OidIsValid(typOid))
    2285           0 :         ereport(ERROR,
    2286             :                 (errcode(ERRCODE_WRONG_OBJECT_TYPE),
    2287             :                  errmsg("relation \"%s\" does not have a composite type",
    2288             :                         "pg_statistic")));
    2289             : 
    2290         456 :     for (exprno = 0; exprno < nexprs; exprno++)
    2291             :     {
    2292             :         int         i,
    2293             :                     k;
    2294         300 :         VacAttrStats *stats = exprdata[exprno].vacattrstat;
    2295             : 
    2296             :         Datum       values[Natts_pg_statistic];
    2297             :         bool        nulls[Natts_pg_statistic];
    2298             :         HeapTuple   stup;
    2299             : 
    2300         300 :         if (!stats->stats_valid)
    2301             :         {
    2302           0 :             astate = accumArrayResult(astate,
    2303             :                                       (Datum) 0,
    2304             :                                       true,
    2305             :                                       typOid,
    2306             :                                       CurrentMemoryContext);
    2307           0 :             continue;
    2308             :         }
    2309             : 
    2310             :         /*
    2311             :          * Construct a new pg_statistic tuple
    2312             :          */
    2313        9600 :         for (i = 0; i < Natts_pg_statistic; ++i)
    2314             :         {
    2315        9300 :             nulls[i] = false;
    2316             :         }
    2317             : 
    2318         300 :         values[Anum_pg_statistic_starelid - 1] = ObjectIdGetDatum(InvalidOid);
    2319         300 :         values[Anum_pg_statistic_staattnum - 1] = Int16GetDatum(InvalidAttrNumber);
    2320         300 :         values[Anum_pg_statistic_stainherit - 1] = BoolGetDatum(false);
    2321         300 :         values[Anum_pg_statistic_stanullfrac - 1] = Float4GetDatum(stats->stanullfrac);
    2322         300 :         values[Anum_pg_statistic_stawidth - 1] = Int32GetDatum(stats->stawidth);
    2323         300 :         values[Anum_pg_statistic_stadistinct - 1] = Float4GetDatum(stats->stadistinct);
    2324         300 :         i = Anum_pg_statistic_stakind1 - 1;
    2325        1800 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2326             :         {
    2327        1500 :             values[i++] = Int16GetDatum(stats->stakind[k]); /* stakindN */
    2328             :         }
    2329         300 :         i = Anum_pg_statistic_staop1 - 1;
    2330        1800 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2331             :         {
    2332        1500 :             values[i++] = ObjectIdGetDatum(stats->staop[k]); /* staopN */
    2333             :         }
    2334         300 :         i = Anum_pg_statistic_stacoll1 - 1;
    2335        1800 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2336             :         {
    2337        1500 :             values[i++] = ObjectIdGetDatum(stats->stacoll[k]);   /* stacollN */
    2338             :         }
    2339         300 :         i = Anum_pg_statistic_stanumbers1 - 1;
    2340        1800 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2341             :         {
    2342        1500 :             int         nnum = stats->numnumbers[k];
    2343             : 
    2344        1500 :             if (nnum > 0)
    2345             :             {
    2346             :                 int         n;
    2347         588 :                 Datum      *numdatums = (Datum *) palloc(nnum * sizeof(Datum));
    2348             :                 ArrayType  *arry;
    2349             : 
    2350        4986 :                 for (n = 0; n < nnum; n++)
    2351        4398 :                     numdatums[n] = Float4GetDatum(stats->stanumbers[k][n]);
    2352         588 :                 arry = construct_array_builtin(numdatums, nnum, FLOAT4OID);
    2353         588 :                 values[i++] = PointerGetDatum(arry);    /* stanumbersN */
    2354             :             }
    2355             :             else
    2356             :             {
    2357         912 :                 nulls[i] = true;
    2358         912 :                 values[i++] = (Datum) 0;
    2359             :             }
    2360             :         }
    2361         300 :         i = Anum_pg_statistic_stavalues1 - 1;
    2362        1800 :         for (k = 0; k < STATISTIC_NUM_SLOTS; k++)
    2363             :         {
    2364        1500 :             if (stats->numvalues[k] > 0)
    2365             :             {
    2366             :                 ArrayType  *arry;
    2367             : 
    2368         318 :                 arry = construct_array(stats->stavalues[k],
    2369             :                                        stats->numvalues[k],
    2370             :                                        stats->statypid[k],
    2371         318 :                                        stats->statyplen[k],
    2372         318 :                                        stats->statypbyval[k],
    2373         318 :                                        stats->statypalign[k]);
    2374         318 :                 values[i++] = PointerGetDatum(arry);    /* stavaluesN */
    2375             :             }
    2376             :             else
    2377             :             {
    2378        1182 :                 nulls[i] = true;
    2379        1182 :                 values[i++] = (Datum) 0;
    2380             :             }
    2381             :         }
    2382             : 
    2383         300 :         stup = heap_form_tuple(RelationGetDescr(sd), values, nulls);
    2384             : 
    2385         300 :         astate = accumArrayResult(astate,
    2386             :                                   heap_copy_tuple_as_datum(stup, RelationGetDescr(sd)),
    2387             :                                   false,
    2388             :                                   typOid,
    2389             :                                   CurrentMemoryContext);
    2390             :     }
    2391             : 
    2392         156 :     table_close(sd, RowExclusiveLock);
    2393             : 
    2394         156 :     return makeArrayResult(astate, CurrentMemoryContext);
    2395             : }
    2396             : 
    2397             : /*
    2398             :  * Loads pg_statistic record from expression statistics for expression
    2399             :  * identified by the supplied index.
    2400             :  */
    2401             : HeapTuple
    2402        1644 : statext_expressions_load(Oid stxoid, bool inh, int idx)
    2403             : {
    2404             :     bool        isnull;
    2405             :     Datum       value;
    2406             :     HeapTuple   htup;
    2407             :     ExpandedArrayHeader *eah;
    2408             :     HeapTupleHeader td;
    2409             :     HeapTupleData tmptup;
    2410             :     HeapTuple   tup;
    2411             : 
    2412        1644 :     htup = SearchSysCache2(STATEXTDATASTXOID,
    2413             :                            ObjectIdGetDatum(stxoid), BoolGetDatum(inh));
    2414        1644 :     if (!HeapTupleIsValid(htup))
    2415           0 :         elog(ERROR, "cache lookup failed for statistics object %u", stxoid);
    2416             : 
    2417        1644 :     value = SysCacheGetAttr(STATEXTDATASTXOID, htup,
    2418             :                             Anum_pg_statistic_ext_data_stxdexpr, &isnull);
    2419        1644 :     if (isnull)
    2420           0 :         elog(ERROR,
    2421             :              "requested statistics kind \"%c\" is not yet built for statistics object %u",
    2422             :              STATS_EXT_EXPRESSIONS, stxoid);
    2423             : 
    2424        1644 :     eah = DatumGetExpandedArray(value);
    2425             : 
    2426        1644 :     deconstruct_expanded_array(eah);
    2427             : 
    2428        1644 :     td = DatumGetHeapTupleHeader(eah->dvalues[idx]);
    2429             : 
    2430             :     /* Build a temporary HeapTuple control structure */
    2431        1644 :     tmptup.t_len = HeapTupleHeaderGetDatumLength(td);
    2432        1644 :     ItemPointerSetInvalid(&(tmptup.t_self));
    2433        1644 :     tmptup.t_tableOid = InvalidOid;
    2434        1644 :     tmptup.t_data = td;
    2435             : 
    2436        1644 :     tup = heap_copytuple(&tmptup);
    2437             : 
    2438        1644 :     ReleaseSysCache(htup);
    2439             : 
    2440        1644 :     return tup;
    2441             : }
    2442             : 
    2443             : /*
    2444             :  * Evaluate the expressions, so that we can use the results to build
    2445             :  * all the requested statistics types. This matters especially for
    2446             :  * expensive expressions, of course.
    2447             :  */
    2448             : static StatsBuildData *
    2449         398 : make_build_data(Relation rel, StatExtEntry *stat, int numrows, HeapTuple *rows,
    2450             :                 VacAttrStats **stats, int stattarget)
    2451             : {
    2452             :     /* evaluated expressions */
    2453             :     StatsBuildData *result;
    2454             :     char       *ptr;
    2455             :     Size        len;
    2456             : 
    2457             :     int         i;
    2458             :     int         k;
    2459             :     int         idx;
    2460             :     TupleTableSlot *slot;
    2461             :     EState     *estate;
    2462             :     ExprContext *econtext;
    2463         398 :     List       *exprstates = NIL;
    2464         398 :     int         nkeys = bms_num_members(stat->columns) + list_length(stat->exprs);
    2465             :     ListCell   *lc;
    2466             : 
    2467             :     /* allocate everything as a single chunk, so we can free it easily */
    2468         398 :     len = MAXALIGN(sizeof(StatsBuildData));
    2469         398 :     len += MAXALIGN(sizeof(AttrNumber) * nkeys);    /* attnums */
    2470         398 :     len += MAXALIGN(sizeof(VacAttrStats *) * nkeys);    /* stats */
    2471             : 
    2472             :     /* values */
    2473         398 :     len += MAXALIGN(sizeof(Datum *) * nkeys);
    2474         398 :     len += nkeys * MAXALIGN(sizeof(Datum) * numrows);
    2475             : 
    2476             :     /* nulls */
    2477         398 :     len += MAXALIGN(sizeof(bool *) * nkeys);
    2478         398 :     len += nkeys * MAXALIGN(sizeof(bool) * numrows);
    2479             : 
    2480         398 :     ptr = palloc(len);
    2481             : 
    2482             :     /* set the pointers */
    2483         398 :     result = (StatsBuildData *) ptr;
    2484         398 :     ptr += MAXALIGN(sizeof(StatsBuildData));
    2485             : 
    2486             :     /* attnums */
    2487         398 :     result->attnums = (AttrNumber *) ptr;
    2488         398 :     ptr += MAXALIGN(sizeof(AttrNumber) * nkeys);
    2489             : 
    2490             :     /* stats */
    2491         398 :     result->stats = (VacAttrStats **) ptr;
    2492         398 :     ptr += MAXALIGN(sizeof(VacAttrStats *) * nkeys);
    2493             : 
    2494             :     /* values */
    2495         398 :     result->values = (Datum **) ptr;
    2496         398 :     ptr += MAXALIGN(sizeof(Datum *) * nkeys);
    2497             : 
    2498             :     /* nulls */
    2499         398 :     result->nulls = (bool **) ptr;
    2500         398 :     ptr += MAXALIGN(sizeof(bool *) * nkeys);
    2501             : 
    2502        1404 :     for (i = 0; i < nkeys; i++)
    2503             :     {
    2504        1006 :         result->values[i] = (Datum *) ptr;
    2505        1006 :         ptr += MAXALIGN(sizeof(Datum) * numrows);
    2506             : 
    2507        1006 :         result->nulls[i] = (bool *) ptr;
    2508        1006 :         ptr += MAXALIGN(sizeof(bool) * numrows);
    2509             :     }
    2510             : 
    2511             :     Assert((ptr - (char *) result) == len);
    2512             : 
    2513             :     /* we have it allocated, so let's fill the values */
    2514         398 :     result->nattnums = nkeys;
    2515         398 :     result->numrows = numrows;
    2516             : 
    2517             :     /* fill the attribute info - first attributes, then expressions */
    2518         398 :     idx = 0;
    2519         398 :     k = -1;
    2520        1104 :     while ((k = bms_next_member(stat->columns, k)) >= 0)
    2521             :     {
    2522         706 :         result->attnums[idx] = k;
    2523         706 :         result->stats[idx] = stats[idx];
    2524             : 
    2525         706 :         idx++;
    2526             :     }
    2527             : 
    2528         398 :     k = -1;
    2529         698 :     foreach(lc, stat->exprs)
    2530             :     {
    2531         300 :         Node       *expr = (Node *) lfirst(lc);
    2532             : 
    2533         300 :         result->attnums[idx] = k;
    2534         300 :         result->stats[idx] = examine_expression(expr, stattarget);
    2535             : 
    2536         300 :         idx++;
    2537         300 :         k--;
    2538             :     }
    2539             : 
    2540             :     /* first extract values for all the regular attributes */
    2541      823204 :     for (i = 0; i < numrows; i++)
    2542             :     {
    2543      822806 :         idx = 0;
    2544      822806 :         k = -1;
    2545     2744982 :         while ((k = bms_next_member(stat->columns, k)) >= 0)
    2546             :         {
    2547     3844352 :             result->values[idx][i] = heap_getattr(rows[i], k,
    2548     1922176 :                                                   result->stats[idx]->tupDesc,
    2549     1922176 :                                                   &result->nulls[idx][i]);
    2550             : 
    2551     1922176 :             idx++;
    2552             :         }
    2553             :     }
    2554             : 
    2555             :     /* Need an EState for evaluation expressions. */
    2556         398 :     estate = CreateExecutorState();
    2557         398 :     econtext = GetPerTupleExprContext(estate);
    2558             : 
    2559             :     /* Need a slot to hold the current heap tuple, too */
    2560         398 :     slot = MakeSingleTupleTableSlot(RelationGetDescr(rel),
    2561             :                                     &TTSOpsHeapTuple);
    2562             : 
    2563             :     /* Arrange for econtext's scan tuple to be the tuple under test */
    2564         398 :     econtext->ecxt_scantuple = slot;
    2565             : 
    2566             :     /* Set up expression evaluation state */
    2567         398 :     exprstates = ExecPrepareExprList(stat->exprs, estate);
    2568             : 
    2569      823204 :     for (i = 0; i < numrows; i++)
    2570             :     {
    2571             :         /*
    2572             :          * Reset the per-tuple context each time, to reclaim any cruft left
    2573             :          * behind by evaluating the statistics object expressions.
    2574             :          */
    2575      822806 :         ResetExprContext(econtext);
    2576             : 
    2577             :         /* Set up for expression evaluation */
    2578      822806 :         ExecStoreHeapTuple(rows[i], slot, false);
    2579             : 
    2580      822806 :         idx = bms_num_members(stat->columns);
    2581     1222436 :         foreach(lc, exprstates)
    2582             :         {
    2583             :             Datum       datum;
    2584             :             bool        isnull;
    2585      399630 :             ExprState  *exprstate = (ExprState *) lfirst(lc);
    2586             : 
    2587             :             /*
    2588             :              * XXX This probably leaks memory. Maybe we should use
    2589             :              * ExecEvalExprSwitchContext but then we need to copy the result
    2590             :              * somewhere else.
    2591             :              */
    2592      399630 :             datum = ExecEvalExpr(exprstate,
    2593      399630 :                                  GetPerTupleExprContext(estate),
    2594             :                                  &isnull);
    2595      399630 :             if (isnull)
    2596             :             {
    2597           0 :                 result->values[idx][i] = (Datum) 0;
    2598           0 :                 result->nulls[idx][i] = true;
    2599             :             }
    2600             :             else
    2601             :             {
    2602      399630 :                 result->values[idx][i] = datum;
    2603      399630 :                 result->nulls[idx][i] = false;
    2604             :             }
    2605             : 
    2606      399630 :             idx++;
    2607             :         }
    2608             :     }
    2609             : 
    2610         398 :     ExecDropSingleTupleTableSlot(slot);
    2611         398 :     FreeExecutorState(estate);
    2612             : 
    2613         398 :     return result;
    2614             : }

Generated by: LCOV version 1.16