This is an automated email from the ASF dual-hosted git repository.
hello-stephen pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 307bf9e333f [Refactor](bitmap) Refactor BitmapValue small_set and
roaring_bitmap (#65421)
307bf9e333f is described below
commit 307bf9e333f349726c0d00cfe82c446138809bf2
Author: linrrarity <[email protected]>
AuthorDate: Thu Jul 16 09:39:54 2026 +0800
[Refactor](bitmap) Refactor BitmapValue small_set and roaring_bitmap
(#65421)
Problem Summary:
This PR optimizes bitmap execution performance by updating the forked
Roaring64Map implementation and refactoring the small-cardinality SET
representation in BitmapValue.
1. Updates Doris's forked Roaring64Map implementation based on CRoaring
v4.7.2:
https://github.com/RoaringBitmap/CRoaring/blob/v4.7.2/cpp/roaring/roaring64map.hh
Doris-specific serialization/deserialization behavior is preserved.
2. Refactors BitmapValue's small-cardinality SET representation from
`phmap::flat_hash_set` to an inline fixed-capacity container backed by
`std::array<uint64_t, 32>`.
Main SET optimizations include:
- Store small bitmap values inline to avoid heap allocation in common
SET operations.
- Add batch insert paths so add_many and SET deserialization can
copy/process values in bulk.
- Optimize subset operations for SET:
- sub_range filters values directly without sorting.
- sub_limit uses filtering plus nth_element to select the smallest
limited subset without fully sorting all values.
- offset_limit uses nth_element-based rank selection to avoid fully
sorting the SET.
- Add direct intersects and contains_all helpers to avoid materializing
temporary bitmaps in `bitmap_has_any` and `bitmap_has_all`.
3. Compatibility:
- No new bitmap type code is introduced.
- Existing EMPTY, SINGLE32, SINGLE64, SET, SET_V2, BITMAP32/64, and
BITMAP32/64_V2 formats remain readable.
- SET still serializes using the historical SET format.
4. Performance
BITMAP_FROM_ARRAY
before:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
array_size(bitmap_to_array(large_bitmap)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (28.962 sec)
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
array_size(bitmap_to_array(small_bitmap)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (1.267 sec)
```
now:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
array_size(bitmap_to_array(large_bitmap)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (21.722 sec)
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
array_size(bitmap_to_array(small_bitmap)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (0.506 sec)
```
---
BITMAP_CONTAINS
before:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
bitmap_contains(small_bitmap, id % 100);
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (0.995 sec)
```
now:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
bitmap_contains(small_bitmap, id % 100);
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (0.290 sec)
```
---
SUB_BITMAP
before:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
bitmap_count(sub_bitmap(large_bitmap, 100, 500)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (1 min 3.175 sec)
```
now:
```text
Doris> SELECT COUNT(*) FROM bitmap_test WHERE
bitmap_count(sub_bitmap(large_bitmap, 100, 500)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (51.151 sec)
```
---
BITMAP_SUBSET_LIMIT
before:
```text
Doris> SELECT COUNT(*)
-> FROM bitmap_test
-> WHERE bitmap_count(bitmap_subset_limit(large_bitmap, id % 10000,
500)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (1 min 11.807 sec)
```
now:
```text
Doris> SELECT COUNT(*)
-> FROM bitmap_test
-> WHERE bitmap_count(bitmap_subset_limit(large_bitmap, id % 10000,
500)) > 0;
+----------+
| COUNT(*) |
+----------+
| 5000000 |
+----------+
1 row in set (48.117 sec)
```
---
be/src/core/value/bitmap_value.h | 1287 +++++++++++++-------
be/src/exprs/function/function_bitmap.cpp | 34 +-
be/src/exprs/function/function_bitmap_min_or_max.h | 12 +-
be/src/util/coding.h | 15 +
be/test/core/block/column_complex_test.cpp | 4 +-
be/test/core/value/bitmap_value_test.cpp | 449 ++++++-
.../bitmap_functions/test_bitmap_function.out | 21 +
.../bitmap_functions/test_bitmap_function.groovy | 13 +
8 files changed, 1366 insertions(+), 469 deletions(-)
diff --git a/be/src/core/value/bitmap_value.h b/be/src/core/value/bitmap_value.h
index 3b7b05d04a1..f18a7eb8fd3 100644
--- a/be/src/core/value/bitmap_value.h
+++ b/be/src/core/value/bitmap_value.h
@@ -21,9 +21,13 @@
#include <parallel_hashmap/phmap.h>
#include <algorithm>
+#include <array>
+#include <bit>
#include <cstdarg>
#include <cstdint>
#include <cstdio>
+#include <initializer_list>
+#include <iterator>
#include <limits>
#include <map>
#include <memory>
@@ -34,7 +38,9 @@
#include <set>
#include <stdexcept>
#include <string>
+#include <type_traits>
#include <utility>
+#include <vector>
#include "common/config.h"
#include "common/exception.h"
@@ -99,12 +105,14 @@ namespace detail {
class Roaring64MapSetBitForwardIterator;
-// Forked from
https://github.com/RoaringBitmap/CRoaring/blob/v0.2.60/cpp/roaring64map.hh
+// Forked from
https://github.com/RoaringBitmap/CRoaring/blob/v4.7.2/cpp/roaring/roaring64map.hh
// What we change includes
// - a custom serialization format is used inside
read()/write()/getSizeInBytes()
// - added clear() and is32BitsEnough()
class Roaring64Map {
public:
+ using RoaringMap = std::map<uint32_t, roaring::Roaring>;
+
/**
* Create an empty bitmap
*/
@@ -141,41 +149,46 @@ public:
* Add value x
*
*/
- void add(uint32_t x) {
- roarings[0].add(x);
- roarings[0].setCopyOnWrite(copyOnWrite);
- }
- void add(uint64_t x) {
- roarings[highBytes(x)].add(lowBytes(x));
- roarings[highBytes(x)].setCopyOnWrite(copyOnWrite);
- }
+ void add(uint32_t x) { lookupOrCreateInner(0).add(x); }
- template <typename T>
+ void add(uint64_t x) { lookupOrCreateInner(highBytes(x)).add(lowBytes(x));
}
+
+ template <typename T,
+ typename = std::enable_if_t<std::is_integral_v<T> &&
+ !std::is_same_v<std::remove_cv_t<T>,
uint64_t>>>
void addMany(size_t n_args, const T* vals) {
if constexpr (sizeof(T) == sizeof(uint32_t)) {
- auto& roaring = roarings[0];
- roaring.addMany(n_args, reinterpret_cast<const uint32_t*>(vals));
- roaring.setCopyOnWrite(copyOnWrite);
+ lookupOrCreateInner(0).addMany(n_args, reinterpret_cast<const
uint32_t*>(vals));
} else if constexpr (sizeof(T) < sizeof(uint32_t)) {
- auto& roaring = roarings[0];
std::vector<uint32_t> values(n_args);
for (size_t i = 0; i != n_args; ++i) {
- values[i] = uint32_t(vals[i]);
+ values[i] = static_cast<uint32_t>(vals[i]);
}
- roaring.addMany(n_args, values.data());
- roaring.setCopyOnWrite(copyOnWrite);
+ lookupOrCreateInner(0).addMany(n_args, values.data());
} else {
- for (size_t lcv = 0; lcv < n_args; lcv++) {
- roarings[highBytes(vals[lcv])].add(lowBytes(vals[lcv]));
- roarings[highBytes(vals[lcv])].setCopyOnWrite(copyOnWrite);
- }
+ addMany64(n_args, vals);
}
}
- void addMany(size_t n_args, const uint64_t* vals) {
+ void addMany(size_t n_args, const uint64_t* vals) { addMany64(n_args,
vals); }
+
+ template <typename T>
+ void addMany64(size_t n_args, const T* vals) {
+ // Potentially reduce outer map lookups by optimistically
+ // assuming that adjacent values will belong to the same inner bitmap.
+ roaring::Roaring* last_inner_bitmap = nullptr;
+ uint32_t last_value_high = 0;
+ roaring::BulkContext last_bulk_context;
for (size_t lcv = 0; lcv < n_args; lcv++) {
- roarings[highBytes(vals[lcv])].add(lowBytes(vals[lcv]));
- roarings[highBytes(vals[lcv])].setCopyOnWrite(copyOnWrite);
+ auto value = static_cast<uint64_t>(vals[lcv]);
+ auto value_high = highBytes(value);
+ auto value_low = lowBytes(value);
+ if (last_inner_bitmap == nullptr || value_high != last_value_high)
{
+ last_inner_bitmap = &lookupOrCreateInner(value_high);
+ last_value_high = value_high;
+ last_bulk_context = roaring::BulkContext {};
+ }
+ last_inner_bitmap->addBulk(last_bulk_context, value_low);
}
}
@@ -192,7 +205,6 @@ public:
}
/**
* Return the largest value (if not empty)
- *
*/
uint64_t maximum() const {
for (auto roaring_iter = roarings.crbegin(); roaring_iter !=
roarings.crend();
@@ -201,14 +213,13 @@ public:
return uniteBytes(roaring_iter->first,
roaring_iter->second.maximum());
}
}
- // we put std::numeric_limits<>::max/min in parenthesis
+ // we put std::numeric_limits<>::max/min in parentheses
// to avoid a clash with the Windows.h header under Windows
return (std::numeric_limits<uint64_t>::min)();
}
/**
* Return the smallest value (if not empty)
- *
*/
uint64_t minimum() const {
for (auto roaring_iter = roarings.cbegin(); roaring_iter !=
roarings.cend();
@@ -217,7 +228,7 @@ public:
return uniteBytes(roaring_iter->first,
roaring_iter->second.minimum());
}
}
- // we put std::numeric_limits<>::max/min in parenthesis
+ // we put std::numeric_limits<>::max/min in parentheses
// to avoid a clash with the Windows.h header under Windows
return (std::numeric_limits<uint64_t>::max)();
}
@@ -226,25 +237,75 @@ public:
* Check if value x is present
*/
bool contains(uint32_t x) const {
- return roarings.count(0) == 0 ? false : roarings.at(0).contains(x);
+ auto iter = roarings.find(0);
+ if (iter == roarings.end()) {
+ return false;
+ }
+ return iter->second.contains(x);
}
bool contains(uint64_t x) const {
- return roarings.count(highBytes(x)) == 0 ? false
- :
roarings.at(highBytes(x)).contains(lowBytes(x));
+ auto iter = roarings.find(highBytes(x));
+ if (iter == roarings.end()) {
+ return false;
+ }
+ return iter->second.contains(lowBytes(x));
}
/**
- * Compute the intersection between the current bitmap and the provided
- * bitmap,
+ * Compute the intersection of the current bitmap and the provided bitmap,
* writing the result in the current bitmap. The provided bitmap is not
* modified.
+ *
+ * Performance hint: if you are computing the intersection between several
+ * bitmaps, two-by-two, it is best to start with the smallest bitmap.
*/
- Roaring64Map& operator&=(const Roaring64Map& r) {
- for (auto& map_entry : roarings) {
- if (r.roarings.count(map_entry.first) == 1) {
- map_entry.second &= r.roarings.at(map_entry.first);
- } else {
- map_entry.second = roaring::Roaring();
+ Roaring64Map& operator&=(const Roaring64Map& other) {
+ if (this == &other) {
+ // ANDing *this with itself is a no-op.
+ return *this;
+ }
+
+ // Logic table summarizing what to do when a given outer key is
+ // present vs. absent from self and other.
+ //
+ // self other (self & other) work to do
+ // --------------------------------------------
+ // absent absent empty None
+ // absent present empty None
+ // present absent empty Erase self
+ // present present empty or not Intersect self with other, but
+ // erase self if result is empty.
+ //
+ // Because there is only work to do when a key is present in 'self',
the
+ // main for loop iterates over entries in 'self'.
+
+ decltype(roarings.begin()) self_next;
+ for (auto self_iter = roarings.begin(); self_iter != roarings.end();
+ self_iter = self_next) {
+ // Do the 'next' operation now, so we don't have to worry about
+ // invalidation of self_iter down below with the 'erase' operation.
+ self_next = std::next(self_iter);
+
+ auto self_key = self_iter->first;
+ auto& self_bitmap = self_iter->second;
+
+ auto other_iter = other.roarings.find(self_key);
+ if (other_iter == other.roarings.end()) {
+ // 'other' doesn't have self_key. In the logic table above,
+ // this reflects the case (self.present & other.absent).
+ // So, erase self.
+ roarings.erase(self_iter);
+ continue;
+ }
+
+ // Both sides have self_key. In the logic table above, this
reflects
+ // the case (self.present & other.present). So, intersect self with
+ // other.
+ const auto& other_bitmap = other_iter->second;
+ self_bitmap &= other_bitmap;
+ if (self_bitmap.isEmpty()) {
+ // ...but if intersection is empty, remove it altogether.
+ roarings.erase(self_iter);
}
}
return *this;
@@ -252,51 +313,178 @@ public:
/**
* Compute the difference between the current bitmap and the provided
- * bitmap,
- * writing the result in the current bitmap. The provided bitmap is not
- * modified.
+ * bitmap, writing the result in the current bitmap. The provided bitmap
+ * is not modified.
*/
- Roaring64Map& operator-=(const Roaring64Map& r) {
- for (auto& map_entry : roarings) {
- if (r.roarings.count(map_entry.first) == 1) {
- map_entry.second -= r.roarings.at(map_entry.first);
+ Roaring64Map& operator-=(const Roaring64Map& other) {
+ if (this == &other) {
+ // Subtracting *this from itself results in the empty map.
+ roarings.clear();
+ return *this;
+ }
+
+ // Logic table summarizing what to do when a given outer key is
+ // present vs. absent from self and other.
+ //
+ // self other (self - other) work to do
+ // --------------------------------------------
+ // absent absent empty None
+ // absent present empty None
+ // present absent unchanged None
+ // present present empty or not Subtract other from self, but
+ // erase self if result is empty
+ //
+ // Because there is only work to do when a key is present in both
'self'
+ // and 'other', the main while loop ping-pongs back and forth until it
+ // finds the next key that is the same on both sides.
+
+ auto self_iter = roarings.begin();
+ auto other_iter = other.roarings.cbegin();
+
+ while (self_iter != roarings.end() && other_iter !=
other.roarings.cend()) {
+ auto self_key = self_iter->first;
+ auto other_key = other_iter->first;
+ if (self_key < other_key) {
+ // Because self_key is < other_key, advance self_iter to the
+ // first point where self_key >= other_key (or end).
+ self_iter = roarings.lower_bound(other_key);
+ continue;
+ }
+
+ if (self_key > other_key) {
+ // Because self_key is > other_key, advance other_iter to the
+ // first point where other_key >= self_key (or end).
+ other_iter = other.roarings.lower_bound(self_key);
+ continue;
+ }
+
+ // Both sides have self_key. In the logic table above, this
reflects
+ // the case (self.present & other.present). So subtract other from
+ // self.
+ auto& self_bitmap = self_iter->second;
+ const auto& other_bitmap = other_iter->second;
+ self_bitmap -= other_bitmap;
+
+ if (self_bitmap.isEmpty()) {
+ // ...but if subtraction is empty, remove it altogether.
+ self_iter = roarings.erase(self_iter);
+ } else {
+ ++self_iter;
}
+ ++other_iter;
}
return *this;
}
/**
- * Compute the union between the current bitmap and the provided bitmap,
+ * Compute the union of the current bitmap and the provided bitmap,
* writing the result in the current bitmap. The provided bitmap is not
* modified.
*
* See also the fastunion function to aggregate many bitmaps more quickly.
*/
- Roaring64Map& operator|=(const Roaring64Map& r) {
- for (const auto& map_entry : r.roarings) {
- if (roarings.count(map_entry.first) == 0) {
- roarings[map_entry.first] = map_entry.second;
- roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
- } else {
- roarings[map_entry.first] |= map_entry.second;
+ Roaring64Map& operator|=(const Roaring64Map& other) {
+ if (this == &other) {
+ // ORing *this with itself is a no-op.
+ return *this;
+ }
+
+ // Logic table summarizing what to do when a given outer key is
+ // present vs. absent from self and other.
+ //
+ // self other (self | other) work to do
+ // --------------------------------------------
+ // absent absent empty None
+ // absent present not empty Copy other to self and set flags
+ // present absent unchanged None
+ // present present not empty self |= other
+ //
+ // Because there is only work to do when a key is present in 'other',
+ // the main for loop iterates over entries in 'other'.
+
+ for (const auto& other_entry : other.roarings) {
+ const auto& other_bitmap = other_entry.second;
+
+ // Try to insert other_bitmap into self at other_key. We take
+ // advantage of the fact that std::map::insert will not overwrite
an
+ // existing entry.
+ auto insert_result = roarings.insert(other_entry);
+ auto self_iter = insert_result.first;
+ auto insert_happened = insert_result.second;
+ auto& self_bitmap = self_iter->second;
+
+ if (insert_happened) {
+ // Key was not present in self, so insert was performed above.
+ // In the logic table above, this reflects the case
+ // (self.absent | other.present). Because the copy has already
+ // happened, thanks to the 'insert' operation above, we just
+ // need to set the copyOnWrite flag.
+ self_bitmap.setCopyOnWrite(copyOnWrite);
+ continue;
}
+
+ // Both sides have self_key, and the insert was not performed. In
+ // the logic table above, this reflects the case
+ // (self.present & other.present). So OR other into self.
+ self_bitmap |= other_bitmap;
}
return *this;
}
/**
- * Compute the symmetric union between the current bitmap and the provided
- * bitmap,
- * writing the result in the current bitmap. The provided bitmap is not
- * modified.
+ * Compute the XOR of the current bitmap and the provided bitmap, writing
+ * the result in the current bitmap. The provided bitmap is not modified.
*/
- Roaring64Map& operator^=(const Roaring64Map& r) {
- for (const auto& map_entry : r.roarings) {
- if (roarings.count(map_entry.first) == 0) {
- roarings[map_entry.first] = map_entry.second;
- roarings[map_entry.first].setCopyOnWrite(copyOnWrite);
- } else {
- roarings[map_entry.first] ^= map_entry.second;
+ Roaring64Map& operator^=(const Roaring64Map& other) {
+ if (this == &other) {
+ // XORing *this with itself results in the empty map.
+ roarings.clear();
+ return *this;
+ }
+
+ // Logic table summarizing what to do when a given outer key is
+ // present vs. absent from self and other.
+ //
+ // self other (self ^ other) work to do
+ // --------------------------------------------
+ // absent absent empty None
+ // absent present non-empty Copy other to self and set flags
+ // present absent unchanged None
+ // present present empty or not XOR other into self, but erase
self
+ // if result is empty.
+ //
+ // Because there is only work to do when a key is present in 'other',
+ // the main for loop iterates over entries in 'other'.
+
+ for (const auto& other_entry : other.roarings) {
+ const auto& other_bitmap = other_entry.second;
+
+ // Try to insert other_bitmap into self at other_key. We take
+ // advantage of the fact that std::map::insert will not overwrite
an
+ // existing entry.
+ auto insert_result = roarings.insert(other_entry);
+ auto self_iter = insert_result.first;
+ auto insert_happened = insert_result.second;
+ auto& self_bitmap = self_iter->second;
+
+ if (insert_happened) {
+ // Key was not present in self, so insert was performed above.
+ // In the logic table above, this reflects the case
+ // (self.absent ^ other.present). Because the copy has already
+ // happened, thanks to the 'insert' operation above, we just
+ // need to set the copyOnWrite flag.
+ self_bitmap.setCopyOnWrite(copyOnWrite);
+ continue;
+ }
+
+ // Both sides have self_key, and the insert was not performed. In
+ // the logic table above, this reflects the case
+ // (self.present ^ other.present). So XOR other into self.
+ self_bitmap ^= other_bitmap;
+
+ if (self_bitmap.isEmpty()) {
+ // ...but if intersection is empty, remove it altogether.
+ roarings.erase(self_iter);
}
}
return *this;
@@ -339,6 +527,18 @@ public:
return card;
}
+ bool intersect(const Roaring64Map& r) const {
+ const auto& smaller = roarings.size() <= r.roarings.size() ? roarings
: r.roarings;
+ const auto& larger = roarings.size() <= r.roarings.size() ? r.roarings
: roarings;
+ for (const auto& map_entry : smaller) {
+ auto it = larger.find(map_entry.first);
+ if (it != larger.cend() && map_entry.second.intersect(it->second))
{
+ return true;
+ }
+ }
+ return false;
+ }
+
/**
* Computes the size of the union between two bitmaps.
*
@@ -394,6 +594,20 @@ public:
return card;
}
+ bool isSubset(const Roaring64Map& r) const {
+ for (const auto& map_entry : roarings) {
+ if (map_entry.second.isEmpty()) {
+ continue;
+ }
+ auto roaring_iter = r.roarings.find(map_entry.first);
+ if (roaring_iter == r.roarings.cend())
+ return false;
+ else if (!map_entry.second.isSubset(roaring_iter->second))
+ return false;
+ }
+ return true;
+ }
+
/**
* Returns true if the bitmap is empty (cardinality is zero).
*/
@@ -425,6 +639,22 @@ public:
: false;
}
+ /**
+ * Convert the bitmap to a sorted array. Write the output to "ans", the
+ * caller is responsible to ensure that there is enough memory allocated
+ * (e.g., ans = new uint64_t[mybitmap.cardinality()];)
+ */
+ void toUint64Array(uint64_t* ans) const {
+ // Annoyingly, VS 2017 marks std::accumulate() as [[nodiscard]]
+ (void)std::accumulate(roarings.cbegin(), roarings.cend(), ans,
+ [](uint64_t* previous,
+ const std::pair<const uint32_t,
roaring::Roaring>& map_entry) {
+ for (uint32_t low_bits : map_entry.second)
+ *previous++ =
uniteBytes(map_entry.first, low_bits);
+ return previous;
+ });
+ }
+
/**
* Return true if the two bitmaps contain the same elements.
*/
@@ -436,10 +666,8 @@ public:
auto rhs_iter = r.roarings.cbegin();
auto rhs_cend = r.roarings.cend();
while (lhs_iter != lhs_cend && rhs_iter != rhs_cend) {
- auto lhs_key = lhs_iter->first;
- auto rhs_key = rhs_iter->first;
- const auto& lhs_map = lhs_iter->second;
- const auto& rhs_map = rhs_iter->second;
+ auto lhs_key = lhs_iter->first, rhs_key = rhs_iter->first;
+ const auto &lhs_map = lhs_iter->second, &rhs_map =
rhs_iter->second;
if (lhs_map.isEmpty()) {
++lhs_iter;
continue;
@@ -487,9 +715,9 @@ public:
}
/**
- * If needed, reallocate memory to shrink the memory usage. Returns
- * the number of bytes saved.
- */
+ * If needed, reallocate memory to shrink the memory usage.
+ * Returns the number of bytes saved.
+ */
size_t shrinkToFit() {
size_t savedBytes = 0;
auto iter = roarings.begin();
@@ -497,7 +725,7 @@ public:
if (iter->second.isEmpty()) {
// empty Roarings are 84 bytes
savedBytes += 88;
- iter = roarings.erase(iter);
+ roarings.erase(iter++);
} else {
savedBytes += iter->second.shrinkToFit();
iter++;
@@ -507,13 +735,15 @@ public:
}
/**
- * Iterate over the bitmap elements. The function iterator is called once
- * for all the values with ptr (can be nullptr) as the second parameter of
each
- * call.
+ * Iterate over the bitmap elements in order(start from the smallest one)
+ * and call iterator once for every element until the iterator function
+ * returns false. To iterate over all values, the iterator function should
+ * always return true.
*
- * roaring_iterator is simply a pointer to a function that returns bool
- * (true means that the iteration should continue while false means that it
- * should stop), and takes (uint32_t,void*) as inputs.
+ * The roaring_iterator64 parameter is a pointer to a function that
+ * returns bool (true means that the iteration should continue while false
+ * means that it should stop), and takes (uint64_t element, void* ptr) as
+ * inputs.
*/
void iterate(roaring::api::roaring_iterator64 iterator, void* ptr) const {
for (const auto& map_entry : roarings) {
@@ -665,8 +895,8 @@ public:
*/
static Roaring64Map fastunion(size_t n, const Roaring64Map** inputs) {
struct pq_entry {
- phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator
iterator;
- phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator end;
+ RoaringMap::const_iterator iterator;
+ RoaringMap::const_iterator end;
};
struct pq_comp {
@@ -746,7 +976,7 @@ public:
const_iterator end() const;
private:
- phmap::btree_map<uint32_t, roaring::Roaring> roarings {};
+ RoaringMap roarings {};
bool copyOnWrite {false};
static uint32_t highBytes(const uint64_t in) { return uint32_t(in >> 32); }
static uint32_t lowBytes(const uint64_t in) { return uint32_t(in); }
@@ -758,23 +988,60 @@ private:
}
void emplaceOrInsert(const uint32_t key, roaring::Roaring&& value) {
+ // CRoaring's C++ move constructor bit-copies the underlying C struct
and
+ // is unsafe with phmap::btree_map value relocation after operations
such as shrinkToFit().
roarings.emplace(key, value);
}
+
+ roaring::Roaring& lookupOrCreateInner(uint32_t key) {
+ auto& bitmap = roarings[key];
+ bitmap.setCopyOnWrite(copyOnWrite);
+ return bitmap;
+ }
};
-// Forked from
https://github.com/RoaringBitmap/CRoaring/blob/v0.4.0/cpp/roaring64map.hh
+// Forked from
https://github.com/RoaringBitmap/CRoaring/blob/v4.7.2/cpp/roaring/roaring64map.hh
// Used to go through the set bits. Not optimally fast, but convenient.
class Roaring64MapSetBitForwardIterator {
public:
+ using iterator_category = std::forward_iterator_tag;
+ using pointer = uint64_t*;
+ using reference_type = uint64_t&;
+ using value_type = uint64_t;
+ using difference_type = int64_t;
using type_of_iterator = Roaring64MapSetBitForwardIterator;
/**
* Provides the location of the set bit.
*/
- uint64_t operator*() const {
+ value_type operator*() const {
return Roaring64Map::uniteBytes(map_iter->first, i.current_value);
}
+ bool operator<(const type_of_iterator& o) const {
+ if (map_iter == map_end) return false;
+ if (o.map_iter == o.map_end) return true;
+ return **this < *o;
+ }
+
+ bool operator<=(const type_of_iterator& o) const {
+ if (o.map_iter == o.map_end) return true;
+ if (map_iter == map_end) return false;
+ return **this <= *o;
+ }
+
+ bool operator>(const type_of_iterator& o) const {
+ if (o.map_iter == o.map_end) return false;
+ if (map_iter == map_end) return true;
+ return **this > *o;
+ }
+
+ bool operator>=(const type_of_iterator& o) const {
+ if (map_iter == map_end) return true;
+ if (o.map_iter == o.map_end) return false;
+ return **this >= *o;
+ }
+
type_of_iterator& operator++() { // ++i, must returned inc. value
if (i.has_value) {
roaring_advance_uint32_iterator(&i);
@@ -798,22 +1065,6 @@ public:
return orig;
}
- bool move(const uint64_t& x) {
- map_iter = p.lower_bound(Roaring64Map::highBytes(x));
- if (map_iter != p.cend()) {
- roaring_init_iterator(&map_iter->second.roaring, &i);
- if (map_iter->first == Roaring64Map::highBytes(x)) {
- if (roaring_move_uint32_iterator_equalorlarger(&i,
Roaring64Map::lowBytes(x)))
- return true;
- map_iter++;
- if (map_iter == map_end) return false;
- roaring_init_iterator(&map_iter->second.roaring, &i);
- }
- return true;
- }
- return false;
- }
-
bool operator==(const Roaring64MapSetBitForwardIterator& o) const {
if (map_iter == map_end && o.map_iter == o.map_end) return true;
if (o.map_iter == o.map_end) return false;
@@ -832,7 +1083,8 @@ public:
return *this;
}
- Roaring64MapSetBitForwardIterator(const Roaring64MapSetBitForwardIterator&
r) = default;
+ Roaring64MapSetBitForwardIterator(const Roaring64MapSetBitForwardIterator&
r)
+ : p(r.p), map_iter(r.map_iter), map_end(r.map_end), i(r.i) {}
Roaring64MapSetBitForwardIterator(const Roaring64Map& parent, bool
exhausted = false)
: p(parent.roarings), map_end(parent.roarings.cend()) {
@@ -850,9 +1102,9 @@ public:
}
protected:
- const phmap::btree_map<uint32_t, roaring::Roaring>& p;
- phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator map_iter {};
- phmap::btree_map<uint32_t, roaring::Roaring>::const_iterator map_end {};
+ const Roaring64Map::RoaringMap& p;
+ Roaring64Map::RoaringMap::const_iterator map_iter {};
+ Roaring64Map::RoaringMap::const_iterator map_end {};
roaring::api::roaring_uint32_iterator_t i {};
};
@@ -866,15 +1118,193 @@ inline Roaring64MapSetBitForwardIterator
Roaring64Map::end() const {
} // namespace detail
+class BitmapValue;
+
+class BitmapSmallSet {
+public:
+ using value_type = uint64_t;
+ using iterator = value_type*;
+ using const_iterator = const value_type*;
+
+ static constexpr size_t INLINE_CAPACITY = 32;
+ static_assert(INLINE_CAPACITY <= std::numeric_limits<uint8_t>::max(),
+ "INLINE_CAPACITY must fit into uint8_t");
+
+ BitmapSmallSet() = default;
+ BitmapSmallSet(const BitmapSmallSet&) = default;
+ BitmapSmallSet& operator=(const BitmapSmallSet&) = default;
+ BitmapSmallSet(BitmapSmallSet&& other) noexcept { *this =
std::move(other); }
+
+ BitmapSmallSet& operator=(BitmapSmallSet&& other) noexcept {
+ if (this == &other) {
+ return *this;
+ }
+ _values = other._values;
+ _size = other._size;
+ other.clear();
+ return *this;
+ }
+
+ size_t size() const { return _size; }
+ bool empty() const { return _size == 0; }
+
+ iterator begin() { return _values.data(); }
+ iterator end() { return _values.data() + _size; }
+ const_iterator begin() const { return _values.data(); }
+ const_iterator end() const { return _values.data() + _size; }
+ const_iterator cbegin() const { return begin(); }
+ const_iterator cend() const { return end(); }
+ const value_type* data() const { return _values.data(); }
+
+ void clear() { _size = 0; }
+
+ bool contains(value_type value) const { return find_index(value) != npos; }
+
+ // Use `insert/insert_many` only when the caller has proved the inline
storage will not overflow.
+ // Paths that may increase cardinality should call
`BitmapValue::add/add_many` instead.
+ void insert(value_type value) {
+ size_t pos = find_index(value);
+ if (pos != npos) {
+ return;
+ }
+
+ DORIS_CHECK(_size < INLINE_CAPACITY) << "BitmapSmallSet overflow";
+
+ _values[_size] = value;
+ ++_size;
+ }
+
+ template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
+ void insert_many(const T* values, size_t n) {
+ DORIS_CHECK(_size + n <= INLINE_CAPACITY) << "BitmapSmallSet overflow";
+ if (n == 0) {
+ return;
+ }
+
+ if constexpr (std::is_same_v<std::remove_cv_t<T>, value_type>) {
+ memcpy(_values.data() + _size, values, sizeof(value_type) * n);
+ } else {
+ std::array<value_type, INLINE_CAPACITY> converted_values {};
+ for (size_t i = 0; i < n; ++i) {
+ converted_values[i] = static_cast<value_type>(values[i]);
+ }
+ memcpy(_values.data() + _size, converted_values.data(),
sizeof(value_type) * n);
+ }
+ _size = static_cast<uint8_t>(_size + n);
+ compact_unique();
+ }
+
+ template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
+ bool try_insert_many(const T* values, size_t n) {
+ if (_size + n <= INLINE_CAPACITY) {
+ insert_many(values, n);
+ return true;
+ }
+
+ BitmapSmallSet candidate = *this;
+ for (size_t i = 0; i < n; ++i) {
+ auto value = static_cast<value_type>(values[i]);
+ if (candidate.contains(value)) {
+ continue;
+ }
+ if (candidate.size() >= INLINE_CAPACITY) {
+ return false;
+ }
+ candidate.insert(value);
+ }
+ *this = std::move(candidate);
+ return true;
+ }
+
+ // Read serialized SET payload. Values are stored as fixed little-endian
uint64_t.
+ bool read(const void* src, size_t n, bool deduplicate = false) {
+ DORIS_CHECK(n <= INLINE_CAPACITY) << "BitmapSmallSet overflow";
+ clear();
+ decode_fixed64_le_array(_values.data(), src, n);
+ _size = static_cast<uint8_t>(n);
+ if (deduplicate) {
+ compact_unique();
+ return true;
+ }
+ return has_unique_values();
+ }
+
+ void copy_to_sorted(value_type* dst) const {
+ if (_size > 0) {
+ memcpy(dst, _values.data(), sizeof(value_type) * _size);
+ }
+ std::sort(dst, dst + _size);
+ }
+
+ size_t erase(value_type value) {
+ size_t pos = find_index(value);
+ if (pos == npos) {
+ return 0;
+ }
+ erase_at(pos);
+ return 1;
+ }
+
+ value_type operator[](size_t index) const { return _values[index]; }
+ value_type& operator[](size_t index) { return _values[index]; }
+
+private:
+ friend class BitmapValue;
+
+ size_t find_index(value_type value) const {
+ for (size_t i = 0; i < _size; ++i) {
+ if (_values[i] == value) {
+ return i;
+ }
+ }
+ return npos;
+ }
+
+ void erase_at(size_t pos) {
+ DCHECK_LT(pos, _size);
+ _values[pos] = _values[_size - 1];
+ --_size;
+ }
+
+ bool has_unique_values() const {
+ for (size_t i = 0; i < _size; ++i) {
+ for (size_t j = i + 1; j < _size; ++j) {
+ if (_values[i] == _values[j]) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ void compact_unique() {
+ size_t unique_size = 0;
+ for (size_t i = 0; i < _size; ++i) {
+ bool found = false;
+ for (size_t j = 0; j < unique_size; ++j) {
+ if (_values[j] == _values[i]) {
+ found = true;
+ break;
+ }
+ }
+ if (!found) {
+ _values[unique_size++] = _values[i];
+ }
+ }
+ _size = static_cast<uint8_t>(unique_size);
+ }
+
+ std::array<value_type, INLINE_CAPACITY> _values {};
+ uint8_t _size = 0;
+ static constexpr size_t npos = static_cast<size_t>(-1);
+};
+
// Represent the in-memory and on-disk structure of Doris's BITMAP data type.
// Optimize for the case where the bitmap contains 0 or 1 element which is
common
// for streaming load scenario.
class BitmapValueIterator;
class BitmapValue {
public:
- template <typename T>
- using SetContainer = phmap::flat_hash_set<T>;
-
// Construct an empty bitmap.
BitmapValue() : _sv(0), _bitmap(nullptr), _type(EMPTY), _is_shared(false)
{ _set.clear(); }
@@ -989,32 +1419,21 @@ public:
break;
}
_is_shared = other._is_shared;
+ other._type = EMPTY;
+ other._is_shared = false;
return *this;
}
// Construct a bitmap from given elements.
- explicit BitmapValue(const std::vector<uint64_t>& bits) :
_is_shared(false) {
- if (bits.size() == 0) {
- _type = EMPTY;
- return;
- }
-
- if (bits.size() == 1) {
- _type = SINGLE;
- _sv = bits[0];
- return;
- }
+ template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
+ explicit BitmapValue(const std::vector<T>& bits) : _is_shared(false) {
+ _type = EMPTY;
+ this->add_many(bits.data(), bits.size());
+ }
- if (!config::enable_set_in_bitmap_value || bits.size() >
SET_TYPE_THRESHOLD) {
- _type = BITMAP;
- _prepare_bitmap_for_write();
- _bitmap->addMany(bits.size(), &bits[0]);
- } else {
- _type = SET;
- for (auto v : bits) {
- _set.insert(v);
- }
- }
+ explicit BitmapValue(const std::vector<uint64_t>& bits) :
_is_shared(false) {
+ _type = EMPTY;
+ add_many(bits.data(), bits.size());
}
BitmapTypeCode::type get_type_code() const {
@@ -1040,18 +1459,27 @@ public:
__builtin_unreachable();
}
- template <typename T>
+ template <typename T, typename = std::enable_if_t<std::is_integral_v<T>>>
void add_many(const T* values, const size_t count) {
+ if (count == 0) {
+ return;
+ }
+
switch (_type) {
case EMPTY:
if (count == 1) {
- _sv = values[0];
+ _sv = static_cast<uint64_t>(values[0]);
_type = SINGLE;
- } else if (config::enable_set_in_bitmap_value && count <
SET_TYPE_THRESHOLD) {
- for (size_t i = 0; i != count; ++i) {
- _set.insert(values[i]);
+ } else if (config::enable_set_in_bitmap_value) {
+ BitmapSmallSet new_set;
+ if (new_set.try_insert_many(values, count)) {
+ _set = std::move(new_set);
+ _type = SET;
+ } else {
+ _prepare_bitmap_for_write();
+ _bitmap->addMany(count, values);
+ _type = BITMAP;
}
- _type = SET;
} else {
_prepare_bitmap_for_write();
_bitmap->addMany(count, values);
@@ -1059,13 +1487,18 @@ public:
}
break;
case SINGLE:
- if (config::enable_set_in_bitmap_value && count <
SET_TYPE_THRESHOLD) {
- _set.insert(_sv);
- for (size_t i = 0; i != count; ++i) {
- _set.insert(values[i]);
+ if (config::enable_set_in_bitmap_value) {
+ BitmapSmallSet new_set;
+ new_set.insert(_sv);
+ if (new_set.try_insert_many(values, count)) {
+ _set = std::move(new_set);
+ _type = SET;
+ } else {
+ _prepare_bitmap_for_write();
+ _bitmap->add(_sv);
+ _bitmap->addMany(count, values);
+ _type = BITMAP;
}
- _type = SET;
- _convert_to_bitmap_if_need();
} else {
_prepare_bitmap_for_write();
_bitmap->add(_sv);
@@ -1078,10 +1511,10 @@ public:
_bitmap->addMany(count, values);
break;
case SET:
- for (size_t i = 0; i != count; ++i) {
- _set.insert(values[i]);
+ if (!_set.try_insert_many(values, count)) {
+ _convert_set_to_bitmap();
+ _bitmap->addMany(count, values);
}
- _convert_to_bitmap_if_need();
break;
}
}
@@ -1093,8 +1526,9 @@ public:
_sv = value;
_type = SINGLE;
} else {
- _set.insert(value);
_type = SET;
+ _set.clear();
+ _set.insert(value);
}
break;
case SINGLE:
@@ -1103,6 +1537,7 @@ public:
break;
}
if (config::enable_set_in_bitmap_value) {
+ _set.clear();
_set.insert(_sv);
_set.insert(value);
_type = SET;
@@ -1118,8 +1553,15 @@ public:
_bitmap->add(value);
break;
case SET:
- _set.insert(value);
- _convert_to_bitmap_if_need();
+ if (_set.contains(value)) {
+ break;
+ }
+ if (_set.size() < SET_TYPE_THRESHOLD) {
+ _set.insert(value);
+ } else {
+ _convert_set_to_bitmap();
+ _bitmap->add(value);
+ }
break;
}
}
@@ -1169,11 +1611,11 @@ public:
_convert_to_smaller_type();
break;
case SET: {
- for (auto it = _set.begin(); it != _set.end();) {
- if (rhs.contains(*it)) {
- it = _set.erase(it);
+ for (size_t i = 0; i < _set.size();) {
+ if (rhs.contains(_set[i])) {
+ _set.erase_at(i);
} else {
- ++it;
+ ++i;
}
}
_convert_to_smaller_type();
@@ -1193,18 +1635,16 @@ public:
case BITMAP:
_prepare_bitmap_for_write();
for (auto v : rhs._set) {
- if (_bitmap->contains(v)) {
- _bitmap->remove(v);
- }
+ _bitmap->remove(v);
}
_convert_to_smaller_type();
break;
case SET: {
- for (auto it = _set.begin(); it != _set.end();) {
- if (rhs.contains(*it)) {
- it = _set.erase(it);
+ for (size_t i = 0; i < _set.size();) {
+ if (rhs.contains(_set[i])) {
+ _set.erase_at(i);
} else {
- ++it;
+ ++i;
}
}
_convert_to_smaller_type();
@@ -1252,11 +1692,10 @@ public:
case SET: {
_prepare_bitmap_for_write();
*_bitmap = *rhs._bitmap;
-
- for (auto v : _set) {
- _bitmap->add(v);
- }
+ _bitmap->addMany(_set.size(), _set.data());
_type = BITMAP;
+
+ _set.clear();
break;
}
}
@@ -1268,34 +1707,19 @@ public:
_type = SET;
break;
case SINGLE: {
- if ((rhs._set.size() + rhs._set.contains(_sv) >
SET_TYPE_THRESHOLD)) {
- _prepare_bitmap_for_write();
- _bitmap->add(_sv);
- for (auto v : rhs._set) {
- _bitmap->add(v);
- }
- _type = BITMAP;
- } else {
- _set = rhs._set;
- _set.insert(_sv);
- _type = SET;
- }
+ _set = rhs._set;
+ _type = SET;
+ this->add(_sv);
break;
}
case BITMAP:
_prepare_bitmap_for_write();
- for (auto v : rhs._set) {
- _bitmap->add(v);
- }
+ _bitmap->addMany(rhs._set.size(), rhs._set.data());
break;
- case SET: {
- for (auto v : rhs._set) {
- _set.insert(v);
- }
- _convert_to_bitmap_if_need();
+ case SET:
+ this->add_many(rhs._set.data(), rhs._set.size());
break;
}
- }
break;
}
return *this;
@@ -1304,7 +1728,7 @@ public:
BitmapValue& fastunion(const std::vector<const BitmapValue*>& values) {
std::vector<const detail::Roaring64Map*> bitmaps;
std::vector<uint64_t> single_values;
- std::vector<const SetContainer<uint64_t>*> sets;
+ std::vector<const BitmapSmallSet*> sets;
for (const auto* value : values) {
switch (value->_type) {
case EMPTY:
@@ -1338,9 +1762,7 @@ public:
break;
case SET: {
*_bitmap = detail::Roaring64Map::fastunion(bitmaps.size(),
bitmaps.data());
- for (auto v : _set) {
- _bitmap->add(v);
- }
+ _bitmap->addMany(_set.size(), _set.data());
_set.clear();
break;
}
@@ -1350,75 +1772,12 @@ public:
if (!sets.empty()) {
for (auto& set : sets) {
- for (auto v : *set) {
- _set.insert(v);
- }
- }
- switch (_type) {
- case EMPTY:
- _type = SET;
- break;
- case SINGLE: {
- _set.insert(_sv);
- _type = SET;
- break;
- }
- case BITMAP:
- _prepare_bitmap_for_write();
- for (auto v : _set) {
- _bitmap->add(v);
- }
- _type = BITMAP;
- _set.clear();
- break;
- case SET: {
- break;
- }
- }
- if (_type == SET) {
- _convert_to_bitmap_if_need();
+ this->add_many(set->data(), set->size());
}
}
- if (_type == EMPTY && single_values.size() == 1) {
- if (config::enable_set_in_bitmap_value) {
- _type = SET;
- _set.insert(single_values[0]);
- } else {
- _sv = single_values[0];
- _type = SINGLE;
- }
- } else if (!single_values.empty()) {
- switch (_type) {
- case EMPTY:
- case SINGLE:
- if (config::enable_set_in_bitmap_value) {
- _set.insert(single_values.cbegin(), single_values.cend());
- if (_type == SINGLE) {
- _set.insert(_sv);
- }
- _type = SET;
- _convert_to_bitmap_if_need();
- } else {
- _prepare_bitmap_for_write();
- _bitmap->addMany(single_values.size(),
single_values.data());
- if (_type == SINGLE) {
- _bitmap->add(_sv);
- }
- _type = BITMAP;
- _convert_to_smaller_type();
- }
- break;
- case BITMAP: {
- _prepare_bitmap_for_write();
- _bitmap->addMany(single_values.size(), single_values.data());
- break;
- }
- case SET:
- _set.insert(single_values.cbegin(), single_values.cend());
- _convert_to_bitmap_if_need();
- break;
- }
+ if (!single_values.empty()) {
+ this->add_many(single_values.data(), single_values.size());
}
return *this;
@@ -1479,11 +1838,11 @@ public:
_convert_to_smaller_type();
break;
case SET:
- for (auto it = _set.begin(); it != _set.end();) {
- if (!rhs._bitmap->contains(*it)) {
- it = _set.erase(it);
+ for (size_t i = 0; i < _set.size();) {
+ if (!rhs._bitmap->contains(_set[i])) {
+ _set.erase_at(i);
} else {
- ++it;
+ ++i;
}
}
_convert_to_smaller_type();
@@ -1512,11 +1871,11 @@ public:
_convert_to_smaller_type();
break;
case SET:
- for (auto it = _set.begin(); it != _set.end();) {
- if (!rhs._set.contains(*it)) {
- it = _set.erase(it);
+ for (size_t i = 0; i < _set.size();) {
+ if (!rhs._set.contains(_set[i])) {
+ _set.erase_at(i);
} else {
- ++it;
+ ++i;
}
}
_convert_to_smaller_type();
@@ -1546,22 +1905,22 @@ public:
if (_sv == rhs._sv) {
_type = EMPTY;
} else {
- add(rhs._sv);
+ this->add(rhs._sv);
}
break;
case BITMAP:
if (!_bitmap->contains(rhs._sv)) {
- add(rhs._sv);
+ this->add(rhs._sv);
} else {
- _prepare_bitmap_for_write();
- _bitmap->remove(rhs._sv);
+ this->remove(rhs._sv);
}
+ _convert_to_smaller_type();
break;
case SET:
if (!_set.contains(rhs._sv)) {
- _set.insert(rhs._sv);
+ this->add(rhs._sv);
} else {
- _set.erase(rhs._sv);
+ this->remove(rhs._sv);
}
break;
}
@@ -1583,7 +1942,7 @@ public:
if (!rhs._bitmap->contains(_sv)) {
_bitmap->add(_sv);
} else {
- _bitmap->remove(_sv);
+ this->remove(_sv);
}
break;
case BITMAP:
@@ -1601,6 +1960,7 @@ public:
_bitmap->add(v);
}
}
+ _set.clear();
_type = BITMAP;
_convert_to_smaller_type();
break;
@@ -1614,12 +1974,12 @@ public:
break;
case SINGLE:
_set = rhs._set;
- if (!rhs._set.contains(_sv)) {
- _set.insert(_sv);
+ _type = SET;
+ if (_set.contains(_sv)) {
+ this->remove(_sv);
} else {
- _set.erase(_sv);
+ this->add(_sv);
}
- _type = SET;
break;
case BITMAP:
_prepare_bitmap_for_write();
@@ -1633,14 +1993,27 @@ public:
_convert_to_smaller_type();
break;
case SET:
- for (auto v : rhs._set) {
- if (_set.contains(v)) {
- _set.erase(v);
- } else {
- _set.insert(v);
+ if (this == &rhs) {
+ reset();
+ break;
+ }
+
+ std::array<uint64_t, SET_TYPE_THRESHOLD> values_to_add {};
+ size_t add_count = 0;
+ for (size_t i = 0; i < rhs._set.size(); ++i) {
+ auto v = rhs._set[i];
+ if (_set.erase(v) == 0) {
+ values_to_add[add_count++] = v;
}
}
- _convert_to_smaller_type();
+
+ if (_set.size() + add_count <= SET_TYPE_THRESHOLD) {
+ _set.insert_many(values_to_add.data(), add_count);
+ _convert_to_smaller_type();
+ } else {
+ _convert_set_to_bitmap();
+ _bitmap->addMany(add_count, values_to_add.data());
+ }
break;
}
break;
@@ -1663,8 +2036,112 @@ public:
return false;
}
- // true if contains a value that belongs to the range [left, right].
- bool contains_any(uint64_t left, uint64_t right) const;
+ bool intersects(const BitmapValue& rhs) const {
+ switch (rhs._type) {
+ case EMPTY:
+ return false;
+ case SINGLE:
+ return contains(rhs._sv);
+ case BITMAP:
+ switch (_type) {
+ case EMPTY:
+ return false;
+ case SINGLE:
+ return rhs._bitmap->contains(_sv);
+ case BITMAP:
+ return _bitmap->intersect(*rhs._bitmap);
+ case SET:
+ for (auto v : _set) {
+ if (rhs._bitmap->contains(v)) {
+ return true;
+ }
+ }
+ return false;
+ }
+ break;
+ case SET:
+ switch (_type) {
+ case EMPTY:
+ return false;
+ case SINGLE:
+ return rhs._set.contains(_sv);
+ case BITMAP:
+ for (auto v : rhs._set) {
+ if (_bitmap->contains(v)) {
+ return true;
+ }
+ }
+ return false;
+ case SET: {
+ const auto& smaller = _set.size() <= rhs._set.size() ? _set :
rhs._set;
+ const auto& larger = _set.size() <= rhs._set.size() ? rhs._set
: _set;
+ for (auto v : smaller) {
+ if (larger.contains(v)) {
+ return true;
+ }
+ }
+ return false;
+ }
+ }
+ }
+ return false;
+ }
+
+ bool contains_all(const BitmapValue& rhs) const {
+ if (rhs.cardinality() == 0) {
+ return true;
+ }
+
+ switch (rhs._type) {
+ case EMPTY:
+ return true;
+ case SINGLE:
+ return contains(rhs._sv);
+ case BITMAP:
+ switch (_type) {
+ case EMPTY:
+ return false;
+ case SINGLE:
+ return rhs._bitmap->cardinality() == 0 ||
+ (rhs._bitmap->cardinality() == 1 &&
rhs._bitmap->contains(_sv));
+ case SET:
+ if (rhs._bitmap->cardinality() > _set.size()) {
+ return false;
+ }
+ for (auto v : *rhs._bitmap) {
+ if (!_set.contains(v)) {
+ return false;
+ }
+ }
+ return true;
+ case BITMAP:
+ return rhs._bitmap->isSubset(*_bitmap);
+ }
+ break;
+ case SET:
+ switch (_type) {
+ case EMPTY:
+ return false;
+ case SINGLE:
+ return rhs._set.size() == 1 && rhs._set.contains(_sv);
+ case BITMAP:
+ for (auto v : rhs._set) {
+ if (!_bitmap->contains(v)) {
+ return false;
+ }
+ }
+ return true;
+ case SET:
+ for (auto v : rhs._set) {
+ if (!_set.contains(v)) {
+ return false;
+ }
+ }
+ return true;
+ }
+ }
+ return false;
+ }
uint64_t cardinality() const {
switch (_type) {
@@ -1732,8 +2209,10 @@ public:
}
case SET: {
uint64_t cardinality = 0;
- for (auto v : _set) {
- if (rhs._set.contains(v)) {
+ const auto& smaller = _set.size() <= rhs._set.size() ? _set :
rhs._set;
+ const auto& larger = _set.size() <= rhs._set.size() ? rhs._set
: _set;
+ for (auto v : smaller) {
+ if (larger.contains(v)) {
++cardinality;
}
}
@@ -1795,13 +2274,7 @@ public:
return cardinality;
}
case SET: {
- uint64_t cardinality = _set.size();
- for (auto v : _set) {
- if (!rhs._set.contains(v)) {
- ++cardinality;
- }
- }
- return cardinality;
+ return _set.size() + rhs._set.size() - and_cardinality(rhs);
}
}
}
@@ -1859,13 +2332,7 @@ public:
return cardinality;
}
case SET: {
- uint64_t cardinality = _set.size();
- for (auto v : rhs._set) {
- if (_set.contains(v)) {
- cardinality -= 1;
- }
- }
- return cardinality;
+ return _set.size() - and_cardinality(rhs);
}
}
}
@@ -1924,9 +2391,14 @@ public:
++dst;
*dst = static_cast<uint8_t>(_set.size());
++dst;
- for (auto v : _set) {
- encode_fixed64_le(reinterpret_cast<uint8_t*>(dst), v);
- dst += sizeof(uint64_t);
+ {
+ // SET serialization does not guarantee a canonical value
order. The old phmap-backed
+ // SET order also depended on bucket state, so write the
current inline order directly.
+ // TypeCode::SET(1 byte) | count(1 byte) | uint64 values in
little-endian order.
+ for (auto v : _set) {
+ encode_fixed64_le(reinterpret_cast<uint8_t*>(dst), v);
+ dst += sizeof(uint64_t);
+ }
}
break;
case BITMAP:
@@ -1938,6 +2410,7 @@ public:
// Deserialize a bitmap value from `src`.
// Return false if `src` begins with unknown type code, true otherwise.
bool deserialize(const char* src) {
+ reset();
switch (*src) {
case BitmapTypeCode::EMPTY:
_type = EMPTY;
@@ -1947,6 +2420,7 @@ public:
_sv = decode_fixed32_le(reinterpret_cast<const uint8_t*>(src + 1));
if (config::enable_set_in_bitmap_value) {
_type = SET;
+ _set.clear();
_set.insert(_sv);
}
break;
@@ -1955,6 +2429,7 @@ public:
_sv = decode_fixed64_le(reinterpret_cast<const uint8_t*>(src + 1));
if (config::enable_set_in_bitmap_value) {
_type = SET;
+ _set.clear();
_set.insert(_sv);
}
break;
@@ -1980,51 +2455,34 @@ public:
throw Exception(ErrorCode::INTERNAL_ERROR,
"bitmap value with incorrect set count, count:
{}", count);
}
- _set.reserve(count);
- for (uint8_t i = 0; i != count; ++i, src += sizeof(uint64_t)) {
- _set.insert(decode_fixed64_le(reinterpret_cast<const
uint8_t*>(src)));
- }
- if (_set.size() != count) {
+ if (!_set.read(src, count)) {
throw Exception(ErrorCode::INTERNAL_ERROR,
- "bitmap value with incorrect set count, count:
{}, set size: {}",
- count, _set.size());
+ "bitmap value with duplicated set values,
count: {}", count);
}
+ src += sizeof(uint64_t) * count;
if (!config::enable_set_in_bitmap_value) {
- _prepare_bitmap_for_write();
- for (auto v : _set) {
- _bitmap->add(v);
- }
- _type = BITMAP;
- _set.clear();
+ _convert_set_to_bitmap();
}
break;
}
case BitmapTypeCode::SET_V2: {
- uint32_t size = 0;
- memcpy(&size, src + 1, sizeof(uint32_t));
+ uint32_t size = decode_fixed32_le(reinterpret_cast<const
uint8_t*>(src + 1));
src += sizeof(uint32_t) + 1;
if (!config::enable_set_in_bitmap_value || size >
SET_TYPE_THRESHOLD) {
_type = BITMAP;
_prepare_bitmap_for_write();
- for (int i = 0; i < size; ++i) {
- uint64_t key {};
- memcpy(&key, src, sizeof(uint64_t));
- _bitmap->add(key);
- src += sizeof(uint64_t);
+ if (size > 0) {
+ std::vector<uint64_t> values(size);
+ decode_fixed64_le_array(values.data(), src, size);
+ _bitmap->addMany(size, values.data());
+ src += sizeof(uint64_t) * size;
}
} else {
_type = SET;
- _set.reserve(size);
-
- for (int i = 0; i < size; ++i) {
- uint64_t key {};
- memcpy(&key, src, sizeof(uint64_t));
- _set.insert(key);
- src += sizeof(uint64_t);
- }
+ _set.read(src, size, true);
}
break;
}
@@ -2087,10 +2545,11 @@ public:
} iter_ctx;
iter_ctx.ss = &ss;
- std::vector<uint64_t> values(_set.begin(), _set.end());
- std::sort(values.begin(), values.end());
+ std::array<uint64_t, SET_TYPE_THRESHOLD> values {};
+ _set.copy_to_sorted(values.data());
- for (auto v : values) {
+ for (size_t i = 0; i < _set.size(); ++i) {
+ auto v = values[i];
if (iter_ctx.first) {
iter_ctx.first = false;
} else {
@@ -2171,14 +2630,12 @@ public:
}
case SET: {
int64_t count = 0;
- std::vector<uint64_t> values(_set.begin(), _set.end());
- std::sort(values.begin(), values.end());
- for (auto it = values.begin(); it != values.end(); ++it) {
- if (*it < range_start || *it >= range_end) {
- continue;
+ for (size_t i = 0; i < _set.size(); ++i) {
+ uint64_t v = _set[i];
+ if (v >= range_start && v < range_end) {
+ ret_bitmap->add(v);
+ ++count;
}
- ret_bitmap->add(*it);
- ++count;
}
return count;
}
@@ -2194,11 +2651,14 @@ public:
*/
int64_t sub_limit(const int64_t& range_start, const int64_t&
cardinality_limit,
BitmapValue* ret_bitmap) const {
+ if (cardinality_limit <= 0) {
+ return 0;
+ }
switch (_type) {
case EMPTY:
return 0;
case SINGLE: {
- //only single value, so range_start must less than _sv
+ // Only single value, so range_start must be less than or equal to
_sv.
if (range_start > _sv) {
return 0;
} else {
@@ -2222,22 +2682,26 @@ public:
return count;
}
case SET: {
- int64_t count = 0;
-
- std::vector<uint64_t> values(_set.begin(), _set.end());
- std::sort(values.begin(), values.end());
- for (auto it = values.begin(); it != values.end(); ++it) {
- if (*it < range_start) {
+ std::array<uint64_t, SET_TYPE_THRESHOLD> values {};
+ size_t count = 0;
+ for (size_t i = 0; i < _set.size(); ++i) {
+ auto v = _set[i];
+ if (v < range_start) {
continue;
}
- if (count < cardinality_limit) {
- ret_bitmap->add(*it);
- ++count;
- } else {
- break;
- }
+ values[count++] = v;
}
- return count;
+
+ const auto output_count = std::min(count,
static_cast<size_t>(cardinality_limit));
+ if (output_count == 0) {
+ return 0;
+ }
+ if (output_count < count) {
+ std::nth_element(values.begin(), values.begin() + output_count,
+ values.begin() + count);
+ }
+ ret_bitmap->add_many(values.data(), output_count);
+ return output_count;
}
}
return 0;
@@ -2250,6 +2714,10 @@ public:
*/
int64_t offset_limit(const int64_t& offset, const int64_t& limit,
BitmapValue* ret_bitmap) const {
+ if (limit <= 0) {
+ return 0;
+ }
+
switch (_type) {
case EMPTY:
return 0;
@@ -2266,7 +2734,7 @@ public:
break;
}
if (_type == BITMAP) {
- if (std::abs(offset) >= _bitmap->cardinality()) {
+ if (std::abs(offset) > _bitmap->cardinality()) {
return 0;
}
int64_t abs_offset = offset;
@@ -2285,7 +2753,7 @@ public:
}
return count;
} else {
- if (std::abs(offset) > _set.size()) {
+ if (std::abs(offset) > _set.size() || limit <= 0) {
return 0;
}
@@ -2293,25 +2761,28 @@ public:
if (offset < 0) {
abs_offset = _set.size() + offset;
}
+ if (abs_offset >= _set.size()) {
+ return 0;
+ }
- std::vector<uint64_t> values(_set.begin(), _set.end());
- std::sort(values.begin(), values.end());
+ std::array<uint64_t, SET_TYPE_THRESHOLD> values {};
+ memcpy(values.data(), _set.data(), sizeof(uint64_t) * _set.size());
- int64_t count = 0;
- size_t index = 0;
- for (auto v : values) {
- if (index < abs_offset) {
- ++index;
- continue;
- }
- if (count == limit || index == values.size()) {
- break;
- }
- ++count;
- ++index;
- ret_bitmap->add(v);
+ const auto start = static_cast<size_t>(abs_offset);
+ const auto end = std::min(_set.size(), start +
static_cast<size_t>(limit));
+ if (end == start) {
+ return 0;
}
- return count;
+
+ if (end < _set.size()) {
+ std::nth_element(values.begin(), values.begin() + end,
+ values.begin() + _set.size());
+ }
+ if (start > 0) {
+ std::nth_element(values.begin(), values.begin() + start,
values.begin() + end);
+ }
+ ret_bitmap->add_many(values.data() + start, end - start);
+ return end - start;
}
}
@@ -2325,16 +2796,17 @@ public:
break;
}
case BITMAP: {
- for (auto it = _bitmap->begin(); it != _bitmap->end(); ++it) {
- data.emplace_back(*it);
- }
+ const auto old_size = data.size();
+ const auto cardinality = _bitmap->cardinality();
+ data.resize(old_size + cardinality);
+ _bitmap->toUint64Array(reinterpret_cast<uint64_t*>(data.data() +
old_size));
break;
}
case SET: {
- std::vector<uint64_t> values(_set.begin(), _set.end());
- std::sort(values.begin(), values.end());
- for (auto v : values) {
- data.emplace_back(v);
+ std::array<uint64_t, SET_TYPE_THRESHOLD> values {};
+ _set.copy_to_sorted(values.data());
+ for (size_t i = 0; i < _set.size(); ++i) {
+ data.emplace_back(values[i]);
}
break;
}
@@ -2354,7 +2826,6 @@ public:
b_iterator begin() const;
b_iterator end() const;
- b_iterator lower_bound(uint64_t val) const;
private:
void _convert_to_smaller_type() {
@@ -2372,6 +2843,7 @@ private:
_sv = _bitmap->minimum();
} else {
_type = SET;
+ _set.clear();
for (auto v : *_bitmap) {
_set.insert(v);
}
@@ -2382,6 +2854,8 @@ private:
_type = SINGLE;
_sv = *_set.begin();
_set.clear();
+ } else if (_set.empty()) {
+ _type = EMPTY;
}
}
}
@@ -2426,14 +2900,12 @@ private:
_is_shared = false;
}
- void _convert_to_bitmap_if_need() {
- if (_type != SET || _set.size() <= SET_TYPE_THRESHOLD) {
- return;
- }
+ // Promote the current SET payload to roaring. Use this only when the
caller has already
+ // decided SET is no longer the right representation, for example add()
detects a new value
+ // cannot fit in the inline set, or an operation intentionally switches to
roaring first.
+ void _convert_set_to_bitmap() {
_prepare_bitmap_for_write();
- for (auto v : _set) {
- _bitmap->add(v);
- }
+ _bitmap->addMany(_set.size(), _set.data());
_type = BITMAP;
_set.clear();
}
@@ -2447,7 +2919,7 @@ private:
uint64_t _sv = 0; // store the single value when _type == SINGLE
// !FIXME: We should rethink the logic about _bitmap and _is_shared
mutable std::shared_ptr<detail::Roaring64Map> _bitmap; // used when _type
== BITMAP
- SetContainer<uint64_t> _set;
+ BitmapSmallSet _set;
BitmapDataType _type {EMPTY};
// Indicate whether the state is shared among multi BitmapValue object
mutable bool _is_shared = true;
@@ -2573,34 +3045,10 @@ public:
bool operator!=(const BitmapValueIterator& other) const { return !(*this
== other); }
- /**
- * Move the iterator to the first value >= `val`.
- */
- BitmapValueIterator& move(uint64_t val) {
- switch (_bitmap._type) {
- case BitmapValue::BitmapDataType::SINGLE:
- if (_sv < val) {
- _end = true;
- }
- break;
- case BitmapValue::BitmapDataType::BITMAP:
- if (!_iter->move(val)) {
- _end = true;
- }
- break;
- case BitmapValue::BitmapDataType::SET: {
- throw Exception(Status::FatalError("BitmapValue with set do not
support move"));
- }
- default:
- break;
- }
- return *this;
- }
-
private:
const BitmapValue& _bitmap;
detail::Roaring64MapSetBitForwardIterator* _iter = nullptr;
- BitmapValue::SetContainer<uint64_t>::const_iterator _set_iter;
+ BitmapSmallSet::const_iterator _set_iter;
uint64_t _sv = 0;
bool _end = false;
};
@@ -2613,25 +3061,4 @@ inline BitmapValueIterator BitmapValue::end() const {
return {*this, true};
}
-inline BitmapValueIterator BitmapValue::lower_bound(uint64_t val) const {
- return BitmapValueIterator(*this).move(val);
-}
-
-inline bool BitmapValue::contains_any(uint64_t left, uint64_t right) const {
- if (left > right) {
- return false;
- }
-
- if (_type == SET) {
- for (auto v : _set) {
- if (v >= left && v <= right) {
- return true;
- }
- }
- return false;
- }
- auto it = lower_bound(left);
- return it != end() && *it <= right;
-}
-
} // namespace doris
diff --git a/be/src/exprs/function/function_bitmap.cpp
b/be/src/exprs/function/function_bitmap.cpp
index 35341f29764..6213066e0e1 100644
--- a/be/src/exprs/function/function_bitmap.cpp
+++ b/be/src/exprs/function/function_bitmap.cpp
@@ -323,10 +323,15 @@ struct BitmapFromArray {
const auto& nested_column_data = static_cast<const
ColumnType&>(nested_column).get_data();
auto size = offset_column_data.size();
res.reserve(size);
- std::vector<uint64_t> bits;
+ // Preserve the nested column's native integer type here.
+ // For Array<Int32>/Array<UInt32>-like inputs can reach the 32-bit
`add_many` fast path
+ // instead of widening every element to uint64_t first.
+ using ValueType = typename ColumnType::value_type;
+ std::vector<ValueType> bits;
for (size_t i = 0; i < size; ++i) {
auto curr_offset = offset_column_data[i];
auto prev_offset = offset_column_data[i - 1];
+ bits.reserve(curr_offset - prev_offset);
for (auto j = prev_offset; j < curr_offset; ++j) {
auto data = nested_column_data[j];
// invaild value
@@ -904,25 +909,19 @@ struct BitmapHasAny {
static void vector_vector(const TData& lvec, const TData& rvec, ResTData&
res) {
size_t size = lvec.size();
for (size_t i = 0; i < size; ++i) {
- auto bitmap = lvec[i];
- bitmap &= rvec[i];
- res[i] = bitmap.cardinality() != 0;
+ res[i] = lvec[i].intersects(rvec[i]);
}
}
static void vector_scalar(const TData& lvec, const BitmapValue& rval,
ResTData& res) {
size_t size = lvec.size();
for (size_t i = 0; i < size; ++i) {
- auto bitmap = lvec[i];
- bitmap &= rval;
- res[i] = bitmap.cardinality() != 0;
+ res[i] = lvec[i].intersects(rval);
}
}
static void scalar_vector(const BitmapValue& lval, const TData& rvec,
ResTData& res) {
size_t size = rvec.size();
for (size_t i = 0; i < size; ++i) {
- auto bitmap = lval;
- bitmap &= rvec[i];
- res[i] = bitmap.cardinality() != 0;
+ res[i] = lval.intersects(rvec[i]);
}
}
};
@@ -942,28 +941,19 @@ struct BitmapHasAll {
static void vector_vector(const TData& lvec, const TData& rvec, ResTData&
res) {
size_t size = lvec.size();
for (size_t i = 0; i < size; ++i) {
- uint64_t lhs_cardinality = lvec[i].cardinality();
- auto bitmap = lvec[i];
- bitmap |= rvec[i];
- res[i] = bitmap.cardinality() == lhs_cardinality;
+ res[i] = lvec[i].contains_all(rvec[i]);
}
}
static void vector_scalar(const TData& lvec, const BitmapValue& rval,
ResTData& res) {
size_t size = lvec.size();
for (size_t i = 0; i < size; ++i) {
- uint64_t lhs_cardinality = lvec[i].cardinality();
- auto bitmap = lvec[i];
- bitmap |= rval;
- res[i] = bitmap.cardinality() == lhs_cardinality;
+ res[i] = lvec[i].contains_all(rval);
}
}
static void scalar_vector(const BitmapValue& lval, const TData& rvec,
ResTData& res) {
size_t size = rvec.size();
- uint64_t lhs_cardinality = lval.cardinality();
for (size_t i = 0; i < size; ++i) {
- auto bitmap = lval;
- bitmap |= rvec[i];
- res[i] = bitmap.cardinality() == lhs_cardinality;
+ res[i] = lval.contains_all(rvec[i]);
}
}
};
diff --git a/be/src/exprs/function/function_bitmap_min_or_max.h
b/be/src/exprs/function/function_bitmap_min_or_max.h
index 2132e6a44d4..76ebf4616b0 100644
--- a/be/src/exprs/function/function_bitmap_min_or_max.h
+++ b/be/src/exprs/function/function_bitmap_min_or_max.h
@@ -68,20 +68,24 @@ public:
private:
void execute_straight(const ColumnBitmap* date_column, ColumnInt64*
result_column,
NullMap& result_null_map, size_t input_rows_count)
const {
+ const auto& data = date_column->get_data();
+ auto& result_data = result_column->get_data();
+ result_data.resize(input_rows_count);
+
for (size_t i = 0; i < input_rows_count; i++) {
if (result_null_map[i]) {
- result_column->insert_default();
+ result_data[i] = 0;
continue;
}
- BitmapValue value = date_column->get_element(i);
+ const BitmapValue& value = data[i];
if (!value.cardinality()) {
result_null_map[i] = true;
- result_column->insert_default();
+ result_data[i] = 0;
continue;
}
-
result_column->insert(Field::create_field<TYPE_BIGINT>(Impl::calculate(value)));
+ result_data[i] = Impl::calculate(value);
}
}
};
diff --git a/be/src/util/coding.h b/be/src/util/coding.h
index 48a2a8532b0..26d6a2f827c 100644
--- a/be/src/util/coding.h
+++ b/be/src/util/coding.h
@@ -71,6 +71,21 @@ inline uint64_t decode_fixed64_le(const uint8_t* buf) {
return to_endian<std::endian::little>(res);
}
+inline void decode_fixed64_le_array(uint64_t* dst, const void* src, size_t n) {
+ if (n == 0) {
+ return;
+ }
+ if constexpr (std::endian::native == std::endian::little) {
+ memcpy(dst, src, sizeof(uint64_t) * n);
+ } else {
+ const auto* ptr = reinterpret_cast<const uint8_t*>(src);
+ for (size_t i = 0; i < n; ++i) {
+ dst[i] = decode_fixed64_le(ptr);
+ ptr += sizeof(uint64_t);
+ }
+ }
+}
+
inline uint128_t decode_fixed128_le(const uint8_t* buf) {
uint128_t res;
memcpy(&res, buf, sizeof(res));
diff --git a/be/test/core/block/column_complex_test.cpp
b/be/test/core/block/column_complex_test.cpp
index 3a2629474f9..4ced4c4f8e7 100644
--- a/be/test/core/block/column_complex_test.cpp
+++ b/be/test/core/block/column_complex_test.cpp
@@ -60,10 +60,10 @@ TEST(ColumnComplexTest, GetDataAtTest) {
column_bitmap_verify->insert_default();
column_hll_verify->insert_default();
column_quantile_state_verify->insert_many_defaults(1);
- ASSERT_EQ(column_bitmap_verify->byte_size(), 80);
+ ASSERT_EQ(column_bitmap_verify->byte_size(), sizeof(BitmapValue));
ASSERT_EQ(column_hll_verify->byte_size(), 64);
ASSERT_EQ(column_quantile_state_verify->byte_size(), 64);
- ASSERT_EQ(column_bitmap_verify->allocated_bytes(), 80);
+ ASSERT_EQ(column_bitmap_verify->allocated_bytes(), sizeof(BitmapValue));
ASSERT_EQ(column_hll_verify->allocated_bytes(), 64);
ASSERT_EQ(column_quantile_state_verify->allocated_bytes(), 64);
std::cout << "1. test byte_size/allocated_bytes empty success" <<
std::endl;
diff --git a/be/test/core/value/bitmap_value_test.cpp
b/be/test/core/value/bitmap_value_test.cpp
index 1f89539c366..b281d71a443 100644
--- a/be/test/core/value/bitmap_value_test.cpp
+++ b/be/test/core/value/bitmap_value_test.cpp
@@ -78,6 +78,27 @@ TEST(BitmapValueTest, Roaring64Map_ctors) {
EXPECT_FALSE(roaring64_map3.contains(uint32_t(0)));
}
+TEST(BitmapValueTest, Roaring64Map_intersect) {
+ constexpr uint64_t high32 = uint64_t {1} << 32;
+ const std::vector<uint64_t> one_map {1, 2};
+ const std::vector<uint64_t> one_map_overlap {2, 3};
+ const std::vector<uint64_t> one_map_disjoint {3, 4};
+ const std::vector<uint64_t> other_map {high32 + 1, high32 + 2};
+ const std::vector<uint64_t> two_maps {1, 2, high32 + 1, high32 + 2};
+
+ detail::Roaring64Map bitmap_one_map(one_map.size(), one_map.data());
+ detail::Roaring64Map bitmap_overlap(one_map_overlap.size(),
one_map_overlap.data());
+ detail::Roaring64Map bitmap_disjoint(one_map_disjoint.size(),
one_map_disjoint.data());
+ detail::Roaring64Map bitmap_other_map(other_map.size(), other_map.data());
+ detail::Roaring64Map bitmap_two_maps(two_maps.size(), two_maps.data());
+
+ EXPECT_TRUE(bitmap_one_map.intersect(bitmap_overlap));
+ EXPECT_FALSE(bitmap_one_map.intersect(bitmap_disjoint));
+ EXPECT_FALSE(bitmap_one_map.intersect(bitmap_other_map));
+ EXPECT_TRUE(bitmap_two_maps.intersect(bitmap_one_map));
+ EXPECT_TRUE(bitmap_one_map.intersect(bitmap_two_maps));
+}
+
TEST(BitmapValueTest, Roaring64Map_add_remove) {
detail::Roaring64Map roaring64_map;
const std::vector<uint32_t> values({1, 3, 5, 7, 9, 2, 4, 6, 8, 1, 8, 9});
@@ -252,17 +273,6 @@ TEST(BitmapValueTest, Roaring64Map_iterators) {
EXPECT_TRUE(iter != end);
iter++;
}
-
- iter = roaring64_map.begin();
- EXPECT_TRUE(iter.move(2));
- EXPECT_TRUE(iter.move(4294967296));
- EXPECT_FALSE(iter.move(4294967299));
-
- iter = roaring64_map.begin();
- auto iter2 = roaring64_map.begin();
- iter.move(3);
- iter2.move(3);
- EXPECT_TRUE(iter == iter2);
}
TEST(BitmapValueTest, set) {
@@ -359,6 +369,80 @@ TEST(BitmapValueTest, add) {
config::enable_set_in_bitmap_value = false;
}
+TEST(BitmapValueTest, small_set_try_insert_many_over_capacity) {
+ BitmapSmallSet set;
+ const uint64_t initial_values[] = {1, 2, 3};
+ const uint64_t duplicate_values[] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3,
1, 2, 3,
+ 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3,
1, 2, 3};
+ const uint64_t new_values[] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18,
+ 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30, 31, 32, 33};
+
+ EXPECT_TRUE(set.try_insert_many(initial_values,
std::size(initial_values)));
+ EXPECT_TRUE(set.try_insert_many(duplicate_values,
std::size(duplicate_values)));
+ EXPECT_EQ(3, set.size());
+ EXPECT_FALSE(set.try_insert_many(new_values, std::size(new_values)));
+ EXPECT_EQ(3, set.size());
+}
+
+TEST(BitmapValueTest, add_many_all_representations) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+ config::enable_set_in_bitmap_value = true;
+
+ const uint64_t one_value[] = {1};
+ const uint64_t small_values[] = {1, 2, 2, 3};
+ std::vector<uint64_t> bitmap_values(33);
+ std::iota(bitmap_values.begin(), bitmap_values.end(), 1);
+
+ BitmapValue empty;
+ empty.add_many(one_value, 0);
+ EXPECT_TRUE(empty.empty());
+ empty.add_many(one_value, std::size(one_value));
+ EXPECT_EQ(BitmapValue::SINGLE, empty._type);
+
+ BitmapValue empty_to_set;
+ empty_to_set.add_many(small_values, std::size(small_values));
+ EXPECT_EQ(BitmapValue::SET, empty_to_set._type);
+ EXPECT_EQ(3, empty_to_set.cardinality());
+
+ BitmapValue empty_to_bitmap;
+ empty_to_bitmap.add_many(bitmap_values.data(), bitmap_values.size());
+ EXPECT_EQ(BitmapValue::BITMAP, empty_to_bitmap._type);
+
+ BitmapValue single_to_set(1);
+ single_to_set.add_many(small_values, std::size(small_values));
+ EXPECT_EQ(BitmapValue::SET, single_to_set._type);
+ EXPECT_EQ(3, single_to_set.cardinality());
+
+ BitmapValue single_to_bitmap(uint64_t {0});
+ single_to_bitmap.add_many(bitmap_values.data(), bitmap_values.size());
+ EXPECT_EQ(BitmapValue::BITMAP, single_to_bitmap._type);
+ EXPECT_EQ(34, single_to_bitmap.cardinality());
+
+ empty_to_bitmap.add_many(one_value, std::size(one_value));
+ EXPECT_EQ(33, empty_to_bitmap.cardinality());
+
+ std::vector<uint64_t> set_values(31);
+ std::iota(set_values.begin(), set_values.end(), 0);
+ BitmapValue set_to_bitmap(set_values);
+ const uint64_t duplicates[] = {0, 1};
+ const uint64_t overflow_values[] = {31, 33};
+ set_to_bitmap.add_many(duplicates, std::size(duplicates));
+ EXPECT_EQ(BitmapValue::SET, set_to_bitmap._type);
+ set_to_bitmap.add_many(overflow_values, std::size(overflow_values));
+ EXPECT_EQ(BitmapValue::BITMAP, set_to_bitmap._type);
+ EXPECT_EQ(33, set_to_bitmap.cardinality());
+
+ config::enable_set_in_bitmap_value = false;
+ BitmapValue no_set_empty;
+ no_set_empty.add_many(small_values, std::size(small_values));
+ EXPECT_EQ(BitmapValue::BITMAP, no_set_empty._type);
+ BitmapValue no_set_single(uint64_t {0});
+ no_set_single.add_many(one_value, std::size(one_value));
+ EXPECT_EQ(BitmapValue::BITMAP, no_set_single._type);
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
void check_bitmap_value_operator(const BitmapValue& left, const BitmapValue&
right) {
auto left_cardinality = left.cardinality();
auto right_cardinality = right.cardinality();
@@ -492,6 +576,88 @@ TEST(BitmapValueTest, operators) {
config::enable_set_in_bitmap_value = false;
}
+TEST(BitmapValueTest, bitmap_operator_cow_with_set_rhs) {
+ config::enable_set_in_bitmap_value = true;
+
+ std::vector<uint64_t> values(128);
+ std::iota(values.begin(), values.end(), 0);
+
+ BitmapValue bitmap;
+ bitmap.add_many(values.data(), values.size());
+
+ BitmapValue rhs_set({1, 2, 200});
+
+ BitmapValue copied = bitmap;
+ bitmap -= rhs_set;
+ EXPECT_FALSE(bitmap.contains(1));
+ EXPECT_FALSE(bitmap.contains(2));
+ EXPECT_TRUE(copied.contains(1));
+ EXPECT_TRUE(copied.contains(2));
+
+ bitmap = copied;
+ copied = bitmap;
+ bitmap |= rhs_set;
+ EXPECT_TRUE(copied.contains(1));
+ EXPECT_TRUE(copied.contains(2));
+ EXPECT_FALSE(copied.contains(200));
+
+ bitmap = copied;
+ copied = bitmap;
+ bitmap ^= BitmapValue(1);
+ EXPECT_FALSE(bitmap.contains(1));
+ EXPECT_TRUE(copied.contains(1));
+
+ config::enable_set_in_bitmap_value = false;
+}
+
+TEST(BitmapValueTest, bitmap_xor_single_and_set) {
+ config::enable_set_in_bitmap_value = true;
+
+ BitmapValue lhs_single(1);
+ lhs_single ^= BitmapValue(2);
+ EXPECT_STREQ("1,2", lhs_single.to_string().c_str());
+
+ lhs_single = BitmapValue(1);
+ lhs_single ^= BitmapValue({2, 3});
+ EXPECT_STREQ("1,2,3", lhs_single.to_string().c_str());
+
+ lhs_single = BitmapValue(1);
+ lhs_single ^= BitmapValue({1, 2});
+ EXPECT_STREQ("2", lhs_single.to_string().c_str());
+
+ config::enable_set_in_bitmap_value = false;
+}
+
+TEST(BitmapValueTest, bitmap_xor_same_set_returns_empty) {
+ config::enable_set_in_bitmap_value = true;
+
+ BitmapValue lhs({1, 2});
+ lhs ^= BitmapValue({1, 2});
+
+ EXPECT_EQ(0, lhs.cardinality());
+ EXPECT_EQ(BitmapTypeCode::EMPTY, lhs.get_type_code());
+
+ config::enable_set_in_bitmap_value = false;
+}
+
+TEST(BitmapValueTest, bitmap_xor_set_bitmap_clear_stale_set) {
+ config::enable_set_in_bitmap_value = true;
+
+ BitmapValue lhs({1, 2});
+ std::vector<uint64_t> rhs_values(33);
+ std::iota(rhs_values.begin(), rhs_values.end(), 1);
+ BitmapValue rhs(rhs_values);
+
+ lhs ^= rhs;
+ for (uint64_t v = 3; v <= 32; ++v) {
+ lhs.remove(v);
+ }
+
+ EXPECT_STREQ("33", lhs.to_string().c_str());
+
+ config::enable_set_in_bitmap_value = false;
+}
+
void check_bitmap_equal(const BitmapValue& left, const BitmapValue& right) {
EXPECT_EQ(left.cardinality(), right.cardinality());
EXPECT_EQ(left.minimum(), right.minimum());
@@ -721,6 +887,18 @@ TEST(BitmapValueTest, sub_range_limit) {
config::enable_set_in_bitmap_value = false;
}
+TEST(BitmapValueTest, offset_limit_negative_cardinality_for_set) {
+ config::enable_set_in_bitmap_value = true;
+
+ BitmapValue bitmap({1, 2, 3});
+ BitmapValue out;
+ auto ret = bitmap.offset_limit(-3, 2, &out);
+ EXPECT_EQ(ret, 2);
+ EXPECT_STREQ("1,2", out.to_string().c_str());
+
+ config::enable_set_in_bitmap_value = false;
+}
+
void bitmap_checker_for_all_type(const std::function<void(const
BitmapValue&)>& checker) {
BitmapValue bitmap_empty;
BitmapValue bitmap_single(1);
@@ -913,6 +1091,24 @@ TEST(BitmapValueTest, bitmap_union) {
config::enable_set_in_bitmap_value = old_config;
}
+TEST(BitmapValueTest, fastunion_set_with_bitmap) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+ config::enable_set_in_bitmap_value = true;
+
+ std::vector<uint64_t> bitmap_values(33);
+ std::iota(bitmap_values.begin(), bitmap_values.end(), 3);
+ BitmapValue bitmap(bitmap_values);
+ BitmapValue set({1, 2});
+
+ set.fastunion({&bitmap});
+ EXPECT_EQ(BitmapValue::BITMAP, set._type);
+ EXPECT_EQ(35, set.cardinality());
+ EXPECT_TRUE(set.contains(1));
+ EXPECT_TRUE(set.contains(35));
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
TEST(BitmapValueTest, bitmap_intersect) {
BitmapValue empty;
BitmapValue single(1024);
@@ -976,6 +1172,51 @@ TEST(BitmapValueTest, bitmap_intersect) {
EXPECT_EQ(2, bitmap6.cardinality());
}
+TEST(BitmapValueTest, bitmap_intersects_all_representations) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+
+ config::enable_set_in_bitmap_value = false;
+ std::vector<uint64_t> bitmap_values(33);
+ std::iota(bitmap_values.begin(), bitmap_values.end(), 0);
+ std::vector<uint64_t> bitmap_overlap_values(33);
+ std::iota(bitmap_overlap_values.begin(), bitmap_overlap_values.end(), 32);
+ std::vector<uint64_t> bitmap_disjoint_values(33);
+ std::iota(bitmap_disjoint_values.begin(), bitmap_disjoint_values.end(),
100);
+ BitmapValue bitmap(bitmap_values);
+ BitmapValue bitmap_overlap(bitmap_overlap_values);
+ BitmapValue bitmap_disjoint(bitmap_disjoint_values);
+ BitmapValue single(1);
+ BitmapValue single_absent(200);
+ BitmapValue empty;
+
+ config::enable_set_in_bitmap_value = true;
+ BitmapValue set({1, 2, 3});
+ BitmapValue set_disjoint({4, 5});
+
+ EXPECT_FALSE(bitmap.intersects(empty));
+ EXPECT_FALSE(empty.intersects(single));
+ EXPECT_TRUE(bitmap.intersects(single));
+ EXPECT_TRUE(set.intersects(single));
+
+ EXPECT_FALSE(empty.intersects(bitmap));
+ EXPECT_TRUE(single.intersects(bitmap));
+ EXPECT_FALSE(single_absent.intersects(bitmap));
+ EXPECT_TRUE(bitmap.intersects(bitmap_overlap));
+ EXPECT_FALSE(bitmap.intersects(bitmap_disjoint));
+ EXPECT_TRUE(set.intersects(bitmap));
+ EXPECT_FALSE(set_disjoint.intersects(bitmap_disjoint));
+
+ EXPECT_FALSE(empty.intersects(set));
+ EXPECT_TRUE(single.intersects(set));
+ EXPECT_FALSE(single_absent.intersects(set));
+ EXPECT_TRUE(bitmap.intersects(set));
+ EXPECT_FALSE(bitmap_disjoint.intersects(set));
+ EXPECT_TRUE(set.intersects(BitmapValue({2, 4})));
+ EXPECT_FALSE(set.intersects(set_disjoint));
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
std::string convert_bitmap_to_string(BitmapValue& bitmap) {
std::string buf;
buf.resize(bitmap.getSizeInBytes());
@@ -995,6 +1236,36 @@ BitmapValue deserialize_bitmap_from_string(const
std::string& buffer) {
return bitmap;
}
+TEST(BitmapValueTest, deserialize_reused_bitmap_to_set_then_promote) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+ config::enable_set_in_bitmap_value = true;
+
+ std::vector<uint64_t> stale_values(41);
+ std::iota(stale_values.begin(), stale_values.end(), 0);
+ BitmapValue reused(stale_values);
+ EXPECT_EQ(BitmapValue::BITMAP, reused._type);
+
+ std::vector<uint64_t> set_values {100, 101};
+ BitmapValue set_bitmap(set_values);
+ EXPECT_EQ(BitmapValue::SET, set_bitmap._type);
+ std::string set_buffer = convert_bitmap_to_string(set_bitmap);
+
+ EXPECT_TRUE(reused.deserialize(set_buffer.data()));
+ EXPECT_EQ(BitmapValue::SET, reused._type);
+ check_bitmap_values(reused, set_values);
+
+ std::vector<uint64_t> promote_values(31);
+ std::iota(promote_values.begin(), promote_values.end(), 102);
+ reused.add_many(promote_values.data(), promote_values.size());
+
+ std::vector<uint64_t> expected {100, 101};
+ expected.insert(expected.end(), promote_values.begin(),
promote_values.end());
+ EXPECT_EQ(BitmapValue::BITMAP, reused._type);
+ check_bitmap_values(reused, expected);
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
TEST(BitmapValueTest, bitmap_serde) {
auto old_enable_set = config::enable_set_in_bitmap_value;
auto old_serialize_version = config::bitmap_serialize_version;
@@ -1293,6 +1564,162 @@ TEST(BitmapValueTest, bitmap_value_iterator_test) {
}
}
+TEST(BitmapValueTest, contains_all_ignore_internal_representation) {
+ bool old_enable_set = config::enable_set_in_bitmap_value;
+
+ config::enable_set_in_bitmap_value = false;
+ BitmapValue lhs_bitmap({1, 2, 3});
+ BitmapValue rhs_bitmap({1, 2});
+ EXPECT_EQ(BitmapValue::BITMAP, lhs_bitmap._type);
+ EXPECT_EQ(BitmapValue::BITMAP, rhs_bitmap._type);
+
+ config::enable_set_in_bitmap_value = true;
+ BitmapValue lhs_set({1, 2, 3});
+ BitmapValue rhs_set({1, 2});
+ EXPECT_EQ(BitmapValue::SET, lhs_set._type);
+ EXPECT_EQ(BitmapValue::SET, rhs_set._type);
+
+ EXPECT_TRUE(lhs_set.contains_all(rhs_bitmap));
+ EXPECT_TRUE(lhs_bitmap.contains_all(rhs_set));
+ EXPECT_TRUE(lhs_bitmap.contains_all(rhs_bitmap));
+ EXPECT_FALSE(rhs_set.contains_all(lhs_bitmap));
+
+ BitmapValue empty_set_rhs({1, 3});
+ empty_set_rhs &= BitmapValue({2, 4});
+ EXPECT_EQ(0, empty_set_rhs.cardinality());
+ EXPECT_TRUE(lhs_set.contains_all(empty_set_rhs));
+ EXPECT_TRUE(BitmapValue().contains_all(empty_set_rhs));
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
+TEST(BitmapValueTest, contains_all_representation_branches) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+
+ config::enable_set_in_bitmap_value = false;
+ BitmapValue bitmap({1, 2, 3});
+ const uint64_t duplicated_one[] = {1, 1};
+ BitmapValue bitmap_one;
+ bitmap_one.add_many(duplicated_one, std::size(duplicated_one));
+ BitmapValue bitmap_two({1, 2});
+ BitmapValue bitmap_missing({1, 4});
+ BitmapValue single(1);
+
+ config::enable_set_in_bitmap_value = true;
+ BitmapValue set({1, 2, 3});
+ BitmapValue set_one;
+ set_one.add(1);
+ BitmapValue set_missing({1, 4});
+
+ EXPECT_FALSE(BitmapValue().contains_all(bitmap_two));
+ EXPECT_TRUE(single.contains_all(BitmapValue(1)));
+ EXPECT_FALSE(single.contains_all(BitmapValue(2)));
+ EXPECT_TRUE(single.contains_all(bitmap_one));
+ EXPECT_FALSE(single.contains_all(bitmap_two));
+ EXPECT_TRUE(set.contains_all(bitmap_two));
+ EXPECT_FALSE(set.contains_all(bitmap_missing));
+ EXPECT_TRUE(bitmap.contains_all(set_one));
+ EXPECT_FALSE(bitmap.contains_all(set_missing));
+ EXPECT_TRUE(single.contains_all(set_one));
+ EXPECT_FALSE(single.contains_all(set_missing));
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
+TEST(BitmapValueTest, deserialize_set_duplicate_values) {
+ bool old_enable_set = config::enable_set_in_bitmap_value;
+ config::enable_set_in_bitmap_value = true;
+
+ {
+ char data[] = {static_cast<char>(BitmapTypeCode::SET),
+ 2,
+ 7,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 7,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0};
+ BitmapValue bitmap;
+ EXPECT_THROW(bitmap.deserialize(data), Exception);
+ }
+
+ {
+ char data[] = {static_cast<char>(BitmapTypeCode::SET_V2),
+ 2,
+ 0,
+ 0,
+ 0,
+ 7,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 7,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0};
+ BitmapValue bitmap;
+ EXPECT_TRUE(bitmap.deserialize(data));
+ EXPECT_EQ(BitmapValue::SET, bitmap._type);
+ EXPECT_EQ(1, bitmap.cardinality());
+ EXPECT_TRUE(bitmap.contains(7));
+ }
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
+TEST(BitmapValueTest, deserialize_set_v2_to_bitmap) {
+ const auto old_enable_set = config::enable_set_in_bitmap_value;
+ config::enable_set_in_bitmap_value = false;
+
+ char data[] = {static_cast<char>(BitmapTypeCode::SET_V2),
+ 2,
+ 0,
+ 0,
+ 0,
+ 7,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 9,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0,
+ 0};
+ BitmapValue bitmap;
+ EXPECT_TRUE(bitmap.deserialize(data));
+ EXPECT_EQ(BitmapValue::BITMAP, bitmap._type);
+ EXPECT_EQ(2, bitmap.cardinality());
+ EXPECT_TRUE(bitmap.contains(7));
+ EXPECT_TRUE(bitmap.contains(9));
+
+ config::enable_set_in_bitmap_value = old_enable_set;
+}
+
TEST(BitmapValueTest, invalid_data) {
BitmapValue bitmap;
char data[] = {0x02, static_cast<char>(0xff), 0x03};
diff --git
a/regression-test/data/query_p0/sql_functions/bitmap_functions/test_bitmap_function.out
b/regression-test/data/query_p0/sql_functions/bitmap_functions/test_bitmap_function.out
index a162f381a4a..8fa306872e2 100644
---
a/regression-test/data/query_p0/sql_functions/bitmap_functions/test_bitmap_function.out
+++
b/regression-test/data/query_p0/sql_functions/bitmap_functions/test_bitmap_function.out
@@ -47,6 +47,27 @@ true
-- !sql --
false
+-- !sql --
+false
+
+-- !sql --
+true
+
+-- !sql --
+true
+
+-- !sql --
+true
+
+-- !sql --
+false
+
+-- !sql --
+true
+
+-- !sql --
+false
+
-- !sql_bitmap_hash1 --
1
diff --git
a/regression-test/suites/query_p0/sql_functions/bitmap_functions/test_bitmap_function.groovy
b/regression-test/suites/query_p0/sql_functions/bitmap_functions/test_bitmap_function.groovy
index fabfef875d3..2c6640a6515 100644
---
a/regression-test/suites/query_p0/sql_functions/bitmap_functions/test_bitmap_function.groovy
+++
b/regression-test/suites/query_p0/sql_functions/bitmap_functions/test_bitmap_function.groovy
@@ -16,6 +16,12 @@
// under the License.
suite("test_bitmap_function") {
+ def low_bitmap =
"0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32"
+ def overlap_bitmap =
"32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64"
+ def disjoint_bitmap =
"33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65"
+ def high_bitmap =
"4294967296,4294967297,4294967298,4294967299,4294967300,4294967301,4294967302,4294967303,4294967304,4294967305,4294967306,4294967307,4294967308,4294967309,4294967310,4294967311,4294967312,4294967313,4294967314,4294967315,4294967316,4294967317,4294967318,4294967319,4294967320,4294967321,4294967322,4294967323,4294967324,4294967325,4294967326,4294967327,4294967328"
+ def two_map_bitmap = "${low_bitmap},${high_bitmap}"
+
// BITMAP_AND
qt_sql """ select bitmap_count(bitmap_and(to_bitmap(1), to_bitmap(2))) cnt
"""
qt_sql """ select bitmap_count(bitmap_and(to_bitmap(1), to_bitmap(1))) cnt
"""
@@ -39,10 +45,17 @@ suite("test_bitmap_function") {
// BITMAP_HAS_ANY
qt_sql """ select bitmap_has_any(to_bitmap(1),to_bitmap(2)) cnt """
qt_sql """ select bitmap_has_any(to_bitmap(1),to_bitmap(1)) cnt """
+ qt_sql """ select bitmap_has_any(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${overlap_bitmap}')) cnt """
+ qt_sql """ select bitmap_has_any(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${disjoint_bitmap}')) cnt """
+ qt_sql """ select bitmap_has_any(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${high_bitmap}')) cnt """
+ qt_sql """ select bitmap_has_any(bitmap_from_string('${two_map_bitmap}'),
bitmap_from_string('${low_bitmap}')) cnt """
+ qt_sql """ select bitmap_has_any(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${two_map_bitmap}')) cnt """
// BITMAP_HAS_ALL
qt_sql """ select bitmap_has_all(bitmap_from_string("0, 1, 2"),
bitmap_from_string("1, 2")) cnt """
qt_sql """ select bitmap_has_all(bitmap_empty(), bitmap_from_string("1,
2")) cnt """
+ qt_sql """ select bitmap_has_all(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${low_bitmap}')) cnt """
+ qt_sql """ select bitmap_has_all(bitmap_from_string('${low_bitmap}'),
bitmap_from_string('${overlap_bitmap}')) cnt """
// BITMAP_HASH
qt_sql_bitmap_hash1 """ select bitmap_count(bitmap_hash('hello')) """
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
