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/table.h"
18
19 namespace perfetto {
20 namespace trace_processor {
21
22 Table::Table() = default;
23 Table::~Table() = default;
24
Table(StringPool * pool)25 Table::Table(StringPool* pool) : string_pool_(pool) {}
26
operator =(Table && other)27 Table& Table::operator=(Table&& other) noexcept {
28 row_count_ = other.row_count_;
29 string_pool_ = other.string_pool_;
30
31 overlays_ = std::move(other.overlays_);
32 columns_ = std::move(other.columns_);
33 for (Column& col : columns_) {
34 col.table_ = this;
35 }
36 return *this;
37 }
38
Copy() const39 Table Table::Copy() const {
40 Table table = CopyExceptOverlays();
41 for (const ColumnStorageOverlay& overlay : overlays_) {
42 table.overlays_.emplace_back(overlay.Copy());
43 }
44 return table;
45 }
46
CopyExceptOverlays() const47 Table Table::CopyExceptOverlays() const {
48 Table table(string_pool_);
49 table.row_count_ = row_count_;
50 for (const Column& col : columns_) {
51 table.columns_.emplace_back(col, &table, col.index_in_table(),
52 col.overlay_index());
53 }
54 return table;
55 }
56
Sort(const std::vector<Order> & od) const57 Table Table::Sort(const std::vector<Order>& od) const {
58 if (od.empty())
59 return Copy();
60
61 // Return a copy if there is a single constraint to sort the table
62 // by a column which is already sorted.
63 const auto& first_col = GetColumn(od.front().col_idx);
64 if (od.size() == 1 && first_col.IsSorted() && !od.front().desc)
65 return Copy();
66
67 // Build an index vector with all the indices for the first |size_| rows.
68 std::vector<uint32_t> idx(row_count_);
69
70 if (od.size() == 1 && first_col.IsSorted()) {
71 // We special case a single constraint in descending order as this
72 // happens any time the |max| function is used in SQLite. We can be
73 // more efficient as this column is already sorted so we simply need
74 // to reverse the order of this column.
75 PERFETTO_DCHECK(od.front().desc);
76 std::iota(idx.rbegin(), idx.rend(), 0);
77 } else {
78 // As our data is columnar, it's always more efficient to sort one column
79 // at a time rather than try and sort lexiographically all at once.
80 // To preserve correctness, we need to stably sort the index vector once
81 // for each order by in *reverse* order. Reverse order is important as it
82 // preserves the lexiographical property.
83 //
84 // For example, suppose we have the following:
85 // Table {
86 // Column x;
87 // Column y
88 // Column z;
89 // }
90 //
91 // Then, to sort "y asc, x desc", we could do one of two things:
92 // 1) sort the index vector all at once and on each index, we compare
93 // y then z. This is slow as the data is columnar and we need to
94 // repeatedly branch inside each column.
95 // 2) we can stably sort first on x desc and then sort on y asc. This will
96 // first put all the x in the correct order such that when we sort on
97 // y asc, we will have the correct order of x where y is the same (since
98 // the sort is stable).
99 //
100 // TODO(lalitm): it is possible that we could sort the last constraint (i.e.
101 // the first constraint in the below loop) in a non-stable way. However,
102 // this is more subtle than it appears as we would then need special
103 // handling where there are order bys on a column which is already sorted
104 // (e.g. ts, id). Investigate whether the performance gains from this are
105 // worthwhile. This also needs changes to the constraint modification logic
106 // in DbSqliteTable which currently eliminates constraints on sorted
107 // columns.
108 std::iota(idx.begin(), idx.end(), 0);
109 for (auto it = od.rbegin(); it != od.rend(); ++it) {
110 columns_[it->col_idx].StableSort(it->desc, &idx);
111 }
112 }
113
114 // Return a copy of this table with the RowMaps using the computed ordered
115 // RowMap.
116 Table table = CopyExceptOverlays();
117 RowMap rm(std::move(idx));
118 for (const ColumnStorageOverlay& overlay : overlays_) {
119 table.overlays_.emplace_back(overlay.SelectRows(rm));
120 PERFETTO_DCHECK(table.overlays_.back().size() == table.row_count());
121 }
122
123 // Remove the sorted and row set flags from all the columns.
124 for (auto& col : table.columns_) {
125 col.flags_ &= ~Column::Flag::kSorted;
126 col.flags_ &= ~Column::Flag::kSetId;
127 }
128
129 // For the first order by, make the column flag itself as sorted but
130 // only if the sort was in ascending order.
131 if (!od.front().desc) {
132 table.columns_[od.front().col_idx].flags_ |= Column::Flag::kSorted;
133 }
134
135 return table;
136 }
137
138 } // namespace trace_processor
139 } // namespace perfetto
140