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/dense_null_overlay.h"
18
19 #include <algorithm>
20 #include <cstdint>
21 #include <iterator>
22 #include <limits>
23 #include <memory>
24 #include <optional>
25 #include <utility>
26 #include <vector>
27
28 #include "perfetto/base/logging.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 using Indices = DataLayerChain::Indices;
40
RemoveAllNullsAndReturnTheFirstOne(Indices & indices,const BitVector & non_null)41 std::optional<Token> RemoveAllNullsAndReturnTheFirstOne(
42 Indices& indices,
43 const BitVector& non_null) {
44 // Find first NULL.
45 auto first_null_it = std::find_if(
46 indices.tokens.begin(), indices.tokens.end(),
47 [&non_null](const Token& t) { return !non_null.IsSet(t.index); });
48
49 // Save first NULL.
50 std::optional<Token> null_tok;
51 if (first_null_it != indices.tokens.end()) {
52 null_tok = *first_null_it;
53 }
54
55 // Erase all NULLs.
56 indices.tokens.erase(std::remove_if(first_null_it, indices.tokens.end(),
57 [&non_null](const Token& idx) {
58 return !non_null.IsSet(idx.index);
59 }),
60 indices.tokens.end());
61 return null_tok;
62 }
63 } // namespace
64
Flatten(uint32_t * start,const uint32_t * end,uint32_t stride)65 void DenseNullOverlay::Flatten(uint32_t* start,
66 const uint32_t* end,
67 uint32_t stride) {
68 for (uint32_t* it = start; it < end; it += stride) {
69 if (!non_null_->IsSet(*it)) {
70 *it = std::numeric_limits<uint32_t>::max();
71 }
72 }
73 }
74
ChainImpl(std::unique_ptr<DataLayerChain> inner,const BitVector * non_null)75 DenseNullOverlay::ChainImpl::ChainImpl(std::unique_ptr<DataLayerChain> inner,
76 const BitVector* non_null)
77 : inner_(std::move(inner)), non_null_(non_null) {}
78
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t index) const79 SingleSearchResult DenseNullOverlay::ChainImpl::SingleSearch(
80 FilterOp op,
81 SqlValue sql_val,
82 uint32_t index) const {
83 switch (op) {
84 case FilterOp::kIsNull:
85 return non_null_->IsSet(index) ? inner_->SingleSearch(op, sql_val, index)
86 : SingleSearchResult::kMatch;
87 case FilterOp::kIsNotNull:
88 case FilterOp::kEq:
89 case FilterOp::kGe:
90 case FilterOp::kGt:
91 case FilterOp::kLt:
92 case FilterOp::kLe:
93 case FilterOp::kNe:
94 case FilterOp::kGlob:
95 case FilterOp::kRegex:
96 return non_null_->IsSet(index) ? inner_->SingleSearch(op, sql_val, index)
97 : SingleSearchResult::kNoMatch;
98 }
99 PERFETTO_FATAL("For GCC");
100 }
101
ValidateSearchConstraints(FilterOp op,SqlValue sql_val) const102 SearchValidationResult DenseNullOverlay::ChainImpl::ValidateSearchConstraints(
103 FilterOp op,
104 SqlValue sql_val) const {
105 if (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull) {
106 return SearchValidationResult::kOk;
107 }
108 if (sql_val.is_null()) {
109 return SearchValidationResult::kNoData;
110 }
111 return inner_->ValidateSearchConstraints(op, sql_val);
112 }
113
SearchValidated(FilterOp op,SqlValue sql_val,Range in) const114 RangeOrBitVector DenseNullOverlay::ChainImpl::SearchValidated(FilterOp op,
115 SqlValue sql_val,
116 Range in) const {
117 PERFETTO_TP_TRACE(metatrace::Category::DB,
118 "DenseNullOverlay::ChainImpl::Search");
119
120 if (op == FilterOp::kIsNull) {
121 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
122 case SearchValidationResult::kNoData: {
123 // There is no need to search in underlying storage. It's enough to
124 // intersect the |non_null_|.
125 BitVector res = non_null_->Copy();
126 res.Resize(in.end, false);
127 res.Not();
128 return RangeOrBitVector(res.IntersectRange(in.start, in.end));
129 }
130 case SearchValidationResult::kAllData:
131 return RangeOrBitVector(in);
132 case SearchValidationResult::kOk:
133 break;
134 }
135 } else if (op == FilterOp::kIsNotNull) {
136 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
137 case SearchValidationResult::kNoData:
138 return RangeOrBitVector(Range());
139 case SearchValidationResult::kAllData:
140 return RangeOrBitVector(non_null_->IntersectRange(in.start, in.end));
141 case SearchValidationResult::kOk:
142 break;
143 }
144 }
145
146 RangeOrBitVector inner_res = inner_->SearchValidated(op, sql_val, in);
147 BitVector res;
148 if (inner_res.IsRange()) {
149 // If the inner storage returns a range, mask out the appropriate values in
150 // |non_null_| which matches the range. Then, resize to |in.end| as this
151 // is mandated by the API contract of |Storage::Search|.
152 Range inner_range = std::move(inner_res).TakeIfRange();
153 PERFETTO_DCHECK(inner_range.empty() || inner_range.end <= in.end);
154 PERFETTO_DCHECK(inner_range.empty() || inner_range.start >= in.start);
155 res = non_null_->IntersectRange(inner_range.start, inner_range.end);
156 res.Resize(in.end, false);
157 } else {
158 res = std::move(inner_res).TakeIfBitVector();
159 }
160
161 if (op == FilterOp::kIsNull) {
162 // For IS NULL, we need to add any rows in |non_null_| which are zeros: we
163 // do this by taking the appropriate number of rows, inverting it and then
164 // bitwise or-ing the result with it.
165 BitVector non_null_copy = non_null_->Copy();
166 non_null_copy.Resize(in.end);
167 non_null_copy.Not();
168 res.Or(non_null_copy);
169 } else {
170 // For anything else, we just need to ensure that any rows which are null
171 // are removed as they would not match.
172 res.And(*non_null_);
173 }
174
175 PERFETTO_DCHECK(res.size() == in.end);
176 return RangeOrBitVector(std::move(res));
177 }
178
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const179 void DenseNullOverlay::ChainImpl::IndexSearchValidated(FilterOp op,
180 SqlValue sql_val,
181 Indices& indices) const {
182 PERFETTO_TP_TRACE(metatrace::Category::DB,
183 "DenseNullOverlay::ChainImpl::IndexSearch");
184
185 if (op == FilterOp::kIsNull) {
186 // Partition the vector into all the null indices followed by all the
187 // non-null indices.
188 auto non_null_it = std::stable_partition(
189 indices.tokens.begin(), indices.tokens.end(),
190 [this](const Token& t) { return !non_null_->IsSet(t.index); });
191
192 // IndexSearch |inner_| with a vector containing a copy of the non-null
193 // indices.
194 Indices non_null{{non_null_it, indices.tokens.end()}, indices.state};
195 inner_->IndexSearch(op, sql_val, non_null);
196
197 // Replace all the original non-null positions with the result from calling
198 // IndexSearch.
199 auto new_non_null_it =
200 indices.tokens.erase(non_null_it, indices.tokens.end());
201 indices.tokens.insert(new_non_null_it, non_null.tokens.begin(),
202 non_null.tokens.end());
203
204 // Merge the two sorted index ranges together using the payload as the
205 // comparator. This is a required post-condition of IndexSearch.
206 std::inplace_merge(indices.tokens.begin(), new_non_null_it,
207 indices.tokens.end(), Token::PayloadComparator());
208 return;
209 }
210
211 auto keep_only_non_null = [this, &indices]() {
212 indices.tokens.erase(
213 std::remove_if(
214 indices.tokens.begin(), indices.tokens.end(),
215 [this](const Token& idx) { return !non_null_->IsSet(idx.index); }),
216 indices.tokens.end());
217 return;
218 };
219 if (op == FilterOp::kIsNotNull) {
220 switch (inner_->ValidateSearchConstraints(op, sql_val)) {
221 case SearchValidationResult::kNoData:
222 indices.tokens.clear();
223 return;
224 case SearchValidationResult::kAllData:
225 keep_only_non_null();
226 return;
227 case SearchValidationResult::kOk:
228 break;
229 }
230 }
231 keep_only_non_null();
232 inner_->IndexSearchValidated(op, sql_val, indices);
233 }
234
StableSort(Token * start,Token * end,SortDirection direction) const235 void DenseNullOverlay::ChainImpl::StableSort(Token* start,
236 Token* end,
237 SortDirection direction) const {
238 Token* it = std::stable_partition(start, end, [this](const Token& idx) {
239 return !non_null_->IsSet(idx.index);
240 });
241 inner_->StableSort(it, end, direction);
242 if (direction == SortDirection::kDescending) {
243 std::rotate(start, it, end);
244 }
245 }
246
Distinct(Indices & indices) const247 void DenseNullOverlay::ChainImpl::Distinct(Indices& indices) const {
248 PERFETTO_TP_TRACE(metatrace::Category::DB,
249 "DenseNullOverlay::ChainImpl::Distinct");
250 std::optional<Token> null_tok =
251 RemoveAllNullsAndReturnTheFirstOne(indices, *non_null_);
252
253 inner_->Distinct(indices);
254
255 // Add the only null as it is distinct value.
256 if (null_tok.has_value()) {
257 indices.tokens.push_back(*null_tok);
258 }
259 }
260
MaxElement(Indices & indices) const261 std::optional<Token> DenseNullOverlay::ChainImpl::MaxElement(
262 Indices& indices) const {
263 PERFETTO_TP_TRACE(metatrace::Category::DB,
264 "DenseNullOverlay::ChainImpl::MaxElement");
265 std::optional<Token> null_tok =
266 RemoveAllNullsAndReturnTheFirstOne(indices, *non_null_);
267
268 std::optional<Token> max_val = inner_->MaxElement(indices);
269
270 return max_val ? max_val : null_tok;
271 }
272
MinElement(Indices & indices) const273 std::optional<Token> DenseNullOverlay::ChainImpl::MinElement(
274 Indices& indices) const {
275 PERFETTO_TP_TRACE(metatrace::Category::DB,
276 "DenseNullOverlay::ChainImpl::MinElement");
277 // Return the first NULL if found.
278 auto first_null_it = std::find_if(
279 indices.tokens.begin(), indices.tokens.end(),
280 [this](const Token& t) { return !non_null_->IsSet(t.index); });
281
282 return (first_null_it == indices.tokens.end()) ? inner_->MinElement(indices)
283 : *first_null_it;
284 }
285
Get_AvoidUsingBecauseSlow(uint32_t index) const286 SqlValue DenseNullOverlay::ChainImpl::Get_AvoidUsingBecauseSlow(
287 uint32_t index) const {
288 return non_null_->IsSet(index) ? inner_->Get_AvoidUsingBecauseSlow(index)
289 : SqlValue();
290 }
291
292 } // namespace perfetto::trace_processor::column
293