/Users/deen/code/yugabyte-db/src/postgres/src/backend/statistics/dependencies.c

Source (jump to first uncovered line)
/*-------------------------------------------------------------------------
 *
 * dependencies.c
 *    POSTGRES functional dependencies
 *
 * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *    src/backend/statistics/dependencies.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/htup_details.h"
#include "access/sysattr.h"
#include "catalog/pg_operator.h"
#include "catalog/pg_statistic_ext.h"
#include "lib/stringinfo.h"
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/var.h"
#include "nodes/nodes.h"
#include "nodes/relation.h"
#include "statistics/extended_stats_internal.h"
#include "statistics/statistics.h"
#include "utils/bytea.h"
#include "utils/fmgroids.h"
#include "utils/fmgrprotos.h"
#include "utils/lsyscache.h"
#include "utils/syscache.h"
#include "utils/typcache.h"

/*
 * Internal state for DependencyGenerator of dependencies. Dependencies are similar to
 * k-permutations of n elements, except that the order does not matter for the
 * first (k-1) elements. That is, (a,b=>c) and (b,a=>c) are equivalent.
 */
typedef struct DependencyGeneratorData
{
  int     k;        /* size of the dependency */
  int     n;        /* number of possible attributes */
  int     current;    /* next dependency to return (index) */
  AttrNumber  ndependencies;  /* number of dependencies generated */
  AttrNumber *dependencies; /* array of pre-generated dependencies  */
} DependencyGeneratorData;

typedef DependencyGeneratorData *DependencyGenerator;

static void generate_dependencies_recurse(DependencyGenerator state,
                int index, AttrNumber start, AttrNumber *current);
static void generate_dependencies(DependencyGenerator state);
static DependencyGenerator DependencyGenerator_init(int n, int k);
static void DependencyGenerator_free(DependencyGenerator state);
static AttrNumber *DependencyGenerator_next(DependencyGenerator state);
static double dependency_degree(int numrows, HeapTuple *rows, int k,
          AttrNumber *dependency, VacAttrStats **stats, Bitmapset *attrs);
static bool dependency_is_fully_matched(MVDependency *dependency,
              Bitmapset *attnums);
static bool dependency_implies_attribute(MVDependency *dependency,
               AttrNumber attnum);
static bool dependency_is_compatible_clause(Node *clause, Index relid,
                AttrNumber *attnum);
static MVDependency *find_strongest_dependency(StatisticExtInfo *stats,
              MVDependencies *dependencies,
              Bitmapset *attnums);

static void
generate_dependencies_recurse(DependencyGenerator state, int index,
                AttrNumber start, AttrNumber *current)
{
  /*
   * The generator handles the first (k-1) elements differently from the
   * last element.
   */
  if (index < (state->k - 1))
  {
    AttrNumber  i;

    /*
     * The first (k-1) values have to be in ascending order, which we
     * generate recursively.
     */

    for (i = start; i < state->n; i++)
    {
      current[index] = i;
      generate_dependencies_recurse(state, (index + 1), (i + 1), current);
    }
  }
  else
  {
    int     i;

    /*
     * the last element is the implied value, which does not respect the
     * ascending order. We just need to check that the value is not in the
     * first (k-1) elements.
     */

    for (i = 0; i < state->n; i++)
    {
      int     j;
      bool    match = false;

      current[index] = i;

      for (j = 0; j < index; j++)
      {
        if (current[j] == i)
        {
          match = true;
          break;
        }
      }

      /*
       * If the value is not found in the first part of the dependency,
       * we're done.
       */
      if (!match)
      {
        state->dependencies = (AttrNumber *) repalloc(state->dependencies,
                                state->k * (state->ndependencies + 1) * sizeof(AttrNumber));
        memcpy(&state->dependencies[(state->k * state->ndependencies)],
             current, state->k * sizeof(AttrNumber));
        state->ndependencies++;
      }
    }
  }
}

/* generate all dependencies (k-permutations of n elements) */
static void
generate_dependencies(DependencyGenerator state)
{
  AttrNumber *current = (AttrNumber *) palloc0(sizeof(AttrNumber) * state->k);

  generate_dependencies_recurse(state, 0, 0, current);

  pfree(current);
}

/*
 * initialize the DependencyGenerator of variations, and prebuild the variations
 *
 * This pre-builds all the variations. We could also generate them in
 * DependencyGenerator_next(), but this seems simpler.
 */
static DependencyGenerator
DependencyGenerator_init(int n, int k)
{
  DependencyGenerator state;

  Assert((n >= k) && (k > 0));

  /* allocate the DependencyGenerator state */
  state = (DependencyGenerator) palloc0(sizeof(DependencyGeneratorData));
  state->dependencies = (AttrNumber *) palloc(k * sizeof(AttrNumber));

  state->ndependencies = 0;
  state->current = 0;
  state->k = k;
  state->n = n;

  /* now actually pre-generate all the variations */
  generate_dependencies(state);

  return state;
}

/* free the DependencyGenerator state */
static void
DependencyGenerator_free(DependencyGenerator state)
{
  pfree(state->dependencies);
  pfree(state);

}

/* generate next combination */
static AttrNumber *
DependencyGenerator_next(DependencyGenerator state)
{
  if (state->current == state->ndependencies)
    return NULL;

  return &state->dependencies[state->k * state->current++];
}


/*
 * validates functional dependency on the data
 *
 * An actual work horse of detecting functional dependencies. Given a variation
 * of k attributes, it checks that the first (k-1) are sufficient to determine
 * the last one.
 */
static double
dependency_degree(int numrows, HeapTuple *rows, int k, AttrNumber *dependency,
          VacAttrStats **stats, Bitmapset *attrs)
{
  int     i,
        j;
  int     nvalues = numrows * k;
  MultiSortSupport mss;
  SortItem   *items;
  Datum    *values;
  bool     *isnull;
  int      *attnums;

  /* counters valid within a group */
  int     group_size = 0;
  int     n_violations = 0;

  /* total number of rows supporting (consistent with) the dependency */
  int     n_supporting_rows = 0;

  /* Make sure we have at least two input attributes. */
  Assert(k >= 2);

  /* sort info for all attributes columns */
  mss = multi_sort_init(k);

  /* data for the sort */
  items = (SortItem *) palloc(numrows * sizeof(SortItem));
  values = (Datum *) palloc(sizeof(Datum) * nvalues);
  isnull = (bool *) palloc(sizeof(bool) * nvalues);

  /* fix the pointers to values/isnull */
  for (i = 0; i < numrows; i++)
  {
    items[i].values = &values[i * k];
    items[i].isnull = &isnull[i * k];
  }

  /*
   * Transform the bms into an array, to make accessing i-th member easier.
   */
  attnums = (int *) palloc(sizeof(int) * bms_num_members(attrs));
  i = 0;
  j = -1;
  while ((j = bms_next_member(attrs, j)) >= 0)
    attnums[i++] = j;

  /*
   * Verify the dependency (a,b,...)->z, using a rather simple algorithm:
   *
   * (a) sort the data lexicographically
   *
   * (b) split the data into groups by first (k-1) columns
   *
   * (c) for each group count different values in the last column
   */

  /* prepare the sort function for the first dimension, and SortItem array */
  for (i = 0; i < k; i++)
  {
    VacAttrStats *colstat = stats[dependency[i]];
    TypeCacheEntry *type;

    type = lookup_type_cache(colstat->attrtypid, TYPECACHE_LT_OPR);
    if (type->lt_opr == InvalidOid) /* shouldn't happen */
      elog(ERROR, "cache lookup failed for ordering operator for type %u",
         colstat->attrtypid);

    /* prepare the sort function for this dimension */
    multi_sort_add_dimension(mss, i, type->lt_opr);

    /* accumulate all the data for both columns into an array and sort it */
    for (j = 0; j < numrows; j++)
    {
      items[j].values[i] =
        heap_getattr(rows[j], attnums[dependency[i]],
               stats[i]->tupDesc, &items[j].isnull[i]);
    }
  }

  /* sort the items so that we can detect the groups */
  qsort_arg((void *) items, numrows, sizeof(SortItem),
        multi_sort_compare, mss);

  /*
   * Walk through the sorted array, split it into rows according to the
   * first (k-1) columns. If there's a single value in the last column, we
   * count the group as 'supporting' the functional dependency. Otherwise we
   * count it as contradicting.
   */

  /* start with the first row forming a group */
  group_size = 1;

  /* loop 1 beyond the end of the array so that we count the final group */
  for (i = 1; i <= numrows; i++)
  {
    /*
     * Check if the group ended, which may be either because we processed
     * all the items (i==numrows), or because the i-th item is not equal
     * to the preceding one.
     */
    if (i == numrows ||
      multi_sort_compare_dims(0, k - 2, &items[i - 1], &items[i], mss) != 0)
    {
      /*
       * If no violations were found in the group then track the rows of
       * the group as supporting the functional dependency.
       */
      if (n_violations == 0)
        n_supporting_rows += group_size;

      /* Reset counters for the new group */
      n_violations = 0;
      group_size = 1;
      continue;
    }
    /* first columns match, but the last one does not (so contradicting) */
    else if (multi_sort_compare_dim(k - 1, &items[i - 1], &items[i], mss) != 0)
      n_violations++;

    group_size++;
  }

  pfree(items);
  pfree(values);
  pfree(isnull);
  pfree(mss);

  /* Compute the 'degree of validity' as (supporting/total). */
  return (n_supporting_rows * 1.0 / numrows);
}

/*
 * detects functional dependencies between groups of columns
 *
 * Generates all possible subsets of columns (variations) and computes
 * the degree of validity for each one. For example when creating statistics
 * on three columns (a,b,c) there are 9 possible dependencies
 *
 *     two columns        three columns
 *     -----------        -------------
 *     (a) -> b         (a,b) -> c
 *     (a) -> c         (a,c) -> b
 *     (b) -> a         (b,c) -> a
 *     (b) -> c
 *     (c) -> a
 *     (c) -> b
 */
MVDependencies *
statext_dependencies_build(int numrows, HeapTuple *rows, Bitmapset *attrs,
               VacAttrStats **stats)
{
  int     i,
        j,
        k;
  int     numattrs;
  int      *attnums;

  /* result */
  MVDependencies *dependencies = NULL;

  numattrs = bms_num_members(attrs);

  /*
   * Transform the bms into an array, to make accessing i-th member easier.
   */
  attnums = palloc(sizeof(int) * bms_num_members(attrs));
  i = 0;
  j = -1;
  while ((j = bms_next_member(attrs, j)) >= 0)
    attnums[i++] = j;

  Assert(numattrs >= 2);

  /*
   * We'll try build functional dependencies starting from the smallest ones
   * covering just 2 columns, to the largest ones, covering all columns
   * included in the statistics object.  We start from the smallest ones
   * because we want to be able to skip already implied ones.
   */
  for (k = 2; k <= numattrs; k++)
  {
    AttrNumber *dependency; /* array with k elements */

    /* prepare a DependencyGenerator of variation */
    DependencyGenerator DependencyGenerator = DependencyGenerator_init(numattrs, k);

    /* generate all possible variations of k values (out of n) */
    while ((dependency = DependencyGenerator_next(DependencyGenerator)))
    {
      double    degree;
      MVDependency *d;

      /* compute how valid the dependency seems */
      degree = dependency_degree(numrows, rows, k, dependency, stats, attrs);

      /*
       * if the dependency seems entirely invalid, don't store it
       */
      if (degree == 0.0)
        continue;

      d = (MVDependency *) palloc0(offsetof(MVDependency, attributes)
                     + k * sizeof(AttrNumber));

      /* copy the dependency (and keep the indexes into stxkeys) */
      d->degree = degree;
      d->nattributes = k;
      for (i = 0; i < k; i++)
        d->attributes[i] = attnums[dependency[i]];

      /* initialize the list of dependencies */
      if (dependencies == NULL)
      {
        dependencies
          = (MVDependencies *) palloc0(sizeof(MVDependencies));

        dependencies->magic = STATS_DEPS_MAGIC;
        dependencies->type = STATS_DEPS_TYPE_BASIC;
        dependencies->ndeps = 0;
      }

      dependencies->ndeps++;
      dependencies = (MVDependencies *) repalloc(dependencies,
                             offsetof(MVDependencies, deps)
                             + dependencies->ndeps * sizeof(MVDependency));

      dependencies->deps[dependencies->ndeps - 1] = d;
    }

    /*
     * we're done with variations of k elements, so free the
     * DependencyGenerator
     */
    DependencyGenerator_free(DependencyGenerator);
  }

  return dependencies;
}


/*
 * Serialize list of dependencies into a bytea value.
 */
bytea *
statext_dependencies_serialize(MVDependencies *dependencies)
{
  int     i;
  bytea    *output;
  char     *tmp;
  Size    len;

  /* we need to store ndeps, with a number of attributes for each one */
  len = VARHDRSZ + SizeOfDependencies
    + dependencies->ndeps * SizeOfDependency;

  /* and also include space for the actual attribute numbers and degrees */
  for (i = 0; i < dependencies->ndeps; i++)
    len += (sizeof(AttrNumber) * dependencies->deps[i]->nattributes);

  output = (bytea *) palloc0(len);
  SET_VARSIZE(output, len);

  tmp = VARDATA(output);

  /* Store the base struct values (magic, type, ndeps) */
  memcpy(tmp, &dependencies->magic, sizeof(uint32));
  tmp += sizeof(uint32);
  memcpy(tmp, &dependencies->type, sizeof(uint32));
  tmp += sizeof(uint32);
  memcpy(tmp, &dependencies->ndeps, sizeof(uint32));
  tmp += sizeof(uint32);

  /* store number of attributes and attribute numbers for each dependency */
  for (i = 0; i < dependencies->ndeps; i++)
  {
    MVDependency *d = dependencies->deps[i];

    memcpy(tmp, d, SizeOfDependency);
    tmp += SizeOfDependency;

    memcpy(tmp, d->attributes, sizeof(AttrNumber) * d->nattributes);
    tmp += sizeof(AttrNumber) * d->nattributes;

    Assert(tmp <= ((char *) output + len));
  }

  return output;
}

/*
 * Reads serialized dependencies into MVDependencies structure.
 */
MVDependencies *
statext_dependencies_deserialize(bytea *data)
{
  int     i;
  Size    min_expected_size;
  MVDependencies *dependencies;
  char     *tmp;

  if (data == NULL)
    return NULL;

  if (VARSIZE_ANY_EXHDR(data) < SizeOfDependencies)
    elog(ERROR, "invalid MVDependencies size %zd (expected at least %zd)",
       VARSIZE_ANY_EXHDR(data), SizeOfDependencies);

  /* read the MVDependencies header */
  dependencies = (MVDependencies *) palloc0(sizeof(MVDependencies));

  /* initialize pointer to the data part (skip the varlena header) */
  tmp = VARDATA_ANY(data);

  /* read the header fields and perform basic sanity checks */
  memcpy(&dependencies->magic, tmp, sizeof(uint32));
  tmp += sizeof(uint32);
  memcpy(&dependencies->type, tmp, sizeof(uint32));
  tmp += sizeof(uint32);
  memcpy(&dependencies->ndeps, tmp, sizeof(uint32));
  tmp += sizeof(uint32);

  if (dependencies->magic != STATS_DEPS_MAGIC)
    elog(ERROR, "invalid dependency magic %d (expected %d)",
       dependencies->magic, STATS_DEPS_MAGIC);

  if (dependencies->type != STATS_DEPS_TYPE_BASIC)
    elog(ERROR, "invalid dependency type %d (expected %d)",
       dependencies->type, STATS_DEPS_TYPE_BASIC);

  if (dependencies->ndeps == 0)
    ereport(ERROR,
        (errcode(ERRCODE_DATA_CORRUPTED),
         errmsg("invalid zero-length item array in MVDependencies")));

  /* what minimum bytea size do we expect for those parameters */
  min_expected_size = SizeOfDependencies +
    dependencies->ndeps * (SizeOfDependency +
                 sizeof(AttrNumber) * 2);

  if (VARSIZE_ANY_EXHDR(data) < min_expected_size)
    elog(ERROR, "invalid dependencies size %zd (expected at least %zd)",
       VARSIZE_ANY_EXHDR(data), min_expected_size);

  /* allocate space for the MCV items */
  dependencies = repalloc(dependencies, offsetof(MVDependencies, deps)
              + (dependencies->ndeps * sizeof(MVDependency *)));

  for (i = 0; i < dependencies->ndeps; i++)
  {
    double    degree;
    AttrNumber  k;
    MVDependency *d;

    /* degree of validity */
    memcpy(&degree, tmp, sizeof(double));
    tmp += sizeof(double);

    /* number of attributes */
    memcpy(&k, tmp, sizeof(AttrNumber));
    tmp += sizeof(AttrNumber);

    /* is the number of attributes valid? */
    Assert((k >= 2) && (k <= STATS_MAX_DIMENSIONS));

    /* now that we know the number of attributes, allocate the dependency */
    d = (MVDependency *) palloc0(offsetof(MVDependency, attributes)
                   + (k * sizeof(AttrNumber)));

    d->degree = degree;
    d->nattributes = k;

    /* copy attribute numbers */
    memcpy(d->attributes, tmp, sizeof(AttrNumber) * d->nattributes);
    tmp += sizeof(AttrNumber) * d->nattributes;

    dependencies->deps[i] = d;

    /* still within the bytea */
    Assert(tmp <= ((char *) data + VARSIZE_ANY(data)));
  }

  /* we should have consumed the whole bytea exactly */
  Assert(tmp == ((char *) data + VARSIZE_ANY(data)));

  return dependencies;
}

/*
 * dependency_is_fully_matched
 *    checks that a functional dependency is fully matched given clauses on
 *    attributes (assuming the clauses are suitable equality clauses)
 */
static bool
dependency_is_fully_matched(MVDependency *dependency, Bitmapset *attnums)
{
  int     j;

  /*
   * Check that the dependency actually is fully covered by clauses. We have
   * to translate all attribute numbers, as those are referenced
   */
  for (j = 0; j < dependency->nattributes; j++)
  {
    int     attnum = dependency->attributes[j];

    if (!bms_is_member(attnum, attnums))
      return false;
  }

  return true;
}

/*
 * dependency_implies_attribute
 *    check that the attnum matches is implied by the functional dependency
 */
static bool
dependency_implies_attribute(MVDependency *dependency, AttrNumber attnum)
{
  if (attnum == dependency->attributes[dependency->nattributes - 1])
    return true;

  return false;
}

/*
 * statext_dependencies_load
 *    Load the functional dependencies for the indicated pg_statistic_ext tuple
 */
MVDependencies *
statext_dependencies_load(Oid mvoid)
{
  MVDependencies *result;
  bool    isnull;
  Datum   deps;
  HeapTuple htup;

  htup = SearchSysCache1(STATEXTOID, ObjectIdGetDatum(mvoid));
  if (!HeapTupleIsValid(htup))
    elog(ERROR, "cache lookup failed for statistics object %u", mvoid);

  deps = SysCacheGetAttr(STATEXTOID, htup,
               Anum_pg_statistic_ext_stxdependencies, &isnull);
  if (isnull)
    elog(ERROR,
       "requested statistic kind \"%c\" is not yet built for statistics object %u",
       STATS_EXT_DEPENDENCIES, mvoid);

  result = statext_dependencies_deserialize(DatumGetByteaPP(deps));

  ReleaseSysCache(htup);

  return result;
}

/*
 * pg_dependencies_in   - input routine for type pg_dependencies.
 *
 * pg_dependencies is real enough to be a table column, but it has no operations
 * of its own, and disallows input too
 */
Datum
pg_dependencies_in(PG_FUNCTION_ARGS)
{
  /*
   * pg_node_list stores the data in binary form and parsing text input is
   * not needed, so disallow this.
   */
  ereport(ERROR,
      (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
       errmsg("cannot accept a value of type %s", "pg_dependencies")));

  PG_RETURN_VOID();     /* keep compiler quiet */
}

/*
 * pg_dependencies    - output routine for type pg_dependencies.
 */
Datum
pg_dependencies_out(PG_FUNCTION_ARGS)
{
  bytea    *data = PG_GETARG_BYTEA_PP(0);
  MVDependencies *dependencies = statext_dependencies_deserialize(data);
  int     i,
        j;
  StringInfoData str;

  initStringInfo(&str);
  appendStringInfoChar(&str, '{');

  for (i = 0; i < dependencies->ndeps; i++)
  {
    MVDependency *dependency = dependencies->deps[i];

    if (i > 0)
      appendStringInfoString(&str, ", ");

    appendStringInfoChar(&str, '"');
    for (j = 0; j < dependency->nattributes; j++)
    {
      if (j == dependency->nattributes - 1)
        appendStringInfoString(&str, " => ");
      else if (j > 0)
        appendStringInfoString(&str, ", ");

      appendStringInfo(&str, "%d", dependency->attributes[j]);
    }
    appendStringInfo(&str, "\": %f", dependency->degree);
  }

  appendStringInfoChar(&str, '}');

  PG_RETURN_CSTRING(str.data);
}

/*
 * pg_dependencies_recv   - binary input routine for type pg_dependencies.
 */
Datum
pg_dependencies_recv(PG_FUNCTION_ARGS)
{
  ereport(ERROR,
      (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
       errmsg("cannot accept a value of type %s", "pg_dependencies")));

  PG_RETURN_VOID();     /* keep compiler quiet */
}

/*
 * pg_dependencies_send   - binary output routine for type pg_dependencies.
 *
 * Functional dependencies are serialized in a bytea value (although the type
 * is named differently), so let's just send that.
 */
Datum
pg_dependencies_send(PG_FUNCTION_ARGS)
{
  return byteasend(fcinfo);
}

/*
 * dependency_is_compatible_clause
 *    Determines if the clause is compatible with functional dependencies
 *
 * Only clauses that have the form of equality to a pseudoconstant, or can be
 * interpreted that way, are currently accepted.  Furthermore the variable
 * part of the clause must be a simple Var belonging to the specified
 * relation, whose attribute number we return in *attnum on success.
 */
static bool
dependency_is_compatible_clause(Node *clause, Index relid, AttrNumber *attnum)
{
  RestrictInfo *rinfo = (RestrictInfo *) clause;
  Var      *var;

  if (!IsA(rinfo, RestrictInfo))
    return false;

  /* Pseudoconstants are not interesting (they couldn't contain a Var) */
  if (rinfo->pseudoconstant)
    return false;

  /* Clauses referencing multiple, or no, varnos are incompatible */
  if (bms_membership(rinfo->clause_relids) != BMS_SINGLETON)
    return false;

  if (is_opclause(rinfo->clause))
  {
    /* If it's an opclause, check for Var = Const or Const = Var. */
    OpExpr     *expr = (OpExpr *) rinfo->clause;

    /* Only expressions with two arguments are candidates. */
    if (list_length(expr->args) != 2)
      return false;

    /* Make sure non-selected argument is a pseudoconstant. */
    if (is_pseudo_constant_clause(lsecond(expr->args)))
      var = linitial(expr->args);
    else if (is_pseudo_constant_clause(linitial(expr->args)))
      var = lsecond(expr->args);
    else
      return false;

    /*
     * If it's not an "=" operator, just ignore the clause, as it's not
     * compatible with functional dependencies.
     *
     * This uses the function for estimating selectivity, not the operator
     * directly (a bit awkward, but well ...).
     *
     * XXX this is pretty dubious; probably it'd be better to check btree
     * or hash opclass membership, so as not to be fooled by custom
     * selectivity functions, and to be more consistent with decisions
     * elsewhere in the planner.
     */
    if (get_oprrest(expr->opno) != F_EQSEL)
      return false;

    /* OK to proceed with checking "var" */
  }
  else if (not_clause((Node *) rinfo->clause))
  {
    /*
     * "NOT x" can be interpreted as "x = false", so get the argument and
     * proceed with seeing if it's a suitable Var.
     */
    var = (Var *) get_notclausearg(rinfo->clause);
  }
  else
  {
    /*
     * A boolean expression "x" can be interpreted as "x = true", so
     * proceed with seeing if it's a suitable Var.
     */
    var = (Var *) rinfo->clause;
  }

  /*
   * We may ignore any RelabelType node above the operand.  (There won't be
   * more than one, since eval_const_expressions has been applied already.)
   */
  if (IsA(var, RelabelType))
    var = (Var *) ((RelabelType *) var)->arg;

  /* We only support plain Vars for now */
  if (!IsA(var, Var))
    return false;

  /* Ensure Var is from the correct relation */
  if (var->varno != relid)
    return false;

  /* We also better ensure the Var is from the current level */
  if (var->varlevelsup != 0)
    return false;

  /* Also ignore system attributes (we don't allow stats on those) */
  if (!AttrNumberIsForUserDefinedAttr(var->varattno))
    return false;

  *attnum = var->varattno;
  return true;
}

/*
 * find_strongest_dependency
 *    find the strongest dependency on the attributes
 *
 * When applying functional dependencies, we start with the strongest
 * dependencies. That is, we select the dependency that:
 *
 * (a) has all attributes covered by equality clauses
 *
 * (b) has the most attributes
 *
 * (c) has the highest degree of validity
 *
 * This guarantees that we eliminate the most redundant conditions first
 * (see the comment in dependencies_clauselist_selectivity).
 */
static MVDependency *
find_strongest_dependency(StatisticExtInfo *stats, MVDependencies *dependencies,
              Bitmapset *attnums)
{
  int     i;
  MVDependency *strongest = NULL;

  /* number of attnums in clauses */
  int     nattnums = bms_num_members(attnums);

  /*
   * Iterate over the MVDependency items and find the strongest one from the
   * fully-matched dependencies. We do the cheap checks first, before
   * matching it against the attnums.
   */
  for (i = 0; i < dependencies->ndeps; i++)
  {
    MVDependency *dependency = dependencies->deps[i];

    /*
     * Skip dependencies referencing more attributes than available
     * clauses, as those can't be fully matched.
     */
    if (dependency->nattributes > nattnums)
      continue;

    if (strongest)
    {
      /* skip dependencies on fewer attributes than the strongest. */
      if (dependency->nattributes < strongest->nattributes)
        continue;

      /* also skip weaker dependencies when attribute count matches */
      if (strongest->nattributes == dependency->nattributes &&
        strongest->degree > dependency->degree)
        continue;
    }

    /*
     * this dependency is stronger, but we must still check that it's
     * fully matched to these attnums. We perform this check last as it's
     * slightly more expensive than the previous checks.
     */
    if (dependency_is_fully_matched(dependency, attnums))
      strongest = dependency; /* save new best match */
  }

  return strongest;
}

/*
 * dependencies_clauselist_selectivity
 *    Return the estimated selectivity of (a subset of) the given clauses
 *    using functional dependency statistics, or 1.0 if no useful functional
 *    dependency statistic exists.
 *
 * 'estimatedclauses' is an output argument that gets a bit set corresponding
 * to the (zero-based) list index of each clause that is included in the
 * estimated selectivity.
 *
 * Given equality clauses on attributes (a,b) we find the strongest dependency
 * between them, i.e. either (a=>b) or (b=>a). Assuming (a=>b) is the selected
 * dependency, we then combine the per-clause selectivities using the formula
 *
 *     P(a,b) = P(a) * [f + (1-f)*P(b)]
 *
 * where 'f' is the degree of the dependency.
 *
 * With clauses on more than two attributes, the dependencies are applied
 * recursively, starting with the widest/strongest dependencies. For example
 * P(a,b,c) is first split like this:
 *
 *     P(a,b,c) = P(a,b) * [f + (1-f)*P(c)]
 *
 * assuming (a,b=>c) is the strongest dependency.
 */
Selectivity
dependencies_clauselist_selectivity(PlannerInfo *root,
                  List *clauses,
                  int varRelid,
                  JoinType jointype,
                  SpecialJoinInfo *sjinfo,
                  RelOptInfo *rel,
                  Bitmapset **estimatedclauses)
{
  Selectivity s1 = 1.0;
  ListCell   *l;
  Bitmapset  *clauses_attnums = NULL;
  StatisticExtInfo *stat;
  MVDependencies *dependencies;
  AttrNumber *list_attnums;
  int     listidx;

  /* initialize output argument */
  *estimatedclauses = NULL;

  /* check if there's any stats that might be useful for us. */
  if (!has_stats_of_kind(rel->statlist, STATS_EXT_DEPENDENCIES))
    return 1.0;

  list_attnums = (AttrNumber *) palloc(sizeof(AttrNumber) *
                     list_length(clauses));

  /*
   * Pre-process the clauses list to extract the attnums seen in each item.
   * We need to determine if there's any clauses which will be useful for
   * dependency selectivity estimations. Along the way we'll record all of
   * the attnums for each clause in a list which we'll reference later so we
   * don't need to repeat the same work again. We'll also keep track of all
   * attnums seen.
   */
  listidx = 0;
  foreach(l, clauses)
  {
    Node     *clause = (Node *) lfirst(l);
    AttrNumber  attnum;

    if (dependency_is_compatible_clause(clause, rel->relid, &attnum))
    {
      list_attnums[listidx] = attnum;
      clauses_attnums = bms_add_member(clauses_attnums, attnum);
    }
    else
      list_attnums[listidx] = InvalidAttrNumber;

    listidx++;
  }

  /*
   * If there's not at least two distinct attnums then reject the whole list
   * of clauses. We must return 1.0 so the calling function's selectivity is
   * unaffected.
   */
  if (bms_num_members(clauses_attnums) < 2)
  {
    pfree(list_attnums);
    return 1.0;
  }

  /* find the best suited statistics object for these attnums */
  stat = choose_best_statistics(rel->statlist, clauses_attnums,
                  STATS_EXT_DEPENDENCIES);

  /* if no matching stats could be found then we've nothing to do */
  if (!stat)
  {
    pfree(list_attnums);
    return 1.0;
  }

  /* load the dependency items stored in the statistics object */
  dependencies = statext_dependencies_load(stat->statOid);

  /*
   * Apply the dependencies recursively, starting with the widest/strongest
   * ones, and proceeding to the smaller/weaker ones. At the end of each
   * round we factor in the selectivity of clauses on the implied attribute,
   * and remove the clauses from the list.
   */
  while (true)
  {
    Selectivity s2 = 1.0;
    MVDependency *dependency;

    /* the widest/strongest dependency, fully matched by clauses */
    dependency = find_strongest_dependency(stat, dependencies,
                         clauses_attnums);

    /* if no suitable dependency was found, we're done */
    if (!dependency)
      break;

    /*
     * We found an applicable dependency, so find all the clauses on the
     * implied attribute - with dependency (a,b => c) we look for clauses
     * on 'c'.
     */
    listidx = -1;
    foreach(l, clauses)
    {
      Node     *clause;

      listidx++;

      /*
       * Skip incompatible clauses, and ones we've already estimated on.
       */
      if (list_attnums[listidx] == InvalidAttrNumber ||
        bms_is_member(listidx, *estimatedclauses))
        continue;

      /*
       * Technically we could find more than one clause for a given
       * attnum. Since these clauses must be equality clauses, we choose
       * to only take the selectivity estimate from the final clause in
       * the list for this attnum. If the attnum happens to be compared
       * to a different Const in another clause then no rows will match
       * anyway. If it happens to be compared to the same Const, then
       * ignoring the additional clause is just the thing to do.
       */
      if (dependency_implies_attribute(dependency,
                       list_attnums[listidx]))
      {
        clause = (Node *) lfirst(l);

        s2 = clause_selectivity(root, clause, varRelid, jointype,
                    sjinfo);

        /* mark this one as done, so we don't touch it again. */
        *estimatedclauses = bms_add_member(*estimatedclauses, listidx);

        /*
         * Mark that we've got and used the dependency on this clause.
         * We'll want to ignore this when looking for the next
         * strongest dependency above.
         */
        clauses_attnums = bms_del_member(clauses_attnums,
                         list_attnums[listidx]);
      }
    }

    /*
     * Now factor in the selectivity for all the "implied" clauses into
     * the final one, using this formula:
     *
     * P(a,b) = P(a) * (f + (1-f) * P(b))
     *
     * where 'f' is the degree of validity of the dependency.
     */
    s1 *= (dependency->degree + (1 - dependency->degree) * s2);
  }

  pfree(dependencies);
  pfree(list_attnums);

  return s1;
}

YugabyteDB (2.13.0.0-b42, bfc6a6643e7399ac8a0e81d06a3ee6d6571b33ab)

Coverage Report

Created: 2022-03-09 17:30