33 #include "utils/fmgrprotos.h"
39 int k,
int *combination);
45 #define SizeOfHeader (3 * sizeof(uint32))
48 #define SizeOfItem(natts) \
49 (sizeof(double) + sizeof(int) + (natts) * sizeof(AttrNumber))
52 #define MinSizeOfItem SizeOfItem(2)
55 #define MinSizeOfItems(nitems) \
56 (SizeOfHeader + (nitems) * MinSizeOfItem)
93 int numattrs =
data->nattnums;
100 result->
nitems = numcombs;
103 for (k = 2; k <= numattrs; k++)
120 for (
j = 0;
j < k;
j++)
158 elog(
ERROR,
"cache lookup failed for statistics object %u", mvoid);
161 Anum_pg_statistic_ext_data_stxdndistinct, &isnull);
164 "requested statistics kind \"%c\" is not yet built for statistics object %u",
165 STATS_EXT_NDISTINCT, mvoid);
214 memcpy(tmp, &ndistinct->
type,
sizeof(
uint32));
227 memcpy(tmp, &item.
ndistinct,
sizeof(
double));
228 tmp +=
sizeof(double);
229 memcpy(tmp, &nmembers,
sizeof(
int));
263 elog(
ERROR,
"invalid MVNDistinct size %zu (expected at least %zu)",
278 elog(
ERROR,
"invalid ndistinct magic %08x (expected %08x)",
281 elog(
ERROR,
"invalid ndistinct type %d (expected %d)",
284 elog(
ERROR,
"invalid zero-length item array in MVNDistinct");
289 elog(
ERROR,
"invalid MVNDistinct size %zu (expected at least %zu)",
307 memcpy(&item->
ndistinct, tmp,
sizeof(
double));
308 tmp +=
sizeof(double);
342 (
errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
343 errmsg(
"cannot accept a value of type %s",
"pg_ndistinct")));
395 (
errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
396 errmsg(
"cannot accept a value of type %s",
"pg_ndistinct")));
426 int k,
int *combination)
437 int numrows =
data->numrows;
449 isnull = (
bool *)
palloc0(
sizeof(
bool) * numrows * k);
451 for (
i = 0;
i < numrows;
i++)
454 items[
i].isnull = &isnull[
i * k];
464 for (
i = 0;
i < k;
i++)
476 elog(
ERROR,
"cache lookup failed for ordering operator for type %u",
483 for (
j = 0;
j < numrows;
j++)
499 for (
i = 1;
i < numrows;
i++)
527 numer = (double) numrows * (
double) d;
529 denom = (double) (numrows -
f1) +
530 (double)
f1 * (
double) numrows / totalrows;
532 ndistinct = numer / denom;
535 if (ndistinct < (
double) d)
536 ndistinct = (
double) d;
538 if (ndistinct > totalrows)
539 ndistinct = totalrows;
541 return floor(ndistinct + 0.5);
555 Assert((k > 0) && (n >= k));
561 for (d = 1; d <= k; ++d)
577 return (1 << n) - (n + 1);
593 Assert((n >= k) && (k > 0));
601 state->combinations = (
int *)
palloc(
sizeof(
int) * k *
state->ncombinations);
682 current,
state->k *
sizeof(
int));
#define AttributeNumberIsValid(attributeNumber)
static Datum values[MAXATTR]
#define Assert(condition)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
int multi_sort_compare(const void *a, const void *b, void *arg)
MultiSortSupport multi_sort_init(int ndims)
void multi_sort_add_dimension(MultiSortSupport mss, int sortdim, Oid oper, Oid collation)
#define PG_GETARG_BYTEA_PP(n)
#define DatumGetByteaPP(X)
#define PG_RETURN_CSTRING(x)
#define HeapTupleIsValid(tuple)
void pfree(void *pointer)
void * palloc0(Size size)
Datum pg_ndistinct_out(PG_FUNCTION_ARGS)
MVNDistinct * statext_ndistinct_load(Oid mvoid, bool inh)
static int n_choose_k(int n, int k)
Datum pg_ndistinct_in(PG_FUNCTION_ARGS)
struct CombinationGenerator CombinationGenerator
static double estimate_ndistinct(double totalrows, int numrows, int d, int f1)
bytea * statext_ndistinct_serialize(MVNDistinct *ndistinct)
static void generate_combinations_recurse(CombinationGenerator *state, int index, int start, int *current)
Datum pg_ndistinct_recv(PG_FUNCTION_ARGS)
static double ndistinct_for_combination(double totalrows, StatsBuildData *data, int k, int *combination)
MVNDistinct * statext_ndistinct_deserialize(bytea *data)
static void generate_combinations(CombinationGenerator *state)
static int num_combinations(int n)
MVNDistinct * statext_ndistinct_build(double totalrows, StatsBuildData *data)
#define SizeOfItem(natts)
static void generator_free(CombinationGenerator *state)
static CombinationGenerator * generator_init(int n, int k)
Datum pg_ndistinct_send(PG_FUNCTION_ARGS)
#define MinSizeOfItems(nitems)
static int * generator_next(CombinationGenerator *state)
void qsort_interruptible(void *base, size_t nel, size_t elsize, qsort_arg_comparator cmp, void *arg)
static Datum BoolGetDatum(bool X)
static Datum ObjectIdGetDatum(Oid X)
#define STATS_NDISTINCT_MAGIC
#define STATS_NDISTINCT_TYPE_BASIC
#define STATS_MAX_DIMENSIONS
void appendStringInfo(StringInfo str, const char *fmt,...)
void appendStringInfoString(StringInfo str, const char *s)
void appendStringInfoChar(StringInfo str, char ch)
void initStringInfo(StringInfo str)
MVNDistinctItem items[FLEXIBLE_ARRAY_MEMBER]
void ReleaseSysCache(HeapTuple tuple)
Datum SysCacheGetAttr(int cacheId, HeapTuple tup, AttrNumber attributeNumber, bool *isNull)
HeapTuple SearchSysCache2(int cacheId, Datum key1, Datum key2)
TypeCacheEntry * lookup_type_cache(Oid type_id, int flags)
#define SET_VARSIZE(PTR, len)
#define VARSIZE_ANY_EXHDR(PTR)
Datum byteasend(PG_FUNCTION_ARGS)