tp: DBv2 - QueryExecutor
Bug:283763282
Change-Id: I1bc438e9232924cada020aa4fd9ec5b133e8d24d
diff --git a/Android.bp b/Android.bp
index 4265016..b1fa451 100644
--- a/Android.bp
+++ b/Android.bp
@@ -9402,6 +9402,7 @@
"src/trace_processor/db/column.cc",
"src/trace_processor/db/column_storage.cc",
"src/trace_processor/db/null_overlay.cc",
+ "src/trace_processor/db/query_executor.cc",
"src/trace_processor/db/table.cc",
"src/trace_processor/db/view.cc",
],
@@ -9449,6 +9450,7 @@
srcs: [
"src/trace_processor/db/column_storage_overlay_unittest.cc",
"src/trace_processor/db/compare_unittest.cc",
+ "src/trace_processor/db/query_executor_unittest.cc",
"src/trace_processor/db/view_unittest.cc",
],
}
diff --git a/BUILD b/BUILD
index f217e0a..6b1e011 100644
--- a/BUILD
+++ b/BUILD
@@ -1312,6 +1312,8 @@
"src/trace_processor/db/compare.h",
"src/trace_processor/db/null_overlay.cc",
"src/trace_processor/db/null_overlay.h",
+ "src/trace_processor/db/query_executor.cc",
+ "src/trace_processor/db/query_executor.h",
"src/trace_processor/db/table.cc",
"src/trace_processor/db/table.h",
"src/trace_processor/db/typed_column.h",
diff --git a/src/trace_processor/db/BUILD.gn b/src/trace_processor/db/BUILD.gn
index 1ef081a..de4dc7f 100644
--- a/src/trace_processor/db/BUILD.gn
+++ b/src/trace_processor/db/BUILD.gn
@@ -26,6 +26,8 @@
"compare.h",
"null_overlay.cc",
"null_overlay.h",
+ "query_executor.cc",
+ "query_executor.h",
"table.cc",
"table.h",
"typed_column.h",
@@ -54,6 +56,7 @@
sources = [
"column_storage_overlay_unittest.cc",
"compare_unittest.cc",
+ "query_executor_unittest.cc",
"view_unittest.cc",
]
deps = [
@@ -64,6 +67,8 @@
"../../base",
"../tables",
"../views",
+ "overlays",
+ "storage",
]
}
diff --git a/src/trace_processor/db/overlays/BUILD.gn b/src/trace_processor/db/overlays/BUILD.gn
index c35891f..21615b0 100644
--- a/src/trace_processor/db/overlays/BUILD.gn
+++ b/src/trace_processor/db/overlays/BUILD.gn
@@ -29,6 +29,7 @@
"../../../../gn:default_deps",
"../../../base",
"../../containers",
+ "../storage",
]
}
diff --git a/src/trace_processor/db/overlays/null_overlay.cc b/src/trace_processor/db/overlays/null_overlay.cc
index ca44204..3ecb317 100644
--- a/src/trace_processor/db/overlays/null_overlay.cc
+++ b/src/trace_processor/db/overlays/null_overlay.cc
@@ -39,6 +39,9 @@
if (op != OverlayOp::kIsNull)
return {std::move(res)};
+ if (res.CountSetBits() == 0)
+ return {non_null_->Not()};
+
BitVector not_non_null = non_null_->Not();
res.Or(not_non_null);
return {std::move(res)};
@@ -50,7 +53,7 @@
PERFETTO_DCHECK(t_iv.indices.size() <= non_null_->size());
if (op != OverlayOp::kOther)
- return BitVector();
+ return BitVector(t_iv.size(), false);
BitVector in_storage(static_cast<uint32_t>(t_iv.indices.size()), false);
@@ -81,7 +84,7 @@
OverlayOp op,
const TableIndexVector& t_iv_overlay_idx) const {
if (op == OverlayOp::kOther)
- return BitVector();
+ return BitVector(t_iv_overlay_idx.size(), false);
BitVector res(static_cast<uint32_t>(t_iv_overlay_idx.indices.size()), false);
if (op == OverlayOp::kIsNull) {
diff --git a/src/trace_processor/db/overlays/null_overlay_unittest.cc b/src/trace_processor/db/overlays/null_overlay_unittest.cc
index 9bec414..0c02ad7 100644
--- a/src/trace_processor/db/overlays/null_overlay_unittest.cc
+++ b/src/trace_processor/db/overlays/null_overlay_unittest.cc
@@ -77,7 +77,7 @@
BitVector lookup_bv =
overlay.IsStorageLookupRequired(OverlayOp::kIsNull, {table_idx});
- ASSERT_EQ(lookup_bv.size(), 0u);
+ ASSERT_EQ(lookup_bv.CountSetBits(), 0u);
}
TEST(NullOverlay, IsStorageLookupRequiredOtherOp) {
@@ -112,7 +112,7 @@
std::vector<uint32_t> table_idx{0, 3, 4};
BitVector idx_search_bv = overlay.IndexSearch(OverlayOp::kOther, {table_idx});
- ASSERT_EQ(idx_search_bv.size(), 0u);
+ ASSERT_EQ(idx_search_bv.CountSetBits(), 0u);
}
TEST(NullOverlay, IndexSearchIsNullOp) {
diff --git a/src/trace_processor/db/overlays/selector_overlay.cc b/src/trace_processor/db/overlays/selector_overlay.cc
index ddcb8c1..bc6fcfb 100644
--- a/src/trace_processor/db/overlays/selector_overlay.cc
+++ b/src/trace_processor/db/overlays/selector_overlay.cc
@@ -15,6 +15,7 @@
*/
#include "src/trace_processor/db/overlays/selector_overlay.h"
+#include "src/trace_processor/containers/bit_vector.h"
namespace perfetto {
namespace trace_processor {
@@ -31,7 +32,7 @@
TableBitVector SelectorOverlay::MapToTableBitVector(StorageBitVector s_bv,
OverlayOp) const {
- PERFETTO_DCHECK(s_bv.bv.size() == selected_->size());
+ PERFETTO_DCHECK(selected_->size() >= s_bv.bv.size());
BitVector res(selected_->CountSetBits());
// TODO(b/283763282): Implement this variation of |UpdateSetBits| in
// BitVector.
diff --git a/src/trace_processor/db/overlays/types.h b/src/trace_processor/db/overlays/types.h
index 4e72a41..7978ada 100644
--- a/src/trace_processor/db/overlays/types.h
+++ b/src/trace_processor/db/overlays/types.h
@@ -18,6 +18,7 @@
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/storage/types.h"
namespace perfetto {
namespace trace_processor {
@@ -46,11 +47,15 @@
// Represents a vector of indices in the table space.
struct TableIndexVector {
std::vector<uint32_t> indices;
+
+ uint32_t size() const { return static_cast<uint32_t>(indices.size()); }
};
// Represents a vector of indices in the storage space.
struct StorageIndexVector {
std::vector<uint32_t> indices;
+
+ uint32_t size() const { return static_cast<uint32_t>(indices.size()); }
};
// A subset of FilterOp containing operations which can be handled by
@@ -61,6 +66,16 @@
kOther,
};
+inline OverlayOp FilterOpToOverlayOp(FilterOp op) {
+ if (op == FilterOp::kIsNull) {
+ return OverlayOp::kIsNull;
+ }
+ if (op == FilterOp::kIsNotNull) {
+ return OverlayOp::kIsNotNull;
+ }
+ return OverlayOp::kOther;
+}
+
// Contains estimates of the cost for each of method in this class per row.
struct CostEstimatePerRow {
uint32_t to_storage_range;
diff --git a/src/trace_processor/db/query_executor.cc b/src/trace_processor/db/query_executor.cc
new file mode 100644
index 0000000..bab60bb
--- /dev/null
+++ b/src/trace_processor/db/query_executor.cc
@@ -0,0 +1,219 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <array>
+#include <numeric>
+#include <vector>
+
+#include "src/trace_processor/db/query_executor.h"
+#include "src/trace_processor/db/table.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+namespace {
+
+using Range = RowMap::Range;
+using OverlayOp = overlays::OverlayOp;
+using StorageRange = overlays::StorageRange;
+using TableRange = overlays::TableRange;
+using Storage = storage::Storage;
+using StorageOverlay = overlays::StorageOverlay;
+using TableIndexVector = overlays::TableIndexVector;
+using StorageIndexVector = overlays::StorageIndexVector;
+using TableBitVector = overlays::TableBitVector;
+using StorageBitVector = overlays::StorageBitVector;
+
+// Helper struct to simplify operations on |global| and |current| sets of
+// indices. Having this coupling enables efficient implementation of
+// IndexedColumnFilter.
+struct IndexFilterHelper {
+ explicit IndexFilterHelper(std::vector<uint32_t> indices)
+ : IndexFilterHelper(indices, std::move(indices)) {}
+
+ // Removes pairs of elements that are not set in the |bv| and returns
+ // Indices made of them.
+ static std::pair<IndexFilterHelper, IndexFilterHelper> Partition(
+ IndexFilterHelper indices,
+ const BitVector& bv) {
+ if (bv.CountSetBits() == 0) {
+ return {IndexFilterHelper(), indices};
+ }
+
+ IndexFilterHelper set_partition;
+ IndexFilterHelper non_set_partition;
+ for (auto it = bv.IterateAllBits(); it; it.Next()) {
+ uint32_t idx = it.index();
+ if (it.IsSet()) {
+ set_partition.PushBack({indices.current_[idx], indices.global_[idx]});
+ } else {
+ non_set_partition.PushBack(
+ {indices.current_[idx], indices.global_[idx]});
+ }
+ }
+ return {set_partition, non_set_partition};
+ }
+
+ // Removes pairs of elements that are not set in the |bv|. Returns count of
+ // removed elements.
+ uint32_t KeepAtSet(BitVector filter_nulls) {
+ PERFETTO_CHECK(filter_nulls.size() == current_.size() ||
+ filter_nulls.CountSetBits() == 0);
+ uint32_t count_removed =
+ static_cast<uint32_t>(current_.size()) - filter_nulls.CountSetBits();
+
+ uint32_t i = 0;
+ auto filter = [&i, &filter_nulls](uint32_t) {
+ return !filter_nulls.IsSet(i++);
+ };
+
+ auto current_it = std::remove_if(current_.begin(), current_.end(), filter);
+ current_.erase(current_it, current_.end());
+
+ i = 0;
+ auto global_it = std::remove_if(global_.begin(), global_.end(), filter);
+ global_.erase(global_it, global_.end());
+
+ return count_removed;
+ }
+
+ std::vector<uint32_t>& current() { return current_; }
+
+ std::vector<uint32_t>& global() { return global_; }
+
+ private:
+ IndexFilterHelper() = default;
+ IndexFilterHelper(std::vector<uint32_t> current, std::vector<uint32_t> global)
+ : current_(std::move(current)), global_(std::move(global)) {
+ PERFETTO_CHECK(current_.size() == global_.size());
+ }
+
+ void PushBack(std::pair<uint32_t, uint32_t> cur_and_global_idx) {
+ current_.push_back(cur_and_global_idx.first);
+ global_.push_back(cur_and_global_idx.second);
+ }
+
+ std::vector<uint32_t> current_;
+ std::vector<uint32_t> global_;
+};
+} // namespace
+
+void QueryExecutor::FilterColumn(const Constraint& c,
+ const SimpleColumn& col,
+ RowMap* rm) {
+ uint32_t rm_first = rm->Get(0);
+ uint32_t rm_last = rm->Get(rm->size() - 1);
+ uint32_t range_size = rm_last - rm_first;
+ // If the range is less than 50% full and size() < 1024, choose the index
+ // algorithm.
+ // TODO(b/283763282):Use Overlay estimations.
+ if (rm->size() < 1024 &&
+ (static_cast<double>(rm->size()) / range_size < 0.5)) {
+ *rm = IndexedColumnFilter(c, col, rm);
+ return;
+ }
+ rm->Intersect(BoundedColumnFilter(c, col, rm));
+}
+
+RowMap QueryExecutor::BoundedColumnFilter(const Constraint& c,
+ const SimpleColumn& col,
+ RowMap* rm) {
+ // TODO(b/283763282): We should align these to word boundaries.
+ TableRange table_range{Range(rm->Get(0), rm->Get(rm->size() - 1) + 1)};
+ base::SmallVector<Range, kMaxOverlayCount> overlay_bounds;
+
+ for (const auto& overlay : col.overlays) {
+ StorageRange storage_range = overlay->MapToStorageRange(table_range);
+ overlay_bounds.emplace_back(storage_range.range);
+ table_range = TableRange({storage_range.range});
+ }
+
+ // Use linear search algorithm on storage.
+ overlays::StorageBitVector filtered_storage{
+ col.storage->LinearSearch(c.op, c.value, table_range.range)};
+
+ for (uint32_t i = 0; i < col.overlays.size(); ++i) {
+ uint32_t rev_i = static_cast<uint32_t>(col.overlays.size()) - 1 - i;
+ TableBitVector mapped_to_table = col.overlays[rev_i]->MapToTableBitVector(
+ std::move(filtered_storage), overlays::FilterOpToOverlayOp(c.op));
+ filtered_storage = StorageBitVector({std::move(mapped_to_table.bv)});
+ }
+ return RowMap(std::move(filtered_storage.bv));
+}
+
+RowMap QueryExecutor::IndexedColumnFilter(const Constraint& c,
+ const SimpleColumn& col,
+ RowMap* rm) {
+ // Create outmost TableIndexVector.
+ std::vector<uint32_t> table_indices;
+ table_indices.reserve(rm->size());
+ for (auto it = rm->IterateRows(); it; it.Next()) {
+ table_indices.push_back(it.index());
+ }
+
+ // Datastructures for storing data across overlays.
+ IndexFilterHelper to_filter(std::move(table_indices));
+ std::vector<uint32_t> valid;
+ uint32_t count_removed = 0;
+
+ // Fetch the list of indices that require storage lookup and deal with all
+ // of the indices that can be compared before it.
+ OverlayOp op = overlays::FilterOpToOverlayOp(c.op);
+ for (auto overlay : col.overlays) {
+ BitVector partition =
+ overlay->IsStorageLookupRequired(op, {to_filter.current()});
+
+ // Most overlays don't require partitioning.
+ if (partition.CountSetBits() == partition.size()) {
+ to_filter.current() =
+ overlay->MapToStorageIndexVector({to_filter.current()}).indices;
+ continue;
+ }
+
+ // Separate indices that don't require storage lookup. Those can be dealt
+ // with in each pass.
+ auto [storage_lookup, no_storage_lookup] =
+ IndexFilterHelper::Partition(to_filter, partition);
+ to_filter = storage_lookup;
+
+ // Erase the values which don't match the constraint and add the
+ // remaining ones to the result.
+ BitVector valid_bv =
+ overlay->IndexSearch(op, {no_storage_lookup.current()});
+ count_removed += no_storage_lookup.KeepAtSet(std::move(valid_bv));
+ valid.insert(valid.end(), no_storage_lookup.global().begin(),
+ no_storage_lookup.global().end());
+
+ // Update the current indices to the next storage overlay.
+ to_filter.current() =
+ overlay->MapToStorageIndexVector({to_filter.current()}).indices;
+ }
+
+ BitVector matched_in_storage = col.storage->IndexSearch(
+ c.op, c.value, to_filter.current().data(),
+ static_cast<uint32_t>(to_filter.current().size()));
+ count_removed += to_filter.KeepAtSet(std::move(matched_in_storage));
+ valid.insert(valid.end(), to_filter.global().begin(),
+ to_filter.global().end());
+
+ PERFETTO_CHECK(rm->size() == valid.size() + count_removed);
+
+ std::sort(valid.begin(), valid.end());
+ return RowMap(std::move(valid));
+}
+
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/db/query_executor.h b/src/trace_processor/db/query_executor.h
new file mode 100644
index 0000000..d70053f
--- /dev/null
+++ b/src/trace_processor/db/query_executor.h
@@ -0,0 +1,115 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#ifndef SRC_TRACE_PROCESSOR_DB_QUERY_EXECUTOR_H_
+#define SRC_TRACE_PROCESSOR_DB_QUERY_EXECUTOR_H_
+
+#include <array>
+#include <numeric>
+#include <vector>
+
+#include "perfetto/ext/base/small_vector.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/column.h"
+#include "src/trace_processor/db/overlays/storage_overlay.h"
+#include "src/trace_processor/db/overlays/types.h"
+#include "src/trace_processor/db/storage/storage.h"
+
+namespace perfetto {
+namespace trace_processor {
+
+// Responsible for executing filtering/sorting operations on a single Table.
+// TODO(b/283763282): Introduce sorting.
+class QueryExecutor {
+ public:
+ static constexpr uint32_t kMaxOverlayCount = 8;
+
+ // Overlay-based definition of the column.
+ struct SimpleColumn {
+ base::SmallVector<const overlays::StorageOverlay*, kMaxOverlayCount>
+ overlays;
+ const storage::Storage* storage;
+ };
+
+ // |row_count| is the size of the last overlay.
+ QueryExecutor(const std::vector<SimpleColumn>& columns, uint32_t row_count)
+ : columns_(columns), row_count_(row_count) {}
+
+ // Apply all the constraints on the data and return the filtered RowMap.
+ RowMap Filter(const std::vector<Constraint>& cs) {
+ RowMap rm(0, row_count_);
+ for (const auto& c : cs) {
+ FilterColumn(c, columns_[c.col_idx], &rm);
+ }
+ return rm;
+ }
+
+ // Sorts using vector of Order.
+ // TODO(b/283763282): Implement.
+ RowMap Sort(const std::vector<Order>&) { PERFETTO_FATAL("Not implemented."); }
+
+ // Enables QueryExecutor::Filter on Table columns.
+ // TODO(b/283763282): Implement.
+ static RowMap FilterLegacy(const Table*, const std::vector<Constraint>&) {
+ PERFETTO_FATAL("Not implemented.");
+ }
+
+ // Enables QueryExecutor::Sort on Table columns.
+ // TODO(b/283763282): Implement.
+ static RowMap SortLegacy(const Table*, const std::vector<Order>&) {
+ PERFETTO_FATAL("Not implemented.");
+ }
+
+ // Used only in unittests. Exposes private function.
+ static RowMap BoundedColumnFilterForTesting(const Constraint& c,
+ const SimpleColumn& col,
+ RowMap* rm) {
+ return BoundedColumnFilter(c, col, rm);
+ }
+
+ // Used only in unittests. Exposes private function.
+ static RowMap IndexedColumnFilterForTesting(const Constraint& c,
+ const SimpleColumn& col,
+ RowMap* rm) {
+ return IndexedColumnFilter(c, col, rm);
+ }
+
+ private:
+ // Updates RowMap with result of filtering single column using the Constraint.
+ static void FilterColumn(const Constraint&, const SimpleColumn&, RowMap*);
+
+ // Filters the column using Range algorithm - tries to find the smallest Range
+ // to filter the storage with.
+ static RowMap BoundedColumnFilter(const Constraint&,
+ const SimpleColumn&,
+ RowMap*);
+
+ // Filters the column using Index algorithm - finds the indices to filter the
+ // storage with.
+ static RowMap IndexedColumnFilter(const Constraint&,
+ const SimpleColumn&,
+ RowMap*);
+
+ std::vector<SimpleColumn> columns_;
+
+ // Number of rows in the outmost overlay.
+ uint32_t row_count_ = 0;
+};
+
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_DB_QUERY_EXECUTOR_H_
diff --git a/src/trace_processor/db/query_executor_unittest.cc b/src/trace_processor/db/query_executor_unittest.cc
new file mode 100644
index 0000000..01fff7a
--- /dev/null
+++ b/src/trace_processor/db/query_executor_unittest.cc
@@ -0,0 +1,286 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/db/query_executor.h"
+#include "src/trace_processor/db/overlays/null_overlay.h"
+#include "src/trace_processor/db/overlays/selector_overlay.h"
+#include "src/trace_processor/db/storage/numeric_storage.h"
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+using OverlaysVec = base::SmallVector<const overlays::StorageOverlay*,
+ QueryExecutor::kMaxOverlayCount>;
+using NumericStorage = storage::NumericStorage;
+using SimpleColumn = QueryExecutor::SimpleColumn;
+using NullOverlay = overlays::NullOverlay;
+using SelectorOverlay = overlays::SelectorOverlay;
+
+TEST(QueryExecutor, OnlyStorageRange) {
+ std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
+ NumericStorage storage(storage_data.data(), 5, ColumnType::kInt64);
+ SimpleColumn col{OverlaysVec(), &storage};
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
+ RowMap rm(0, 5);
+ RowMap res = QueryExecutor::BoundedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 3u);
+ ASSERT_EQ(res.Get(0), 2u);
+}
+
+TEST(QueryExecutor, OnlyStorageRangeIsNull) {
+ std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
+ NumericStorage storage(storage_data.data(), 5, ColumnType::kInt64);
+ SimpleColumn col{OverlaysVec(), &storage};
+
+ Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ RowMap rm(0, 5);
+ RowMap res = QueryExecutor::BoundedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 0u);
+}
+
+TEST(QueryExecutor, OnlyStorageIndex) {
+ // Setup storage
+ std::vector<int64_t> storage_data(10);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ std::transform(storage_data.begin(), storage_data.end(), storage_data.begin(),
+ [](int64_t n) { return n % 5; });
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+
+ SimpleColumn col{OverlaysVec(), &storage};
+ Constraint c{0, FilterOp::kLt, SqlValue::Long(2)};
+ RowMap rm(0, 10);
+ RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 4u);
+ ASSERT_EQ(res.Get(0), 0u);
+ ASSERT_EQ(res.Get(1), 1u);
+ ASSERT_EQ(res.Get(2), 5u);
+ ASSERT_EQ(res.Get(3), 6u);
+}
+
+TEST(QueryExecutor, OnlyStorageIndexIsNull) {
+ std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
+ NumericStorage storage(storage_data.data(), 5, ColumnType::kInt64);
+ SimpleColumn col{OverlaysVec(), &storage};
+
+ Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ RowMap rm(0, 5);
+ RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 0u);
+}
+
+TEST(QueryExecutor, NullOverlayBounds) {
+ std::vector<int64_t> storage_data(5);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+ BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
+ overlays::NullOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
+ RowMap rm(0, 10);
+ RowMap res = QueryExecutor::BoundedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 2u);
+ ASSERT_EQ(res.Get(0), 4u);
+ ASSERT_EQ(res.Get(1), 8u);
+}
+
+TEST(QueryExecutor, NullOverlayRangeIsNull) {
+ std::vector<int64_t> storage_data(5);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+ BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
+ overlays::NullOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ RowMap rm(0, 10);
+ RowMap res = QueryExecutor::BoundedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 5u);
+ ASSERT_EQ(res.Get(0), 2u);
+ ASSERT_EQ(res.Get(1), 5u);
+ ASSERT_EQ(res.Get(2), 6u);
+ ASSERT_EQ(res.Get(3), 7u);
+ ASSERT_EQ(res.Get(4), 9u);
+}
+
+TEST(QueryExecutor, NullOverlayIndex) {
+ std::vector<int64_t> storage_data(6);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ std::transform(storage_data.begin(), storage_data.end(), storage_data.begin(),
+ [](int64_t n) { return n % 3; });
+ NumericStorage storage(storage_data.data(), 6, ColumnType::kInt64);
+
+ BitVector bv{1, 1, 0, 1, 1, 0, 1, 0, 0, 1};
+ NullOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(1)};
+ RowMap rm(0, 10);
+ RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 4u);
+ ASSERT_EQ(res.Get(0), 1u);
+ ASSERT_EQ(res.Get(1), 3u);
+ ASSERT_EQ(res.Get(2), 6u);
+ ASSERT_EQ(res.Get(3), 9u);
+}
+
+TEST(QueryExecutor, NullOverlayIndexIsNull) {
+ std::vector<int64_t> storage_data(5);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+ BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
+ overlays::NullOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ RowMap rm(0, 10);
+ RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 5u);
+ ASSERT_EQ(res.Get(0), 2u);
+ ASSERT_EQ(res.Get(1), 5u);
+ ASSERT_EQ(res.Get(2), 6u);
+ ASSERT_EQ(res.Get(3), 7u);
+ ASSERT_EQ(res.Get(4), 9u);
+}
+
+TEST(QueryExecutor, SelectorOverlayBounds) {
+ std::vector<int64_t> storage_data(5);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ NumericStorage storage(storage_data.data(), 5, ColumnType::kInt64);
+
+ BitVector bv{1, 1, 0, 0, 1};
+ SelectorOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kGt, SqlValue::Long(1)};
+ RowMap rm(0, 3);
+ RowMap res = QueryExecutor::BoundedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 1u);
+ ASSERT_EQ(res.Get(0), 2u);
+}
+
+TEST(QueryExecutor, SelectorOverlayIndex) {
+ std::vector<int64_t> storage_data(10);
+ std::iota(storage_data.begin(), storage_data.end(), 0);
+ std::transform(storage_data.begin(), storage_data.end(), storage_data.begin(),
+ [](int64_t n) { return n % 5; });
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+
+ BitVector bv{1, 1, 0, 1, 1, 0, 1, 0, 0, 1};
+ SelectorOverlay overlay(&bv);
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&overlay);
+
+ SimpleColumn col{overlays_vec, &storage};
+
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(2)};
+ RowMap rm(0, 6);
+ RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, col, &rm);
+
+ ASSERT_EQ(res.size(), 3u);
+ ASSERT_EQ(res.Get(0), 2u);
+ ASSERT_EQ(res.Get(1), 3u);
+ ASSERT_EQ(res.Get(2), 5u);
+}
+
+TEST(QueryExecutor, SingleConstraintWithNullAndSelector) {
+ std::vector<int64_t> storage_data{0, 1, 2, 3, 4, 0, 1, 2, 3, 4};
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+
+ // Select 6 elements from storage, resulting in a vector {0, 1, 3, 4, 1, 2}.
+ BitVector selector_bv{1, 1, 0, 1, 1, 0, 1, 1, 0, 0};
+ SelectorOverlay selector_overlay(&selector_bv);
+
+ // Add nulls, final vector {0, 1, NULL, 3, 4, NULL, 1, 2, NULL}.
+ BitVector null_bv{1, 1, 0, 1, 1, 0, 1, 1, 0};
+ NullOverlay null_overlay(&null_bv);
+
+ // Create the column.
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&null_overlay);
+ overlays_vec.emplace_back(&selector_overlay);
+ SimpleColumn col{overlays_vec, &storage};
+
+ // Filter.
+ Constraint c{0, FilterOp::kGe, SqlValue::Long(2)};
+ QueryExecutor exec({col}, 9);
+ RowMap res = exec.Filter({c});
+
+ ASSERT_EQ(res.size(), 3u);
+ ASSERT_EQ(res.Get(0), 3u);
+ ASSERT_EQ(res.Get(1), 4u);
+ ASSERT_EQ(res.Get(2), 7u);
+}
+
+TEST(QueryExecutor, IsNull) {
+ std::vector<int64_t> storage_data{0, 1, 2, 3, 4, 0, 1, 2, 3, 4};
+ NumericStorage storage(storage_data.data(), 10, ColumnType::kInt64);
+
+ // Select 6 elements from storage, resulting in a vector {0, 1, 3, 4, 1, 2}.
+ BitVector selector_bv{1, 1, 0, 1, 1, 0, 1, 1, 0, 0};
+ SelectorOverlay selector_overlay(&selector_bv);
+
+ // Add nulls, final vector {0, 1, NULL, 3, 4, NULL, 1, 2, NULL}.
+ BitVector null_bv{1, 1, 0, 1, 1, 0, 1, 1, 0};
+ NullOverlay null_overlay(&null_bv);
+
+ // Create the column.
+ OverlaysVec overlays_vec;
+ overlays_vec.emplace_back(&null_overlay);
+ overlays_vec.emplace_back(&selector_overlay);
+ SimpleColumn col{overlays_vec, &storage};
+
+ // Filter.
+ Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ QueryExecutor exec({col}, 9);
+ RowMap res = exec.Filter({c});
+
+ ASSERT_EQ(res.size(), 3u);
+ ASSERT_EQ(res.Get(0), 2u);
+ ASSERT_EQ(res.Get(1), 5u);
+ ASSERT_EQ(res.Get(2), 8u);
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/db/storage/numeric_storage.cc b/src/trace_processor/db/storage/numeric_storage.cc
index eb1dd08..3a074af 100644
--- a/src/trace_processor/db/storage/numeric_storage.cc
+++ b/src/trace_processor/db/storage/numeric_storage.cc
@@ -240,7 +240,7 @@
return BitVector(size(), true);
if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return BitVector();
+ return BitVector(size(), false);
BitVector::Builder builder(range.end);
builder.Skip(range.start);
@@ -267,7 +267,7 @@
return BitVector(size(), true);
if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return BitVector();
+ return BitVector(size(), false);
BitVector::Builder builder(indices_count);
std::visit(
