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