Merge "[ui] Roll stable" into main
diff --git a/Android.bp b/Android.bp
index e6cf71f..430b10a 100644
--- a/Android.bp
+++ b/Android.bp
@@ -10931,7 +10931,7 @@
name: "perfetto_src_trace_processor_db_column_column",
srcs: [
"src/trace_processor/db/column/arrangement_overlay.cc",
- "src/trace_processor/db/column/column.cc",
+ "src/trace_processor/db/column/data_node.cc",
"src/trace_processor/db/column/dense_null_overlay.cc",
"src/trace_processor/db/column/dummy_storage.cc",
"src/trace_processor/db/column/id_storage.cc",
@@ -11960,6 +11960,7 @@
"src/trace_processor/perfetto_sql/stdlib/android/broadcasts.sql",
"src/trace_processor/perfetto_sql/stdlib/android/dvfs.sql",
"src/trace_processor/perfetto_sql/stdlib/android/garbage_collection.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/input.sql",
"src/trace_processor/perfetto_sql/stdlib/android/io.sql",
"src/trace_processor/perfetto_sql/stdlib/android/monitor_contention.sql",
"src/trace_processor/perfetto_sql/stdlib/android/network_packets.sql",
diff --git a/BUILD b/BUILD
index 9460a5e..702ce4d 100644
--- a/BUILD
+++ b/BUILD
@@ -1290,8 +1290,8 @@
srcs = [
"src/trace_processor/db/column/arrangement_overlay.cc",
"src/trace_processor/db/column/arrangement_overlay.h",
- "src/trace_processor/db/column/column.cc",
- "src/trace_processor/db/column/column.h",
+ "src/trace_processor/db/column/data_node.cc",
+ "src/trace_processor/db/column/data_node.h",
"src/trace_processor/db/column/dense_null_overlay.cc",
"src/trace_processor/db/column/dense_null_overlay.h",
"src/trace_processor/db/column/dummy_storage.cc",
@@ -2264,6 +2264,7 @@
"src/trace_processor/perfetto_sql/stdlib/android/broadcasts.sql",
"src/trace_processor/perfetto_sql/stdlib/android/dvfs.sql",
"src/trace_processor/perfetto_sql/stdlib/android/garbage_collection.sql",
+ "src/trace_processor/perfetto_sql/stdlib/android/input.sql",
"src/trace_processor/perfetto_sql/stdlib/android/io.sql",
"src/trace_processor/perfetto_sql/stdlib/android/monitor_contention.sql",
"src/trace_processor/perfetto_sql/stdlib/android/network_packets.sql",
diff --git a/src/trace_processor/db/column/BUILD.gn b/src/trace_processor/db/column/BUILD.gn
index d5fa718..6bae901 100644
--- a/src/trace_processor/db/column/BUILD.gn
+++ b/src/trace_processor/db/column/BUILD.gn
@@ -18,8 +18,8 @@
sources = [
"arrangement_overlay.cc",
"arrangement_overlay.h",
- "column.cc",
- "column.h",
+ "data_node.cc",
+ "data_node.h",
"dense_null_overlay.cc",
"dense_null_overlay.h",
"dummy_storage.cc",
@@ -44,6 +44,7 @@
"../..:metatrace",
"../../../../gn:default_deps",
"../../../../include/perfetto/trace_processor:basic_types",
+ "../../../../include/perfetto/trace_processor:trace_processor",
"../../../../protos/perfetto/trace_processor:zero",
"../../../base",
"../../containers",
@@ -86,6 +87,7 @@
"../../../../gn:default_deps",
"../../../../gn:gtest_and_gmock",
"../../../../include/perfetto/trace_processor:basic_types",
+ "../../../base",
"../../containers",
]
}
diff --git a/src/trace_processor/db/column/arrangement_overlay.cc b/src/trace_processor/db/column/arrangement_overlay.cc
index 1af8504..1742d40 100644
--- a/src/trace_processor/db/column/arrangement_overlay.cc
+++ b/src/trace_processor/db/column/arrangement_overlay.cc
@@ -18,42 +18,62 @@
#include <algorithm>
#include <cstdint>
+#include <memory>
+#include <utility>
#include <vector>
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+#include "perfetto/base/logging.h"
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/tp_metatrace.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
-namespace {} // namespace
+#include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
-ArrangementOverlay::ArrangementOverlay(std::unique_ptr<Column> inner,
- const std::vector<uint32_t>* arrangement,
+namespace perfetto::trace_processor::column {
+
+ArrangementOverlay::ArrangementOverlay(const std::vector<uint32_t>* arrangement,
bool does_arrangement_order_storage)
- : inner_(std::move(inner)),
- arrangement_(arrangement),
+ : arrangement_(arrangement),
arrangement_state_(
std::is_sorted(arrangement->begin(), arrangement->end())
? Indices::State::kMonotonic
: Indices::State::kNonmonotonic),
+ does_arrangement_order_storage_(does_arrangement_order_storage) {}
+
+std::unique_ptr<DataNode::Queryable> ArrangementOverlay::MakeQueryable(
+ std::unique_ptr<DataNode::Queryable> inner) {
+ return std::make_unique<Queryable>(std::move(inner), arrangement_,
+ arrangement_state_,
+ does_arrangement_order_storage_);
+}
+
+ArrangementOverlay::Queryable::Queryable(
+ std::unique_ptr<DataNode::Queryable> inner,
+ const std::vector<uint32_t>* arrangement,
+ Indices::State arrangement_state,
+ bool does_arrangement_order_storage)
+ : inner_(std::move(inner)),
+ arrangement_(arrangement),
+ arrangement_state_(arrangement_state),
does_arrangement_order_storage_(does_arrangement_order_storage) {
PERFETTO_DCHECK(*std::max_element(arrangement->begin(), arrangement->end()) <=
inner_->size());
}
-SearchValidationResult ArrangementOverlay::ValidateSearchConstraints(
+SearchValidationResult ArrangementOverlay::Queryable::ValidateSearchConstraints(
SqlValue sql_val,
FilterOp op) const {
return inner_->ValidateSearchConstraints(sql_val, op);
}
-RangeOrBitVector ArrangementOverlay::Search(FilterOp op,
- SqlValue sql_val,
- Range in) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "ArrangementOverlay::Search");
+RangeOrBitVector ArrangementOverlay::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range in) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "ArrangementOverlay::Queryable::Search");
if (does_arrangement_order_storage_ && op != FilterOp::kGlob &&
op != FilterOp::kRegex) {
@@ -110,10 +130,12 @@
return RangeOrBitVector(std::move(builder).Build());
}
-RangeOrBitVector ArrangementOverlay::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "ArrangementOverlay::IndexSearch");
+RangeOrBitVector ArrangementOverlay::Queryable::IndexSearch(
+ FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "ArrangementOverlay::Queryable::IndexSearch");
std::vector<uint32_t> storage_iv(indices.size);
// Should be SIMD optimized.
@@ -136,17 +158,17 @@
Indices::State::kNonmonotonic});
}
-void ArrangementOverlay::StableSort(uint32_t*, uint32_t) const {
+void ArrangementOverlay::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void ArrangementOverlay::Sort(uint32_t*, uint32_t) const {
+void ArrangementOverlay::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void ArrangementOverlay::Serialize(StorageProto* storage) const {
+void ArrangementOverlay::Queryable::Serialize(StorageProto* storage) const {
auto* arrangement_overlay = storage->set_arrangement_overlay();
arrangement_overlay->set_values(
reinterpret_cast<const uint8_t*>(arrangement_->data()),
@@ -154,6 +176,4 @@
inner_->Serialize(arrangement_overlay->set_storage());
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/arrangement_overlay.h b/src/trace_processor/db/column/arrangement_overlay.h
index 233ca6a..9de7fd4 100644
--- a/src/trace_processor/db/column/arrangement_overlay.h
+++ b/src/trace_processor/db/column/arrangement_overlay.h
@@ -24,56 +24,66 @@
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
// Storage responsible for rearranging the elements of another Storage. It deals
// with duplicates, permutations and selection; for selection only, it's more
// efficient to use `SelectorOverlay`.
-class ArrangementOverlay : public Column {
+class ArrangementOverlay : public DataNode {
public:
- explicit ArrangementOverlay(std::unique_ptr<Column> inner,
- const std::vector<uint32_t>* arrangement,
- bool does_arrangement_order_storage);
+ ArrangementOverlay(const std::vector<uint32_t>* arrangement,
+ bool does_arrangement_order_storage);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp op,
- SqlValue value,
- Range range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override {
- PERFETTO_FATAL("OrderedIndexSearch can't be called on ArrangementOverlay");
- }
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override {
- return static_cast<uint32_t>(arrangement_->size());
- }
-
- std::string DebugString() const override { return "ArrangementOverlay"; }
+ std::unique_ptr<Queryable> MakeQueryable(std::unique_ptr<Queryable>) override;
private:
- std::unique_ptr<Column> inner_;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(std::unique_ptr<DataNode::Queryable> inner,
+ const std::vector<uint32_t>* arrangement,
+ Indices::State arrangement_state,
+ bool does_arrangement_order_storage);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override {
+ PERFETTO_FATAL(
+ "OrderedIndexSearch can't be called on ArrangementOverlay");
+ }
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override {
+ return static_cast<uint32_t>(arrangement_->size());
+ }
+
+ std::string DebugString() const override { return "ArrangementOverlay"; }
+
+ private:
+ std::unique_ptr<DataNode::Queryable> inner_;
+ const std::vector<uint32_t>* arrangement_;
+ const Indices::State arrangement_state_;
+ const bool does_arrangement_order_storage_;
+ };
+
+ std::unique_ptr<DataNode::Queryable> inner_;
const std::vector<uint32_t>* arrangement_;
const Indices::State arrangement_state_;
const bool does_arrangement_order_storage_;
};
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_ARRANGEMENT_OVERLAY_H_
diff --git a/src/trace_processor/db/column/arrangement_overlay_unittest.cc b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
index 4b1617f..b724ffc 100644
--- a/src/trace_processor/db/column/arrangement_overlay_unittest.cc
+++ b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
@@ -16,14 +16,17 @@
#include "src/trace_processor/db/column/arrangement_overlay.h"
+#include <cstdint>
+#include <vector>
+
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/db/column/fake_storage.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
namespace {
using testing::ElementsAre;
@@ -31,49 +34,56 @@
TEST(ArrangementOverlay, SearchAll) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
- ArrangementOverlay storage(FakeStorage::SearchAll(5), &arrangement, false);
+ auto fake = FakeStorage::SearchAll(5);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
+ auto res = queriable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2u, 3u));
}
TEST(ArrangementOverlay, SearchNone) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
- ArrangementOverlay storage(FakeStorage::SearchNone(5), &arrangement, false);
+ auto fake = FakeStorage::SearchNone(5);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
+ auto res = queriable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 4));
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
}
TEST(ArrangementOverlay, DISABLED_SearchLimited) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
- ArrangementOverlay storage(FakeStorage::SearchSubset(5, Range(4, 5)),
- &arrangement, false);
+ auto fake = FakeStorage::SearchSubset(5, Range(4, 5));
+ ArrangementOverlay storage(&arrangement, false);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 7));
+ auto res = queriable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(2, 7));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6u));
}
TEST(ArrangementOverlay, SearchBitVector) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
- ArrangementOverlay storage(
- FakeStorage::SearchSubset(5, BitVector({0, 1, 0, 1, 0})), &arrangement,
- false);
+ auto fake = FakeStorage::SearchSubset(
+ 5, BitVector({false, true, false, true, false}));
+ ArrangementOverlay storage(&arrangement, false);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
// Table bv:
// 1, 1, 0, 0, 1, 1, 0, 0, 1, 1
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 10));
+ auto res = queriable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 10));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 8, 9));
}
TEST(ArrangementOverlay, IndexSearch) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
- ArrangementOverlay storage(
- FakeStorage::SearchSubset(5, BitVector({0, 1, 0, 1, 0})), &arrangement,
- false);
+ auto fake = FakeStorage::SearchSubset(
+ 5, BitVector({false, true, false, true, false}));
+ ArrangementOverlay storage(&arrangement, false);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{7u, 1u, 3u};
- RangeOrBitVector res = storage.IndexSearch(
+ RangeOrBitVector res = queriable->IndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
Indices::State::kNonmonotonic});
@@ -83,17 +93,16 @@
TEST(ArrangementOverlay, OrderingSearch) {
std::vector<uint32_t> arrangement{0, 2, 4, 1, 3};
- ArrangementOverlay storage(
- FakeStorage::SearchSubset(5, BitVector({0, 1, 0, 1, 0})), &arrangement,
- true);
+ auto fake = FakeStorage::SearchSubset(
+ 5, BitVector({false, true, false, true, false}));
+ ArrangementOverlay storage(&arrangement, true);
+ auto queriable = storage.MakeQueryable(fake->MakeQueryable());
RangeOrBitVector res =
- storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 5));
+ queriable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
} // namespace
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/column.h b/src/trace_processor/db/column/column.h
deleted file mode 100644
index 9232d8f..0000000
--- a/src/trace_processor/db/column/column.h
+++ /dev/null
@@ -1,130 +0,0 @@
-/*
- * 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_COLUMN_COLUMN_H_
-#define SRC_TRACE_PROCESSOR_DB_COLUMN_COLUMN_H_
-
-#include <cstdint>
-#include <string>
-
-#include "perfetto/trace_processor/basic_types.h"
-#include "src/trace_processor/db/column/types.h"
-
-namespace perfetto {
-namespace protos::pbzero {
-class SerializedColumn_Storage;
-}
-
-namespace trace_processor::column {
-
-// Defines an API of a Column. Storages and Overlays both inherit from
-// Column.
-class Column {
- public:
- using StorageProto = protos::pbzero::SerializedColumn_Storage;
-
- virtual ~Column();
-
- // Verifies whether any further filtering is needed and if not, whether the
- // search would return all values or none of them. This allows for skipping
- // the |Search| and |IndexSearch| in special cases.
- //
- // Notes for callers:
- // * The SqlValue and FilterOp have to be valid in Sqlite: it will crash if
- // either: value is NULL and operation is different than "IS NULL" and "IS
- // NOT NULL" or the operation is "IS NULL" and "IS NOT NULL" and value is
- // different than NULL.
- virtual SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const = 0;
-
- // Searches for elements which match |op| and |value| between |range.start|
- // and |range.end|.
- //
- // Returns either a range or BitVector which indicate the positions in |range|
- // which match the constraint. If a BitVector is returned, it will be
- // *precisely* as large as |range.end|.
- //
- // Notes for callers:
- // * Should only be called if ValidateSearchContraints returned kOk.
- // * Callers should note that the return value of this function corresponds
- // to positions in the storage.
- //
- // Notes for implementors:
- // * Implementations should ensure that the return value *only* includes
- // positions in |range| as callers will expect this to be true and can
- // optimize based on this.
- // * Implementations should ensure that, if they return a BitVector, it is
- // precisely of size |range.end|.
- virtual RangeOrBitVector Search(FilterOp, SqlValue, Range) const = 0;
-
- // Searches for elements which match |op| and |value| at the positions given
- // by |indices| array.
- //
- // Returns either a range of BitVector which indicate the positions in
- // |indices| which match the constraint. If a BitVector is returned, it will
- // be *precisely* as large as |indices_count|.
- //
- // Notes for callers:
- // * Should only be called if ValidateSearchContraints returned kOk.
- // * Callers should note that the return value of this function corresponds
- // to positions in |indices| *not* positions in the storage.
- //
- // Notes for implementors:
- // * Implementations should ensure that, if they return a BitVector, it is
- // precisely of size |indices_count|.
- virtual RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const = 0;
-
- // Searches for elements which match |op| and |value| at the positions given
- // by indices data.
- //
- // Returns a Range into Indices data of indices that pass the constraint.
- //
- // Notes for callers:
- // * Should not be called on:
- // - kGlob and kRegex as those operations can't use the sorted state hence
- // they can't return a Range.
- // - kNe as this is inherently unsorted. Use kEq and then reverse the
- // result.
- // * Should only be called if ValidateSearchContraints returned kOk.
- // * Callers should note that the return value of this function corresponds
- // to positions in |indices| *not* positions in the storage.
- virtual Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const = 0;
-
- // Sorts |rows| in ascending order with the comparator:
- // data[rows[a]] < data[rows[b]].
- virtual void Sort(uint32_t* rows, uint32_t rows_size) const = 0;
-
- // Stable sorts |rows| in ascending order with the comparator:
- // data[rows[a]] < data[rows[b]].
- virtual void StableSort(uint32_t* rows, uint32_t rows_size) const = 0;
-
- // Serializes storage data to proto format.
- virtual void Serialize(StorageProto*) const = 0;
-
- // Returns a string which represents the column for debugging purposes.
- //
- // Warning: the format of the string returned by this class is *not* stable
- // and should be relied upon for anything except printing for debugging
- // purposes.
- virtual std::string DebugString() const = 0;
-
- // Number of elements in stored data.
- virtual uint32_t size() const = 0;
-};
-
-} // namespace trace_processor::column
-} // namespace perfetto
-
-#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_COLUMN_H_
diff --git a/src/trace_processor/db/column/column.cc b/src/trace_processor/db/column/data_node.cc
similarity index 73%
rename from src/trace_processor/db/column/column.cc
rename to src/trace_processor/db/column/data_node.cc
index a3e62d4..22ba2dc 100644
--- a/src/trace_processor/db/column/column.cc
+++ b/src/trace_processor/db/column/data_node.cc
@@ -14,14 +14,11 @@
* limitations under the License.
*/
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
-Column::~Column() = default;
+DataNode::~DataNode() = default;
+DataNode::Queryable::~Queryable() = default;
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/data_node.h b/src/trace_processor/db/column/data_node.h
new file mode 100644
index 0000000..89020df
--- /dev/null
+++ b/src/trace_processor/db/column/data_node.h
@@ -0,0 +1,144 @@
+/*
+ * 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_COLUMN_DATA_NODE_H_
+#define SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_NODE_H_
+
+#include <cstdint>
+#include <memory>
+#include <string>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/trace_processor/basic_types.h"
+#include "perfetto/trace_processor/ref_counted.h"
+#include "src/trace_processor/db/column/types.h"
+
+namespace perfetto {
+namespace protos::pbzero {
+class SerializedColumn_Storage;
+}
+
+namespace trace_processor::column {
+
+class DataNode : public RefCounted {
+ public:
+ class Queryable {
+ public:
+ using StorageProto = protos::pbzero::SerializedColumn_Storage;
+
+ virtual ~Queryable();
+
+ // Verifies whether any further filtering is needed and if not, whether the
+ // search would return all values or none of them. This allows for skipping
+ // the |Search| and |IndexSearch| in special cases.
+ //
+ // Notes for callers:
+ // * The SqlValue and FilterOp have to be valid in Sqlite: it will crash if
+ // either: value is NULL and operation is different than "IS NULL" and "IS
+ // NOT NULL" or the operation is "IS NULL" and "IS NOT NULL" and value is
+ // different than NULL.
+ virtual SearchValidationResult ValidateSearchConstraints(SqlValue, FilterOp)
+ const = 0;
+
+ // Searches for elements which match |op| and |value| between |range.start|
+ // and |range.end|.
+ //
+ // Returns either a range or BitVector which indicate the positions in
+ // |range| which match the constraint. If a BitVector is returned, it will
+ // be *precisely* as large as |range.end|.
+ //
+ // Notes for callers:
+ // * Should only be called if ValidateSearchContraints returned kOk.
+ // * Callers should note that the return value of this function corresponds
+ // to positions in the storage.
+ //
+ // Notes for implementors:
+ // * Implementations should ensure that the return value *only* includes
+ // positions in |range| as callers will expect this to be true and can
+ // optimize based on this.
+ // * Implementations should ensure that, if they return a BitVector, it is
+ // precisely of size |range.end|.
+ virtual RangeOrBitVector Search(FilterOp, SqlValue, Range) const = 0;
+
+ // Searches for elements which match |op| and |value| at the positions given
+ // by |indices| array.
+ //
+ // Returns either a range of BitVector which indicate the positions in
+ // |indices| which match the constraint. If a BitVector is returned, it will
+ // be *precisely* as large as |indices_count|.
+ //
+ // Notes for callers:
+ // * Should only be called if ValidateSearchContraints returned kOk.
+ // * Callers should note that the return value of this function corresponds
+ // to positions in |indices| *not* positions in the storage.
+ //
+ // Notes for implementors:
+ // * Implementations should ensure that, if they return a BitVector, it is
+ // precisely of size |indices_count|.
+ virtual RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const = 0;
+
+ // Searches for elements which match |op| and |value| at the positions given
+ // by indices data.
+ //
+ // Returns a Range into Indices data of indices that pass the constraint.
+ //
+ // Notes for callers:
+ // * Should not be called on:
+ // - kGlob and kRegex as those operations can't use the sorted state
+ // hence they can't return a Range.
+ // - kNe as this is inherently unsorted. Use kEq and then reverse the
+ // result.
+ // * Should only be called if ValidateSearchContraints returned kOk.
+ // * Callers should note that the return value of this function corresponds
+ // to positions in |indices| *not* positions in the storage.
+ virtual Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const = 0;
+
+ // Sorts |rows| in ascending order with the comparator:
+ // data[rows[a]] < data[rows[b]].
+ virtual void Sort(uint32_t* rows, uint32_t rows_size) const = 0;
+
+ // Stable sorts |rows| in ascending order with the comparator:
+ // data[rows[a]] < data[rows[b]].
+ virtual void StableSort(uint32_t* rows, uint32_t rows_size) const = 0;
+
+ // Serializes storage data to proto format.
+ virtual void Serialize(StorageProto*) const = 0;
+
+ // Returns a string which represents the column for debugging purposes.
+ //
+ // Warning: the format of the string returned by this class is *not* stable
+ // and should be relied upon for anything except printing for debugging
+ // purposes.
+ virtual std::string DebugString() const = 0;
+
+ // Number of elements in stored data.
+ virtual uint32_t size() const = 0;
+ };
+
+ virtual ~DataNode();
+
+ virtual std::unique_ptr<Queryable> MakeQueryable() {
+ PERFETTO_FATAL("Unimplemented");
+ }
+ virtual std::unique_ptr<Queryable> MakeQueryable(std::unique_ptr<Queryable>) {
+ PERFETTO_FATAL("Unimplemented");
+ }
+};
+
+} // namespace trace_processor::column
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_DATA_NODE_H_
diff --git a/src/trace_processor/db/column/dense_null_overlay.cc b/src/trace_processor/db/column/dense_null_overlay.cc
index e1e6b98..ac07d3f 100644
--- a/src/trace_processor/db/column/dense_null_overlay.cc
+++ b/src/trace_processor/db/column/dense_null_overlay.cc
@@ -25,7 +25,7 @@
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/tp_metatrace.h"
@@ -34,11 +34,20 @@
namespace perfetto::trace_processor::column {
-DenseNullOverlay::DenseNullOverlay(std::unique_ptr<Column> inner,
- const BitVector* non_null)
+DenseNullOverlay::DenseNullOverlay(const BitVector* non_null)
+ : non_null_(non_null) {}
+
+std::unique_ptr<DataNode::Queryable> DenseNullOverlay::MakeQueryable(
+ std::unique_ptr<DataNode::Queryable> inner) {
+ return std::make_unique<Queryable>(std::move(inner), non_null_);
+}
+
+DenseNullOverlay::Queryable::Queryable(
+ std::unique_ptr<DataNode::Queryable> inner,
+ const BitVector* non_null)
: inner_(std::move(inner)), non_null_(non_null) {}
-SearchValidationResult DenseNullOverlay::ValidateSearchConstraints(
+SearchValidationResult DenseNullOverlay::Queryable::ValidateSearchConstraints(
SqlValue sql_val,
FilterOp op) const {
if (op == FilterOp::kIsNull) {
@@ -48,10 +57,11 @@
return inner_->ValidateSearchConstraints(sql_val, op);
}
-RangeOrBitVector DenseNullOverlay::Search(FilterOp op,
- SqlValue sql_val,
- Range in) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "DenseNullOverlay::Search");
+RangeOrBitVector DenseNullOverlay::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range in) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "DenseNullOverlay::Queryable::Search");
if (op == FilterOp::kIsNull) {
switch (inner_->ValidateSearchConstraints(sql_val, op)) {
@@ -103,10 +113,12 @@
return RangeOrBitVector(std::move(res));
}
-RangeOrBitVector DenseNullOverlay::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "DenseNullOverlay::IndexSearch");
+RangeOrBitVector DenseNullOverlay::Queryable::IndexSearch(
+ FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "DenseNullOverlay::Queryable::IndexSearch");
if (op == FilterOp::kIsNull) {
switch (inner_->ValidateSearchConstraints(sql_val, op)) {
@@ -157,14 +169,14 @@
return RangeOrBitVector(std::move(res));
}
-Range DenseNullOverlay::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range DenseNullOverlay::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
// For NOT EQUAL the further analysis needs to be done by the caller.
PERFETTO_CHECK(op != FilterOp::kNe);
PERFETTO_TP_TRACE(metatrace::Category::DB,
- "DenseNullOverlay::OrderedIndexSearch");
+ "DenseNullOverlay::Queryable::OrderedIndexSearch");
// We assume all NULLs are ordered to be in the front. We are looking for the
// first index that points to non NULL value.
@@ -199,17 +211,17 @@
inner_range.end + non_null_offset);
}
-void DenseNullOverlay::StableSort(uint32_t*, uint32_t) const {
+void DenseNullOverlay::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void DenseNullOverlay::Sort(uint32_t*, uint32_t) const {
+void DenseNullOverlay::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void DenseNullOverlay::Serialize(StorageProto* storage) const {
+void DenseNullOverlay::Queryable::Serialize(StorageProto* storage) const {
auto* null_overlay = storage->set_dense_null_overlay();
non_null_->Serialize(null_overlay->set_bit_vector());
inner_->Serialize(null_overlay->set_storage());
diff --git a/src/trace_processor/db/column/dense_null_overlay.h b/src/trace_processor/db/column/dense_null_overlay.h
index 9b473fc..d2b341b 100644
--- a/src/trace_processor/db/column/dense_null_overlay.h
+++ b/src/trace_processor/db/column/dense_null_overlay.h
@@ -19,49 +19,57 @@
#include <cstdint>
#include <memory>
-#include <variant>
+#include <string>
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
// Overlay which introduces the layer of nullability but without changing the
// "spacing" of the underlying storage i.e. this overlay simply "masks" out
// rows in the underlying storage with nulls.
-class DenseNullOverlay : public Column {
+class DenseNullOverlay : public DataNode {
public:
- DenseNullOverlay(std::unique_ptr<Column> inner, const BitVector* non_null);
+ explicit DenseNullOverlay(const BitVector* non_null);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override { return non_null_->size(); }
-
- std::string DebugString() const override { return "DenseNullOverlay"; }
+ std::unique_ptr<Queryable> MakeQueryable(std::unique_ptr<Queryable>) override;
private:
- std::unique_ptr<Column> inner_;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(std::unique_ptr<DataNode::Queryable> inner,
+ const BitVector* non_null);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return non_null_->size(); }
+
+ std::string DebugString() const override { return "DenseNullOverlay"; }
+
+ private:
+ std::unique_ptr<DataNode::Queryable> inner_;
+ const BitVector* non_null_ = nullptr;
+ };
+
const BitVector* non_null_ = nullptr;
};
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_DENSE_NULL_OVERLAY_H_
diff --git a/src/trace_processor/db/column/dense_null_overlay_unittest.cc b/src/trace_processor/db/column/dense_null_overlay_unittest.cc
index 871e424..5067b2d 100644
--- a/src/trace_processor/db/column/dense_null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/dense_null_overlay_unittest.cc
@@ -43,9 +43,10 @@
std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
BitVector bv{0, 1, 0, 1, 0};
- DenseNullOverlay storage(std::move(numeric), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
}
@@ -55,9 +56,10 @@
std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
BitVector bv{0, 1, 0, 1, 0};
- DenseNullOverlay storage(std::move(numeric), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(1, 3));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0), Range(1, 3));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
}
@@ -65,9 +67,10 @@
auto fake = FakeStorage::SearchSubset(5, Range(1, 3));
BitVector bv{0, 1, 0, 1, 0};
- DenseNullOverlay storage(std::move(fake), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
}
@@ -75,9 +78,10 @@
auto fake = FakeStorage::SearchSubset(5, BitVector({0, 1, 1, 0, 0}));
BitVector bv{0, 1, 0, 1, 0};
- DenseNullOverlay storage(std::move(fake), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
}
@@ -85,9 +89,10 @@
auto fake = FakeStorage::SearchSubset(5, BitVector({1, 1, 0, 0, 1}));
BitVector bv{1, 0, 0, 1, 1};
- DenseNullOverlay storage(std::move(fake), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kIsNull, SqlValue(), Range(0, 5));
+ auto res = queryable->Search(FilterOp::kIsNull, SqlValue(), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4));
}
@@ -97,10 +102,11 @@
std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
BitVector bv{1, 0, 0, 1, 1, 1};
- DenseNullOverlay storage(std::move(numeric), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
std::vector<uint32_t> index({5, 2, 3, 4, 1});
- auto res = storage.IndexSearch(
+ auto res = queryable->IndexSearch(
FilterOp::kGe, SqlValue::Long(0),
Indices{index.data(), static_cast<uint32_t>(index.size()),
Indices::State::kNonmonotonic});
@@ -111,10 +117,11 @@
auto fake = FakeStorage::SearchSubset(6, BitVector({0, 0, 0, 1, 1, 1}));
BitVector bv{0, 1, 0, 1, 1, 1};
- DenseNullOverlay storage(std::move(fake), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> index({5, 2, 3, 4, 1});
- auto res = storage.IndexSearch(
+ auto res = queryable->IndexSearch(
FilterOp::kIsNull, SqlValue(),
Indices{index.data(), static_cast<uint32_t>(index.size()),
Indices::State::kMonotonic});
@@ -125,37 +132,44 @@
auto fake = FakeStorage::SearchSubset(6, BitVector({0, 1, 0, 1, 0, 1}));
BitVector bv{0, 1, 0, 1, 0, 1};
- DenseNullOverlay storage(std::move(fake), &bv);
+ DenseNullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> indices_vec({0, 2, 4, 1, 3, 5});
Indices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
Range res =
- storage.OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ queryable->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 3u);
- res = storage.OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = storage.OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = storage.OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = storage.OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = storage.OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = storage.OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
}
diff --git a/src/trace_processor/db/column/dummy_storage.cc b/src/trace_processor/db/column/dummy_storage.cc
index df24dfa..5475cc4 100644
--- a/src/trace_processor/db/column/dummy_storage.cc
+++ b/src/trace_processor/db/column/dummy_storage.cc
@@ -15,46 +15,59 @@
*/
#include "src/trace_processor/db/column/dummy_storage.h"
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+
+#include <cstdint>
+#include <memory>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
-SearchValidationResult DummyStorage::ValidateSearchConstraints(SqlValue,
- FilterOp) const {
+std::unique_ptr<DataNode::Queryable> DummyStorage::MakeQueryable() {
+ return std::make_unique<Queryable>();
+}
+
+SearchValidationResult DummyStorage::Queryable::ValidateSearchConstraints(
+ SqlValue,
+ FilterOp) const {
PERFETTO_FATAL("Shouldn't be called");
}
-RangeOrBitVector DummyStorage::Search(FilterOp, SqlValue, Range) const {
+RangeOrBitVector DummyStorage::Queryable::Search(FilterOp,
+ SqlValue,
+ Range) const {
PERFETTO_FATAL("Shouldn't be called");
}
-RangeOrBitVector DummyStorage::IndexSearch(FilterOp, SqlValue, Indices) const {
+RangeOrBitVector DummyStorage::Queryable::IndexSearch(FilterOp,
+ SqlValue,
+ Indices) const {
PERFETTO_FATAL("Shouldn't be called");
}
-Range DummyStorage::OrderedIndexSearch(FilterOp, SqlValue, Indices) const {
+Range DummyStorage::Queryable::OrderedIndexSearch(FilterOp,
+ SqlValue,
+ Indices) const {
PERFETTO_FATAL("Shouldn't be called");
}
-void DummyStorage::StableSort(uint32_t*, uint32_t) const {
+void DummyStorage::Queryable::StableSort(uint32_t*, uint32_t) const {
PERFETTO_FATAL("Shouldn't be called");
}
-void DummyStorage::Sort(uint32_t*, uint32_t) const {
+void DummyStorage::Queryable::Sort(uint32_t*, uint32_t) const {
PERFETTO_FATAL("Shouldn't be called");
}
-uint32_t DummyStorage::size() const {
+uint32_t DummyStorage::Queryable::size() const {
return 0;
}
-void DummyStorage::Serialize(StorageProto*) const {
+void DummyStorage::Queryable::Serialize(StorageProto*) const {
PERFETTO_FATAL("Shouldn't be called");
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/dummy_storage.h b/src/trace_processor/db/column/dummy_storage.h
index 9158f6f..ab5e547 100644
--- a/src/trace_processor/db/column/dummy_storage.h
+++ b/src/trace_processor/db/column/dummy_storage.h
@@ -17,38 +17,45 @@
#define SRC_TRACE_PROCESSOR_DB_COLUMN_DUMMY_STORAGE_H_
#include <cstdint>
+#include <memory>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Dummy storage. Used for columns that are not supposed to have operations done
// on them.
-class DummyStorage final : public Column {
+class DummyStorage final : public DataNode {
public:
- DummyStorage() = default;
+ std::unique_ptr<DataNode::Queryable> MakeQueryable() override;
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+ private:
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable() = default;
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
- void StableSort(uint32_t*, uint32_t) const override;
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
- void Sort(uint32_t*, uint32_t) const override;
+ void StableSort(uint32_t*, uint32_t) const override;
- void Serialize(StorageProto*) const override;
+ void Sort(uint32_t*, uint32_t) const override;
- uint32_t size() const override;
+ void Serialize(StorageProto*) const override;
- std::string DebugString() const override { return "DummyStorage"; }
+ uint32_t size() const override;
+
+ std::string DebugString() const override { return "DummyStorage"; }
+ };
};
} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/fake_storage.cc b/src/trace_processor/db/column/fake_storage.cc
index f130f9f..f868157 100644
--- a/src/trace_processor/db/column/fake_storage.cc
+++ b/src/trace_processor/db/column/fake_storage.cc
@@ -15,24 +15,47 @@
*/
#include "src/trace_processor/db/column/fake_storage.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <iterator>
+#include <memory>
+#include <utility>
+
+#include "perfetto/base/logging.h"
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/containers/row_map.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
FakeStorage::FakeStorage(uint32_t size, SearchStrategy strategy)
: size_(size), strategy_(strategy) {}
-SearchValidationResult FakeStorage::ValidateSearchConstraints(SqlValue,
- FilterOp) const {
+std::unique_ptr<DataNode::Queryable> FakeStorage::MakeQueryable() {
+ return std::make_unique<Queryable>(size_, strategy_, range_,
+ bit_vector_.Copy());
+}
+
+FakeStorage::Queryable::Queryable(uint32_t size,
+ SearchStrategy strategy,
+ Range range,
+ BitVector bv)
+ : size_(size),
+ strategy_(strategy),
+ range_(range),
+ bit_vector_(std::move(bv)) {}
+
+SearchValidationResult FakeStorage::Queryable::ValidateSearchConstraints(
+ SqlValue,
+ FilterOp) const {
return SearchValidationResult::kOk;
}
-RangeOrBitVector FakeStorage::Search(FilterOp, SqlValue, Range in) const {
+RangeOrBitVector FakeStorage::Queryable::Search(FilterOp,
+ SqlValue,
+ Range in) const {
switch (strategy_) {
case kAll:
return RangeOrBitVector(in);
@@ -47,9 +70,9 @@
PERFETTO_FATAL("For GCC");
}
-RangeOrBitVector FakeStorage::IndexSearch(FilterOp,
- SqlValue,
- Indices indices) const {
+RangeOrBitVector FakeStorage::Queryable::IndexSearch(FilterOp,
+ SqlValue,
+ Indices indices) const {
switch (strategy_) {
case kAll:
return RangeOrBitVector(Range(0, indices.size));
@@ -70,15 +93,15 @@
PERFETTO_FATAL("For GCC");
}
-Range FakeStorage::OrderedIndexSearch(FilterOp,
- SqlValue,
- Indices indices) const {
+Range FakeStorage::Queryable::OrderedIndexSearch(FilterOp,
+ SqlValue,
+ Indices indices) const {
if (strategy_ == kAll) {
- return Range(0, indices.size);
+ return {0, indices.size};
}
if (strategy_ == kNone) {
- return Range();
+ return {};
}
if (strategy_ == kRange) {
@@ -89,10 +112,9 @@
const uint32_t* first_outside_range =
std::partition_point(first_in_range, indices.data + indices.size,
[this](uint32_t i) { return range_.Contains(i); });
- return Range(
- static_cast<uint32_t>(std::distance(indices.data, first_in_range)),
- static_cast<uint32_t>(
- std::distance(indices.data, first_outside_range)));
+ return {static_cast<uint32_t>(std::distance(indices.data, first_in_range)),
+ static_cast<uint32_t>(
+ std::distance(indices.data, first_outside_range))};
}
PERFETTO_DCHECK(strategy_ == kBitVector);
@@ -103,26 +125,23 @@
const uint32_t* first_non_set =
std::partition_point(first_set, indices.data + indices.size,
[this](uint32_t i) { return bit_vector_.IsSet(i); });
- return Range(
- static_cast<uint32_t>(std::distance(indices.data, first_set)),
- static_cast<uint32_t>(std::distance(indices.data, first_non_set)));
+ return {static_cast<uint32_t>(std::distance(indices.data, first_set)),
+ static_cast<uint32_t>(std::distance(indices.data, first_non_set))};
}
-void FakeStorage::StableSort(uint32_t*, uint32_t) const {
+void FakeStorage::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void FakeStorage::Sort(uint32_t*, uint32_t) const {
+void FakeStorage::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void FakeStorage::Serialize(StorageProto*) const {
+void FakeStorage::Queryable::Serialize(StorageProto*) const {
// FakeStorage doesn't really make sense to serialize.
PERFETTO_FATAL("Not implemented");
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/fake_storage.h b/src/trace_processor/db/column/fake_storage.h
index a1d7c6f..b4dbdde 100644
--- a/src/trace_processor/db/column/fake_storage.h
+++ b/src/trace_processor/db/column/fake_storage.h
@@ -21,59 +21,47 @@
#include <memory>
#include <string>
#include <utility>
+#include <vector>
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
// Fake implementation of Storage for use in tests.
-class FakeStorage final : public Column {
+class FakeStorage final : public DataNode {
public:
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
+ std::unique_ptr<Queryable> MakeQueryable() override;
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- static std::unique_ptr<Column> SearchAll(uint32_t size) {
- return std::unique_ptr<Column>(new FakeStorage(size, SearchStrategy::kAll));
+ static std::unique_ptr<DataNode> SearchAll(uint32_t size) {
+ return std::unique_ptr<DataNode>(
+ new FakeStorage(size, SearchStrategy::kAll));
}
- static std::unique_ptr<Column> SearchNone(uint32_t size) {
- return std::unique_ptr<Column>(
+ static std::unique_ptr<DataNode> SearchNone(uint32_t size) {
+ return std::unique_ptr<DataNode>(
new FakeStorage(size, SearchStrategy::kNone));
}
- static std::unique_ptr<Column> SearchSubset(uint32_t size, Range r) {
+ static std::unique_ptr<DataNode> SearchSubset(uint32_t size, Range r) {
std::unique_ptr<FakeStorage> storage(
new FakeStorage(size, SearchStrategy::kRange));
storage->range_ = r;
return std::move(storage);
}
- static std::unique_ptr<Column> SearchSubset(uint32_t size, BitVector bv) {
+ static std::unique_ptr<DataNode> SearchSubset(uint32_t size, BitVector bv) {
std::unique_ptr<FakeStorage> storage(
new FakeStorage(size, SearchStrategy::kBitVector));
storage->bit_vector_ = std::move(bv);
return std::move(storage);
}
- static std::unique_ptr<Column> SearchSubset(uint32_t size,
- std::vector<uint32_t> index_vec) {
+ static std::unique_ptr<DataNode> SearchSubset(
+ uint32_t size,
+ const std::vector<uint32_t>& index_vec) {
std::unique_ptr<FakeStorage> storage(
new FakeStorage(size, SearchStrategy::kBitVector));
BitVector bv(size);
@@ -84,12 +72,39 @@
return std::move(storage);
}
- uint32_t size() const override { return size_; }
-
- std::string DebugString() const override { return "FakeStorage"; }
-
private:
enum SearchStrategy { kNone, kAll, kRange, kBitVector };
+
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(uint32_t, SearchStrategy, Range, BitVector);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return size_; }
+
+ std::string DebugString() const override { return "FakeStorage"; }
+
+ private:
+ uint32_t size_ = 0;
+ SearchStrategy strategy_ = SearchStrategy::kNone;
+ Range range_;
+ BitVector bit_vector_;
+ };
+
FakeStorage(uint32_t size, SearchStrategy strategy);
uint32_t size_ = 0;
@@ -98,8 +113,6 @@
BitVector bit_vector_;
};
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_FAKE_STORAGE_H_
diff --git a/src/trace_processor/db/column/id_storage.cc b/src/trace_processor/db/column/id_storage.cc
index 7dc60ba..b1a7d08 100644
--- a/src/trace_processor/db/column/id_storage.cc
+++ b/src/trace_processor/db/column/id_storage.cc
@@ -15,22 +15,29 @@
*/
#include "src/trace_processor/db/column/id_storage.h"
+
#include <algorithm>
-#include <optional>
+#include <cstdint>
+#include <functional>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <string>
+#include <utility>
#include "perfetto/base/logging.h"
#include "perfetto/public/compiler.h"
#include "perfetto/trace_processor/basic_types.h"
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "src/trace_processor/tp_metatrace.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+#include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+
+namespace perfetto::trace_processor::column {
namespace {
@@ -73,8 +80,9 @@
} // namespace
-SearchValidationResult IdStorage::ValidateSearchConstraints(SqlValue val,
- FilterOp op) const {
+SearchValidationResult IdStorage::Queryable::ValidateSearchConstraints(
+ SqlValue val,
+ FilterOp op) const {
// NULL checks.
if (PERFETTO_UNLIKELY(val.is_null())) {
if (op == FilterOp::kIsNotNull) {
@@ -124,9 +132,9 @@
}
// Bounds of the value.
- double_t num_val = val.type == SqlValue::kLong
- ? static_cast<double_t>(val.AsLong())
- : val.AsDouble();
+ double num_val = val.type == SqlValue::kLong
+ ? static_cast<double>(val.AsLong())
+ : val.AsDouble();
if (PERFETTO_UNLIKELY(num_val > std::numeric_limits<uint32_t>::max())) {
if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
@@ -144,10 +152,18 @@
return SearchValidationResult::kOk;
}
-RangeOrBitVector IdStorage::Search(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::Search",
+IdStorage::IdStorage(uint32_t size) : size_(size) {}
+
+std::unique_ptr<DataNode::Queryable> IdStorage::MakeQueryable() {
+ return std::make_unique<Queryable>(size_);
+}
+
+IdStorage::Queryable::Queryable(uint32_t size) : size_(size) {}
+
+RangeOrBitVector IdStorage::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range search_range) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::Queryable::Search",
[&search_range, op](metatrace::Record* r) {
r->AddArg("Start", std::to_string(search_range.start));
r->AddArg("End", std::to_string(search_range.end));
@@ -170,8 +186,7 @@
}
}
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
if (op == FilterOp::kNe) {
BitVector ret(search_range.start, false);
ret.Resize(search_range.end, true);
@@ -182,15 +197,15 @@
return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
-RangeOrBitVector IdStorage::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+RangeOrBitVector IdStorage::Queryable::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "IdStorage::Queryable::IndexSearch",
+ [indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.size));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
// It's a valid filter operation if |sql_val| is a double, although it
// requires special logic.
@@ -205,27 +220,26 @@
}
}
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
switch (op) {
case FilterOp::kEq:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::equal_to<uint32_t>());
+ std::equal_to<>());
case FilterOp::kNe:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::not_equal_to<uint32_t>());
+ std::not_equal_to<>());
case FilterOp::kLe:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::less_equal<uint32_t>());
+ std::less_equal<>());
case FilterOp::kLt:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::less<uint32_t>());
+ std::less<>());
case FilterOp::kGt:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::greater<uint32_t>());
+ std::greater<>());
case FilterOp::kGe:
return IndexSearchWithComparator(val, indices.data, indices.size,
- std::greater_equal<uint32_t>());
+ std::greater_equal<>());
case FilterOp::kIsNotNull:
case FilterOp::kIsNull:
case FilterOp::kGlob:
@@ -235,17 +249,17 @@
PERFETTO_FATAL("FilterOp not matched");
}
-Range IdStorage::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range IdStorage::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
PERFETTO_DCHECK(op != FilterOp::kNe);
- PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::OrderedIndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "IdStorage::Queryable::OrderedIndexSearch",
+ [indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.size));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
// It's a valid filter operation if |sql_val| is a double, although it
// requires special logic.
@@ -254,42 +268,42 @@
case SearchValidationResult::kOk:
break;
case SearchValidationResult::kAllData:
- return Range(0, indices.size);
+ return {0, indices.size};
case SearchValidationResult::kNoData:
- return Range();
+ return {};
}
}
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
// Indices are monotonic non contiguous values if OrderedIndexSearch was
// called.
-
// Look for the first and last index and find the result of looking for this
// range in IdStorage.
Range indices_range(indices.data[0], indices.data[indices.size - 1] + 1);
Range bin_search_ret = BinarySearchIntrinsic(op, val, indices_range);
- auto start_ptr = std::lower_bound(indices.data, indices.data + indices.size,
- bin_search_ret.start);
- auto end_ptr = std::lower_bound(start_ptr, indices.data + indices.size,
- bin_search_ret.end);
-
- return Range(static_cast<uint32_t>(std::distance(indices.data, start_ptr)),
- static_cast<uint32_t>(std::distance(indices.data, end_ptr)));
+ const auto* start_ptr = std::lower_bound(
+ indices.data, indices.data + indices.size, bin_search_ret.start);
+ const auto* end_ptr = std::lower_bound(start_ptr, indices.data + indices.size,
+ bin_search_ret.end);
+ return {static_cast<uint32_t>(std::distance(indices.data, start_ptr)),
+ static_cast<uint32_t>(std::distance(indices.data, end_ptr))};
}
-Range IdStorage::BinarySearchIntrinsic(FilterOp op, Id val, Range range) const {
+Range IdStorage::Queryable::BinarySearchIntrinsic(FilterOp op,
+ Id val,
+ Range range) {
switch (op) {
case FilterOp::kEq:
- return Range(val, val + (range.start <= val && val < range.end));
+ return {val, val + (range.start <= val && val < range.end)};
case FilterOp::kLe:
- return Range(range.start, std::min(val + 1, range.end));
+ return {range.start, std::min(val + 1, range.end)};
case FilterOp::kLt:
- return Range(range.start, std::min(val, range.end));
+ return {range.start, std::min(val, range.end)};
case FilterOp::kGe:
- return Range(std::max(val, range.start), range.end);
+ return {std::max(val, range.start), range.end};
case FilterOp::kGt:
- return Range(std::max(val + 1, range.start), range.end);
+ return {std::max(val + 1, range.start), range.end};
case FilterOp::kIsNotNull:
case FilterOp::kNe:
case FilterOp::kIsNull:
@@ -300,20 +314,20 @@
PERFETTO_FATAL("FilterOp not matched");
}
-void IdStorage::StableSort(uint32_t* indices, uint32_t indices_size) const {
+void IdStorage::Queryable::StableSort(uint32_t* indices,
+ uint32_t indices_size) const {
// We can use sort, as |indices| will not have duplicates.
Sort(indices, indices_size);
}
-void IdStorage::Sort(uint32_t* indices, uint32_t indices_size) const {
+void IdStorage::Queryable::Sort(uint32_t* indices,
+ uint32_t indices_size) const {
std::sort(indices, indices + indices_size);
}
-void IdStorage::Serialize(StorageProto* storage) const {
+void IdStorage::Queryable::Serialize(StorageProto* storage) const {
auto* id_storage = storage->set_id_storage();
id_storage->set_size(size_);
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/id_storage.h b/src/trace_processor/db/column/id_storage.h
index e8304f5..61769dd 100644
--- a/src/trace_processor/db/column/id_storage.h
+++ b/src/trace_processor/db/column/id_storage.h
@@ -17,44 +17,55 @@
#define SRC_TRACE_PROCESSOR_DB_COLUMN_ID_STORAGE_H_
#include <cstdint>
+#include <memory>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Storage for Id columns.
-class IdStorage final : public Column {
+class IdStorage final : public DataNode {
public:
- explicit IdStorage(uint32_t size) : size_(size) {}
+ explicit IdStorage(uint32_t size);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override { return size_; }
-
- std::string DebugString() const override { return "IdStorage"; }
+ std::unique_ptr<DataNode::Queryable> MakeQueryable() override;
private:
- using Id = uint32_t;
+ class Queryable : public DataNode::Queryable {
+ public:
+ explicit Queryable(uint32_t size);
- BitVector IndexSearch(FilterOp, Id, uint32_t*, uint32_t) const;
- Range BinarySearchIntrinsic(FilterOp op, Id, Range search_range) const;
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t*, uint32_t) const override;
+
+ void Sort(uint32_t*, uint32_t) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return size_; }
+
+ std::string DebugString() const override { return "IdStorage"; }
+
+ private:
+ using Id = uint32_t;
+
+ BitVector IndexSearch(FilterOp, Id, uint32_t*, uint32_t) const;
+ static Range BinarySearchIntrinsic(FilterOp, Id, Range);
+
+ const uint32_t size_ = 0;
+ };
const uint32_t size_ = 0;
};
diff --git a/src/trace_processor/db/column/id_storage_unittest.cc b/src/trace_processor/db/column/id_storage_unittest.cc
index 7cffe47..5d17187 100644
--- a/src/trace_processor/db/column/id_storage_unittest.cc
+++ b/src/trace_processor/db/column/id_storage_unittest.cc
@@ -14,10 +14,13 @@
* limitations under the License.
*/
#include "src/trace_processor/db/column/id_storage.h"
+#include <cstdint>
#include <limits>
+#include <vector>
#include "perfetto/trace_processor/basic_types.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
@@ -41,68 +44,72 @@
TEST(IdStorage, InvalidSearchConstraints) {
IdStorage storage(100);
+ auto queryable = storage.MakeQueryable();
// NULL checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
- SearchValidationResult::kAllData);
+ ASSERT_EQ(
+ queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
+ SearchValidationResult::kAllData);
// FilterOp checks
ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
+ queryable->ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
SearchValidationResult::kNoData);
- ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kRegex),
- SearchValidationResult::kNoData);
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::Long(15),
+ FilterOp::kRegex),
+ SearchValidationResult::kNoData);
// Type checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue::String("cheese"),
- FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::String("cheese"),
+ FilterOp::kGe),
SearchValidationResult::kNoData);
// With double
ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Double(-1), FilterOp::kGe),
+ queryable->ValidateSearchConstraints(SqlValue::Double(-1), FilterOp::kGe),
SearchValidationResult::kAllData);
// Value bounds
SqlValue max_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kEq),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kNe),
SearchValidationResult::kAllData);
SqlValue min_val = SqlValue::Long(-1);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kNe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kEq),
SearchValidationResult::kNoData);
}
TEST(IdStorage, SearchEqSimple) {
IdStorage storage(100);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(15), Range(10, 20))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(15), Range(10, 20))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 1u);
ASSERT_EQ(range.start, 15u);
ASSERT_EQ(range.end, 16u);
@@ -110,196 +117,213 @@
TEST(IdStorage, SearchEqOnRangeBoundary) {
IdStorage storage(100);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(20), Range(10, 20))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(20), Range(10, 20))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
TEST(IdStorage, SearchEqOutsideRange) {
IdStorage storage(100);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(25), Range(10, 20))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(25), Range(10, 20))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
TEST(IdStorage, SearchEqTooBig) {
IdStorage storage(100);
+ auto queryable = storage.MakeQueryable();
Range range =
- storage.Search(FilterOp::kEq, SqlValue::Long(125), Range(10, 20))
+ queryable->Search(FilterOp::kEq, SqlValue::Long(125), Range(10, 20))
.TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
TEST(IdStorage, SearchSimple) {
IdStorage storage(10);
+ auto queryable = storage.MakeQueryable();
SqlValue val = SqlValue::Long(5);
Range filter_range(3, 7);
FilterOp op = FilterOp::kEq;
- auto res = storage.Search(op, val, filter_range);
+ auto res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5));
op = FilterOp::kNe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 6));
op = FilterOp::kLe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
op = FilterOp::kLt;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
op = FilterOp::kGe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(5, 6));
op = FilterOp::kGt;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6));
}
TEST(IdStorage, IndexSearchSimple) {
IdStorage storage(10);
+ auto queryable = storage.MakeQueryable();
SqlValue val = SqlValue::Long(5);
std::vector<uint32_t> indices_vec{5, 4, 3, 9, 8, 7};
Indices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
- auto res = storage.IndexSearch(op, val, indices);
+ auto res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
op = FilterOp::kNe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
op = FilterOp::kLe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
op = FilterOp::kLt;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2));
op = FilterOp::kGe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 3, 4, 5));
op = FilterOp::kGt;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
}
TEST(IdStorage, OrderedIndexSearch) {
IdStorage storage(10);
+ auto queryable = storage.MakeQueryable();
std::vector<uint32_t> indices_vec{0, 1, 2, 4, 4};
Indices indices{indices_vec.data(), 5, Indices::State::kMonotonic};
Range range =
- storage.OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
+ queryable->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 2u);
ASSERT_EQ(range.end, 3u);
- range = storage.OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 3u);
ASSERT_EQ(range.end, 5u);
- range = storage.OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 2u);
ASSERT_EQ(range.end, 5u);
- range = storage.OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 2u);
- range = storage.OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 3u);
}
TEST(IdStorage, IndexSearchEqTooBig) {
IdStorage storage(12);
+ auto queryable = storage.MakeQueryable();
std::vector<uint32_t> indices{1, 3, 5, 7, 9, 11, 2, 4};
- BitVector bv = storage
- .IndexSearch(FilterOp::kEq, SqlValue::Long(20),
- Indices{indices.data(),
- static_cast<uint32_t>(indices.size()),
- Indices::State::kMonotonic})
- .TakeIfBitVector();
+ BitVector bv =
+ queryable
+ ->IndexSearch(
+ FilterOp::kEq, SqlValue::Long(20),
+ Indices{indices.data(), static_cast<uint32_t>(indices.size()),
+ Indices::State::kMonotonic})
+ .TakeIfBitVector();
ASSERT_EQ(bv.CountSetBits(), 0u);
}
TEST(IdStorage, SearchWithIdAsDoubleSimple) {
IdStorage storage(100);
+ auto queryable = storage.MakeQueryable();
SqlValue double_val = SqlValue::Double(15.0);
SqlValue long_val = SqlValue::Long(15);
Range range(10, 20);
- auto res_double = storage.Search(FilterOp::kEq, double_val, range);
- auto res_long = storage.Search(FilterOp::kEq, long_val, range);
+ auto res_double = queryable->Search(FilterOp::kEq, double_val, range);
+ auto res_long = queryable->Search(FilterOp::kEq, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
- res_double = storage.Search(FilterOp::kNe, double_val, range);
- res_long = storage.Search(FilterOp::kNe, long_val, range);
+ res_double = queryable->Search(FilterOp::kNe, double_val, range);
+ res_long = queryable->Search(FilterOp::kNe, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
- res_double = storage.Search(FilterOp::kLe, double_val, range);
- res_long = storage.Search(FilterOp::kLe, long_val, range);
+ res_double = queryable->Search(FilterOp::kLe, double_val, range);
+ res_long = queryable->Search(FilterOp::kLe, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
- res_double = storage.Search(FilterOp::kLt, double_val, range);
- res_long = storage.Search(FilterOp::kLt, long_val, range);
+ res_double = queryable->Search(FilterOp::kLt, double_val, range);
+ res_long = queryable->Search(FilterOp::kLt, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
- res_double = storage.Search(FilterOp::kGe, double_val, range);
- res_long = storage.Search(FilterOp::kGe, long_val, range);
+ res_double = queryable->Search(FilterOp::kGe, double_val, range);
+ res_long = queryable->Search(FilterOp::kGe, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
- res_double = storage.Search(FilterOp::kGt, double_val, range);
- res_long = storage.Search(FilterOp::kGt, long_val, range);
+ res_double = queryable->Search(FilterOp::kGt, double_val, range);
+ res_long = queryable->Search(FilterOp::kGt, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res_double),
utils::ToIndexVectorForTests(res_long));
}
TEST(IdStorage, SearchWithIdAsDouble) {
IdStorage storage(100);
+ auto queryable = storage.MakeQueryable();
Range range(10, 20);
SqlValue val = SqlValue::Double(15.5);
- auto res = storage.Search(FilterOp::kEq, val, range);
+ auto res = queryable->Search(FilterOp::kEq, val, range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, range);
+ res = queryable->Search(FilterOp::kNe, val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(res).size(), 20u);
- res = storage.Search(FilterOp::kLe, val, range);
+ res = queryable->Search(FilterOp::kLe, val, range);
ASSERT_THAT(utils::ToIndexVectorForTests(res),
ElementsAre(10, 11, 12, 13, 14, 15));
- res = storage.Search(FilterOp::kLt, val, range);
+ res = queryable->Search(FilterOp::kLt, val, range);
ASSERT_THAT(utils::ToIndexVectorForTests(res),
ElementsAre(10, 11, 12, 13, 14, 15));
- res = storage.Search(FilterOp::kGe, val, range);
+ res = queryable->Search(FilterOp::kGe, val, range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(16, 17, 18, 19));
- res = storage.Search(FilterOp::kGt, val, range);
+ res = queryable->Search(FilterOp::kGt, val, range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(16, 17, 18, 19));
}
TEST(IdStorage, Sort) {
std::vector<uint32_t> order{4, 3, 6, 1, 5};
IdStorage storage(10);
- storage.Sort(order.data(), 5);
+ auto queryable = storage.MakeQueryable();
+ queryable->Sort(order.data(), 5);
std::vector<uint32_t> sorted_order{1, 3, 4, 5, 6};
ASSERT_EQ(order, sorted_order);
diff --git a/src/trace_processor/db/column/null_overlay.cc b/src/trace_processor/db/column/null_overlay.cc
index 31a5794..fa93c1f 100644
--- a/src/trace_processor/db/column/null_overlay.cc
+++ b/src/trace_processor/db/column/null_overlay.cc
@@ -16,19 +16,25 @@
#include "src/trace_processor/db/column/null_overlay.h"
+#include <algorithm>
#include <cstdint>
+#include <iterator>
+#include <memory>
+#include <utility>
+#include <vector>
+#include "perfetto/base/logging.h"
+#include "perfetto/public/compiler.h"
#include "perfetto/trace_processor/basic_types.h"
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/containers/row_map.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/tp_metatrace.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+#include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+
+namespace perfetto::trace_processor::column {
namespace {
BitVector ReconcileStorageResult(FilterOp op,
@@ -72,7 +78,20 @@
} // namespace
-SearchValidationResult NullOverlay::ValidateSearchConstraints(
+NullOverlay::NullOverlay(const BitVector* non_null) : non_null_(non_null) {}
+
+std::unique_ptr<DataNode::Queryable> NullOverlay::MakeQueryable(
+ std::unique_ptr<DataNode::Queryable> inner) {
+ return std::make_unique<Queryable>(std::move(inner), non_null_);
+}
+
+NullOverlay::Queryable::Queryable(std::unique_ptr<DataNode::Queryable> innner,
+ const BitVector* non_null)
+ : inner_(std::move(innner)), non_null_(non_null) {
+ PERFETTO_DCHECK(non_null_->CountSetBits() <= inner_->size());
+}
+
+SearchValidationResult NullOverlay::Queryable::ValidateSearchConstraints(
SqlValue sql_val,
FilterOp op) const {
if (op == FilterOp::kIsNull) {
@@ -82,16 +101,10 @@
return inner_->ValidateSearchConstraints(sql_val, op);
}
-NullOverlay::NullOverlay(std::unique_ptr<Column> storage,
- const BitVector* non_null)
- : inner_(std::move(storage)), non_null_(non_null) {
- PERFETTO_DCHECK(non_null_->CountSetBits() <= inner_->size());
-}
-
-RangeOrBitVector NullOverlay::Search(FilterOp op,
- SqlValue sql_val,
- Range in) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "NullOverlay::Search");
+RangeOrBitVector NullOverlay::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range in) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "NullOverlay::Queryable::Search");
if (op == FilterOp::kIsNull) {
switch (inner_->ValidateSearchConstraints(sql_val, op)) {
@@ -121,10 +134,11 @@
return RangeOrBitVector(std::move(res));
}
-RangeOrBitVector NullOverlay::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "NullOverlay::IndexSearch");
+RangeOrBitVector NullOverlay::Queryable::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "NullOverlay::Queryable::IndexSearch");
if (op == FilterOp::kIsNull) {
switch (inner_->ValidateSearchConstraints(sql_val, op)) {
@@ -168,35 +182,36 @@
return RangeOrBitVector(std::move(res));
}
-Range NullOverlay::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range NullOverlay::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
// For NOT EQUAL the translation or results from EQUAL needs to be done by the
// caller.
PERFETTO_CHECK(op != FilterOp::kNe);
- PERFETTO_TP_TRACE(metatrace::Category::DB, "NullOverlay::OrderedIndexSearch");
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "NullOverlay::Queryable::OrderedIndexSearch");
// We assume all NULLs are ordered to be in the front. We are looking for the
// first index that points to non NULL value.
const uint32_t* first_non_null =
std::partition_point(indices.data, indices.data + indices.size,
[this](uint32_t i) { return !non_null_->IsSet(i); });
- const uint32_t non_null_offset =
+ auto non_null_offset =
static_cast<uint32_t>(std::distance(indices.data, first_non_null));
- const uint32_t non_null_size = static_cast<uint32_t>(
+ auto non_null_size = static_cast<uint32_t>(
std::distance(first_non_null, indices.data + indices.size));
if (op == FilterOp::kIsNull) {
- return Range(0, non_null_offset);
+ return {0, non_null_offset};
}
if (op == FilterOp::kIsNotNull) {
switch (inner_->ValidateSearchConstraints(sql_val, op)) {
case SearchValidationResult::kNoData:
- return Range();
+ return {};
case SearchValidationResult::kAllData:
- return Range(non_null_offset, indices.size);
+ return {non_null_offset, indices.size};
case SearchValidationResult::kOk:
break;
}
@@ -211,26 +226,24 @@
Range inner_range = inner_->OrderedIndexSearch(
op, sql_val, Indices{storage_iv.data(), non_null_size, indices.state});
- return Range(inner_range.start + non_null_offset,
- inner_range.end + non_null_offset);
+ return {inner_range.start + non_null_offset,
+ inner_range.end + non_null_offset};
}
-void NullOverlay::StableSort(uint32_t*, uint32_t) const {
+void NullOverlay::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void NullOverlay::Sort(uint32_t*, uint32_t) const {
+void NullOverlay::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void NullOverlay::Serialize(StorageProto* storage) const {
+void NullOverlay::Queryable::Serialize(StorageProto* storage) const {
auto* null_storage = storage->set_null_overlay();
non_null_->Serialize(null_storage->set_bit_vector());
inner_->Serialize(null_storage->set_storage());
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/null_overlay.h b/src/trace_processor/db/column/null_overlay.h
index 1bc92b7..3f0cbc7 100644
--- a/src/trace_processor/db/column/null_overlay.h
+++ b/src/trace_processor/db/column/null_overlay.h
@@ -23,38 +23,48 @@
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Overlay which introduces the layer of nullability. Specifically, spreads out
// the storage with nulls using a BitVector.
-class NullOverlay : public Column {
+class NullOverlay : public DataNode {
public:
- NullOverlay(std::unique_ptr<Column>, const BitVector* non_null);
+ explicit NullOverlay(const BitVector* non_null);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override { return non_null_->size(); }
-
- std::string DebugString() const override { return "NullOverlay"; }
+ std::unique_ptr<Queryable> MakeQueryable(std::unique_ptr<Queryable>) override;
private:
- std::unique_ptr<Column> inner_ = nullptr;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(std::unique_ptr<DataNode::Queryable>, const BitVector* non_null);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return non_null_->size(); }
+
+ std::string DebugString() const override { return "NullOverlay"; }
+
+ private:
+ std::unique_ptr<DataNode::Queryable> inner_ = nullptr;
+ const BitVector* non_null_ = nullptr;
+ };
+
const BitVector* non_null_ = nullptr;
};
diff --git a/src/trace_processor/db/column/null_overlay_unittest.cc b/src/trace_processor/db/column/null_overlay_unittest.cc
index ea2d985..2f58068 100644
--- a/src/trace_processor/db/column/null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/null_overlay_unittest.cc
@@ -16,9 +16,11 @@
#include "src/trace_processor/db/column/null_overlay.h"
+#include <cstdint>
#include <memory>
#include <vector>
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/column/fake_storage.h"
@@ -27,9 +29,7 @@
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
namespace {
using testing::ElementsAre;
@@ -37,111 +37,131 @@
TEST(NullOverlay, SearchInputInsideBoundary) {
BitVector bv{0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0};
- NullOverlay storage(FakeStorage::SearchAll(4u), &bv);
+ auto fake = FakeStorage::SearchAll(4u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(1, 6));
+ auto res = queryable->Search(FilterOp::kGt, SqlValue::Long(0), Range(1, 6));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
TEST(NullOverlay, SearchInputOutsideBoundary) {
BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
- NullOverlay storage(FakeStorage::SearchAll(5u), &bv);
+ auto fake = FakeStorage::SearchAll(5u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(3, 8));
+ auto res = queryable->Search(FilterOp::kGt, SqlValue::Long(0), Range(3, 8));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 7));
}
TEST(NullOverlay, SubsetResultOutsideBoundary) {
BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
- NullOverlay storage(FakeStorage::SearchSubset(5u, Range(1, 3)), &bv);
+ auto fake = FakeStorage::SearchSubset(5u, Range(1, 3));
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
+ auto res = queryable->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
TEST(NullOverlay, SubsetResultOnBoundary) {
BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
- NullOverlay storage(FakeStorage::SearchAll(5u), &bv);
+ auto fake = FakeStorage::SearchAll(5u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
+ auto res = queryable->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4, 7, 8));
}
TEST(NullOverlay, BitVectorSubset) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1}),
- &bv);
+ auto fake = FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1});
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 8));
+ auto res = queryable->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 8));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 6));
}
TEST(NullOverlay, BitVectorSubsetIsNull) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1}),
- &bv);
+ auto fake = FakeStorage::SearchSubset(4u, BitVector{0, 1, 0, 1});
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kIsNull, SqlValue(), Range(0, 8));
+ auto res = queryable->Search(FilterOp::kIsNull, SqlValue(), Range(0, 8));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2, 3, 4, 6, 7));
}
TEST(NullOverlay, IndexSearchAllElements) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchAll(4u), &bv);
+ auto fake = FakeStorage::SearchAll(4u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{1, 5, 2};
- auto res =
- storage.IndexSearch(FilterOp::kGt, SqlValue::Long(0),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
+ auto res = queryable->IndexSearch(
+ FilterOp::kGt, SqlValue::Long(0),
+ Indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
}
TEST(NullOverlay, IndexSearchPartialElements) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchAll(4u), &bv);
+ auto fake = FakeStorage::SearchAll(4u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{1, 4, 2};
- auto res =
- storage.IndexSearch(FilterOp::kGt, SqlValue::Long(0),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
+ auto res = queryable->IndexSearch(
+ FilterOp::kGt, SqlValue::Long(0),
+ Indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2));
}
TEST(NullOverlay, IndexSearchIsNullOpEmptyRes) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchNone(4u), &bv);
+ auto fake = FakeStorage::SearchNone(4u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{0, 3, 5, 4, 2};
- auto res =
- storage.IndexSearch(FilterOp::kIsNull, SqlValue(),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
+ auto res = queryable->IndexSearch(
+ FilterOp::kIsNull, SqlValue(),
+ Indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 3));
}
TEST(NullOverlay, IndexSearchIsNullOp) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchSubset(4u, Range(2, 3)), &bv);
+ auto fake = FakeStorage::SearchSubset(4u, Range(2, 3));
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{0, 3, 2, 4, 5};
- auto res =
- storage.IndexSearch(FilterOp::kIsNull, SqlValue(),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
+ auto res = queryable->IndexSearch(
+ FilterOp::kIsNull, SqlValue(),
+ Indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 3, 4));
}
TEST(NullOverlay, IndexSearchIsNotNullOp) {
BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
- NullOverlay storage(FakeStorage::SearchAll(4u), &bv);
+ auto fake = FakeStorage::SearchAll(4u);
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{0, 3, 4};
- auto res =
- storage.IndexSearch(FilterOp::kIsNotNull, SqlValue(),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
+ auto res = queryable->IndexSearch(
+ FilterOp::kIsNotNull, SqlValue(),
+ Indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
}
@@ -149,7 +169,9 @@
BitVector bv{0, 1, 1, 1, 0, 1};
// Passing values in final storage (on normal operations)
// 0, 1, 0, 1, 0, 0
- NullOverlay storage(FakeStorage::SearchSubset(4, BitVector{1, 0, 1, 0}), &bv);
+ auto fake = FakeStorage::SearchSubset(4, BitVector{1, 0, 1, 0});
+ NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
// Passing values on final data
// NULL, NULL, 0, 1, 1
@@ -158,36 +180,40 @@
Indices::State::kNonmonotonic};
Range res =
- storage.OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ queryable->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 2u);
- res = storage.OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = storage.OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = storage.OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = storage.OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = storage.OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = storage.OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
+ res =
+ queryable->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
}
} // namespace
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/numeric_storage.cc b/src/trace_processor/db/column/numeric_storage.cc
index 1a61977..182c1ca 100644
--- a/src/trace_processor/db/column/numeric_storage.cc
+++ b/src/trace_processor/db/column/numeric_storage.cc
@@ -22,22 +22,27 @@
#include <cstddef>
#include <cstdint>
#include <functional>
+#include <limits>
+#include <memory>
#include <string>
+#include <utility>
+#include <variant>
#include "perfetto/base/compiler.h"
#include "perfetto/base/logging.h"
#include "perfetto/public/compiler.h"
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "src/trace_processor/tp_metatrace.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+#include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+
+namespace perfetto::trace_processor::column {
namespace {
using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
@@ -106,8 +111,9 @@
[data, search_range](auto val_data) {
using T = decltype(val_data);
const T* typed_start = static_cast<const T*>(data);
- auto lower = std::lower_bound(typed_start + search_range.start,
- typed_start + search_range.end, val_data);
+ const auto* lower =
+ std::lower_bound(typed_start + search_range.start,
+ typed_start + search_range.end, val_data);
return static_cast<uint32_t>(std::distance(typed_start, lower));
},
val);
@@ -120,8 +126,9 @@
[data, search_range](auto val_data) {
using T = decltype(val_data);
const T* typed_start = static_cast<const T*>(data);
- auto upper = std::upper_bound(typed_start + search_range.start,
- typed_start + search_range.end, val_data);
+ const auto* upper =
+ std::upper_bound(typed_start + search_range.start,
+ typed_start + search_range.end, val_data);
return static_cast<uint32_t>(std::distance(typed_start, upper));
},
val);
@@ -129,7 +136,7 @@
template <typename T>
uint32_t TypedLowerBoundExtrinsic(T val, const T* data, Indices indices) {
- auto lower = std::lower_bound(
+ const auto* lower = std::lower_bound(
indices.data, indices.data + indices.size, val,
[data](uint32_t index, T value) { return data[index] < value; });
return static_cast<uint32_t>(std::distance(indices.data, lower));
@@ -139,19 +146,19 @@
NumericValue val,
Indices indices) {
if (const auto* u32 = std::get_if<uint32_t>(&val)) {
- auto* start = static_cast<const uint32_t*>(data);
+ const auto* start = static_cast<const uint32_t*>(data);
return TypedLowerBoundExtrinsic(*u32, start, indices);
}
if (const auto* i64 = std::get_if<int64_t>(&val)) {
- auto* start = static_cast<const int64_t*>(data);
+ const auto* start = static_cast<const int64_t*>(data);
return TypedLowerBoundExtrinsic(*i64, start, indices);
}
if (const auto* i32 = std::get_if<int32_t>(&val)) {
- auto* start = static_cast<const int32_t*>(data);
+ const auto* start = static_cast<const int32_t*>(data);
return TypedLowerBoundExtrinsic(*i32, start, indices);
}
if (const auto* db = std::get_if<double>(&val)) {
- auto* start = static_cast<const double*>(data);
+ const auto* start = static_cast<const double*>(data);
return TypedLowerBoundExtrinsic(*db, start, indices);
}
PERFETTO_FATAL("Type not handled");
@@ -164,7 +171,7 @@
[data, indices](auto val_data) {
using T = decltype(val_data);
const T* typed_start = static_cast<const T*>(data);
- auto upper =
+ const auto* upper =
std::upper_bound(indices.data, indices.data + indices.size,
val_data, [typed_start](T value, uint32_t index) {
return value < typed_start[index];
@@ -210,12 +217,11 @@
double double_val = sql_val->AsDouble();
// Case when |sql_val| can be interpreted as a SqlValue::Double.
- if (std::equal_to<double>()(
- static_cast<double>(static_cast<int64_t>(double_val)), double_val)) {
+ if (std::equal_to<>()(static_cast<double>(static_cast<int64_t>(double_val)),
+ double_val)) {
*sql_val = SqlValue::Long(static_cast<int64_t>(double_val));
return SearchValidationResult::kOk;
}
-
// Logic for when the value is a real double.
switch (op) {
case FilterOp::kEq:
@@ -244,7 +250,7 @@
SearchValidationResult DoubleColumnWithInt(SqlValue* sql_val, FilterOp op) {
int64_t i = sql_val->AsLong();
- double i_as_d = static_cast<double>(i);
+ auto i_as_d = static_cast<double>(i);
// Case when |sql_val| can be interpreted as a SqlValue::Long.
if (std::equal_to<int64_t>()(i, static_cast<int64_t>(i_as_d))) {
@@ -282,7 +288,23 @@
} // namespace
-SearchValidationResult NumericStorageBase::ValidateSearchConstraints(
+NumericStorageBase::NumericStorageBase(const void* data,
+ uint32_t size,
+ ColumnType type,
+ bool is_sorted)
+ : size_(size), data_(data), storage_type_(type), is_sorted_(is_sorted) {}
+
+std::unique_ptr<DataNode::Queryable> NumericStorageBase::MakeQueryable() {
+ return std::make_unique<Queryable>(data_, size_, storage_type_, is_sorted_);
+}
+
+NumericStorageBase::Queryable::Queryable(const void* data,
+ uint32_t size,
+ ColumnType type,
+ bool is_sorted)
+ : size_(size), data_(data), storage_type_(type), is_sorted_(is_sorted) {}
+
+SearchValidationResult NumericStorageBase::Queryable::ValidateSearchConstraints(
SqlValue val,
FilterOp op) const {
// NULL checks.
@@ -391,18 +413,19 @@
PERFETTO_FATAL("For GCC");
}
-RangeOrBitVector NumericStorageBase::Search(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
+RangeOrBitVector NumericStorageBase::Queryable::Search(
+ FilterOp op,
+ SqlValue sql_val,
+ Range search_range) const {
PERFETTO_DCHECK(search_range.end <= size_);
- PERFETTO_TP_TRACE(metatrace::Category::DB, "NumericStorage::Search",
- [&search_range, op](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(search_range.start));
- r->AddArg("End", std::to_string(search_range.end));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "NumericStorage::Queryable::Search",
+ [&search_range, op](metatrace::Record* r) {
+ r->AddArg("Start", std::to_string(search_range.start));
+ r->AddArg("End", std::to_string(search_range.end));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
// Mismatched types - value is double and column is int.
if (sql_val.type == SqlValue::kDouble &&
@@ -438,22 +461,22 @@
bv.Resize(search_range.end, true);
return RangeOrBitVector(std::move(bv));
}
-
return RangeOrBitVector(LinearSearchInternal(op, val, search_range));
}
-RangeOrBitVector NumericStorageBase::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+RangeOrBitVector NumericStorageBase::Queryable::IndexSearch(
+ FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
PERFETTO_DCHECK(*std::max_element(indices.data, indices.data + indices.size) <
size_);
- PERFETTO_TP_TRACE(metatrace::Category::DB, "NumericStorage::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "NumericStorage::Queryable::IndexSearch",
+ [indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.size));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
// Mismatched types - value is double and column is int.
if (sql_val.type == SqlValue::kDouble &&
@@ -476,19 +499,18 @@
}
NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
-
return RangeOrBitVector(
IndexSearchInternal(op, val, indices.data, indices.size));
}
-Range NumericStorageBase::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range NumericStorageBase::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
PERFETTO_DCHECK(*std::max_element(indices.data, indices.data + indices.size) <
size_);
PERFETTO_TP_TRACE(
- metatrace::Category::DB, "NumericStorage::OrderedIndexSearch",
+ metatrace::Category::DB, "NumericStorage::Queryable::OrderedIndexSearch",
[indices, op](metatrace::Record* r) {
r->AddArg("Count", std::to_string(indices.size));
r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
@@ -536,16 +558,16 @@
switch (op) {
case FilterOp::kEq:
- return Range(LowerBoundExtrinsic(data_, val, indices),
- UpperBoundExtrinsic(data_, val, indices));
+ return {LowerBoundExtrinsic(data_, val, indices),
+ UpperBoundExtrinsic(data_, val, indices)};
case FilterOp::kLe:
- return Range(0, UpperBoundExtrinsic(data_, val, indices));
+ return {0, UpperBoundExtrinsic(data_, val, indices)};
case FilterOp::kLt:
- return Range(0, LowerBoundExtrinsic(data_, val, indices));
+ return {0, LowerBoundExtrinsic(data_, val, indices)};
case FilterOp::kGe:
- return Range(LowerBoundExtrinsic(data_, val, indices), indices.size);
+ return {LowerBoundExtrinsic(data_, val, indices), indices.size};
case FilterOp::kGt:
- return Range(UpperBoundExtrinsic(data_, val, indices), indices.size);
+ return {UpperBoundExtrinsic(data_, val, indices), indices.size};
case FilterOp::kNe:
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
@@ -556,21 +578,22 @@
PERFETTO_FATAL("For GCC");
}
-BitVector NumericStorageBase::LinearSearchInternal(FilterOp op,
- NumericValue val,
- Range range) const {
+BitVector NumericStorageBase::Queryable::LinearSearchInternal(
+ FilterOp op,
+ NumericValue val,
+ Range range) const {
BitVector::Builder builder(range.end, range.start);
if (const auto* u32 = std::get_if<uint32_t>(&val)) {
- auto* start = static_cast<const uint32_t*>(data_) + range.start;
+ const auto* start = static_cast<const uint32_t*>(data_) + range.start;
TypedLinearSearch(*u32, start, op, builder);
} else if (const auto* i64 = std::get_if<int64_t>(&val)) {
- auto* start = static_cast<const int64_t*>(data_) + range.start;
+ const auto* start = static_cast<const int64_t*>(data_) + range.start;
TypedLinearSearch(*i64, start, op, builder);
} else if (const auto* i32 = std::get_if<int32_t>(&val)) {
- auto* start = static_cast<const int32_t*>(data_) + range.start;
+ const auto* start = static_cast<const int32_t*>(data_) + range.start;
TypedLinearSearch(*i32, start, op, builder);
} else if (const auto* db = std::get_if<double>(&val)) {
- auto* start = static_cast<const double*>(data_) + range.start;
+ const auto* start = static_cast<const double*>(data_) + range.start;
TypedLinearSearch(*db, start, op, builder);
} else {
PERFETTO_DFATAL("Invalid");
@@ -578,7 +601,7 @@
return std::move(builder).Build();
}
-BitVector NumericStorageBase::IndexSearchInternal(
+BitVector NumericStorageBase::Queryable::IndexSearchInternal(
FilterOp op,
NumericValue val,
const uint32_t* indices,
@@ -599,37 +622,37 @@
return std::move(builder).Build();
}
-Range NumericStorageBase::BinarySearchIntrinsic(FilterOp op,
- NumericValue val,
- Range search_range) const {
+Range NumericStorageBase::Queryable::BinarySearchIntrinsic(
+ FilterOp op,
+ NumericValue val,
+ Range search_range) const {
switch (op) {
case FilterOp::kEq:
- return Range(LowerBoundIntrinsic(data_, val, search_range),
- UpperBoundIntrinsic(data_, val, search_range));
+ return {LowerBoundIntrinsic(data_, val, search_range),
+ UpperBoundIntrinsic(data_, val, search_range)};
case FilterOp::kLe: {
- return Range(search_range.start,
- UpperBoundIntrinsic(data_, val, search_range));
+ return {search_range.start,
+ UpperBoundIntrinsic(data_, val, search_range)};
}
case FilterOp::kLt:
- return Range(search_range.start,
- LowerBoundIntrinsic(data_, val, search_range));
+ return {search_range.start,
+ LowerBoundIntrinsic(data_, val, search_range)};
case FilterOp::kGe:
- return Range(LowerBoundIntrinsic(data_, val, search_range),
- search_range.end);
+ return {LowerBoundIntrinsic(data_, val, search_range), search_range.end};
case FilterOp::kGt:
- return Range(UpperBoundIntrinsic(data_, val, search_range),
- search_range.end);
+ return {UpperBoundIntrinsic(data_, val, search_range), search_range.end};
case FilterOp::kNe:
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
case FilterOp::kGlob:
case FilterOp::kRegex:
- return Range();
+ return {};
}
- return Range();
+ return {};
}
-void NumericStorageBase::StableSort(uint32_t* rows, uint32_t rows_size) const {
+void NumericStorageBase::Queryable::StableSort(uint32_t* rows,
+ uint32_t rows_size) const {
std::visit(
[this, &rows, rows_size](auto val_data) {
using T = decltype(val_data);
@@ -644,12 +667,12 @@
GetNumericTypeVariant(storage_type_, SqlValue::Long(0)));
}
-void NumericStorageBase::Sort(uint32_t*, uint32_t) const {
+void NumericStorageBase::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_ELOG("Not implemented");
}
-void NumericStorageBase::Serialize(StorageProto* msg) const {
+void NumericStorageBase::Queryable::Serialize(StorageProto* msg) const {
auto* numeric_storage_msg = msg->set_numeric_storage();
numeric_storage_msg->set_is_sorted(is_sorted_);
numeric_storage_msg->set_column_type(static_cast<uint32_t>(storage_type_));
@@ -677,6 +700,4 @@
static_cast<size_t>(type_size) * size_);
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/numeric_storage.h b/src/trace_processor/db/column/numeric_storage.h
index d50d97b..9f24353 100644
--- a/src/trace_processor/db/column/numeric_storage.h
+++ b/src/trace_processor/db/column/numeric_storage.h
@@ -17,60 +17,73 @@
#define SRC_TRACE_PROCESSOR_DB_COLUMN_NUMERIC_STORAGE_H_
#include <cstdint>
+#include <memory>
#include <string>
#include <variant>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Storage for all numeric type data (i.e. doubles, int32, int64, uint32).
-class NumericStorageBase : public Column {
+class NumericStorageBase : public DataNode {
public:
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- inline uint32_t size() const override { return size_; }
-
- std::string DebugString() const override { return "NumericStorage"; }
+ std::unique_ptr<DataNode::Queryable> MakeQueryable() override;
protected:
NumericStorageBase(const void* data,
uint32_t size,
ColumnType type,
- bool is_sorted = false)
- : size_(size), data_(data), storage_type_(type), is_sorted_(is_sorted) {}
+ bool is_sorted);
private:
- // All viable numeric values for ColumnTypes.
- using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(const void* data, uint32_t size, ColumnType type, bool is_sorted);
- BitVector LinearSearchInternal(FilterOp op, NumericValue val, Range) const;
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
- BitVector IndexSearchInternal(FilterOp op,
- NumericValue value,
- const uint32_t* indices,
- uint32_t indices_count) const;
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
- Range BinarySearchIntrinsic(FilterOp op,
- NumericValue val,
- Range search_range) const;
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t*, uint32_t) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void Sort(uint32_t*, uint32_t) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ inline uint32_t size() const override { return size_; }
+
+ std::string DebugString() const override { return "NumericStorage"; }
+
+ private:
+ // All viable numeric values for ColumnTypes.
+ using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
+
+ BitVector LinearSearchInternal(FilterOp op, NumericValue val, Range) const;
+
+ BitVector IndexSearchInternal(FilterOp op,
+ NumericValue value,
+ const uint32_t* indices,
+ uint32_t indices_count) const;
+
+ Range BinarySearchIntrinsic(FilterOp op,
+ NumericValue val,
+ Range search_range) const;
+
+ const uint32_t size_ = 0;
+ const void* data_ = nullptr;
+ const ColumnType storage_type_ = ColumnType::kDummy;
+ const bool is_sorted_ = false;
+ };
const uint32_t size_ = 0;
const void* data_ = nullptr;
diff --git a/src/trace_processor/db/column/numeric_storage_unittest.cc b/src/trace_processor/db/column/numeric_storage_unittest.cc
index 428fcf4..3d5cecd 100644
--- a/src/trace_processor/db/column/numeric_storage_unittest.cc
+++ b/src/trace_processor/db/column/numeric_storage_unittest.cc
@@ -14,9 +14,16 @@
* limitations under the License.
*/
#include "src/trace_processor/db/column/numeric_storage.h"
+
+#include <cmath>
#include <cstdint>
+#include <limits>
+#include <numeric>
+#include <tuple>
+#include <vector>
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "src/trace_processor/db/compare.h"
@@ -39,28 +46,30 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
Range test_range(20, 100);
Range full_range(0, 100);
Range empty_range;
// NULL checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
- SearchValidationResult::kAllData);
+ ASSERT_EQ(
+ queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
+ SearchValidationResult::kAllData);
// FilterOp checks
ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
+ queryable->ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
SearchValidationResult::kNoData);
- ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kRegex),
- SearchValidationResult::kNoData);
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::Long(15),
+ FilterOp::kRegex),
+ SearchValidationResult::kNoData);
// Type checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue::String("cheese"),
- FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::String("cheese"),
+ FilterOp::kGe),
SearchValidationResult::kNoData);
}
@@ -68,37 +77,38 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
SqlValue max_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kEq),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kNe),
SearchValidationResult::kAllData);
SqlValue min_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kNe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kEq),
SearchValidationResult::kNoData);
}
@@ -106,37 +116,38 @@
std::vector<int32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
SqlValue max_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 10);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kEq),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kNe),
SearchValidationResult::kAllData);
SqlValue min_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kNe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kEq),
SearchValidationResult::kNoData);
}
@@ -145,8 +156,9 @@
std::vector<uint32_t> out = {0, 1, 2, 3, 4, 5, 6, 7, 8};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
RowMap rm(0, 9);
- storage.StableSort(out.data(), 9);
+ queryable->StableSort(out.data(), 9);
std::vector<uint32_t> stable_out{0, 3, 6, 1, 4, 7, 2, 5, 8};
ASSERT_EQ(out, stable_out);
@@ -157,8 +169,9 @@
std::vector<uint32_t> out = {1, 7, 4, 0, 6, 3, 2, 5, 8};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
RowMap rm(0, 9);
- storage.StableSort(out.data(), 9);
+ queryable->StableSort(out.data(), 9);
std::vector<uint32_t> stable_out{0, 6, 3, 1, 7, 4, 2, 5, 8};
ASSERT_EQ(out, stable_out);
@@ -167,106 +180,110 @@
TEST(NumericStorage, Search) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Long(4);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3, 4));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
}
TEST(NumericStorage, SearchCompareWithNegative) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Long(-3);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
}
TEST(NumericStorage, IndexSearch) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
// -5, -3, -3, 3, 5, 0
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Long(3);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 5));
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
TEST(NumericStorage, IndexSearchCompareWithNegative) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
// -5, -3, -3, 3, 5, 0
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Long(-3);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2));
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 3, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
}
@@ -274,8 +291,9 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
RangeOrBitVector range_or_bv =
- storage.Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
+ queryable->Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
BitVector bv = std::move(range_or_bv).TakeIfBitVector();
ASSERT_TRUE(range_or_bv.IsBitVector());
ASSERT_EQ(bv.CountSetBits(), 28u);
@@ -286,8 +304,9 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
+ auto queryable = storage.MakeQueryable();
Range range =
- storage.Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128))
+ queryable->Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128))
.TakeIfRange();
ASSERT_EQ(range.size(), 28u);
ASSERT_EQ(range.start, 100u);
@@ -298,8 +317,9 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
+ auto queryable = storage.MakeQueryable();
BitVector bv =
- storage.Search(FilterOp::kNe, SqlValue::Long(100), Range(0, 128))
+ queryable->Search(FilterOp::kNe, SqlValue::Long(100), Range(0, 128))
.TakeIfBitVector();
ASSERT_EQ(bv.CountSetBits(), 127u);
}
@@ -308,8 +328,9 @@
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
+ auto queryable = storage.MakeQueryable();
Range range =
- storage.Search(FilterOp::kGe, SqlValue::Long(100), Range(102, 104))
+ queryable->Search(FilterOp::kGe, SqlValue::Long(100), Range(102, 104))
.TakeIfRange();
ASSERT_EQ(range.size(), 2u);
ASSERT_EQ(range.start, 102u);
@@ -323,33 +344,34 @@
Indices::State::kNonmonotonic};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+ auto queryable = storage.MakeQueryable();
- Range range = storage.OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(60),
- sorted_order);
+ Range range = queryable->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(60),
+ sorted_order);
ASSERT_EQ(range.size(), 1u);
ASSERT_EQ(range.start, 6u);
ASSERT_EQ(range.end, 7u);
- range = storage.OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(60),
- sorted_order);
+ range = queryable->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(60),
+ sorted_order);
ASSERT_EQ(range.size(), 3u);
ASSERT_EQ(range.start, 7u);
ASSERT_EQ(range.end, 10u);
- range = storage.OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(60),
- sorted_order);
+ range = queryable->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(60),
+ sorted_order);
ASSERT_EQ(range.size(), 4u);
ASSERT_EQ(range.start, 6u);
ASSERT_EQ(range.end, 10u);
- range = storage.OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(60),
- sorted_order);
+ range = queryable->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(60),
+ sorted_order);
ASSERT_EQ(range.size(), 6u);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 6u);
- range = storage.OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(60),
- sorted_order);
+ range = queryable->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(60),
+ sorted_order);
ASSERT_EQ(range.size(), 7u);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 7u);
@@ -358,211 +380,219 @@
TEST(NumericStorage, SearchWithIntAsDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Double(4);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3, 4));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
}
TEST(NumericStorage, IndexSearchWithIntAsDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
// -5, -3, -3, 3, 5, 0
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Double(3);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 5));
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
TEST(NumericStorage, SearchInt32WithDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Double(3.5);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
}
TEST(NumericStorage, SearchInt32WithNegDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Double(-3.5);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
}
TEST(NumericStorage, IndexSearchInt32WithDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
// -5, -3, -3, 3, 5, 0
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Double(1.5);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
TEST(NumericStorage, IndexSearchInt32WithNegDouble) {
std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
// -5, -3, -3, 3, 5, 0
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Double(-2.5);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
}
TEST(NumericStorage, SearchUint32WithNegDouble) {
std::vector<uint32_t> data_vec{0, 1, 2, 3, 4, 5};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
Range test_range(1, 5);
SqlValue val = SqlValue::Double(-3.5);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
}
TEST(NumericStorage, IndexSearchUint32WithNegDouble) {
std::vector<uint32_t> data_vec{0, 1, 2, 3, 4, 5, 6};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kInt32);
+ auto queryable = storage.MakeQueryable();
std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
SqlValue val = SqlValue::Double(-2.5);
- auto res = storage.IndexSearch(FilterOp::kEq, val, indices);
+ auto res = queryable->IndexSearch(FilterOp::kEq, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.IndexSearch(FilterOp::kNe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kNe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
- res = storage.IndexSearch(FilterOp::kLt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.IndexSearch(FilterOp::kLe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kLe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.IndexSearch(FilterOp::kGt, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGt, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
- res = storage.IndexSearch(FilterOp::kGe, val, indices);
+ res = queryable->IndexSearch(FilterOp::kGe, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
}
@@ -580,24 +610,25 @@
ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[1]) < 0);
NumericStorage<double> storage(&data_vec, ColumnType::kDouble);
+ auto queryable = storage.MakeQueryable();
Range test_range(0, 2);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
}
@@ -615,24 +646,25 @@
ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[1]) > 0);
NumericStorage<double> storage(&data_vec, ColumnType::kDouble);
+ auto queryable = storage.MakeQueryable();
Range test_range(0, 2);
- auto res = storage.Search(FilterOp::kEq, val, test_range);
+ auto res = queryable->Search(FilterOp::kEq, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
- res = storage.Search(FilterOp::kNe, val, test_range);
+ res = queryable->Search(FilterOp::kNe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
- res = storage.Search(FilterOp::kLt, val, test_range);
+ res = queryable->Search(FilterOp::kLt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
- res = storage.Search(FilterOp::kLe, val, test_range);
+ res = queryable->Search(FilterOp::kLe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
- res = storage.Search(FilterOp::kGt, val, test_range);
+ res = queryable->Search(FilterOp::kGt, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
- res = storage.Search(FilterOp::kGe, val, test_range);
+ res = queryable->Search(FilterOp::kGe, val, test_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
}
diff --git a/src/trace_processor/db/column/selector_overlay.cc b/src/trace_processor/db/column/selector_overlay.cc
index 011f418..68a09d6 100644
--- a/src/trace_processor/db/column/selector_overlay.cc
+++ b/src/trace_processor/db/column/selector_overlay.cc
@@ -25,7 +25,7 @@
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/tp_metatrace.h"
@@ -34,20 +34,30 @@
namespace perfetto::trace_processor::column {
-SelectorOverlay::SelectorOverlay(std::unique_ptr<Column> inner,
- const BitVector* selector)
+SelectorOverlay::SelectorOverlay(const BitVector* selector)
+ : selector_(selector) {}
+
+std::unique_ptr<DataNode::Queryable> SelectorOverlay::MakeQueryable(
+ std::unique_ptr<DataNode::Queryable> inner) {
+ return std::make_unique<Queryable>(std::move(inner), selector_);
+}
+
+SelectorOverlay::Queryable::Queryable(
+ std::unique_ptr<DataNode::Queryable> inner,
+ const BitVector* selector)
: inner_(std::move(inner)), selector_(selector) {}
-SearchValidationResult SelectorOverlay::ValidateSearchConstraints(
+SearchValidationResult SelectorOverlay::Queryable::ValidateSearchConstraints(
SqlValue sql_val,
FilterOp op) const {
return inner_->ValidateSearchConstraints(sql_val, op);
}
-RangeOrBitVector SelectorOverlay::Search(FilterOp op,
- SqlValue sql_val,
- Range in) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "SelectorOverlay::Search");
+RangeOrBitVector SelectorOverlay::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range in) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "SelectorOverlay::Queryable::Search");
// Figure out the bounds of the indices in the underlying storage and search
// it.
@@ -75,16 +85,18 @@
return RangeOrBitVector(std::move(res).Build());
}
-RangeOrBitVector SelectorOverlay::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+RangeOrBitVector SelectorOverlay::Queryable::IndexSearch(
+ FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
PERFETTO_DCHECK(
indices.size == 0 ||
*std::max_element(indices.data, indices.data + indices.size) <=
selector_->size());
// TODO(b/307482437): Use OrderedIndexSearch if arrangement orders storage.
- PERFETTO_TP_TRACE(metatrace::Category::DB, "SelectorOverlay::IndexSearch");
+ PERFETTO_TP_TRACE(metatrace::Category::DB,
+ "SelectorOverlay::Queryable::IndexSearch");
// To go from TableIndexVector to StorageIndexVector we need to find index in
// |selector_| by looking only into set bits.
@@ -98,9 +110,9 @@
indices.state});
}
-Range SelectorOverlay::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range SelectorOverlay::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
// To go from TableIndexVector to StorageIndexVector we need to find index in
// |selector_| by looking only into set bits.
std::vector<uint32_t> inner_indices(indices.size);
@@ -113,17 +125,17 @@
indices.state});
}
-void SelectorOverlay::StableSort(uint32_t*, uint32_t) const {
+void SelectorOverlay::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void SelectorOverlay::Sort(uint32_t*, uint32_t) const {
+void SelectorOverlay::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_FATAL("Not implemented");
}
-void SelectorOverlay::Serialize(StorageProto* storage) const {
+void SelectorOverlay::Queryable::Serialize(StorageProto* storage) const {
auto* selector_overlay = storage->set_selector_overlay();
inner_->Serialize(selector_overlay->set_storage());
selector_->Serialize(selector_overlay->set_bit_vector());
diff --git a/src/trace_processor/db/column/selector_overlay.h b/src/trace_processor/db/column/selector_overlay.h
index 33666e5..f901ba8 100644
--- a/src/trace_processor/db/column/selector_overlay.h
+++ b/src/trace_processor/db/column/selector_overlay.h
@@ -23,7 +23,7 @@
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
@@ -31,31 +31,41 @@
// Storage which "selects" specific rows from an underlying storage using a
// BitVector. See ArrangementOverlay for a more generic class which allows
// duplication and rearragement but is less performant.
-class SelectorOverlay : public Column {
+class SelectorOverlay : public DataNode {
public:
- SelectorOverlay(std::unique_ptr<Column>, const BitVector*);
+ explicit SelectorOverlay(const BitVector*);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp p, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override { return selector_->size(); }
-
- std::string DebugString() const override { return "SelectorOverlay"; }
+ std::unique_ptr<Queryable> MakeQueryable(std::unique_ptr<Queryable>) override;
private:
- std::unique_ptr<Column> inner_ = nullptr;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(std::unique_ptr<DataNode::Queryable>, const BitVector*);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp p, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return selector_->size(); }
+
+ std::string DebugString() const override { return "SelectorOverlay"; }
+
+ private:
+ std::unique_ptr<DataNode::Queryable> inner_ = nullptr;
+ const BitVector* selector_ = nullptr;
+ };
+
const BitVector* selector_ = nullptr;
};
diff --git a/src/trace_processor/db/column/selector_overlay_unittest.cc b/src/trace_processor/db/column/selector_overlay_unittest.cc
index 9d44010..a093f68 100644
--- a/src/trace_processor/db/column/selector_overlay_unittest.cc
+++ b/src/trace_processor/db/column/selector_overlay_unittest.cc
@@ -16,13 +16,17 @@
#include "src/trace_processor/db/column/selector_overlay.h"
+#include <cstdint>
+#include <vector>
+
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/db/column/fake_storage.h"
+#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
namespace {
using testing::ElementsAre;
@@ -30,47 +34,52 @@
TEST(SelectorOverlay, SearchAll) {
BitVector selector{0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1};
- SelectorOverlay storage(FakeStorage::SearchAll(10), &selector);
+ auto fake = FakeStorage::SearchAll(10);
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 4));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 4));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1u, 2u, 3u));
}
TEST(SelectorOverlay, SearchNone) {
BitVector selector{0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1};
- SelectorOverlay storage(FakeStorage::SearchNone(10), &selector);
+ auto fake = FakeStorage::SearchNone(10);
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 4));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 4));
ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
}
TEST(SelectorOverlay, SearchLimited) {
BitVector selector{0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1};
- SelectorOverlay storage(FakeStorage::SearchSubset(10, Range(4, 5)),
- &selector);
+ auto fake = FakeStorage::SearchSubset(10, Range(4, 5));
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 5));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(1, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2u));
}
TEST(SelectorOverlay, SearchBitVector) {
BitVector selector{0, 1, 1, 0, 0, 1, 1, 0};
- SelectorOverlay storage(
- FakeStorage::SearchSubset(8, BitVector({0, 1, 0, 1, 0, 1, 0, 0})),
- &selector);
+ auto fake = FakeStorage::SearchSubset(8, BitVector({0, 1, 0, 1, 0, 1, 0, 0}));
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
- auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 4));
+ auto res = queryable->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 4));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2));
}
TEST(SelectorOverlay, IndexSearch) {
BitVector selector{0, 1, 1, 0, 0, 1, 1, 0};
- SelectorOverlay storage(
- FakeStorage::SearchSubset(8, BitVector({0, 1, 0, 1, 0, 1, 0, 0})),
- &selector);
+ auto fake = FakeStorage::SearchSubset(8, BitVector({0, 1, 0, 1, 0, 1, 0, 0}));
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{1u, 0u, 3u};
- RangeOrBitVector res = storage.IndexSearch(
+ RangeOrBitVector res = queryable->IndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
Indices::State::kNonmonotonic});
@@ -79,10 +88,12 @@
TEST(SelectorOverlay, OrderedIndexSearchTrivial) {
BitVector selector{1, 0, 1, 0, 1};
- SelectorOverlay storage(FakeStorage::SearchAll(5), &selector);
+ auto fake = FakeStorage::SearchAll(5);
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{1u, 0u, 2u};
- Range res = storage.OrderedIndexSearch(
+ Range res = queryable->OrderedIndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
Indices::State::kNonmonotonic});
@@ -92,10 +103,12 @@
TEST(SelectorOverlay, OrderedIndexSearchNone) {
BitVector selector{1, 0, 1, 0, 1};
- SelectorOverlay storage(FakeStorage::SearchNone(5), &selector);
+ auto fake = FakeStorage::SearchNone(5);
+ SelectorOverlay storage(&selector);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
std::vector<uint32_t> table_idx{1u, 0u, 2u};
- Range res = storage.OrderedIndexSearch(
+ Range res = queryable->OrderedIndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
Indices::State::kNonmonotonic});
@@ -103,6 +116,4 @@
}
} // namespace
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/set_id_storage.cc b/src/trace_processor/db/column/set_id_storage.cc
index 20a9f38..75019cc 100644
--- a/src/trace_processor/db/column/set_id_storage.cc
+++ b/src/trace_processor/db/column/set_id_storage.cc
@@ -16,19 +16,29 @@
#include "src/trace_processor/db/column/set_id_storage.h"
+#include <algorithm>
+#include <cstdint>
#include <functional>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <string>
+#include <utility>
+#include <vector>
#include "perfetto/base/logging.h"
-#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+#include "perfetto/public/compiler.h"
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "src/trace_processor/tp_metatrace.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+#include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+
+namespace perfetto::trace_processor::column {
namespace {
@@ -38,7 +48,7 @@
if (id >= range.end) {
return range.end;
}
- auto upper =
+ const auto* upper =
std::upper_bound(data + std::max(range.start, id), data + range.end, id);
return static_cast<uint32_t>(std::distance(data, upper));
}
@@ -57,7 +67,17 @@
} // namespace
-SearchValidationResult SetIdStorage::ValidateSearchConstraints(
+SetIdStorage::SetIdStorage(const std::vector<uint32_t>* values)
+ : values_(values) {}
+
+std::unique_ptr<DataNode::Queryable> SetIdStorage::MakeQueryable() {
+ return std::make_unique<Queryable>(values_);
+}
+
+SetIdStorage::Queryable::Queryable(const std::vector<uint32_t>* values)
+ : values_(values) {}
+
+SearchValidationResult SetIdStorage::Queryable::ValidateSearchConstraints(
SqlValue val,
FilterOp op) const {
// NULL checks.
@@ -108,10 +128,9 @@
}
// Bounds of the value.
- double_t num_val = val.type == SqlValue::kLong
- ? static_cast<double_t>(val.AsLong())
- : val.AsDouble();
-
+ double num_val = val.type == SqlValue::kLong
+ ? static_cast<double>(val.AsLong())
+ : val.AsDouble();
if (PERFETTO_UNLIKELY(num_val > std::numeric_limits<uint32_t>::max())) {
if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
return SearchValidationResult::kAllData;
@@ -128,12 +147,12 @@
return SearchValidationResult::kOk;
}
-RangeOrBitVector SetIdStorage::Search(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
+RangeOrBitVector SetIdStorage::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range search_range) const {
PERFETTO_DCHECK(search_range.end <= size());
- PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::Search",
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::Queryable::Search",
[&search_range, op](metatrace::Record* r) {
r->AddArg("Start", std::to_string(search_range.start));
r->AddArg("End", std::to_string(search_range.end));
@@ -154,8 +173,7 @@
}
}
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
if (op == FilterOp::kNe) {
// Not equal is a special operation on binary search, as it doesn't define a
// range, and rather just `not` range returned with `equal` operation.
@@ -169,15 +187,15 @@
return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
-RangeOrBitVector SetIdStorage::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+RangeOrBitVector SetIdStorage::Queryable::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "SetIdStorage::Queryable::IndexSearch",
+ [indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.size));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
// It's a valid filter operation if |sql_val| is a double, although it
// requires special logic.
@@ -192,8 +210,7 @@
}
}
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
BitVector::Builder builder(indices.size);
// TODO(mayzner): Instead of utils::IndexSearchWithComparator, use the
@@ -201,27 +218,27 @@
switch (op) {
case FilterOp::kEq:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::equal_to<uint32_t>(), builder);
+ std::equal_to<>(), builder);
break;
case FilterOp::kNe:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::not_equal_to<uint32_t>(), builder);
+ std::not_equal_to<>(), builder);
break;
case FilterOp::kLe:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::less_equal<uint32_t>(), builder);
+ std::less_equal<>(), builder);
break;
case FilterOp::kLt:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::less<uint32_t>(), builder);
+ std::less<>(), builder);
break;
case FilterOp::kGt:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::greater<uint32_t>(), builder);
+ std::greater<>(), builder);
break;
case FilterOp::kGe:
utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::greater_equal<uint32_t>(), builder);
+ std::greater_equal<>(), builder);
break;
case FilterOp::kIsNotNull:
return RangeOrBitVector(Range(0, indices.size));
@@ -234,42 +251,40 @@
return RangeOrBitVector(std::move(builder).Build());
}
-Range SetIdStorage::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range SetIdStorage::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
// Indices are monotonic non-contiguous values.
- auto res = SetIdStorage::Search(
+ auto res = SetIdStorage::Queryable::Search(
op, sql_val, Range(indices.data[0], indices.data[indices.size - 1] + 1));
PERFETTO_CHECK(res.IsRange());
Range res_range = std::move(res).TakeIfRange();
- auto start_ptr = std::lower_bound(indices.data, indices.data + indices.size,
- res_range.start);
- auto end_ptr =
+ const auto* start_ptr = std::lower_bound(
+ indices.data, indices.data + indices.size, res_range.start);
+ const auto* end_ptr =
std::lower_bound(start_ptr, indices.data + indices.size, res_range.end);
- return Range(static_cast<uint32_t>(std::distance(indices.data, start_ptr)),
- static_cast<uint32_t>(std::distance(indices.data, end_ptr)));
+ return {static_cast<uint32_t>(std::distance(indices.data, start_ptr)),
+ static_cast<uint32_t>(std::distance(indices.data, end_ptr))};
}
-Range SetIdStorage::BinarySearchIntrinsic(FilterOp op,
- SetId val,
- Range range) const {
+Range SetIdStorage::Queryable::BinarySearchIntrinsic(FilterOp op,
+ SetId val,
+ Range range) const {
switch (op) {
case FilterOp::kEq:
- return Range(LowerBoundIntrinsic(values_->data(), val, range),
- UpperBoundIntrinsic(values_->data(), val, range));
+ return {LowerBoundIntrinsic(values_->data(), val, range),
+ UpperBoundIntrinsic(values_->data(), val, range)};
case FilterOp::kLe: {
- return Range(range.start,
- UpperBoundIntrinsic(values_->data(), val, range));
+ return {range.start, UpperBoundIntrinsic(values_->data(), val, range)};
}
case FilterOp::kLt:
- return Range(range.start,
- LowerBoundIntrinsic(values_->data(), val, range));
+ return {range.start, LowerBoundIntrinsic(values_->data(), val, range)};
case FilterOp::kGe:
- return Range(LowerBoundIntrinsic(values_->data(), val, range), range.end);
+ return {LowerBoundIntrinsic(values_->data(), val, range), range.end};
case FilterOp::kGt:
- return Range(UpperBoundIntrinsic(values_->data(), val, range), range.end);
+ return {UpperBoundIntrinsic(values_->data(), val, range), range.end};
case FilterOp::kIsNotNull:
return range;
case FilterOp::kNe:
@@ -277,27 +292,25 @@
case FilterOp::kIsNull:
case FilterOp::kGlob:
case FilterOp::kRegex:
- return Range();
+ return {};
}
- return Range();
+ return {};
}
-void SetIdStorage::StableSort(uint32_t*, uint32_t) const {
+void SetIdStorage::Queryable::StableSort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_ELOG("Not implemented");
}
-void SetIdStorage::Sort(uint32_t*, uint32_t) const {
+void SetIdStorage::Queryable::Sort(uint32_t*, uint32_t) const {
// TODO(b/307482437): Implement.
PERFETTO_ELOG("Not implemented");
}
-void SetIdStorage::Serialize(StorageProto* msg) const {
+void SetIdStorage::Queryable::Serialize(StorageProto* msg) const {
auto* vec_msg = msg->set_set_id_storage();
vec_msg->set_values(reinterpret_cast<const uint8_t*>(values_->data()),
sizeof(SetId) * size());
}
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/set_id_storage.h b/src/trace_processor/db/column/set_id_storage.h
index 46e71a5..f7cab36 100644
--- a/src/trace_processor/db/column/set_id_storage.h
+++ b/src/trace_processor/db/column/set_id_storage.h
@@ -17,50 +17,59 @@
#define SRC_TRACE_PROCESSOR_DB_COLUMN_SET_ID_STORAGE_H_
#include <cstdint>
+#include <memory>
#include <string>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Storage for SetId columns.
-class SetIdStorage final : public Column {
+class SetIdStorage final : public DataNode {
public:
using SetId = uint32_t;
- explicit SetIdStorage(const std::vector<uint32_t>* data) : values_(data) {}
+ explicit SetIdStorage(const std::vector<uint32_t>*);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override {
- return static_cast<uint32_t>(values_->size());
- }
-
- std::string DebugString() const override { return "SetIdStorage"; }
+ std::unique_ptr<Queryable> MakeQueryable() override;
private:
- BitVector IndexSearch(FilterOp, SetId, uint32_t*, uint32_t) const;
- Range BinarySearchIntrinsic(FilterOp, SetId, Range search_range) const;
+ class Queryable : public DataNode::Queryable {
+ public:
+ explicit Queryable(const std::vector<uint32_t>*);
- // TODO(b/307482437): After the migration vectors should be owned by storage,
- // so change from pointer to value.
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t*, uint32_t) const override;
+
+ void Sort(uint32_t*, uint32_t) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override {
+ return static_cast<uint32_t>(values_->size());
+ }
+
+ std::string DebugString() const override { return "SetIdStorage"; }
+
+ private:
+ BitVector IndexSearch(FilterOp, SetId, uint32_t*, uint32_t) const;
+ Range BinarySearchIntrinsic(FilterOp, SetId, Range search_range) const;
+
+ const std::vector<SetId>* values_ = nullptr;
+ };
+
const std::vector<SetId>* values_ = nullptr;
};
diff --git a/src/trace_processor/db/column/set_id_storage_unittest.cc b/src/trace_processor/db/column/set_id_storage_unittest.cc
index 38b2878..a6ef367 100644
--- a/src/trace_processor/db/column/set_id_storage_unittest.cc
+++ b/src/trace_processor/db/column/set_id_storage_unittest.cc
@@ -15,13 +15,18 @@
*/
#include "src/trace_processor/db/column/set_id_storage.h"
+#include <cstdint>
+#include <limits>
+#include <tuple>
+#include <vector>
+
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
+namespace perfetto::trace_processor {
inline bool operator==(const Range& a, const Range& b) {
return std::tie(a.start, a.end) == std::tie(b.start, b.end);
@@ -40,149 +45,159 @@
TEST(SetIdStorage, InvalidSearchConstraints) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
+
// NULL checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNull),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
- SearchValidationResult::kAllData);
+ ASSERT_EQ(
+ queryable->ValidateSearchConstraints(SqlValue(), FilterOp::kIsNotNull),
+ SearchValidationResult::kAllData);
// FilterOp checks
ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
+ queryable->ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kGlob),
SearchValidationResult::kNoData);
- ASSERT_EQ(
- storage.ValidateSearchConstraints(SqlValue::Long(15), FilterOp::kRegex),
- SearchValidationResult::kNoData);
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::Long(15),
+ FilterOp::kRegex),
+ SearchValidationResult::kNoData);
// Type checks
- ASSERT_EQ(storage.ValidateSearchConstraints(SqlValue::String("cheese"),
- FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(SqlValue::String("cheese"),
+ FilterOp::kGe),
SearchValidationResult::kNoData);
// Value bounds
SqlValue max_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kGt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kEq),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kLt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(max_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(max_val, FilterOp::kNe),
SearchValidationResult::kAllData);
SqlValue min_val = SqlValue::Long(
static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kGt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kGt),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kNe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kNe),
SearchValidationResult::kAllData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLe),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLe),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kLt),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kLt),
SearchValidationResult::kNoData);
- ASSERT_EQ(storage.ValidateSearchConstraints(min_val, FilterOp::kEq),
+ ASSERT_EQ(queryable->ValidateSearchConstraints(min_val, FilterOp::kEq),
SearchValidationResult::kNoData);
}
TEST(SetIdStorage, SearchSimple) {
std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
SqlValue val = SqlValue::Long(4);
Range filter_range(1, 7);
FilterOp op = FilterOp::kEq;
- auto res = storage.Search(op, val, filter_range);
+ auto res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4, 5));
op = FilterOp::kNe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 6));
op = FilterOp::kLe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
op = FilterOp::kLt;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
op = FilterOp::kGe;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4, 5, 6));
op = FilterOp::kGt;
- res = storage.Search(op, val, filter_range);
+ res = queryable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(6));
}
TEST(SetIdStorage, IndexSearchSimple) {
std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
SqlValue val = SqlValue::Long(4);
// 6, 4, 2, 0
std::vector<uint32_t> indices_vec{6, 4, 2, 0};
Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
- auto res = storage.IndexSearch(op, val, indices);
+ auto res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
op = FilterOp::kNe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2, 3));
op = FilterOp::kLe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
op = FilterOp::kLt;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3));
op = FilterOp::kGe;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
op = FilterOp::kGt;
- res = storage.IndexSearch(op, val, indices);
+ res = queryable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
}
TEST(SetIdStorage, OrderedIndexSearchSimple) {
std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
// 0, 2, 2, 4
std::vector<uint32_t> indices_vec{0, 3, 3, 5};
Indices indices{indices_vec.data(), 4, Indices::State::kMonotonic};
Range range =
- storage.OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
+ queryable->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 1u);
ASSERT_EQ(range.end, 3u);
- range = storage.OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 3u);
ASSERT_EQ(range.end, 4u);
- range = storage.OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 1u);
ASSERT_EQ(range.end, 4u);
- range = storage.OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 1u);
- range = storage.OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
+ range =
+ queryable->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(2), indices);
ASSERT_EQ(range.start, 0u);
ASSERT_EQ(range.end, 3u);
}
@@ -191,8 +206,10 @@
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(3), Range(4, 10))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(3), Range(4, 10))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 2u);
ASSERT_EQ(range.start, 4u);
@@ -203,7 +220,8 @@
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(9), Range(6, 9))
+ auto queryable = storage.MakeQueryable();
+ Range range = queryable->Search(FilterOp::kEq, SqlValue::Long(9), Range(6, 9))
.TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
@@ -212,8 +230,10 @@
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(12), Range(6, 9))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(12), Range(6, 9))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
@@ -221,21 +241,25 @@
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
- Range range = storage.Search(FilterOp::kEq, SqlValue::Long(100), Range(6, 9))
- .TakeIfRange();
+ auto queryable = storage.MakeQueryable();
+ Range range =
+ queryable->Search(FilterOp::kEq, SqlValue::Long(100), Range(6, 9))
+ .TakeIfRange();
ASSERT_EQ(range.size(), 0u);
}
TEST(SetIdStorage, IndexSearchEqTooBig) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
// {0, 3, 3, 6, 9, 9, 0, 3}
std::vector<uint32_t> indices_vec{1, 3, 5, 7, 9, 11, 2, 4};
Indices indices{indices_vec.data(), 8, Indices::State::kMonotonic};
- BitVector bv = storage.IndexSearch(FilterOp::kEq, SqlValue::Long(10), indices)
- .TakeIfBitVector();
+ BitVector bv =
+ queryable->IndexSearch(FilterOp::kEq, SqlValue::Long(10), indices)
+ .TakeIfBitVector();
ASSERT_EQ(bv.CountSetBits(), 0u);
}
@@ -243,43 +267,44 @@
TEST(SetIdStorage, SearchWithIdAsSimpleDoubleIsInt) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
SqlValue double_val = SqlValue::Double(7.0);
SqlValue long_val = SqlValue::Long(7);
Range range(1, 9);
FilterOp op = FilterOp::kEq;
- auto double_res = storage.Search(op, double_val, range);
- auto int_res = storage.Search(op, long_val, range);
+ auto double_res = queryable->Search(op, double_val, range);
+ auto int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
op = FilterOp::kNe;
- double_res = storage.Search(op, double_val, range);
- int_res = storage.Search(op, long_val, range);
+ double_res = queryable->Search(op, double_val, range);
+ int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
op = FilterOp::kLe;
- double_res = storage.Search(op, double_val, range);
- int_res = storage.Search(op, long_val, range);
+ double_res = queryable->Search(op, double_val, range);
+ int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
op = FilterOp::kLt;
- double_res = storage.Search(op, double_val, range);
- int_res = storage.Search(op, long_val, range);
+ double_res = queryable->Search(op, double_val, range);
+ int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
op = FilterOp::kGe;
- double_res = storage.Search(op, double_val, range);
- int_res = storage.Search(op, long_val, range);
+ double_res = queryable->Search(op, double_val, range);
+ int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
op = FilterOp::kGt;
- double_res = storage.Search(op, double_val, range);
- int_res = storage.Search(op, long_val, range);
+ double_res = queryable->Search(op, double_val, range);
+ int_res = queryable->Search(op, long_val, range);
ASSERT_EQ(utils::ToIndexVectorForTests(double_res),
utils::ToIndexVectorForTests(int_res));
}
@@ -287,29 +312,29 @@
TEST(SetIdStorage, SearchWithIdAsDouble) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
SqlValue val = SqlValue::Double(7.5);
Range range(5, 10);
- Range res = storage.Search(FilterOp::kEq, val, range).TakeIfRange();
+ Range res = queryable->Search(FilterOp::kEq, val, range).TakeIfRange();
ASSERT_EQ(res, Range());
- res = storage.Search(FilterOp::kNe, val, range).TakeIfRange();
+ res = queryable->Search(FilterOp::kNe, val, range).TakeIfRange();
ASSERT_EQ(res, Range(0, 10));
- res = storage.Search(FilterOp::kLe, val, range).TakeIfRange();
+ res = queryable->Search(FilterOp::kLe, val, range).TakeIfRange();
ASSERT_EQ(res, Range(5, 9));
- res = storage.Search(FilterOp::kLt, val, range).TakeIfRange();
+ res = queryable->Search(FilterOp::kLt, val, range).TakeIfRange();
ASSERT_EQ(res, Range(5, 9));
- res = storage.Search(FilterOp::kGe, val, range).TakeIfRange();
+ res = queryable->Search(FilterOp::kGe, val, range).TakeIfRange();
ASSERT_EQ(res, Range(9, 10));
- res = storage.Search(FilterOp::kGt, val, range).TakeIfRange();
+ res = queryable->Search(FilterOp::kGt, val, range).TakeIfRange();
ASSERT_EQ(res, Range(9, 10));
}
} // namespace
} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/db/column/string_storage.cc b/src/trace_processor/db/column/string_storage.cc
index b495892..53f061f 100644
--- a/src/trace_processor/db/column/string_storage.cc
+++ b/src/trace_processor/db/column/string_storage.cc
@@ -20,6 +20,7 @@
#include <cstdint>
#include <functional>
#include <iterator>
+#include <memory>
#include <string>
#include <utility>
#include <vector>
@@ -31,7 +32,7 @@
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/null_term_string_view.h"
#include "src/trace_processor/containers/string_pool.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "src/trace_processor/tp_metatrace.h"
@@ -195,7 +196,21 @@
} // namespace
-SearchValidationResult StringStorage::ValidateSearchConstraints(
+StringStorage::StringStorage(StringPool* string_pool,
+ const std::vector<StringPool::Id>* data,
+ bool is_sorted)
+ : data_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
+
+std::unique_ptr<DataNode::Queryable> StringStorage::MakeQueryable() {
+ return std::make_unique<Queryable>(string_pool_, data_, is_sorted_);
+}
+
+StringStorage::Queryable::Queryable(StringPool* string_pool,
+ const std::vector<StringPool::Id>* data,
+ bool is_sorted)
+ : data_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
+
+SearchValidationResult StringStorage::Queryable::ValidateSearchConstraints(
SqlValue val,
FilterOp op) const {
// Type checks.
@@ -217,10 +232,10 @@
return SearchValidationResult::kOk;
}
-RangeOrBitVector StringStorage::Search(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::Search",
+RangeOrBitVector StringStorage::Queryable::Search(FilterOp op,
+ SqlValue sql_val,
+ Range search_range) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::Queryable::Search",
[&search_range, op](metatrace::Record* r) {
r->AddArg("Start", std::to_string(search_range.start));
r->AddArg("End", std::to_string(search_range.end));
@@ -259,23 +274,23 @@
return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
}
-RangeOrBitVector StringStorage::IndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+RangeOrBitVector StringStorage::Queryable::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
PERFETTO_DCHECK(indices.size <= size());
- PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
- r->AddArg("Op",
- std::to_string(static_cast<uint32_t>(op)));
- });
+ PERFETTO_TP_TRACE(
+ metatrace::Category::DB, "StringStorage::Queryable::IndexSearch",
+ [indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.size));
+ r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
+ });
return RangeOrBitVector(
IndexSearchInternal(op, sql_val, indices.data, indices.size));
}
-BitVector StringStorage::LinearSearch(FilterOp op,
- SqlValue sql_val,
- Range range) const {
+BitVector StringStorage::Queryable::LinearSearch(FilterOp op,
+ SqlValue sql_val,
+ Range range) const {
StringPool::Id val =
(op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
? StringPool::Id::Null()
@@ -286,8 +301,7 @@
BitVector::Builder builder(range.end, range.start);
switch (op) {
case FilterOp::kEq:
- utils::LinearSearchWithComparator(
- val, start, std::equal_to<StringPool::Id>(), builder);
+ utils::LinearSearchWithComparator(val, start, std::equal_to<>(), builder);
break;
case FilterOp::kNe:
utils::LinearSearchWithComparator(val, start, NotEqual(), builder);
@@ -363,9 +377,9 @@
return std::move(builder).Build();
}
-Range StringStorage::OrderedIndexSearch(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range StringStorage::Queryable::OrderedIndexSearch(FilterOp op,
+ SqlValue sql_val,
+ Indices indices) const {
StringPool::Id val =
(op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
? StringPool::Id::Null()
@@ -422,7 +436,7 @@
PERFETTO_FATAL("For GCC");
}
-RangeOrBitVector StringStorage::IndexSearchInternal(
+RangeOrBitVector StringStorage::Queryable::IndexSearchInternal(
FilterOp op,
SqlValue sql_val,
const uint32_t* indices,
@@ -437,8 +451,8 @@
switch (op) {
case FilterOp::kEq:
- utils::IndexSearchWithComparator(
- val, start, indices, std::equal_to<StringPool::Id>(), builder);
+ utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>(),
+ builder);
break;
case FilterOp::kNe:
utils::IndexSearchWithComparator(val, start, indices, NotEqual(),
@@ -464,8 +478,8 @@
util::GlobMatcher matcher =
util::GlobMatcher::FromPattern(sql_val.AsString());
if (matcher.IsEquality()) {
- utils::IndexSearchWithComparator(
- val, start, indices, std::equal_to<StringPool::Id>(), builder);
+ utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>(),
+ builder);
break;
}
utils::IndexSearchWithComparator(std::move(matcher), start, indices,
@@ -491,9 +505,10 @@
return RangeOrBitVector(std::move(builder).Build());
}
-Range StringStorage::BinarySearchIntrinsic(FilterOp op,
- SqlValue sql_val,
- Range search_range) const {
+Range StringStorage::Queryable::BinarySearchIntrinsic(
+ FilterOp op,
+ SqlValue sql_val,
+ Range search_range) const {
StringPool::Id val =
(op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
? StringPool::Id::Null()
@@ -502,27 +517,26 @@
switch (op) {
case FilterOp::kEq:
- return Range(LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range),
- UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range));
+ return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range),
+ UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range)};
case FilterOp::kLe:
- return Range(search_range.start,
- UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range));
+ return {search_range.start,
+ UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range)};
case FilterOp::kLt:
- return Range(search_range.start,
- LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range));
+ return {search_range.start,
+ LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range)};
case FilterOp::kGe:
- return Range(LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range),
- search_range.end);
+ return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range),
+ search_range.end};
case FilterOp::kGt:
- return Range(UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
- search_range),
- search_range.end);
-
+ return {UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
+ search_range),
+ search_range.end};
case FilterOp::kNe:
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
@@ -533,7 +547,8 @@
PERFETTO_FATAL("For gcc");
}
-void StringStorage::StableSort(uint32_t* indices, uint32_t indices_size) const {
+void StringStorage::Queryable::StableSort(uint32_t* indices,
+ uint32_t indices_size) const {
std::stable_sort(indices, indices + indices_size,
[this](uint32_t a_idx, uint32_t b_idx) {
return string_pool_->Get((*data_)[a_idx]) <
@@ -541,7 +556,8 @@
});
}
-void StringStorage::Sort(uint32_t* indices, uint32_t indices_size) const {
+void StringStorage::Queryable::Sort(uint32_t* indices,
+ uint32_t indices_size) const {
std::sort(indices, indices + indices_size,
[this](uint32_t a_idx, uint32_t b_idx) {
return string_pool_->Get((*data_)[a_idx]) <
@@ -549,7 +565,7 @@
});
}
-void StringStorage::Serialize(StorageProto* msg) const {
+void StringStorage::Queryable::Serialize(StorageProto* msg) const {
auto* string_storage_msg = msg->set_string_storage();
string_storage_msg->set_is_sorted(is_sorted_);
diff --git a/src/trace_processor/db/column/string_storage.h b/src/trace_processor/db/column/string_storage.h
index d7bd958..da868ff 100644
--- a/src/trace_processor/db/column/string_storage.h
+++ b/src/trace_processor/db/column/string_storage.h
@@ -17,60 +17,74 @@
#define SRC_TRACE_PROCESSOR_DB_COLUMN_STRING_STORAGE_H_
#include <cstdint>
+#include <memory>
#include <string>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/string_pool.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/types.h"
namespace perfetto::trace_processor::column {
// Storage for String columns.
-class StringStorage final : public Column {
+class StringStorage final : public DataNode {
public:
StringStorage(StringPool* string_pool,
const std::vector<StringPool::Id>* data,
- bool is_sorted = false)
- : data_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
+ bool is_sorted = false);
- SearchValidationResult ValidateSearchConstraints(SqlValue,
- FilterOp) const override;
-
- RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
-
- RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
-
- Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
-
- void StableSort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Sort(uint32_t* rows, uint32_t rows_size) const override;
-
- void Serialize(StorageProto*) const override;
-
- uint32_t size() const override {
- return static_cast<uint32_t>(data_->size());
- }
-
- std::string DebugString() const override { return "StringStorage"; }
+ std::unique_ptr<DataNode::Queryable> MakeQueryable() override;
private:
- BitVector LinearSearch(FilterOp, SqlValue, Range) const;
+ class Queryable : public DataNode::Queryable {
+ public:
+ Queryable(StringPool* string_pool,
+ const std::vector<StringPool::Id>* data,
+ bool is_sorted);
- RangeOrBitVector IndexSearchInternal(FilterOp op,
- SqlValue sql_val,
- const uint32_t* indices,
- uint32_t indices_size) const;
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
- Range BinarySearchIntrinsic(FilterOp op,
- SqlValue val,
- Range search_range) const;
+ RangeOrBitVector Search(FilterOp, SqlValue, Range) const override;
- // TODO(b/307482437): After the migration vectors should be owned by storage,
- // so change from pointer to value.
+ RangeOrBitVector IndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ Range OrderedIndexSearch(FilterOp, SqlValue, Indices) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override {
+ return static_cast<uint32_t>(data_->size());
+ }
+
+ std::string DebugString() const override { return "StringStorage"; }
+
+ private:
+ BitVector LinearSearch(FilterOp, SqlValue, Range) const;
+
+ RangeOrBitVector IndexSearchInternal(FilterOp op,
+ SqlValue sql_val,
+ const uint32_t* indices,
+ uint32_t indices_size) const;
+
+ Range BinarySearchIntrinsic(FilterOp op,
+ SqlValue val,
+ Range search_range) const;
+
+ // TODO(b/307482437): After the migration vectors should be owned by
+ // storage, so change from pointer to value.
+ const std::vector<StringPool::Id>* data_ = nullptr;
+ StringPool* string_pool_ = nullptr;
+ const bool is_sorted_ = false;
+ };
+
const std::vector<StringPool::Id>* data_ = nullptr;
StringPool* string_pool_ = nullptr;
const bool is_sorted_ = false;
diff --git a/src/trace_processor/db/column/string_storage_unittest.cc b/src/trace_processor/db/column/string_storage_unittest.cc
index 7fb6464..e4ce5ac 100644
--- a/src/trace_processor/db/column/string_storage_unittest.cc
+++ b/src/trace_processor/db/column/string_storage_unittest.cc
@@ -15,14 +15,20 @@
*/
#include "src/trace_processor/db/column/string_storage.h"
+#include <cstdint>
+#include <string>
+#include <vector>
+
+#include "perfetto/base/build_config.h"
+#include "perfetto/ext/base/string_view.h"
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/string_pool.h"
#include "src/trace_processor/db/column/types.h"
#include "src/trace_processor/db/column/utils.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
-namespace column {
+namespace perfetto::trace_processor::column {
namespace {
using testing::ElementsAre;
@@ -38,43 +44,44 @@
}
ids.insert(ids.begin() + 3, StringPool::Id::Null());
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
SqlValue val = SqlValue::String("pierogi");
Range filter_range(0, 7);
FilterOp op = FilterOp::kEq;
- auto res = storage.Search(op, val, filter_range);
+ auto res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
op = FilterOp::kNe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5, 6));
op = FilterOp::kLt;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 5, 6));
op = FilterOp::kLe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 6));
op = FilterOp::kGt;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
op = FilterOp::kGe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
op = FilterOp::kIsNull;
- res = storage.Search(op, SqlValue(), filter_range);
+ res = queriable->Search(op, SqlValue(), filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
op = FilterOp::kIsNotNull;
- res = storage.Search(op, SqlValue(), filter_range);
+ res = queriable->Search(op, SqlValue(), filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5, 6));
op = FilterOp::kGlob;
- res = storage.Search(op, SqlValue::String("p*"), filter_range);
+ res = queriable->Search(op, SqlValue::String("p*"), filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
}
@@ -88,45 +95,46 @@
}
ids.insert(ids.begin() + 3, StringPool::Id::Null());
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
SqlValue val = SqlValue::String("pierogi");
// "fries", "onion", "pierogi", NULL, "pizza", "pasta", "cheese"
std::vector<uint32_t> indices_vec{6, 5, 4, 3, 2, 1, 0};
Indices indices{indices_vec.data(), 7, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
- auto res = storage.IndexSearch(op, val, indices);
+ auto res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
op = FilterOp::kNe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 6));
op = FilterOp::kLt;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 5, 6));
op = FilterOp::kLe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5, 6));
op = FilterOp::kGt;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
op = FilterOp::kGe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
op = FilterOp::kIsNull;
- res = storage.IndexSearch(op, SqlValue(), indices);
+ res = queriable->IndexSearch(op, SqlValue(), indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
op = FilterOp::kIsNotNull;
- res = storage.IndexSearch(op, SqlValue(), indices);
+ res = queriable->IndexSearch(op, SqlValue(), indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5, 6));
op = FilterOp::kGlob;
- res = storage.IndexSearch(op, SqlValue::String("p*"), indices);
+ res = queriable->IndexSearch(op, SqlValue::String("p*"), indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4, 5));
}
@@ -142,8 +150,10 @@
ids.insert(ids.begin() + 3, StringPool::Id::Null());
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
BitVector bv =
- storage.Search(FilterOp::kRegex, SqlValue::String(".*zz.*"), Range(0, 7))
+ queriable
+ ->Search(FilterOp::kRegex, SqlValue::String(".*zz.*"), Range(0, 7))
.TakeIfBitVector();
ASSERT_EQ(bv.CountSetBits(), 1u);
@@ -160,8 +170,9 @@
ids.insert(ids.begin() + 3, StringPool::Id::Null());
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
BitVector bv =
- storage.Search(FilterOp::kRegex, SqlValue::String("*"), Range(0, 7))
+ queriable->Search(FilterOp::kRegex, SqlValue::String("*"), Range(0, 7))
.TakeIfBitVector();
ASSERT_EQ(bv.CountSetBits(), 0u);
@@ -177,35 +188,36 @@
ids.push_back(pool.InternString(base::StringView(string)));
}
StringStorage storage(&pool, &ids, true);
+ auto queriable = storage.MakeQueryable();
SqlValue val = SqlValue::String("cheese");
Range filter_range(0, 6);
FilterOp op = FilterOp::kEq;
- auto res = storage.Search(op, val, filter_range);
+ auto res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
op = FilterOp::kNe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 3, 4, 5));
op = FilterOp::kLt;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
op = FilterOp::kLe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
op = FilterOp::kGt;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
op = FilterOp::kGe;
- res = storage.Search(op, val, filter_range);
+ res = queriable->Search(op, val, filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3, 4, 5));
op = FilterOp::kGlob;
- res = storage.Search(op, SqlValue::String("*e"), filter_range);
+ res = queriable->Search(op, SqlValue::String("*e"), filter_range);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2));
}
@@ -218,37 +230,38 @@
ids.push_back(pool.InternString(base::StringView(string)));
}
StringStorage storage(&pool, &ids, true);
+ auto queriable = storage.MakeQueryable();
SqlValue val = SqlValue::String("cheese");
// fries, eggplant, cheese, burger
std::vector<uint32_t> indices_vec{5, 4, 2, 1};
Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
- auto res = storage.IndexSearch(op, val, indices);
+ auto res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
op = FilterOp::kNe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 3));
op = FilterOp::kLt;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
op = FilterOp::kLe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3));
op = FilterOp::kGt;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
op = FilterOp::kGe;
- res = storage.IndexSearch(op, val, indices);
+ res = queriable->IndexSearch(op, val, indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
op = FilterOp::kGlob;
- res = storage.IndexSearch(op, SqlValue::String("*e"), indices);
+ res = queriable->IndexSearch(op, SqlValue::String("*e"), indices);
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
}
@@ -261,33 +274,34 @@
ids.push_back(pool.InternString(base::StringView(string)));
}
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
SqlValue val = SqlValue::String("pierogi");
// cheese, fries, onion, pasta, pierogi, pizza
std::vector<uint32_t> indices_vec{0, 5, 4, 1, 3, 2};
Indices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
- Range res = storage.OrderedIndexSearch(op, val, indices);
+ Range res = queriable->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 4u);
ASSERT_EQ(res.end, 5u);
op = FilterOp::kLt;
- res = storage.OrderedIndexSearch(op, val, indices);
+ res = queriable->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 4u);
op = FilterOp::kLe;
- res = storage.OrderedIndexSearch(op, val, indices);
+ res = queriable->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 5u);
op = FilterOp::kGt;
- res = storage.OrderedIndexSearch(op, val, indices);
+ res = queriable->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 5u);
ASSERT_EQ(res.end, 6u);
op = FilterOp::kGe;
- res = storage.OrderedIndexSearch(op, val, indices);
+ res = queriable->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 4u);
ASSERT_EQ(res.end, 6u);
}
@@ -301,10 +315,12 @@
ids.push_back(pool.InternString(base::StringView(string)));
}
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
std::vector<uint32_t> indices_vec{0, 2, 5, 7};
Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
- auto res = storage.OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ auto res =
+ queriable->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 2u);
}
@@ -318,16 +334,15 @@
ids.push_back(pool.InternString(base::StringView(string)));
}
StringStorage storage(&pool, &ids);
+ auto queriable = storage.MakeQueryable();
std::vector<uint32_t> indices_vec{0, 2, 5, 7};
Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
auto res =
- storage.OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ queriable->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
ASSERT_EQ(res.start, 2u);
ASSERT_EQ(res.end, 4u);
}
} // namespace
-} // namespace column
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/query_executor.cc b/src/trace_processor/db/query_executor.cc
index 226e75a..b7f23c8 100644
--- a/src/trace_processor/db/query_executor.cc
+++ b/src/trace_processor/db/query_executor.cc
@@ -14,20 +14,22 @@
* limitations under the License.
*/
-#include <array>
-#include <cmath>
-#include <cstddef>
+#include <algorithm>
+#include <cstdint>
#include <memory>
-#include <numeric>
#include <optional>
+#include <utility>
#include <vector>
#include "perfetto/base/logging.h"
-#include "perfetto/ext/base/status_or.h"
+#include "perfetto/ext/base/small_vector.h"
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/containers/string_pool.h"
+#include "src/trace_processor/db/column.h"
#include "src/trace_processor/db/column/arrangement_overlay.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/dense_null_overlay.h"
#include "src/trace_processor/db/column/dummy_storage.h"
#include "src/trace_processor/db/column/id_storage.h"
@@ -40,18 +42,16 @@
#include "src/trace_processor/db/query_executor.h"
#include "src/trace_processor/db/table.h"
-namespace perfetto {
-namespace trace_processor {
+namespace perfetto::trace_processor {
namespace {
using Range = RowMap::Range;
-using Storage = column::Column;
} // namespace
void QueryExecutor::FilterColumn(const Constraint& c,
- const column::Column& storage,
+ const column::DataNode::Queryable& queryable,
RowMap* rm) {
// Shortcut of empty row map.
if (rm->empty())
@@ -65,7 +65,7 @@
return;
}
- switch (storage.ValidateSearchConstraints(c.value, c.op)) {
+ switch (queryable.ValidateSearchConstraints(c.value, c.op)) {
case SearchValidationResult::kAllData:
return;
case SearchValidationResult::kNoData:
@@ -88,20 +88,20 @@
rm->IsIndexVector() || rm_size < 1024 || rm_size * 10 < range_size;
if (!disallows_index_search && prefers_index_search) {
- IndexSearch(c, storage, rm);
+ IndexSearch(c, queryable, rm);
return;
}
- LinearSearch(c, storage, rm);
+ LinearSearch(c, queryable, rm);
}
void QueryExecutor::LinearSearch(const Constraint& c,
- const column::Column& storage,
+ const column::DataNode::Queryable& queryable,
RowMap* rm) {
// TODO(b/283763282): Align these to word boundaries.
Range bounds(rm->Get(0), rm->Get(rm->size() - 1) + 1);
// Search the storage.
- RangeOrBitVector res = storage.Search(c.op, c.value, bounds);
+ RangeOrBitVector res = queryable.Search(c.op, c.value, bounds);
if (rm->IsRange()) {
if (res.IsRange()) {
Range range = std::move(res).TakeIfRange();
@@ -123,12 +123,12 @@
}
void QueryExecutor::IndexSearch(const Constraint& c,
- const column::Column& storage,
+ const column::DataNode::Queryable& queryable,
RowMap* rm) {
// Create outmost TableIndexVector.
std::vector<uint32_t> table_indices = std::move(*rm).TakeAsIndexVector();
- RangeOrBitVector matched = storage.IndexSearch(
+ RangeOrBitVector matched = queryable.IndexSearch(
c.op, c.value,
Indices{table_indices.data(), static_cast<uint32_t>(table_indices.size()),
Indices::State::kMonotonic});
@@ -184,105 +184,133 @@
}
// Create storage
- std::unique_ptr<column::Column> storage;
+ base::SmallVector<std::unique_ptr<column::DataNode>, 4> data_nodes;
+ std::unique_ptr<column::DataNode::Queryable> queryable;
if (col.IsSetId()) {
if (col.IsNullable()) {
- storage = std::make_unique<column::SetIdStorage>(
- &col.storage<std::optional<uint32_t>>().non_null_vector());
+ data_nodes.emplace_back(std::make_unique<column::SetIdStorage>(
+ &col.storage<std::optional<uint32_t>>().non_null_vector()));
+ queryable = data_nodes.back()->MakeQueryable();
} else {
- storage = std::make_unique<column::SetIdStorage>(
- &col.storage<uint32_t>().vector());
+ data_nodes.emplace_back(std::make_unique<column::SetIdStorage>(
+ &col.storage<uint32_t>().vector()));
+ queryable = data_nodes.back()->MakeQueryable();
}
} else {
switch (col.col_type()) {
case ColumnType::kDummy:
- storage = std::make_unique<column::DummyStorage>();
+ data_nodes.emplace_back(std::make_unique<column::DummyStorage>());
+ queryable = data_nodes.back()->MakeQueryable();
break;
case ColumnType::kId:
- storage = std::make_unique<column::IdStorage>(column_size);
+ data_nodes.emplace_back(
+ std::make_unique<column::IdStorage>(column_size));
+ queryable = data_nodes.back()->MakeQueryable();
break;
case ColumnType::kString:
- storage = std::make_unique<column::StringStorage>(
+ data_nodes.emplace_back(std::make_unique<column::StringStorage>(
table->string_pool(), &col.storage<StringPool::Id>().vector(),
- col.IsSorted());
+ col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
break;
case ColumnType::kInt64:
if (col.IsNullable()) {
- storage = std::make_unique<column::NumericStorage<int64_t>>(
- &col.storage<std::optional<int64_t>>().non_null_vector(),
- col.col_type(), col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<int64_t>>(
+ &col.storage<std::optional<int64_t>>().non_null_vector(),
+ col.col_type(), col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
} else {
- storage = std::make_unique<column::NumericStorage<int64_t>>(
- &col.storage<int64_t>().vector(), col.col_type(),
- col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<int64_t>>(
+ &col.storage<int64_t>().vector(), col.col_type(),
+ col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
}
break;
case ColumnType::kUint32:
if (col.IsNullable()) {
- storage = std::make_unique<column::NumericStorage<uint32_t>>(
- &col.storage<std::optional<uint32_t>>().non_null_vector(),
- col.col_type(), col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<uint32_t>>(
+ &col.storage<std::optional<uint32_t>>().non_null_vector(),
+ col.col_type(), col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
} else {
- storage = std::make_unique<column::NumericStorage<uint32_t>>(
- &col.storage<uint32_t>().vector(), col.col_type(),
- col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<uint32_t>>(
+ &col.storage<uint32_t>().vector(), col.col_type(),
+ col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
}
break;
case ColumnType::kInt32:
if (col.IsNullable()) {
- storage = std::make_unique<column::NumericStorage<int32_t>>(
- &col.storage<std::optional<int32_t>>().non_null_vector(),
- col.col_type(), col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<int32_t>>(
+ &col.storage<std::optional<int32_t>>().non_null_vector(),
+ col.col_type(), col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
} else {
- storage = std::make_unique<column::NumericStorage<int32_t>>(
- &col.storage<int32_t>().vector(), col.col_type(),
- col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<int32_t>>(
+ &col.storage<int32_t>().vector(), col.col_type(),
+ col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
}
break;
case ColumnType::kDouble:
if (col.IsNullable()) {
- storage = std::make_unique<column::NumericStorage<double>>(
- &col.storage<std::optional<double>>().non_null_vector(),
- col.col_type(), col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<double>>(
+ &col.storage<std::optional<double>>().non_null_vector(),
+ col.col_type(), col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
} else {
- storage = std::make_unique<column::NumericStorage<double>>(
- &col.storage<double>().vector(), col.col_type(),
- col.IsSorted());
+ data_nodes.emplace_back(
+ std::make_unique<column::NumericStorage<double>>(
+ &col.storage<double>().vector(), col.col_type(),
+ col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable();
}
}
}
+
if (col.IsNullable()) {
// String columns are inherently nullable: null values are signified
// with Id::Null().
PERFETTO_CHECK(col.col_type() != ColumnType::kString);
if (col.IsDense()) {
- storage = std::make_unique<column::DenseNullOverlay>(
- std::move(storage), col.storage_base().bv());
+ data_nodes.emplace_back(std::make_unique<column::DenseNullOverlay>(
+ col.storage_base().bv()));
+ queryable = data_nodes.back()->MakeQueryable(std::move(queryable));
} else {
- storage = std::make_unique<column::NullOverlay>(
- std::move(storage), col.storage_base().bv());
+ data_nodes.emplace_back(
+ std::make_unique<column::NullOverlay>(col.storage_base().bv()));
+ queryable = data_nodes.back()->MakeQueryable(std::move(queryable));
}
}
if (col.overlay().row_map().IsIndexVector()) {
- storage = std::make_unique<column::ArrangementOverlay>(
- std::move(storage), col.overlay().row_map().GetIfIndexVector(),
- col.IsSorted());
+ data_nodes.emplace_back(std::make_unique<column::ArrangementOverlay>(
+ col.overlay().row_map().GetIfIndexVector(), col.IsSorted()));
+ queryable = data_nodes.back()->MakeQueryable(std::move(queryable));
}
if (col.overlay().row_map().IsBitVector()) {
- storage = std::make_unique<column::SelectorOverlay>(
- std::move(storage), col.overlay().row_map().GetIfBitVector());
+ data_nodes.emplace_back(std::make_unique<column::SelectorOverlay>(
+ col.overlay().row_map().GetIfBitVector()));
+ queryable = data_nodes.back()->MakeQueryable(std::move(queryable));
}
uint32_t pre_count = rm.size();
- FilterColumn(c, *storage.get(), &rm);
+ FilterColumn(c, *queryable, &rm);
PERFETTO_DCHECK(rm.size() <= pre_count);
}
return rm;
}
-void QueryExecutor::BoundedColumnFilterForTesting(const Constraint& c,
- const column::Column& col,
- RowMap* rm) {
+void QueryExecutor::BoundedColumnFilterForTesting(
+ const Constraint& c,
+ const column::DataNode::Queryable& col,
+ RowMap* rm) {
switch (col.ValidateSearchConstraints(c.value, c.op)) {
case SearchValidationResult::kAllData:
return;
@@ -296,9 +324,10 @@
LinearSearch(c, col, rm);
}
-void QueryExecutor::IndexedColumnFilterForTesting(const Constraint& c,
- const column::Column& col,
- RowMap* rm) {
+void QueryExecutor::IndexedColumnFilterForTesting(
+ const Constraint& c,
+ const column::DataNode::Queryable& col,
+ RowMap* rm) {
switch (col.ValidateSearchConstraints(c.value, c.op)) {
case SearchValidationResult::kAllData:
return;
@@ -312,5 +341,4 @@
IndexSearch(c, col, rm);
}
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/db/query_executor.h b/src/trace_processor/db/query_executor.h
index e5feff5..863382d 100644
--- a/src/trace_processor/db/query_executor.h
+++ b/src/trace_processor/db/query_executor.h
@@ -16,14 +16,16 @@
#ifndef SRC_TRACE_PROCESSOR_DB_QUERY_EXECUTOR_H_
#define SRC_TRACE_PROCESSOR_DB_QUERY_EXECUTOR_H_
+#include <cstdint>
#include <vector>
+#include "perfetto/base/logging.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/column.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
+#include "src/trace_processor/db/column/types.h"
-namespace perfetto {
-namespace trace_processor {
+namespace perfetto::trace_processor {
// Responsible for executing filtering/sorting operations on a single Table.
// TODO(b/283763282): Introduce sorting.
@@ -32,7 +34,8 @@
static constexpr uint32_t kMaxOverlayCount = 8;
// |row_count| is the size of the last overlay.
- QueryExecutor(const std::vector<column::Column*>& columns, uint32_t row_count)
+ QueryExecutor(const std::vector<column::DataNode::Queryable*>& columns,
+ uint32_t row_count)
: columns_(columns), row_count_(row_count) {}
// Apply all the constraints on the data and return the filtered RowMap.
@@ -44,48 +47,43 @@
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.
static RowMap FilterLegacy(const Table*, const std::vector<Constraint>&);
- // 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 void BoundedColumnFilterForTesting(const Constraint&,
- const column::Column&,
+ const column::DataNode::Queryable&,
RowMap*);
// Used only in unittests. Exposes private function.
static void IndexedColumnFilterForTesting(const Constraint&,
- const column::Column&,
+ const column::DataNode::Queryable&,
RowMap*);
private:
// Updates RowMap with result of filtering single column using the Constraint.
- static void FilterColumn(const Constraint&, const column::Column&, RowMap*);
+ static void FilterColumn(const Constraint&,
+ const column::DataNode::Queryable&,
+ RowMap*);
// Filters the column using Range algorithm - tries to find the smallest Range
// to filter the storage with.
- static void LinearSearch(const Constraint&, const column::Column&, RowMap*);
+ static void LinearSearch(const Constraint&,
+ const column::DataNode::Queryable&,
+ RowMap*);
// Filters the column using Index algorithm - finds the indices to filter the
// storage with.
- static void IndexSearch(const Constraint&, const column::Column&, RowMap*);
+ static void IndexSearch(const Constraint&,
+ const column::DataNode::Queryable&,
+ RowMap*);
- std::vector<column::Column*> columns_;
+ std::vector<column::DataNode::Queryable*> columns_;
// Number of rows in the outmost overlay.
uint32_t row_count_ = 0;
};
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor
#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
index b3a1bc5..ecff6a6 100644
--- a/src/trace_processor/db/query_executor_unittest.cc
+++ b/src/trace_processor/db/query_executor_unittest.cc
@@ -16,9 +16,20 @@
#include "src/trace_processor/db/query_executor.h"
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+#include <numeric>
+#include <string>
+#include <vector>
+
+#include "perfetto/ext/base/string_view.h"
#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/containers/string_pool.h"
#include "src/trace_processor/db/column/arrangement_overlay.h"
-#include "src/trace_processor/db/column/column.h"
+#include "src/trace_processor/db/column/data_node.h"
#include "src/trace_processor/db/column/fake_storage.h"
#include "src/trace_processor/db/column/id_storage.h"
#include "src/trace_processor/db/column/null_overlay.h"
@@ -26,10 +37,10 @@
#include "src/trace_processor/db/column/selector_overlay.h"
#include "src/trace_processor/db/column/set_id_storage.h"
#include "src/trace_processor/db/column/string_storage.h"
+#include "src/trace_processor/db/column/types.h"
#include "test/gtest_and_gmock.h"
-namespace perfetto {
-namespace trace_processor {
+namespace perfetto::trace_processor {
namespace {
using testing::ElementsAre;
@@ -44,10 +55,11 @@
TEST(QueryExecutor, OnlyStorageRange) {
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
+ auto queryable = storage.MakeQueryable();
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
- RowMap rm(0, storage.size());
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ RowMap rm(0, queryable->size());
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 3u);
ASSERT_EQ(rm.Get(0), 2u);
@@ -56,10 +68,11 @@
TEST(QueryExecutor, OnlyStorageRangeIsNull) {
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
+ auto queryable = storage.MakeQueryable();
Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 5);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 0u);
}
@@ -71,10 +84,11 @@
std::transform(storage_data.begin(), storage_data.end(), storage_data.begin(),
[](int64_t n) { return n % 5; });
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
+ auto queryable = storage.MakeQueryable();
Constraint c{0, FilterOp::kLt, SqlValue::Long(2)};
RowMap rm(0, 10);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 4u);
ASSERT_EQ(rm.Get(0), 0u);
@@ -86,10 +100,11 @@
TEST(QueryExecutor, OnlyStorageIndexIsNull) {
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
+ auto queryable = storage.MakeQueryable();
Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 5);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 0u);
}
@@ -100,11 +115,12 @@
auto numeric = std::make_unique<column::NumericStorage<int64_t>>(
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
- column::NullOverlay storage(std::move(numeric), &bv);
+ column::NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
RowMap rm(0, 10);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 2u);
ASSERT_EQ(rm.Get(0), 4u);
@@ -118,11 +134,12 @@
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
- column::NullOverlay storage(std::move(numeric), &bv);
+ column::NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- RowMap rm(0, storage.size());
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ RowMap rm(0, queryable->size());
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 5u);
ASSERT_EQ(rm.Get(0), 2u);
@@ -141,11 +158,12 @@
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 1, 1, 0, 1, 0, 0, 1};
- column::NullOverlay storage(std::move(numeric), &bv);
+ column::NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(1)};
RowMap rm(0, 10);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 4u);
ASSERT_EQ(rm.Get(0), 1u);
@@ -161,11 +179,12 @@
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
- column::NullOverlay storage(std::move(numeric), &bv);
+ column::NullOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 10);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_EQ(rm.size(), 5u);
ASSERT_EQ(rm.Get(0), 2u);
@@ -182,11 +201,12 @@
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 0, 1};
- SelectorOverlay storage(std::move(numeric), &bv);
+ SelectorOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGt, SqlValue::Long(1)};
RowMap rm(0, 3);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u));
}
@@ -200,11 +220,12 @@
&storage_data, ColumnType::kInt64);
BitVector bv{1, 1, 0, 1, 1, 0, 1, 0, 0, 1};
- SelectorOverlay storage(std::move(numeric), &bv);
+ SelectorOverlay storage(&bv);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(2)};
RowMap rm(0, 6);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u, 3u, 5u));
}
@@ -216,39 +237,40 @@
&storage_data, ColumnType::kInt64);
std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
- ArrangementOverlay storage(std::move(numeric), &arrangement, false);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
RowMap rm(0, 5);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(0u, 4u));
}
TEST(QueryExecutor, ArrangementOverlaySubsetInputRange) {
- std::unique_ptr<column::Column> fake =
- column::FakeStorage::SearchSubset(5u, RowMap::Range(2u, 4u));
+ auto fake = column::FakeStorage::SearchSubset(5u, RowMap::Range(2u, 4u));
std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
- ArrangementOverlay storage(std::move(fake), &arrangement, false);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(0u)};
RowMap rm(1, 3);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u));
}
TEST(QueryExecutor, ArrangementOverlaySubsetInputBitvector) {
- std::unique_ptr<column::Column> fake =
- column::FakeStorage::SearchSubset(5u, BitVector({0, 0, 1, 1, 0}));
+ auto fake = column::FakeStorage::SearchSubset(5u, BitVector({0, 0, 1, 1, 0}));
std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
- ArrangementOverlay storage(std::move(fake), &arrangement, false);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queryable = storage.MakeQueryable(fake->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(0u)};
RowMap rm(1, 3);
- QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::BoundedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u));
}
@@ -260,11 +282,12 @@
&storage_data, ColumnType::kInt64);
std::vector<uint32_t> arrangement{4, 1, 2, 2, 3};
- ArrangementOverlay storage(std::move(numeric), &arrangement, false);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queryable = storage.MakeQueryable(numeric->MakeQueryable());
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
RowMap rm(0, 5);
- QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, *queryable, &rm);
ASSERT_THAT(rm.GetAllIndices(), ElementsAre(0u, 4u));
}
@@ -272,10 +295,11 @@
TEST(QueryExecutor, MismatchedTypeNullWithOtherOperations) {
std::vector<int64_t> storage_data{0, 1, 2, 3, 0, 1, 2, 3};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue()};
- QueryExecutor exec({&storage}, 6);
+ QueryExecutor exec({queryable.get()}, 6);
RowMap res = exec.Filter({c});
ASSERT_TRUE(res.empty());
@@ -289,17 +313,18 @@
// Current vector
// 0, 1, NULL, 2, 3, 0, NULL, NULL, 1, 2, 3, NULL
BitVector null_bv{1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0};
- auto null =
- std::make_unique<column::NullOverlay>(std::move(numeric), &null_bv);
+ auto null = std::make_unique<column::NullOverlay>(&null_bv);
// Final vector
// 0, NULL, 3, NULL, 1, 3
BitVector selector_bv{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
- SelectorOverlay storage(std::move(null), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable =
+ storage.MakeQueryable(null->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::Long(2)};
- QueryExecutor exec({&storage}, 6);
+ QueryExecutor exec({queryable.get()}, 6);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -315,17 +340,18 @@
// Current vector
// 0, 1, NULL, 2, 3, 0, NULL, NULL, 1, 2, 3, NULL
BitVector null_bv{1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0};
- auto null =
- std::make_unique<column::NullOverlay>(std::move(numeric), &null_bv);
+ auto null = std::make_unique<column::NullOverlay>(&null_bv);
// Final vector
// NULL, 3, NULL, NULL, 3, NULL
std::vector<uint32_t> arrangement{2, 4, 6, 2, 4, 6};
- ArrangementOverlay storage(std::move(null), &arrangement, false);
+ ArrangementOverlay storage(&arrangement, false);
+ auto queryable =
+ storage.MakeQueryable(null->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::Long(1)};
- QueryExecutor exec({&storage}, 6);
+ QueryExecutor exec({queryable.get()}, 6);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -341,17 +367,18 @@
// Current vector
// 0, 1, NULL, 2, 3, 0, NULL, NULL, 1, 2, 3, NULL
BitVector null_bv{1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0};
- auto null =
- std::make_unique<column::NullOverlay>(std::move(numeric), &null_bv);
+ auto null = std::make_unique<column::NullOverlay>(&null_bv);
// Final vector
// 0, NULL, 3, NULL, 1, 3
BitVector selector_bv{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0};
- SelectorOverlay storage(std::move(null), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable =
+ storage.MakeQueryable(null->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- QueryExecutor exec({&storage}, 6);
+ QueryExecutor exec({queryable.get()}, 6);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -366,16 +393,18 @@
// Add nulls - {0, 1, NULL, NULL, 2, 3, NULL, NULL, 4, 5, 6, NULL}
BitVector null_bv{1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0};
- auto null =
- std::make_unique<column::NullOverlay>(std::move(numeric), &null_bv);
+ auto null = std::make_unique<column::NullOverlay>(&null_bv);
// Final vector {1, NULL, 3, NULL, 5, NULL}.
BitVector selector_bv{0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
- SelectorOverlay storage(std::move(null), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+
+ auto queryable =
+ storage.MakeQueryable(null->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
- QueryExecutor exec({&storage}, 6);
+ QueryExecutor exec({queryable.get()}, 6);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -390,16 +419,18 @@
// Select 6 elements from storage, resulting in a vector {0, 1, 3, 4, 6, 7}.
BitVector selector_bv{1, 1, 0, 1, 1, 0, 1, 1, 0, 0};
- auto selector =
- std::make_unique<SelectorOverlay>(std::move(numeric), &selector_bv);
+ auto selector = std::make_unique<SelectorOverlay>(&selector_bv);
// Add nulls, final vector {NULL, NULL, NULL 0, 1, 3, 4, 6, 7}.
BitVector null_bv{0, 0, 0, 1, 1, 1, 1, 1, 1};
- column::NullOverlay storage(std::move(selector), &null_bv);
+ column::NullOverlay storage(&null_bv);
+
+ auto queryable =
+ storage.MakeQueryable(selector->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- QueryExecutor exec({&storage}, 9);
+ QueryExecutor exec({queryable.get()}, 9);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 3u);
@@ -414,16 +445,18 @@
// Select 6 elements from storage, resulting in a vector {0, 3, 3, 6, 9, 9}.
BitVector selector_bv{0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
- auto selector =
- std::make_unique<SelectorOverlay>(std::move(numeric), &selector_bv);
+ auto selector = std::make_unique<SelectorOverlay>(&selector_bv);
// Add nulls - vector (size 10) {NULL, 0, 3, NULL, 3, 6, NULL, 9, 9, NULL}.
BitVector null_bv{0, 1, 1, 0, 1, 1, 0, 1, 1, 0};
- column::NullOverlay storage(std::move(selector), &null_bv);
+ column::NullOverlay storage(&null_bv);
+
+ auto queryable =
+ storage.MakeQueryable(selector->MakeQueryable(numeric->MakeQueryable()));
// Filter.
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- QueryExecutor exec({&storage}, 10);
+ QueryExecutor exec({queryable.get()}, 10);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 4u);
@@ -437,10 +470,11 @@
std::vector<int64_t> storage_data{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64,
true);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kNe, SqlValue::Long(5)};
- QueryExecutor exec({&storage}, 10);
+ QueryExecutor exec({queryable.get()}, 10);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 9u);
@@ -448,10 +482,11 @@
TEST(QueryExecutor, IdSearchIsNull) {
IdStorage storage(5);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 0u);
@@ -459,10 +494,11 @@
TEST(QueryExecutor, IdSearchIsNotNull) {
IdStorage storage(5);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kIsNotNull, SqlValue()};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 5u);
@@ -470,10 +506,11 @@
TEST(QueryExecutor, IdSearchNotEq) {
IdStorage storage(5);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kNe, SqlValue::Long(3)};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 4u);
@@ -492,11 +529,12 @@
// Final vec {"cheese", "pasta", "NULL", "pierogi", "fries"}.
BitVector selector_bv{1, 1, 0, 1, 1, 0, 1};
- SelectorOverlay storage(std::move(string), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable = storage.MakeQueryable(string->MakeQueryable());
// Filter.
Constraint c{0, FilterOp::kIsNull, SqlValue()};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 1u);
@@ -515,11 +553,12 @@
// Final vec {"apple", "burger", "doughnut", "eggplant"}.
BitVector selector_bv{1, 1, 0, 1, 1, 0};
- SelectorOverlay storage(std::move(string), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable = storage.MakeQueryable(string->MakeQueryable());
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::String("camembert")};
- QueryExecutor exec({&storage}, 4);
+ QueryExecutor exec({queryable.get()}, 4);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -538,11 +577,12 @@
// Final vec {"apple", "burger", "doughnut", "eggplant"}.
BitVector selector_bv{1, 1, 0, 1, 1, 0};
- SelectorOverlay storage(std::move(string), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable = storage.MakeQueryable(string->MakeQueryable());
// Filter.
Constraint c{0, FilterOp::kNe, SqlValue::String("doughnut")};
- QueryExecutor exec({&storage}, 4);
+ QueryExecutor exec({queryable.get()}, 4);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 3u);
@@ -551,10 +591,11 @@
TEST(QueryExecutor, MismatchedTypeIdWithString) {
IdStorage storage(5);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::String("cheese")};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 0u);
@@ -562,10 +603,11 @@
TEST(QueryExecutor, MismatchedTypeIdWithDouble) {
IdStorage storage(5);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::Double(1.5)};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 3u);
@@ -574,10 +616,11 @@
TEST(QueryExecutor, MismatchedTypeSetIdWithDouble) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
SetIdStorage storage(&storage_data);
+ auto queryable = storage.MakeQueryable();
// Filter.
Constraint c{0, FilterOp::kGe, SqlValue::Double(1.5)};
- QueryExecutor exec({&storage}, storage.size());
+ QueryExecutor exec({queryable.get()}, queryable->size());
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 9u);
@@ -597,11 +640,12 @@
// Final vec {"cheese", "pasta", "NULL", "pierogi", "fries"}.
BitVector selector_bv{1, 1, 0, 1, 1, 0, 1};
- SelectorOverlay storage(std::move(string), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable = storage.MakeQueryable(string->MakeQueryable());
// Filter.
Constraint c{0, FilterOp::kRegex, SqlValue::String("p.*")};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 2u);
@@ -622,11 +666,12 @@
// Final vec {"cheese", "pasta", "NULL", "pierogi", "fries"}.
BitVector selector_bv{1, 1, 0, 1, 1, 0, 1};
- SelectorOverlay storage(std::move(string), &selector_bv);
+ SelectorOverlay storage(&selector_bv);
+ auto queryable = storage.MakeQueryable(string->MakeQueryable());
// Filter.
Constraint c{0, FilterOp::kRegex, SqlValue::Long(4)};
- QueryExecutor exec({&storage}, 5);
+ QueryExecutor exec({queryable.get()}, 5);
RowMap res = exec.Filter({c});
ASSERT_EQ(res.size(), 0u);
@@ -634,5 +679,4 @@
#endif
} // namespace
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/BUILD.gn b/src/trace_processor/perfetto_sql/stdlib/android/BUILD.gn
index 776b8b2..0d6a3cb 100644
--- a/src/trace_processor/perfetto_sql/stdlib/android/BUILD.gn
+++ b/src/trace_processor/perfetto_sql/stdlib/android/BUILD.gn
@@ -25,6 +25,7 @@
"broadcasts.sql",
"dvfs.sql",
"garbage_collection.sql",
+ "input.sql",
"io.sql",
"monitor_contention.sql",
"network_packets.sql",
diff --git a/src/trace_processor/perfetto_sql/stdlib/android/input.sql b/src/trace_processor/perfetto_sql/stdlib/android/input.sql
new file mode 100644
index 0000000..f344c20
--- /dev/null
+++ b/src/trace_processor/perfetto_sql/stdlib/android/input.sql
@@ -0,0 +1,134 @@
+--
+-- Copyright 2024 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
+--
+-- https://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 PERFETTO MODULE common.timestamps;
+
+CREATE PERFETTO TABLE _input_message_sent
+AS
+SELECT
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 3), ')', 0) AS event_type,
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 2), ',', 0) AS event_seq,
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 1), ',', 0) AS event_channel,
+ thread.tid,
+ thread.name AS thread_name,
+ process.pid,
+ process.name AS process_name,
+ slice.ts,
+ slice.dur,
+ slice.track_id
+FROM slice
+JOIN thread_track
+ ON thread_track.id = slice.track_id
+JOIN thread
+ USING (utid)
+JOIN process
+ USING (upid)
+WHERE slice.name GLOB 'sendMessage(*';
+
+CREATE PERFETTO TABLE _input_message_received
+AS
+SELECT
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 3), ')', 0) AS event_type,
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 2), ',', 0) AS event_seq,
+ STR_SPLIT(STR_SPLIT(slice.name, '=', 1), ',', 0) AS event_channel,
+ thread.tid,
+ thread.name AS thread_name,
+ process.pid,
+ process.name AS process_name,
+ slice.ts,
+ slice.dur,
+ slice.track_id
+FROM slice
+JOIN thread_track
+ ON thread_track.id = slice.track_id
+JOIN thread
+ USING (utid)
+JOIN process
+ USING (upid)
+WHERE slice.name GLOB 'receiveMessage(*';
+
+-- All input events with round trip latency breakdown. Input delivery is socket based and every
+-- input event sent from the OS needs to be ACK'ed by the app. This gives us 4 subevents to measure
+-- latencies between:
+-- 1. Input dispatch event sent from OS.
+-- 2. Input dispatch event received in app.
+-- 3. Input ACK event sent from app.
+-- 4. Input ACk event received in OS.
+CREATE PERFETTO TABLE android_input_events (
+ -- Duration from input dispatch to input received.
+ dispatch_latency_dur INT,
+ -- Duration from input received to input ACK sent.
+ handling_latency_dur INT,
+ -- Duration from input ACK sent to input ACK recieved.
+ ack_latency_dur INT,
+ -- Duration from input dispatch to input event ACK received.
+ total_latency_dur INT,
+ -- Tid of thread receiving the input event.
+ tid INT,
+ -- Name of thread receiving the input event.
+ thread_name INT,
+ -- Pid of process receiving the input event.
+ pid INT,
+ -- Name of process receiving the input event.
+ process_name INT,
+ -- Input event type. See InputTransport.h: InputMessage#Type
+ event_type INT,
+ -- Input event sequence number, monotonically increasing for an event channel and pid.
+ event_seq INT,
+ -- Input event channel name.
+ event_channel INT,
+ -- Thread track id of input event dispatching thread.
+ dispatch_track_id INT,
+ -- Timestamp input event was dispatched.
+ dispatch_ts INT,
+ -- Duration of input event dispatch.
+ dispatch_dur INT,
+ -- Thread track id of input event receiving thread.
+ receive_track_id INT,
+ -- Timestamp input event was received.
+ receive_ts INT,
+ -- Duration of input event receipt.
+ receive_dur INT
+ )
+AS
+SELECT
+ receive.ts - dispatch.ts AS dispatch_latency_dur,
+ finish.ts - receive.ts AS handling_latency_dur,
+ finish_ack.ts - finish.ts AS ack_latency_dur,
+ finish_ack.ts - dispatch.ts AS total_latency_dur,
+ finish.tid AS tid,
+ finish.thread_name AS thread_name,
+ finish.pid AS pid,
+ finish.process_name AS process_name,
+ dispatch.event_type,
+ dispatch.event_seq,
+ dispatch.event_channel,
+ dispatch.track_id AS dispatch_track_id,
+ dispatch.ts AS dispatch_ts,
+ dispatch.dur AS dispatch_dur,
+ receive.ts AS receive_ts,
+ receive.dur AS receive_dur,
+ receive.track_id AS receive_track_id
+FROM (SELECT * FROM _input_message_sent WHERE thread_name = 'InputDispatcher') dispatch
+JOIN (SELECT * FROM _input_message_received WHERE event_type != '0x2') receive
+ ON
+ REPLACE(receive.event_channel, '(client)', '(server)') = dispatch.event_channel
+ AND dispatch.event_seq = receive.event_seq
+JOIN (SELECT * FROM _input_message_sent WHERE thread_name != 'InputDispatcher') finish
+ ON
+ REPLACE(finish.event_channel, '(client)', '(server)') = dispatch.event_channel
+ AND dispatch.event_seq = finish.event_seq
+JOIN (SELECT * FROM _input_message_received WHERE event_type = '0x2') finish_ack
+ ON finish_ack.event_channel = dispatch.event_channel AND dispatch.event_seq = finish_ack.event_seq;
diff --git a/test/data/post_boot_trace.atr.sha256 b/test/data/post_boot_trace.atr.sha256
new file mode 100644
index 0000000..199aa56
--- /dev/null
+++ b/test/data/post_boot_trace.atr.sha256
@@ -0,0 +1 @@
+ed411bb57c771ecff0f04e9eac8dcec3ccafa8c13c82106a4c8f555fe9617fe6
\ No newline at end of file
diff --git a/test/trace_processor/diff_tests/stdlib/android/tests.py b/test/trace_processor/diff_tests/stdlib/android/tests.py
index cbd56e4..177174b 100644
--- a/test/trace_processor/diff_tests/stdlib/android/tests.py
+++ b/test/trace_processor/diff_tests/stdlib/android/tests.py
@@ -1088,4 +1088,42 @@
3494,3487,"HeapTaskDaemon","com.android.providers.media.module","young",0,"[NULL]","[NULL]","[NULL]",213263593,55205035,10429437,0,0,1208604
3494,3487,"HeapTaskDaemon","com.android.providers.media.module","collector_transition",0,1.248000,2.201000,3.449000,169735717,65828710,20965673,0,0,0
3556,3549,"HeapTaskDaemon","com.android.externalstorage","collector_transition",0,0.450000,2.038000,2.488000,166379142,52906367,7881722,0,0,0
+ """))
+
+ def test_input_events(self):
+ return DiffTestBlueprint(
+ trace=DataPath('post_boot_trace.atr'),
+ query="""
+ INCLUDE PERFETTO MODULE android.input;
+ SELECT
+ total_latency_dur,
+ handling_latency_dur,
+ dispatch_latency_dur,
+ tid,
+ thread_name,
+ pid,
+ process_name,
+ event_type,
+ event_seq,
+ event_channel,
+ dispatch_ts,
+ dispatch_dur,
+ receive_ts,
+ receive_dur
+ FROM android_input_events
+ ORDER BY dispatch_ts
+ LIMIT 10
+ """,
+ out=Csv("""
+ "total_latency_dur","handling_latency_dur","dispatch_latency_dur","tid","thread_name","pid","process_name","event_type","event_seq","event_channel","dispatch_ts","dispatch_dur","receive_ts","receive_dur"
+ 377149054,77503,377032734,7493,"ndroid.systemui",7493,"com.android.systemui","0x3","0x1","4325794 NotificationShade (server)",578307771330,1292,578684804064,1412
+ 1684318,772908,48433,7493,"ndroid.systemui",7493,"com.android.systemui","0x1","0x2","a0526ca NavigationBar0 (server)",581956322279,1299,581956370712,1806
+ 22069988,12614508,804831,7493,"ndroid.systemui",7493,"com.android.systemui","0x1","0x3","4325794 NotificationShade (server)",581956391308,1212,581957196139,1362
+ 1603522,645723,75328,7964,"droid.launcher3",7964,"com.android.launcher3","0x1","0x4","[Gesture Monitor] swipe-up (server)",581956445376,1232,581956520704,1708
+ 1583707,644313,208973,7310,"android.ui",7288,"system_server","0x1","0x5","PointerEventDispatcher0 (server)",581956495788,1208,581956704761,1281
+ 22622740,22582066,25729,7493,"ndroid.systemui",7493,"com.android.systemui","0x1","0x6","4325794 NotificationShade (server)",582019627670,1230,582019653399,1607
+ 20228399,20116160,95263,7964,"droid.launcher3",7964,"com.android.launcher3","0x1","0x7","[Gesture Monitor] swipe-up (server)",582019685639,1309,582019780902,1942
+ 459763,287436,27342,7310,"android.ui",7288,"system_server","0x1","0x8","PointerEventDispatcher0 (server)",582019737156,1192,582019764498,1664
+ 9848456,9806401,22714,7493,"ndroid.systemui",7493,"com.android.systemui","0x1","0x9","4325794 NotificationShade (server)",582051061377,1227,582051084091,1596
+ 5533919,5487703,25013,7964,"droid.launcher3",7964,"com.android.launcher3","0x1","0xa","[Gesture Monitor] swipe-up (server)",582051112236,1258,582051137249,1771
"""))
