Functions used to work with (approximate) count distinct sets. More...

#include "Descriptors/CountDistinctDescriptor.h"
#include "HyperLogLog.h"
#include "ThirdParty/robin_hood/robin_hood.h"
#include <bitset>
#include <vector>

Include dependency graph for CountDistinct.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
using	CountDistinctDescriptors = std::vector< CountDistinctDescriptor >

using	CountDistinctSet = robin_hood::unordered_set< int64_t >

Functions
size_t	bitmap_set_size (const int8_t *bitmap, const size_t bitmap_byte_sz)

void	bitmap_set_union (int8_t lhs, int8_t rhs, const size_t bitmap_sz)

void	partial_bitmap_union (int8_t *set_vals, const CountDistinctDescriptor &count_distinct_desc)

int64_t	count_distinct_set_size (const int64_t set_handle, const CountDistinctDescriptor &count_distinct_desc)

void	count_distinct_set_union (const int64_t new_set_handle, const int64_t old_set_handle, const CountDistinctDescriptor &new_count_distinct_desc, const CountDistinctDescriptor &old_count_distinct_desc)

Detailed Description

Functions used to work with (approximate) count distinct sets.

Definition in file CountDistinct.h.

Typedef Documentation

using CountDistinctDescriptors = std::vector<CountDistinctDescriptor>

Definition at line 34 of file CountDistinct.h.

using CountDistinctSet = robin_hood::unordered_set<int64_t>

Definition at line 35 of file CountDistinct.h.

Function Documentation

size_t bitmap_set_size	(	const int8_t *	bitmap,
		const size_t	bitmap_byte_sz
	)

inline

Definition at line 37 of file CountDistinct.h.

Referenced by count_distinct_set_size(), and ResultSet::getNDVEstimator().

                                                                                  {
   const auto bitmap_word_count = bitmap_byte_sz >> 3;
   const auto bitmap_rem_bytes = bitmap_byte_sz & 7;
   const auto bitmap64 = reinterpret_cast<const int64_t*>(bitmap);
   size_t set_size = 0;
   for (size_t i = 0; i < bitmap_word_count; ++i) {
     std::bitset<64> word_bitset(bitmap64[i]);
     set_size += word_bitset.count();
   }
   const auto rem_bitmap = reinterpret_cast<const int8_t*>(&bitmap64[bitmap_word_count]);
   for (size_t i = 0; i < bitmap_rem_bytes; ++i) {
     std::bitset<8> byte_bitset(rem_bitmap[i]);
     set_size += byte_bitset.count();
   }
   return set_size;
 }

Here is the caller graph for this function:

void bitmap_set_union	(	int8_t *	lhs,
		int8_t *	rhs,
		const size_t	bitmap_sz
	)

inline

Definition at line 54 of file CountDistinct.h.

Referenced by count_distinct_set_union(), and partial_bitmap_union().

                                                                                {
   for (size_t i = 0; i < bitmap_sz; ++i) {
     lhs[i] = rhs[i] = lhs[i] | rhs[i];
   }
 }

Here is the caller graph for this function:

int64_t count_distinct_set_size	(	const int64_t	set_handle,
		const CountDistinctDescriptor &	count_distinct_desc
	)

inline

Definition at line 75 of file CountDistinct.h.

References CountDistinctDescriptor::approximate, Bitmap, bitmap_set_size(), CountDistinctDescriptor::bitmap_sz_bits, CountDistinctDescriptor::bitmapSizeBytes(), CHECK, CHECK_GT, CountDistinctDescriptor::device_type, GPU, hll_size(), CountDistinctDescriptor::impl_type_, partial_bitmap_union(), CountDistinctDescriptor::sub_bitmap_count, and UnorderedSet.

Referenced by ResultSet::makeTargetValue(), ResultSet::ResultSetComparator< BUFFER_ITERATOR_TYPE >::materializeCountDistinctColumn(), and ResultSetStorage::reduceSingleRow().

                                                         {
   if (!set_handle) {
     return 0;
   }
   if (count_distinct_desc.impl_type_ == CountDistinctImplType::Bitmap) {
     auto set_vals = reinterpret_cast<int8_t*>(set_handle);
     if (count_distinct_desc.approximate) {
       CHECK_GT(count_distinct_desc.bitmap_sz_bits, 0);
       return count_distinct_desc.device_type == ExecutorDeviceType::GPU
                  ? hll_size(reinterpret_cast<const int32_t*>(set_vals),
                             count_distinct_desc.bitmap_sz_bits)
                  : hll_size(reinterpret_cast<const int8_t*>(set_vals),
                             count_distinct_desc.bitmap_sz_bits);
     }
     if (count_distinct_desc.sub_bitmap_count > 1) {
       partial_bitmap_union(set_vals, count_distinct_desc);
     }
     return bitmap_set_size(set_vals, count_distinct_desc.bitmapSizeBytes());
   }
   CHECK(count_distinct_desc.impl_type_ == CountDistinctImplType::UnorderedSet);
   return reinterpret_cast<CountDistinctSet*>(set_handle)->size();
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void count_distinct_set_union	(	const int64_t	new_set_handle,
		const int64_t	old_set_handle,
		const CountDistinctDescriptor &	new_count_distinct_desc,
		const CountDistinctDescriptor &	old_count_distinct_desc
	)

inline

Definition at line 100 of file CountDistinct.h.

References CountDistinctDescriptor::approximate, Bitmap, bitmap_set_union(), CountDistinctDescriptor::bitmap_sz_bits, CountDistinctDescriptor::bitmapPaddedSizeBytes(), CountDistinctDescriptor::bitmapSizeBytes(), CHECK, CHECK_EQ, CHECK_GE, CPU, CountDistinctDescriptor::device_type, GPU, hll_unify(), CountDistinctDescriptor::impl_type_, CountDistinctDescriptor::sub_bitmap_count, and UnorderedSet.

Referenced by count_distinct_set_union_jit_rt(), and ResultSetStorage::reduceOneCountDistinctSlot().

                                                             {
   if (new_count_distinct_desc.impl_type_ == CountDistinctImplType::Bitmap) {
     auto new_set = reinterpret_cast<int8_t*>(new_set_handle);
     auto old_set = reinterpret_cast<int8_t*>(old_set_handle);
     if (new_count_distinct_desc.approximate) {
       CHECK(old_count_distinct_desc.approximate);
       if (new_count_distinct_desc.device_type == ExecutorDeviceType::GPU &&
           old_count_distinct_desc.device_type == ExecutorDeviceType::GPU) {
         hll_unify(reinterpret_cast<int32_t*>(new_set),
                   reinterpret_cast<int32_t*>(old_set),
                   size_t(1) << old_count_distinct_desc.bitmap_sz_bits);
       } else if (new_count_distinct_desc.device_type == ExecutorDeviceType::GPU &&
                  old_count_distinct_desc.device_type == ExecutorDeviceType::CPU) {
         hll_unify(reinterpret_cast<int32_t*>(new_set),
                   reinterpret_cast<int8_t*>(old_set),
                   size_t(1) << old_count_distinct_desc.bitmap_sz_bits);
       } else if (new_count_distinct_desc.device_type == ExecutorDeviceType::CPU &&
                  old_count_distinct_desc.device_type == ExecutorDeviceType::GPU) {
         hll_unify(reinterpret_cast<int8_t*>(new_set),
                   reinterpret_cast<int32_t*>(old_set),
                   size_t(1) << old_count_distinct_desc.bitmap_sz_bits);
       } else {
         CHECK(old_count_distinct_desc.device_type == ExecutorDeviceType::CPU &&
               new_count_distinct_desc.device_type == ExecutorDeviceType::CPU);
         hll_unify(reinterpret_cast<int8_t*>(new_set),
                   reinterpret_cast<int8_t*>(old_set),
                   size_t(1) << old_count_distinct_desc.bitmap_sz_bits);
       }
     } else {
       CHECK_EQ(new_count_distinct_desc.sub_bitmap_count,
                old_count_distinct_desc.sub_bitmap_count);
       CHECK_GE(old_count_distinct_desc.sub_bitmap_count, size_t(1));
       // NB: For low cardinality input and if the query ran on GPU the bitmap is
       // composed of multiple padded sub-bitmaps. Treat them as if they are regular
       // bitmaps and let count_distinct_set_size take care of additional reduction.
       const auto bitmap_byte_sz = old_count_distinct_desc.sub_bitmap_count == 1
                                       ? old_count_distinct_desc.bitmapSizeBytes()
                                       : old_count_distinct_desc.bitmapPaddedSizeBytes();
       bitmap_set_union(new_set, old_set, bitmap_byte_sz);
     }
   } else {
     CHECK(old_count_distinct_desc.impl_type_ == CountDistinctImplType::UnorderedSet);
     auto old_set = reinterpret_cast<CountDistinctSet*>(old_set_handle);
     auto new_set = reinterpret_cast<CountDistinctSet*>(new_set_handle);
     new_set->insert(old_set->begin(), old_set->end());
     old_set->insert(new_set->begin(), new_set->end());
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void partial_bitmap_union	(	int8_t *	set_vals,
		const CountDistinctDescriptor &	count_distinct_desc
	)

inline

Definition at line 61 of file CountDistinct.h.

References bitmap_set_union(), CountDistinctDescriptor::bitmapPaddedSizeBytes(), CountDistinctDescriptor::bitmapSizeBytes(), CHECK_EQ, and CountDistinctDescriptor::sub_bitmap_count.

Referenced by count_distinct_set_size().

                                                                                      {
   auto partial_set_vals = set_vals;
   CHECK_EQ(
       size_t(0),
       count_distinct_desc.bitmapPaddedSizeBytes() % count_distinct_desc.sub_bitmap_count);
   const auto partial_padded_size =
       count_distinct_desc.bitmapPaddedSizeBytes() / count_distinct_desc.sub_bitmap_count;
   for (size_t i = 1; i < count_distinct_desc.sub_bitmap_count; ++i) {
     partial_set_vals += partial_padded_size;
     bitmap_set_union(set_vals, partial_set_vals, count_distinct_desc.bitmapSizeBytes());
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation