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,const Table * parent)25 Table::Table(StringPool* pool, const Table* parent) : string_pool_(pool) {
26 if (!parent)
27 return;
28
29 // If this table has a parent, then copy over all the columns pointing to
30 // empty RowMaps.
31 for (uint32_t i = 0; i < parent->row_maps_.size(); ++i)
32 row_maps_.emplace_back();
33 for (const Column& col : parent->columns_)
34 columns_.emplace_back(col, this, columns_.size(), col.row_map_idx_);
35 }
36
operator =(Table && other)37 Table& Table::operator=(Table&& other) noexcept {
38 row_count_ = other.row_count_;
39 string_pool_ = other.string_pool_;
40
41 row_maps_ = std::move(other.row_maps_);
42 columns_ = std::move(other.columns_);
43 for (Column& col : columns_) {
44 col.table_ = this;
45 }
46 return *this;
47 }
48
Copy() const49 Table Table::Copy() const {
50 Table table = CopyExceptRowMaps();
51 for (const RowMap& rm : row_maps_) {
52 table.row_maps_.emplace_back(rm.Copy());
53 }
54 return table;
55 }
56
CopyExceptRowMaps() const57 Table Table::CopyExceptRowMaps() const {
58 Table table(string_pool_, nullptr);
59 table.row_count_ = row_count_;
60 for (const Column& col : columns_) {
61 table.columns_.emplace_back(col, &table, col.index_in_table(),
62 col.row_map_idx_);
63 }
64 return table;
65 }
66
Sort(const std::vector<Order> & od) const67 Table Table::Sort(const std::vector<Order>& od) const {
68 if (od.empty())
69 return Copy();
70
71 // Return a copy if there is a single constraint to sort the table
72 // by a column which is already sorted.
73 const auto& first_col = GetColumn(od.front().col_idx);
74 if (od.size() == 1 && first_col.IsSorted() && !od.front().desc)
75 return Copy();
76
77 // Build an index vector with all the indices for the first |size_| rows.
78 std::vector<uint32_t> idx(row_count_);
79
80 if (od.size() == 1 && first_col.IsSorted()) {
81 // We special case a single constraint in descending order as this
82 // happens any time the |max| function is used in SQLite. We can be
83 // more efficient as this column is already sorted so we simply need
84 // to reverse the order of this column.
85 PERFETTO_DCHECK(od.front().desc);
86 std::iota(idx.rbegin(), idx.rend(), 0);
87 } else {
88 // As our data is columnar, it's always more efficient to sort one column
89 // at a time rather than try and sort lexiographically all at once.
90 // To preserve correctness, we need to stably sort the index vector once
91 // for each order by in *reverse* order. Reverse order is important as it
92 // preserves the lexiographical property.
93 //
94 // For example, suppose we have the following:
95 // Table {
96 // Column x;
97 // Column y
98 // Column z;
99 // }
100 //
101 // Then, to sort "y asc, x desc", we could do one of two things:
102 // 1) sort the index vector all at once and on each index, we compare
103 // y then z. This is slow as the data is columnar and we need to
104 // repeatedly branch inside each column.
105 // 2) we can stably sort first on x desc and then sort on y asc. This will
106 // first put all the x in the correct order such that when we sort on
107 // y asc, we will have the correct order of x where y is the same (since
108 // the sort is stable).
109 //
110 // TODO(lalitm): it is possible that we could sort the last constraint (i.e.
111 // the first constraint in the below loop) in a non-stable way. However,
112 // this is more subtle than it appears as we would then need special
113 // handling where there are order bys on a column which is already sorted
114 // (e.g. ts, id). Investigate whether the performance gains from this are
115 // worthwhile. This also needs changes to the constraint modification logic
116 // in DbSqliteTable which currently eliminates constraints on sorted
117 // columns.
118 std::iota(idx.begin(), idx.end(), 0);
119 for (auto it = od.rbegin(); it != od.rend(); ++it) {
120 columns_[it->col_idx].StableSort(it->desc, &idx);
121 }
122 }
123
124 // Return a copy of this table with the RowMaps using the computed ordered
125 // RowMap.
126 Table table = CopyExceptRowMaps();
127 RowMap rm(std::move(idx));
128 for (const RowMap& map : row_maps_) {
129 table.row_maps_.emplace_back(map.SelectRows(rm));
130 PERFETTO_DCHECK(table.row_maps_.back().size() == table.row_count());
131 }
132
133 // Remove the sorted flag from all the columns.
134 for (auto& col : table.columns_) {
135 col.flags_ &= ~Column::Flag::kSorted;
136 }
137
138 // For the first order by, make the column flag itself as sorted but
139 // only if the sort was in ascending order.
140 if (!od.front().desc) {
141 table.columns_[od.front().col_idx].flags_ |= Column::Flag::kSorted;
142 }
143
144 return table;
145 }
146
LookupJoin(JoinKey left,const Table & other,JoinKey right)147 Table Table::LookupJoin(JoinKey left, const Table& other, JoinKey right) {
148 // The join table will have the same size and RowMaps as the left (this)
149 // table because the left column is indexing the right table.
150 Table table(string_pool_, nullptr);
151 table.row_count_ = row_count_;
152 for (const RowMap& rm : row_maps_) {
153 table.row_maps_.emplace_back(rm.Copy());
154 }
155
156 for (const Column& col : columns_) {
157 // We skip id columns as they are misleading on join tables.
158 if (col.IsId())
159 continue;
160 table.columns_.emplace_back(col, &table, table.columns_.size(),
161 col.row_map_idx_);
162 }
163
164 const Column& left_col = columns_[left.col_idx];
165 const Column& right_col = other.columns_[right.col_idx];
166
167 // For each index in the left column, retrieve the index of the row inside
168 // the RowMap of the right column. By getting the index of the row rather
169 // than the row number itself, we can call |Apply| on the other RowMaps
170 // in the right table.
171 std::vector<uint32_t> indices(row_count_);
172 for (uint32_t i = 0; i < row_count_; ++i) {
173 SqlValue val = left_col.Get(i);
174 PERFETTO_CHECK(val.type != SqlValue::Type::kNull);
175 indices[i] = right_col.IndexOf(val).value();
176 }
177
178 // Apply the computed RowMap to each of the right RowMaps, adding it to the
179 // join table as we go.
180 RowMap rm(std::move(indices));
181 for (const RowMap& ot : other.row_maps_) {
182 table.row_maps_.emplace_back(ot.SelectRows(rm));
183 }
184
185 uint32_t left_row_maps_size = static_cast<uint32_t>(row_maps_.size());
186 for (const Column& col : other.columns_) {
187 // We skip id columns as they are misleading on join tables.
188 if (col.IsId())
189 continue;
190
191 // Ensure that we offset the RowMap index by the number of RowMaps in the
192 // left table.
193 table.columns_.emplace_back(col, &table, table.columns_.size(),
194 col.row_map_idx_ + left_row_maps_size);
195 }
196 return table;
197 }
198
199 } // namespace trace_processor
200 } // namespace perfetto
201