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/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(NullOverlay,SingleSearch)43 TEST(NullOverlay, SingleSearch) {
44 BitVector bv{0, 1, 0, 1, 1, 1};
45 auto fake = FakeStorageChain::SearchSubset(4, std::vector<uint32_t>{1, 2});
46 NullOverlay storage(&bv);
47 auto chain = storage.MakeChain(std::move(fake));
48
49 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 3),
50 SingleSearchResult::kMatch);
51 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 1),
52 SingleSearchResult::kNoMatch);
53 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0u), 2),
54 SingleSearchResult::kNoMatch);
55 }
56
TEST(NullOverlay,SingleSearchIsNull)57 TEST(NullOverlay, SingleSearchIsNull) {
58 BitVector bv{0, 1, 0, 1, 1, 1};
59 auto fake = FakeStorageChain::SearchNone(4);
60 NullOverlay storage(&bv);
61 auto chain = storage.MakeChain(std::move(fake));
62
63 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 0),
64 SingleSearchResult::kMatch);
65 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 1),
66 SingleSearchResult::kNoMatch);
67 }
68
TEST(NullOverlay,SingleSearchIsNotNull)69 TEST(NullOverlay, SingleSearchIsNotNull) {
70 BitVector bv{0, 1, 0, 1, 1, 1};
71 auto fake = FakeStorageChain::SearchAll(4);
72 NullOverlay storage(&bv);
73 auto chain = storage.MakeChain(std::move(fake));
74
75 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 1),
76 SingleSearchResult::kMatch);
77 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 0),
78 SingleSearchResult::kNoMatch);
79 }
80
TEST(NullOverlay,SearchInputInsideBoundary)81 TEST(NullOverlay, SearchInputInsideBoundary) {
82 BitVector bv{0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0};
83 auto fake = FakeStorageChain::SearchAll(4u);
84 NullOverlay storage(&bv);
85 auto chain = storage.MakeChain(std::move(fake));
86
87 auto res = chain->Search(FilterOp::kGt, SqlValue::Long(0), Range(1, 6));
88 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
89 }
90
TEST(NullOverlay,SearchInputOutsideBoundary)91 TEST(NullOverlay, SearchInputOutsideBoundary) {
92 BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
93 auto fake = FakeStorageChain::SearchAll(5u);
94 NullOverlay storage(&bv);
95 auto chain = storage.MakeChain(std::move(fake));
96
97 auto res = chain->Search(FilterOp::kGt, SqlValue::Long(0), Range(3, 8));
98 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4, 7));
99 }
100
TEST(NullOverlay,SubsetResultOutsideBoundary)101 TEST(NullOverlay, SubsetResultOutsideBoundary) {
102 BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
103 auto fake = FakeStorageChain::SearchSubset(5u, Range(1, 3));
104 NullOverlay storage(&bv);
105 auto chain = storage.MakeChain(std::move(fake));
106
107 auto res = chain->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
108 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3, 4));
109 }
110
TEST(NullOverlay,SubsetResultOnBoundary)111 TEST(NullOverlay, SubsetResultOnBoundary) {
112 BitVector bv{0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0};
113 auto fake = FakeStorageChain::SearchAll(5u);
114 NullOverlay storage(&bv);
115 auto chain = storage.MakeChain(std::move(fake));
116
117 auto res = chain->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 11));
118 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4, 7, 8));
119 }
120
TEST(NullOverlay,BitVectorSubset)121 TEST(NullOverlay, BitVectorSubset) {
122 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
123 auto fake = FakeStorageChain::SearchSubset(4u, BitVector{0, 1, 0, 1});
124 NullOverlay storage(&bv);
125 auto chain = storage.MakeChain(std::move(fake));
126
127 auto res = chain->Search(FilterOp::kGt, SqlValue::Long(0), Range(0, 8));
128 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 6));
129 }
130
TEST(NullOverlay,BitVectorSubsetIsNull)131 TEST(NullOverlay, BitVectorSubsetIsNull) {
132 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
133 auto fake = FakeStorageChain::SearchSubset(4u, BitVector{0, 1, 0, 1});
134 NullOverlay storage(&bv);
135 auto chain = storage.MakeChain(std::move(fake));
136
137 auto res = chain->Search(FilterOp::kIsNull, SqlValue(), Range(0, 8));
138 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 2, 3, 4, 6, 7));
139 }
140
TEST(NullOverlay,IndexSearchAllElements)141 TEST(NullOverlay, IndexSearchAllElements) {
142 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
143 auto fake = FakeStorageChain::SearchAll(4u);
144 NullOverlay storage(&bv);
145 auto chain = storage.MakeChain(std::move(fake));
146
147 Indices indices = Indices::CreateWithIndexPayloadForTesting(
148 {1, 5, 2}, Indices::State::kNonmonotonic);
149 chain->IndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
150 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
151 }
152
TEST(NullOverlay,IndexSearchPartialElements)153 TEST(NullOverlay, IndexSearchPartialElements) {
154 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
155 auto fake = FakeStorageChain::SearchAll(4u);
156 NullOverlay storage(&bv);
157 auto chain = storage.MakeChain(std::move(fake));
158
159 Indices indices = Indices::CreateWithIndexPayloadForTesting(
160 {1, 4, 2}, Indices::State::kNonmonotonic);
161 chain->IndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
162 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 2));
163 }
164
TEST(NullOverlay,IndexSearchIsNullOpEmptyRes)165 TEST(NullOverlay, IndexSearchIsNullOpEmptyRes) {
166 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
167 auto fake = FakeStorageChain::SearchNone(4u);
168 NullOverlay storage(&bv);
169 auto chain = storage.MakeChain(std::move(fake));
170
171 Indices indices = Indices::CreateWithIndexPayloadForTesting(
172 {0, 3, 5, 4, 2}, Indices::State::kNonmonotonic);
173 chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
174 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 3));
175 }
176
TEST(NullOverlay,IndexSearchIsNullOp)177 TEST(NullOverlay, IndexSearchIsNullOp) {
178 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
179 auto fake = FakeStorageChain::SearchSubset(4u, Range(2, 3));
180 NullOverlay storage(&bv);
181 auto chain = storage.MakeChain(std::move(fake));
182
183 Indices indices = Indices::CreateWithIndexPayloadForTesting(
184 {0, 3, 2, 4, 5}, Indices::State::kNonmonotonic);
185 chain->IndexSearch(FilterOp::kIsNull, SqlValue(), indices);
186 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
187 ElementsAre(0, 1, 3, 4));
188 }
189
TEST(NullOverlay,IndexSearchIsNotNullOp)190 TEST(NullOverlay, IndexSearchIsNotNullOp) {
191 BitVector bv{0, 1, 1, 0, 0, 1, 1, 0};
192 auto fake = FakeStorageChain::SearchAll(4u);
193 NullOverlay storage(&bv);
194 auto chain = storage.MakeChain(std::move(fake));
195
196 Indices indices = Indices::CreateWithIndexPayloadForTesting(
197 {0, 3, 4}, Indices::State::kNonmonotonic);
198 chain->IndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
199 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
200 }
201
TEST(NullOverlay,OrderedIndexSearch)202 TEST(NullOverlay, OrderedIndexSearch) {
203 std::vector<uint32_t> numeric_data{1, 0, 1, 0};
204 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
205
206 BitVector bv{0, 1, 1, 1, 0, 1};
207 NullOverlay storage(&bv);
208 auto chain = storage.MakeChain(numeric.MakeChain());
209
210 // Passing values on final data
211 // NULL, NULL, 0, 0, 1, 1
212 std::vector<uint32_t> table_idx{0, 4, 5, 1, 3};
213 OrderedIndices indices{table_idx.data(), uint32_t(table_idx.size()),
214 Indices::State::kNonmonotonic};
215
216 Range res = chain->OrderedIndexSearch(FilterOp::kIsNull, SqlValue(), indices);
217 ASSERT_EQ(res.start, 0u);
218 ASSERT_EQ(res.end, 2u);
219
220 res = chain->OrderedIndexSearch(FilterOp::kIsNotNull, SqlValue(), indices);
221 ASSERT_EQ(res.start, 2u);
222 ASSERT_EQ(res.end, 5u);
223
224 res = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(1), indices);
225 ASSERT_EQ(res.start, 3u);
226 ASSERT_EQ(res.end, 5u);
227
228 res = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(0), indices);
229 ASSERT_EQ(res.start, 3u);
230 ASSERT_EQ(res.end, 5u);
231
232 res = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(1), indices);
233 ASSERT_EQ(res.start, 3u);
234 ASSERT_EQ(res.end, 5u);
235
236 res = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(1), indices);
237 ASSERT_EQ(res.start, 0u);
238 ASSERT_EQ(res.end, 3u);
239
240 res = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(0), indices);
241 ASSERT_EQ(res.start, 0u);
242 ASSERT_EQ(res.end, 3u);
243 }
244
TEST(NullOverlay,StableSort)245 TEST(NullOverlay, StableSort) {
246 std::vector<uint32_t> numeric_data{3, 1, 0, 2, 4};
247 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
248
249 BitVector null{0, 1, 0, 1, 1, 1, 1};
250 NullOverlay overlay(&null);
251 auto chain = overlay.MakeChain(numeric.MakeChain());
252
253 auto make_tokens = []() {
254 return std::vector{
255 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3},
256 Token{4, 4}, Token{5, 5}, Token{6, 6},
257 };
258 };
259 {
260 auto tokens = make_tokens();
261 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
262 SortDirection::kAscending);
263 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
264 ElementsAre(0, 2, 4, 3, 5, 1, 6));
265 }
266 {
267 auto tokens = make_tokens();
268 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
269 SortDirection::kDescending);
270 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
271 ElementsAre(6, 1, 5, 3, 4, 0, 2));
272 }
273 }
274
TEST(NullOverlay,Distinct)275 TEST(NullOverlay, Distinct) {
276 std::vector<uint32_t> numeric_data{0, 0, 1, 1, 2};
277 NumericStorage<uint32_t> numeric(&numeric_data, ColumnType::kUint32, false);
278
279 // NULL, 0, NULL, 0, 1, 1, 2
280 BitVector null{0, 1, 0, 1, 1, 1, 1};
281 NullOverlay overlay(&null);
282 auto chain = overlay.MakeChain(numeric.MakeChain());
283
284 // NULL, 0, 1, 1, 2
285 auto indices = Indices::CreateWithIndexPayloadForTesting(
286 {0, 1, 4, 5, 6}, Indices::State::kNonmonotonic);
287 chain->Distinct(indices);
288 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
289 UnorderedElementsAre(0, 1, 2, 4));
290 }
291
292 } // namespace
293 } // namespace perfetto::trace_processor::column
294