Merge "tp: CEngine cleanup" into main
diff --git a/src/trace_processor/db/query_executor.cc b/src/trace_processor/db/query_executor.cc
index bd04fa0..e6b91d3 100644
--- a/src/trace_processor/db/query_executor.cc
+++ b/src/trace_processor/db/query_executor.cc
@@ -50,9 +50,11 @@
void QueryExecutor::FilterColumn(const Constraint& c,
const storage::Storage& storage,
RowMap* rm) {
+ // Shortcut of empty row map.
if (rm->empty())
return;
+ // Decide which algorithm should be used for filtering.
uint32_t rm_size = rm->size();
uint32_t rm_first = rm->Get(0);
uint32_t rm_last = rm->Get(rm_size - 1);
@@ -64,8 +66,9 @@
bool disallows_index_search = rm->IsRange();
bool prefers_index_search =
rm->IsIndexVector() || rm_size < 1024 || rm_size * 10 < range_size;
+
if (!disallows_index_search && prefers_index_search) {
- *rm = IndexSearch(c, storage, rm);
+ IndexSearch(c, storage, rm);
return;
}
LinearSearch(c, storage, rm);
@@ -99,9 +102,9 @@
rm->Intersect(RowMap(std::move(res).TakeIfBitVector()));
}
-RowMap QueryExecutor::IndexSearch(const Constraint& c,
- const storage::Storage& storage,
- RowMap* rm) {
+void QueryExecutor::IndexSearch(const Constraint& c,
+ const storage::Storage& storage,
+ RowMap* rm) {
// Create outmost TableIndexVector.
std::vector<uint32_t> table_indices = std::move(*rm).TakeAsIndexVector();
@@ -109,16 +112,27 @@
c.op, c.value, table_indices.data(),
static_cast<uint32_t>(table_indices.size()), false /* sorted */);
- // TODO(b/283763282): Remove after implementing extrinsic binary search.
- PERFETTO_CHECK(matched.IsBitVector());
+ 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;
+ }
- 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());
- return RowMap(std::move(table_indices));
+ Range res = std::move(matched).TakeIfRange();
+ if (res.size() == 0) {
+ rm->Clear();
+ return;
+ }
+ if (res.size() == table_indices.size()) {
+ return;
+ }
+ // TODO(b/283763282): Remove after implementing extrinsic binary search.
+ PERFETTO_FATAL("Extrinsic binary search is not implemented.");
}
RowMap QueryExecutor::FilterLegacy(const Table* table,
@@ -226,8 +240,8 @@
}
}
if (col.IsNullable()) {
- // String columns are inherently nullable: null values are signified with
- // Id::Null().
+ // String columns are inherently nullable: null values are signified
+ // with Id::Null().
PERFETTO_CHECK(col.col_type() != ColumnType::kString);
storage = std::make_unique<storage::NullStorage>(std::move(storage),
col.storage_base().bv());
diff --git a/src/trace_processor/db/query_executor.h b/src/trace_processor/db/query_executor.h
index 07281f7..013dbf2 100644
--- a/src/trace_processor/db/query_executor.h
+++ b/src/trace_processor/db/query_executor.h
@@ -70,10 +70,10 @@
}
// Used only in unittests. Exposes private function.
- static RowMap IndexedColumnFilterForTesting(const Constraint& c,
- const storage::Storage& col,
- RowMap* rm) {
- return IndexSearch(c, col, rm);
+ static void IndexedColumnFilterForTesting(const Constraint& c,
+ const storage::Storage& col,
+ RowMap* rm) {
+ IndexSearch(c, col, rm);
}
private:
@@ -86,9 +86,7 @@
// Filters the column using Index algorithm - finds the indices to filter the
// storage with.
- static RowMap IndexSearch(const Constraint&,
- const storage::Storage&,
- RowMap*);
+ static void IndexSearch(const Constraint&, const storage::Storage&, RowMap*);
std::vector<storage::Storage*> columns_;
diff --git a/src/trace_processor/db/query_executor_unittest.cc b/src/trace_processor/db/query_executor_unittest.cc
index 849c1cb..19eca3d 100644
--- a/src/trace_processor/db/query_executor_unittest.cc
+++ b/src/trace_processor/db/query_executor_unittest.cc
@@ -56,7 +56,7 @@
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
storage::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 5);
QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
@@ -73,24 +73,24 @@
Constraint c{0, FilterOp::kLt, SqlValue::Long(2)};
RowMap rm(0, 10);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_EQ(res.size(), 4u);
- ASSERT_EQ(res.Get(0), 0u);
- ASSERT_EQ(res.Get(1), 1u);
- ASSERT_EQ(res.Get(2), 5u);
- ASSERT_EQ(res.Get(3), 6u);
+ ASSERT_EQ(rm.size(), 4u);
+ ASSERT_EQ(rm.Get(0), 0u);
+ ASSERT_EQ(rm.Get(1), 1u);
+ ASSERT_EQ(rm.Get(2), 5u);
+ ASSERT_EQ(rm.Get(3), 6u);
}
TEST(QueryExecutor, OnlyStorageIndexIsNull) {
std::vector<int64_t> storage_data{1, 2, 3, 4, 5};
storage::NumericStorage<int64_t> storage(&storage_data, ColumnType::kInt64);
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 5);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_EQ(res.size(), 0u);
+ ASSERT_EQ(rm.size(), 0u);
}
TEST(QueryExecutor, NullBounds) {
@@ -118,7 +118,7 @@
BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
storage::NullStorage storage(std::move(numeric), &bv);
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 10);
QueryExecutor::BoundedColumnFilterForTesting(c, storage, &rm);
@@ -143,13 +143,13 @@
Constraint c{0, FilterOp::kGe, SqlValue::Long(1)};
RowMap rm(0, 10);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_EQ(res.size(), 4u);
- ASSERT_EQ(res.Get(0), 1u);
- ASSERT_EQ(res.Get(1), 3u);
- ASSERT_EQ(res.Get(2), 6u);
- ASSERT_EQ(res.Get(3), 9u);
+ ASSERT_EQ(rm.size(), 4u);
+ ASSERT_EQ(rm.Get(0), 1u);
+ ASSERT_EQ(rm.Get(1), 3u);
+ ASSERT_EQ(rm.Get(2), 6u);
+ ASSERT_EQ(rm.Get(3), 9u);
}
TEST(QueryExecutor, NullIndexIsNull) {
@@ -161,16 +161,16 @@
BitVector bv{1, 1, 0, 1, 1, 0, 0, 0, 1, 0};
storage::NullStorage storage(std::move(numeric), &bv);
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(3)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
RowMap rm(0, 10);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_EQ(res.size(), 5u);
- ASSERT_EQ(res.Get(0), 2u);
- ASSERT_EQ(res.Get(1), 5u);
- ASSERT_EQ(res.Get(2), 6u);
- ASSERT_EQ(res.Get(3), 7u);
- ASSERT_EQ(res.Get(4), 9u);
+ ASSERT_EQ(rm.size(), 5u);
+ ASSERT_EQ(rm.Get(0), 2u);
+ ASSERT_EQ(rm.Get(1), 5u);
+ ASSERT_EQ(rm.Get(2), 6u);
+ ASSERT_EQ(rm.Get(3), 7u);
+ ASSERT_EQ(rm.Get(4), 9u);
}
TEST(QueryExecutor, SelectorStorageBounds) {
@@ -202,9 +202,9 @@
Constraint c{0, FilterOp::kGe, SqlValue::Long(2)};
RowMap rm(0, 6);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_THAT(res.GetAllIndices(), ElementsAre(2u, 3u, 5u));
+ ASSERT_THAT(rm.GetAllIndices(), ElementsAre(2u, 3u, 5u));
}
TEST(QueryExecutor, ArrangementStorageBounds) {
@@ -262,9 +262,9 @@
Constraint c{0, FilterOp::kGe, SqlValue::Long(3)};
RowMap rm(0, 5);
- RowMap res = QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
+ QueryExecutor::IndexedColumnFilterForTesting(c, storage, &rm);
- ASSERT_THAT(res.GetAllIndices(), ElementsAre(0u, 4u));
+ ASSERT_THAT(rm.GetAllIndices(), ElementsAre(0u, 4u));
}
TEST(QueryExecutor, SingleConstraintWithNullAndSelector) {
@@ -336,7 +336,7 @@
SelectorStorage storage(std::move(null), &selector_bv);
// Filter.
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
QueryExecutor exec({&storage}, 6);
RowMap res = exec.Filter({c});
@@ -436,7 +436,7 @@
IdStorage storage(5);
// Filter.
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
QueryExecutor exec({&storage}, 5);
RowMap res = exec.Filter({c});
@@ -447,7 +447,7 @@
IdStorage storage(5);
// Filter.
- Constraint c{0, FilterOp::kIsNotNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNotNull, SqlValue()};
QueryExecutor exec({&storage}, 5);
RowMap res = exec.Filter({c});
@@ -481,7 +481,7 @@
SelectorStorage storage(std::move(string), &selector_bv);
// Filter.
- Constraint c{0, FilterOp::kIsNull, SqlValue::Long(0)};
+ Constraint c{0, FilterOp::kIsNull, SqlValue()};
QueryExecutor exec({&storage}, 5);
RowMap res = exec.Filter({c});
diff --git a/src/trace_processor/db/storage/arrangement_storage.cc b/src/trace_processor/db/storage/arrangement_storage.cc
index b0171db..fac7f68 100644
--- a/src/trace_processor/db/storage/arrangement_storage.cc
+++ b/src/trace_processor/db/storage/arrangement_storage.cc
@@ -40,6 +40,12 @@
inner_->size());
}
+Storage::SearchValidationResult ArrangementStorage::ValidateSearchConstraints(
+ SqlValue sql_val,
+ FilterOp op) const {
+ return inner_->ValidateSearchConstraints(sql_val, op);
+}
+
RangeOrBitVector ArrangementStorage::Search(FilterOp op,
SqlValue sql_val,
Range in) const {
diff --git a/src/trace_processor/db/storage/arrangement_storage.h b/src/trace_processor/db/storage/arrangement_storage.h
index cfc10c9..97a944e 100644
--- a/src/trace_processor/db/storage/arrangement_storage.h
+++ b/src/trace_processor/db/storage/arrangement_storage.h
@@ -32,6 +32,9 @@
explicit ArrangementStorage(std::unique_ptr<Storage> inner,
const std::vector<uint32_t>* arrangement);
+ Storage::SearchValidationResult ValidateSearchConstraints(SqlValue, FilterOp)
+ const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
diff --git a/src/trace_processor/db/storage/dummy_storage.cc b/src/trace_processor/db/storage/dummy_storage.cc
index 4c6eb05..b4f0be5 100644
--- a/src/trace_processor/db/storage/dummy_storage.cc
+++ b/src/trace_processor/db/storage/dummy_storage.cc
@@ -21,6 +21,12 @@
namespace trace_processor {
namespace storage {
+DummyStorage::SearchValidationResult DummyStorage::ValidateSearchConstraints(
+ SqlValue,
+ FilterOp) const {
+ PERFETTO_FATAL("Shouldn't be called");
+}
+
RangeOrBitVector DummyStorage::Search(FilterOp, SqlValue, RowMap::Range) const {
PERFETTO_FATAL("Shouldn't be called");
}
diff --git a/src/trace_processor/db/storage/dummy_storage.h b/src/trace_processor/db/storage/dummy_storage.h
index 8d76d2f..7fd3a40 100644
--- a/src/trace_processor/db/storage/dummy_storage.h
+++ b/src/trace_processor/db/storage/dummy_storage.h
@@ -36,6 +36,9 @@
RangeOrBitVector Search(FilterOp, SqlValue, RowMap::Range) const override;
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector IndexSearch(FilterOp,
SqlValue,
uint32_t*,
diff --git a/src/trace_processor/db/storage/fake_storage.cc b/src/trace_processor/db/storage/fake_storage.cc
index 8d2550c..fd9ac2c 100644
--- a/src/trace_processor/db/storage/fake_storage.cc
+++ b/src/trace_processor/db/storage/fake_storage.cc
@@ -17,6 +17,7 @@
#include "src/trace_processor/db/storage/fake_storage.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/types.h"
namespace perfetto {
@@ -26,6 +27,12 @@
FakeStorage::FakeStorage(uint32_t size, SearchStrategy strategy)
: size_(size), strategy_(strategy) {}
+FakeStorage::SearchValidationResult FakeStorage::ValidateSearchConstraints(
+ SqlValue,
+ FilterOp) const {
+ return SearchValidationResult::kOk;
+}
+
RangeOrBitVector FakeStorage::Search(FilterOp,
SqlValue,
RowMap::Range in) const {
diff --git a/src/trace_processor/db/storage/fake_storage.h b/src/trace_processor/db/storage/fake_storage.h
index 942be1a..2320269 100644
--- a/src/trace_processor/db/storage/fake_storage.h
+++ b/src/trace_processor/db/storage/fake_storage.h
@@ -20,6 +20,7 @@
#include <memory>
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/storage.h"
+#include "src/trace_processor/db/storage/types.h"
namespace perfetto {
namespace trace_processor {
@@ -28,6 +29,9 @@
// Fake implementation of Storage for use in tests.
class FakeStorage final : public Storage {
public:
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
diff --git a/src/trace_processor/db/storage/id_storage.cc b/src/trace_processor/db/storage/id_storage.cc
index 0493f97..bec9b041 100644
--- a/src/trace_processor/db/storage/id_storage.cc
+++ b/src/trace_processor/db/storage/id_storage.cc
@@ -16,12 +16,15 @@
#include "src/trace_processor/db/storage/id_storage.h"
+#include <optional>
+
#include "perfetto/base/logging.h"
-#include "perfetto/trace_processor/basic_types.h"
+#include "perfetto/public/compiler.h"
#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/types.h"
+#include "src/trace_processor/db/storage/utils.h"
#include "src/trace_processor/tp_metatrace.h"
namespace perfetto {
@@ -68,34 +71,112 @@
}
return RangeOrBitVector(std::move(builder).Build());
}
+
} // namespace
+IdStorage::SearchValidationResult IdStorage::ValidateSearchConstraints(
+ SqlValue val,
+ FilterOp op) const {
+ // NULL checks.
+ if (PERFETTO_UNLIKELY(val.is_null())) {
+ if (op == FilterOp::kIsNotNull) {
+ return SearchValidationResult::kAllData;
+ }
+ if (op == FilterOp::kIsNull) {
+ return SearchValidationResult::kNoData;
+ }
+ PERFETTO_DFATAL(
+ "Invalid filter operation. NULL should only be compared with 'IS NULL' "
+ "and 'IS NOT NULL'");
+ return SearchValidationResult::kNoData;
+ }
+
+ // FilterOp checks. Switch so that we get a warning if new FilterOp is not
+ // handled.
+ switch (op) {
+ case FilterOp::kEq:
+ case FilterOp::kNe:
+ case FilterOp::kLt:
+ case FilterOp::kLe:
+ case FilterOp::kGt:
+ case FilterOp::kGe:
+ break;
+ case FilterOp::kIsNull:
+ case FilterOp::kIsNotNull:
+ PERFETTO_FATAL("Invalid constraint");
+ case FilterOp::kGlob:
+ case FilterOp::kRegex:
+ return SearchValidationResult::kNoData;
+ }
+
+ // Type checks.
+ switch (val.type) {
+ case SqlValue::kNull:
+ case SqlValue::kLong:
+ case SqlValue::kDouble:
+ break;
+ case SqlValue::kString:
+ // Any string is always more than any numeric.
+ if (op == FilterOp::kLt || op == FilterOp::kLe) {
+ return Storage::SearchValidationResult::kAllData;
+ }
+ return Storage::SearchValidationResult::kNoData;
+ case SqlValue::kBytes:
+ return Storage::SearchValidationResult::kNoData;
+ }
+
+ // TODO(b/307482437): Remove after adding support for double
+ PERFETTO_CHECK(val.type != SqlValue::kDouble);
+
+ // Bounds of the value.
+ if (PERFETTO_UNLIKELY(val.AsLong() > std::numeric_limits<uint32_t>::max())) {
+ if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ }
+ if (PERFETTO_UNLIKELY(val.AsLong() < std::numeric_limits<uint32_t>::min())) {
+ if (op == FilterOp::kGe || op == FilterOp::kGt || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ }
+
+ return SearchValidationResult::kOk;
+}
+
RangeOrBitVector IdStorage::Search(FilterOp op,
SqlValue sql_val,
- RowMap::Range range) const {
+ RowMap::Range search_range) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "IdStorage::Search",
- [&range, op](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(range.start));
- r->AddArg("End", std::to_string(range.end));
+ [&search_range, op](metatrace::Record* r) {
+ r->AddArg("Start", std::to_string(search_range.start));
+ r->AddArg("End", std::to_string(search_range.end));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
+ PERFETTO_DCHECK(search_range.end <= size_);
+
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(search_range);
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+
+ uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
if (op == FilterOp::kNe) {
- if (sql_val.AsLong() > std::numeric_limits<uint32_t>::max() ||
- sql_val.AsLong() < std::numeric_limits<uint32_t>::min()) {
- return RangeOrBitVector(range);
- }
-
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
- BitVector ret(range.start, false);
- ret.Resize(range.end, true);
+ BitVector ret(search_range.start, false);
+ ret.Resize(search_range.end, true);
ret.Resize(size_, false);
-
ret.Clear(val);
return RangeOrBitVector(std::move(ret));
}
- return RangeOrBitVector(BinarySearchIntrinsic(op, sql_val, range));
+ return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
RangeOrBitVector IdStorage::IndexSearch(FilterOp op,
@@ -109,29 +190,17 @@
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
- // Validate sql_val
- if (PERFETTO_UNLIKELY(sql_val.is_null())) {
- if (op == FilterOp::kIsNotNull) {
- return RangeOrBitVector(Range(indices_size, true));
- }
- return RangeOrBitVector(Range());
+
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, indices_size));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
}
- if (PERFETTO_UNLIKELY(sql_val.AsLong() >
- std::numeric_limits<uint32_t>::max())) {
- if (op == FilterOp::kLe || op == FilterOp::kLt) {
- return RangeOrBitVector(Range(indices_size, true));
- }
- return RangeOrBitVector(Range());
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() <
- std::numeric_limits<uint32_t>::min())) {
- if (op == FilterOp::kGe || op == FilterOp::kGt) {
- return RangeOrBitVector(Range(indices_size, true));
- }
- return RangeOrBitVector(Range());
- }
uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
switch (op) {
@@ -154,46 +223,15 @@
return IndexSearchWithComparator(val, indices, indices_size,
std::greater_equal<uint32_t>());
case FilterOp::kIsNotNull:
- return RangeOrBitVector(Range(indices_size, true));
case FilterOp::kIsNull:
case FilterOp::kGlob:
case FilterOp::kRegex:
- return RangeOrBitVector(Range());
+ PERFETTO_FATAL("Invalid filter operation");
}
PERFETTO_FATAL("FilterOp not matched");
}
-Range IdStorage::BinarySearchIntrinsic(FilterOp op,
- SqlValue sql_val,
- Range range) const {
- PERFETTO_DCHECK(range.end <= size_);
-
- // Validate sql_value
- if (PERFETTO_UNLIKELY(sql_val.is_null())) {
- if (op == FilterOp::kIsNotNull) {
- return range;
- }
- return Range();
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() >
- std::numeric_limits<uint32_t>::max())) {
- if (op == FilterOp::kLe || op == FilterOp::kLt) {
- return range;
- }
- return Range();
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() <
- std::numeric_limits<uint32_t>::min())) {
- if (op == FilterOp::kGe || op == FilterOp::kGt) {
- return range;
- }
- return Range();
- }
-
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
+Range IdStorage::BinarySearchIntrinsic(FilterOp op, Id val, Range range) const {
switch (op) {
case FilterOp::kEq:
return Range(val, val + (range.start <= val && val < range.end));
@@ -206,13 +244,11 @@
case FilterOp::kGt:
return RowMap::Range(std::max(val + 1, range.start), range.end);
case FilterOp::kIsNotNull:
- return range;
case FilterOp::kNe:
- PERFETTO_FATAL("Shouldn't be called");
case FilterOp::kIsNull:
case FilterOp::kGlob:
case FilterOp::kRegex:
- return RowMap::Range();
+ PERFETTO_FATAL("Invalid filter operation");
}
PERFETTO_FATAL("FilterOp not matched");
}
diff --git a/src/trace_processor/db/storage/id_storage.h b/src/trace_processor/db/storage/id_storage.h
index e797028..475c29b 100644
--- a/src/trace_processor/db/storage/id_storage.h
+++ b/src/trace_processor/db/storage/id_storage.h
@@ -16,6 +16,10 @@
#ifndef SRC_TRACE_PROCESSOR_DB_STORAGE_ID_STORAGE_H_
#define SRC_TRACE_PROCESSOR_DB_STORAGE_ID_STORAGE_H_
+#include "perfetto/base/status.h"
+#include "perfetto/ext/base/status_or.h"
+#include "perfetto/trace_processor/basic_types.h"
+#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/types.h"
@@ -34,6 +38,9 @@
public:
explicit IdStorage(uint32_t size) : size_(size) {}
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
@@ -53,9 +60,11 @@
uint32_t size() const override { return size_; }
private:
- BitVector IndexSearch(FilterOp, SqlValue, uint32_t*, uint32_t) const;
+ using Id = uint32_t;
+
+ BitVector IndexSearch(FilterOp, Id, uint32_t*, uint32_t) const;
RowMap::Range BinarySearchIntrinsic(FilterOp op,
- SqlValue val,
+ Id,
RowMap::Range search_range) const;
const uint32_t size_ = 0;
diff --git a/src/trace_processor/db/storage/id_storage_unittest.cc b/src/trace_processor/db/storage/id_storage_unittest.cc
index 57c148d..2262c43 100644
--- a/src/trace_processor/db/storage/id_storage_unittest.cc
+++ b/src/trace_processor/db/storage/id_storage_unittest.cc
@@ -14,17 +14,100 @@
* limitations under the License.
*/
#include "src/trace_processor/db/storage/id_storage.h"
+#include <limits>
#include "src/trace_processor/db/storage/types.h"
#include "test/gtest_and_gmock.h"
namespace perfetto {
namespace trace_processor {
+
+inline bool operator==(const RowMap::Range& a, const RowMap::Range& b) {
+ return std::tie(a.start, a.end) == std::tie(b.start, b.end);
+}
+
namespace storage {
namespace {
using Range = RowMap::Range;
+TEST(IdStorageUnittest, InvalidSearchConstraints) {
+ IdStorage storage(100);
+ Range test_range(10, 20);
+ Range empty_range;
+
+ // NULL checks
+ SqlValue val;
+ val.type = SqlValue::kNull;
+ Range search_result =
+ storage.Search(FilterOp::kIsNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kIsNotNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+
+ // FilterOp checks
+ search_result =
+ storage.Search(FilterOp::kGlob, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kRegex, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ // Type checks
+ search_result =
+ storage.Search(FilterOp::kGe, SqlValue::String("cheese"), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ // Value bounds
+ SqlValue max_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
+ search_result =
+ storage.Search(FilterOp::kGe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kGt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+ search_result =
+ storage.Search(FilterOp::kLt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+ search_result =
+ storage.Search(FilterOp::kNe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+
+ SqlValue min_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
+ search_result =
+ storage.Search(FilterOp::kGe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+ search_result =
+ storage.Search(FilterOp::kGt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+ search_result =
+ storage.Search(FilterOp::kNe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, test_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kLt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+}
+
TEST(IdStorageUnittest, BinarySearchIntrinsicEqSimple) {
IdStorage storage(100);
Range range = storage.Search(FilterOp::kEq, SqlValue::Long(15), Range(10, 20))
diff --git a/src/trace_processor/db/storage/null_storage.cc b/src/trace_processor/db/storage/null_storage.cc
index cac62d6..6de2759 100644
--- a/src/trace_processor/db/storage/null_storage.cc
+++ b/src/trace_processor/db/storage/null_storage.cc
@@ -73,6 +73,12 @@
} // namespace
+Storage::SearchValidationResult NullStorage::ValidateSearchConstraints(
+ SqlValue sql_val,
+ FilterOp op) const {
+ return storage_->ValidateSearchConstraints(sql_val, op);
+}
+
NullStorage::NullStorage(std::unique_ptr<Storage> storage,
const BitVector* non_null)
: storage_(std::move(storage)), non_null_(non_null) {
diff --git a/src/trace_processor/db/storage/null_storage.h b/src/trace_processor/db/storage/null_storage.h
index c1ea44b..3087749 100644
--- a/src/trace_processor/db/storage/null_storage.h
+++ b/src/trace_processor/db/storage/null_storage.h
@@ -34,6 +34,9 @@
public:
NullStorage(std::unique_ptr<Storage> storage, const BitVector* non_null);
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
diff --git a/src/trace_processor/db/storage/numeric_storage.cc b/src/trace_processor/db/storage/numeric_storage.cc
index b7ecfa9..8b5aa50 100644
--- a/src/trace_processor/db/storage/numeric_storage.cc
+++ b/src/trace_processor/db/storage/numeric_storage.cc
@@ -17,12 +17,18 @@
#include "src/trace_processor/db/storage/numeric_storage.h"
+#include <cmath>
#include <cstddef>
#include <string>
+#include "perfetto/base/compiler.h"
+#include "perfetto/base/logging.h"
+#include "perfetto/public/compiler.h"
+#include "perfetto/trace_processor/basic_types.h"
#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
+#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/types.h"
#include "src/trace_processor/db/storage/utils.h"
#include "src/trace_processor/tp_metatrace.h"
@@ -32,7 +38,7 @@
namespace storage {
namespace {
-// All viable numeric values for ColumnTypes.
+using Range = RowMap::Range;
using NumericValue = std::variant<uint32_t, int32_t, int64_t, double_t>;
// Using the fact that binary operators in std are operators() of classes, we
@@ -46,33 +52,22 @@
std::equal_to<T>,
std::not_equal_to<T>>;
-// Based on SqlValue and ColumnType, casts SqlValue to proper type, returns
-// std::nullopt if SqlValue can't be cast and should be considered invalid for
-// comparison.
-inline std::optional<NumericValue> GetNumericTypeVariant(ColumnType type,
- SqlValue val) {
- if (val.is_null())
- return std::nullopt;
-
+// Based on SqlValue and ColumnType, casts SqlValue to proper type. Assumes the
+// |val| and |type| are correct.
+inline NumericValue GetNumericTypeVariant(ColumnType type, SqlValue val) {
switch (type) {
case ColumnType::kDouble:
return val.AsDouble();
case ColumnType::kInt64:
return val.AsLong();
case ColumnType::kInt32:
- if (val.AsLong() > std::numeric_limits<int32_t>::max() ||
- val.AsLong() < std::numeric_limits<int32_t>::min())
- return std::nullopt;
return static_cast<int32_t>(val.AsLong());
case ColumnType::kUint32:
- if (val.AsLong() > std::numeric_limits<uint32_t>::max() ||
- val.AsLong() < std::numeric_limits<uint32_t>::min())
- return std::nullopt;
return static_cast<uint32_t>(val.AsLong());
case ColumnType::kString:
case ColumnType::kDummy:
case ColumnType::kId:
- return std::nullopt;
+ PERFETTO_FATAL("Invalid type");
}
PERFETTO_FATAL("For GCC");
}
@@ -201,72 +196,198 @@
} // namespace
+NumericStorageBase::SearchValidationResult
+NumericStorageBase::ValidateSearchConstraints(SqlValue val, FilterOp op) const {
+ // NULL checks.
+ if (PERFETTO_UNLIKELY(val.is_null())) {
+ if (op == FilterOp::kIsNotNull) {
+ return SearchValidationResult::kAllData;
+ }
+ if (op == FilterOp::kIsNull) {
+ return SearchValidationResult::kNoData;
+ }
+ PERFETTO_FATAL(
+ "Invalid path. NULL should only be compared with 'IS NULL' and 'IS NOT "
+ "NULL'");
+ }
+
+ // FilterOp checks. Switch so that we get a warning if new FilterOp is not
+ // handled.
+ switch (op) {
+ case FilterOp::kEq:
+ case FilterOp::kNe:
+ case FilterOp::kLt:
+ case FilterOp::kLe:
+ case FilterOp::kGt:
+ case FilterOp::kGe:
+ break;
+ case FilterOp::kIsNull:
+ case FilterOp::kIsNotNull:
+ PERFETTO_FATAL("Invalid constraint");
+ case FilterOp::kGlob:
+ case FilterOp::kRegex:
+ return SearchValidationResult::kNoData;
+ }
+
+ // Type checks.
+ switch (val.type) {
+ case SqlValue::kNull:
+ case SqlValue::kLong:
+ case SqlValue::kDouble:
+ break;
+ case SqlValue::kString:
+ // Any string is always more than any numeric.
+ if (op == FilterOp::kLt || op == FilterOp::kLe) {
+ return Storage::SearchValidationResult::kAllData;
+ }
+ return Storage::SearchValidationResult::kNoData;
+ case SqlValue::kBytes:
+ return Storage::SearchValidationResult::kNoData;
+ }
+
+ // TODO(b/307482437): There is currently no support for comparison with double
+ // and it is prevented on QueryExecutor level.
+ if (type_ != ColumnType::kDouble) {
+ PERFETTO_CHECK(val.type != SqlValue::kDouble);
+ }
+
+ // Bounds of the value.
+ enum ExtremeVal { kTooBig, kTooSmall, kOk };
+ ExtremeVal extreme_validator = kOk;
+
+ switch (type_) {
+ case ColumnType::kDouble:
+ // Any value would make a sensible comparison with a double.
+ case ColumnType::kInt64:
+ // TODO(b/307482437): As long as the type is not double there is nothing
+ // to verify here, as all values are going to be in the int64_t limits.
+ break;
+ case ColumnType::kInt32:
+ if (val.AsLong() > std::numeric_limits<int32_t>::max()) {
+ extreme_validator = kTooBig;
+ break;
+ }
+ if (val.AsLong() < std::numeric_limits<int32_t>::min()) {
+ extreme_validator = kTooSmall;
+ break;
+ }
+ break;
+ case ColumnType::kUint32:
+ if (val.AsLong() > std::numeric_limits<uint32_t>::max()) {
+ extreme_validator = kTooBig;
+ break;
+ }
+ if (val.AsLong() < std::numeric_limits<uint32_t>::min()) {
+ extreme_validator = kTooSmall;
+ break;
+ }
+ break;
+ case ColumnType::kString:
+ case ColumnType::kDummy:
+ case ColumnType::kId:
+ break;
+ }
+
+ switch (extreme_validator) {
+ case kOk:
+ return Storage::SearchValidationResult::kOk;
+ case kTooBig:
+ if (op == FilterOp::kLt || op == FilterOp::kLe || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ case kTooSmall:
+ if (op == FilterOp::kGt || op == FilterOp::kGe || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ }
+
+ PERFETTO_FATAL("For GCC");
+}
+
RangeOrBitVector NumericStorageBase::Search(FilterOp op,
- SqlValue value,
- RowMap::Range range) const {
+ SqlValue sql_val,
+ RowMap::Range search_range) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "NumericStorage::Search",
- [&range, op](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(range.start));
- r->AddArg("End", std::to_string(range.end));
+ [&search_range, op](metatrace::Record* r) {
+ r->AddArg("Start", std::to_string(search_range.start));
+ r->AddArg("End", std::to_string(search_range.end));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, search_range.end));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+
+ NumericValue val = GetNumericTypeVariant(type_, sql_val);
+
if (is_sorted_) {
if (op != FilterOp::kNe) {
- return RangeOrBitVector(BinarySearchIntrinsic(op, value, range));
+ return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
// Not equal is a special operation on binary search, as it doesn't define a
// range, and rather just `not` range returned with `equal` operation.
- RowMap::Range r = BinarySearchIntrinsic(FilterOp::kEq, value, range);
+ RowMap::Range r = BinarySearchIntrinsic(FilterOp::kEq, val, search_range);
BitVector bv(r.start, true);
bv.Resize(r.end, false);
- bv.Resize(range.end, true);
+ bv.Resize(search_range.end, true);
return RangeOrBitVector(std::move(bv));
}
- return RangeOrBitVector(LinearSearchInternal(op, value, range));
+
+ return RangeOrBitVector(LinearSearchInternal(op, val, search_range));
}
RangeOrBitVector NumericStorageBase::IndexSearch(FilterOp op,
- SqlValue value,
+ SqlValue sql_val,
uint32_t* indices,
- uint32_t indices_count,
+ uint32_t indices_size,
bool sorted) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "NumericStorage::IndexSearch",
- [indices_count, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices_count));
+ [indices_size, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices_size));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
+
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, indices_size));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+ NumericValue val = GetNumericTypeVariant(type_, sql_val);
if (sorted) {
return RangeOrBitVector(
- BinarySearchExtrinsic(op, value, indices, indices_count));
+ BinarySearchExtrinsic(op, val, indices, indices_size));
}
- return RangeOrBitVector(
- IndexSearchInternal(op, value, indices, indices_count));
+ return RangeOrBitVector(IndexSearchInternal(op, val, indices, indices_size));
}
BitVector NumericStorageBase::LinearSearchInternal(FilterOp op,
- SqlValue sql_val,
+ NumericValue val,
RowMap::Range range) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
- if (op == FilterOp::kIsNotNull)
- return BitVector(range.end, true);
-
- if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return BitVector(range.end, false);
-
BitVector::Builder builder(range.end, range.start);
- if (const auto* u32 = std::get_if<uint32_t>(&*val)) {
+ if (const auto* u32 = std::get_if<uint32_t>(&val)) {
auto* start = static_cast<const uint32_t*>(data_) + range.start;
TypedLinearSearch(*u32, start, op, builder);
- } else if (const auto* i64 = std::get_if<int64_t>(&*val)) {
+ } else if (const auto* i64 = std::get_if<int64_t>(&val)) {
auto* start = static_cast<const int64_t*>(data_) + range.start;
TypedLinearSearch(*i64, start, op, builder);
- } else if (const auto* i32 = std::get_if<int32_t>(&*val)) {
+ } else if (const auto* i32 = std::get_if<int32_t>(&val)) {
auto* start = static_cast<const int32_t*>(data_) + range.start;
TypedLinearSearch(*i32, start, op, builder);
- } else if (const auto* db = std::get_if<double>(&*val)) {
+ } else if (const auto* db = std::get_if<double>(&val)) {
auto* start = static_cast<const double*>(data_) + range.start;
TypedLinearSearch(*db, start, op, builder);
} else {
@@ -277,16 +398,9 @@
BitVector NumericStorageBase::IndexSearchInternal(
FilterOp op,
- SqlValue sql_val,
+ NumericValue val,
uint32_t* indices,
uint32_t indices_count) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
- if (op == FilterOp::kIsNotNull)
- return BitVector(indices_count, true);
-
- if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return BitVector(indices_count, false);
-
BitVector::Builder builder(indices_count);
std::visit(
[this, indices, op, &builder](auto val) {
@@ -299,37 +413,30 @@
},
GetFilterOpVariant<T>(op));
},
- *val);
+ val);
return std::move(builder).Build();
}
RowMap::Range NumericStorageBase::BinarySearchIntrinsic(
FilterOp op,
- SqlValue sql_val,
+ NumericValue val,
RowMap::Range search_range) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
- if (op == FilterOp::kIsNotNull)
- return search_range;
-
- if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return RowMap::Range();
-
switch (op) {
case FilterOp::kEq:
- return RowMap::Range(LowerBoundIntrinsic(data_, *val, search_range),
- UpperBoundIntrinsic(data_, *val, search_range));
+ return RowMap::Range(LowerBoundIntrinsic(data_, val, search_range),
+ UpperBoundIntrinsic(data_, val, search_range));
case FilterOp::kLe: {
return RowMap::Range(search_range.start,
- UpperBoundIntrinsic(data_, *val, search_range));
+ UpperBoundIntrinsic(data_, val, search_range));
}
case FilterOp::kLt:
return RowMap::Range(search_range.start,
- LowerBoundIntrinsic(data_, *val, search_range));
+ LowerBoundIntrinsic(data_, val, search_range));
case FilterOp::kGe:
- return RowMap::Range(LowerBoundIntrinsic(data_, *val, search_range),
+ return RowMap::Range(LowerBoundIntrinsic(data_, val, search_range),
search_range.end);
case FilterOp::kGt:
- return RowMap::Range(UpperBoundIntrinsic(data_, *val, search_range),
+ return RowMap::Range(UpperBoundIntrinsic(data_, val, search_range),
search_range.end);
case FilterOp::kNe:
case FilterOp::kIsNull:
@@ -343,34 +450,26 @@
RowMap::Range NumericStorageBase::BinarySearchExtrinsic(
FilterOp op,
- SqlValue sql_val,
+ NumericValue val,
uint32_t* indices,
uint32_t indices_count) const {
- std::optional<NumericValue> val = GetNumericTypeVariant(type_, sql_val);
-
- if (op == FilterOp::kIsNotNull)
- return RowMap::Range(0, size());
-
- if (!val.has_value() || op == FilterOp::kIsNull || op == FilterOp::kGlob)
- return RowMap::Range();
-
switch (op) {
case FilterOp::kEq:
return RowMap::Range(
- LowerBoundExtrinsic(data_, *val, indices, indices_count),
- UpperBoundExtrinsic(data_, *val, indices, indices_count));
+ LowerBoundExtrinsic(data_, val, indices, indices_count),
+ UpperBoundExtrinsic(data_, val, indices, indices_count));
case FilterOp::kLe:
return RowMap::Range(
- 0, UpperBoundExtrinsic(data_, *val, indices, indices_count));
+ 0, UpperBoundExtrinsic(data_, val, indices, indices_count));
case FilterOp::kLt:
return RowMap::Range(
- 0, LowerBoundExtrinsic(data_, *val, indices, indices_count));
+ 0, LowerBoundExtrinsic(data_, val, indices, indices_count));
case FilterOp::kGe:
return RowMap::Range(
- LowerBoundExtrinsic(data_, *val, indices, indices_count), size_);
+ LowerBoundExtrinsic(data_, val, indices, indices_count), size_);
case FilterOp::kGt:
return RowMap::Range(
- UpperBoundExtrinsic(data_, *val, indices, indices_count), size_);
+ UpperBoundExtrinsic(data_, val, indices, indices_count), size_);
case FilterOp::kNe:
case FilterOp::kIsNull:
case FilterOp::kIsNotNull:
@@ -382,7 +481,6 @@
}
void NumericStorageBase::StableSort(uint32_t* rows, uint32_t rows_size) const {
- NumericValue val = *GetNumericTypeVariant(type_, SqlValue::Long(0));
std::visit(
[this, &rows, rows_size](auto val_data) {
using T = decltype(val_data);
@@ -394,7 +492,7 @@
return first_val < second_val;
});
},
- val);
+ GetNumericTypeVariant(type_, SqlValue::Long(0)));
}
void NumericStorageBase::Sort(uint32_t*, uint32_t) const {
diff --git a/src/trace_processor/db/storage/numeric_storage.h b/src/trace_processor/db/storage/numeric_storage.h
index a91e289..741a8e0 100644
--- a/src/trace_processor/db/storage/numeric_storage.h
+++ b/src/trace_processor/db/storage/numeric_storage.h
@@ -18,6 +18,7 @@
#include <variant>
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/types.h"
@@ -33,6 +34,9 @@
// Storage for all numeric type data (i.e. doubles, int32, int64, uint32).
class NumericStorageBase : public Storage {
public:
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
@@ -59,21 +63,24 @@
: size_(size), data_(data), type_(type), is_sorted_(is_sorted) {}
private:
+ // All viable numeric values for ColumnTypes.
+ using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
+
BitVector LinearSearchInternal(FilterOp op,
- SqlValue val,
+ NumericValue val,
RowMap::Range) const;
BitVector IndexSearchInternal(FilterOp op,
- SqlValue value,
+ NumericValue value,
uint32_t* indices,
uint32_t indices_count) const;
RowMap::Range BinarySearchIntrinsic(FilterOp op,
- SqlValue val,
+ NumericValue val,
RowMap::Range search_range) const;
RowMap::Range BinarySearchExtrinsic(FilterOp op,
- SqlValue val,
+ NumericValue val,
uint32_t* indices,
uint32_t indices_count) const;
diff --git a/src/trace_processor/db/storage/numeric_storage_unittest.cc b/src/trace_processor/db/storage/numeric_storage_unittest.cc
index b6ffb59..e82883f 100644
--- a/src/trace_processor/db/storage/numeric_storage_unittest.cc
+++ b/src/trace_processor/db/storage/numeric_storage_unittest.cc
@@ -20,11 +20,160 @@
namespace perfetto {
namespace trace_processor {
+
+inline bool operator==(const RowMap::Range& a, const RowMap::Range& b) {
+ return std::tie(a.start, a.end) == std::tie(b.start, b.end);
+}
+
namespace storage {
namespace {
using Range = RowMap::Range;
+TEST(IdStorageUnittest, InvalidSearchConstraintsGeneralChecks) {
+ std::vector<uint32_t> data_vec(128);
+ std::iota(data_vec.begin(), data_vec.end(), 0);
+ NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+
+ Range test_range(20, 100);
+ Range full_range(0, 100);
+ Range empty_range;
+
+ // NULL checks
+ SqlValue val;
+ val.type = SqlValue::kNull;
+ Range search_result =
+ storage.Search(FilterOp::kIsNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kIsNotNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ // FilterOp checks
+ search_result =
+ storage.Search(FilterOp::kGlob, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kRegex, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ // Type checks
+ search_result =
+ storage.Search(FilterOp::kGe, SqlValue::String("cheese"), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+}
+
+TEST(IdStorageUnittest, InvalidValueBoundsUint32) {
+ std::vector<uint32_t> data_vec(128);
+ std::iota(data_vec.begin(), data_vec.end(), 0);
+ NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32);
+
+ Range test_range(20, 100);
+ Range full_range(0, 100);
+ Range empty_range;
+
+ SqlValue max_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
+ Range search_result =
+ storage.Search(FilterOp::kGe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kGt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kLt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ SqlValue min_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
+ search_result =
+ storage.Search(FilterOp::kGe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kGt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kLt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+}
+
+TEST(IdStorageUnittest, InvalidValueBoundsInt32) {
+ std::vector<int32_t> data_vec(128);
+ std::iota(data_vec.begin(), data_vec.end(), 0);
+ NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32);
+
+ Range test_range(20, 100);
+ Range full_range(0, 100);
+ Range empty_range;
+
+ SqlValue max_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 10);
+ Range search_result =
+ storage.Search(FilterOp::kGe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kGt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kLt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ SqlValue min_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1);
+ search_result =
+ storage.Search(FilterOp::kGe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kGt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kLt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+}
+
TEST(NumericStorageUnittest, StableSortTrivial) {
std::vector<uint32_t> data_vec{0, 1, 2, 0, 1, 2, 0, 1, 2};
std::vector<uint32_t> out = {0, 1, 2, 3, 4, 5, 6, 7, 8};
diff --git a/src/trace_processor/db/storage/selector_storage.cc b/src/trace_processor/db/storage/selector_storage.cc
index 8a4e93a..934b900 100644
--- a/src/trace_processor/db/storage/selector_storage.cc
+++ b/src/trace_processor/db/storage/selector_storage.cc
@@ -31,6 +31,12 @@
const BitVector* selector)
: inner_(std::move(inner)), selector_(selector) {}
+Storage::SearchValidationResult SelectorStorage::ValidateSearchConstraints(
+ SqlValue sql_val,
+ FilterOp op) const {
+ return inner_->ValidateSearchConstraints(sql_val, op);
+}
+
RangeOrBitVector SelectorStorage::Search(FilterOp op,
SqlValue sql_val,
RowMap::Range in) const {
diff --git a/src/trace_processor/db/storage/selector_storage.h b/src/trace_processor/db/storage/selector_storage.h
index bc8de30..9d368e2 100644
--- a/src/trace_processor/db/storage/selector_storage.h
+++ b/src/trace_processor/db/storage/selector_storage.h
@@ -31,6 +31,9 @@
public:
SelectorStorage(std::unique_ptr<Storage> storage, const BitVector* non_null);
+ Storage::SearchValidationResult ValidateSearchConstraints(SqlValue, FilterOp)
+ const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
diff --git a/src/trace_processor/db/storage/set_id_storage.cc b/src/trace_processor/db/storage/set_id_storage.cc
index 8244ae0..570afb7 100644
--- a/src/trace_processor/db/storage/set_id_storage.cc
+++ b/src/trace_processor/db/storage/set_id_storage.cc
@@ -58,74 +58,139 @@
} // namespace
+SetIdStorage::SearchValidationResult SetIdStorage::ValidateSearchConstraints(
+ SqlValue val,
+ FilterOp op) const {
+ // NULL checks.
+ if (PERFETTO_UNLIKELY(val.is_null())) {
+ if (op == FilterOp::kIsNotNull) {
+ return SearchValidationResult::kAllData;
+ }
+ if (op == FilterOp::kIsNull) {
+ return SearchValidationResult::kNoData;
+ }
+ PERFETTO_FATAL(
+ "Invalid filter operation. NULL should only be compared with 'IS NULL' "
+ "and 'IS NOT NULL'");
+ }
+
+ // FilterOp checks. Switch so that we get a warning if new FilterOp is not
+ // handled.
+ switch (op) {
+ case FilterOp::kEq:
+ case FilterOp::kNe:
+ case FilterOp::kLt:
+ case FilterOp::kLe:
+ case FilterOp::kGt:
+ case FilterOp::kGe:
+ break;
+ case FilterOp::kIsNull:
+ case FilterOp::kIsNotNull:
+ PERFETTO_FATAL("Invalid constraints.");
+ case FilterOp::kGlob:
+ case FilterOp::kRegex:
+ return SearchValidationResult::kNoData;
+ }
+
+ // Type checks.
+ switch (val.type) {
+ case SqlValue::kNull:
+ case SqlValue::kLong:
+ case SqlValue::kDouble:
+ break;
+ case SqlValue::kString:
+ // Any string is always more than any numeric.
+ if (op == FilterOp::kLt || op == FilterOp::kLe) {
+ return Storage::SearchValidationResult::kAllData;
+ }
+ return Storage::SearchValidationResult::kNoData;
+ case SqlValue::kBytes:
+ return Storage::SearchValidationResult::kNoData;
+ }
+
+ // TODO(b/307482437): Remove after adding support for double
+ PERFETTO_CHECK(val.type != SqlValue::kDouble);
+
+ // Bounds of the value.
+ if (PERFETTO_UNLIKELY(val.AsLong() > std::numeric_limits<uint32_t>::max())) {
+ if (op == FilterOp::kLe || op == FilterOp::kLt || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ }
+ if (PERFETTO_UNLIKELY(val.AsLong() < std::numeric_limits<uint32_t>::min())) {
+ if (op == FilterOp::kGe || op == FilterOp::kGt || op == FilterOp::kNe) {
+ return SearchValidationResult::kAllData;
+ }
+ return SearchValidationResult::kNoData;
+ }
+
+ return SearchValidationResult::kOk;
+}
+
RangeOrBitVector SetIdStorage::Search(FilterOp op,
SqlValue sql_val,
- RowMap::Range range) const {
+ RowMap::Range search_range) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::Search",
- [&range, op](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(range.start));
- r->AddArg("End", std::to_string(range.end));
+ [&search_range, op](metatrace::Record* r) {
+ r->AddArg("Start", std::to_string(search_range.start));
+ r->AddArg("End", std::to_string(search_range.end));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
- PERFETTO_DCHECK(range.end <= size());
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, search_range.end));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+
+ PERFETTO_DCHECK(search_range.end <= size());
+ uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
if (op == FilterOp::kNe) {
- if (sql_val.is_null()) {
- return RangeOrBitVector(Range());
- }
// Not equal is a special operation on binary search, as it doesn't define a
// range, and rather just `not` range returned with `equal` operation.
RowMap::Range eq_range =
- BinarySearchIntrinsic(FilterOp::kEq, sql_val, range);
- BitVector bv(range.start, false);
+ BinarySearchIntrinsic(FilterOp::kEq, val, search_range);
+ BitVector bv(search_range.start, false);
bv.Resize(eq_range.start, true);
bv.Resize(eq_range.end, false);
- bv.Resize(range.end, true);
+ bv.Resize(search_range.end, true);
return RangeOrBitVector(std::move(bv));
}
- return RangeOrBitVector(BinarySearchIntrinsic(op, sql_val, range));
+ return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
}
RangeOrBitVector SetIdStorage::IndexSearch(FilterOp op,
SqlValue sql_val,
uint32_t* indices,
- uint32_t indices_count,
+ uint32_t indices_size,
bool) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "SetIdStorage::IndexSearch",
- [indices_count, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices_count));
+ [indices_size, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices_size));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
- // Validate sql_val
- if (PERFETTO_UNLIKELY(sql_val.is_null())) {
- if (op == FilterOp::kIsNotNull) {
- return RangeOrBitVector(Range(indices_count, true));
- }
- return RangeOrBitVector(Range());
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, indices_size));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
}
- if (PERFETTO_UNLIKELY(sql_val.AsLong() >
- std::numeric_limits<uint32_t>::max())) {
- if (op == FilterOp::kLe || op == FilterOp::kLt) {
- return RangeOrBitVector(Range(indices_count, true));
- }
- return RangeOrBitVector(Range());
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() <
- std::numeric_limits<uint32_t>::min())) {
- if (op == FilterOp::kGe || op == FilterOp::kGt) {
- return RangeOrBitVector(Range(indices_count, true));
- }
- return RangeOrBitVector(Range());
- }
uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
- BitVector::Builder builder(indices_count);
+ 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.
@@ -155,7 +220,7 @@
std::greater_equal<uint32_t>(), builder);
break;
case FilterOp::kIsNotNull:
- return RangeOrBitVector(Range(0, indices_count));
+ return RangeOrBitVector(Range(0, indices_size));
case FilterOp::kIsNull:
return RangeOrBitVector(Range());
case FilterOp::kGlob:
@@ -166,34 +231,8 @@
}
Range SetIdStorage::BinarySearchIntrinsic(FilterOp op,
- SqlValue sql_val,
+ SetId val,
Range range) const {
- // Validate sql_value
- if (PERFETTO_UNLIKELY(sql_val.is_null())) {
- if (op == FilterOp::kIsNotNull) {
- return range;
- }
- return Range();
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() >
- std::numeric_limits<uint32_t>::max())) {
- if (op == FilterOp::kLe || op == FilterOp::kLt) {
- return range;
- }
- return Range();
- }
-
- if (PERFETTO_UNLIKELY(sql_val.AsLong() <
- std::numeric_limits<uint32_t>::min())) {
- if (op == FilterOp::kGe || op == FilterOp::kGt) {
- return range;
- }
- return Range();
- }
-
- uint32_t val = static_cast<uint32_t>(sql_val.AsLong());
-
switch (op) {
case FilterOp::kEq:
return Range(LowerBoundIntrinsic(values_->data(), val, range),
diff --git a/src/trace_processor/db/storage/set_id_storage.h b/src/trace_processor/db/storage/set_id_storage.h
index ad9fd1a..6886bef 100644
--- a/src/trace_processor/db/storage/set_id_storage.h
+++ b/src/trace_processor/db/storage/set_id_storage.h
@@ -36,6 +36,9 @@
explicit SetIdStorage(const std::vector<uint32_t>* data) : values_(data) {}
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
@@ -57,9 +60,9 @@
}
private:
- BitVector IndexSearch(FilterOp, SqlValue, uint32_t*, uint32_t) const;
- RowMap::Range BinarySearchIntrinsic(FilterOp op,
- SqlValue val,
+ BitVector IndexSearch(FilterOp, SetId, uint32_t*, uint32_t) const;
+ RowMap::Range BinarySearchIntrinsic(FilterOp,
+ SetId,
RowMap::Range search_range) const;
// TODO(b/307482437): After the migration vectors should be owned by storage,
diff --git a/src/trace_processor/db/storage/set_id_storage_unittest.cc b/src/trace_processor/db/storage/set_id_storage_unittest.cc
index f487dfa..658b731 100644
--- a/src/trace_processor/db/storage/set_id_storage_unittest.cc
+++ b/src/trace_processor/db/storage/set_id_storage_unittest.cc
@@ -19,11 +19,96 @@
namespace perfetto {
namespace trace_processor {
+
+inline bool operator==(const RowMap::Range& a, const RowMap::Range& b) {
+ return std::tie(a.start, a.end) == std::tie(b.start, b.end);
+}
+
namespace storage {
namespace {
using Range = RowMap::Range;
+TEST(IdStorageUnittest, InvalidSearchConstraints) {
+ std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
+ SetIdStorage storage(&storage_data);
+
+ Range test_range(3, 9);
+ Range full_range(0, 9);
+ Range empty_range;
+
+ // NULL checks
+ SqlValue val;
+ val.type = SqlValue::kNull;
+ Range search_result =
+ storage.Search(FilterOp::kIsNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kIsNotNull, val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ // FilterOp checks
+ search_result =
+ storage.Search(FilterOp::kGlob, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kRegex, SqlValue::Long(15), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ // Type checks
+ search_result =
+ storage.Search(FilterOp::kGe, SqlValue::String("cheese"), test_range)
+ .TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ // Value bounds
+ SqlValue max_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
+ search_result =
+ storage.Search(FilterOp::kGe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kGt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kLt, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, max_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ SqlValue min_val = SqlValue::Long(
+ static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
+ search_result =
+ storage.Search(FilterOp::kGe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kGt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+ search_result =
+ storage.Search(FilterOp::kNe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, full_range);
+
+ search_result =
+ storage.Search(FilterOp::kLe, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kLt, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+ search_result =
+ storage.Search(FilterOp::kEq, min_val, test_range).TakeIfRange();
+ ASSERT_EQ(search_result, empty_range);
+}
+
TEST(SetIdStorageUnittest, SearchEqSimple) {
std::vector<uint32_t> storage_data{0, 0, 0, 3, 3, 3, 6, 6, 6, 9, 9, 9};
diff --git a/src/trace_processor/db/storage/storage.h b/src/trace_processor/db/storage/storage.h
index 605329b..2a9c9fb 100644
--- a/src/trace_processor/db/storage/storage.h
+++ b/src/trace_processor/db/storage/storage.h
@@ -16,7 +16,6 @@
#ifndef SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_H_
#define SRC_TRACE_PROCESSOR_DB_STORAGE_STORAGE_H_
-#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/db/storage/types.h"
@@ -34,8 +33,24 @@
public:
using StorageProto = protos::pbzero::SerializedColumn_Storage;
+ enum class SearchValidationResult { kOk = 0, kAllData = 1, kNoData = 2 };
+
virtual ~Storage();
+ // Verifies whether any further filtering is needed and if not, whether the
+ // search would return all values or none of them. This allows for skipping
+ // the |Search| and |IndexSearch| in special cases.
+ //
+ // Notes for callers:
+ // * This function is being called by Search and IndexSearch and there is no
+ // need to call it before searches.
+ // * The SqlValue and FilterOp have to be valid in Sqlite: it will crash if
+ // either: value is NULL and operation is different than "IS NULL" and "IS
+ // NOT NULL" or the operation is "IS NULL" and "IS NOT NULL" and value is
+ // different than NULL.
+ virtual SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const = 0;
+
// Searches for elements which match |op| and |value| between |range.start|
// and |range.end|.
//
@@ -49,9 +64,7 @@
// optimize based on this.
// * Implementations should ensure that, if they return a BitVector, it is
// precisely of size |range.end|.
- virtual RangeOrBitVector Search(FilterOp op,
- SqlValue value,
- RowMap::Range range) const = 0;
+ virtual RangeOrBitVector Search(FilterOp, SqlValue, RowMap::Range) const = 0;
// Searches for elements which match |op| and |value| at the positions given
// by |indices| array. The |sorted| flag allows the caller to specify if the
@@ -69,8 +82,8 @@
// Notes for implementors:
// * Implementations should ensure that, if they return a BitVector, it is
// precisely of size |indices_count|.
- virtual RangeOrBitVector IndexSearch(FilterOp op,
- SqlValue value,
+ virtual RangeOrBitVector IndexSearch(FilterOp,
+ SqlValue,
uint32_t* indices,
uint32_t indices_count,
bool sorted) const = 0;
diff --git a/src/trace_processor/db/storage/string_storage.cc b/src/trace_processor/db/storage/string_storage.cc
index d1d88b7..d9c9b98 100644
--- a/src/trace_processor/db/storage/string_storage.cc
+++ b/src/trace_processor/db/storage/string_storage.cc
@@ -19,7 +19,6 @@
#include "perfetto/ext/base/scoped_file.h"
#include "perfetto/ext/base/status_or.h"
#include "perfetto/ext/base/string_utils.h"
-#include "perfetto/trace_processor/basic_types.h"
#include "protos/perfetto/trace_processor/serialization.pbzero.h"
#include "perfetto/base/logging.h"
@@ -27,6 +26,7 @@
#include "src/trace_processor/containers/null_term_string_view.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/containers/string_pool.h"
+#include "src/trace_processor/db/storage/storage.h"
#include "src/trace_processor/db/storage/types.h"
#include "src/trace_processor/db/storage/utils.h"
@@ -163,55 +163,97 @@
} // namespace
+StringStorage::SearchValidationResult StringStorage::ValidateSearchConstraints(
+ SqlValue val,
+ FilterOp op) const {
+ // Type checks.
+ switch (val.type) {
+ case SqlValue::kNull:
+ case SqlValue::kString:
+ break;
+ case SqlValue::kLong:
+ case SqlValue::kDouble:
+ // Any string is always more than any numeric.
+ if (op == FilterOp::kGt || op == FilterOp::kGe) {
+ return Storage::SearchValidationResult::kAllData;
+ }
+ return Storage::SearchValidationResult::kNoData;
+ case SqlValue::kBytes:
+ return Storage::SearchValidationResult::kNoData;
+ }
+
+ return SearchValidationResult::kOk;
+}
+
RangeOrBitVector StringStorage::Search(FilterOp op,
- SqlValue value,
- RowMap::Range range) const {
- PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::LinearSearch",
- [&range, op](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(range.start));
- r->AddArg("End", std::to_string(range.end));
+ SqlValue sql_val,
+ Range search_range) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::Search",
+ [&search_range, op](metatrace::Record* r) {
+ r->AddArg("Start", std::to_string(search_range.start));
+ r->AddArg("End", std::to_string(search_range.end));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, search_range.end));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+
if (is_sorted_) {
if (op != FilterOp::kNe) {
- return RangeOrBitVector(BinarySearchIntrinsic(op, value, range));
+ return RangeOrBitVector(BinarySearchIntrinsic(op, sql_val, search_range));
}
// Not equal is a special operation on binary search, as it doesn't define
// a range, and rather just `not` range returned with `equal` operation.
- RowMap::Range r = BinarySearchIntrinsic(FilterOp::kEq, value, range);
+ Range r = BinarySearchIntrinsic(FilterOp::kEq, sql_val, search_range);
BitVector bv(r.start, true);
- bv.Resize(r.end, false);
- bv.Resize(range.end, true);
+ bv.Resize(r.end);
+ bv.Resize(search_range.end, true);
return RangeOrBitVector(std::move(bv));
}
- return RangeOrBitVector(LinearSearchInternal(op, value, range));
+ return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
}
RangeOrBitVector StringStorage::IndexSearch(FilterOp op,
- SqlValue value,
+ SqlValue sql_val,
uint32_t* indices,
- uint32_t indices_count,
- bool sorted) const {
+ uint32_t indices_size,
+ bool indices_sorted) const {
PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::IndexSearch",
- [indices_count, op](metatrace::Record* r) {
- r->AddArg("Count", std::to_string(indices_count));
+ [indices_size, op](metatrace::Record* r) {
+ r->AddArg("Count", std::to_string(indices_size));
r->AddArg("Op",
std::to_string(static_cast<uint32_t>(op)));
});
- if (sorted) {
+ // After this switch we assume the search is valid.
+ switch (ValidateSearchConstraints(sql_val, op)) {
+ case SearchValidationResult::kOk:
+ break;
+ case SearchValidationResult::kAllData:
+ return RangeOrBitVector(Range(0, indices_size));
+ case SearchValidationResult::kNoData:
+ return RangeOrBitVector(Range());
+ }
+
+ if (indices_sorted) {
return RangeOrBitVector(
- BinarySearchExtrinsic(op, value, indices, indices_count));
+ BinarySearchExtrinsic(op, sql_val, indices, indices_size));
}
return RangeOrBitVector(
- IndexSearchInternal(op, value, indices, indices_count, sorted));
+ IndexSearchInternal(op, sql_val, indices, indices_size));
}
-BitVector StringStorage::LinearSearchInternal(FilterOp op,
- SqlValue sql_val,
- RowMap::Range range) const {
+BitVector StringStorage::LinearSearch(FilterOp op,
+ SqlValue sql_val,
+ RowMap::Range range) const {
if (sql_val.is_null() &&
(op != FilterOp::kIsNotNull && op != FilterOp::kIsNull)) {
return BitVector(range.end, false);
@@ -227,16 +269,6 @@
? StringPool::Id::Null()
: string_pool_->InternString(base::StringView(sql_val.AsString()));
const StringPool::Id* start = values_->data() + range.start;
- PERFETTO_TP_TRACE(
- metatrace::Category::DB, "StringStorage::Search",
- [range, op, &sql_val](metatrace::Record* r) {
- r->AddArg("Start", std::to_string(range.start));
- r->AddArg("End", std::to_string(range.end));
- r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
- r->AddArg("String", sql_val.type == SqlValue::Type::kString
- ? sql_val.AsString()
- : "NULL");
- });
BitVector::Builder builder(range.end, range.start);
switch (op) {
@@ -318,11 +350,11 @@
return std::move(builder).Build();
}
-RangeOrBitVector StringStorage::IndexSearchInternal(FilterOp op,
- SqlValue sql_val,
- uint32_t* indices,
- uint32_t indices_size,
- bool) const {
+RangeOrBitVector StringStorage::IndexSearchInternal(
+ FilterOp op,
+ SqlValue sql_val,
+ uint32_t* indices,
+ uint32_t indices_size) const {
if (sql_val.is_null() &&
(op != FilterOp::kIsNotNull && op != FilterOp::kIsNull)) {
return RangeOrBitVector(Range());
diff --git a/src/trace_processor/db/storage/string_storage.h b/src/trace_processor/db/storage/string_storage.h
index 9f14917..1e89f24 100644
--- a/src/trace_processor/db/storage/string_storage.h
+++ b/src/trace_processor/db/storage/string_storage.h
@@ -16,6 +16,7 @@
#ifndef SRC_TRACE_PROCESSOR_DB_STORAGE_STRING_STORAGE_H_
#define SRC_TRACE_PROCESSOR_DB_STORAGE_STRING_STORAGE_H_
+#include "perfetto/trace_processor/basic_types.h"
#include "src/trace_processor/containers/row_map.h"
#include "src/trace_processor/containers/string_pool.h"
#include "src/trace_processor/db/storage/storage.h"
@@ -38,6 +39,9 @@
bool is_sorted = false)
: values_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
RangeOrBitVector Search(FilterOp op,
SqlValue value,
RowMap::Range range) const override;
@@ -58,13 +62,12 @@
}
private:
- BitVector LinearSearchInternal(FilterOp, SqlValue, RowMap::Range) const;
+ BitVector LinearSearch(FilterOp, SqlValue, RowMap::Range) const;
RangeOrBitVector IndexSearchInternal(FilterOp op,
SqlValue sql_val,
uint32_t* indices,
- uint32_t indices_size,
- bool) const;
+ uint32_t indices_size) const;
RowMap::Range BinarySearchExtrinsic(FilterOp,
SqlValue,
