1 /*
2 * Copyright (C) 2023 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/db/column/dense_null_overlay.h"
18
19 #include <cstdint>
20 #include <memory>
21 #include <utility>
22 #include <vector>
23
24 #include "perfetto/trace_processor/basic_types.h"
25 #include "src/trace_processor/containers/bit_vector.h"
26 #include "src/trace_processor/db/column/data_layer.h"
27 #include "src/trace_processor/db/column/fake_storage.h"
28 #include "src/trace_processor/db/column/numeric_storage.h"
29 #include "src/trace_processor/db/column/types.h"
30 #include "src/trace_processor/db/column/utils.h"
31 #include "test/gtest_and_gmock.h"
32
33 namespace perfetto::trace_processor::column {
34 namespace {
35
36 using testing::ElementsAre;
37 using testing::IsEmpty;
38 using testing::UnorderedElementsAre;
39
40 using Indices = DataLayerChain::Indices;
41 using OrderedIndices = DataLayerChain::OrderedIndices;
42
TEST(DenseNullOverlay,NoFilteringSearch)43 TEST(DenseNullOverlay, NoFilteringSearch) {
44 std::vector<uint32_t> data{0, 1, 0, 1, 0};
45 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
46 &data, ColumnType::kUint32, false);
47
48 BitVector bv{0, 1, 0, 1, 0};
49 DenseNullOverlay storage(&bv);
50 auto chain = storage.MakeChain(numeric->MakeChain());
51
52 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
53 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
54 }
55
TEST(DenseNullOverlay,RestrictInputSearch)56 TEST(DenseNullOverlay, RestrictInputSearch) {
57 std::vector<uint32_t> data{0, 1, 0, 1, 0};
58 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
59 &data, ColumnType::kUint32, false);
60
61 BitVector bv{0, 1, 0, 1, 0};
62 DenseNullOverlay storage(&bv);
63 auto chain = storage.MakeChain(numeric->MakeChain());
64
65 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(1, 3));
66 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
67 }
68
TEST(DenseNullOverlay,RangeFilterSearch)69 TEST(DenseNullOverlay, RangeFilterSearch) {
70 auto fake = FakeStorageChain::SearchSubset(5, Range(1, 3));
71
72 BitVector bv{0, 1, 0, 1, 0};
73 DenseNullOverlay storage(&bv);
74 auto chain = storage.MakeChain(std::move(fake));
75
76 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
77 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
78 }
79
TEST(DenseNullOverlay,BitvectorFilterSearch)80 TEST(DenseNullOverlay, BitvectorFilterSearch) {
81 auto fake = FakeStorageChain::SearchSubset(5, BitVector({0, 1, 1, 0, 0}));
82
83 BitVector bv{0, 1, 0, 1, 0};
84 DenseNullOverlay storage(&bv);
85 auto chain = storage.MakeChain(std::move(fake));
86
87 auto res = chain->Search(FilterOp::kGe, SqlValue::Long(0), Range(0, 5));
88 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
89 }
90
TEST(DenseNullOverlay,IsNullSearch)91 TEST(DenseNullOverlay, IsNullSearch) {
92 auto fake = FakeStorageChain::SearchSubset(5, BitVector({1, 1, 0, 0, 1}));
93
94 BitVector bv{1, 0, 0, 1, 1};
95 DenseNullOverlay storage(&bv);
96 auto chain = storage.MakeChain(std::move(fake));
97
98 auto res = chain->Search(FilterOp::kIsNull, SqlValue(), Range(0, 5));
99 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1, 2, 4));
100 }
101
TEST(DenseNullOverlay,IndexSearch)102 TEST(DenseNullOverlay, IndexSearch) {
103 std::vector<uint32_t> data{1, 0, 0, 1, 1, 1};
104 auto numeric = std::make_unique<NumericStorage<uint32_t>>(
105 &data, ColumnType::kUint32, false);
106
107 BitVector bv{1, 0, 0, 1, 1, 1};
108 DenseNullOverlay storage(&bv);
109 auto chain = storage.MakeChain(numeric->MakeChain());
110
111 Indices indices = Indices::CreateWithIndexPayloadForTesting(
112 {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
113 chain->IndexSearch(FilterOp::kGe, SqlValue::Long(0), indices);
114 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2, 3));
115 }
116
TEST(DenseNullOverlay,IsNullIndexSearch)117 TEST(DenseNullOverlay, IsNullIndexSearch) {
118 auto fake = FakeStorageChain::SearchSubset(6, BitVector({0, 0, 0, 1, 1, 1}));
119
120 BitVector bv{0, 1, 0, 1, 1, 1};
121 DenseNullOverlay storage(&bv);
122 auto chain = storage.MakeChain(std::move(fake));
123
124 Indices indices = Indices::CreateWithIndexPayloadForTesting(
125 {5, 2, 3, 4, 1}, Indices::State::kNonmonotonic);
126 chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
127 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
128 ElementsAre(0, 1, 2, 3));
129 }
130
TEST(DenseNullOverlay,OrderedIndexSearch)131 TEST(DenseNullOverlay, OrderedIndexSearch) {
132 std::vector<uint32_t> numeric_data{0, 1, 0, 1, 0, 1};
133 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
134
135 BitVector bv{0, 1, 0, 1, 0, 1};
136 DenseNullOverlay storage(&bv);
137 auto chain = storage.MakeChain(numeric.MakeChain());
138
139 std::vector<uint32_t> indices_vec({0, 2, 4, 1, 3, 5});
140 OrderedIndices indices{indices_vec.data(), 6, Indices::State::kNonmonotonic};
141
142 Range res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
143 ASSERT_EQ(res.start, 0u);
144 ASSERT_EQ(res.end, 3u);
145
146 res = chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
147 ASSERT_EQ(res.start, 3u);
148 ASSERT_EQ(res.end, 6u);
149
150 res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(1), indices);
151 ASSERT_EQ(res.start, 3u);
152 ASSERT_EQ(res.end, 6u);
153
154 res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
155 ASSERT_EQ(res.start, 3u);
156 ASSERT_EQ(res.end, 6u);
157
158 res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(1), indices);
159 ASSERT_EQ(res.start, 3u);
160 ASSERT_EQ(res.end, 6u);
161
162 res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(1), indices);
163 ASSERT_EQ(res.start, 0u);
164 ASSERT_EQ(res.end, 3u);
165
166 res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(0), indices);
167 ASSERT_EQ(res.start, 0u);
168 ASSERT_EQ(res.end, 3u);
169 }
170
TEST(DenseNullOverlay,SingleSearch)171 TEST(DenseNullOverlay, SingleSearch) {
172 BitVector bv{0, 1, 0, 1, 1, 1};
173 DenseNullOverlay storage(&bv);
174 auto fake = FakeStorageChain::SearchSubset(5, std::vector<uint32_t>{1, 2});
175 auto chain = storage.MakeChain(std::move(fake));
176
177 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 1),
178 SingleSearchResult::kMatch);
179 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 2),
180 SingleSearchResult::kNoMatch);
181 }
182
TEST(DenseNullOverlay,SingleSearchIsNull)183 TEST(DenseNullOverlay, SingleSearchIsNull) {
184 BitVector bv{0, 1, 0, 1, 1, 1};
185 DenseNullOverlay storage(&bv);
186 auto fake = FakeStorageChain::SearchNone(5);
187 auto chain = storage.MakeChain(std::move(fake));
188
189 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 0),
190 SingleSearchResult::kMatch);
191 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 1),
192 SingleSearchResult::kNoMatch);
193 }
194
TEST(DenseNullOverlay,SingleSearchIsNotNull)195 TEST(DenseNullOverlay, SingleSearchIsNotNull) {
196 BitVector bv{0, 1, 0, 1, 1, 1};
197 DenseNullOverlay storage(&bv);
198 auto fake = FakeStorageChain::SearchAll(5);
199 auto chain = storage.MakeChain(std::move(fake));
200
201 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 0),
202 SingleSearchResult::kNoMatch);
203 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 1),
204 SingleSearchResult::kMatch);
205 }
206
TEST(DenseNullOverlay,StableSort)207 TEST(DenseNullOverlay, StableSort) {
208 std::vector<uint32_t> numeric_data{0, 3, 0, 1, 0, 2, 4};
209 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
210
211 BitVector null{0, 1, 0, 1, 1, 1, 1};
212 DenseNullOverlay overlay(&null);
213 auto chain = overlay.MakeChain(numeric.MakeChain());
214
215 auto make_tokens = []() {
216 return std::vector{
217 column::DataLayerChain::SortToken{0, 0},
218 column::DataLayerChain::SortToken{1, 1},
219 column::DataLayerChain::SortToken{2, 2},
220 column::DataLayerChain::SortToken{3, 3},
221 column::DataLayerChain::SortToken{4, 4},
222 column::DataLayerChain::SortToken{5, 5},
223 column::DataLayerChain::SortToken{6, 6},
224 };
225 };
226 {
227 auto tokens = make_tokens();
228 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
229 column::DataLayerChain::SortDirection::kAscending);
230 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
231 ElementsAre(0, 2, 4, 3, 5, 1, 6));
232 }
233 {
234 auto tokens = make_tokens();
235 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
236 column::DataLayerChain::SortDirection::kDescending);
237 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
238 ElementsAre(6, 1, 5, 3, 4, 0, 2));
239 }
240 }
241
TEST(DenseNullOverlay,Distinct)242 TEST(DenseNullOverlay, Distinct) {
243 std::vector<uint32_t> numeric_data{0, 3, 0, 1, 0, 2, 4};
244 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
245
246 // NULL, 1, NULL, 1, 0, 2, 4
247 BitVector null{0, 1, 0, 1, 1, 1, 1};
248 DenseNullOverlay overlay(&null);
249 auto chain = overlay.MakeChain(numeric.MakeChain());
250
251 // NULL, 0, 1, 1
252 auto indices = Indices::CreateWithIndexPayloadForTesting(
253 {0, 1, 3, 3}, Indices::State::kNonmonotonic);
254 chain->Distinct(indices);
255 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
256 UnorderedElementsAre(0, 1, 2));
257 }
258
259 } // namespace
260 } // namespace perfetto::trace_processor::column
261