OmniSciDB  1dac507f6e
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
CountDistinct.h
Go to the documentation of this file.
1 /*
2  * Copyright 2017 MapD Technologies, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
25 #ifndef QUERYENGINE_COUNTDISTINCT_H
26 #define QUERYENGINE_COUNTDISTINCT_H
27 
29 #include "HyperLogLog.h"
30 
31 #include <bitset>
32 #include <set>
33 #include <vector>
34 
35 using CountDistinctDescriptors = std::vector<CountDistinctDescriptor>;
36 
37 inline size_t bitmap_set_size(const int8_t* bitmap, const size_t bitmap_byte_sz) {
38  const auto bitmap_word_count = bitmap_byte_sz >> 3;
39  const auto bitmap_rem_bytes = bitmap_byte_sz & 7;
40  const auto bitmap64 = reinterpret_cast<const int64_t*>(bitmap);
41  size_t set_size = 0;
42  for (size_t i = 0; i < bitmap_word_count; ++i) {
43  std::bitset<64> word_bitset(bitmap64[i]);
44  set_size += word_bitset.count();
45  }
46  const auto rem_bitmap = reinterpret_cast<const int8_t*>(&bitmap64[bitmap_word_count]);
47  for (size_t i = 0; i < bitmap_rem_bytes; ++i) {
48  std::bitset<8> byte_bitset(rem_bitmap[i]);
49  set_size += byte_bitset.count();
50  }
51  return set_size;
52 }
53 
54 inline void bitmap_set_union(int8_t* lhs, int8_t* rhs, const size_t bitmap_sz) {
55  for (size_t i = 0; i < bitmap_sz; ++i) {
56  lhs[i] = rhs[i] = lhs[i] | rhs[i];
57  }
58 }
59 
60 // Bring all the set bits in the multiple sub-bitmaps into the first sub-bitmap.
61 inline void partial_bitmap_union(int8_t* set_vals,
62  const CountDistinctDescriptor& count_distinct_desc) {
63  auto partial_set_vals = set_vals;
64  CHECK_EQ(
65  size_t(0),
66  count_distinct_desc.bitmapPaddedSizeBytes() % count_distinct_desc.sub_bitmap_count);
67  const auto partial_padded_size =
68  count_distinct_desc.bitmapPaddedSizeBytes() / count_distinct_desc.sub_bitmap_count;
69  for (size_t i = 1; i < count_distinct_desc.sub_bitmap_count; ++i) {
70  partial_set_vals += partial_padded_size;
71  bitmap_set_union(set_vals, partial_set_vals, count_distinct_desc.bitmapSizeBytes());
72  }
73 }
74 
75 inline int64_t count_distinct_set_size(
76  const int64_t set_handle,
77  const CountDistinctDescriptor& count_distinct_desc) {
78  if (!set_handle) {
79  return 0;
80  }
81  if (count_distinct_desc.impl_type_ == CountDistinctImplType::Bitmap) {
82  auto set_vals = reinterpret_cast<int8_t*>(set_handle);
83  if (count_distinct_desc.approximate) {
84  CHECK_GT(count_distinct_desc.bitmap_sz_bits, 0);
85  return count_distinct_desc.device_type == ExecutorDeviceType::GPU
86  ? hll_size(reinterpret_cast<const int32_t*>(set_vals),
87  count_distinct_desc.bitmap_sz_bits)
88  : hll_size(reinterpret_cast<const int8_t*>(set_vals),
89  count_distinct_desc.bitmap_sz_bits);
90  }
91  if (count_distinct_desc.sub_bitmap_count > 1) {
92  partial_bitmap_union(set_vals, count_distinct_desc);
93  }
94  return bitmap_set_size(set_vals, count_distinct_desc.bitmapSizeBytes());
95  }
96  CHECK(count_distinct_desc.impl_type_ == CountDistinctImplType::StdSet);
97  return reinterpret_cast<std::set<int64_t>*>(set_handle)->size();
98 }
99 
101  const int64_t new_set_handle,
102  const int64_t old_set_handle,
103  const CountDistinctDescriptor& new_count_distinct_desc,
104  const CountDistinctDescriptor& old_count_distinct_desc) {
105  if (new_count_distinct_desc.impl_type_ == CountDistinctImplType::Bitmap) {
106  auto new_set = reinterpret_cast<int8_t*>(new_set_handle);
107  auto old_set = reinterpret_cast<int8_t*>(old_set_handle);
108  if (new_count_distinct_desc.approximate) {
109  CHECK(old_count_distinct_desc.approximate);
110  if (new_count_distinct_desc.device_type == ExecutorDeviceType::GPU &&
111  old_count_distinct_desc.device_type == ExecutorDeviceType::GPU) {
112  hll_unify(reinterpret_cast<int32_t*>(new_set),
113  reinterpret_cast<int32_t*>(old_set),
114  1 << old_count_distinct_desc.bitmap_sz_bits);
115  } else if (new_count_distinct_desc.device_type == ExecutorDeviceType::GPU &&
116  old_count_distinct_desc.device_type == ExecutorDeviceType::CPU) {
117  hll_unify(reinterpret_cast<int32_t*>(new_set),
118  reinterpret_cast<int8_t*>(old_set),
119  1 << old_count_distinct_desc.bitmap_sz_bits);
120  } else if (new_count_distinct_desc.device_type == ExecutorDeviceType::CPU &&
121  old_count_distinct_desc.device_type == ExecutorDeviceType::GPU) {
122  hll_unify(reinterpret_cast<int8_t*>(new_set),
123  reinterpret_cast<int32_t*>(old_set),
124  1 << old_count_distinct_desc.bitmap_sz_bits);
125  } else {
126  CHECK(old_count_distinct_desc.device_type == ExecutorDeviceType::CPU &&
127  new_count_distinct_desc.device_type == ExecutorDeviceType::CPU);
128  hll_unify(reinterpret_cast<int8_t*>(new_set),
129  reinterpret_cast<int8_t*>(old_set),
130  1 << old_count_distinct_desc.bitmap_sz_bits);
131  }
132  } else {
133  CHECK_EQ(new_count_distinct_desc.sub_bitmap_count,
134  old_count_distinct_desc.sub_bitmap_count);
135  CHECK_GE(old_count_distinct_desc.sub_bitmap_count, size_t(1));
136  // NB: For low cardinality input and if the query ran on GPU the bitmap is
137  // composed of multiple padded sub-bitmaps. Treat them as if they are regular
138  // bitmaps and let count_distinct_set_size take care of additional reduction.
139  const auto bitmap_byte_sz = old_count_distinct_desc.sub_bitmap_count == 1
140  ? old_count_distinct_desc.bitmapSizeBytes()
141  : old_count_distinct_desc.bitmapPaddedSizeBytes();
142  bitmap_set_union(new_set, old_set, bitmap_byte_sz);
143  }
144  } else {
145  CHECK(old_count_distinct_desc.impl_type_ == CountDistinctImplType::StdSet);
146  auto old_set = reinterpret_cast<std::set<int64_t>*>(old_set_handle);
147  auto new_set = reinterpret_cast<std::set<int64_t>*>(new_set_handle);
148  new_set->insert(old_set->begin(), old_set->end());
149  old_set->insert(new_set->begin(), new_set->end());
150  }
151 }
152 
153 #endif
#define CHECK_EQ(x, y)
Definition: Logger.h:198
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)
Descriptor for the storage layout use for (approximate) count distinct operations.
void hll_unify(T1 *lhs, T2 *rhs, const size_t m)
Definition: HyperLogLog.h:109
#define CHECK_GE(x, y)
Definition: Logger.h:203
void bitmap_set_union(int8_t *lhs, int8_t *rhs, const size_t bitmap_sz)
Definition: CountDistinct.h:54
CountDistinctImplType impl_type_
size_t hll_size(const T *M, const size_t bitmap_sz_bits)
Definition: HyperLogLog.h:90
#define CHECK_GT(x, y)
Definition: Logger.h:202
CHECK(cgen_state)
int64_t count_distinct_set_size(const int64_t set_handle, const CountDistinctDescriptor &count_distinct_desc)
Definition: CountDistinct.h:75
std::vector< CountDistinctDescriptor > CountDistinctDescriptors
Definition: CountDistinct.h:35
void partial_bitmap_union(int8_t *set_vals, const CountDistinctDescriptor &count_distinct_desc)
Definition: CountDistinct.h:61
Functions used to work with HyperLogLog records.
size_t bitmap_set_size(const int8_t *bitmap, const size_t bitmap_byte_sz)
Definition: CountDistinct.h:37