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