1 /*
2 * Copyright (C) 2019 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.h"
18
19 #include "src/trace_processor/db/compare.h"
20 #include "src/trace_processor/db/table.h"
21
22 namespace perfetto {
23 namespace trace_processor {
24
Column(const Column & column,Table * table,uint32_t col_idx,uint32_t row_map_idx)25 Column::Column(const Column& column,
26 Table* table,
27 uint32_t col_idx,
28 uint32_t row_map_idx)
29 : Column(column.name_,
30 column.type_,
31 column.flags_,
32 table,
33 col_idx,
34 row_map_idx,
35 column.nullable_vector_,
36 column.owned_nullable_vector_) {}
37
Column(const char * name,ColumnType type,uint32_t flags,Table * table,uint32_t col_idx_in_table,uint32_t row_map_idx,NullableVectorBase * nv,std::shared_ptr<NullableVectorBase> owned_nullable_vector)38 Column::Column(const char* name,
39 ColumnType type,
40 uint32_t flags,
41 Table* table,
42 uint32_t col_idx_in_table,
43 uint32_t row_map_idx,
44 NullableVectorBase* nv,
45 std::shared_ptr<NullableVectorBase> owned_nullable_vector)
46 : owned_nullable_vector_(owned_nullable_vector),
47 type_(type),
48 nullable_vector_(nv),
49 name_(name),
50 flags_(flags),
51 table_(table),
52 col_idx_in_table_(col_idx_in_table),
53 row_map_idx_(row_map_idx),
54 string_pool_(table->string_pool_) {
55 switch (type_) {
56 case ColumnType::kInt32:
57 PERFETTO_CHECK(nullable_vector<int32_t>().IsDense() == IsDense());
58 break;
59 case ColumnType::kUint32:
60 PERFETTO_CHECK(nullable_vector<uint32_t>().IsDense() == IsDense());
61 break;
62 case ColumnType::kInt64:
63 PERFETTO_CHECK(nullable_vector<int64_t>().IsDense() == IsDense());
64 break;
65 case ColumnType::kDouble:
66 PERFETTO_CHECK(nullable_vector<double>().IsDense() == IsDense());
67 break;
68 case ColumnType::kString:
69 PERFETTO_CHECK(nullable_vector<StringPool::Id>().IsDense() == IsDense());
70 break;
71 case ColumnType::kId:
72 break;
73 }
74 }
75
IdColumn(Table * table,uint32_t col_idx,uint32_t row_map_idx)76 Column Column::IdColumn(Table* table, uint32_t col_idx, uint32_t row_map_idx) {
77 return Column("id", ColumnType::kId, kIdFlags, table, col_idx, row_map_idx,
78 nullptr, nullptr);
79 }
80
StableSort(bool desc,std::vector<uint32_t> * idx) const81 void Column::StableSort(bool desc, std::vector<uint32_t>* idx) const {
82 if (desc) {
83 StableSort<true /* desc */>(idx);
84 } else {
85 StableSort<false /* desc */>(idx);
86 }
87 }
88
FilterIntoSlow(FilterOp op,SqlValue value,RowMap * rm) const89 void Column::FilterIntoSlow(FilterOp op, SqlValue value, RowMap* rm) const {
90 switch (type_) {
91 case ColumnType::kInt32: {
92 if (IsNullable()) {
93 FilterIntoNumericSlow<int32_t, true /* is_nullable */>(op, value, rm);
94 } else {
95 FilterIntoNumericSlow<int32_t, false /* is_nullable */>(op, value, rm);
96 }
97 break;
98 }
99 case ColumnType::kUint32: {
100 if (IsNullable()) {
101 FilterIntoNumericSlow<uint32_t, true /* is_nullable */>(op, value, rm);
102 } else {
103 FilterIntoNumericSlow<uint32_t, false /* is_nullable */>(op, value, rm);
104 }
105 break;
106 }
107 case ColumnType::kInt64: {
108 if (IsNullable()) {
109 FilterIntoNumericSlow<int64_t, true /* is_nullable */>(op, value, rm);
110 } else {
111 FilterIntoNumericSlow<int64_t, false /* is_nullable */>(op, value, rm);
112 }
113 break;
114 }
115 case ColumnType::kDouble: {
116 if (IsNullable()) {
117 FilterIntoNumericSlow<double, true /* is_nullable */>(op, value, rm);
118 } else {
119 FilterIntoNumericSlow<double, false /* is_nullable */>(op, value, rm);
120 }
121 break;
122 }
123 case ColumnType::kString: {
124 FilterIntoStringSlow(op, value, rm);
125 break;
126 }
127 case ColumnType::kId: {
128 FilterIntoIdSlow(op, value, rm);
129 break;
130 }
131 }
132 }
133
134 template <typename T, bool is_nullable>
FilterIntoNumericSlow(FilterOp op,SqlValue value,RowMap * rm) const135 void Column::FilterIntoNumericSlow(FilterOp op,
136 SqlValue value,
137 RowMap* rm) const {
138 PERFETTO_DCHECK(IsNullable() == is_nullable);
139 PERFETTO_DCHECK(type_ == ToColumnType<T>());
140 PERFETTO_DCHECK(std::is_arithmetic<T>::value);
141
142 if (op == FilterOp::kIsNull) {
143 PERFETTO_DCHECK(value.is_null());
144 if (is_nullable) {
145 row_map().FilterInto(rm, [this](uint32_t row) {
146 return !nullable_vector<T>().Get(row).has_value();
147 });
148 } else {
149 rm->Intersect(RowMap());
150 }
151 return;
152 } else if (op == FilterOp::kIsNotNull) {
153 PERFETTO_DCHECK(value.is_null());
154 if (is_nullable) {
155 row_map().FilterInto(rm, [this](uint32_t row) {
156 return nullable_vector<T>().Get(row).has_value();
157 });
158 }
159 return;
160 }
161
162 if (value.type == SqlValue::Type::kDouble) {
163 double double_value = value.double_value;
164 if (std::is_same<T, double>::value) {
165 auto fn = [double_value](T v) {
166 // We static cast here as this code will be compiled even when T ==
167 // int64_t as we don't have if constexpr in C++11. In reality the cast
168 // is a noop but we cannot statically verify that for the compiler.
169 return compare::Numeric(static_cast<double>(v), double_value);
170 };
171 FilterIntoNumericWithComparatorSlow<T, is_nullable>(op, rm, fn);
172 } else {
173 auto fn = [double_value](T v) {
174 // We static cast here as this code will be compiled even when T ==
175 // double as we don't have if constexpr in C++11. In reality the cast is
176 // a noop but we cannot statically verify that for the compiler.
177 return compare::LongToDouble(static_cast<int64_t>(v), double_value);
178 };
179 FilterIntoNumericWithComparatorSlow<T, is_nullable>(op, rm, fn);
180 }
181 } else if (value.type == SqlValue::Type::kLong) {
182 int64_t long_value = value.long_value;
183 if (std::is_same<T, double>::value) {
184 auto fn = [long_value](T v) {
185 // We negate the return value as the long is always the first parameter
186 // for this function even though the LHS of the comparator should
187 // actually be |v|. This saves us having a duplicate implementation of
188 // the comparision function.
189 return -compare::LongToDouble(long_value, static_cast<double>(v));
190 };
191 FilterIntoNumericWithComparatorSlow<T, is_nullable>(op, rm, fn);
192 } else {
193 auto fn = [long_value](T v) {
194 // We static cast here as this code will be compiled even when T ==
195 // double as we don't have if constexpr in C++11. In reality the cast is
196 // a noop but we cannot statically verify that for the compiler.
197 return compare::Numeric(static_cast<int64_t>(v), long_value);
198 };
199 FilterIntoNumericWithComparatorSlow<T, is_nullable>(op, rm, fn);
200 }
201 } else {
202 rm->Intersect(RowMap());
203 }
204 }
205
206 template <typename T, bool is_nullable, typename Comparator>
FilterIntoNumericWithComparatorSlow(FilterOp op,RowMap * rm,Comparator cmp) const207 void Column::FilterIntoNumericWithComparatorSlow(FilterOp op,
208 RowMap* rm,
209 Comparator cmp) const {
210 switch (op) {
211 case FilterOp::kLt:
212 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
213 if (is_nullable) {
214 auto opt_value = nullable_vector<T>().Get(idx);
215 return opt_value && cmp(*opt_value) < 0;
216 }
217 return cmp(nullable_vector<T>().GetNonNull(idx)) < 0;
218 });
219 break;
220 case FilterOp::kEq:
221 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
222 if (is_nullable) {
223 auto opt_value = nullable_vector<T>().Get(idx);
224 return opt_value && cmp(*opt_value) == 0;
225 }
226 return cmp(nullable_vector<T>().GetNonNull(idx)) == 0;
227 });
228 break;
229 case FilterOp::kGt:
230 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
231 if (is_nullable) {
232 auto opt_value = nullable_vector<T>().Get(idx);
233 return opt_value && cmp(*opt_value) > 0;
234 }
235 return cmp(nullable_vector<T>().GetNonNull(idx)) > 0;
236 });
237 break;
238 case FilterOp::kNe:
239 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
240 if (is_nullable) {
241 auto opt_value = nullable_vector<T>().Get(idx);
242 return opt_value && cmp(*opt_value) != 0;
243 }
244 return cmp(nullable_vector<T>().GetNonNull(idx)) != 0;
245 });
246 break;
247 case FilterOp::kLe:
248 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
249 if (is_nullable) {
250 auto opt_value = nullable_vector<T>().Get(idx);
251 return opt_value && cmp(*opt_value) <= 0;
252 }
253 return cmp(nullable_vector<T>().GetNonNull(idx)) <= 0;
254 });
255 break;
256 case FilterOp::kGe:
257 row_map().FilterInto(rm, [this, &cmp](uint32_t idx) {
258 if (is_nullable) {
259 auto opt_value = nullable_vector<T>().Get(idx);
260 return opt_value && cmp(*opt_value) >= 0;
261 }
262 return cmp(nullable_vector<T>().GetNonNull(idx)) >= 0;
263 });
264 break;
265 case FilterOp::kIsNull:
266 case FilterOp::kIsNotNull:
267 PERFETTO_FATAL("Should be handled above");
268 }
269 }
270
FilterIntoStringSlow(FilterOp op,SqlValue value,RowMap * rm) const271 void Column::FilterIntoStringSlow(FilterOp op,
272 SqlValue value,
273 RowMap* rm) const {
274 PERFETTO_DCHECK(type_ == ColumnType::kString);
275
276 if (op == FilterOp::kIsNull) {
277 PERFETTO_DCHECK(value.is_null());
278 row_map().FilterInto(rm, [this](uint32_t row) {
279 return GetStringPoolStringAtIdx(row).data() == nullptr;
280 });
281 return;
282 } else if (op == FilterOp::kIsNotNull) {
283 PERFETTO_DCHECK(value.is_null());
284 row_map().FilterInto(rm, [this](uint32_t row) {
285 return GetStringPoolStringAtIdx(row).data() != nullptr;
286 });
287 return;
288 }
289
290 if (value.type != SqlValue::Type::kString) {
291 rm->Intersect(RowMap());
292 return;
293 }
294
295 NullTermStringView str_value = value.string_value;
296 PERFETTO_DCHECK(str_value.data() != nullptr);
297
298 switch (op) {
299 case FilterOp::kLt:
300 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
301 auto v = GetStringPoolStringAtIdx(idx);
302 return v.data() != nullptr && compare::String(v, str_value) < 0;
303 });
304 break;
305 case FilterOp::kEq:
306 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
307 auto v = GetStringPoolStringAtIdx(idx);
308 return v.data() != nullptr && compare::String(v, str_value) == 0;
309 });
310 break;
311 case FilterOp::kGt:
312 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
313 auto v = GetStringPoolStringAtIdx(idx);
314 return v.data() != nullptr && compare::String(v, str_value) > 0;
315 });
316 break;
317 case FilterOp::kNe:
318 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
319 auto v = GetStringPoolStringAtIdx(idx);
320 return v.data() != nullptr && compare::String(v, str_value) != 0;
321 });
322 break;
323 case FilterOp::kLe:
324 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
325 auto v = GetStringPoolStringAtIdx(idx);
326 return v.data() != nullptr && compare::String(v, str_value) <= 0;
327 });
328 break;
329 case FilterOp::kGe:
330 row_map().FilterInto(rm, [this, str_value](uint32_t idx) {
331 auto v = GetStringPoolStringAtIdx(idx);
332 return v.data() != nullptr && compare::String(v, str_value) >= 0;
333 });
334 break;
335 case FilterOp::kIsNull:
336 case FilterOp::kIsNotNull:
337 PERFETTO_FATAL("Should be handled above");
338 }
339 }
340
FilterIntoIdSlow(FilterOp op,SqlValue value,RowMap * rm) const341 void Column::FilterIntoIdSlow(FilterOp op, SqlValue value, RowMap* rm) const {
342 PERFETTO_DCHECK(type_ == ColumnType::kId);
343
344 if (op == FilterOp::kIsNull) {
345 PERFETTO_DCHECK(value.is_null());
346 rm->Intersect(RowMap());
347 return;
348 } else if (op == FilterOp::kIsNotNull) {
349 PERFETTO_DCHECK(value.is_null());
350 return;
351 }
352
353 if (value.type != SqlValue::Type::kLong) {
354 rm->Intersect(RowMap());
355 return;
356 }
357
358 uint32_t id_value = static_cast<uint32_t>(value.long_value);
359 switch (op) {
360 case FilterOp::kLt:
361 row_map().FilterInto(rm, [id_value](uint32_t idx) {
362 return compare::Numeric(idx, id_value) < 0;
363 });
364 break;
365 case FilterOp::kEq:
366 row_map().FilterInto(rm, [id_value](uint32_t idx) {
367 return compare::Numeric(idx, id_value) == 0;
368 });
369 break;
370 case FilterOp::kGt:
371 row_map().FilterInto(rm, [id_value](uint32_t idx) {
372 return compare::Numeric(idx, id_value) > 0;
373 });
374 break;
375 case FilterOp::kNe:
376 row_map().FilterInto(rm, [id_value](uint32_t idx) {
377 return compare::Numeric(idx, id_value) != 0;
378 });
379 break;
380 case FilterOp::kLe:
381 row_map().FilterInto(rm, [id_value](uint32_t idx) {
382 return compare::Numeric(idx, id_value) <= 0;
383 });
384 break;
385 case FilterOp::kGe:
386 row_map().FilterInto(rm, [id_value](uint32_t idx) {
387 return compare::Numeric(idx, id_value) >= 0;
388 });
389 break;
390 case FilterOp::kIsNull:
391 case FilterOp::kIsNotNull:
392 PERFETTO_FATAL("Should be handled above");
393 }
394 }
395
396 template <bool desc>
StableSort(std::vector<uint32_t> * out) const397 void Column::StableSort(std::vector<uint32_t>* out) const {
398 switch (type_) {
399 case ColumnType::kInt32: {
400 if (IsNullable()) {
401 StableSortNumeric<desc, int32_t, true /* is_nullable */>(out);
402 } else {
403 StableSortNumeric<desc, int32_t, false /* is_nullable */>(out);
404 }
405 break;
406 }
407 case ColumnType::kUint32: {
408 if (IsNullable()) {
409 StableSortNumeric<desc, uint32_t, true /* is_nullable */>(out);
410 } else {
411 StableSortNumeric<desc, uint32_t, false /* is_nullable */>(out);
412 }
413 break;
414 }
415 case ColumnType::kInt64: {
416 if (IsNullable()) {
417 StableSortNumeric<desc, int64_t, true /* is_nullable */>(out);
418 } else {
419 StableSortNumeric<desc, int64_t, false /* is_nullable */>(out);
420 }
421 break;
422 }
423 case ColumnType::kDouble: {
424 if (IsNullable()) {
425 StableSortNumeric<desc, double, true /* is_nullable */>(out);
426 } else {
427 StableSortNumeric<desc, double, false /* is_nullable */>(out);
428 }
429 break;
430 }
431 case ColumnType::kString: {
432 row_map().StableSort(out, [this](uint32_t a_idx, uint32_t b_idx) {
433 auto a_str = GetStringPoolStringAtIdx(a_idx);
434 auto b_str = GetStringPoolStringAtIdx(b_idx);
435
436 int res = compare::NullableString(a_str, b_str);
437 return desc ? res > 0 : res < 0;
438 });
439 break;
440 }
441 case ColumnType::kId:
442 row_map().StableSort(out, [](uint32_t a_idx, uint32_t b_idx) {
443 int res = compare::Numeric(a_idx, b_idx);
444 return desc ? res > 0 : res < 0;
445 });
446 }
447 }
448
449 template <bool desc, typename T, bool is_nullable>
StableSortNumeric(std::vector<uint32_t> * out) const450 void Column::StableSortNumeric(std::vector<uint32_t>* out) const {
451 PERFETTO_DCHECK(IsNullable() == is_nullable);
452 PERFETTO_DCHECK(ToColumnType<T>() == type_);
453
454 const auto& nv = nullable_vector<T>();
455 row_map().StableSort(out, [&nv](uint32_t a_idx, uint32_t b_idx) {
456 if (is_nullable) {
457 auto a_val = nv.Get(a_idx);
458 auto b_val = nv.Get(b_idx);
459
460 int res = compare::NullableNumeric(a_val, b_val);
461 return desc ? res > 0 : res < 0;
462 }
463 auto a_val = nv.GetNonNull(a_idx);
464 auto b_val = nv.GetNonNull(b_idx);
465
466 return desc ? compare::Numeric(a_val, b_val) > 0
467 : compare::Numeric(a_val, b_val) < 0;
468 });
469 }
470
row_map() const471 const RowMap& Column::row_map() const {
472 return table_->row_maps_[row_map_idx_];
473 }
474
475 } // namespace trace_processor
476 } // namespace perfetto
477