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