From 7300a699502fe5432b05fbc75baca534b080bebb Mon Sep 17 00:00:00 2001 From: Tomas Vondra Date: Wed, 27 Mar 2019 18:32:18 +0100 Subject: Add support for multivariate MCV lists Introduce a third extended statistic type, supported by the CREATE STATISTICS command - MCV lists, a generalization of the statistic already built and used for individual columns. Compared to the already supported types (n-distinct coefficients and functional dependencies), MCV lists are more complex, include column values and allow estimation of much wider range of common clauses (equality and inequality conditions, IS NULL, IS NOT NULL etc.). Similarly to the other types, a new pseudo-type (pg_mcv_list) is used. Author: Tomas Vondra Reviewed-by: Dean Rasheed, David Rowley, Mark Dilger, Alvaro Herrera Discussion: https://postgr.es/m/dfdac334-9cf2-2597-fb27-f0fb3753f435@2ndquadrant.com --- src/backend/nodes/bitmapset.c | 44 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) (limited to 'src/backend/nodes/bitmapset.c') diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c index 07e6f03a871..4ad17d0c31e 100644 --- a/src/backend/nodes/bitmapset.c +++ b/src/backend/nodes/bitmapset.c @@ -443,6 +443,50 @@ bms_is_member(int x, const Bitmapset *a) return false; } +/* + * bms_member_index + * determine 0-based index of member x in the bitmap + * + * Returns (-1) when x is not a member. + */ +int +bms_member_index(Bitmapset *a, int x) +{ + int i; + int bitnum; + int wordnum; + int result = 0; + bitmapword mask; + + /* return -1 if not a member of the bitmap */ + if (!bms_is_member(x, a)) + return -1; + + wordnum = WORDNUM(x); + bitnum = BITNUM(x); + + /* count bits in preceding words */ + for (i = 0; i < wordnum; i++) + { + bitmapword w = a->words[i]; + + /* No need to count the bits in a zero word */ + if (w != 0) + result += bmw_popcount(w); + } + + /* + * Now add bits of the last word, but only those before the item. + * We can do that by applying a mask and then using popcount again. + * To get 0-based index, we want to count only preceding bits, not + * the item itself, so we subtract 1. + */ + mask = ((bitmapword) 1 << bitnum) - 1; + result += bmw_popcount(a->words[wordnum] & mask); + + return result; +} + /* * bms_overlap - do sets overlap (ie, have a nonempty intersection)? */ -- cgit v1.2.3