Merge "tp: rewrite OrderedIndexSearch to be truly O(logn)" into main
diff --git a/Android.bp b/Android.bp
index e83139e..972f828 100644
--- a/Android.bp
+++ b/Android.bp
@@ -2391,6 +2391,7 @@
":perfetto_src_shared_lib_test_utils",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
@@ -16061,6 +16062,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
@@ -16298,6 +16300,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_importers_common_common",
":perfetto_src_trace_processor_importers_common_parser_types",
@@ -16457,6 +16460,7 @@
":perfetto_src_protozero_protozero",
":perfetto_src_trace_processor_containers_containers",
":perfetto_src_trace_processor_db_column_column",
+ ":perfetto_src_trace_processor_db_compare",
":perfetto_src_trace_processor_db_db",
":perfetto_src_trace_processor_db_minimal",
":perfetto_src_trace_processor_export_json",
diff --git a/BUILD b/BUILD
index 430f9dc..537ccc4 100644
--- a/BUILD
+++ b/BUILD
@@ -217,6 +217,7 @@
":src_kernel_utils_syscall_table",
":src_protozero_proto_ring_buffer",
":src_trace_processor_db_column_column",
+ ":src_trace_processor_db_compare",
":src_trace_processor_db_db",
":src_trace_processor_db_minimal",
":src_trace_processor_export_json",
@@ -1426,6 +1427,14 @@
],
)
+# GN target: //src/trace_processor/db:compare
+perfetto_filegroup(
+ name = "src_trace_processor_db_compare",
+ srcs = [
+ "src/trace_processor/db/compare.h",
+ ],
+)
+
# GN target: //src/trace_processor/db:db
perfetto_filegroup(
name = "src_trace_processor_db_db",
@@ -5979,6 +5988,7 @@
srcs = [
":src_kernel_utils_syscall_table",
":src_trace_processor_db_column_column",
+ ":src_trace_processor_db_compare",
":src_trace_processor_db_db",
":src_trace_processor_db_minimal",
":src_trace_processor_export_json",
@@ -6158,6 +6168,7 @@
":src_profiling_symbolizer_symbolizer",
":src_protozero_proto_ring_buffer",
":src_trace_processor_db_column_column",
+ ":src_trace_processor_db_compare",
":src_trace_processor_db_db",
":src_trace_processor_db_minimal",
":src_trace_processor_export_json",
@@ -6397,6 +6408,7 @@
":src_profiling_symbolizer_symbolizer",
":src_protozero_proto_ring_buffer",
":src_trace_processor_db_column_column",
+ ":src_trace_processor_db_compare",
":src_trace_processor_db_db",
":src_trace_processor_db_minimal",
":src_trace_processor_export_json",
diff --git a/src/trace_processor/containers/string_pool.h b/src/trace_processor/containers/string_pool.h
index 75a57a2..2e03592 100644
--- a/src/trace_processor/containers/string_pool.h
+++ b/src/trace_processor/containers/string_pool.h
@@ -17,21 +17,25 @@
#ifndef SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
#define SRC_TRACE_PROCESSOR_CONTAINERS_STRING_POOL_H_
-#include <stddef.h>
-#include <stdint.h>
-
+#include <cstddef>
+#include <cstdint>
+#include <functional>
#include <limits>
+#include <memory>
#include <optional>
+#include <string>
+#include <utility>
#include <vector>
+#include "perfetto/base/logging.h"
#include "perfetto/ext/base/flat_hash_map.h"
#include "perfetto/ext/base/hash.h"
#include "perfetto/ext/base/paged_memory.h"
+#include "perfetto/ext/base/string_view.h"
#include "perfetto/protozero/proto_utils.h"
#include "src/trace_processor/containers/null_term_string_view.h"
-namespace perfetto {
-namespace trace_processor {
+namespace perfetto::trace_processor {
// Interns strings in a string pool and hands out compact StringIds which can
// be used to retrieve the string in O(1).
@@ -40,34 +44,38 @@
struct Id {
Id() = default;
- bool operator==(const Id& other) const { return other.id == id; }
- bool operator!=(const Id& other) const { return !(other == *this); }
- bool operator<(const Id& other) const { return id < other.id; }
+ constexpr bool operator==(const Id& other) const { return other.id == id; }
+ constexpr bool operator!=(const Id& other) const {
+ return !(other == *this);
+ }
+ constexpr bool operator<(const Id& other) const { return id < other.id; }
- bool is_null() const { return id == 0u; }
+ constexpr bool is_null() const { return id == 0u; }
- bool is_large_string() const { return id & kLargeStringFlagBitMask; }
+ constexpr bool is_large_string() const {
+ return id & kLargeStringFlagBitMask;
+ }
- uint32_t block_offset() const { return id & kBlockOffsetBitMask; }
+ constexpr uint32_t block_offset() const { return id & kBlockOffsetBitMask; }
- uint32_t block_index() const {
+ constexpr uint32_t block_index() const {
return (id & kBlockIndexBitMask) >> kNumBlockOffsetBits;
}
- uint32_t large_string_index() const {
+ constexpr uint32_t large_string_index() const {
PERFETTO_DCHECK(is_large_string());
return id & ~kLargeStringFlagBitMask;
}
- uint32_t raw_id() const { return id; }
+ constexpr uint32_t raw_id() const { return id; }
- static Id LargeString(size_t index) {
+ static constexpr Id LargeString(size_t index) {
PERFETTO_DCHECK(index <= static_cast<uint32_t>(index));
PERFETTO_DCHECK(!(index & kLargeStringFlagBitMask));
return Id(kLargeStringFlagBitMask | static_cast<uint32_t>(index));
}
- static Id BlockString(size_t index, uint32_t offset) {
+ static constexpr Id BlockString(size_t index, uint32_t offset) {
PERFETTO_DCHECK(index < (1u << (kNumBlockIndexBits + 1)));
PERFETTO_DCHECK(offset < (1u << (kNumBlockOffsetBits + 1)));
return Id(~kLargeStringFlagBitMask &
@@ -80,7 +88,7 @@
static constexpr Id Null() { return Id(0u); }
private:
- constexpr Id(uint32_t i) : id(i) {}
+ constexpr explicit Id(uint32_t i) : id(i) {}
uint32_t id;
};
@@ -88,7 +96,7 @@
// Iterator over the strings in the pool.
class Iterator {
public:
- Iterator(const StringPool*);
+ explicit Iterator(const StringPool*);
explicit operator bool() const;
Iterator& operator++();
@@ -278,7 +286,7 @@
static NullTermStringView GetFromBlockPtr(const uint8_t* ptr) {
uint32_t size = 0;
const uint8_t* str_ptr = ReadSize(ptr, &size);
- return NullTermStringView(reinterpret_cast<const char*>(str_ptr), size);
+ return {reinterpret_cast<const char*>(str_ptr), size};
}
// Lookup a string in the |large_strings_| vector. |id| should have the MSB
@@ -288,7 +296,7 @@
size_t index = id.large_string_index();
PERFETTO_DCHECK(index < large_strings_.size());
const std::string* str = large_strings_[index].get();
- return NullTermStringView(str->c_str(), str->size());
+ return {str->c_str(), str->size()};
}
// The actual memory storing the strings.
@@ -308,8 +316,7 @@
string_index_{/*initial_capacity=*/4096u};
};
-} // namespace trace_processor
-} // namespace perfetto
+} // namespace perfetto::trace_processor
template <>
struct std::hash<::perfetto::trace_processor::StringPool::Id> {
diff --git a/src/trace_processor/db/column/BUILD.gn b/src/trace_processor/db/column/BUILD.gn
index d53e7ae..f77887f 100644
--- a/src/trace_processor/db/column/BUILD.gn
+++ b/src/trace_processor/db/column/BUILD.gn
@@ -43,6 +43,7 @@
"utils.h",
]
deps = [
+ "..:compare",
"../..:metatrace",
"../../../../gn:default_deps",
"../../../../include/perfetto/trace_processor",
diff --git a/src/trace_processor/db/column/arrangement_overlay.cc b/src/trace_processor/db/column/arrangement_overlay.cc
index c31d7c2..e7bc8ff 100644
--- a/src/trace_processor/db/column/arrangement_overlay.cc
+++ b/src/trace_processor/db/column/arrangement_overlay.cc
@@ -68,12 +68,21 @@
if (does_arrangement_order_storage_ && op != FilterOp::kGlob &&
op != FilterOp::kRegex) {
- Range inner_res = inner_->OrderedIndexSearchValidated(
- op, sql_val,
- OrderedIndices{arrangement_->data() + in.start, in.size(),
- arrangement_state_});
+ OrderedIndices indices{arrangement_->data() + in.start, in.size(),
+ arrangement_state_};
+ if (op == FilterOp::kNe) {
+ // Do an equality search and "invert" the range.
+ Range inner_res =
+ inner_->OrderedIndexSearchValidated(FilterOp::kEq, sql_val, indices);
+ BitVector bv(in.start);
+ bv.Resize(in.start + inner_res.start, true);
+ bv.Resize(in.start + inner_res.end, false);
+ bv.Resize(in.end, true);
+ return RangeOrBitVector(std::move(bv));
+ }
+ Range inner_res = inner_->OrderedIndexSearchValidated(op, sql_val, indices);
return RangeOrBitVector(
- Range(inner_res.start + in.start, inner_res.end + in.start));
+ Range(in.start + inner_res.start, in.start + inner_res.end));
}
const auto& arrangement = *arrangement_;
@@ -196,6 +205,11 @@
return inner_->MinElement(indices);
}
+SqlValue ArrangementOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return inner_->Get_AvoidUsingBecauseSlow((*arrangement_)[index]);
+}
+
void ArrangementOverlay::ChainImpl::Serialize(StorageProto* storage) const {
auto* arrangement_overlay = storage->set_arrangement_overlay();
arrangement_overlay->set_values(
diff --git a/src/trace_processor/db/column/arrangement_overlay.h b/src/trace_processor/db/column/arrangement_overlay.h
index 3656b07..85b9ce4 100644
--- a/src/trace_processor/db/column/arrangement_overlay.h
+++ b/src/trace_processor/db/column/arrangement_overlay.h
@@ -19,10 +19,10 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include <vector>
-#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/db/column/data_layer.h"
#include "src/trace_processor/db/column/types.h"
@@ -61,13 +61,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override {
- PERFETTO_FATAL(
- "OrderedIndexSearch can't be called on ArrangementOverlay");
- }
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -78,6 +71,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override {
diff --git a/src/trace_processor/db/column/arrangement_overlay_unittest.cc b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
index 55f310b..8820336 100644
--- a/src/trace_processor/db/column/arrangement_overlay_unittest.cc
+++ b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
@@ -108,15 +108,20 @@
}
TEST(ArrangementOverlay, OrderingSearch) {
- std::vector<uint32_t> arrangement{0, 2, 4, 1, 3};
- auto fake = FakeStorageChain::SearchSubset(5, BitVector({0, 1, 0, 1, 0}));
+ std::vector<uint32_t> numeric_data{0, 1, 2, 0, 1, 0};
+ NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
+
+ std::vector<uint32_t> arrangement{0, 3, 5, 1, 4, 2};
ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
- auto chain =
- storage.MakeChain(std::move(fake), DataLayer::ChainCreationArgs(true));
+ auto chain = storage.MakeChain(numeric.MakeChain(),
+ DataLayer::ChainCreationArgs(true));
RangeOrBitVector res =
- chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 5));
+ chain->Search(FilterOp::kGe, SqlValue::Long(1u), Range(0, 5));
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
+
+ res = chain->Search(FilterOp::kNe, SqlValue::Long(1u), Range(1, 6));
+ ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 5));
}
TEST(ArrangementOverlay, StableSort) {
diff --git a/src/trace_processor/db/column/data_layer.cc b/src/trace_processor/db/column/data_layer.cc
index 634cbce..a570415 100644
--- a/src/trace_processor/db/column/data_layer.cc
+++ b/src/trace_processor/db/column/data_layer.cc
@@ -16,12 +16,15 @@
#include "src/trace_processor/db/column/data_layer.h"
+#include <algorithm>
#include <cstdint>
+#include <iterator>
#include <memory>
#include <utility>
#include <vector>
#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/string_pool.h"
#include "src/trace_processor/db/column/arrangement_overlay.h"
@@ -35,6 +38,7 @@
#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 "src/trace_processor/db/compare.h"
namespace perfetto::trace_processor::column {
@@ -113,6 +117,53 @@
PERFETTO_FATAL("For GCC");
}
+Range DataLayerChain::OrderedIndexSearchValidated(
+ FilterOp op,
+ SqlValue value,
+ const OrderedIndices& indices) const {
+ auto lb = [&]() {
+ return static_cast<uint32_t>(std::distance(
+ indices.data,
+ std::lower_bound(indices.data, indices.data + indices.size, value,
+ [this](uint32_t idx, const SqlValue& v) {
+ return compare::SqlValueComparator(
+ Get_AvoidUsingBecauseSlow(idx), v);
+ })));
+ };
+ auto ub = [&]() {
+ return static_cast<uint32_t>(std::distance(
+ indices.data,
+ std::upper_bound(indices.data, indices.data + indices.size, value,
+ [this](const SqlValue& v, uint32_t idx) {
+ return compare::SqlValueComparator(
+ v, Get_AvoidUsingBecauseSlow(idx));
+ })));
+ };
+ switch (op) {
+ case FilterOp::kEq:
+ return {lb(), ub()};
+ case FilterOp::kLe:
+ return {0, ub()};
+ case FilterOp::kLt:
+ return {0, lb()};
+ case FilterOp::kGe:
+ return {lb(), indices.size};
+ case FilterOp::kGt:
+ return {ub(), indices.size};
+ case FilterOp::kIsNull:
+ PERFETTO_CHECK(value.is_null());
+ return {0, ub()};
+ case FilterOp::kIsNotNull:
+ PERFETTO_CHECK(value.is_null());
+ return {ub(), indices.size};
+ case FilterOp::kNe:
+ case FilterOp::kGlob:
+ case FilterOp::kRegex:
+ PERFETTO_FATAL("Wrong filtering operation");
+ }
+ PERFETTO_FATAL("For GCC");
+}
+
ArrangementOverlay::ArrangementOverlay(
const std::vector<uint32_t>* arrangement,
DataLayerChain::Indices::State arrangement_state)
diff --git a/src/trace_processor/db/column/data_layer.h b/src/trace_processor/db/column/data_layer.h
index 5e34539..b6f9382 100644
--- a/src/trace_processor/db/column/data_layer.h
+++ b/src/trace_processor/db/column/data_layer.h
@@ -321,9 +321,26 @@
// Post-validated implementation of |OrderedIndexSearch|. See
// |OrderedIndexSearch|'s documentation.
- virtual Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const = 0;
+ Range OrderedIndexSearchValidated(FilterOp op,
+ SqlValue value,
+ const OrderedIndices& indices) const;
+
+ // Returns the SqlValue representing the value at a given index.
+ //
+ // This function might be very tempting to use as it appears cheap on the
+ // surface but because of how DataLayerChains might be layered on top of each
+ // other, this might require *several* virtual function calls per index.
+ // If you're tempted to use this, please consider instead create a new
+ // "vectorized" function instead and only using this as a last resort.
+ //
+ // The correct "class" of algorithms to use this function are cases where you
+ // have a set of indices you want to lookup and based on the value returned
+ // you will only use a fraction of them. In this case, it might be worth
+ // paying the non-vectorized lookup to vastly reduce how many indices need
+ // to be translated.
+ //
+ // An example of such an algorithm is binary search on indices.
+ virtual SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const = 0;
};
} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/dense_null_overlay.cc b/src/trace_processor/db/column/dense_null_overlay.cc
index 79ca3c0..426c6d2 100644
--- a/src/trace_processor/db/column/dense_null_overlay.cc
+++ b/src/trace_processor/db/column/dense_null_overlay.cc
@@ -219,50 +219,6 @@
inner_->IndexSearchValidated(op, sql_val, indices);
}
-Range DenseNullOverlay::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& 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::ChainImpl::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); });
-
- auto non_null_offset =
- static_cast<uint32_t>(std::distance(indices.data, first_non_null));
- auto non_null_size = static_cast<uint32_t>(
- std::distance(first_non_null, indices.data + indices.size));
-
- if (op == FilterOp::kIsNull) {
- return {0, non_null_offset};
- }
-
- if (op == FilterOp::kIsNotNull) {
- switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData:
- return {};
- case SearchValidationResult::kAllData:
- return {non_null_offset, indices.size};
- case SearchValidationResult::kOk:
- break;
- }
- }
-
- Range inner_range = inner_->OrderedIndexSearchValidated(
- op, sql_val,
- OrderedIndices{first_non_null, non_null_size,
- Indices::State::kNonmonotonic});
- return {inner_range.start + non_null_offset,
- inner_range.end + non_null_offset};
-}
-
void DenseNullOverlay::ChainImpl::StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const {
@@ -314,6 +270,12 @@
: *first_null_it;
}
+SqlValue DenseNullOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return non_null_->IsSet(index) ? inner_->Get_AvoidUsingBecauseSlow(index)
+ : SqlValue();
+}
+
void DenseNullOverlay::ChainImpl::Serialize(StorageProto* storage) const {
auto* null_overlay = storage->set_dense_null_overlay();
non_null_->Serialize(null_overlay->set_bit_vector());
diff --git a/src/trace_processor/db/column/dense_null_overlay.h b/src/trace_processor/db/column/dense_null_overlay.h
index e253400..d0a95d2 100644
--- a/src/trace_processor/db/column/dense_null_overlay.h
+++ b/src/trace_processor/db/column/dense_null_overlay.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -56,10 +57,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -70,6 +67,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override { return non_null_->size(); }
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 24b1eee..7cd74f6 100644
--- a/src/trace_processor/db/column/dense_null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/dense_null_overlay_unittest.cc
@@ -129,11 +129,12 @@
}
TEST(DenseNullOverlay, OrderedIndexSearch) {
- auto fake = FakeStorageChain::SearchSubset(6, BitVector({0, 1, 0, 1, 0, 1}));
+ std::vector<uint32_t> numeric_data{0, 1, 0, 1, 0, 1};
+ NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
BitVector bv{0, 1, 0, 1, 0, 1};
DenseNullOverlay storage(&bv);
- auto chain = storage.MakeChain(std::move(fake));
+ auto chain = storage.MakeChain(numeric.MakeChain());
std::vector<uint32_t> indices_vec({0, 2, 4, 1, 3, 5});
OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
@@ -146,25 +147,25 @@
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
+ res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(1), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
+ res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
+ res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(1), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 6u);
- res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
- ASSERT_EQ(res.start, 3u);
- ASSERT_EQ(res.end, 6u);
+ res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(1), indices);
+ ASSERT_EQ(res.start, 0u);
+ ASSERT_EQ(res.end, 3u);
- res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
- ASSERT_EQ(res.start, 3u);
- ASSERT_EQ(res.end, 6u);
+ res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(0), indices);
+ ASSERT_EQ(res.start, 0u);
+ ASSERT_EQ(res.end, 3u);
}
TEST(DenseNullOverlay, SingleSearch) {
diff --git a/src/trace_processor/db/column/dummy_storage.cc b/src/trace_processor/db/column/dummy_storage.cc
index 631cbb7..ef9cacf 100644
--- a/src/trace_processor/db/column/dummy_storage.cc
+++ b/src/trace_processor/db/column/dummy_storage.cc
@@ -17,6 +17,7 @@
#include "src/trace_processor/db/column/dummy_storage.h"
#include <cstdint>
+#include <optional>
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
@@ -49,13 +50,6 @@
PERFETTO_FATAL("Shouldn't be called");
}
-Range DummyStorage::ChainImpl::OrderedIndexSearchValidated(
- FilterOp,
- SqlValue,
- const OrderedIndices&) const {
- PERFETTO_FATAL("Shouldn't be called");
-}
-
void DummyStorage::ChainImpl::StableSort(SortToken*,
SortToken*,
SortDirection) const {
@@ -78,6 +72,10 @@
PERFETTO_FATAL("Shouldn't be called");
}
+SqlValue DummyStorage::ChainImpl::Get_AvoidUsingBecauseSlow(uint32_t) const {
+ PERFETTO_FATAL("Shouldn't be called");
+}
+
void DummyStorage::ChainImpl::Serialize(StorageProto*) const {
PERFETTO_FATAL("Shouldn't be called");
}
diff --git a/src/trace_processor/db/column/dummy_storage.h b/src/trace_processor/db/column/dummy_storage.h
index ffa0c73..66f2497 100644
--- a/src/trace_processor/db/column/dummy_storage.h
+++ b/src/trace_processor/db/column/dummy_storage.h
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -45,10 +46,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -59,6 +56,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override;
diff --git a/src/trace_processor/db/column/fake_storage.cc b/src/trace_processor/db/column/fake_storage.cc
index 5a26961..5015bf3 100644
--- a/src/trace_processor/db/column/fake_storage.cc
+++ b/src/trace_processor/db/column/fake_storage.cc
@@ -19,6 +19,7 @@
#include <algorithm>
#include <cstdint>
#include <iterator>
+#include <optional>
#include <utility>
#include "perfetto/base/logging.h"
@@ -112,43 +113,6 @@
PERFETTO_FATAL("For GCC");
}
-Range FakeStorageChain::OrderedIndexSearchValidated(
- FilterOp,
- SqlValue,
- const OrderedIndices& indices) const {
- switch (strategy_) {
- case kAll:
- return {0, indices.size};
- case kNone:
- return {};
- case kRange: {
- // We are looking at intersection of |range_| and |indices_|.
- const uint32_t* first_in_range = std::partition_point(
- indices.data, indices.data + indices.size,
- [this](uint32_t i) { return !range_.Contains(i); });
- 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 {
- static_cast<uint32_t>(std::distance(indices.data, first_in_range)),
- static_cast<uint32_t>(
- std::distance(indices.data, first_outside_range))};
- }
- case kBitVector:
- // We are looking at intersection of |range_| and |bit_vector_|.
- const uint32_t* first_set = std::partition_point(
- indices.data, indices.data + indices.size,
- [this](uint32_t i) { return !bit_vector_.IsSet(i); });
- 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 {
- static_cast<uint32_t>(std::distance(indices.data, first_set)),
- static_cast<uint32_t>(std::distance(indices.data, first_non_set))};
- }
- PERFETTO_FATAL("For GCC");
-}
-
void FakeStorageChain::Distinct(Indices&) const {
// Fake storage shouldn't implement Distinct as it's not a binary (this index
// passes or not) operation on a column.
@@ -166,6 +130,10 @@
PERFETTO_FATAL("Not implemented");
}
+SqlValue FakeStorageChain::Get_AvoidUsingBecauseSlow(uint32_t) const {
+ PERFETTO_FATAL("Not implemented");
+}
+
void FakeStorageChain::Serialize(StorageProto*) const {
// FakeStorage doesn't really make sense to serialize.
PERFETTO_FATAL("Not implemented");
diff --git a/src/trace_processor/db/column/fake_storage.h b/src/trace_processor/db/column/fake_storage.h
index 7adf786..980a951 100644
--- a/src/trace_processor/db/column/fake_storage.h
+++ b/src/trace_processor/db/column/fake_storage.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include <utility>
#include <vector>
@@ -84,10 +85,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -95,8 +92,11 @@
void Distinct(Indices&) const override;
std::optional<Token> MaxElement(Indices&) const override;
+
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override { return size_; }
diff --git a/src/trace_processor/db/column/fake_storage_unittest.cc b/src/trace_processor/db/column/fake_storage_unittest.cc
index 908b7e0..28c497f 100644
--- a/src/trace_processor/db/column/fake_storage_unittest.cc
+++ b/src/trace_processor/db/column/fake_storage_unittest.cc
@@ -43,7 +43,6 @@
using testing::IsEmpty;
using Indices = DataLayerChain::Indices;
-using OrderedIndices = DataLayerChain::OrderedIndices;
TEST(FakeStorage, ValidateSearchConstraints) {
{
@@ -197,48 +196,6 @@
}
}
-TEST(FakeStorage, OrderedIndexSearchValidated) {
- std::vector<uint32_t> table_idx{4, 3, 2, 1};
- OrderedIndices indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic};
- {
- // All passes
- auto fake = FakeStorageChain::SearchAll(5);
- Range ret =
- fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
- EXPECT_EQ(ret, Range(0, 4));
- }
- {
- // None passes
- auto fake = FakeStorageChain::SearchNone(5);
- Range ret =
- fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
- EXPECT_EQ(ret, Range(0, 0));
- }
- {
- // BitVector
- auto fake = FakeStorageChain::SearchSubset(5, BitVector{0, 0, 1, 1, 1});
- Range ret =
- fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
- EXPECT_EQ(ret, Range(0, 3));
- }
- {
- // Index vector
- auto fake =
- FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2, 3});
- Range ret =
- fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
- EXPECT_EQ(ret, Range(1, 4));
- }
- {
- // Range
- auto fake = FakeStorageChain::SearchSubset(5, Range(1, 4));
- Range ret =
- fake->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
- EXPECT_EQ(ret, Range(1, 4));
- }
-}
-
} // namespace
} // namespace column
} // namespace perfetto::trace_processor
diff --git a/src/trace_processor/db/column/id_storage.cc b/src/trace_processor/db/column/id_storage.cc
index ea1e909..1ebe459 100644
--- a/src/trace_processor/db/column/id_storage.cc
+++ b/src/trace_processor/db/column/id_storage.cc
@@ -246,47 +246,6 @@
PERFETTO_FATAL("FilterOp not matched");
}
-Range IdStorage::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& indices) const {
- PERFETTO_DCHECK(op != FilterOp::kNe);
-
- PERFETTO_TP_TRACE(
- metatrace::Category::DB, "IdStorage::ChainImpl::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.
- if (sql_val.type == SqlValue::kDouble) {
- switch (utils::CompareIntColumnWithDouble(op, &sql_val)) {
- case SearchValidationResult::kOk:
- break;
- case SearchValidationResult::kAllData:
- return {0, indices.size};
- case SearchValidationResult::kNoData:
- return {};
- }
- }
- auto val = static_cast<uint32_t>(sql_val.AsLong());
-
- // OrderedIndices 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);
-
- 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::ChainImpl::BinarySearchIntrinsic(FilterOp op,
Id val,
Range range) {
@@ -363,6 +322,10 @@
return *tok;
}
+SqlValue IdStorage::ChainImpl::Get_AvoidUsingBecauseSlow(uint32_t index) const {
+ return SqlValue::Long(index);
+}
+
void IdStorage::ChainImpl::Serialize(StorageProto* storage) const {
storage->set_id_storage();
}
diff --git a/src/trace_processor/db/column/id_storage.h b/src/trace_processor/db/column/id_storage.h
index 420568d..c3aeadf 100644
--- a/src/trace_processor/db/column/id_storage.h
+++ b/src/trace_processor/db/column/id_storage.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <limits>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -55,10 +56,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -69,6 +66,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override {
diff --git a/src/trace_processor/db/column/null_overlay.cc b/src/trace_processor/db/column/null_overlay.cc
index 128d3ff..372d3b0 100644
--- a/src/trace_processor/db/column/null_overlay.cc
+++ b/src/trace_processor/db/column/null_overlay.cc
@@ -256,56 +256,6 @@
inner_->IndexSearchValidated(op, sql_val, indices);
}
-Range NullOverlay::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& 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::ChainImpl::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); });
- auto non_null_offset =
- static_cast<uint32_t>(std::distance(indices.data, first_non_null));
- auto non_null_size = static_cast<uint32_t>(
- std::distance(first_non_null, indices.data + indices.size));
-
- if (op == FilterOp::kIsNull) {
- return {0, non_null_offset};
- }
-
- if (op == FilterOp::kIsNotNull) {
- switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData:
- return {};
- case SearchValidationResult::kAllData:
- return {non_null_offset, indices.size};
- case SearchValidationResult::kOk:
- break;
- }
- }
-
- std::vector<uint32_t> storage_iv;
- storage_iv.reserve(non_null_size);
- for (const uint32_t* it = first_non_null;
- it != first_non_null + non_null_size; it++) {
- storage_iv.push_back(non_null_->CountSetBits(*it));
- }
-
- Range inner_range = inner_->OrderedIndexSearchValidated(
- op, sql_val,
- OrderedIndices{storage_iv.data(), non_null_size, indices.state});
- return {inner_range.start + non_null_offset,
- inner_range.end + non_null_offset};
-}
-
void NullOverlay::ChainImpl::StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const {
@@ -369,6 +319,13 @@
return inner_->MinElement(indices);
}
+SqlValue NullOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return non_null_->IsSet(index)
+ ? inner_->Get_AvoidUsingBecauseSlow(non_null_->CountSetBits(index))
+ : SqlValue();
+}
+
void NullOverlay::ChainImpl::Serialize(StorageProto* storage) const {
auto* null_storage = storage->set_null_overlay();
non_null_->Serialize(null_storage->set_bit_vector());
diff --git a/src/trace_processor/db/column/null_overlay.h b/src/trace_processor/db/column/null_overlay.h
index 187c056..a74f211 100644
--- a/src/trace_processor/db/column/null_overlay.h
+++ b/src/trace_processor/db/column/null_overlay.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -55,10 +56,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -69,6 +66,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override { return non_null_->size(); }
diff --git a/src/trace_processor/db/column/null_overlay_unittest.cc b/src/trace_processor/db/column/null_overlay_unittest.cc
index 981c7bd..9cff095 100644
--- a/src/trace_processor/db/column/null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/null_overlay_unittest.cc
@@ -200,15 +200,15 @@
}
TEST(NullOverlay, OrderedIndexSearch) {
+ std::vector<uint32_t> numeric_data{1, 0, 1, 0};
+ NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
+
BitVector bv{0, 1, 1, 1, 0, 1};
- // Passing values in final storage (on normal operations)
- // 0, 1, 0, 1, 0, 0
- auto fake = FakeStorageChain::SearchSubset(4, BitVector{1, 0, 1, 0});
NullOverlay storage(&bv);
- auto chain = storage.MakeChain(std::move(fake));
+ auto chain = storage.MakeChain(numeric.MakeChain());
// Passing values on final data
- // NULL, NULL, 0, 1, 1
+ // NULL, NULL, 0, 0, 1, 1
std::vector<uint32_t> table_idx{0, 4, 5, 1, 3};
OrderedIndices indices{table_idx.data(), uint32_t(table_idx.size()),
Indices::State::kNonmonotonic};
@@ -218,28 +218,28 @@
ASSERT_EQ(res.end, 2u);
res = chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ ASSERT_EQ(res.start, 2u);
+ ASSERT_EQ(res.end, 5u);
+
+ res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(1), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(3), indices);
+ res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(3), indices);
+ res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(1), indices);
ASSERT_EQ(res.start, 3u);
ASSERT_EQ(res.end, 5u);
- res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(3), indices);
- ASSERT_EQ(res.start, 3u);
- ASSERT_EQ(res.end, 5u);
+ res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(1), indices);
+ ASSERT_EQ(res.start, 0u);
+ ASSERT_EQ(res.end, 3u);
- res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(3), indices);
- ASSERT_EQ(res.start, 3u);
- ASSERT_EQ(res.end, 5u);
-
- res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(3), indices);
- ASSERT_EQ(res.start, 3u);
- ASSERT_EQ(res.end, 5u);
+ res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(0), indices);
+ ASSERT_EQ(res.start, 0u);
+ ASSERT_EQ(res.end, 3u);
}
TEST(NullOverlay, StableSort) {
diff --git a/src/trace_processor/db/column/numeric_storage.cc b/src/trace_processor/db/column/numeric_storage.cc
index b39b4cb..3612356 100644
--- a/src/trace_processor/db/column/numeric_storage.cc
+++ b/src/trace_processor/db/column/numeric_storage.cc
@@ -138,60 +138,6 @@
}
template <typename T>
-uint32_t TypedLowerBoundExtrinsic(T val,
- const T* data,
- OrderedIndices indices) {
- 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));
-}
-
-uint32_t LowerBoundExtrinsic(const void* vector_ptr,
- NumericValue val,
- OrderedIndices indices) {
- if (const auto* u32 = std::get_if<uint32_t>(&val)) {
- const auto* start =
- static_cast<const std::vector<uint32_t>*>(vector_ptr)->data();
- return TypedLowerBoundExtrinsic(*u32, start, indices);
- }
- if (const auto* i64 = std::get_if<int64_t>(&val)) {
- const auto* start =
- static_cast<const std::vector<int64_t>*>(vector_ptr)->data();
- return TypedLowerBoundExtrinsic(*i64, start, indices);
- }
- if (const auto* i32 = std::get_if<int32_t>(&val)) {
- const auto* start =
- static_cast<const std::vector<int32_t>*>(vector_ptr)->data();
- return TypedLowerBoundExtrinsic(*i32, start, indices);
- }
- if (const auto* db = std::get_if<double>(&val)) {
- const auto* start =
- static_cast<const std::vector<double>*>(vector_ptr)->data();
- return TypedLowerBoundExtrinsic(*db, start, indices);
- }
- PERFETTO_FATAL("Type not handled");
-}
-
-uint32_t UpperBoundExtrinsic(const void* vector_ptr,
- NumericValue val,
- OrderedIndices indices) {
- return std::visit(
- [vector_ptr, indices](auto val_data) {
- using T = decltype(val_data);
- const T* typed_start =
- static_cast<const std::vector<T>*>(vector_ptr)->data();
- 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];
- });
- return static_cast<uint32_t>(std::distance(indices.data, upper));
- },
- val);
-}
-
-template <typename T>
void TypedLinearSearch(T typed_val,
const T* start,
FilterOp op,
@@ -504,79 +450,6 @@
val);
}
-Range NumericStorageBase::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& indices) const {
- PERFETTO_TP_TRACE(
- metatrace::Category::DB, "NumericStorage::ChainImpl::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)));
- });
-
- // Mismatched types - value is double and column is int.
- if (sql_val.type == SqlValue::kDouble &&
- storage_type_ != ColumnType::kDouble) {
- if (auto ret = utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val),
- indices.size);
- ret) {
- return *ret;
- }
- }
-
- // Mismatched types - column is double and value is int.
- if (sql_val.type != SqlValue::kDouble &&
- storage_type_ == ColumnType::kDouble) {
- if (auto ret = utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val),
- indices.size);
- ret) {
- return *ret;
- }
- }
-
- NumericValue val;
- switch (storage_type_) {
- case ColumnType::kDouble:
- val = sql_val.AsDouble();
- break;
- case ColumnType::kInt64:
- val = sql_val.AsLong();
- break;
- case ColumnType::kInt32:
- val = static_cast<int32_t>(sql_val.AsLong());
- break;
- case ColumnType::kUint32:
- val = static_cast<uint32_t>(sql_val.AsLong());
- break;
- case ColumnType::kString:
- case ColumnType::kDummy:
- case ColumnType::kId:
- PERFETTO_FATAL("Invalid type");
- }
-
- switch (op) {
- case FilterOp::kEq:
- return {LowerBoundExtrinsic(vector_ptr_, val, indices),
- UpperBoundExtrinsic(vector_ptr_, val, indices)};
- case FilterOp::kLe:
- return {0, UpperBoundExtrinsic(vector_ptr_, val, indices)};
- case FilterOp::kLt:
- return {0, LowerBoundExtrinsic(vector_ptr_, val, indices)};
- case FilterOp::kGe:
- return {LowerBoundExtrinsic(vector_ptr_, val, indices), indices.size};
- case FilterOp::kGt:
- return {UpperBoundExtrinsic(vector_ptr_, val, indices), indices.size};
- case FilterOp::kNe:
- case FilterOp::kIsNull:
- case FilterOp::kIsNotNull:
- case FilterOp::kGlob:
- case FilterOp::kRegex:
- PERFETTO_FATAL("Wrong filtering operation");
- }
- PERFETTO_FATAL("For GCC");
-}
-
BitVector NumericStorageBase::ChainImpl::LinearSearchInternal(
FilterOp op,
NumericValue val,
diff --git a/src/trace_processor/db/column/numeric_storage.h b/src/trace_processor/db/column/numeric_storage.h
index fd27d26..3c4416b 100644
--- a/src/trace_processor/db/column/numeric_storage.h
+++ b/src/trace_processor/db/column/numeric_storage.h
@@ -23,6 +23,7 @@
#include <optional>
#include <set>
#include <string>
+#include <type_traits>
#include <unordered_set>
#include <variant>
#include <vector>
@@ -49,10 +50,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void Serialize(StorageProto*) const override;
std::string DebugString() const override { return "NumericStorage"; }
@@ -145,6 +142,13 @@
return *tok;
}
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override {
+ if constexpr (std::is_same_v<T, double>) {
+ return SqlValue::Double((*vector_)[index]);
+ }
+ return SqlValue::Long((*vector_)[index]);
+ }
+
void StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const override {
diff --git a/src/trace_processor/db/column/range_overlay.cc b/src/trace_processor/db/column/range_overlay.cc
index 81bb7ae..dee7838 100644
--- a/src/trace_processor/db/column/range_overlay.cc
+++ b/src/trace_processor/db/column/range_overlay.cc
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <utility>
#include <vector>
@@ -118,22 +119,6 @@
inner_->IndexSearchValidated(op, sql_val, indices);
}
-Range RangeOverlay::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::IndexSearch");
-
- // Should be SIMD optimized.
- std::vector<uint32_t> storage_iv(indices.size);
- for (uint32_t i = 0; i < indices.size; ++i) {
- storage_iv[i] = indices.data[i] + range_->start;
- }
- return inner_->OrderedIndexSearchValidated(
- op, sql_val,
- OrderedIndices{storage_iv.data(), indices.size, indices.state});
-}
-
void RangeOverlay::ChainImpl::StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const {
@@ -160,6 +145,11 @@
return inner_->MaxElement(indices);
}
+SqlValue RangeOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return inner_->Get_AvoidUsingBecauseSlow(index + range_->start);
+}
+
std::optional<Token> RangeOverlay::ChainImpl::MinElement(
Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::MinElement");
diff --git a/src/trace_processor/db/column/range_overlay.h b/src/trace_processor/db/column/range_overlay.h
index f15e8dc..a58df40 100644
--- a/src/trace_processor/db/column/range_overlay.h
+++ b/src/trace_processor/db/column/range_overlay.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -52,10 +53,6 @@
void IndexSearchValidated(FilterOp p, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -66,6 +63,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override { return range_->size(); }
diff --git a/src/trace_processor/db/column/selector_overlay.cc b/src/trace_processor/db/column/selector_overlay.cc
index b2cbc43..9e957cb 100644
--- a/src/trace_processor/db/column/selector_overlay.cc
+++ b/src/trace_processor/db/column/selector_overlay.cc
@@ -16,9 +16,9 @@
#include "src/trace_processor/db/column/selector_overlay.h"
-#include <algorithm>
#include <cstdint>
#include <memory>
+#include <optional>
#include <utility>
#include <vector>
@@ -35,7 +35,7 @@
namespace perfetto::trace_processor::column {
namespace {
-static constexpr uint32_t kIndexOfNthSetRatio = 32;
+constexpr uint32_t kIndexOfNthSetRatio = 32;
} // namespace
@@ -97,23 +97,6 @@
return inner_->IndexSearchValidated(op, sql_val, indices);
}
-Range SelectorOverlay::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& 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);
- for (uint32_t i = 0; i < indices.size; ++i) {
- inner_indices[i] = selector_->IndexOfNthSet(indices.data[i]);
- }
- return inner_->OrderedIndexSearchValidated(
- op, sql_val,
- OrderedIndices{inner_indices.data(),
- static_cast<uint32_t>(inner_indices.size()),
- indices.state});
-}
-
void SelectorOverlay::ChainImpl::StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const {
@@ -148,6 +131,11 @@
return inner_->MinElement(indices);
}
+SqlValue SelectorOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return inner_->Get_AvoidUsingBecauseSlow(selector_->IndexOfNthSet(index));
+}
+
void SelectorOverlay::ChainImpl::Serialize(StorageProto* storage) const {
auto* selector_overlay = storage->set_selector_overlay();
inner_->Serialize(selector_overlay->set_storage());
@@ -164,15 +152,15 @@
for (auto& token : indices.tokens) {
token.index = selector_->IndexOfNthSet(token.index);
}
- } else {
- // TODO(mayzner): once we have a reverse index for IndexOfNthSet in
- // BitVector, this should no longer be necessary.
- std::vector<uint32_t> lookup = selector_->GetSetBitIndices();
- for (auto& token : indices.tokens) {
- token.index = lookup[token.index];
- }
+ return;
}
- return;
+
+ // TODO(mayzner): once we have a reverse index for IndexOfNthSet in
+ // BitVector, this should no longer be necessary.
+ std::vector<uint32_t> lookup = selector_->GetSetBitIndices();
+ for (auto& token : indices.tokens) {
+ token.index = lookup[token.index];
+ }
}
} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/selector_overlay.h b/src/trace_processor/db/column/selector_overlay.h
index d54bdf5..3726f9f 100644
--- a/src/trace_processor/db/column/selector_overlay.h
+++ b/src/trace_processor/db/column/selector_overlay.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include "perfetto/trace_processor/basic_types.h"
@@ -56,10 +57,6 @@
void IndexSearchValidated(FilterOp p, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection) const override;
@@ -70,6 +67,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override { return selector_->size(); }
diff --git a/src/trace_processor/db/column/selector_overlay_unittest.cc b/src/trace_processor/db/column/selector_overlay_unittest.cc
index 0abae4c..def2a77 100644
--- a/src/trace_processor/db/column/selector_overlay_unittest.cc
+++ b/src/trace_processor/db/column/selector_overlay_unittest.cc
@@ -17,6 +17,7 @@
#include "src/trace_processor/db/column/selector_overlay.h"
#include <cstdint>
+#include <utility>
#include <vector>
#include "data_layer.h"
@@ -103,35 +104,23 @@
ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
}
-TEST(SelectorOverlay, OrderedIndexSearchTrivial) {
+TEST(SelectorOverlay, OrderedIndexSearch) {
+ std::vector<uint32_t> numeric_data{1, 0, 0, 1, 1};
+ NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
+
BitVector selector{1, 0, 1, 0, 1};
- auto fake = FakeStorageChain::SearchAll(5);
SelectorOverlay storage(&selector);
- auto chain = storage.MakeChain(std::move(fake));
+ auto chain = storage.MakeChain(numeric.MakeChain());
std::vector<uint32_t> table_idx{1u, 0u, 2u};
Range res = chain->OrderedIndexSearch(
- FilterOp::kGe, SqlValue::Long(0u),
+ FilterOp::kGe, SqlValue::Long(1u),
OrderedIndices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
Indices::State::kNonmonotonic});
- ASSERT_EQ(res.start, 0u);
+ ASSERT_EQ(res.start, 1u);
ASSERT_EQ(res.end, 3u);
}
-TEST(SelectorOverlay, OrderedIndexSearchNone) {
- BitVector selector{1, 0, 1, 0, 1};
- auto fake = FakeStorageChain::SearchNone(5);
- SelectorOverlay storage(&selector);
- auto chain = storage.MakeChain(std::move(fake));
-
- std::vector<uint32_t> table_idx{1u, 0u, 2u};
- Range res = chain->OrderedIndexSearch(
- FilterOp::kGe, SqlValue::Long(0u),
- OrderedIndices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
- ASSERT_EQ(res.size(), 0u);
-}
-
TEST(SelectorOverlay, StableSort) {
std::vector<uint32_t> numeric_data{3, 1, 0, 0, 2, 4, 3, 4};
NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
diff --git a/src/trace_processor/db/column/set_id_storage.cc b/src/trace_processor/db/column/set_id_storage.cc
index 207b649..42ab4ea 100644
--- a/src/trace_processor/db/column/set_id_storage.cc
+++ b/src/trace_processor/db/column/set_id_storage.cc
@@ -19,10 +19,7 @@
#include <algorithm>
#include <cstdint>
#include <functional>
-#include <iterator>
-#include <limits>
-#include <memory>
-#include <set>
+#include <optional>
#include <string>
#include <unordered_set>
#include <utility>
@@ -250,38 +247,17 @@
}
}
-Range SetIdStorage::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB,
- "SetIdStorage::ChainImpl::OrderedIndexSearch");
- // OrderedIndices are monotonic non-contiguous values.
- auto res = SearchValidated(
- op, sql_val, Range(indices.data[0], indices.data[indices.size - 1] + 1));
- PERFETTO_CHECK(res.IsRange());
- Range res_range = std::move(res).TakeIfRange();
-
- 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 {static_cast<uint32_t>(std::distance(indices.data, start_ptr)),
- static_cast<uint32_t>(std::distance(indices.data, end_ptr))};
-}
-
Range SetIdStorage::ChainImpl::BinarySearchIntrinsic(FilterOp op,
SetId val,
Range range) const {
switch (op) {
case FilterOp::kEq: {
- if (values_->data()[val] != val) {
- return Range();
+ if ((*values_)[val] != val) {
+ return {};
}
uint32_t start = std::max(val, range.start);
uint32_t end = UpperBoundIntrinsic(values_->data(), val, range);
- return Range(std::min(start, end), end);
+ return {std::min(start, end), end};
}
case FilterOp::kLe: {
return {range.start, UpperBoundIntrinsic(values_->data(), val, range)};
@@ -370,6 +346,11 @@
return *tok;
}
+SqlValue SetIdStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ return SqlValue::Long((*values_)[index]);
+}
+
void SetIdStorage::ChainImpl::Serialize(StorageProto* msg) const {
auto* vec_msg = msg->set_set_id_storage();
vec_msg->set_values(reinterpret_cast<const uint8_t*>(values_->data()),
diff --git a/src/trace_processor/db/column/set_id_storage.h b/src/trace_processor/db/column/set_id_storage.h
index 2fa6c81..e459106 100644
--- a/src/trace_processor/db/column/set_id_storage.h
+++ b/src/trace_processor/db/column/set_id_storage.h
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include <vector>
@@ -54,10 +55,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const override;
@@ -70,6 +67,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
uint32_t size() const override {
return static_cast<uint32_t>(values_->size());
}
diff --git a/src/trace_processor/db/column/string_storage.cc b/src/trace_processor/db/column/string_storage.cc
index adf3eda..1d25dbb 100644
--- a/src/trace_processor/db/column/string_storage.cc
+++ b/src/trace_processor/db/column/string_storage.cc
@@ -163,36 +163,6 @@
return static_cast<uint32_t>(std::distance(data, upper));
}
-uint32_t LowerBoundExtrinsic(StringPool* pool,
- const StringPool::Id* data,
- NullTermStringView val,
- const uint32_t* indices,
- uint32_t indices_count,
- uint32_t offset) {
- Less comp{pool};
- const auto* lower =
- std::lower_bound(indices + offset, indices + indices_count, val,
- [comp, data](uint32_t index, NullTermStringView val) {
- return comp(data[index], val);
- });
- return static_cast<uint32_t>(std::distance(indices, lower));
-}
-
-uint32_t UpperBoundExtrinsic(StringPool* pool,
- const StringPool::Id* data,
- NullTermStringView val,
- const uint32_t* indices,
- uint32_t indices_count,
- uint32_t offset) {
- Greater comp{pool};
- const auto* upper =
- std::upper_bound(indices + offset, indices + indices_count, val,
- [comp, data](NullTermStringView val, uint32_t index) {
- return comp(data[index], val);
- });
- return static_cast<uint32_t>(std::distance(indices, upper));
-}
-
} // namespace
StringStorage::ChainImpl::ChainImpl(StringPool* string_pool,
@@ -518,64 +488,6 @@
return std::move(builder).Build();
}
-Range StringStorage::ChainImpl::OrderedIndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- const OrderedIndices& indices) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB,
- "StringStorage::ChainImpl::OrderedIndexSearch");
- StringPool::Id val =
- (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
- ? StringPool::Id::Null()
- : string_pool_->InternString(base::StringView(sql_val.AsString()));
- NullTermStringView val_str = string_pool_->Get(val);
-
- auto first_non_null = static_cast<uint32_t>(std::distance(
- indices.data,
- std::partition_point(indices.data, indices.data + indices.size,
- [this](uint32_t i) {
- return (*data_)[i] == StringPool::Id::Null();
- })));
-
- switch (op) {
- case FilterOp::kEq:
- return {LowerBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null),
- UpperBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null)};
- case FilterOp::kLe:
- return {first_non_null,
- UpperBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null)};
- case FilterOp::kLt:
- return {first_non_null,
- LowerBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null)};
- case FilterOp::kGe:
- return {LowerBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null),
- indices.size};
- case FilterOp::kGt:
- return {UpperBoundExtrinsic(string_pool_, data_->data(), val_str,
- indices.data, indices.size, first_non_null),
- indices.size};
- case FilterOp::kIsNull: {
- // Assuming nulls are at the front.
- return Range(0, first_non_null);
- }
- case FilterOp::kIsNotNull: {
- // Assuming nulls are at the front.
- return Range(first_non_null, indices.size);
- }
-
- case FilterOp::kNe:
- case FilterOp::kGlob:
- case FilterOp::kRegex:
- PERFETTO_FATAL("Not supported for OrderedIndexSearch");
- }
- PERFETTO_FATAL("For GCC");
-}
-
Range StringStorage::ChainImpl::BinarySearchIntrinsic(
FilterOp op,
SqlValue sql_val,
@@ -715,6 +627,14 @@
return *tok;
}
+SqlValue StringStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
+ uint32_t index) const {
+ StringPool::Id id = (*data_)[index];
+ return id == StringPool::Id::Null()
+ ? SqlValue()
+ : SqlValue::String(string_pool_->Get(id).c_str());
+}
+
void StringStorage::ChainImpl::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 470ccd1..1c05dd7 100644
--- a/src/trace_processor/db/column/string_storage.h
+++ b/src/trace_processor/db/column/string_storage.h
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <optional>
#include <string>
#include <vector>
@@ -57,10 +58,6 @@
void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- const OrderedIndices&) const override;
-
void StableSort(SortToken* start,
SortToken* end,
SortDirection direction) const override;
@@ -71,6 +68,8 @@
std::optional<Token> MinElement(Indices&) const override;
+ SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
+
void Serialize(StorageProto*) const override;
uint32_t size() const override {
diff --git a/src/trace_processor/db/column/string_storage_unittest.cc b/src/trace_processor/db/column/string_storage_unittest.cc
index 4474ea9..7e7cadb 100644
--- a/src/trace_processor/db/column/string_storage_unittest.cc
+++ b/src/trace_processor/db/column/string_storage_unittest.cc
@@ -383,12 +383,12 @@
op = FilterOp::kLt;
res = chain->OrderedIndexSearch(op, val, indices);
- ASSERT_EQ(res.start, 1u);
+ ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 4u);
op = FilterOp::kLe;
res = chain->OrderedIndexSearch(op, val, indices);
- ASSERT_EQ(res.start, 1u);
+ ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 5u);
op = FilterOp::kGt;
@@ -402,6 +402,7 @@
ASSERT_EQ(res.end, 6u);
op = FilterOp::kIsNull;
+ val = SqlValue();
res = chain->OrderedIndexSearch(op, val, indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 1u);
diff --git a/src/trace_processor/db/query_executor_benchmark.cc b/src/trace_processor/db/query_executor_benchmark.cc
index d6cc57f..dcd75f0 100644
--- a/src/trace_processor/db/query_executor_benchmark.cc
+++ b/src/trace_processor/db/query_executor_benchmark.cc
@@ -513,6 +513,29 @@
}
BENCHMARK(BM_QEFilterOrderedArrangement);
+void BM_QEFilterNullOrderedArrangement(benchmark::State& state) {
+ SliceTableForBenchmark table(state);
+ Order order{table.table_.parent_id().index_in_table(), false};
+ Table slice_sorted_with_parent_id = table.table_.Sort({order});
+
+ Constraint c{table.table_.parent_id().index_in_table(), FilterOp::kGt,
+ SqlValue::Long(26091)};
+ Query q;
+ q.constraints = {c};
+ for (auto _ : state) {
+ benchmark::DoNotOptimize(slice_sorted_with_parent_id.QueryToRowMap(q));
+ }
+ state.counters["s/row"] = benchmark::Counter(
+ static_cast<double>(slice_sorted_with_parent_id.row_count()),
+ benchmark::Counter::kIsIterationInvariantRate |
+ benchmark::Counter::kInvert);
+ state.counters["s/out"] = benchmark::Counter(
+ static_cast<double>(table.table_.QueryToRowMap(q).size()),
+ benchmark::Counter::kIsIterationInvariantRate |
+ benchmark::Counter::kInvert);
+}
+BENCHMARK(BM_QEFilterNullOrderedArrangement);
+
void BM_QESliceFilterIndexSearchOneElement(benchmark::State& state) {
SliceTableForBenchmark table(state);
BenchmarkSliceTableFilter(
