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 <algorithm>
20 #include <cstdint>
21 #include <limits>
22 #include <memory>
23 #include <optional>
24 #include <utility>
25 #include <vector>
26
27 #include "perfetto/base/logging.h"
28 #include "perfetto/public/compiler.h"
29 #include "perfetto/trace_processor/basic_types.h"
30 #include "src/trace_processor/containers/bit_vector.h"
31 #include "src/trace_processor/db/column/data_layer.h"
32 #include "src/trace_processor/db/column/types.h"
33 #include "src/trace_processor/tp_metatrace.h"
34
35 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
36
37 namespace perfetto::trace_processor::column {
38 namespace {
39
40 namespace {
41 using Indices = DataLayerChain::Indices;
42
UpdateIndicesForInner(Indices & indices,const BitVector & non_null)43 std::optional<Token> UpdateIndicesForInner(Indices& indices,
44 const BitVector& non_null) {
45 // Find first NULL.
46 auto first_null_it = std::find_if(
47 indices.tokens.begin(), indices.tokens.end(),
48 [&non_null](const Token& t) { return !non_null.IsSet(t.index); });
49
50 // Save first NULL.
51 std::optional<Token> null_tok;
52 if (first_null_it != indices.tokens.end()) {
53 null_tok = *first_null_it;
54 }
55
56 // Erase all NULLs.
57 indices.tokens.erase(std::remove_if(first_null_it, indices.tokens.end(),
58 [&non_null](const Token& idx) {
59 return !non_null.IsSet(idx.index);
60 }),
61 indices.tokens.end());
62
63 // Update index of each token so they all point to inner.
64 for (auto& token : indices.tokens) {
65 token.index = non_null.CountSetBits(token.index);
66 }
67 return null_tok;
68 }
69 } // namespace
70
ReconcileStorageResult(FilterOp op,const BitVector & non_null,RangeOrBitVector storage_result,Range in_range)71 BitVector ReconcileStorageResult(FilterOp op,
72 const BitVector& non_null,
73 RangeOrBitVector storage_result,
74 Range in_range) {
75 PERFETTO_CHECK(in_range.end <= non_null.size());
76
77 // Reconcile the results of the Search operation with the non-null indices
78 // to ensure only those positions are set.
79 BitVector res;
80 if (storage_result.IsRange()) {
81 Range range = std::move(storage_result).TakeIfRange();
82 if (!range.empty()) {
83 res = non_null.IntersectRange(non_null.IndexOfNthSet(range.start),
84 non_null.IndexOfNthSet(range.end - 1) + 1);
85
86 // We should always have at least as many elements as the input range
87 // itself.
88 PERFETTO_CHECK(res.size() <= in_range.end);
89 }
90 } else {
91 res = non_null.Copy();
92 res.UpdateSetBits(std::move(storage_result).TakeIfBitVector());
93 }
94
95 // Ensure that |res| exactly matches the size which we need to return,
96 // padding with zeros or truncating if necessary.
97 res.Resize(in_range.end, false);
98
99 // For the IS NULL constraint, we also need to include all the null indices
100 // themselves.
101 if (PERFETTO_UNLIKELY(op == FilterOp::kIsNull)) {
102 BitVector null = non_null.IntersectRange(in_range.start, in_range.end);
103 null.Resize(in_range.end, false);
104 null.Not();
105 res.Or(null);
106 }
107 return res;
108 }
109
110 } // namespace
111
Flatten(uint32_t * start,const uint32_t * end,uint32_t stride)112 void NullOverlay::Flatten(uint32_t* start,
113 const uint32_t* end,
114 uint32_t stride) {
115 for (uint32_t* it = start; it < end; it += stride) {
116 if (non_null_->IsSet(*it)) {
117 *it = non_null_->CountSetBits(*it);
118 } else {
119 *it = std::numeric_limits<uint32_t>::max();
120 }
121 }
122 }
123
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t index) const124 SingleSearchResult NullOverlay::ChainImpl::SingleSearch(FilterOp op,
125 SqlValue sql_val,
126 uint32_t index) const {
127 switch (op) {
128 case FilterOp::kIsNull:
129 return non_null_->IsSet(index)
130 ? inner_->SingleSearch(op, sql_val,
131 non_null_->CountSetBits(index))
132 : SingleSearchResult::kMatch;
133 case FilterOp::kIsNotNull:
134 case FilterOp::kEq:
135 case FilterOp::kGe:
136 case FilterOp::kGt:
137 case FilterOp::kLt:
138 case FilterOp::kLe:
139 case FilterOp::kNe:
140 case FilterOp::kGlob:
141 case FilterOp::kRegex:
142 return non_null_->IsSet(index)
143 ? inner_->SingleSearch(op, sql_val,
144 non_null_->CountSetBits(index))
145 : SingleSearchResult::kNoMatch;
146 }
147 PERFETTO_FATAL("For GCC");
148 }
149
ChainImpl(std::unique_ptr<DataLayerChain> inner,const BitVector * non_null)150 NullOverlay::ChainImpl::ChainImpl(std::unique_ptr<DataLayerChain> inner,
151 const BitVector* non_null)
152 : inner_(std::move(inner)), non_null_(non_null) {
153 PERFETTO_DCHECK(non_null_->CountSetBits() <= inner_->size());
154 }
155
ValidateSearchConstraints(FilterOp op,SqlValue sql_val) const156 SearchValidationResult NullOverlay::ChainImpl::ValidateSearchConstraints(
157 FilterOp op,
158 SqlValue sql_val) const {
159 if (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull) {
160 return SearchValidationResult::kOk;
161 }
162 if (sql_val.is_null()) {
163 return SearchValidationResult::kNoData;
164 }
165 return inner_->ValidateSearchConstraints(op, sql_val);
166 }
167
SearchValidated(FilterOp op,SqlValue sql_val,Range in) const168 RangeOrBitVector NullOverlay::ChainImpl::SearchValidated(FilterOp op,
169 SqlValue sql_val,
170 Range in) const {
171 PERFETTO_TP_TRACE(metatrace::Category::DB, "NullOverlay::ChainImpl::Search");
172
173 if (op == FilterOp::kIsNull) {
174 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
175 case SearchValidationResult::kNoData: {
176 // There is no need to search in underlying storage. It's enough to
177 // intersect the |non_null_|.
178 BitVector res = non_null_->Copy();
179 res.Resize(in.end, false);
180 res.Not();
181 return RangeOrBitVector(res.IntersectRange(in.start, in.end));
182 }
183 case SearchValidationResult::kAllData:
184 return RangeOrBitVector(in);
185 case SearchValidationResult::kOk:
186 break;
187 }
188 } else if (op == FilterOp::kIsNotNull) {
189 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
190 case SearchValidationResult::kNoData:
191 return RangeOrBitVector(Range());
192 case SearchValidationResult::kAllData:
193 return RangeOrBitVector(non_null_->IntersectRange(in.start, in.end));
194 case SearchValidationResult::kOk:
195 break;
196 }
197 }
198
199 // Figure out the bounds of the indices in the underlying storage and search
200 // it.
201 uint32_t start = non_null_->CountSetBits(in.start);
202 uint32_t end = non_null_->CountSetBits(in.end);
203 BitVector res = ReconcileStorageResult(
204 op, *non_null_, inner_->SearchValidated(op, sql_val, Range(start, end)),
205 in);
206
207 PERFETTO_DCHECK(res.size() == in.end);
208 return RangeOrBitVector(std::move(res));
209 }
210
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const211 void NullOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
212 SqlValue sql_val,
213 Indices& indices) const {
214 PERFETTO_TP_TRACE(metatrace::Category::DB,
215 "NullOverlay::ChainImpl::IndexSearch");
216
217 if (op == FilterOp::kIsNull) {
218 // Partition the vector into all the null indices followed by all the
219 // non-null indices.
220 auto non_null_it = std::stable_partition(
221 indices.tokens.begin(), indices.tokens.end(),
222 [this](const Token& t) { return !non_null_->IsSet(t.index); });
223
224 // IndexSearch |inner_| with a vector containing a copy of the (translated)
225 // non-null indices.
226 Indices non_null{{non_null_it, indices.tokens.end()}, indices.state};
227 for (auto& token : non_null.tokens) {
228 token.index = non_null_->CountSetBits(token.index);
229 }
230 inner_->IndexSearch(op, sql_val, non_null);
231
232 // Replace all the original non-null positions with the result from calling
233 // IndexSearch.
234 auto new_non_null_it =
235 indices.tokens.erase(non_null_it, indices.tokens.end());
236 indices.tokens.insert(new_non_null_it, non_null.tokens.begin(),
237 non_null.tokens.end());
238
239 // Merge the two sorted index ranges together using the payload as the
240 // comparator. This is a required post-condition of IndexSearch.
241 std::inplace_merge(indices.tokens.begin(), new_non_null_it,
242 indices.tokens.end(), Token::PayloadComparator());
243 return;
244 }
245
246 auto keep_only_non_null = [this, &indices]() {
247 indices.tokens.erase(
248 std::remove_if(
249 indices.tokens.begin(), indices.tokens.end(),
250 [this](const Token& idx) { return !non_null_->IsSet(idx.index); }),
251 indices.tokens.end());
252 return;
253 };
254 if (op == FilterOp::kIsNotNull) {
255 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
256 case SearchValidationResult::kNoData:
257 indices.tokens.clear();
258 return;
259 case SearchValidationResult::kAllData:
260 keep_only_non_null();
261 return;
262 case SearchValidationResult::kOk:
263 break;
264 }
265 }
266 keep_only_non_null();
267 for (auto& token : indices.tokens) {
268 token.index = non_null_->CountSetBits(token.index);
269 }
270 inner_->IndexSearchValidated(op, sql_val, indices);
271 }
272
StableSort(Token * start,Token * end,SortDirection direction) const273 void NullOverlay::ChainImpl::StableSort(Token* start,
274 Token* end,
275 SortDirection direction) const {
276 PERFETTO_TP_TRACE(metatrace::Category::DB,
277 "NullOverlay::ChainImpl::StableSort");
278 Token* middle = std::stable_partition(start, end, [this](const Token& idx) {
279 return !non_null_->IsSet(idx.index);
280 });
281 for (Token* it = middle; it != end; ++it) {
282 it->index = non_null_->CountSetBits(it->index);
283 }
284 inner_->StableSort(middle, end, direction);
285 if (direction == SortDirection::kDescending) {
286 std::rotate(start, middle, end);
287 }
288 }
289
Distinct(Indices & indices) const290 void NullOverlay::ChainImpl::Distinct(Indices& indices) const {
291 PERFETTO_TP_TRACE(metatrace::Category::DB,
292 "NullOverlay::ChainImpl::Distinct");
293 auto null_tok = UpdateIndicesForInner(indices, *non_null_);
294
295 inner_->Distinct(indices);
296
297 // Add the only null as it is distinct value.
298 if (null_tok.has_value()) {
299 indices.tokens.push_back(*null_tok);
300 }
301 }
302
MaxElement(Indices & indices) const303 std::optional<Token> NullOverlay::ChainImpl::MaxElement(
304 Indices& indices) const {
305 PERFETTO_TP_TRACE(metatrace::Category::DB,
306 "NullOverlay::ChainImpl::MaxElement");
307 auto null_tok = UpdateIndicesForInner(indices, *non_null_);
308
309 std::optional<Token> max_tok = inner_->MaxElement(indices);
310
311 return max_tok ? max_tok : null_tok;
312 }
313
MinElement(Indices & indices) const314 std::optional<Token> NullOverlay::ChainImpl::MinElement(
315 Indices& indices) const {
316 PERFETTO_TP_TRACE(metatrace::Category::DB,
317 "NullOverlay::ChainImpl::MinDistinct");
318 // The smallest value would be a NULL, so we should just return NULL here.
319 auto first_null_it = std::find_if(
320 indices.tokens.begin(), indices.tokens.end(),
321 [this](const Token& t) { return !non_null_->IsSet(t.index); });
322
323 if (first_null_it != indices.tokens.end()) {
324 return *first_null_it;
325 }
326
327 // If we didn't find a null in indices we need to update index of each token
328 // so they all point to inner and look for the smallest value in the storage.
329 for (auto& token : indices.tokens) {
330 token.index = non_null_->CountSetBits(token.index);
331 }
332
333 return inner_->MinElement(indices);
334 }
335
Get_AvoidUsingBecauseSlow(uint32_t index) const336 SqlValue NullOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
337 uint32_t index) const {
338 return non_null_->IsSet(index)
339 ? inner_->Get_AvoidUsingBecauseSlow(non_null_->CountSetBits(index))
340 : SqlValue();
341 }
342
343 } // namespace perfetto::trace_processor::column
344