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 #include "src/trace_processor/db/column/numeric_storage.h"
17
18 #include <cmath>
19 #include <cstdint>
20 #include <limits>
21 #include <numeric>
22 #include <tuple>
23 #include <vector>
24
25 #include "perfetto/trace_processor/basic_types.h"
26 #include "src/trace_processor/containers/row_map.h"
27 #include "src/trace_processor/db/column/data_layer.h"
28 #include "src/trace_processor/db/column/types.h"
29 #include "src/trace_processor/db/column/utils.h"
30 #include "src/trace_processor/db/compare.h"
31 #include "test/gtest_and_gmock.h"
32
33 namespace perfetto::trace_processor {
34
operator ==(const Range & a,const Range & b)35 inline bool operator==(const Range& a, const Range& b) {
36 return std::tie(a.start, a.end) == std::tie(b.start, b.end);
37 }
38
39 namespace column {
40 namespace {
41
42 using testing::ElementsAre;
43 using testing::IsEmpty;
44
45 using Indices = DataLayerChain::Indices;
46 using OrderedIndices = DataLayerChain::OrderedIndices;
47
TEST(NumericStorage,InvalidSearchConstraintsGeneralChecks)48 TEST(NumericStorage, InvalidSearchConstraintsGeneralChecks) {
49 std::vector<uint32_t> data_vec(128);
50 std::iota(data_vec.begin(), data_vec.end(), 0);
51 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, false);
52 auto chain = storage.MakeChain();
53
54 Range test_range(20, 100);
55 Range full_range(0, 100);
56 Range empty_range;
57
58 // NULL checks
59 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNull, SqlValue()),
60 SearchValidationResult::kNoData);
61 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kIsNotNull, SqlValue()),
62 SearchValidationResult::kAllData);
63
64 // FilterOp checks
65 ASSERT_EQ(
66 chain->ValidateSearchConstraints(FilterOp::kGlob, SqlValue::Long(15)),
67 SearchValidationResult::kNoData);
68 ASSERT_EQ(
69 chain->ValidateSearchConstraints(FilterOp::kRegex, SqlValue::Long(15)),
70 SearchValidationResult::kNoData);
71
72 // Type checks
73 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe,
74 SqlValue::String("cheese")),
75 SearchValidationResult::kNoData);
76 }
77
TEST(NumericStorage,InvalidValueBoundsUint32)78 TEST(NumericStorage, InvalidValueBoundsUint32) {
79 std::vector<uint32_t> data_vec(128);
80 std::iota(data_vec.begin(), data_vec.end(), 0);
81 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, false);
82 auto chain = storage.MakeChain();
83
84 SqlValue max_val = SqlValue::Long(
85 static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 10);
86 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, max_val),
87 SearchValidationResult::kNoData);
88 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, max_val),
89 SearchValidationResult::kNoData);
90 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, max_val),
91 SearchValidationResult::kNoData);
92
93 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, max_val),
94 SearchValidationResult::kAllData);
95 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, max_val),
96 SearchValidationResult::kAllData);
97 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, max_val),
98 SearchValidationResult::kAllData);
99
100 SqlValue min_val = SqlValue::Long(
101 static_cast<int64_t>(std::numeric_limits<uint32_t>::min()) - 1);
102 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, min_val),
103 SearchValidationResult::kAllData);
104 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, min_val),
105 SearchValidationResult::kAllData);
106 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, min_val),
107 SearchValidationResult::kAllData);
108
109 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, min_val),
110 SearchValidationResult::kNoData);
111 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, min_val),
112 SearchValidationResult::kNoData);
113 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, min_val),
114 SearchValidationResult::kNoData);
115 }
116
TEST(NumericStorage,InvalidValueBoundsInt32)117 TEST(NumericStorage, InvalidValueBoundsInt32) {
118 std::vector<int32_t> data_vec(128);
119 std::iota(data_vec.begin(), data_vec.end(), 0);
120 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
121 auto chain = storage.MakeChain();
122
123 SqlValue max_val = SqlValue::Long(
124 static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 10);
125 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, max_val),
126 SearchValidationResult::kNoData);
127 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, max_val),
128 SearchValidationResult::kNoData);
129 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, max_val),
130 SearchValidationResult::kNoData);
131
132 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, max_val),
133 SearchValidationResult::kAllData);
134 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, max_val),
135 SearchValidationResult::kAllData);
136 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, max_val),
137 SearchValidationResult::kAllData);
138
139 SqlValue min_val = SqlValue::Long(
140 static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1);
141 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGe, min_val),
142 SearchValidationResult::kAllData);
143 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kGt, min_val),
144 SearchValidationResult::kAllData);
145 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kNe, min_val),
146 SearchValidationResult::kAllData);
147
148 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLe, min_val),
149 SearchValidationResult::kNoData);
150 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kLt, min_val),
151 SearchValidationResult::kNoData);
152 ASSERT_EQ(chain->ValidateSearchConstraints(FilterOp::kEq, min_val),
153 SearchValidationResult::kNoData);
154 }
155
TEST(NumericStorage,SingleSearch)156 TEST(NumericStorage, SingleSearch) {
157 std::vector<int32_t> data_vec{0, 1, 2, 3, 0, -1, -2, -3};
158 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
159 auto chain = storage.MakeChain();
160
161 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(1), 1),
162 SingleSearchResult::kMatch);
163 ASSERT_EQ(chain->SingleSearch(FilterOp::kEq, SqlValue::Long(1), 5),
164 SingleSearchResult::kNoMatch);
165
166 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(1), 0),
167 SingleSearchResult::kMatch);
168 ASSERT_EQ(chain->SingleSearch(FilterOp::kNe, SqlValue::Long(-2), 6),
169 SingleSearchResult::kNoMatch);
170
171 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(3), 2),
172 SingleSearchResult::kMatch);
173 ASSERT_EQ(chain->SingleSearch(FilterOp::kLt, SqlValue::Long(-2), 5),
174 SingleSearchResult::kNoMatch);
175
176 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(4), 4),
177 SingleSearchResult::kMatch);
178 ASSERT_EQ(chain->SingleSearch(FilterOp::kLe, SqlValue::Long(0), 3),
179 SingleSearchResult::kNoMatch);
180
181 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(0), 3),
182 SingleSearchResult::kMatch);
183 ASSERT_EQ(chain->SingleSearch(FilterOp::kGt, SqlValue::Long(0), 5),
184 SingleSearchResult::kNoMatch);
185
186 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0), 0),
187 SingleSearchResult::kMatch);
188 ASSERT_EQ(chain->SingleSearch(FilterOp::kGe, SqlValue::Long(0), 5),
189 SingleSearchResult::kNoMatch);
190
191 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNull, SqlValue(), 0),
192 SingleSearchResult::kNoMatch);
193 ASSERT_EQ(chain->SingleSearch(FilterOp::kIsNotNull, SqlValue(), 0),
194 SingleSearchResult::kMatch);
195 }
196
TEST(NumericStorage,Search)197 TEST(NumericStorage, Search) {
198 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
199 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
200 auto chain = storage.MakeChain();
201 Range test_range(1, 5);
202 SqlValue val = SqlValue::Long(4);
203
204 auto res = chain->Search(FilterOp::kEq, val, test_range);
205 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
206
207 res = chain->Search(FilterOp::kNe, val, test_range);
208 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
209
210 res = chain->Search(FilterOp::kLt, val, test_range);
211 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
212
213 res = chain->Search(FilterOp::kLe, val, test_range);
214 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3, 4));
215
216 res = chain->Search(FilterOp::kGt, val, test_range);
217 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
218
219 res = chain->Search(FilterOp::kGe, val, test_range);
220 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
221 }
222
TEST(NumericStorage,SearchCompareWithNegative)223 TEST(NumericStorage, SearchCompareWithNegative) {
224 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
225 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
226 auto chain = storage.MakeChain();
227 Range test_range(1, 5);
228 SqlValue val = SqlValue::Long(-3);
229
230 auto res = chain->Search(FilterOp::kEq, val, test_range);
231 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(4));
232
233 res = chain->Search(FilterOp::kNe, val, test_range);
234 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3));
235
236 res = chain->Search(FilterOp::kLt, val, test_range);
237 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
238
239 res = chain->Search(FilterOp::kLe, val, test_range);
240 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
241
242 res = chain->Search(FilterOp::kGt, val, test_range);
243 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
244
245 res = chain->Search(FilterOp::kGe, val, test_range);
246 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
247 }
248
TEST(NumericStorage,IndexSearch)249 TEST(NumericStorage, IndexSearch) {
250 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
251 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
252 auto chain = storage.MakeChain();
253
254 // -5, -3, -3, 3, 5, 0
255 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
256 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
257 SqlValue val = SqlValue::Long(3);
258
259 auto indices = common_indices;
260 chain->IndexSearch(FilterOp::kEq, val, indices);
261 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
262
263 indices = common_indices;
264 chain->IndexSearch(FilterOp::kNe, val, indices);
265 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
266 ElementsAre(0, 1, 2, 4, 5));
267
268 indices = common_indices;
269 chain->IndexSearch(FilterOp::kLt, val, indices);
270 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
271 ElementsAre(0, 1, 2, 5));
272
273 indices = common_indices;
274 chain->IndexSearch(FilterOp::kLe, val, indices);
275 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
276 ElementsAre(0, 1, 2, 3, 5));
277
278 indices = common_indices;
279 chain->IndexSearch(FilterOp::kGt, val, indices);
280 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
281
282 indices = common_indices;
283 chain->IndexSearch(FilterOp::kGe, val, indices);
284 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
285 }
286
TEST(NumericStorage,IndexSearchCompareWithNegative)287 TEST(NumericStorage, IndexSearchCompareWithNegative) {
288 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
289 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
290 auto chain = storage.MakeChain();
291
292 // -5, -3, -3, 3, 5, 0
293 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
294 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
295 SqlValue val = SqlValue::Long(-3);
296
297 auto indices = common_indices;
298 chain->IndexSearch(FilterOp::kEq, val, indices);
299 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(1, 2));
300
301 indices = common_indices;
302 chain->IndexSearch(FilterOp::kNe, val, indices);
303 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
304 ElementsAre(0, 3, 4, 5));
305
306 indices = common_indices;
307 chain->IndexSearch(FilterOp::kLt, val, indices);
308 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0));
309
310 indices = common_indices;
311 chain->IndexSearch(FilterOp::kLe, val, indices);
312 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
313
314 indices = common_indices;
315 chain->IndexSearch(FilterOp::kGt, val, indices);
316 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
317
318 indices = common_indices;
319 chain->IndexSearch(FilterOp::kGe, val, indices);
320 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
321 ElementsAre(1, 2, 3, 4, 5));
322 }
323
TEST(NumericStorage,SearchFast)324 TEST(NumericStorage, SearchFast) {
325 std::vector<uint32_t> data_vec(128);
326 std::iota(data_vec.begin(), data_vec.end(), 0);
327 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, false);
328 auto chain = storage.MakeChain();
329 RangeOrBitVector range_or_bv =
330 chain->Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128));
331 BitVector bv = std::move(range_or_bv).TakeIfBitVector();
332 ASSERT_TRUE(range_or_bv.IsBitVector());
333 ASSERT_EQ(bv.CountSetBits(), 28u);
334 ASSERT_EQ(bv.IndexOfNthSet(0), 100u);
335 }
336
TEST(NumericStorage,SearchSorted)337 TEST(NumericStorage, SearchSorted) {
338 std::vector<uint32_t> data_vec(128);
339 std::iota(data_vec.begin(), data_vec.end(), 0);
340 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
341 auto chain = storage.MakeChain();
342 Range range = chain->Search(FilterOp::kGe, SqlValue::Long(100), Range(0, 128))
343 .TakeIfRange();
344 ASSERT_EQ(range.size(), 28u);
345 ASSERT_EQ(range.start, 100u);
346 ASSERT_EQ(range.end, 128u);
347 }
348
TEST(NumericStorage,SearchSortedNe)349 TEST(NumericStorage, SearchSortedNe) {
350 std::vector<uint32_t> data_vec(128);
351 std::iota(data_vec.begin(), data_vec.end(), 0);
352 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
353 auto chain = storage.MakeChain();
354 BitVector bv =
355 chain->Search(FilterOp::kNe, SqlValue::Long(100), Range(0, 128))
356 .TakeIfBitVector();
357 ASSERT_EQ(bv.CountSetBits(), 127u);
358 }
359
TEST(NumericStorage,SearchSortedSubset)360 TEST(NumericStorage, SearchSortedSubset) {
361 std::vector<uint32_t> data_vec(128);
362 std::iota(data_vec.begin(), data_vec.end(), 0);
363 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, true);
364 auto chain = storage.MakeChain();
365 Range range =
366 chain->Search(FilterOp::kGe, SqlValue::Long(100), Range(102, 104))
367 .TakeIfRange();
368 ASSERT_EQ(range.size(), 2u);
369 ASSERT_EQ(range.start, 102u);
370 ASSERT_EQ(range.end, 104u);
371 }
372
TEST(NumericStorage,OrderedIndexSearch)373 TEST(NumericStorage, OrderedIndexSearch) {
374 std::vector<uint32_t> data_vec{30, 40, 50, 60, 90, 80, 70, 0, 10, 20};
375 std::vector<uint32_t> sorted_order_vec{7, 8, 9, 0, 1, 2, 3, 6, 5, 4};
376 OrderedIndices sorted_order{sorted_order_vec.data(), 10,
377 Indices::State::kNonmonotonic};
378
379 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kUint32, false);
380 auto chain = storage.MakeChain();
381
382 Range range = chain->OrderedIndexSearch(FilterOp::kEq, SqlValue::Long(60),
383 sorted_order);
384 ASSERT_EQ(range.size(), 1u);
385 ASSERT_EQ(range.start, 6u);
386 ASSERT_EQ(range.end, 7u);
387
388 range = chain->OrderedIndexSearch(FilterOp::kGt, SqlValue::Long(60),
389 sorted_order);
390 ASSERT_EQ(range.size(), 3u);
391 ASSERT_EQ(range.start, 7u);
392 ASSERT_EQ(range.end, 10u);
393
394 range = chain->OrderedIndexSearch(FilterOp::kGe, SqlValue::Long(60),
395 sorted_order);
396 ASSERT_EQ(range.size(), 4u);
397 ASSERT_EQ(range.start, 6u);
398 ASSERT_EQ(range.end, 10u);
399
400 range = chain->OrderedIndexSearch(FilterOp::kLt, SqlValue::Long(60),
401 sorted_order);
402 ASSERT_EQ(range.size(), 6u);
403 ASSERT_EQ(range.start, 0u);
404 ASSERT_EQ(range.end, 6u);
405
406 range = chain->OrderedIndexSearch(FilterOp::kLe, SqlValue::Long(60),
407 sorted_order);
408 ASSERT_EQ(range.size(), 7u);
409 ASSERT_EQ(range.start, 0u);
410 ASSERT_EQ(range.end, 7u);
411 }
412
TEST(NumericStorage,SearchWithIntAsDouble)413 TEST(NumericStorage, SearchWithIntAsDouble) {
414 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
415 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
416 auto chain = storage.MakeChain();
417 Range test_range(1, 5);
418 SqlValue val = SqlValue::Double(4);
419
420 auto res = chain->Search(FilterOp::kEq, val, test_range);
421 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(3));
422
423 res = chain->Search(FilterOp::kNe, val, test_range);
424 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 4));
425
426 res = chain->Search(FilterOp::kLt, val, test_range);
427 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
428
429 res = chain->Search(FilterOp::kLe, val, test_range);
430 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 3, 4));
431
432 res = chain->Search(FilterOp::kGt, val, test_range);
433 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
434
435 res = chain->Search(FilterOp::kGe, val, test_range);
436 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
437 }
438
TEST(NumericStorage,IndexSearchWithIntAsDouble)439 TEST(NumericStorage, IndexSearchWithIntAsDouble) {
440 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
441 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
442 auto chain = storage.MakeChain();
443
444 // -5, -3, -3, 3, 5, 0
445 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
446 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
447 SqlValue val = SqlValue::Double(3);
448
449 auto indices = common_indices;
450 chain->IndexSearch(FilterOp::kEq, val, indices);
451 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3));
452
453 indices = common_indices;
454 chain->IndexSearch(FilterOp::kNe, val, indices);
455 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
456 ElementsAre(0, 1, 2, 4, 5));
457
458 indices = common_indices;
459 chain->IndexSearch(FilterOp::kLt, val, indices);
460 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
461 ElementsAre(0, 1, 2, 5));
462
463 indices = common_indices;
464 chain->IndexSearch(FilterOp::kLe, val, indices);
465 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
466 ElementsAre(0, 1, 2, 3, 5));
467
468 indices = common_indices;
469 chain->IndexSearch(FilterOp::kGt, val, indices);
470 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(4));
471
472 indices = common_indices;
473 chain->IndexSearch(FilterOp::kGe, val, indices);
474 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
475 }
476
TEST(NumericStorage,SearchInt32WithDouble)477 TEST(NumericStorage, SearchInt32WithDouble) {
478 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
479 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
480 auto chain = storage.MakeChain();
481 Range test_range(1, 5);
482 SqlValue val = SqlValue::Double(3.5);
483
484 auto res = chain->Search(FilterOp::kEq, val, test_range);
485 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
486
487 res = chain->Search(FilterOp::kNe, val, test_range);
488 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
489
490 res = chain->Search(FilterOp::kLt, val, test_range);
491 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
492
493 res = chain->Search(FilterOp::kLe, val, test_range);
494 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2, 4));
495
496 res = chain->Search(FilterOp::kGt, val, test_range);
497 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
498
499 res = chain->Search(FilterOp::kGe, val, test_range);
500 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3));
501 }
502
TEST(NumericStorage,SearchInt32WithNegDouble)503 TEST(NumericStorage, SearchInt32WithNegDouble) {
504 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
505 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
506 auto chain = storage.MakeChain();
507 Range test_range(1, 5);
508 SqlValue val = SqlValue::Double(-3.5);
509
510 auto res = chain->Search(FilterOp::kEq, val, test_range);
511 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
512
513 res = chain->Search(FilterOp::kNe, val, test_range);
514 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
515
516 res = chain->Search(FilterOp::kLt, val, test_range);
517 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
518
519 res = chain->Search(FilterOp::kLe, val, test_range);
520 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(2));
521
522 res = chain->Search(FilterOp::kGt, val, test_range);
523 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
524
525 res = chain->Search(FilterOp::kGe, val, test_range);
526 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 3, 4));
527 }
528
TEST(NumericStorage,IndexSearchInt32WithDouble)529 TEST(NumericStorage, IndexSearchInt32WithDouble) {
530 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
531 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
532 auto chain = storage.MakeChain();
533
534 // -5, -3, -3, 3, 5, 0
535 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
536 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
537 SqlValue val = SqlValue::Double(1.5);
538
539 auto indices = common_indices;
540 chain->IndexSearch(FilterOp::kEq, val, indices);
541 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
542
543 indices = common_indices;
544 chain->IndexSearch(FilterOp::kNe, val, indices);
545 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
546 ElementsAre(0, 1, 2, 3, 4, 5));
547
548 indices = common_indices;
549 chain->IndexSearch(FilterOp::kLt, val, indices);
550 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
551 ElementsAre(0, 1, 2, 5));
552
553 indices = common_indices;
554 chain->IndexSearch(FilterOp::kLe, val, indices);
555 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
556 ElementsAre(0, 1, 2, 5));
557
558 indices = common_indices;
559 chain->IndexSearch(FilterOp::kGt, val, indices);
560 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
561
562 indices = common_indices;
563 chain->IndexSearch(FilterOp::kGe, val, indices);
564 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4));
565 }
566
TEST(NumericStorage,IndexSearchInt32WithNegDouble)567 TEST(NumericStorage, IndexSearchInt32WithNegDouble) {
568 std::vector<int32_t> data_vec{-5, 5, -4, 4, -3, 3, 0};
569 NumericStorage<int32_t> storage(&data_vec, ColumnType::kInt32, false);
570 auto chain = storage.MakeChain();
571
572 // -5, -3, -3, 3, 5, 0
573 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
574 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
575 SqlValue val = SqlValue::Double(-2.5);
576
577 auto indices = common_indices;
578 chain->IndexSearch(FilterOp::kEq, val, indices);
579 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
580
581 indices = common_indices;
582 chain->IndexSearch(FilterOp::kNe, val, indices);
583 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
584 ElementsAre(0, 1, 2, 3, 4, 5));
585
586 indices = common_indices;
587 chain->IndexSearch(FilterOp::kLt, val, indices);
588 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
589
590 indices = common_indices;
591 chain->IndexSearch(FilterOp::kLe, val, indices);
592 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
593
594 indices = common_indices;
595 chain->IndexSearch(FilterOp::kGt, val, indices);
596 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
597
598 indices = common_indices;
599 chain->IndexSearch(FilterOp::kGe, val, indices);
600 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(3, 4, 5));
601 }
602
TEST(NumericStorage,SearchUint32WithNegDouble)603 TEST(NumericStorage, SearchUint32WithNegDouble) {
604 std::vector<uint32_t> data_vec{0, 1, 2, 3, 4, 5};
605 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kInt32, false);
606 auto chain = storage.MakeChain();
607 Range test_range(1, 5);
608 SqlValue val = SqlValue::Double(-3.5);
609
610 auto res = chain->Search(FilterOp::kEq, val, test_range);
611 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
612
613 res = chain->Search(FilterOp::kNe, val, test_range);
614 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
615
616 res = chain->Search(FilterOp::kLt, val, test_range);
617 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
618
619 res = chain->Search(FilterOp::kLe, val, test_range);
620 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
621
622 res = chain->Search(FilterOp::kGt, val, test_range);
623 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
624
625 res = chain->Search(FilterOp::kGe, val, test_range);
626 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1, 2, 3, 4));
627 }
628
TEST(NumericStorage,IndexSearchUint32WithNegDouble)629 TEST(NumericStorage, IndexSearchUint32WithNegDouble) {
630 std::vector<uint32_t> data_vec{0, 1, 2, 3, 4, 5, 6};
631 NumericStorage<uint32_t> storage(&data_vec, ColumnType::kInt32, false);
632 auto chain = storage.MakeChain();
633
634 Indices common_indices = Indices::CreateWithIndexPayloadForTesting(
635 {0, 4, 4, 5, 1, 6}, Indices::State::kNonmonotonic);
636 SqlValue val = SqlValue::Double(-2.5);
637
638 auto indices = common_indices;
639 chain->IndexSearch(FilterOp::kEq, val, indices);
640 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
641
642 indices = common_indices;
643 chain->IndexSearch(FilterOp::kNe, val, indices);
644 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
645 ElementsAre(0, 1, 2, 3, 4, 5));
646
647 indices = common_indices;
648 chain->IndexSearch(FilterOp::kLt, val, indices);
649 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
650
651 indices = common_indices;
652 chain->IndexSearch(FilterOp::kLe, val, indices);
653 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), IsEmpty());
654
655 indices = common_indices;
656 chain->IndexSearch(FilterOp::kGt, val, indices);
657 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
658 ElementsAre(0, 1, 2, 3, 4, 5));
659
660 indices = common_indices;
661 chain->IndexSearch(FilterOp::kGe, val, indices);
662 ASSERT_THAT(utils::ExtractPayloadForTesting(indices),
663 ElementsAre(0, 1, 2, 3, 4, 5));
664 }
665
TEST(NumericStorage,DoubleColumnWithIntThatCantBeRepresentedAsDouble)666 TEST(NumericStorage, DoubleColumnWithIntThatCantBeRepresentedAsDouble) {
667 // Sanity check that this value can't be represented as double.
668 int64_t not_rep_i = 9007199254740993;
669 EXPECT_FALSE(std::nextafter(static_cast<double>(not_rep_i), 1.0) ==
670 static_cast<double>(not_rep_i));
671 SqlValue val = SqlValue::Long(not_rep_i);
672
673 std::vector<double> data_vec{9007199254740992.0, 9007199254740994.0};
674
675 // Whether LongToDouble has the expected results.
676 ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[0]) > 0);
677 ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[1]) < 0);
678
679 NumericStorage<double> storage(&data_vec, ColumnType::kDouble, false);
680 auto chain = storage.MakeChain();
681 Range test_range(0, 2);
682
683 auto res = chain->Search(FilterOp::kEq, val, test_range);
684 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
685
686 res = chain->Search(FilterOp::kNe, val, test_range);
687 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
688
689 res = chain->Search(FilterOp::kLt, val, test_range);
690 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
691
692 res = chain->Search(FilterOp::kLe, val, test_range);
693 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
694
695 res = chain->Search(FilterOp::kGt, val, test_range);
696 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
697
698 res = chain->Search(FilterOp::kGe, val, test_range);
699 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
700 }
701
TEST(NumericStorage,DoubleColumnWithNegIntThatCantBeRepresentedAsDouble)702 TEST(NumericStorage, DoubleColumnWithNegIntThatCantBeRepresentedAsDouble) {
703 // Sanity check that this value can't be represented as double.
704 int64_t not_rep_i = -9007199254740993;
705 EXPECT_FALSE(std::nextafter(static_cast<double>(not_rep_i), 1.0) ==
706 static_cast<double>(not_rep_i));
707 SqlValue val = SqlValue::Long(not_rep_i);
708
709 std::vector<double> data_vec{-9007199254740992.0, -9007199254740994.0};
710
711 // Whether LongToDouble has the expected results.
712 ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[0]) < 0);
713 ASSERT_TRUE(compare::LongToDouble(not_rep_i, data_vec[1]) > 0);
714
715 NumericStorage<double> storage(&data_vec, ColumnType::kDouble, false);
716 auto chain = storage.MakeChain();
717 Range test_range(0, 2);
718
719 auto res = chain->Search(FilterOp::kEq, val, test_range);
720 ASSERT_THAT(utils::ToIndexVectorForTests(res), IsEmpty());
721
722 res = chain->Search(FilterOp::kNe, val, test_range);
723 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0, 1));
724
725 res = chain->Search(FilterOp::kLt, val, test_range);
726 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
727
728 res = chain->Search(FilterOp::kLe, val, test_range);
729 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(1));
730
731 res = chain->Search(FilterOp::kGt, val, test_range);
732 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
733
734 res = chain->Search(FilterOp::kGe, val, test_range);
735 ASSERT_THAT(utils::ToIndexVectorForTests(res), ElementsAre(0));
736 }
737
TEST(NumericStorage,StableSort)738 TEST(NumericStorage, StableSort) {
739 std::vector<int64_t> data{
740 -1, -100, 2, 100, 2,
741 };
742 NumericStorage<int64_t> storage(&data, ColumnType::kInt64, false);
743 auto chain = storage.MakeChain();
744 auto make_tokens = []() {
745 return std::vector{
746 Token{0, 0}, Token{1, 1}, Token{2, 2}, Token{3, 3}, Token{4, 4},
747 };
748 };
749 {
750 auto tokens = make_tokens();
751 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
752 SortDirection::kAscending);
753 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
754 ElementsAre(1, 0, 2, 4, 3));
755 }
756 {
757 auto tokens = make_tokens();
758 chain->StableSort(tokens.data(), tokens.data() + tokens.size(),
759 SortDirection::kDescending);
760 ASSERT_THAT(utils::ExtractPayloadForTesting(tokens),
761 ElementsAre(3, 2, 4, 0, 1));
762 }
763 }
764
TEST(NumericStorage,DistinctFromIndexVector)765 TEST(NumericStorage, DistinctFromIndexVector) {
766 std::vector<int64_t> data{
767 1, 100, 2, 100, 2,
768 };
769 NumericStorage<int64_t> storage(&data, ColumnType::kInt64, false);
770 auto chain = storage.MakeChain();
771
772 auto indices = Indices::CreateWithIndexPayloadForTesting(
773 {2, 1, 0, 3}, Indices::State::kNonmonotonic);
774 chain->Distinct(indices);
775 ASSERT_THAT(utils::ExtractPayloadForTesting(indices), ElementsAre(0, 1, 2));
776 }
777
778 } // namespace
779 } // namespace column
780 } // namespace perfetto::trace_processor
781