Merge "ui: Rename mouseenter -> onmouseenter in notes panel" into main
diff --git a/python/generators/trace_processor_table/serialize.py b/python/generators/trace_processor_table/serialize.py
index 2881ce0..2096f55 100644
--- a/python/generators/trace_processor_table/serialize.py
+++ b/python/generators/trace_processor_table/serialize.py
@@ -591,7 +591,7 @@
if (overlays()[i].row_map().IsIndexVector()) {{
overlay_layers[i].reset(new column::ArrangementOverlay(
overlays()[i].row_map().GetIfIndexVector(),
- Indices::State::kNonmonotonic));
+ column::DataLayerChain::Indices::State::kNonmonotonic));
}} else if (overlays()[i].row_map().IsBitVector()) {{
overlay_layers[i].reset(new column::SelectorOverlay(
overlays()[i].row_map().GetIfBitVector()));
diff --git a/src/trace_processor/db/column/arrangement_overlay.cc b/src/trace_processor/db/column/arrangement_overlay.cc
index b9e3000..4f4af85 100644
--- a/src/trace_processor/db/column/arrangement_overlay.cc
+++ b/src/trace_processor/db/column/arrangement_overlay.cc
@@ -71,8 +71,8 @@
op != FilterOp::kRegex) {
Range inner_res = inner_->OrderedIndexSearchValidated(
op, sql_val,
- Indices{arrangement_->data() + in.start, in.size(),
- arrangement_state_});
+ OrderedIndices{arrangement_->data() + in.start, in.size(),
+ arrangement_state_});
return RangeOrBitVector(
Range(inner_res.start + in.start, inner_res.end + in.start));
}
@@ -122,31 +122,22 @@
return RangeOrBitVector(std::move(builder).Build());
}
-RangeOrBitVector ArrangementOverlay::ChainImpl::IndexSearchValidated(
+void ArrangementOverlay::ChainImpl::IndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB,
"ArrangementOverlay::ChainImpl::IndexSearch");
- std::vector<uint32_t> storage_iv(indices.size);
- // Should be SIMD optimized.
- for (uint32_t i = 0; i < indices.size; ++i) {
- storage_iv[i] = (*arrangement_)[indices.data[i]];
+ for (auto& i : indices.tokens) {
+ i.index = (*arrangement_)[i.index];
}
-
- // If both the arrangment passed indices are monotonic, we know that this
- // state was not lost.
- if (indices.state == Indices::State::kMonotonic) {
- return inner_->IndexSearchValidated(
- op, sql_val,
- Indices{storage_iv.data(), static_cast<uint32_t>(storage_iv.size()),
- arrangement_state_});
- }
- return inner_->IndexSearchValidated(
- op, sql_val,
- Indices{storage_iv.data(), static_cast<uint32_t>(storage_iv.size()),
- Indices::State::kNonmonotonic});
+ // If the indices state is monotonic, we can just pass the arrangement's
+ // state.
+ indices.state = indices.state == Indices::State::kMonotonic
+ ? arrangement_state_
+ : Indices::State::kNonmonotonic;
+ return inner_->IndexSearchValidated(op, sql_val, indices);
}
void ArrangementOverlay::ChainImpl::StableSort(SortToken* start,
diff --git a/src/trace_processor/db/column/arrangement_overlay.h b/src/trace_processor/db/column/arrangement_overlay.h
index bca884f..2bc61cb 100644
--- a/src/trace_processor/db/column/arrangement_overlay.h
+++ b/src/trace_processor/db/column/arrangement_overlay.h
@@ -35,7 +35,7 @@
class ArrangementOverlay final : public DataLayer {
public:
ArrangementOverlay(const std::vector<uint32_t>* arrangement,
- Indices::State arrangement_state);
+ DataLayerChain::Indices::State arrangement_state);
~ArrangementOverlay() override;
std::unique_ptr<DataLayerChain> MakeChain(
@@ -59,13 +59,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override {
+ const OrderedIndices&) const override {
PERFETTO_FATAL(
"OrderedIndexSearch can't be called on ArrangementOverlay");
}
@@ -91,7 +89,7 @@
std::unique_ptr<DataLayerChain> inner_;
const std::vector<uint32_t>* arrangement_;
- const Indices::State arrangement_state_;
+ const DataLayerChain::Indices::State arrangement_state_;
};
} // namespace perfetto::trace_processor::column
diff --git a/src/trace_processor/db/column/arrangement_overlay_unittest.cc b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
index 07f13c0..3a26f0c 100644
--- a/src/trace_processor/db/column/arrangement_overlay_unittest.cc
+++ b/src/trace_processor/db/column/arrangement_overlay_unittest.cc
@@ -18,6 +18,7 @@
#include <array>
#include <cstdint>
+#include <utility>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
@@ -35,6 +36,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(ArrangementOverlay, SingleSearch) {
std::vector<uint32_t> arrangement{1, 1, 2, 2, 3, 3, 4, 4, 1, 1};
auto fake = FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2});
@@ -97,13 +101,10 @@
ArrangementOverlay storage(&arrangement, Indices::State::kNonmonotonic);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{7u, 1u, 3u};
- RangeOrBitVector res = chain->IndexSearch(
- FilterOp::kGe, SqlValue::Long(0u),
- Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
-
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1u));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {7u, 1u, 3u}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
}
TEST(ArrangementOverlay, OrderingSearch) {
@@ -116,7 +117,6 @@
RangeOrBitVector res =
chain->Search(FilterOp::kGe, SqlValue::Long(0u), Range(0, 5));
-
ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
}
diff --git a/src/trace_processor/db/column/data_layer.cc b/src/trace_processor/db/column/data_layer.cc
index c8f8b68..634cbce 100644
--- a/src/trace_processor/db/column/data_layer.cc
+++ b/src/trace_processor/db/column/data_layer.cc
@@ -113,8 +113,9 @@
PERFETTO_FATAL("For GCC");
}
-ArrangementOverlay::ArrangementOverlay(const std::vector<uint32_t>* arrangement,
- Indices::State arrangement_state)
+ArrangementOverlay::ArrangementOverlay(
+ const std::vector<uint32_t>* arrangement,
+ DataLayerChain::Indices::State arrangement_state)
: DataLayer(Impl::kArrangement),
arrangement_(arrangement),
arrangement_state_(arrangement_state) {}
diff --git a/src/trace_processor/db/column/data_layer.h b/src/trace_processor/db/column/data_layer.h
index f43999c..c8d74a8 100644
--- a/src/trace_processor/db/column/data_layer.h
+++ b/src/trace_processor/db/column/data_layer.h
@@ -20,6 +20,8 @@
#include <cstdint>
#include <memory>
#include <string>
+#include <utility>
+#include <vector>
#include "perfetto/base/compiler.h"
#include "perfetto/base/logging.h"
@@ -107,6 +109,62 @@
};
using StorageProto = protos::pbzero::SerializedColumn_Storage;
+ // Index vector related data required to Filter using IndexSearch.
+ struct Indices {
+ enum class State {
+ // We can't guarantee that data is in monotonic order.
+ kNonmonotonic,
+ // Data is in monotonic order.
+ kMonotonic,
+ };
+ // Contains an index to an element in the chain and an opaque payload class
+ // which can be set to whatever the user of the chain requires.
+ struct Token {
+ // An index pointing to an element in this chain. Indicates the element
+ // at this index should be filtered.
+ uint32_t index;
+
+ // An opaque value which can be set to some value meaningful to the
+ // caller. While the exact meaning of |payload| should not be depended
+ // upon, implementations are free to make assumptions that |payload| will
+ // be strictly monotonic.
+ uint32_t payload;
+
+ struct PayloadComparator {
+ bool operator()(const Token& a, const Token& b) {
+ return a.payload < b.payload;
+ }
+ };
+ };
+ static Indices Create(const std::vector<uint32_t>& raw, State state) {
+ std::vector<Token> tokens;
+ tokens.reserve(tokens.size());
+ for (uint32_t r : raw) {
+ tokens.push_back(Token{r, r});
+ }
+ return Indices{std::move(tokens), state};
+ }
+ static Indices CreateWithIndexPayloadForTesting(
+ const std::vector<uint32_t>& raw,
+ State state) {
+ std::vector<Token> tokens;
+ tokens.reserve(tokens.size());
+ for (uint32_t i = 0; i < raw.size(); ++i) {
+ tokens.push_back(Token{raw[i], i});
+ }
+ return Indices{std::move(tokens), state};
+ }
+ std::vector<Token> tokens;
+ State state = State::kNonmonotonic;
+ };
+
+ // Index vector related data required to Filter using IndexSearch.
+ struct OrderedIndices {
+ const uint32_t* data = nullptr;
+ uint32_t size = 0;
+ Indices::State state = Indices::State::kNonmonotonic;
+ };
+
virtual ~DataLayerChain();
// Start of public API.
@@ -138,6 +196,7 @@
PERFETTO_ALWAYS_INLINE RangeOrBitVector Search(FilterOp op,
SqlValue value,
Range range) const {
+ PERFETTO_DCHECK(range.end <= size());
switch (ValidateSearchConstraints(op, value)) {
case SearchValidationResult::kAllData:
return RangeOrBitVector(range);
@@ -163,24 +222,27 @@
// Notes for implementors:
// * Implementations should ensure that, if they return a BitVector, it is
// precisely of size |indices_count|.
- PERFETTO_ALWAYS_INLINE RangeOrBitVector IndexSearch(FilterOp op,
- SqlValue value,
- Indices indices) const {
+ PERFETTO_ALWAYS_INLINE void IndexSearch(FilterOp op,
+ SqlValue value,
+ Indices& indices) const {
switch (ValidateSearchConstraints(op, value)) {
case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
+ return;
case SearchValidationResult::kNoData:
- return RangeOrBitVector(Range());
+ indices.tokens.clear();
+ return;
case SearchValidationResult::kOk:
- return IndexSearchValidated(op, value, indices);
+ IndexSearchValidated(op, value, indices);
+ return;
}
PERFETTO_FATAL("For GCC");
}
// Searches for elements which match |op| and |value| at the positions given
- // by indices data.
+ // by OrderedIndicesdata.
//
- // Returns a Range into Indices data of indices that pass the constraint.
+ // Returns a Range into OrderedIndicesdata of OrderedIndicesthat pass the
+ // constraint.
//
// Notes for callers:
// * Should not be called on:
@@ -190,9 +252,10 @@
// result.
// * Callers should note that the return value of this function corresponds
// to positions in |indices| *not* positions in the storage.
- PERFETTO_ALWAYS_INLINE Range OrderedIndexSearch(FilterOp op,
- SqlValue value,
- Indices indices) const {
+ PERFETTO_ALWAYS_INLINE Range
+ OrderedIndexSearch(FilterOp op,
+ SqlValue value,
+ const OrderedIndices& indices) const {
switch (ValidateSearchConstraints(op, value)) {
case SearchValidationResult::kAllData:
return {0, indices.size};
@@ -254,15 +317,13 @@
// Post-validated implementation of |IndexSearch|. See |IndexSearch|'s
// documentation.
- virtual RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const = 0;
+ virtual void IndexSearchValidated(FilterOp, SqlValue, Indices&) const = 0;
// Post-validated implementation of |OrderedIndexSearch|. See
// |OrderedIndexSearch|'s documentation.
virtual Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const = 0;
+ const OrderedIndices&) 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 970eb0f..e171ec0 100644
--- a/src/trace_processor/db/column/dense_null_overlay.cc
+++ b/src/trace_processor/db/column/dense_null_overlay.cc
@@ -21,6 +21,7 @@
#include <iterator>
#include <memory>
#include <utility>
+#include <vector>
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
@@ -135,84 +136,68 @@
return RangeOrBitVector(std::move(res));
}
-RangeOrBitVector DenseNullOverlay::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+void DenseNullOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB,
"DenseNullOverlay::ChainImpl::IndexSearch");
if (op == FilterOp::kIsNull) {
+ // Partition the vector into all the null indices followed by all the
+ // non-null indices.
+ auto non_null_it = std::stable_partition(
+ indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& t) { return !non_null_->IsSet(t.index); });
+
+ // IndexSearch |inner_| with a vector containing a copy of the non-null
+ // indices.
+ Indices non_null{{non_null_it, indices.tokens.end()}, indices.state};
+ inner_->IndexSearch(op, sql_val, non_null);
+
+ // Replace all the original non-null positions with the result from calling
+ // IndexSearch.
+ auto new_non_null_it =
+ indices.tokens.erase(non_null_it, indices.tokens.end());
+ indices.tokens.insert(new_non_null_it, non_null.tokens.begin(),
+ non_null.tokens.end());
+
+ // Merge the two sorted index ranges together using the payload as the
+ // comparator. This is a required post-condition of IndexSearch.
+ std::inplace_merge(indices.tokens.begin(), new_non_null_it,
+ indices.tokens.end(),
+ Indices::Token::PayloadComparator());
+ return;
+ }
+
+ auto keep_only_non_null = [this, &indices]() {
+ indices.tokens.erase(
+ std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& idx) {
+ return !non_null_->IsSet(idx.index);
+ }),
+ indices.tokens.end());
+ return;
+ };
+ if (op == FilterOp::kIsNotNull) {
switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData: {
- BitVector::Builder null_indices(indices.size);
- for (const uint32_t* it = indices.data;
- it != indices.data + indices.size; it++) {
- null_indices.Append(!non_null_->IsSet(*it));
- }
- // There is no need to search in underlying storage. We should just
- // check if the index is set in |non_null_|.
- return RangeOrBitVector(std::move(null_indices).Build());
- }
+ case SearchValidationResult::kNoData:
+ indices.tokens.clear();
+ return;
case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
- case SearchValidationResult::kOk:
- break;
- }
- } else if (op == FilterOp::kIsNotNull) {
- switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData: {
- BitVector::Builder non_null_indices(indices.size);
- for (const uint32_t* it = indices.data;
- it != indices.data + indices.size; it++) {
- non_null_indices.Append(non_null_->IsSet(*it));
- }
- // There is no need to search in underlying storage. We should just
- // check if the index is set in |non_null_|.
- return RangeOrBitVector(std::move(non_null_indices).Build());
- }
- case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
+ keep_only_non_null();
+ return;
case SearchValidationResult::kOk:
break;
}
}
-
- RangeOrBitVector inner_res =
- inner_->IndexSearchValidated(op, sql_val, indices);
- if (inner_res.IsRange()) {
- Range inner_range = std::move(inner_res).TakeIfRange();
- BitVector::Builder builder(indices.size, inner_range.start);
- for (uint32_t i = inner_range.start; i < inner_range.end; ++i) {
- builder.Append(non_null_->IsSet(indices.data[i]));
- }
- return RangeOrBitVector(std::move(builder).Build());
- }
-
- BitVector::Builder builder(indices.size);
- for (uint32_t i = 0; i < indices.size; ++i) {
- builder.Append(non_null_->IsSet(indices.data[i]));
- }
- BitVector non_null = std::move(builder).Build();
-
- BitVector res = std::move(inner_res).TakeIfBitVector();
-
- if (op == FilterOp::kIsNull) {
- BitVector null = std::move(non_null);
- null.Not();
- res.Or(null);
- } else {
- res.And(non_null);
- }
-
- PERFETTO_DCHECK(res.size() == indices.size);
- return RangeOrBitVector(std::move(res));
+ keep_only_non_null();
+ inner_->IndexSearchValidated(op, sql_val, indices);
}
Range DenseNullOverlay::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ const OrderedIndices& indices) const {
// For NOT EQUAL the further analysis needs to be done by the caller.
PERFETTO_CHECK(op != FilterOp::kNe);
@@ -247,7 +232,8 @@
Range inner_range = inner_->OrderedIndexSearchValidated(
op, sql_val,
- Indices{first_non_null, non_null_size, Indices::State::kNonmonotonic});
+ OrderedIndices{first_non_null, non_null_size,
+ Indices::State::kNonmonotonic});
return {inner_range.start + non_null_offset,
inner_range.end + non_null_offset};
}
diff --git a/src/trace_processor/db/column/dense_null_overlay.h b/src/trace_processor/db/column/dense_null_overlay.h
index 0f881fb..b27beb5 100644
--- a/src/trace_processor/db/column/dense_null_overlay.h
+++ b/src/trace_processor/db/column/dense_null_overlay.h
@@ -54,13 +54,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
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 0cf6276..efda157 100644
--- a/src/trace_processor/db/column/dense_null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/dense_null_overlay_unittest.cc
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <utility>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
@@ -35,6 +36,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(DenseNullOverlay, NoFilteringSearch) {
std::vector<uint32_t> data{0, 1, 0, 1, 0};
auto numeric = std::make_unique<NumericStorage<uint32_t>>(
@@ -103,12 +107,10 @@
DenseNullOverlay storage(&bv);
auto chain = storage.MakeChain(numeric->MakeChain());
- std::vector<uint32_t> index({5, 2, 3, 4, 1});
- auto res = chain->IndexSearch(
- FilterOp::kGe, SqlValue::Long(0),
- Indices{index.data(), static_cast<uint32_t>(index.size()),
- Indices::State::kNonmonotonic});
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2, 3));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
}
TEST(DenseNullOverlay, IsNullIndexSearch) {
@@ -118,12 +120,11 @@
DenseNullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> index({5, 2, 3, 4, 1});
- auto res = chain->IndexSearch(
- FilterOp::kIsNull, SqlValue(),
- Indices{index.data(), static_cast<uint32_t>(index.size()),
- Indices::State::kMonotonic});
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3));
}
TEST(DenseNullOverlay, OrderedIndexSearch) {
@@ -134,7 +135,7 @@
auto chain = storage.MakeChain(std::move(fake));
std::vector<uint32_t> indices_vec({0, 2, 4, 1, 3, 5});
- Indices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
+ OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
Range res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
diff --git a/src/trace_processor/db/column/dummy_storage.cc b/src/trace_processor/db/column/dummy_storage.cc
index 54d7c61..27b464f 100644
--- a/src/trace_processor/db/column/dummy_storage.cc
+++ b/src/trace_processor/db/column/dummy_storage.cc
@@ -43,15 +43,16 @@
PERFETTO_FATAL("Shouldn't be called");
}
-RangeOrBitVector DummyStorage::ChainImpl::IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const {
+void DummyStorage::ChainImpl::IndexSearchValidated(FilterOp,
+ SqlValue,
+ Indices&) const {
PERFETTO_FATAL("Shouldn't be called");
}
-Range DummyStorage::ChainImpl::OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const {
+Range DummyStorage::ChainImpl::OrderedIndexSearchValidated(
+ FilterOp,
+ SqlValue,
+ const OrderedIndices&) 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 ced41a9..80674bb 100644
--- a/src/trace_processor/db/column/dummy_storage.h
+++ b/src/trace_processor/db/column/dummy_storage.h
@@ -43,13 +43,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/fake_storage.cc b/src/trace_processor/db/column/fake_storage.cc
index 9fbc3ae..f587c77 100644
--- a/src/trace_processor/db/column/fake_storage.cc
+++ b/src/trace_processor/db/column/fake_storage.cc
@@ -82,32 +82,39 @@
PERFETTO_FATAL("For GCC");
}
-RangeOrBitVector FakeStorageChain::IndexSearchValidated(FilterOp,
- SqlValue,
- Indices indices) const {
+void FakeStorageChain::IndexSearchValidated(FilterOp,
+ SqlValue,
+ Indices& indices) const {
switch (strategy_) {
case kAll:
- return RangeOrBitVector(Range(0, indices.size));
+ return;
case kNone:
- return RangeOrBitVector(Range());
+ indices.tokens.clear();
+ return;
case kRange:
- case kBitVector: {
- BitVector::Builder builder(indices.size);
- for (const uint32_t* it = indices.data; it != indices.data + indices.size;
- ++it) {
- bool in_range = strategy_ == kRange && range_.Contains(*it);
- bool in_bv = strategy_ == kBitVector && bit_vector_.IsSet(*it);
- builder.Append(in_range || in_bv);
- }
- return RangeOrBitVector(std::move(builder).Build());
- }
+ indices.tokens.erase(
+ std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& token) {
+ return !range_.Contains(token.index);
+ }),
+ indices.tokens.end());
+ return;
+ case kBitVector:
+ indices.tokens.erase(
+ std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& token) {
+ return !bit_vector_.IsSet(token.index);
+ }),
+ indices.tokens.end());
+ return;
}
PERFETTO_FATAL("For GCC");
}
-Range FakeStorageChain::OrderedIndexSearchValidated(FilterOp,
- SqlValue,
- Indices indices) const {
+Range FakeStorageChain::OrderedIndexSearchValidated(
+ FilterOp,
+ SqlValue,
+ const OrderedIndices& indices) const {
if (strategy_ == kAll) {
return {0, indices.size};
}
diff --git a/src/trace_processor/db/column/fake_storage.h b/src/trace_processor/db/column/fake_storage.h
index aca6890..bc02300 100644
--- a/src/trace_processor/db/column/fake_storage.h
+++ b/src/trace_processor/db/column/fake_storage.h
@@ -82,11 +82,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
- Range OrderedIndexSearchValidated(FilterOp, SqlValue, Indices) const override;
+ Range OrderedIndexSearchValidated(FilterOp,
+ SqlValue,
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/id_storage.cc b/src/trace_processor/db/column/id_storage.cc
index df662af..e3f4d8a 100644
--- a/src/trace_processor/db/column/id_storage.cc
+++ b/src/trace_processor/db/column/id_storage.cc
@@ -21,7 +21,6 @@
#include <functional>
#include <iterator>
#include <limits>
-#include <memory>
#include <string>
#include <utility>
@@ -41,40 +40,13 @@
namespace {
template <typename Comparator>
-RangeOrBitVector IndexSearchWithComparator(uint32_t val,
- const uint32_t* indices,
- uint32_t indices_size,
- Comparator comparator) {
- // Slow path: we compare <64 elements and append to get us to a word
- // boundary.
- const uint32_t* ptr = indices;
- BitVector::Builder builder(indices_size);
- uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
- for (uint32_t i = 0; i < front_elements; ++i) {
- builder.Append(comparator(ptr[i], val));
- }
- ptr += front_elements;
-
- // Fast path: we compare as many groups of 64 elements as we can.
- // This should be very easy for the compiler to auto-vectorize.
- uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
- for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
- uint64_t word = 0;
- // This part should be optimised by SIMD and is expected to be fast.
- for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k) {
- bool comp_result = comparator(ptr[i + k], val);
- word |= static_cast<uint64_t>(comp_result) << k;
- }
- builder.AppendWord(word);
- }
- ptr += fast_path_elements;
-
- // Slow path: we compare <64 elements and append to fill the Builder.
- uint32_t back_elements = builder.BitsUntilFull();
- for (uint32_t i = 0; i < back_elements; ++i) {
- builder.Append(comparator(ptr[i], val));
- }
- return RangeOrBitVector(std::move(builder).Build());
+void IndexSearchWithComparator(uint32_t val, DataLayerChain::Indices& indices) {
+ indices.tokens.erase(
+ std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [val](const DataLayerChain::Indices::Token& idx) {
+ return !Comparator()(idx.index, val);
+ }),
+ indices.tokens.end());
}
} // namespace
@@ -226,14 +198,13 @@
return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
-RangeOrBitVector IdStorage::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+void IdStorage::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(
metatrace::Category::DB, "IdStorage::ChainImpl::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
+ [&indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.tokens.size()));
r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
});
@@ -241,35 +212,30 @@
// requires special logic.
if (sql_val.type == SqlValue::kDouble) {
switch (utils::CompareIntColumnWithDouble(op, &sql_val)) {
+ case SearchValidationResult::kAllData:
+ return;
+ case SearchValidationResult::kNoData:
+ indices.tokens.clear();
+ return;
case SearchValidationResult::kOk:
break;
- case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
- case SearchValidationResult::kNoData:
- return RangeOrBitVector(Range());
}
}
auto val = static_cast<uint32_t>(sql_val.AsLong());
switch (op) {
case FilterOp::kEq:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::equal_to<>());
+ return IndexSearchWithComparator<std::equal_to<>>(val, indices);
case FilterOp::kNe:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::not_equal_to<>());
+ return IndexSearchWithComparator<std::not_equal_to<>>(val, indices);
case FilterOp::kLe:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::less_equal<>());
+ return IndexSearchWithComparator<std::less_equal<>>(val, indices);
case FilterOp::kLt:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::less<>());
+ return IndexSearchWithComparator<std::less<>>(val, indices);
case FilterOp::kGt:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::greater<>());
+ return IndexSearchWithComparator<std::greater<>>(val, indices);
case FilterOp::kGe:
- return IndexSearchWithComparator(val, indices.data, indices.size,
- std::greater_equal<>());
+ return IndexSearchWithComparator<std::greater_equal<>>(val, indices);
case FilterOp::kIsNotNull:
case FilterOp::kIsNull:
case FilterOp::kGlob:
@@ -279,9 +245,10 @@
PERFETTO_FATAL("FilterOp not matched");
}
-Range IdStorage::ChainImpl::OrderedIndexSearchValidated(FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+Range IdStorage::ChainImpl::OrderedIndexSearchValidated(
+ FilterOp op,
+ SqlValue sql_val,
+ const OrderedIndices& indices) const {
PERFETTO_DCHECK(op != FilterOp::kNe);
PERFETTO_TP_TRACE(
@@ -305,10 +272,9 @@
}
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.
+ // 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);
diff --git a/src/trace_processor/db/column/id_storage.h b/src/trace_processor/db/column/id_storage.h
index e6e25ab..51b9f0d 100644
--- a/src/trace_processor/db/column/id_storage.h
+++ b/src/trace_processor/db/column/id_storage.h
@@ -53,13 +53,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/id_storage_unittest.cc b/src/trace_processor/db/column/id_storage_unittest.cc
index 48ce18e..2d6fd44 100644
--- a/src/trace_processor/db/column/id_storage_unittest.cc
+++ b/src/trace_processor/db/column/id_storage_unittest.cc
@@ -42,6 +42,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(IdStorage, InvalidSearchConstraints) {
IdStorage storage;
auto chain = storage.MakeChain();
@@ -214,32 +217,35 @@
IdStorage storage;
auto chain = storage.MakeChain();
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 = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
+ auto common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {5, 4, 3, 9, 8, 7}, Indices::State::kNonmonotonic);
- op = FilterOp::kNe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
- op = FilterOp::kLe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(1, 2, 3, 4, 5));
- op = FilterOp::kLt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
- op = FilterOp::kGe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2));
- op = FilterOp::kGt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 3, 4, 5));
+
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
}
TEST(IdStorage, OrderedIndexSearch) {
@@ -247,7 +253,7 @@
auto chain = storage.MakeChain();
std::vector<uint32_t> indices_vec{0, 1, 2, 4, 4};
- Indices indices{indices_vec.data(), 5, Indices::State::kMonotonic};
+ OrderedIndices indices{indices_vec.data(), 5, Indices::State::kMonotonic};
Range range =
chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
@@ -274,17 +280,11 @@
TEST(IdStorage, IndexSearchEqTooBig) {
IdStorage storage;
auto chain = storage.MakeChain();
- std::vector<uint32_t> indices{1, 3, 5, 7, 9, 11, 2, 4};
- BitVector bv =
- chain
- ->IndexSearch(
- FilterOp::kEq, SqlValue::Long(20),
- Indices{indices.data(), static_cast<uint32_t>(indices.size()),
- Indices::State::kMonotonic})
- .TakeIfBitVector();
-
- ASSERT_EQ(bv.CountSetBits(), 0u);
+ auto indices = Indices::CreateWithIndexPayloadForTesting(
+ {1, 3, 5, 7, 9, 11, 2, 4}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kEq, SqlValue::Long(20), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
}
TEST(IdStorage, SearchWithIdAsDoubleSimple) {
diff --git a/src/trace_processor/db/column/null_overlay.cc b/src/trace_processor/db/column/null_overlay.cc
index 8634eb6..fa1e679 100644
--- a/src/trace_processor/db/column/null_overlay.cc
+++ b/src/trace_processor/db/column/null_overlay.cc
@@ -162,76 +162,74 @@
return RangeOrBitVector(std::move(res));
}
-RangeOrBitVector NullOverlay::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+void NullOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB,
"NullOverlay::ChainImpl::IndexSearch");
if (op == FilterOp::kIsNull) {
- switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData: {
- BitVector::Builder null_indices(indices.size);
- for (const uint32_t* it = indices.data;
- it != indices.data + indices.size; it++) {
- null_indices.Append(!non_null_->IsSet(*it));
- }
- // There is no need to search in underlying storage. We should just
- // check if the index is set in |non_null_|.
- return RangeOrBitVector(std::move(null_indices).Build());
- }
- case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
- case SearchValidationResult::kOk:
- break;
+ // Partition the vector into all the null indices followed by all the
+ // non-null indices.
+ auto non_null_it = std::stable_partition(
+ indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& t) { return !non_null_->IsSet(t.index); });
+
+ // IndexSearch |inner_| with a vector containing a copy of the (translated)
+ // non-null indices.
+ Indices non_null{{non_null_it, indices.tokens.end()}, indices.state};
+ for (auto& token : non_null.tokens) {
+ token.index = non_null_->CountSetBits(token.index);
}
- } else if (op == FilterOp::kIsNotNull) {
+ inner_->IndexSearch(op, sql_val, non_null);
+
+ // Replace all the original non-null positions with the result from calling
+ // IndexSearch.
+ auto new_non_null_it =
+ indices.tokens.erase(non_null_it, indices.tokens.end());
+ indices.tokens.insert(new_non_null_it, non_null.tokens.begin(),
+ non_null.tokens.end());
+
+ // Merge the two sorted index ranges together using the payload as the
+ // comparator. This is a required post-condition of IndexSearch.
+ std::inplace_merge(indices.tokens.begin(), new_non_null_it,
+ indices.tokens.end(),
+ Indices::Token::PayloadComparator());
+ return;
+ }
+
+ auto keep_only_non_null = [this, &indices]() {
+ indices.tokens.erase(
+ std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [this](const Indices::Token& idx) {
+ return !non_null_->IsSet(idx.index);
+ }),
+ indices.tokens.end());
+ return;
+ };
+ if (op == FilterOp::kIsNotNull) {
switch (inner_->ValidateSearchConstraints(op, sql_val)) {
- case SearchValidationResult::kNoData: {
- BitVector::Builder non_null_indices(indices.size);
- for (const uint32_t* it = indices.data;
- it != indices.data + indices.size; it++) {
- non_null_indices.Append(non_null_->IsSet(*it));
- }
- // There is no need to search in underlying storage. We should just
- // check if the index is set in |non_null_|.
- return RangeOrBitVector(std::move(non_null_indices).Build());
- }
+ case SearchValidationResult::kNoData:
+ indices.tokens.clear();
+ return;
case SearchValidationResult::kAllData:
- return RangeOrBitVector(Range(0, indices.size));
+ keep_only_non_null();
+ return;
case SearchValidationResult::kOk:
break;
}
}
-
- BitVector::Builder storage_non_null(indices.size);
- std::vector<uint32_t> storage_iv;
- storage_iv.reserve(indices.size);
- for (const uint32_t* it = indices.data; it != indices.data + indices.size;
- it++) {
- bool is_non_null = non_null_->IsSet(*it);
- if (is_non_null) {
- storage_iv.push_back(non_null_->CountSetBits(*it));
- }
- storage_non_null.Append(is_non_null);
+ keep_only_non_null();
+ for (auto& token : indices.tokens) {
+ token.index = non_null_->CountSetBits(token.index);
}
- RangeOrBitVector range_or_bv = inner_->IndexSearchValidated(
- op, sql_val,
- Indices{storage_iv.data(), static_cast<uint32_t>(storage_iv.size()),
- indices.state});
- BitVector res =
- ReconcileStorageResult(op, std::move(storage_non_null).Build(),
- std::move(range_or_bv), Range(0, indices.size));
-
- PERFETTO_DCHECK(res.size() == indices.size);
- return RangeOrBitVector(std::move(res));
+ inner_->IndexSearchValidated(op, sql_val, indices);
}
Range NullOverlay::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ 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);
@@ -272,7 +270,8 @@
}
Range inner_range = inner_->OrderedIndexSearchValidated(
- op, sql_val, Indices{storage_iv.data(), non_null_size, indices.state});
+ 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};
}
diff --git a/src/trace_processor/db/column/null_overlay.h b/src/trace_processor/db/column/null_overlay.h
index 99f6256..625959d 100644
--- a/src/trace_processor/db/column/null_overlay.h
+++ b/src/trace_processor/db/column/null_overlay.h
@@ -53,13 +53,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/null_overlay_unittest.cc b/src/trace_processor/db/column/null_overlay_unittest.cc
index ceb6c9f..8f15746 100644
--- a/src/trace_processor/db/column/null_overlay_unittest.cc
+++ b/src/trace_processor/db/column/null_overlay_unittest.cc
@@ -18,6 +18,7 @@
#include <cstdint>
#include <memory>
+#include <utility>
#include <vector>
#include "perfetto/trace_processor/basic_types.h"
@@ -35,6 +36,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(NullOverlay, SingleSearch) {
BitVector bv{0, 1, 0, 1, 1, 1};
auto fake = FakeStorageChain::SearchSubset(4, std::vector<uint32_t>{1, 2});
@@ -139,12 +143,10 @@
NullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{1, 5, 2};
- auto res =
- chain->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));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {1, 5, 2}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
}
TEST(NullOverlay, IndexSearchPartialElements) {
@@ -153,12 +155,10 @@
NullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{1, 4, 2};
- auto res =
- chain->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));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {1, 4, 2}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
}
TEST(NullOverlay, IndexSearchIsNullOpEmptyRes) {
@@ -167,12 +167,10 @@
NullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{0, 3, 5, 4, 2};
- auto res =
- chain->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));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 3, 5, 4, 2}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 3));
}
TEST(NullOverlay, IndexSearchIsNullOp) {
@@ -181,12 +179,11 @@
NullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{0, 3, 2, 4, 5};
- auto res =
- chain->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));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 3, 2, 4, 5}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 3, 4));
}
TEST(NullOverlay, IndexSearchIsNotNullOp) {
@@ -195,12 +192,10 @@
NullOverlay storage(&bv);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{0, 3, 4};
- auto res =
- chain->IndexSearch(FilterOp::kIsNotNull, SqlValue(),
- Indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic});
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 3, 4}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
}
TEST(NullOverlay, OrderedIndexSearch) {
@@ -214,8 +209,8 @@
// Passing values on final data
// NULL, NULL, 0, 1, 1
std::vector<uint32_t> table_idx{0, 4, 5, 1, 3};
- Indices indices{table_idx.data(), uint32_t(table_idx.size()),
- Indices::State::kNonmonotonic};
+ OrderedIndices indices{table_idx.data(), uint32_t(table_idx.size()),
+ Indices::State::kNonmonotonic};
Range res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
diff --git a/src/trace_processor/db/column/numeric_storage.cc b/src/trace_processor/db/column/numeric_storage.cc
index 2c16edd..46ab450 100644
--- a/src/trace_processor/db/column/numeric_storage.cc
+++ b/src/trace_processor/db/column/numeric_storage.cc
@@ -43,6 +43,9 @@
namespace perfetto::trace_processor::column {
namespace {
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
// Using the fact that binary operators in std are operators() of classes, we
@@ -135,7 +138,9 @@
}
template <typename T>
-uint32_t TypedLowerBoundExtrinsic(T val, const T* data, Indices indices) {
+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; });
@@ -144,7 +149,7 @@
uint32_t LowerBoundExtrinsic(const void* vector_ptr,
NumericValue val,
- Indices indices) {
+ 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();
@@ -170,7 +175,7 @@
uint32_t UpperBoundExtrinsic(const void* vector_ptr,
NumericValue val,
- Indices indices) {
+ OrderedIndices indices) {
return std::visit(
[vector_ptr, indices](auto val_data) {
using T = decltype(val_data);
@@ -458,49 +463,51 @@
return RangeOrBitVector(LinearSearchInternal(op, val, search_range));
}
-RangeOrBitVector NumericStorageBase::ChainImpl::IndexSearchValidated(
+void NumericStorageBase::ChainImpl::IndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
- PERFETTO_DCHECK(*std::max_element(indices.data, indices.data + indices.size) <
- size());
-
+ Indices& indices) const {
PERFETTO_TP_TRACE(
metatrace::Category::DB, "NumericStorage::ChainImpl::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
+ [&indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.tokens.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) {
- auto ret_opt =
- utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), indices.size);
- if (ret_opt) {
- return RangeOrBitVector(*ret_opt);
+ if (utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), indices)) {
+ return;
}
}
// Mismatched types - column is double and value is int.
if (sql_val.type != SqlValue::kDouble &&
storage_type_ == ColumnType::kDouble) {
- auto ret_opt =
- utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), indices.size);
- if (ret_opt) {
- return RangeOrBitVector(*ret_opt);
+ if (utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), indices)) {
+ return;
}
}
NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
- return RangeOrBitVector(
- IndexSearchInternal(op, val, indices.data, indices.size));
+ std::visit(
+ [this, &indices, op](auto val) {
+ using T = decltype(val);
+ auto* start = static_cast<const std::vector<T>*>(vector_ptr_)->data();
+ std::visit(
+ [start, &indices, val](auto comparator) {
+ utils::IndexSearchWithComparator(val, start, indices, comparator);
+ },
+ GetFilterOpVariant<T>(op));
+ },
+ val);
}
Range NumericStorageBase::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ const OrderedIndices& indices) const {
PERFETTO_DCHECK(*std::max_element(indices.data, indices.data + indices.size) <
size());
@@ -604,27 +611,6 @@
return std::move(builder).Build();
}
-BitVector NumericStorageBase::ChainImpl::IndexSearchInternal(
- FilterOp op,
- NumericValue val,
- const uint32_t* indices,
- uint32_t indices_count) const {
- BitVector::Builder builder(indices_count);
- std::visit(
- [this, indices, op, &builder](auto val) {
- using T = decltype(val);
- auto* start = static_cast<const std::vector<T>*>(vector_ptr_)->data();
- std::visit(
- [start, indices, val, &builder](auto comparator) {
- utils::IndexSearchWithComparator(val, start, indices, comparator,
- builder);
- },
- GetFilterOpVariant<T>(op));
- },
- val);
- return std::move(builder).Build();
-}
-
Range NumericStorageBase::ChainImpl::BinarySearchIntrinsic(
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 2dfafc6..f7cb51c 100644
--- a/src/trace_processor/db/column/numeric_storage.h
+++ b/src/trace_processor/db/column/numeric_storage.h
@@ -42,13 +42,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void Serialize(StorageProto*) const override;
@@ -63,11 +61,6 @@
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;
diff --git a/src/trace_processor/db/column/numeric_storage_unittest.cc b/src/trace_processor/db/column/numeric_storage_unittest.cc
index 534338c..2b20306 100644
--- a/src/trace_processor/db/column/numeric_storage_unittest.cc
+++ b/src/trace_processor/db/column/numeric_storage_unittest.cc
@@ -42,6 +42,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(NumericStorage, InvalidSearchConstraintsGeneralChecks) {
std::vector<uint32_t> data_vec(128);
std::iota(data_vec.begin(), data_vec.end(), 0);
@@ -244,27 +247,36 @@
auto chain = storage.MakeChain();
// -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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Long(3);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 5));
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 5));
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
}
TEST(NumericStorage, IndexSearchCompareWithNegative) {
@@ -273,27 +285,35 @@
auto chain = storage.MakeChain();
// -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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Long(-3);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2));
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 3, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(1, 2, 3, 4, 5));
}
TEST(NumericStorage, SearchFast) {
@@ -348,8 +368,8 @@
TEST(NumericStorage, OrderedIndexSearch) {
std::vector<uint32_t> data_vec{30, 40, 50, 60, 90, 80, 70, 0, 10, 20};
std::vector<uint32_t> sorted_order_vec{7, 8, 9, 0, 1, 2, 3, 6, 5, 4};
- Indices sorted_order{sorted_order_vec.data(), 10,
- Indices::State::kNonmonotonic};
+ OrderedIndices sorted_order{sorted_order_vec.data(), 10,
+ Indices::State::kNonmonotonic};
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, false);
auto chain = storage.MakeChain();
@@ -417,27 +437,36 @@
auto chain = storage.MakeChain();
// -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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Double(3);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 5));
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 5));
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
}
TEST(NumericStorage, SearchInt32WithDouble) {
@@ -498,27 +527,36 @@
auto chain = storage.MakeChain();
// -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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Double(1.5);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 5));
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 5));
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
}
TEST(NumericStorage, IndexSearchInt32WithNegDouble) {
@@ -527,27 +565,34 @@
auto chain = storage.MakeChain();
// -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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Double(-2.5);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
}
TEST(NumericStorage, SearchUint32WithNegDouble) {
@@ -581,27 +626,36 @@
NumericStorage<uint32_t> storage(&data_vec, ColumnType::kInt32, false);
auto chain = storage.MakeChain();
- std::vector<uint32_t> indices_vec{0, 4, 4, 5, 1, 6};
- Indices indices{indices_vec.data(), 6, Indices::State::kMonotonic};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
SqlValue val = SqlValue::Double(-2.5);
- auto res = chain->IndexSearch(FilterOp::kEq, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
- res = chain->IndexSearch(FilterOp::kNe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 4, 5));
- res = chain->IndexSearch(FilterOp::kLt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
- res = chain->IndexSearch(FilterOp::kLe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
- res = chain->IndexSearch(FilterOp::kGt, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 4, 5));
- res = chain->IndexSearch(FilterOp::kGe, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 3, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 3, 4, 5));
}
TEST(NumericStorage, DoubleColumnWithIntThatCantBeRepresentedAsDouble) {
diff --git a/src/trace_processor/db/column/range_overlay.cc b/src/trace_processor/db/column/range_overlay.cc
index 338c989..84f19ce 100644
--- a/src/trace_processor/db/column/range_overlay.cc
+++ b/src/trace_processor/db/column/range_overlay.cc
@@ -108,34 +108,30 @@
return RangeOrBitVector(std::move(builder).Build());
}
-RangeOrBitVector RangeOverlay::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+void RangeOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::IndexSearch");
-
- std::vector<uint32_t> storage_iv(indices.size);
- // Should be SIMD optimized.
- for (uint32_t i = 0; i < indices.size; ++i) {
- storage_iv[i] = indices.data[i] + range_->start;
+ for (auto& token : indices.tokens) {
+ token.index += range_->start;
}
- return inner_->IndexSearchValidated(
- op, sql_val, Indices{storage_iv.data(), indices.size, indices.state});
+ inner_->IndexSearchValidated(op, sql_val, indices);
}
Range RangeOverlay::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ const OrderedIndices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "RangeOverlay::IndexSearch");
- std::vector<uint32_t> storage_iv(indices.size);
// 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, Indices{storage_iv.data(), indices.size, indices.state});
+ op, sql_val,
+ OrderedIndices{storage_iv.data(), indices.size, indices.state});
}
void RangeOverlay::ChainImpl::StableSort(SortToken* start,
diff --git a/src/trace_processor/db/column/range_overlay.h b/src/trace_processor/db/column/range_overlay.h
index 200d5d4..3adb319 100644
--- a/src/trace_processor/db/column/range_overlay.h
+++ b/src/trace_processor/db/column/range_overlay.h
@@ -50,13 +50,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp p,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp p, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/range_overlay_unittest.cc b/src/trace_processor/db/column/range_overlay_unittest.cc
index 96c2f80..a965be3 100644
--- a/src/trace_processor/db/column/range_overlay_unittest.cc
+++ b/src/trace_processor/db/column/range_overlay_unittest.cc
@@ -35,6 +35,9 @@
using testing::IsEmpty;
using Range = Range;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(RangeOverlay, SearchSingle) {
Range range(3, 8);
RangeOverlay storage(&range);
@@ -96,12 +99,10 @@
RangeOverlay storage(&range);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{1u, 0u, 3u};
- RangeOrBitVector res = chain->IndexSearch(
- FilterOp::kGe, SqlValue::Long(0u),
- Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1u));
+ Indices indices = Indices::CreateWithIndexPayloadForTesting(
+ {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
}
TEST(RangeOverlay, StableSort) {
diff --git a/src/trace_processor/db/column/selector_overlay.cc b/src/trace_processor/db/column/selector_overlay.cc
index 9ebbb71..999e4bb 100644
--- a/src/trace_processor/db/column/selector_overlay.cc
+++ b/src/trace_processor/db/column/selector_overlay.cc
@@ -56,8 +56,8 @@
PERFETTO_TP_TRACE(metatrace::Category::DB,
"SelectorOverlay::ChainImpl::Search");
- // Figure out the bounds of the indices in the underlying storage and search
- // it.
+ // Figure out the bounds of the OrderedIndices in the underlying storage and
+ // search it.
uint32_t start_idx = selector_->IndexOfNthSet(in.start);
uint32_t end_idx = selector_->IndexOfNthSet(in.end - 1) + 1;
@@ -83,35 +83,24 @@
return RangeOrBitVector(std::move(storage_bitvector));
}
-RangeOrBitVector SelectorOverlay::ChainImpl::IndexSearchValidated(
- 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.
-
+void SelectorOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(metatrace::Category::DB,
"SelectorOverlay::ChainImpl::IndexSearch");
// To go from TableIndexVector to StorageIndexVector we need to find index in
// |selector_| by looking only into set bits.
- std::vector<uint32_t> storage_iv(indices.size);
- for (uint32_t i = 0; i < indices.size; ++i) {
- storage_iv[i] = selector_->IndexOfNthSet(indices.data[i]);
+ for (auto& token : indices.tokens) {
+ token.index = selector_->IndexOfNthSet(token.index);
}
- return inner_->IndexSearchValidated(
- op, sql_val,
- Indices{storage_iv.data(), static_cast<uint32_t>(storage_iv.size()),
- indices.state});
+ return inner_->IndexSearchValidated(op, sql_val, indices);
}
Range SelectorOverlay::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ 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);
@@ -120,8 +109,9 @@
}
return inner_->OrderedIndexSearchValidated(
op, sql_val,
- Indices{inner_indices.data(), static_cast<uint32_t>(inner_indices.size()),
- indices.state});
+ OrderedIndices{inner_indices.data(),
+ static_cast<uint32_t>(inner_indices.size()),
+ indices.state});
}
void SelectorOverlay::ChainImpl::StableSort(SortToken* start,
diff --git a/src/trace_processor/db/column/selector_overlay.h b/src/trace_processor/db/column/selector_overlay.h
index 04f178a..82e2fe3 100644
--- a/src/trace_processor/db/column/selector_overlay.h
+++ b/src/trace_processor/db/column/selector_overlay.h
@@ -54,13 +54,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp p,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp p, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/selector_overlay_unittest.cc b/src/trace_processor/db/column/selector_overlay_unittest.cc
index 11d20f2..0abae4c 100644
--- a/src/trace_processor/db/column/selector_overlay_unittest.cc
+++ b/src/trace_processor/db/column/selector_overlay_unittest.cc
@@ -34,6 +34,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(SelectorOverlay, SingleSearch) {
BitVector selector{0, 1, 1, 0, 0, 1, 1, 0};
auto fake = FakeStorageChain::SearchSubset(8, Range(2, 5));
@@ -94,12 +97,10 @@
SelectorOverlay storage(&selector);
auto chain = storage.MakeChain(std::move(fake));
- std::vector<uint32_t> table_idx{1u, 0u, 3u};
- RangeOrBitVector res = chain->IndexSearch(
- FilterOp::kGe, SqlValue::Long(0u),
- Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1u));
+ auto indices = Indices::CreateWithIndexPayloadForTesting(
+ {1u, 0u, 3u}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0u), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1u));
}
TEST(SelectorOverlay, OrderedIndexSearchTrivial) {
@@ -111,8 +112,8 @@
std::vector<uint32_t> table_idx{1u, 0u, 2u};
Range res = chain->OrderedIndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
- Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
+ OrderedIndices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 3u);
}
@@ -126,8 +127,8 @@
std::vector<uint32_t> table_idx{1u, 0u, 2u};
Range res = chain->OrderedIndexSearch(
FilterOp::kGe, SqlValue::Long(0u),
- Indices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
- Indices::State::kNonmonotonic});
+ OrderedIndices{table_idx.data(), static_cast<uint32_t>(table_idx.size()),
+ Indices::State::kNonmonotonic});
ASSERT_EQ(res.size(), 0u);
}
diff --git a/src/trace_processor/db/column/set_id_storage.cc b/src/trace_processor/db/column/set_id_storage.cc
index 780761c..23b63b8 100644
--- a/src/trace_processor/db/column/set_id_storage.cc
+++ b/src/trace_processor/db/column/set_id_storage.cc
@@ -194,76 +194,66 @@
return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
-RangeOrBitVector SetIdStorage::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
+void SetIdStorage::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
PERFETTO_TP_TRACE(
metatrace::Category::DB, "SetIdStorage::ChainImpl::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
+ [&indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.tokens.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 RangeOrBitVector(Range(0, indices.size));
- case SearchValidationResult::kNoData:
- return RangeOrBitVector(Range());
+ if (utils::CanReturnEarly(utils::CompareIntColumnWithDouble(op, &sql_val),
+ indices)) {
+ return;
}
}
- auto val = static_cast<uint32_t>(sql_val.AsLong());
- BitVector::Builder builder(indices.size);
-
// TODO(mayzner): Instead of utils::IndexSearchWithComparator, use the
// property of SetId data - that for each index i, data[i] <= i.
+ auto val = static_cast<uint32_t>(sql_val.AsLong());
switch (op) {
case FilterOp::kEq:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::equal_to<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::equal_to<>());
break;
case FilterOp::kNe:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::not_equal_to<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::not_equal_to<>());
break;
case FilterOp::kLe:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::less_equal<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::less_equal<>());
break;
case FilterOp::kLt:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::less<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::less<>());
break;
case FilterOp::kGt:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::greater<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::greater<>());
break;
case FilterOp::kGe:
- utils::IndexSearchWithComparator(val, values_->data(), indices.data,
- std::greater_equal<>(), builder);
+ utils::IndexSearchWithComparator(val, values_->data(), indices,
+ std::greater_equal<>());
break;
case FilterOp::kIsNotNull:
- return RangeOrBitVector(Range(0, indices.size));
case FilterOp::kIsNull:
- return RangeOrBitVector(Range());
case FilterOp::kGlob:
case FilterOp::kRegex:
PERFETTO_FATAL("Illegal argument");
}
- return RangeOrBitVector(std::move(builder).Build());
}
Range SetIdStorage::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
- // Indices are monotonic non-contiguous values.
+ const OrderedIndices& indices) const {
+ // 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());
diff --git a/src/trace_processor/db/column/set_id_storage.h b/src/trace_processor/db/column/set_id_storage.h
index 64f14a3..e5bdb76 100644
--- a/src/trace_processor/db/column/set_id_storage.h
+++ b/src/trace_processor/db/column/set_id_storage.h
@@ -52,13 +52,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
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 99371dc..7af21ac 100644
--- a/src/trace_processor/db/column/set_id_storage_unittest.cc
+++ b/src/trace_processor/db/column/set_id_storage_unittest.cc
@@ -44,6 +44,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(SetIdStorage, SearchSingle) {
std::vector<uint32_t> storage_data{0, 0, 2, 2, 4, 4, 6, 6};
SetIdStorage storage(&storage_data);
@@ -176,32 +179,32 @@
auto chain = storage.MakeChain();
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};
+ auto common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {6, 4, 2, 0}, Indices::State::kNonmonotonic);
- FilterOp op = FilterOp::kEq;
- auto res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1));
- op = FilterOp::kNe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2, 3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
- op = FilterOp::kLe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2, 3));
- op = FilterOp::kLt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 3));
- op = FilterOp::kGe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1));
- op = FilterOp::kGt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
}
TEST(SetIdStorage, OrderedIndexSearchSimple) {
@@ -211,7 +214,7 @@
// 0, 2, 2, 4
std::vector<uint32_t> indices_vec{0, 3, 3, 5};
- Indices indices{indices_vec.data(), 4, Indices::State::kMonotonic};
+ OrderedIndices indices{indices_vec.data(), 4, Indices::State::kMonotonic};
Range range =
chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(2), indices);
@@ -284,13 +287,10 @@
auto chain = storage.MakeChain();
// {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 = chain->IndexSearch(FilterOp::kEq, SqlValue::Long(10), indices)
- .TakeIfBitVector();
-
- ASSERT_EQ(bv.CountSetBits(), 0u);
+ auto indices = Indices::CreateWithIndexPayloadForTesting(
+ {1, 3, 5, 7, 9, 11, 2, 4}, Indices::State::kNonmonotonic);
+ chain->IndexSearch(FilterOp::kEq, SqlValue::Long(10), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
}
TEST(SetIdStorage, SearchWithIdAsSimpleDoubleIsInt) {
diff --git a/src/trace_processor/db/column/string_storage.cc b/src/trace_processor/db/column/string_storage.cc
index 05f5932..02c8696 100644
--- a/src/trace_processor/db/column/string_storage.cc
+++ b/src/trace_processor/db/column/string_storage.cc
@@ -76,20 +76,20 @@
};
struct NotEqual {
- bool operator()(StringPool::Id lhs, StringPool::Id rhs) {
+ bool operator()(StringPool::Id lhs, StringPool::Id rhs) const {
return lhs != StringPool::Id::Null() && lhs != rhs;
}
};
struct Glob {
- bool operator()(StringPool::Id lhs, util::GlobMatcher& matcher) const {
+ bool operator()(StringPool::Id lhs, const util::GlobMatcher& matcher) const {
return lhs != StringPool::Id::Null() && matcher.Matches(pool_->Get(lhs));
}
const StringPool* pool_;
};
struct GlobFullStringPool {
- GlobFullStringPool(StringPool* pool, util::GlobMatcher& matcher)
+ GlobFullStringPool(StringPool* pool, const util::GlobMatcher& matcher)
: pool_(pool), matches_(pool->MaxSmallStringId().raw_id()) {
PERFETTO_DCHECK(!pool->HasLargeString());
for (auto it = pool->CreateIterator(); it; ++it) {
@@ -97,7 +97,7 @@
matches_[id.raw_id()] = matcher.Matches(pool->Get(id));
}
}
- bool operator()(StringPool::Id lhs, StringPool::Id) {
+ bool operator()(StringPool::Id lhs, StringPool::Id) const {
return lhs != StringPool::Id::Null() && matches_[lhs.raw_id()];
}
StringPool* pool_;
@@ -105,7 +105,7 @@
};
struct Regex {
- bool operator()(StringPool::Id lhs, regex::Regex& pattern) const {
+ bool operator()(StringPool::Id lhs, const regex::Regex& pattern) const {
return lhs != StringPool::Id::Null() &&
pattern.Search(pool_->Get(lhs).c_str());
}
@@ -122,7 +122,7 @@
id != StringPool::Id::Null() && regex.Search(pool_->Get(id).c_str());
}
}
- bool operator()(StringPool::Id lhs, StringPool::Id) {
+ bool operator()(StringPool::Id lhs, StringPool::Id) const {
return matches_[lhs.raw_id()];
}
StringPool* pool_;
@@ -345,19 +345,71 @@
return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
}
-RangeOrBitVector StringStorage::ChainImpl::IndexSearchValidated(
- FilterOp op,
- SqlValue sql_val,
- Indices indices) const {
- PERFETTO_DCHECK(indices.size <= size());
+void StringStorage::ChainImpl::IndexSearchValidated(FilterOp op,
+ SqlValue sql_val,
+ Indices& indices) const {
+ PERFETTO_DCHECK(indices.tokens.size() <= size());
PERFETTO_TP_TRACE(
metatrace::Category::DB, "StringStorage::ChainImpl::IndexSearch",
- [indices, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices.size));
+ [&indices, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices.tokens.size()));
r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
});
- return RangeOrBitVector(
- IndexSearchInternal(op, sql_val, indices.data, indices.size));
+
+ StringPool::Id val =
+ (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
+ ? StringPool::Id::Null()
+ : string_pool_->InternString(base::StringView(sql_val.AsString()));
+ const StringPool::Id* start = data_->data();
+ switch (op) {
+ case FilterOp::kEq:
+ utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>());
+ break;
+ case FilterOp::kNe:
+ utils::IndexSearchWithComparator(val, start, indices, NotEqual());
+ break;
+ case FilterOp::kLe:
+ utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
+ LessEqual{string_pool_});
+ break;
+ case FilterOp::kLt:
+ utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
+ Less{string_pool_});
+ break;
+ case FilterOp::kGt:
+ utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
+ Greater{string_pool_});
+ break;
+ case FilterOp::kGe:
+ utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
+ GreaterEqual{string_pool_});
+ break;
+ case FilterOp::kGlob: {
+ util::GlobMatcher matcher =
+ util::GlobMatcher::FromPattern(sql_val.AsString());
+ if (matcher.IsEquality()) {
+ utils::IndexSearchWithComparator(val, start, indices,
+ std::equal_to<>());
+ break;
+ }
+ utils::IndexSearchWithComparator(std::move(matcher), start, indices,
+ Glob{string_pool_});
+ break;
+ }
+ case FilterOp::kRegex: {
+ base::StatusOr<regex::Regex> regex =
+ regex::Regex::Create(sql_val.AsString());
+ utils::IndexSearchWithComparator(std::move(regex.value()), start, indices,
+ Regex{string_pool_});
+ break;
+ }
+ case FilterOp::kIsNull:
+ utils::IndexSearchWithComparator(val, start, indices, IsNull());
+ break;
+ case FilterOp::kIsNotNull:
+ utils::IndexSearchWithComparator(val, start, indices, IsNotNull());
+ break;
+ }
}
BitVector StringStorage::ChainImpl::LinearSearch(FilterOp op,
@@ -452,7 +504,7 @@
Range StringStorage::ChainImpl::OrderedIndexSearchValidated(
FilterOp op,
SqlValue sql_val,
- Indices indices) const {
+ const OrderedIndices& indices) const {
StringPool::Id val =
(op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
? StringPool::Id::Null()
@@ -509,75 +561,6 @@
PERFETTO_FATAL("For GCC");
}
-RangeOrBitVector StringStorage::ChainImpl::IndexSearchInternal(
- FilterOp op,
- SqlValue sql_val,
- const uint32_t* indices,
- uint32_t indices_size) const {
- StringPool::Id val =
- (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
- ? StringPool::Id::Null()
- : string_pool_->InternString(base::StringView(sql_val.AsString()));
- const StringPool::Id* start = data_->data();
-
- BitVector::Builder builder(indices_size);
-
- switch (op) {
- case FilterOp::kEq:
- utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>(),
- builder);
- break;
- case FilterOp::kNe:
- utils::IndexSearchWithComparator(val, start, indices, NotEqual(),
- builder);
- break;
- case FilterOp::kLe:
- utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
- LessEqual{string_pool_}, builder);
- break;
- case FilterOp::kLt:
- utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
- Less{string_pool_}, builder);
- break;
- case FilterOp::kGt:
- utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
- Greater{string_pool_}, builder);
- break;
- case FilterOp::kGe:
- utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
- GreaterEqual{string_pool_}, builder);
- break;
- case FilterOp::kGlob: {
- util::GlobMatcher matcher =
- util::GlobMatcher::FromPattern(sql_val.AsString());
- if (matcher.IsEquality()) {
- utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>(),
- builder);
- break;
- }
- utils::IndexSearchWithComparator(std::move(matcher), start, indices,
- Glob{string_pool_}, builder);
- break;
- }
- case FilterOp::kRegex: {
- base::StatusOr<regex::Regex> regex =
- regex::Regex::Create(sql_val.AsString());
- utils::IndexSearchWithComparator(std::move(regex.value()), start, indices,
- Regex{string_pool_}, builder);
- break;
- }
- case FilterOp::kIsNull:
- utils::IndexSearchWithComparator(val, start, indices, IsNull(), builder);
- break;
- case FilterOp::kIsNotNull:
- utils::IndexSearchWithComparator(val, start, indices, IsNotNull(),
- builder);
- break;
- }
-
- return RangeOrBitVector(std::move(builder).Build());
-}
-
Range StringStorage::ChainImpl::BinarySearchIntrinsic(
FilterOp op,
SqlValue sql_val,
diff --git a/src/trace_processor/db/column/string_storage.h b/src/trace_processor/db/column/string_storage.h
index d61aef5..f037bd1 100644
--- a/src/trace_processor/db/column/string_storage.h
+++ b/src/trace_processor/db/column/string_storage.h
@@ -55,13 +55,11 @@
RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
- RangeOrBitVector IndexSearchValidated(FilterOp,
- SqlValue,
- Indices) const override;
+ void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
Range OrderedIndexSearchValidated(FilterOp,
SqlValue,
- Indices) const override;
+ const OrderedIndices&) const override;
void StableSort(SortToken* start,
SortToken* end,
diff --git a/src/trace_processor/db/column/string_storage_unittest.cc b/src/trace_processor/db/column/string_storage_unittest.cc
index 303ab66..5312404 100644
--- a/src/trace_processor/db/column/string_storage_unittest.cc
+++ b/src/trace_processor/db/column/string_storage_unittest.cc
@@ -35,6 +35,9 @@
using testing::ElementsAre;
using testing::IsEmpty;
+using Indices = DataLayerChain::Indices;
+using OrderedIndices = DataLayerChain::OrderedIndices;
+
TEST(StringStorage, SearchOneElement) {
std::vector<std::string> strings{"cheese", "pasta", "pizza",
"pierogi", "onion", "fries"};
@@ -161,44 +164,48 @@
auto chain = storage.MakeChain();
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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {6, 5, 4, 3, 2, 1, 0}, Indices::State::kNonmonotonic);
- FilterOp op = FilterOp::kEq;
- auto res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
- op = FilterOp::kNe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 4, 5, 6));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 4, 5, 6));
- op = FilterOp::kLt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 5, 6));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 5, 6));
- op = FilterOp::kLe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 5, 6));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 5, 6));
- op = FilterOp::kGt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
- op = FilterOp::kGe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 4));
- op = FilterOp::kIsNull;
- res = chain->IndexSearch(op, SqlValue(), indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
- op = FilterOp::kIsNotNull;
- res = chain->IndexSearch(op, SqlValue(), indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4, 5, 6));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
+ ElementsAre(0, 1, 2, 4, 5, 6));
- op = FilterOp::kGlob;
- res = chain->IndexSearch(op, SqlValue::String("p*"), indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4, 5));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGlob, SqlValue::String("p*"), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 4, 5));
}
#if !PERFETTO_BUILDFLAG(PERFETTO_OS_WIN)
@@ -294,37 +301,36 @@
StringStorage storage(&pool, &ids, true);
auto chain = storage.MakeChain();
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};
+ Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
+ {5, 4, 2, 1}, Indices::State::kNonmonotonic);
- FilterOp op = FilterOp::kEq;
- auto res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
+ auto indices = common_indices;
+ chain->IndexSearch(FilterOp::kEq, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
- op = FilterOp::kNe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kNe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 3));
- op = FilterOp::kLt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
- op = FilterOp::kLe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kLe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2, 3));
- op = FilterOp::kGt;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGt, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1));
- op = FilterOp::kGe;
- res = chain->IndexSearch(op, val, indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGe, val, indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
- op = FilterOp::kGlob;
- res = chain->IndexSearch(op, SqlValue::String("*e"), indices);
- ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
+ indices = common_indices;
+ chain->IndexSearch(FilterOp::kGlob, SqlValue::String("*e"), indices);
+ ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(2));
}
TEST(StringStorage, OrderedIndexSearch) {
@@ -340,7 +346,7 @@
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};
+ OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
FilterOp op = FilterOp::kEq;
Range res = chain->OrderedIndexSearch(op, val, indices);
@@ -380,7 +386,7 @@
auto chain = storage.MakeChain();
std::vector<uint32_t> indices_vec{0, 2, 5, 7};
- Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
+ OrderedIndices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
auto res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
ASSERT_EQ(res.start, 0u);
ASSERT_EQ(res.end, 2u);
@@ -398,7 +404,7 @@
auto chain = storage.MakeChain();
std::vector<uint32_t> indices_vec{0, 2, 5, 7};
- Indices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
+ OrderedIndices indices{indices_vec.data(), 4, Indices::State::kNonmonotonic};
auto res =
chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
ASSERT_EQ(res.start, 2u);
diff --git a/src/trace_processor/db/column/types.h b/src/trace_processor/db/column/types.h
index 803c6ce..b59084b 100644
--- a/src/trace_processor/db/column/types.h
+++ b/src/trace_processor/db/column/types.h
@@ -19,6 +19,7 @@
#include <cstdint>
#include <utility>
#include <variant>
+#include <vector>
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
@@ -113,21 +114,6 @@
kDummy,
};
-// Index vector related data required to Filter using IndexSearch.
-struct Indices {
- enum class State {
- // We can't guarantee that data is in monotonic order.
- kNonmonotonic,
- // Data is in monotonic order.
- // TODO(b/307482437): Use this to optimise filtering if storage is sorted.
- kMonotonic
- };
-
- const uint32_t* data = nullptr;
- uint32_t size = 0;
- State state = Indices::State::kNonmonotonic;
-};
-
} // namespace perfetto::trace_processor
#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_TYPES_H_
diff --git a/src/trace_processor/db/column/utils.cc b/src/trace_processor/db/column/utils.cc
index efec000..e24f3bf 100644
--- a/src/trace_processor/db/column/utils.cc
+++ b/src/trace_processor/db/column/utils.cc
@@ -79,6 +79,16 @@
}
std::vector<uint32_t> ExtractPayloadForTesting(
+ const DataLayerChain::Indices& indices) {
+ std::vector<uint32_t> payload;
+ payload.reserve(indices.tokens.size());
+ for (const auto& token : indices.tokens) {
+ payload.push_back(token.payload);
+ }
+ return payload;
+}
+
+std::vector<uint32_t> ExtractPayloadForTesting(
std::vector<column::DataLayerChain::SortToken>& tokens) {
std::vector<uint32_t> payload;
payload.reserve(tokens.size());
@@ -113,4 +123,18 @@
PERFETTO_FATAL("For GCC");
}
+bool CanReturnEarly(SearchValidationResult res,
+ DataLayerChain::Indices& indices) {
+ switch (res) {
+ case SearchValidationResult::kOk:
+ return false;
+ case SearchValidationResult::kAllData:
+ return true;
+ case SearchValidationResult::kNoData:
+ indices.tokens.clear();
+ return true;
+ }
+ PERFETTO_FATAL("For GCC");
+}
+
} // namespace perfetto::trace_processor::column::utils
diff --git a/src/trace_processor/db/column/utils.h b/src/trace_processor/db/column/utils.h
index b1c71a3..14c6456 100644
--- a/src/trace_processor/db/column/utils.h
+++ b/src/trace_processor/db/column/utils.h
@@ -16,6 +16,7 @@
#ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
#define SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
+#include <algorithm>
#include <cstdint>
#include <functional>
#include <optional>
@@ -65,28 +66,14 @@
template <typename Comparator, typename ValType, typename DataType>
void IndexSearchWithComparator(ValType val,
const DataType* data_ptr,
- const uint32_t* indices,
- Comparator comparator,
- BitVector::Builder& builder) {
- // Fast path: we compare as many groups of 64 elements as we can.
- // This should be very easy for the compiler to auto-vectorize.
- const uint32_t* cur_idx = indices;
- uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
- for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
- uint64_t word = 0;
- // This part should be optimised by SIMD and is expected to be fast.
- for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k, ++cur_idx) {
- bool comp_result = comparator(*(data_ptr + *cur_idx), val);
- word |= static_cast<uint64_t>(comp_result) << k;
- }
- builder.AppendWord(word);
- }
-
- // Slow path: we compare <64 elements and append to fill the Builder.
- uint32_t back_elements = builder.BitsUntilFull();
- for (uint32_t i = 0; i < back_elements; ++i, ++cur_idx) {
- builder.Append(comparator(*(data_ptr + *cur_idx), val));
- }
+ DataLayerChain::Indices& indices,
+ Comparator comparator) {
+ auto it = std::remove_if(indices.tokens.begin(), indices.tokens.end(),
+ [&comparator, data_ptr,
+ &val](const DataLayerChain::Indices::Token& token) {
+ return !comparator(*(data_ptr + token.index), val);
+ });
+ indices.tokens.erase(it, indices.tokens.end());
}
template <typename T>
@@ -136,11 +123,18 @@
std::optional<Range> CanReturnEarly(SearchValidationResult,
uint32_t indices_size);
+// If the validation result doesn't require further search, will modify
+// |indices| to match and return true. Otherwise returns false.
+bool CanReturnEarly(SearchValidationResult res,
+ DataLayerChain::Indices& indices);
+
std::vector<uint32_t> ExtractPayloadForTesting(
std::vector<column::DataLayerChain::SortToken>&);
std::vector<uint32_t> ToIndexVectorForTests(RangeOrBitVector&);
+std::vector<uint32_t> ExtractPayloadForTesting(const DataLayerChain::Indices&);
+
} // namespace perfetto::trace_processor::column::utils
#endif // SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
diff --git a/src/trace_processor/db/query_executor.cc b/src/trace_processor/db/query_executor.cc
index bd15245..0dd3aa9 100644
--- a/src/trace_processor/db/query_executor.cc
+++ b/src/trace_processor/db/query_executor.cc
@@ -19,6 +19,7 @@
#include <utility>
#include <vector>
+#include <sys/types.h>
#include "perfetto/base/logging.h"
#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
@@ -116,36 +117,17 @@
// Create outmost TableIndexVector.
std::vector<uint32_t> table_indices = std::move(*rm).TakeAsIndexVector();
- RangeOrBitVector matched = chain.IndexSearch(
- c.op, c.value,
- Indices{table_indices.data(), static_cast<uint32_t>(table_indices.size()),
- Indices::State::kMonotonic});
+ using Indices = column::DataLayerChain::Indices;
+ Indices indices = Indices::Create(table_indices, Indices::State::kMonotonic);
+ chain.IndexSearch(c.op, c.value, indices);
- if (matched.IsBitVector()) {
- BitVector res = std::move(matched).TakeIfBitVector();
- uint32_t i = 0;
- table_indices.erase(
- std::remove_if(table_indices.begin(), table_indices.end(),
- [&i, &res](uint32_t) { return !res.IsSet(i++); }),
- table_indices.end());
- *rm = RowMap(std::move(table_indices));
- return;
+ PERFETTO_DCHECK(indices.tokens.size() <= table_indices.size());
+ for (uint32_t i = 0; i < indices.tokens.size(); ++i) {
+ table_indices[i] = indices.tokens[i].payload;
}
-
- Range res = std::move(matched).TakeIfRange();
- if (res.size() == 0) {
- rm->Clear();
- return;
- }
- if (res.size() == table_indices.size()) {
- return;
- }
-
- PERFETTO_DCHECK(res.end <= table_indices.size());
- std::vector<uint32_t> res_as_iv(
- table_indices.begin() + static_cast<int>(res.start),
- table_indices.begin() + static_cast<int>(res.end));
- *rm = RowMap(std::move(res_as_iv));
+ table_indices.resize(indices.tokens.size());
+ PERFETTO_DCHECK(std::is_sorted(table_indices.begin(), table_indices.end()));
+ *rm = RowMap(std::move(table_indices));
}
RowMap QueryExecutor::FilterLegacy(const Table* table,
diff --git a/src/trace_processor/db/query_executor_unittest.cc b/src/trace_processor/db/query_executor_unittest.cc
index f0d8f03..161a106 100644
--- a/src/trace_processor/db/query_executor_unittest.cc
+++ b/src/trace_processor/db/query_executor_unittest.cc
@@ -52,6 +52,8 @@
using ArrangementOverlay = column::ArrangementOverlay;
using SelectorOverlay = column::SelectorOverlay;
+using Indices = column::DataLayerChain::Indices;
+
TEST(QueryExecutor, OnlyStorageRange) {
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
column::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64,
diff --git a/src/trace_processor/db/table.cc b/src/trace_processor/db/table.cc
index 7bedbb7..641c745 100644
--- a/src/trace_processor/db/table.cc
+++ b/src/trace_processor/db/table.cc
@@ -157,7 +157,7 @@
if (table.overlays_[i].row_map().IsIndexVector()) {
overlay_layers[i].reset(new column::ArrangementOverlay(
table.overlays_[i].row_map().GetIfIndexVector(),
- Indices::State::kNonmonotonic));
+ column::DataLayerChain::Indices::State::kNonmonotonic));
} else if (table.overlays_[i].row_map().IsBitVector()) {
overlay_layers[i].reset(new column::SelectorOverlay(
table.overlays_[i].row_map().GetIfBitVector()));
diff --git a/src/trace_processor/util/glob.cc b/src/trace_processor/util/glob.cc
index f930683..3f44f36 100644
--- a/src/trace_processor/util/glob.cc
+++ b/src/trace_processor/util/glob.cc
@@ -78,7 +78,7 @@
trailing_star_ = !pattern.empty() && empty_segment;
}
-bool GlobMatcher::Matches(base::StringView in) {
+bool GlobMatcher::Matches(base::StringView in) const {
// If there are no segments, that means the pattern is either '' or '*'
// (or '**', '***' etc which is really the same as '*'). This means
// we are match if either a) there is a leading star (== trailing star) or
@@ -115,10 +115,10 @@
// sequentially with possibly some characters separating them. To handle
// this, we just need to iteratively find each segment, starting from the
// previous segment.
- Segment* segment_start = segments_.begin() + (leading_star_ ? 0 : 1);
- Segment* segment_end = segments_.end() - (trailing_star_ ? 0 : 1);
+ const Segment* segment_start = segments_.begin() + (leading_star_ ? 0 : 1);
+ const Segment* segment_end = segments_.end() - (trailing_star_ ? 0 : 1);
size_t find_idx = leading_star_ ? 0 : segments_.front().matched_chars;
- for (Segment* segment = segment_start; segment < segment_end; ++segment) {
+ for (const auto* segment = segment_start; segment < segment_end; ++segment) {
size_t pos = Find(in, *segment, find_idx);
if (pos == base::StringView::npos) {
return false;
@@ -131,7 +131,8 @@
return true;
}
-bool GlobMatcher::StartsWithSlow(base::StringView in, const Segment& segment) {
+bool GlobMatcher::StartsWithSlow(base::StringView in,
+ const Segment& segment) const {
base::StringView pattern = segment.pattern;
for (uint32_t i = 0, p = 0; p < pattern.size(); ++i, ++p) {
// We've run out of characters to consume in the input but still have more
diff --git a/src/trace_processor/util/glob.h b/src/trace_processor/util/glob.h
index b5bce6e..518cca8 100644
--- a/src/trace_processor/util/glob.h
+++ b/src/trace_processor/util/glob.h
@@ -80,7 +80,7 @@
// Checks the provided string against the pattern and returns whether it
// matches.
- bool Matches(base::StringView input);
+ bool Matches(base::StringView input) const;
// Returns whether the comparison should really be an equality comparison.
bool IsEquality() {
@@ -110,7 +110,7 @@
// Returns whether |input| starts with the pattern in |segment| following
// glob matching rules.
- bool StartsWith(base::StringView input, const Segment& segment) {
+ bool StartsWith(base::StringView input, const Segment& segment) const {
if (!contains_char_class_or_question_) {
return input.StartsWith(segment.pattern);
}
@@ -119,7 +119,7 @@
// Returns whether |input| ends with the pattern in |segment| following
// glob matching rules.
- bool EndsWith(base::StringView input, const Segment& segment) {
+ bool EndsWith(base::StringView input, const Segment& segment) const {
if (!contains_char_class_or_question_) {
return input.EndsWith(segment.pattern);
}
@@ -131,7 +131,9 @@
// Returns the index where |input| matches the pattern in |segment|
// following glob matching rules or base::StringView::npos, if no such index
// exists.
- size_t Find(base::StringView input, const Segment& segment, size_t start) {
+ size_t Find(base::StringView input,
+ const Segment& segment,
+ size_t start) const {
if (!contains_char_class_or_question_) {
return input.find(segment.pattern, start);
}
@@ -151,7 +153,7 @@
// Matches |in| against the given character class.
static bool MatchesCharacterClass(char input, base::StringView char_class);
- bool StartsWithSlow(base::StringView input, const Segment& segment);
+ bool StartsWithSlow(base::StringView input, const Segment& segment) const;
// IMPORTANT: this should *not* be modified after the constructor as we store
// pointers to the data inside here.
