xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/query_executor.cc (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc)
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 <algorithm>
18 #include <cstdint>
19 #include <optional>
20 #include <unordered_set>
21 #include <utility>
22 #include <vector>
23 
24 #include <sys/types.h>
25 #include "perfetto/base/logging.h"
26 #include "perfetto/trace_processor/basic_types.h"
27 #include "src/trace_processor/containers/bit_vector.h"
28 #include "src/trace_processor/containers/row_map.h"
29 #include "src/trace_processor/db/column/data_layer.h"
30 #include "src/trace_processor/db/column/types.h"
31 #include "src/trace_processor/db/query_executor.h"
32 #include "src/trace_processor/db/table.h"
33 
34 namespace perfetto::trace_processor {
35 
36 namespace {
37 
38 using Range = RowMap::Range;
39 using Indices = column::DataLayerChain::Indices;
40 using OrderedIndices = column::DataLayerChain::OrderedIndices;
41 
42 }  // namespace
43 
ApplyConstraint(const Constraint & c,const column::DataLayerChain & chain,RowMap * rm)44 void QueryExecutor::ApplyConstraint(const Constraint& c,
45                                     const column::DataLayerChain& chain,
46                                     RowMap* rm) {
47   // Shortcut of empty row map.
48   uint32_t rm_size = rm->size();
49   if (rm_size == 0)
50     return;
51 
52   uint32_t rm_first = rm->Get(0);
53   if (rm_size == 1) {
54     switch (chain.SingleSearch(c.op, c.value, rm_first)) {
55       case SingleSearchResult::kMatch:
56         return;
57       case SingleSearchResult::kNoMatch:
58         rm->Clear();
59         return;
60       case SingleSearchResult::kNeedsFullSearch:
61         break;
62     }
63   }
64 
65   switch (chain.ValidateSearchConstraints(c.op, c.value)) {
66     case SearchValidationResult::kNoData:
67       rm->Clear();
68       return;
69     case SearchValidationResult::kAllData:
70       return;
71     case SearchValidationResult::kOk:
72       break;
73   }
74 
75   uint32_t rm_last = rm->Get(rm_size - 1);
76   uint32_t range_size = rm_last - rm_first;
77 
78   // If the number of elements in the rowmap is small or the number of
79   // elements is less than 1/10th of the range, use indexed filtering.
80   // TODO(b/283763282): use Overlay estimations.
81   bool disallows_index_search = rm->IsRange();
82   bool prefers_index_search =
83       rm->IsIndexVector() || rm_size < 1024 || rm_size * 10 < range_size;
84 
85   if (!disallows_index_search && prefers_index_search) {
86     IndexSearch(c, chain, rm);
87     return;
88   }
89   LinearSearch(c, chain, rm);
90 }
91 
LinearSearch(const Constraint & c,const column::DataLayerChain & chain,RowMap * rm)92 void QueryExecutor::LinearSearch(const Constraint& c,
93                                  const column::DataLayerChain& chain,
94                                  RowMap* rm) {
95   // TODO(b/283763282): Align these to word boundaries.
96   Range bounds(rm->Get(0), rm->Get(rm->size() - 1) + 1);
97 
98   // Search the storage.
99   RangeOrBitVector res = chain.Search(c.op, c.value, bounds);
100   if (rm->IsRange()) {
101     if (res.IsRange()) {
102       Range range = std::move(res).TakeIfRange();
103       *rm = RowMap(range.start, range.end);
104     } else {
105       // The BitVector was already limited on the RowMap when created, so we
106       // can take it as it is.
107       *rm = RowMap(std::move(res).TakeIfBitVector());
108     }
109     return;
110   }
111 
112   if (res.IsRange()) {
113     Range range = std::move(res).TakeIfRange();
114     rm->Intersect(RowMap(range.start, range.end));
115     return;
116   }
117   rm->Intersect(RowMap(std::move(res).TakeIfBitVector()));
118 }
119 
IndexSearch(const Constraint & c,const column::DataLayerChain & chain,RowMap * rm)120 void QueryExecutor::IndexSearch(const Constraint& c,
121                                 const column::DataLayerChain& chain,
122                                 RowMap* rm) {
123   // Create outmost TableIndexVector.
124   std::vector<uint32_t> table_indices = std::move(*rm).TakeAsIndexVector();
125 
126   Indices indices = Indices::Create(table_indices, Indices::State::kMonotonic);
127   chain.IndexSearch(c.op, c.value, indices);
128 
129   PERFETTO_DCHECK(indices.tokens.size() <= table_indices.size());
130   for (uint32_t i = 0; i < indices.tokens.size(); ++i) {
131     table_indices[i] = indices.tokens[i].payload;
132   }
133   table_indices.resize(indices.tokens.size());
134   PERFETTO_DCHECK(std::is_sorted(table_indices.begin(), table_indices.end()));
135   *rm = RowMap(std::move(table_indices));
136 }
137 
SortLegacy(const Table * table,const std::vector<Order> & ob,std::vector<uint32_t> & out)138 void QueryExecutor::SortLegacy(const Table* table,
139                                const std::vector<Order>& ob,
140                                std::vector<uint32_t>& out) {
141   // Setup the sort token payload to match the input vector of indices. The
142   // value of the payload will be untouched by the algorithm even while the
143   // order changes to match the ordering defined by the input constraint set.
144   std::vector<Token> rows(out.size());
145   for (uint32_t i = 0; i < out.size(); ++i) {
146     rows[i].payload = out[i];
147   }
148 
149   // As our data is columnar, it's always more efficient to sort one column
150   // at a time rather than try and sort lexiographically all at once.
151   // To preserve correctness, we need to stably sort the index vector once
152   // for each order by in *reverse* order. Reverse order is important as it
153   // preserves the lexiographical property.
154   //
155   // For example, suppose we have the following:
156   // Table {
157   //   Column x;
158   //   Column y
159   //   Column z;
160   // }
161   //
162   // Then, to sort "y asc, x desc", we could do one of two things:
163   //  1) sort the index vector all at once and on each index, we compare
164   //     y then z. This is slow as the data is columnar and we need to
165   //     repeatedly branch inside each column.
166   //  2) we can stably sort first on x desc and then sort on y asc. This will
167   //     first put all the x in the correct order such that when we sort on
168   //     y asc, we will have the correct order of x where y is the same (since
169   //     the sort is stable).
170   //
171   // TODO(lalitm): it is possible that we could sort the last constraint (i.e.
172   // the first constraint in the below loop) in a non-stable way. However,
173   // this is more subtle than it appears as we would then need special
174   // handling where there are order bys on a column which is already sorted
175   // (e.g. ts, id). Investigate whether the performance gains from this are
176   // worthwhile. This also needs changes to the constraint modification logic
177   // in DbSqliteTable which currently eliminates constraints on sorted
178   // columns.
179   for (auto it = ob.rbegin(); it != ob.rend(); ++it) {
180     // Reset the index to the payload at the start of each iote
181     for (uint32_t i = 0; i < out.size(); ++i) {
182       rows[i].index = rows[i].payload;
183     }
184     table->ChainForColumn(it->col_idx)
185         .StableSort(
186             rows.data(), rows.data() + rows.size(),
187             it->desc ? SortDirection::kDescending : SortDirection::kAscending);
188   }
189 
190   // Recapture the payload from each of the sort tokens whose order now
191   // indicates the order
192   for (uint32_t i = 0; i < out.size(); ++i) {
193     out[i] = rows[i].payload;
194   }
195 }
196 
BoundedColumnFilterForTesting(const Constraint & c,const column::DataLayerChain & col,RowMap * rm)197 void QueryExecutor::BoundedColumnFilterForTesting(
198     const Constraint& c,
199     const column::DataLayerChain& col,
200     RowMap* rm) {
201   LinearSearch(c, col, rm);
202 }
203 
IndexedColumnFilterForTesting(const Constraint & c,const column::DataLayerChain & col,RowMap * rm)204 void QueryExecutor::IndexedColumnFilterForTesting(
205     const Constraint& c,
206     const column::DataLayerChain& col,
207     RowMap* rm) {
208   IndexSearch(c, col, rm);
209 }
210 
211 }  // namespace perfetto::trace_processor
212