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