granicus.if.org Git - postgresql/blob - src/backend/utils/adt/array_selfuncs.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * array_selfuncs.c
   4  *        Functions for selectivity estimation of array operators
   5  *
   6  * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/utils/adt/array_selfuncs.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include <math.h>
  18
  19 #include "access/htup_details.h"
  20 #include "catalog/pg_collation.h"
  21 #include "catalog/pg_operator.h"
  22 #include "catalog/pg_statistic.h"
  23 #include "optimizer/clauses.h"
  24 #include "utils/array.h"
  25 #include "utils/lsyscache.h"
  26 #include "utils/selfuncs.h"
  27 #include "utils/typcache.h"
  28
  29
  30 /* Default selectivity constant for "@>" and "<@" operators */
  31 #define DEFAULT_CONTAIN_SEL 0.005
  32
  33 /* Default selectivity constant for "&&" operator */
  34 #define DEFAULT_OVERLAP_SEL 0.01
  35
  36 /* Default selectivity for given operator */
  37 #define DEFAULT_SEL(operator) \
  38         ((operator) == OID_ARRAY_OVERLAP_OP ? \
  39                 DEFAULT_OVERLAP_SEL : DEFAULT_CONTAIN_SEL)
  40
  41 static Selectivity calc_arraycontsel(VariableStatData *vardata, Datum constval,
  42                                   Oid elemtype, Oid operator);
  43 static Selectivity mcelem_array_selec(ArrayType *array,
  44                                    TypeCacheEntry *typentry,
  45                                    Datum *mcelem, int nmcelem,
  46                                    float4 *numbers, int nnumbers,
  47                                    float4 *hist, int nhist,
  48                                    Oid operator, FmgrInfo *cmpfunc);
  49 static Selectivity mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem,
  50                                                                    float4 *numbers, int nnumbers,
  51                                                                    Datum *array_data, int nitems,
  52                                                                    Oid operator, FmgrInfo *cmpfunc);
  53 static Selectivity mcelem_array_contained_selec(Datum *mcelem, int nmcelem,
  54                                                          float4 *numbers, int nnumbers,
  55                                                          Datum *array_data, int nitems,
  56                                                          float4 *hist, int nhist,
  57                                                          Oid operator, FmgrInfo *cmpfunc);
  58 static float *calc_hist(const float4 *hist, int nhist, int n);
  59 static float *calc_distr(const float *p, int n, int m, float rest);
  60 static int      floor_log2(uint32 n);
  61 static bool find_next_mcelem(Datum *mcelem, int nmcelem, Datum value,
  62                                  int *index, FmgrInfo *cmpfunc);
  63 static int      element_compare(const void *key1, const void *key2, void *arg);
  64 static int      float_compare_desc(const void *key1, const void *key2);
  65
  66
  67 /*
  68  * scalararraysel_containment
  69  *              Estimate selectivity of ScalarArrayOpExpr via array containment.
  70  *
  71  * scalararraysel() has already verified that the operator of a
  72  * ScalarArrayOpExpr is the array element type's default equality or
  73  * inequality operator.  If we have const =/<> ANY/ALL (array_var)
  74  * then we can estimate the selectivity as though this were an array
  75  * containment operator, array_var op ARRAY[const].
  76  *
  77  * Returns selectivity (0..1), or -1 if we fail to estimate selectivity.
  78  */
  79 Selectivity
  80 scalararraysel_containment(PlannerInfo *root,
  81                                                    Node *leftop, Node *rightop,
  82                                                    Oid elemtype, bool isEquality, bool useOr,
  83                                                    int varRelid)
  84 {
  85         Selectivity selec;
  86         VariableStatData vardata;
  87         Datum           constval;
  88         TypeCacheEntry *typentry;
  89         FmgrInfo   *cmpfunc;
  90
  91         /*
  92          * rightop must be a variable, else punt.
  93          */
  94         examine_variable(root, rightop, varRelid, &vardata);
  95         if (!vardata.rel)
  96         {
  97                 ReleaseVariableStats(vardata);
  98                 return -1.0;
  99         }
 100
 101         /*
 102          * Aggressively reduce leftop to a constant, if possible.
 103          */
 104         leftop = estimate_expression_value(root, leftop);
 105         if (!IsA(leftop, Const))
 106         {
 107                 ReleaseVariableStats(vardata);
 108                 return -1.0;
 109         }
 110         if (((Const *) leftop)->constisnull)
 111         {
 112                 /* qual can't succeed if null on left */
 113                 ReleaseVariableStats(vardata);
 114                 return (Selectivity) 0.0;
 115         }
 116         constval = ((Const *) leftop)->constvalue;
 117
 118         /* Get element type's default comparison function */
 119         typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
 120         if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
 121         {
 122                 ReleaseVariableStats(vardata);
 123                 return -1.0;
 124         }
 125         cmpfunc = &typentry->cmp_proc_finfo;
 126
 127         /*
 128          * If the operator is <>, swap ANY/ALL, then invert the result later.
 129          */
 130         if (!isEquality)
 131                 useOr = !useOr;
 132
 133         /* Get array element stats for var, if available */
 134         if (HeapTupleIsValid(vardata.statsTuple))
 135         {
 136                 Form_pg_statistic stats;
 137                 Datum      *values;
 138                 int                     nvalues;
 139                 float4     *numbers;
 140                 int                     nnumbers;
 141                 float4     *hist;
 142                 int                     nhist;
 143
 144                 stats = (Form_pg_statistic) GETSTRUCT(vardata.statsTuple);
 145
 146                 /* MCELEM will be an array of same type as element */
 147                 if (get_attstatsslot(vardata.statsTuple,
 148                                                          elemtype, vardata.atttypmod,
 149                                                          STATISTIC_KIND_MCELEM, InvalidOid,
 150                                                          NULL,
 151                                                          &values, &nvalues,
 152                                                          &numbers, &nnumbers))
 153                 {
 154                         /* For ALL case, also get histogram of distinct-element counts */
 155                         if (useOr ||
 156                                 !get_attstatsslot(vardata.statsTuple,
 157                                                                   elemtype, vardata.atttypmod,
 158                                                                   STATISTIC_KIND_DECHIST, InvalidOid,
 159                                                                   NULL,
 160                                                                   NULL, NULL,
 161                                                                   &hist, &nhist))
 162                         {
 163                                 hist = NULL;
 164                                 nhist = 0;
 165                         }
 166
 167                         /*
 168                          * For = ANY, estimate as var @> ARRAY[const].
 169                          *
 170                          * For = ALL, estimate as var <@ ARRAY[const].
 171                          */
 172                         if (useOr)
 173                                 selec = mcelem_array_contain_overlap_selec(values, nvalues,
 174                                                                                                                    numbers, nnumbers,
 175                                                                                                                    &constval, 1,
 176                                                                                                            OID_ARRAY_CONTAINS_OP,
 177                                                                                                                    cmpfunc);
 178                         else
 179                                 selec = mcelem_array_contained_selec(values, nvalues,
 180                                                                                                          numbers, nnumbers,
 181                                                                                                          &constval, 1,
 182                                                                                                          hist, nhist,
 183                                                                                                          OID_ARRAY_CONTAINED_OP,
 184                                                                                                          cmpfunc);
 185
 186                         if (hist)
 187                                 free_attstatsslot(elemtype, NULL, 0, hist, nhist);
 188                         free_attstatsslot(elemtype, values, nvalues, numbers, nnumbers);
 189                 }
 190                 else
 191                 {
 192                         /* No most-common-elements info, so do without */
 193                         if (useOr)
 194                                 selec = mcelem_array_contain_overlap_selec(NULL, 0,
 195                                                                                                                    NULL, 0,
 196                                                                                                                    &constval, 1,
 197                                                                                                            OID_ARRAY_CONTAINS_OP,
 198                                                                                                                    cmpfunc);
 199                         else
 200                                 selec = mcelem_array_contained_selec(NULL, 0,
 201                                                                                                          NULL, 0,
 202                                                                                                          &constval, 1,
 203                                                                                                          NULL, 0,
 204                                                                                                          OID_ARRAY_CONTAINED_OP,
 205                                                                                                          cmpfunc);
 206                 }
 207
 208                 /*
 209                  * MCE stats count only non-null rows, so adjust for null rows.
 210                  */
 211                 selec *= (1.0 - stats->stanullfrac);
 212         }
 213         else
 214         {
 215                 /* No stats at all, so do without */
 216                 if (useOr)
 217                         selec = mcelem_array_contain_overlap_selec(NULL, 0,
 218                                                                                                            NULL, 0,
 219                                                                                                            &constval, 1,
 220                                                                                                            OID_ARRAY_CONTAINS_OP,
 221                                                                                                            cmpfunc);
 222                 else
 223                         selec = mcelem_array_contained_selec(NULL, 0,
 224                                                                                                  NULL, 0,
 225                                                                                                  &constval, 1,
 226                                                                                                  NULL, 0,
 227                                                                                                  OID_ARRAY_CONTAINED_OP,
 228                                                                                                  cmpfunc);
 229                 /* we assume no nulls here, so no stanullfrac correction */
 230         }
 231
 232         ReleaseVariableStats(vardata);
 233
 234         /*
 235          * If the operator is <>, invert the results.
 236          */
 237         if (!isEquality)
 238                 selec = 1.0 - selec;
 239
 240         CLAMP_PROBABILITY(selec);
 241
 242         return selec;
 243 }
 244
 245 /*
 246  * arraycontsel -- restriction selectivity for array @>, &&, <@ operators
 247  */
 248 Datum
 249 arraycontsel(PG_FUNCTION_ARGS)
 250 {
 251         PlannerInfo *root = (PlannerInfo *) PG_GETARG_POINTER(0);
 252         Oid                     operator = PG_GETARG_OID(1);
 253         List       *args = (List *) PG_GETARG_POINTER(2);
 254         int                     varRelid = PG_GETARG_INT32(3);
 255         VariableStatData vardata;
 256         Node       *other;
 257         bool            varonleft;
 258         Selectivity selec;
 259         Oid                     element_typeid;
 260
 261         /*
 262          * If expression is not (variable op something) or (something op
 263          * variable), then punt and return a default estimate.
 264          */
 265         if (!get_restriction_variable(root, args, varRelid,
 266                                                                   &vardata, &other, &varonleft))
 267                 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
 268
 269         /*
 270          * Can't do anything useful if the something is not a constant, either.
 271          */
 272         if (!IsA(other, Const))
 273         {
 274                 ReleaseVariableStats(vardata);
 275                 PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
 276         }
 277
 278         /*
 279          * The "&&", "@>" and "<@" operators are strict, so we can cope with a
 280          * NULL constant right away.
 281          */
 282         if (((Const *) other)->constisnull)
 283         {
 284                 ReleaseVariableStats(vardata);
 285                 PG_RETURN_FLOAT8(0.0);
 286         }
 287
 288         /*
 289          * If var is on the right, commute the operator, so that we can assume the
 290          * var is on the left in what follows.
 291          */
 292         if (!varonleft)
 293         {
 294                 if (operator == OID_ARRAY_CONTAINS_OP)
 295                         operator = OID_ARRAY_CONTAINED_OP;
 296                 else if (operator == OID_ARRAY_CONTAINED_OP)
 297                         operator = OID_ARRAY_CONTAINS_OP;
 298         }
 299
 300         /*
 301          * OK, there's a Var and a Const we're dealing with here.  We need the
 302          * Const to be a array with same element type as column, else we can't do
 303          * anything useful.  (Such cases will likely fail at runtime, but here
 304          * we'd rather just return a default estimate.)
 305          */
 306         element_typeid = get_base_element_type(((Const *) other)->consttype);
 307         if (element_typeid != InvalidOid &&
 308                 element_typeid == get_base_element_type(vardata.vartype))
 309         {
 310                 selec = calc_arraycontsel(&vardata, ((Const *) other)->constvalue,
 311                                                                   element_typeid, operator);
 312         }
 313         else
 314         {
 315                 selec = DEFAULT_SEL(operator);
 316         }
 317
 318         ReleaseVariableStats(vardata);
 319
 320         CLAMP_PROBABILITY(selec);
 321
 322         PG_RETURN_FLOAT8((float8) selec);
 323 }
 324
 325 /*
 326  * arraycontjoinsel -- join selectivity for array @>, &&, <@ operators
 327  */
 328 Datum
 329 arraycontjoinsel(PG_FUNCTION_ARGS)
 330 {
 331         /* For the moment this is just a stub */
 332         Oid                     operator = PG_GETARG_OID(1);
 333
 334         PG_RETURN_FLOAT8(DEFAULT_SEL(operator));
 335 }
 336
 337 /*
 338  * Calculate selectivity for "arraycolumn @> const", "arraycolumn && const"
 339  * or "arraycolumn <@ const" based on the statistics
 340  *
 341  * This function is mainly responsible for extracting the pg_statistic data
 342  * to be used; we then pass the problem on to mcelem_array_selec().
 343  */
 344 static Selectivity
 345 calc_arraycontsel(VariableStatData *vardata, Datum constval,
 346                                   Oid elemtype, Oid operator)
 347 {
 348         Selectivity selec;
 349         TypeCacheEntry *typentry;
 350         FmgrInfo   *cmpfunc;
 351         ArrayType  *array;
 352
 353         /* Get element type's default comparison function */
 354         typentry = lookup_type_cache(elemtype, TYPECACHE_CMP_PROC_FINFO);
 355         if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
 356                 return DEFAULT_SEL(operator);
 357         cmpfunc = &typentry->cmp_proc_finfo;
 358
 359         /*
 360          * The caller made sure the const is a array with same element type, so
 361          * get it now
 362          */
 363         array = DatumGetArrayTypeP(constval);
 364
 365         if (HeapTupleIsValid(vardata->statsTuple))
 366         {
 367                 Form_pg_statistic stats;
 368                 Datum      *values;
 369                 int                     nvalues;
 370                 float4     *numbers;
 371                 int                     nnumbers;
 372                 float4     *hist;
 373                 int                     nhist;
 374
 375                 stats = (Form_pg_statistic) GETSTRUCT(vardata->statsTuple);
 376
 377                 /* MCELEM will be an array of same type as column */
 378                 if (get_attstatsslot(vardata->statsTuple,
 379                                                          elemtype, vardata->atttypmod,
 380                                                          STATISTIC_KIND_MCELEM, InvalidOid,
 381                                                          NULL,
 382                                                          &values, &nvalues,
 383                                                          &numbers, &nnumbers))
 384                 {
 385                         /*
 386                          * For "array <@ const" case we also need histogram of distinct
 387                          * element counts.
 388                          */
 389                         if (operator != OID_ARRAY_CONTAINED_OP ||
 390                                 !get_attstatsslot(vardata->statsTuple,
 391                                                                   elemtype, vardata->atttypmod,
 392                                                                   STATISTIC_KIND_DECHIST, InvalidOid,
 393                                                                   NULL,
 394                                                                   NULL, NULL,
 395                                                                   &hist, &nhist))
 396                         {
 397                                 hist = NULL;
 398                                 nhist = 0;
 399                         }
 400
 401                         /* Use the most-common-elements slot for the array Var. */
 402                         selec = mcelem_array_selec(array, typentry,
 403                                                                            values, nvalues,
 404                                                                            numbers, nnumbers,
 405                                                                            hist, nhist,
 406                                                                            operator, cmpfunc);
 407
 408                         if (hist)
 409                                 free_attstatsslot(elemtype, NULL, 0, hist, nhist);
 410                         free_attstatsslot(elemtype, values, nvalues, numbers, nnumbers);
 411                 }
 412                 else
 413                 {
 414                         /* No most-common-elements info, so do without */
 415                         selec = mcelem_array_selec(array, typentry,
 416                                                                            NULL, 0, NULL, 0, NULL, 0,
 417                                                                            operator, cmpfunc);
 418                 }
 419
 420                 /*
 421                  * MCE stats count only non-null rows, so adjust for null rows.
 422                  */
 423                 selec *= (1.0 - stats->stanullfrac);
 424         }
 425         else
 426         {
 427                 /* No stats at all, so do without */
 428                 selec = mcelem_array_selec(array, typentry,
 429                                                                    NULL, 0, NULL, 0, NULL, 0,
 430                                                                    operator, cmpfunc);
 431                 /* we assume no nulls here, so no stanullfrac correction */
 432         }
 433
 434         /* If constant was toasted, release the copy we made */
 435         if (PointerGetDatum(array) != constval)
 436                 pfree(array);
 437
 438         return selec;
 439 }
 440
 441 /*
 442  * Array selectivity estimation based on most common elements statistics
 443  *
 444  * This function just deconstructs and sorts the array constant's contents,
 445  * and then passes the problem on to mcelem_array_contain_overlap_selec or
 446  * mcelem_array_contained_selec depending on the operator.
 447  */
 448 static Selectivity
 449 mcelem_array_selec(ArrayType *array, TypeCacheEntry *typentry,
 450                                    Datum *mcelem, int nmcelem,
 451                                    float4 *numbers, int nnumbers,
 452                                    float4 *hist, int nhist,
 453                                    Oid operator, FmgrInfo *cmpfunc)
 454 {
 455         Selectivity selec;
 456         int                     num_elems;
 457         Datum      *elem_values;
 458         bool       *elem_nulls;
 459         bool            null_present;
 460         int                     nonnull_nitems;
 461         int                     i;
 462
 463         /*
 464          * Prepare constant array data for sorting.  Sorting lets us find unique
 465          * elements and efficiently merge with the MCELEM array.
 466          */
 467         deconstruct_array(array,
 468                                           typentry->type_id,
 469                                           typentry->typlen,
 470                                           typentry->typbyval,
 471                                           typentry->typalign,
 472                                           &elem_values, &elem_nulls, &num_elems);
 473
 474         /* Collapse out any null elements */
 475         nonnull_nitems = 0;
 476         null_present = false;
 477         for (i = 0; i < num_elems; i++)
 478         {
 479                 if (elem_nulls[i])
 480                         null_present = true;
 481                 else
 482                         elem_values[nonnull_nitems++] = elem_values[i];
 483         }
 484
 485         /*
 486          * Query "column @> '{anything, null}'" matches nothing.  For the other
 487          * two operators, presence of a null in the constant can be ignored.
 488          */
 489         if (null_present && operator == OID_ARRAY_CONTAINS_OP)
 490         {
 491                 pfree(elem_values);
 492                 pfree(elem_nulls);
 493                 return (Selectivity) 0.0;
 494         }
 495
 496         /* Sort extracted elements using their default comparison function. */
 497         qsort_arg(elem_values, nonnull_nitems, sizeof(Datum),
 498                           element_compare, cmpfunc);
 499
 500         /* Separate cases according to operator */
 501         if (operator == OID_ARRAY_CONTAINS_OP || operator == OID_ARRAY_OVERLAP_OP)
 502                 selec = mcelem_array_contain_overlap_selec(mcelem, nmcelem,
 503                                                                                                    numbers, nnumbers,
 504                                                                                                  elem_values, nonnull_nitems,
 505                                                                                                    operator, cmpfunc);
 506         else if (operator == OID_ARRAY_CONTAINED_OP)
 507                 selec = mcelem_array_contained_selec(mcelem, nmcelem,
 508                                                                                          numbers, nnumbers,
 509                                                                                          elem_values, nonnull_nitems,
 510                                                                                          hist, nhist,
 511                                                                                          operator, cmpfunc);
 512         else
 513         {
 514                 elog(ERROR, "arraycontsel called for unrecognized operator %u",
 515                          operator);
 516                 selec = 0.0;                    /* keep compiler quiet */
 517         }
 518
 519         pfree(elem_values);
 520         pfree(elem_nulls);
 521         return selec;
 522 }
 523
 524 /*
 525  * Estimate selectivity of "column @> const" and "column && const" based on
 526  * most common element statistics.      This estimation assumes element
 527  * occurrences are independent.
 528  *
 529  * mcelem (of length nmcelem) and numbers (of length nnumbers) are from
 530  * the array column's MCELEM statistics slot, or are NULL/0 if stats are
 531  * not available.  array_data (of length nitems) is the constant's elements.
 532  *
 533  * Both the mcelem and array_data arrays are assumed presorted according
 534  * to the element type's cmpfunc.  Null elements are not present.
 535  *
 536  * TODO: this estimate probably could be improved by using the distinct
 537  * elements count histogram.  For example, excepting the special case of
 538  * "column @> '{}'", we can multiply the calculated selectivity by the
 539  * fraction of nonempty arrays in the column.
 540  */
 541 static Selectivity
 542 mcelem_array_contain_overlap_selec(Datum *mcelem, int nmcelem,
 543                                                                    float4 *numbers, int nnumbers,
 544                                                                    Datum *array_data, int nitems,
 545                                                                    Oid operator, FmgrInfo *cmpfunc)
 546 {
 547         Selectivity selec,
 548                                 elem_selec;
 549         int                     mcelem_index,
 550                                 i;
 551         bool            use_bsearch;
 552         float4          minfreq;
 553
 554         /*
 555          * There should be three more Numbers than Values, because the last three
 556          * cells should hold minimal and maximal frequency among the non-null
 557          * elements, and then the frequency of null elements.  Ignore the Numbers
 558          * if not right.
 559          */
 560         if (nnumbers != nmcelem + 3)
 561         {
 562                 numbers = NULL;
 563                 nnumbers = 0;
 564         }
 565
 566         if (numbers)
 567         {
 568                 /* Grab the lowest observed frequency */
 569                 minfreq = numbers[nmcelem];
 570         }
 571         else
 572         {
 573                 /* Without statistics make some default assumptions */
 574                 minfreq = 2 * (float4) DEFAULT_CONTAIN_SEL;
 575         }
 576
 577         /* Decide whether it is faster to use binary search or not. */
 578         if (nitems * floor_log2((uint32) nmcelem) < nmcelem + nitems)
 579                 use_bsearch = true;
 580         else
 581                 use_bsearch = false;
 582
 583         if (operator == OID_ARRAY_CONTAINS_OP)
 584         {
 585                 /*
 586                  * Initial selectivity for "column @> const" query is 1.0, and it will
 587                  * be decreased with each element of constant array.
 588                  */
 589                 selec = 1.0;
 590         }
 591         else
 592         {
 593                 /*
 594                  * Initial selectivity for "column && const" query is 0.0, and it will
 595                  * be increased with each element of constant array.
 596                  */
 597                 selec = 0.0;
 598         }
 599
 600         /* Scan mcelem and array in parallel. */
 601         mcelem_index = 0;
 602         for (i = 0; i < nitems; i++)
 603         {
 604                 bool            match = false;
 605
 606                 /* Ignore any duplicates in the array data. */
 607                 if (i > 0 &&
 608                         element_compare(&array_data[i - 1], &array_data[i], cmpfunc) == 0)
 609                         continue;
 610
 611                 /* Find the smallest MCELEM >= this array item. */
 612                 if (use_bsearch)
 613                 {
 614                         match = find_next_mcelem(mcelem, nmcelem, array_data[i],
 615                                                                          &mcelem_index, cmpfunc);
 616                 }
 617                 else
 618                 {
 619                         while (mcelem_index < nmcelem)
 620                         {
 621                                 int                     cmp = element_compare(&mcelem[mcelem_index],
 622                                                                                                   &array_data[i],
 623                                                                                                   cmpfunc);
 624
 625                                 if (cmp < 0)
 626                                         mcelem_index++;
 627                                 else
 628                                 {
 629                                         if (cmp == 0)
 630                                                 match = true;   /* mcelem is found */
 631                                         break;
 632                                 }
 633                         }
 634                 }
 635
 636                 if (match && numbers)
 637                 {
 638                         /* MCELEM matches the array item; use its frequency. */
 639                         elem_selec = numbers[mcelem_index];
 640                         mcelem_index++;
 641                 }
 642                 else
 643                 {
 644                         /*
 645                          * The element is not in MCELEM.  Punt, but assume that the
 646                          * selectivity cannot be more than minfreq / 2.
 647                          */
 648                         elem_selec = Min(DEFAULT_CONTAIN_SEL, minfreq / 2);
 649                 }
 650
 651                 /*
 652                  * Update overall selectivity using the current element's selectivity
 653                  * and an assumption of element occurrence independence.
 654                  */
 655                 if (operator == OID_ARRAY_CONTAINS_OP)
 656                         selec *= elem_selec;
 657                 else
 658                         selec = selec + elem_selec - selec * elem_selec;
 659
 660                 /* Clamp intermediate results to stay sane despite roundoff error */
 661                 CLAMP_PROBABILITY(selec);
 662         }
 663
 664         return selec;
 665 }
 666
 667 /*
 668  * Estimate selectivity of "column <@ const" based on most common element
 669  * statistics.
 670  *
 671  * mcelem (of length nmcelem) and numbers (of length nnumbers) are from
 672  * the array column's MCELEM statistics slot, or are NULL/0 if stats are
 673  * not available.  array_data (of length nitems) is the constant's elements.
 674  * hist (of length nhist) is from the array column's DECHIST statistics slot,
 675  * or is NULL/0 if those stats are not available.
 676  *
 677  * Both the mcelem and array_data arrays are assumed presorted according
 678  * to the element type's cmpfunc.  Null elements are not present.
 679  *
 680  * Independent element occurrence would imply a particular distribution of
 681  * distinct element counts among matching rows.  Real data usually falsifies
 682  * that assumption.  For example, in a set of 11-element integer arrays having
 683  * elements in the range [0..10], element occurrences are typically not
 684  * independent.  If they were, a sufficiently-large set would include all
 685  * distinct element counts 0 through 11.  We correct for this using the
 686  * histogram of distinct element counts.
 687  *
 688  * In the "column @> const" and "column && const" cases, we usually have a
 689  * "const" with low number of elements (otherwise we have selectivity close
 690  * to 0 or 1 respectively).  That's why the effect of dependence related
 691  * to distinct element count distribution is negligible there.  In the
 692  * "column <@ const" case, number of elements is usually high (otherwise we
 693  * have selectivity close to 0).  That's why we should do a correction with
 694  * the array distinct element count distribution here.
 695  *
 696  * Using the histogram of distinct element counts produces a different
 697  * distribution law than independent occurrences of elements.  This
 698  * distribution law can be described as follows:
 699  *
 700  * P(o1, o2, ..., on) = f1^o1 * (1 - f1)^(1 - o1) * f2^o2 *
 701  *        (1 - f2)^(1 - o2) * ... * fn^on * (1 - fn)^(1 - on) * hist[m] / ind[m]
 702  *
 703  * where:
 704  * o1, o2, ..., on - occurrences of elements 1, 2, ..., n
 705  *              (1 - occurrence, 0 - no occurrence) in row
 706  * f1, f2, ..., fn - frequencies of elements 1, 2, ..., n
 707  *              (scalar values in [0..1]) according to collected statistics
 708  * m = o1 + o2 + ... + on = total number of distinct elements in row
 709  * hist[m] - histogram data for occurrence of m elements.
 710  * ind[m] - probability of m occurrences from n events assuming their
 711  *        probabilities to be equal to frequencies of array elements.
 712  *
 713  * ind[m] = sum(f1^o1 * (1 - f1)^(1 - o1) * f2^o2 * (1 - f2)^(1 - o2) *
 714  * ... * fn^on * (1 - fn)^(1 - on), o1, o2, ..., on) | o1 + o2 + .. on = m
 715  */
 716 static Selectivity
 717 mcelem_array_contained_selec(Datum *mcelem, int nmcelem,
 718                                                          float4 *numbers, int nnumbers,
 719                                                          Datum *array_data, int nitems,
 720                                                          float4 *hist, int nhist,
 721                                                          Oid operator, FmgrInfo *cmpfunc)
 722 {
 723         int                     mcelem_index,
 724                                 i,
 725                                 unique_nitems = 0;
 726         float           selec,
 727                                 minfreq,
 728                                 nullelem_freq;
 729         float      *dist,
 730                            *mcelem_dist,
 731                            *hist_part;
 732         float           avg_count,
 733                                 mult,
 734                                 rest;
 735         float      *elem_selec;
 736
 737         /*
 738          * There should be three more Numbers than Values in the MCELEM slot,
 739          * because the last three cells should hold minimal and maximal frequency
 740          * among the non-null elements, and then the frequency of null elements.
 741          * Punt if not right, because we can't do much without the element freqs.
 742          */
 743         if (numbers == NULL || nnumbers != nmcelem + 3)
 744                 return DEFAULT_CONTAIN_SEL;
 745
 746         /* Can't do much without a count histogram, either */
 747         if (hist == NULL || nhist < 3)
 748                 return DEFAULT_CONTAIN_SEL;
 749
 750         /*
 751          * Grab some of the summary statistics that compute_array_stats() stores:
 752          * lowest frequency, frequency of null elements, and average distinct
 753          * element count.
 754          */
 755         minfreq = numbers[nmcelem];
 756         nullelem_freq = numbers[nmcelem + 2];
 757         avg_count = hist[nhist - 1];
 758
 759         /*
 760          * "rest" will be the sum of the frequencies of all elements not
 761          * represented in MCELEM.  The average distinct element count is the sum
 762          * of the frequencies of *all* elements.  Begin with that; we will proceed
 763          * to subtract the MCELEM frequencies.
 764          */
 765         rest = avg_count;
 766
 767         /*
 768          * mult is a multiplier representing estimate of probability that each
 769          * mcelem that is not present in constant doesn't occur.
 770          */
 771         mult = 1.0f;
 772
 773         /*
 774          * elem_selec is array of estimated frequencies for elements in the
 775          * constant.
 776          */
 777         elem_selec = (float *) palloc(sizeof(float) * nitems);
 778
 779         /* Scan mcelem and array in parallel. */
 780         mcelem_index = 0;
 781         for (i = 0; i < nitems; i++)
 782         {
 783                 bool            match = false;
 784
 785                 /* Ignore any duplicates in the array data. */
 786                 if (i > 0 &&
 787                         element_compare(&array_data[i - 1], &array_data[i], cmpfunc) == 0)
 788                         continue;
 789
 790                 /*
 791                  * Iterate over MCELEM until we find an entry greater than or equal to
 792                  * this element of the constant.  Update "rest" and "mult" for mcelem
 793                  * entries skipped over.
 794                  */
 795                 while (mcelem_index < nmcelem)
 796                 {
 797                         int                     cmp = element_compare(&mcelem[mcelem_index],
 798                                                                                           &array_data[i],
 799                                                                                           cmpfunc);
 800
 801                         if (cmp < 0)
 802                         {
 803                                 mult *= (1.0f - numbers[mcelem_index]);
 804                                 rest -= numbers[mcelem_index];
 805                                 mcelem_index++;
 806                         }
 807                         else
 808                         {
 809                                 if (cmp == 0)
 810                                         match = true;           /* mcelem is found */
 811                                 break;
 812                         }
 813                 }
 814
 815                 if (match)
 816                 {
 817                         /* MCELEM matches the array item. */
 818                         elem_selec[unique_nitems] = numbers[mcelem_index];
 819                         /* "rest" is decremented for all mcelems, matched or not */
 820                         rest -= numbers[mcelem_index];
 821                         mcelem_index++;
 822                 }
 823                 else
 824                 {
 825                         /*
 826                          * The element is not in MCELEM.  Punt, but assume that the
 827                          * selectivity cannot be more than minfreq / 2.
 828                          */
 829                         elem_selec[unique_nitems] = Min(DEFAULT_CONTAIN_SEL,
 830                                                                                         minfreq / 2);
 831                 }
 832
 833                 unique_nitems++;
 834         }
 835
 836         /*
 837          * If we handled all constant elements without exhausting the MCELEM
 838          * array, finish walking it to complete calculation of "rest" and "mult".
 839          */
 840         while (mcelem_index < nmcelem)
 841         {
 842                 mult *= (1.0f - numbers[mcelem_index]);
 843                 rest -= numbers[mcelem_index];
 844                 mcelem_index++;
 845         }
 846
 847         /*
 848          * The presence of many distinct rare elements materially decreases
 849          * selectivity.  Use the Poisson distribution to estimate the probability
 850          * of a column value having zero occurrences of such elements.  See above
 851          * for the definition of "rest".
 852          */
 853         mult *= exp(-rest);
 854
 855         /*----------
 856          * Using the distinct element count histogram requires
 857          *              O(unique_nitems * (nmcelem + unique_nitems))
 858          * operations.  Beyond a certain computational cost threshold, it's
 859          * reasonable to sacrifice accuracy for decreased planning time.  We limit
 860          * the number of operations to EFFORT * nmcelem; since nmcelem is limited
 861          * by the column's statistics target, the work done is user-controllable.
 862          *
 863          * If the number of operations would be too large, we can reduce it
 864          * without losing all accuracy by reducing unique_nitems and considering
 865          * only the most-common elements of the constant array.  To make the
 866          * results exactly match what we would have gotten with only those
 867          * elements to start with, we'd have to remove any discarded elements'
 868          * frequencies from "mult", but since this is only an approximation
 869          * anyway, we don't bother with that.  Therefore it's sufficient to qsort
 870          * elem_selec[] and take the largest elements.  (They will no longer match
 871          * up with the elements of array_data[], but we don't care.)
 872          *----------
 873          */
 874 #define EFFORT 100
 875
 876         if ((nmcelem + unique_nitems) > 0 &&
 877                 unique_nitems > EFFORT * nmcelem / (nmcelem + unique_nitems))
 878         {
 879                 /*
 880                  * Use the quadratic formula to solve for largest allowable N.  We
 881                  * have A = 1, B = nmcelem, C = - EFFORT * nmcelem.
 882                  */
 883                 double          b = (double) nmcelem;
 884                 int                     n;
 885
 886                 n = (int) ((sqrt(b * b + 4 * EFFORT * b) - b) / 2);
 887
 888                 /* Sort, then take just the first n elements */
 889                 qsort(elem_selec, unique_nitems, sizeof(float),
 890                           float_compare_desc);
 891                 unique_nitems = n;
 892         }
 893
 894         /*
 895          * Calculate probabilities of each distinct element count for both mcelems
 896          * and constant elements.  At this point, assume independent element
 897          * occurrence.
 898          */
 899         dist = calc_distr(elem_selec, unique_nitems, unique_nitems, 0.0f);
 900         mcelem_dist = calc_distr(numbers, nmcelem, unique_nitems, rest);
 901
 902         /* ignore hist[nhist-1], which is the average not a histogram member */
 903         hist_part = calc_hist(hist, nhist - 1, unique_nitems);
 904
 905         selec = 0.0f;
 906         for (i = 0; i <= unique_nitems; i++)
 907         {
 908                 /*
 909                  * mult * dist[i] / mcelem_dist[i] gives us probability of qual
 910                  * matching from assumption of independent element occurrence with the
 911                  * condition that distinct element count = i.
 912                  */
 913                 if (mcelem_dist[i] > 0)
 914                         selec += hist_part[i] * mult * dist[i] / mcelem_dist[i];
 915         }
 916
 917         pfree(dist);
 918         pfree(mcelem_dist);
 919         pfree(hist_part);
 920         pfree(elem_selec);
 921
 922         /* Take into account occurrence of NULL element. */
 923         selec *= (1.0f - nullelem_freq);
 924
 925         CLAMP_PROBABILITY(selec);
 926
 927         return selec;
 928 }
 929
 930 /*
 931  * Calculate the first n distinct element count probabilities from a
 932  * histogram of distinct element counts.
 933  *
 934  * Returns a palloc'd array of n+1 entries, with array[k] being the
 935  * probability of element count k, k in [0..n].
 936  *
 937  * We assume that a histogram box with bounds a and b gives 1 / ((b - a + 1) *
 938  * (nhist - 1)) probability to each value in (a,b) and an additional half of
 939  * that to a and b themselves.
 940  */
 941 static float *
 942 calc_hist(const float4 *hist, int nhist, int n)
 943 {
 944         float      *hist_part;
 945         int                     k,
 946                                 i = 0;
 947         float           prev_interval = 0,
 948                                 next_interval;
 949         float           frac;
 950
 951         hist_part = (float *) palloc((n + 1) * sizeof(float));
 952
 953         /*
 954          * frac is a probability contribution for each interval between histogram
 955          * values.      We have nhist - 1 intervals, so contribution of each one will
 956          * be 1 / (nhist - 1).
 957          */
 958         frac = 1.0f / ((float) (nhist - 1));
 959
 960         for (k = 0; k <= n; k++)
 961         {
 962                 int                     count = 0;
 963
 964                 /*
 965                  * Count the histogram boundaries equal to k.  (Although the histogram
 966                  * should theoretically contain only exact integers, entries are
 967                  * floats so there could be roundoff error in large values.  Treat any
 968                  * fractional value as equal to the next larger k.)
 969                  */
 970                 while (i < nhist && hist[i] <= k)
 971                 {
 972                         count++;
 973                         i++;
 974                 }
 975
 976                 if (count > 0)
 977                 {
 978                         /* k is an exact bound for at least one histogram box. */
 979                         float           val;
 980
 981                         /* Find length between current histogram value and the next one */
 982                         if (i < nhist)
 983                                 next_interval = hist[i] - hist[i - 1];
 984                         else
 985                                 next_interval = 0;
 986
 987                         /*
 988                          * count - 1 histogram boxes contain k exclusively.  They
 989                          * contribute a total of (count - 1) * frac probability.  Also
 990                          * factor in the partial histogram boxes on either side.
 991                          */
 992                         val = (float) (count - 1);
 993                         if (next_interval > 0)
 994                                 val += 0.5f / next_interval;
 995                         if (prev_interval > 0)
 996                                 val += 0.5f / prev_interval;
 997                         hist_part[k] = frac * val;
 998
 999                         prev_interval = next_interval;
1000                 }
1001                 else
1002                 {
1003                         /* k does not appear as an exact histogram bound. */
1004                         if (prev_interval > 0)
1005                                 hist_part[k] = frac / prev_interval;
1006                         else
1007                                 hist_part[k] = 0.0f;
1008                 }
1009         }
1010
1011         return hist_part;
1012 }
1013
1014 /*
1015  * Consider n independent events with probabilities p[].  This function
1016  * calculates probabilities of exact k of events occurrence for k in [0..m].
1017  * Returns a palloc'd array of size m+1.
1018  *
1019  * "rest" is the sum of the probabilities of all low-probability events not
1020  * included in p.
1021  *
1022  * Imagine matrix M of size (n + 1) x (m + 1).  Element M[i,j] denotes the
1023  * probability that exactly j of first i events occur.  Obviously M[0,0] = 1.
1024  * For any constant j, each increment of i increases the probability iff the
1025  * event occurs.  So, by the law of total probability:
1026  *      M[i,j] = M[i - 1, j] * (1 - p[i]) + M[i - 1, j - 1] * p[i]
1027  *              for i > 0, j > 0.
1028  *      M[i,0] = M[i - 1, 0] * (1 - p[i]) for i > 0.
1029  */
1030 static float *
1031 calc_distr(const float *p, int n, int m, float rest)
1032 {
1033         float      *row,
1034                            *prev_row,
1035                            *tmp;
1036         int                     i,
1037                                 j;
1038
1039         /*
1040          * Since we return only the last row of the matrix and need only the
1041          * current and previous row for calculations, allocate two rows.
1042          */
1043         row = (float *) palloc((m + 1) * sizeof(float));
1044         prev_row = (float *) palloc((m + 1) * sizeof(float));
1045
1046         /* M[0,0] = 1 */
1047         row[0] = 1.0f;
1048         for (i = 1; i <= n; i++)
1049         {
1050                 float           t = p[i - 1];
1051
1052                 /* Swap rows */
1053                 tmp = row;
1054                 row = prev_row;
1055                 prev_row = tmp;
1056
1057                 /* Calculate next row */
1058                 for (j = 0; j <= i && j <= m; j++)
1059                 {
1060                         float           val = 0.0f;
1061
1062                         if (j < i)
1063                                 val += prev_row[j] * (1.0f - t);
1064                         if (j > 0)
1065                                 val += prev_row[j - 1] * t;
1066                         row[j] = val;
1067                 }
1068         }
1069
1070         /*
1071          * The presence of many distinct rare (not in "p") elements materially
1072          * decreases selectivity.  Model their collective occurrence with the
1073          * Poisson distribution.
1074          */
1075         if (rest > DEFAULT_CONTAIN_SEL)
1076         {
1077                 float           t;
1078
1079                 /* Swap rows */
1080                 tmp = row;
1081                 row = prev_row;
1082                 prev_row = tmp;
1083
1084                 for (i = 0; i <= m; i++)
1085                         row[i] = 0.0f;
1086
1087                 /* Value of Poisson distribution for 0 occurrences */
1088                 t = exp(-rest);
1089
1090                 /*
1091                  * Calculate convolution of previously computed distribution and the
1092                  * Poisson distribution.
1093                  */
1094                 for (i = 0; i <= m; i++)
1095                 {
1096                         for (j = 0; j <= m - i; j++)
1097                                 row[j + i] += prev_row[j] * t;
1098
1099                         /* Get Poisson distribution value for (i + 1) occurrences */
1100                         t *= rest / (float) (i + 1);
1101                 }
1102         }
1103
1104         pfree(prev_row);
1105         return row;
1106 }
1107
1108 /* Fast function for floor value of 2 based logarithm calculation. */
1109 static int
1110 floor_log2(uint32 n)
1111 {
1112         int                     logval = 0;
1113
1114         if (n == 0)
1115                 return -1;
1116         if (n >= (1 << 16))
1117         {
1118                 n >>= 16;
1119                 logval += 16;
1120         }
1121         if (n >= (1 << 8))
1122         {
1123                 n >>= 8;
1124                 logval += 8;
1125         }
1126         if (n >= (1 << 4))
1127         {
1128                 n >>= 4;
1129                 logval += 4;
1130         }
1131         if (n >= (1 << 2))
1132         {
1133                 n >>= 2;
1134                 logval += 2;
1135         }
1136         if (n >= (1 << 1))
1137         {
1138                 logval += 1;
1139         }
1140         return logval;
1141 }
1142
1143 /*
1144  * find_next_mcelem binary-searches a most common elements array, starting
1145  * from *index, for the first member >= value.  It saves the position of the
1146  * match into *index and returns true if it's an exact match.  (Note: we
1147  * assume the mcelem elements are distinct so there can't be more than one
1148  * exact match.)
1149  */
1150 static bool
1151 find_next_mcelem(Datum *mcelem, int nmcelem, Datum value, int *index,
1152                                  FmgrInfo *cmpfunc)
1153 {
1154         int                     l = *index,
1155                                 r = nmcelem - 1,
1156                                 i,
1157                                 res;
1158
1159         while (l <= r)
1160         {
1161                 i = (l + r) / 2;
1162                 res = element_compare(&mcelem[i], &value, cmpfunc);
1163                 if (res == 0)
1164                 {
1165                         *index = i;
1166                         return true;
1167                 }
1168                 else if (res < 0)
1169                         l = i + 1;
1170                 else
1171                         r = i - 1;
1172         }
1173         *index = l;
1174         return false;
1175 }
1176
1177 /*
1178  * Comparison function for elements.
1179  *
1180  * We use the element type's default btree opclass, and the default collation
1181  * if the type is collation-sensitive.
1182  *
1183  * XXX consider using SortSupport infrastructure
1184  */
1185 static int
1186 element_compare(const void *key1, const void *key2, void *arg)
1187 {
1188         Datum           d1 = *((const Datum *) key1);
1189         Datum           d2 = *((const Datum *) key2);
1190         FmgrInfo   *cmpfunc = (FmgrInfo *) arg;
1191         Datum           c;
1192
1193         c = FunctionCall2Coll(cmpfunc, DEFAULT_COLLATION_OID, d1, d2);
1194         return DatumGetInt32(c);
1195 }
1196
1197 /*
1198  * Comparison function for sorting floats into descending order.
1199  */
1200 static int
1201 float_compare_desc(const void *key1, const void *key2)
1202 {
1203         float           d1 = *((const float *) key1);
1204         float           d2 = *((const float *) key2);
1205
1206         if (d1 > d2)
1207                 return -1;
1208         else if (d1 < d2)
1209                 return 1;
1210         else
1211                 return 0;
1212 }