xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/column/numeric_storage.cc (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc) 
1 
2 /*
3  * Copyright (C) 2023 The Android Open Source Project
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  *      http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS,
13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  * See the License for the specific language governing permissions and
15  * limitations under the License.
16  */
17 
18 #include "src/trace_processor/db/column/numeric_storage.h"
19 
20 #include <algorithm>
21 #include <cmath>
22 #include <cstdint>
23 #include <functional>
24 #include <limits>
25 #include <optional>
26 #include <string>
27 #include <utility>
28 #include <variant>
29 #include <vector>
30 
31 #include "perfetto/base/logging.h"
32 #include "perfetto/public/compiler.h"
33 #include "perfetto/trace_processor/basic_types.h"
34 #include "src/trace_processor/containers/bit_vector.h"
35 #include "src/trace_processor/db/column/data_layer.h"
36 #include "src/trace_processor/db/column/types.h"
37 #include "src/trace_processor/db/column/utils.h"
38 #include "src/trace_processor/tp_metatrace.h"
39 
40 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
41 
42 namespace perfetto::trace_processor::column {
43 namespace {
44 
45 using Indices = DataLayerChain::Indices;
46 using OrderedIndices = DataLayerChain::OrderedIndices;
47 
48 using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>;
49 
50 // Using the fact that binary operators in std are operators() of classes, we
51 // can wrap those classes in variants and use them for std::visit in
52 // SerialComparators. This helps prevent excess templating and switches.
53 template <typename T>
54 using FilterOpVariant = std::variant<std::greater<T>,
55                                      std::greater_equal<T>,
56                                      std::less<T>,
57                                      std::less_equal<T>,
58                                      std::equal_to<T>,
59                                      std::not_equal_to<T>>;
60 
61 // Based on SqlValue and ColumnType, casts SqlValue to proper type. Assumes the
62 // |val| and |type| are correct.
GetNumericTypeVariant(ColumnType type,SqlValue val)63 inline NumericValue GetNumericTypeVariant(ColumnType type, SqlValue val) {
64   switch (type) {
65     case ColumnType::kDouble:
66       return val.AsDouble();
67     case ColumnType::kInt64:
68       return val.AsLong();
69     case ColumnType::kInt32:
70       return static_cast<int32_t>(val.AsLong());
71     case ColumnType::kUint32:
72       return static_cast<uint32_t>(val.AsLong());
73     case ColumnType::kString:
74     case ColumnType::kDummy:
75     case ColumnType::kId:
76       PERFETTO_FATAL("Invalid type");
77   }
78   PERFETTO_FATAL("For GCC");
79 }
80 
81 // Fetch std binary comparator class based on FilterOp. Can be used in
82 // std::visit for comparison.
83 template <typename T>
GetFilterOpVariant(FilterOp op)84 inline FilterOpVariant<T> GetFilterOpVariant(FilterOp op) {
85   switch (op) {
86     case FilterOp::kEq:
87       return FilterOpVariant<T>(std::equal_to<T>());
88     case FilterOp::kNe:
89       return FilterOpVariant<T>(std::not_equal_to<T>());
90     case FilterOp::kGe:
91       return FilterOpVariant<T>(std::greater_equal<T>());
92     case FilterOp::kGt:
93       return FilterOpVariant<T>(std::greater<T>());
94     case FilterOp::kLe:
95       return FilterOpVariant<T>(std::less_equal<T>());
96     case FilterOp::kLt:
97       return FilterOpVariant<T>(std::less<T>());
98     case FilterOp::kGlob:
99     case FilterOp::kRegex:
100     case FilterOp::kIsNotNull:
101     case FilterOp::kIsNull:
102       PERFETTO_FATAL("Not a valid operation on numeric type.");
103   }
104   PERFETTO_FATAL("For GCC");
105 }
106 
LowerBoundIntrinsic(const void * vector_ptr,NumericValue val,Range search_range)107 uint32_t LowerBoundIntrinsic(const void* vector_ptr,
108                              NumericValue val,
109                              Range search_range) {
110   return std::visit(
111       [vector_ptr, search_range](auto val_data) {
112         using T = decltype(val_data);
113         const T* typed_start =
114             static_cast<const std::vector<T>*>(vector_ptr)->data();
115         const auto* lower =
116             std::lower_bound(typed_start + search_range.start,
117                              typed_start + search_range.end, val_data);
118         return static_cast<uint32_t>(std::distance(typed_start, lower));
119       },
120       val);
121 }
122 
UpperBoundIntrinsic(const void * vector_ptr,NumericValue val,Range search_range)123 uint32_t UpperBoundIntrinsic(const void* vector_ptr,
124                              NumericValue val,
125                              Range search_range) {
126   return std::visit(
127       [vector_ptr, search_range](auto val_data) {
128         using T = decltype(val_data);
129         const T* typed_start =
130             static_cast<const std::vector<T>*>(vector_ptr)->data();
131         const auto* upper =
132             std::upper_bound(typed_start + search_range.start,
133                              typed_start + search_range.end, val_data);
134         return static_cast<uint32_t>(std::distance(typed_start, upper));
135       },
136       val);
137 }
138 
139 template <typename T>
TypedLinearSearch(T typed_val,const T * start,FilterOp op,BitVector::Builder & builder)140 void TypedLinearSearch(T typed_val,
141                        const T* start,
142                        FilterOp op,
143                        BitVector::Builder& builder) {
144   switch (op) {
145     case FilterOp::kEq:
146       return utils::LinearSearchWithComparator(typed_val, start,
147                                                std::equal_to<T>(), builder);
148     case FilterOp::kNe:
149       return utils::LinearSearchWithComparator(typed_val, start,
150                                                std::not_equal_to<T>(), builder);
151     case FilterOp::kLe:
152       return utils::LinearSearchWithComparator(typed_val, start,
153                                                std::less_equal<T>(), builder);
154     case FilterOp::kLt:
155       return utils::LinearSearchWithComparator(typed_val, start, std::less<T>(),
156                                                builder);
157     case FilterOp::kGt:
158       return utils::LinearSearchWithComparator(typed_val, start,
159                                                std::greater<T>(), builder);
160     case FilterOp::kGe:
161       return utils::LinearSearchWithComparator(
162           typed_val, start, std::greater_equal<T>(), builder);
163     case FilterOp::kGlob:
164     case FilterOp::kRegex:
165     case FilterOp::kIsNotNull:
166     case FilterOp::kIsNull:
167       PERFETTO_DFATAL("Illegal argument");
168   }
169 }
170 
IntColumnWithDouble(FilterOp op,SqlValue * sql_val)171 SearchValidationResult IntColumnWithDouble(FilterOp op, SqlValue* sql_val) {
172   double double_val = sql_val->AsDouble();
173 
174   // Case when |sql_val| can be interpreted as a SqlValue::Double.
175   if (std::equal_to<>()(static_cast<double>(static_cast<int64_t>(double_val)),
176                         double_val)) {
177     *sql_val = SqlValue::Long(static_cast<int64_t>(double_val));
178     return SearchValidationResult::kOk;
179   }
180   // Logic for when the value is a real double.
181   switch (op) {
182     case FilterOp::kEq:
183       return SearchValidationResult::kNoData;
184     case FilterOp::kNe:
185       return SearchValidationResult::kAllData;
186 
187     case FilterOp::kLe:
188     case FilterOp::kGt:
189       *sql_val = SqlValue::Long(static_cast<int64_t>(std::floor(double_val)));
190       return SearchValidationResult::kOk;
191 
192     case FilterOp::kLt:
193     case FilterOp::kGe:
194       *sql_val = SqlValue::Long(static_cast<int64_t>(std::ceil(double_val)));
195       return SearchValidationResult::kOk;
196 
197     case FilterOp::kIsNotNull:
198     case FilterOp::kIsNull:
199     case FilterOp::kGlob:
200     case FilterOp::kRegex:
201       PERFETTO_FATAL("Invalid filter operation");
202   }
203   PERFETTO_FATAL("For GCC");
204 }
205 
DoubleColumnWithInt(FilterOp op,SqlValue * sql_val)206 SearchValidationResult DoubleColumnWithInt(FilterOp op, SqlValue* sql_val) {
207   int64_t i = sql_val->AsLong();
208   auto i_as_d = static_cast<double>(i);
209 
210   // Case when |sql_val| can be interpreted as a SqlValue::Long.
211   if (std::equal_to<int64_t>()(i, static_cast<int64_t>(i_as_d))) {
212     *sql_val = SqlValue::Double(i_as_d);
213     return SearchValidationResult::kOk;
214   }
215 
216   // Logic for when the value can't be represented as double.
217   switch (op) {
218     case FilterOp::kEq:
219       return SearchValidationResult::kNoData;
220     case FilterOp::kNe:
221       return SearchValidationResult::kAllData;
222 
223     case FilterOp::kLe:
224     case FilterOp::kGt:
225       // The first double value smaller than |i|.
226       *sql_val = SqlValue::Double(std::nextafter(i_as_d, i - 1));
227       return SearchValidationResult::kOk;
228 
229     case FilterOp::kLt:
230     case FilterOp::kGe:
231       // The first double value bigger than |i|.
232       *sql_val = SqlValue::Double(std::nextafter(i_as_d, i + 1));
233       return SearchValidationResult::kOk;
234 
235     case FilterOp::kIsNotNull:
236     case FilterOp::kIsNull:
237     case FilterOp::kGlob:
238     case FilterOp::kRegex:
239       PERFETTO_FATAL("Invalid filter operation");
240   }
241   PERFETTO_FATAL("For GCC");
242 }
243 
244 }  // namespace
245 
ChainImpl(const void * vector_ptr,ColumnType type,bool is_sorted)246 NumericStorageBase::ChainImpl::ChainImpl(const void* vector_ptr,
247                                          ColumnType type,
248                                          bool is_sorted)
249     : vector_ptr_(vector_ptr), storage_type_(type), is_sorted_(is_sorted) {}
250 
ValidateSearchConstraints(FilterOp op,SqlValue val) const251 SearchValidationResult NumericStorageBase::ChainImpl::ValidateSearchConstraints(
252     FilterOp op,
253     SqlValue val) const {
254   // NULL checks.
255   if (PERFETTO_UNLIKELY(val.is_null())) {
256     if (op == FilterOp::kIsNotNull) {
257       return SearchValidationResult::kAllData;
258     }
259     return SearchValidationResult::kNoData;
260   }
261 
262   // FilterOp checks. Switch so that we get a warning if new FilterOp is not
263   // handled.
264   switch (op) {
265     case FilterOp::kEq:
266     case FilterOp::kNe:
267     case FilterOp::kLt:
268     case FilterOp::kLe:
269     case FilterOp::kGt:
270     case FilterOp::kGe:
271       break;
272     case FilterOp::kIsNull:
273     case FilterOp::kIsNotNull:
274       PERFETTO_FATAL("Invalid constraint");
275     case FilterOp::kGlob:
276     case FilterOp::kRegex:
277       return SearchValidationResult::kNoData;
278   }
279 
280   // Type checks.
281   switch (val.type) {
282     case SqlValue::kNull:
283     case SqlValue::kLong:
284     case SqlValue::kDouble:
285       break;
286     case SqlValue::kString:
287       // Any string is always more than any numeric.
288       if (op == FilterOp::kLt || op == FilterOp::kLe) {
289         return SearchValidationResult::kAllData;
290       }
291       return SearchValidationResult::kNoData;
292     case SqlValue::kBytes:
293       return SearchValidationResult::kNoData;
294   }
295 
296   // Bounds of the value.
297   enum ExtremeVal { kTooBig, kTooSmall, kOk };
298   ExtremeVal extreme_validator = kOk;
299 
300   double num_val = val.type == SqlValue::kLong
301                        ? static_cast<double>(val.AsLong())
302                        : val.AsDouble();
303 
304   switch (storage_type_) {
305     case ColumnType::kDouble:
306       // Any value would make a sensible comparison with a double.
307     case ColumnType::kInt64:
308       // TODO(b/307482437): As long as the type is not double there is nothing
309       // to verify here, as all values are going to be in the int64_t limits.
310       break;
311     case ColumnType::kInt32:
312       if (num_val > std::numeric_limits<int32_t>::max()) {
313         extreme_validator = kTooBig;
314         break;
315       }
316       if (num_val < std::numeric_limits<int32_t>::min()) {
317         extreme_validator = kTooSmall;
318         break;
319       }
320       break;
321     case ColumnType::kUint32:
322       if (num_val > std::numeric_limits<uint32_t>::max()) {
323         extreme_validator = kTooBig;
324         break;
325       }
326       if (num_val < std::numeric_limits<uint32_t>::min()) {
327         extreme_validator = kTooSmall;
328         break;
329       }
330       break;
331     case ColumnType::kString:
332     case ColumnType::kDummy:
333     case ColumnType::kId:
334       break;
335   }
336 
337   switch (extreme_validator) {
338     case kOk:
339       return SearchValidationResult::kOk;
340     case kTooBig:
341       if (op == FilterOp::kLt || op == FilterOp::kLe || op == FilterOp::kNe) {
342         return SearchValidationResult::kAllData;
343       }
344       return SearchValidationResult::kNoData;
345     case kTooSmall:
346       if (op == FilterOp::kGt || op == FilterOp::kGe || op == FilterOp::kNe) {
347         return SearchValidationResult::kAllData;
348       }
349       return SearchValidationResult::kNoData;
350   }
351 
352   PERFETTO_FATAL("For GCC");
353 }
354 
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const355 RangeOrBitVector NumericStorageBase::ChainImpl::SearchValidated(
356     FilterOp op,
357     SqlValue sql_val,
358     Range search_range) const {
359   PERFETTO_DCHECK(search_range.end <= size());
360 
361   PERFETTO_TP_TRACE(
362       metatrace::Category::DB, "NumericStorage::ChainImpl::Search",
363       [&search_range, op](metatrace::Record* r) {
364         r->AddArg("Start", std::to_string(search_range.start));
365         r->AddArg("End", std::to_string(search_range.end));
366         r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
367       });
368 
369   // Mismatched types - value is double and column is int.
370   if (sql_val.type == SqlValue::kDouble &&
371       storage_type_ != ColumnType::kDouble) {
372     auto ret_opt =
373         utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), search_range);
374     if (ret_opt) {
375       return RangeOrBitVector(*ret_opt);
376     }
377   }
378 
379   // Mismatched types - column is double and value is int.
380   if (sql_val.type != SqlValue::kDouble &&
381       storage_type_ == ColumnType::kDouble) {
382     auto ret_opt =
383         utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), search_range);
384     if (ret_opt) {
385       return RangeOrBitVector(*ret_opt);
386     }
387   }
388 
389   NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
390 
391   if (is_sorted_) {
392     if (op != FilterOp::kNe) {
393       return RangeOrBitVector(BinarySearchIntrinsic(op, val, search_range));
394     }
395     // Not equal is a special operation on binary search, as it doesn't define a
396     // range, and rather just `not` range returned with `equal` operation.
397     Range r = BinarySearchIntrinsic(FilterOp::kEq, val, search_range);
398     BitVector bv(r.start, true);
399     bv.Resize(r.end, false);
400     bv.Resize(search_range.end, true);
401     return RangeOrBitVector(std::move(bv));
402   }
403   return RangeOrBitVector(LinearSearchInternal(op, val, search_range));
404 }
405 
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const406 void NumericStorageBase::ChainImpl::IndexSearchValidated(
407     FilterOp op,
408     SqlValue sql_val,
409     Indices& indices) const {
410   PERFETTO_TP_TRACE(
411       metatrace::Category::DB, "NumericStorage::ChainImpl::IndexSearch",
412       [&indices, op](metatrace::Record* r) {
413         r->AddArg("Count", std::to_string(indices.tokens.size()));
414         r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
415       });
416 
417   // Mismatched types - value is double and column is int.
418   if (sql_val.type == SqlValue::kDouble &&
419       storage_type_ != ColumnType::kDouble) {
420     if (utils::CanReturnEarly(IntColumnWithDouble(op, &sql_val), indices)) {
421       return;
422     }
423   }
424 
425   // Mismatched types - column is double and value is int.
426   if (sql_val.type != SqlValue::kDouble &&
427       storage_type_ == ColumnType::kDouble) {
428     if (utils::CanReturnEarly(DoubleColumnWithInt(op, &sql_val), indices)) {
429       return;
430     }
431   }
432 
433   NumericValue val = GetNumericTypeVariant(storage_type_, sql_val);
434   std::visit(
435       [this, &indices, op](auto val) {
436         using T = decltype(val);
437         auto* start = static_cast<const std::vector<T>*>(vector_ptr_)->data();
438         std::visit(
439             [start, &indices, val](auto comparator) {
440               utils::IndexSearchWithComparator(val, start, indices, comparator);
441             },
442             GetFilterOpVariant<T>(op));
443       },
444       val);
445 }
446 
LinearSearchInternal(FilterOp op,NumericValue val,Range range) const447 BitVector NumericStorageBase::ChainImpl::LinearSearchInternal(
448     FilterOp op,
449     NumericValue val,
450     Range range) const {
451   BitVector::Builder builder(range.end, range.start);
452   if (const auto* u32 = std::get_if<uint32_t>(&val)) {
453     const auto* start =
454         static_cast<const std::vector<uint32_t>*>(vector_ptr_)->data() +
455         range.start;
456     TypedLinearSearch(*u32, start, op, builder);
457   } else if (const auto* i64 = std::get_if<int64_t>(&val)) {
458     const auto* start =
459         static_cast<const std::vector<int64_t>*>(vector_ptr_)->data() +
460         range.start;
461     TypedLinearSearch(*i64, start, op, builder);
462   } else if (const auto* i32 = std::get_if<int32_t>(&val)) {
463     const auto* start =
464         static_cast<const std::vector<int32_t>*>(vector_ptr_)->data() +
465         range.start;
466     TypedLinearSearch(*i32, start, op, builder);
467   } else if (const auto* db = std::get_if<double>(&val)) {
468     const auto* start =
469         static_cast<const std::vector<double>*>(vector_ptr_)->data() +
470         range.start;
471     TypedLinearSearch(*db, start, op, builder);
472   } else {
473     PERFETTO_DFATAL("Invalid");
474   }
475   return std::move(builder).Build();
476 }
477 
BinarySearchIntrinsic(FilterOp op,NumericValue val,Range search_range) const478 Range NumericStorageBase::ChainImpl::BinarySearchIntrinsic(
479     FilterOp op,
480     NumericValue val,
481     Range search_range) const {
482   switch (op) {
483     case FilterOp::kEq:
484       return {LowerBoundIntrinsic(vector_ptr_, val, search_range),
485               UpperBoundIntrinsic(vector_ptr_, val, search_range)};
486     case FilterOp::kLe:
487       return {search_range.start,
488               UpperBoundIntrinsic(vector_ptr_, val, search_range)};
489     case FilterOp::kLt:
490       return {search_range.start,
491               LowerBoundIntrinsic(vector_ptr_, val, search_range)};
492     case FilterOp::kGe:
493       return {LowerBoundIntrinsic(vector_ptr_, val, search_range),
494               search_range.end};
495     case FilterOp::kGt:
496       return {UpperBoundIntrinsic(vector_ptr_, val, search_range),
497               search_range.end};
498     case FilterOp::kNe:
499     case FilterOp::kIsNull:
500     case FilterOp::kIsNotNull:
501     case FilterOp::kGlob:
502     case FilterOp::kRegex:
503       return {};
504   }
505   return {};
506 }
507 
508 }  // namespace perfetto::trace_processor::column
509