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