tp: add dense storage to CEngine am: 60314bbfe3
Original change: https://android-review.googlesource.com/c/platform/external/perfetto/+/2863852
Change-Id: Iddeee82ebf79a0e909bb02d9ec83019a5655a626
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>
diff --git a/Android.bp b/Android.bp
index fe9bd0a..ef5737b 100644
--- a/Android.bp
+++ b/Android.bp
@@ -10974,6 +10974,7 @@
name: "perfetto_src_trace_processor_db_storage_storage",
srcs: [
"src/trace_processor/db/storage/arrangement_storage.cc",
+ "src/trace_processor/db/storage/dense_null_storage.cc",
"src/trace_processor/db/storage/dummy_storage.cc",
"src/trace_processor/db/storage/id_storage.cc",
"src/trace_processor/db/storage/null_storage.cc",
@@ -10990,6 +10991,7 @@
name: "perfetto_src_trace_processor_db_storage_unittests",
srcs: [
"src/trace_processor/db/storage/arrangement_storage_unittest.cc",
+ "src/trace_processor/db/storage/dense_null_storage_unittest.cc",
"src/trace_processor/db/storage/id_storage_unittest.cc",
"src/trace_processor/db/storage/null_storage_unittest.cc",
"src/trace_processor/db/storage/numeric_storage_unittest.cc",
diff --git a/BUILD b/BUILD
index cddab6b..5c8fbe6 100644
--- a/BUILD
+++ b/BUILD
@@ -1302,6 +1302,8 @@
srcs = [
"src/trace_processor/db/storage/arrangement_storage.cc",
"src/trace_processor/db/storage/arrangement_storage.h",
+ "src/trace_processor/db/storage/dense_null_storage.cc",
+ "src/trace_processor/db/storage/dense_null_storage.h",
"src/trace_processor/db/storage/dummy_storage.cc",
"src/trace_processor/db/storage/dummy_storage.h",
"src/trace_processor/db/storage/id_storage.cc",
diff --git a/protos/perfetto/trace_processor/serialization.proto b/protos/perfetto/trace_processor/serialization.proto
index e79b7c9..f559bd9 100644
--- a/protos/perfetto/trace_processor/serialization.proto
+++ b/protos/perfetto/trace_processor/serialization.proto
@@ -92,6 +92,12 @@
optional Storage storage = 2;
}
+ // A schema for serialization of |storage::DenseNullStorage|.
+ message DenseNullStorage {
+ optional BitVector bit_vector = 1;
+ optional Storage storage = 2;
+ }
+
oneof data {
DummyStorage dummy_storage = 1;
IdStorage id_storage = 2;
@@ -101,6 +107,7 @@
NullStorage null_storage = 6;
ArrangementStorage arrangement_storage = 7;
SelectorStorage selector_storage = 8;
+ DenseNullStorage dense_null_storage = 9;
}
}
diff --git a/src/trace_processor/db/query_executor.cc b/src/trace_processor/db/query_executor.cc
index c77cb38..046aee4 100644
--- a/src/trace_processor/db/query_executor.cc
+++ b/src/trace_processor/db/query_executor.cc
@@ -28,6 +28,7 @@
#include "src/trace_processor/containers/string_pool.h"
#include "src/trace_processor/db/query_executor.h"
#include "src/trace_processor/db/storage/arrangement_storage.h"
+#include "src/trace_processor/db/storage/dense_null_storage.h"
#include "src/trace_processor/db/storage/dummy_storage.h"
#include "src/trace_processor/db/storage/id_storage.h"
#include "src/trace_processor/db/storage/null_storage.h"
@@ -170,9 +171,6 @@
(c.op != FilterOp::kIsNull && c.op != FilterOp::kIsNotNull &&
(int_with_double || double_with_int));
- // Dense columns.
- use_legacy = use_legacy || col.IsDense();
-
// Extrinsically sorted columns.
use_legacy = use_legacy ||
(col.IsSorted() && col.overlay().row_map().IsIndexVector());
@@ -255,8 +253,13 @@
// 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());
+ if (col.IsDense()) {
+ storage = std::make_unique<storage::DenseNullStorage>(
+ std::move(storage), col.storage_base().bv());
+ } else {
+ storage = std::make_unique<storage::NullStorage>(
+ std::move(storage), col.storage_base().bv());
+ }
}
if (col.overlay().row_map().IsIndexVector()) {
storage = std::make_unique<storage::ArrangementStorage>(
diff --git a/src/trace_processor/db/storage/BUILD.gn b/src/trace_processor/db/storage/BUILD.gn
index 55b7eb8..bd80ec7 100644
--- a/src/trace_processor/db/storage/BUILD.gn
+++ b/src/trace_processor/db/storage/BUILD.gn
@@ -18,6 +18,8 @@
sources = [
"arrangement_storage.cc",
"arrangement_storage.h",
+ "dense_null_storage.cc",
+ "dense_null_storage.h",
"dummy_storage.cc",
"dummy_storage.h",
"id_storage.cc",
@@ -67,6 +69,7 @@
testonly = true
sources = [
"arrangement_storage_unittest.cc",
+ "dense_null_storage_unittest.cc",
"id_storage_unittest.cc",
"null_storage_unittest.cc",
"numeric_storage_unittest.cc",
diff --git a/src/trace_processor/db/storage/dense_null_storage.cc b/src/trace_processor/db/storage/dense_null_storage.cc
new file mode 100644
index 0000000..9f764a4
--- /dev/null
+++ b/src/trace_processor/db/storage/dense_null_storage.cc
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/db/storage/dense_null_storage.h"
+
+#include <cstdint>
+#include <variant>
+
+#include "protos/perfetto/trace_processor/serialization.pbzero.h"
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/storage/types.h"
+#include "src/trace_processor/tp_metatrace.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace storage {
+
+DenseNullStorage::DenseNullStorage(std::unique_ptr<Storage> inner,
+ const BitVector* non_null)
+ : inner_(std::move(inner)), non_null_(non_null) {}
+
+Storage::SearchValidationResult DenseNullStorage::ValidateSearchConstraints(
+ SqlValue sql_val,
+ FilterOp op) const {
+ return inner_->ValidateSearchConstraints(sql_val, op);
+}
+
+RangeOrBitVector DenseNullStorage::Search(FilterOp op,
+ SqlValue sql_val,
+ RowMap::Range in) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "DenseNullStorage::Search");
+
+ RangeOrBitVector inner_res = inner_->Search(op, sql_val, in);
+ BitVector res;
+ if (inner_res.IsRange()) {
+ // If the inner storage returns a range, mask out the appropriate values in
+ // |non_null_| which matches the range. Then, resize to |in.end| as this
+ // is mandated by the API contract of |Storage::Search|.
+ RowMap::Range inner_range = std::move(inner_res).TakeIfRange();
+ PERFETTO_DCHECK(inner_range.end <= in.end);
+ PERFETTO_DCHECK(inner_range.start >= in.start);
+ res = non_null_->IntersectRange(inner_range.start, inner_range.end);
+ res.Resize(in.end, false);
+ } else {
+ res = std::move(inner_res).TakeIfBitVector();
+ }
+ PERFETTO_DCHECK(res.size() == in.end);
+
+ if (op == FilterOp::kIsNull) {
+ // For IS NULL, we need to add any rows in |non_null_| which are zeros: we
+ // do this by taking the appropriate number of rows, inverting it and then
+ // bitwise or-ing the result with it.
+ BitVector non_null_copy = non_null_->Copy();
+ non_null_copy.Resize(in.end);
+ non_null_copy.Not();
+ res.Or(non_null_copy);
+ } else {
+ // For anything else, we just need to ensure that any rows which are null
+ // are removed as they would not match.
+ res.And(*non_null_);
+ }
+ return RangeOrBitVector(std::move(res));
+}
+
+RangeOrBitVector DenseNullStorage::IndexSearch(FilterOp op,
+ SqlValue sql_val,
+ uint32_t* indices,
+ uint32_t indices_size,
+ bool sorted) const {
+ PERFETTO_TP_TRACE(metatrace::Category::DB, "DenseNullStorage::IndexSearch");
+
+ RangeOrBitVector inner_res =
+ inner_->IndexSearch(op, sql_val, indices, indices_size, sorted);
+ if (inner_res.IsRange()) {
+ RowMap::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[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[i]));
+ }
+ BitVector non_null = std::move(builder).Build();
+ PERFETTO_DCHECK(non_null.size() == indices_size);
+
+ BitVector res = std::move(inner_res).TakeIfBitVector();
+ PERFETTO_DCHECK(res.size() == indices_size);
+
+ if (op == FilterOp::kIsNull) {
+ BitVector null = std::move(non_null);
+ null.Not();
+ res.Or(null);
+ } else {
+ res.And(non_null);
+ }
+ return RangeOrBitVector(std::move(res));
+}
+
+void DenseNullStorage::StableSort(uint32_t*, uint32_t) const {
+ // TODO(b/307482437): Implement.
+ PERFETTO_FATAL("Not implemented");
+}
+
+void DenseNullStorage::Sort(uint32_t*, uint32_t) const {
+ // TODO(b/307482437): Implement.
+ PERFETTO_FATAL("Not implemented");
+}
+
+void DenseNullStorage::Serialize(StorageProto* storage) const {
+ auto* null_storage = storage->set_dense_null_storage();
+ non_null_->Serialize(null_storage->set_bit_vector());
+ inner_->Serialize(null_storage->set_storage());
+}
+
+} // namespace storage
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/db/storage/dense_null_storage.h b/src/trace_processor/db/storage/dense_null_storage.h
new file mode 100644
index 0000000..ec7b6e9
--- /dev/null
+++ b/src/trace_processor/db/storage/dense_null_storage.h
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef SRC_TRACE_PROCESSOR_DB_STORAGE_DENSE_NULL_STORAGE_H_
+#define SRC_TRACE_PROCESSOR_DB_STORAGE_DENSE_NULL_STORAGE_H_
+
+#include <memory>
+#include <variant>
+
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/storage/storage.h"
+#include "src/trace_processor/db/storage/types.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace storage {
+
+// Storage which introduces the layer of nullability but without changing the
+// "spacing" of the underlying storage i.e. this storage simply "masks" out
+// rows in the underlying storage with nulls.
+class DenseNullStorage : public Storage {
+ public:
+ DenseNullStorage(std::unique_ptr<Storage> inner, const BitVector* non_null);
+
+ SearchValidationResult ValidateSearchConstraints(SqlValue,
+ FilterOp) const override;
+
+ RangeOrBitVector Search(FilterOp op,
+ SqlValue value,
+ RowMap::Range range) const override;
+
+ RangeOrBitVector IndexSearch(FilterOp op,
+ SqlValue value,
+ uint32_t* indices,
+ uint32_t indices_count,
+ bool sorted) const override;
+
+ void StableSort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Sort(uint32_t* rows, uint32_t rows_size) const override;
+
+ void Serialize(StorageProto*) const override;
+
+ uint32_t size() const override { return non_null_->size(); }
+
+ private:
+ std::unique_ptr<Storage> inner_;
+ const BitVector* non_null_ = nullptr;
+};
+
+} // namespace storage
+} // namespace trace_processor
+} // namespace perfetto
+
+#endif // SRC_TRACE_PROCESSOR_DB_STORAGE_DENSE_NULL_STORAGE_H_
diff --git a/src/trace_processor/db/storage/dense_null_storage_unittest.cc b/src/trace_processor/db/storage/dense_null_storage_unittest.cc
new file mode 100644
index 0000000..d8ec93c
--- /dev/null
+++ b/src/trace_processor/db/storage/dense_null_storage_unittest.cc
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/db/storage/dense_null_storage.h"
+#include <cstdint>
+#include <memory>
+#include <vector>
+
+#include "src/trace_processor/containers/bit_vector.h"
+#include "src/trace_processor/db/storage/fake_storage.h"
+#include "src/trace_processor/db/storage/numeric_storage.h"
+#include "src/trace_processor/db/storage/types.h"
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace storage {
+namespace {
+
+using testing::ElementsAre;
+using testing::IsEmpty;
+using Range = RowMap::Range;
+
+std::vector<uint32_t> ToIndexVector(RangeOrBitVector& r_or_bv) {
+ RowMap rm;
+ if (r_or_bv.IsBitVector()) {
+ rm = RowMap(std::move(r_or_bv).TakeIfBitVector());
+ } else {
+ Range range = std::move(r_or_bv).TakeIfRange();
+ rm = RowMap(range.start, range.end);
+ }
+ return rm.GetAllIndices();
+}
+
+TEST(DenseNullStorage, NoFilteringSearch) {
+ std::vector<uint32_t> data{0, 1, 0, 1, 0};
+ auto numeric =
+ std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
+
+ BitVector bv{0, 1, 0, 1, 0};
+ DenseNullStorage storage(std::move(numeric), &bv);
+
+ auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(1, 3));
+}
+
+TEST(DenseNullStorage, RestrictInputSearch) {
+ std::vector<uint32_t> data{0, 1, 0, 1, 0};
+ auto numeric =
+ std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
+
+ BitVector bv{0, 1, 0, 1, 0};
+ DenseNullStorage storage(std::move(numeric), &bv);
+
+ auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(1, 3));
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(1));
+}
+
+TEST(DenseNullStorage, RangeFilterSearch) {
+ auto fake = FakeStorage::SearchSubset(5, Range(1, 3));
+
+ BitVector bv{0, 1, 0, 1, 0};
+ DenseNullStorage storage(std::move(fake), &bv);
+
+ auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(1));
+}
+
+TEST(DenseNullStorage, BitvectorFilterSearch) {
+ auto fake = FakeStorage::SearchSubset(5, BitVector({0, 1, 1, 0, 0}));
+
+ BitVector bv{0, 1, 0, 1, 0};
+ DenseNullStorage storage(std::move(fake), &bv);
+
+ auto res = storage.Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(1));
+}
+
+TEST(DenseNullStorage, IsNullSearch) {
+ auto fake = FakeStorage::SearchSubset(5, BitVector({1, 1, 0, 0, 1}));
+
+ BitVector bv{1, 0, 0, 1, 1};
+ DenseNullStorage storage(std::move(fake), &bv);
+
+ auto res = storage.Search(FilterOp::kIsNull, SqlValue(), Range(0, 5));
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(0, 1, 2, 4));
+}
+
+TEST(DenseNullStorage, IndexSearch) {
+ std::vector<uint32_t> data{1, 0, 0, 1, 1, 1};
+ auto numeric =
+ std::make_unique<NumericStorage<uint32_t>>(&data, ColumnType::kUint32);
+
+ BitVector bv{1, 0, 0, 1, 1, 1};
+ DenseNullStorage storage(std::move(numeric), &bv);
+
+ std::vector<uint32_t> index({5, 2, 3, 4, 1});
+ auto res = storage.IndexSearch(FilterOp::kGe, SqlValue::Long(0), index.data(),
+ static_cast<uint32_t>(index.size()), false);
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(0, 2, 3));
+}
+
+TEST(DenseNullStorage, IsNullIndexSearch) {
+ auto fake = FakeStorage::SearchSubset(6, BitVector({0, 0, 0, 1, 1, 1}));
+
+ BitVector bv{0, 1, 0, 1, 1, 1};
+ DenseNullStorage storage(std::move(fake), &bv);
+
+ std::vector<uint32_t> index({5, 2, 3, 4, 1});
+ auto res = storage.IndexSearch(FilterOp::kIsNull, SqlValue(), index.data(),
+ static_cast<uint32_t>(index.size()), false);
+ ASSERT_THAT(ToIndexVector(res), ElementsAre(0, 1, 2, 3));
+}
+
+} // namespace
+} // namespace storage
+} // namespace trace_processor
+} // namespace perfetto
