Bitmap-based count distinct query rewrite in a relational SQL algebra

One or more non-transitory computer-readable media storing instructions that, when executed by one or more computing devices, cause:

• storing, in a materialized view:
• bitmap data that represents a bitmap,
• wherein the bitmap corresponds to a particular expression,
• wherein the particular expression has a set of possible distinct values,
• wherein each bit in the bitmap represents a respective value of the set of possible distinct values,
• wherein the bitmap data comprises a plurality of sets of bits representing at least a particular portion of the bitmap, and
• wherein each set of bits, of the plurality of sets of bits:
• corresponds to a corresponding grouping key value, of a particular grouping key, that exists in a particular set of data,
• comprises bits, set to a first value, that correspond to values, of the set of possible distinct values of the particular expression, that exist in the particular set of data in association with the corresponding grouping key value,
• wherein bits, in said each set of bits, that correspond to values, of the set of possible distinct values of the particular expression, that do not exist, in association with the corresponding grouping key value, in the particular set of data are set to a second value that is different than the first value,
• receiving a query with a particular count distinct operation that requests a number of distinct values, of the particular expression, in the particular set of data;
• in response to receiving the query, a database server rewriting the query to produce a rewritten query that is configured to compute the number of distinct values based, at least in part, on the bitmap data of the materialized view;
• and
• the database server executing the rewritten query to compute the requested number of distinct values based, at least in part, on the bitmap data of the materialized view by:
• aggregating at least two sets of bits, of the plurality of sets of bits, to produce an aggregate set of bits, and
• counting bits in the aggregate set of bits that are set to the first value.