1 /* 2 * Copyright (C) 2018 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/storage_table.h" 18 19 namespace perfetto { 20 namespace trace_processor { 21 22 StorageTable::StorageTable() = default; 23 StorageTable::~StorageTable() = default; 24 25 base::Optional<Table::Schema> StorageTable::Init(int, const char* const*) { 26 schema_ = CreateStorageSchema(); 27 return schema_.ToTableSchema(); 28 } 29 30 std::unique_ptr<Table::Cursor> StorageTable::CreateCursor() { 31 return std::unique_ptr<Cursor>(new Cursor(this)); 32 } 33 34 std::unique_ptr<RowIterator> StorageTable::CreateBestRowIterator( 35 const QueryConstraints& qc, 36 sqlite3_value** argv) { 37 const auto& cs = qc.constraints(); 38 auto obs = RemoveRedundantOrderBy(cs, qc.order_by()); 39 40 // Figure out whether the data is already ordered and which order we should 41 // traverse the data. 42 bool is_ordered, is_desc = false; 43 std::tie(is_ordered, is_desc) = IsOrdered(obs); 44 45 // Create the range iterator and if we are sorted, just return it. 46 auto index = CreateRangeIterator(cs, argv); 47 if (!index.error().empty()) { 48 SetErrorMessage(sqlite3_mprintf(index.error().c_str())); 49 return nullptr; 50 } 51 52 if (is_ordered) 53 return index.ToRowIterator(is_desc); 54 55 // Otherwise, create the sorted vector of indices and create the vector 56 // iterator. 57 return std::unique_ptr<VectorRowIterator>( 58 new VectorRowIterator(CreateSortedIndexVector(std::move(index), obs))); 59 } 60 61 FilteredRowIndex StorageTable::CreateRangeIterator( 62 const std::vector<QueryConstraints::Constraint>& cs, 63 sqlite3_value** argv) { 64 // Try and bound the search space to the smallest possible index region and 65 // store any leftover constraints to filter using bitvector. 66 uint32_t min_idx = 0; 67 uint32_t max_idx = RowCount(); 68 std::vector<size_t> bitvector_cs; 69 for (size_t i = 0; i < cs.size(); i++) { 70 const auto& c = cs[i]; 71 size_t column = static_cast<size_t>(c.iColumn); 72 auto bounds = schema_.GetColumn(column).BoundFilter(c.op, argv[i]); 73 74 min_idx = std::max(min_idx, bounds.min_idx); 75 max_idx = std::min(max_idx, bounds.max_idx); 76 77 // If the lower bound is higher than the upper bound, return a zero-sized 78 // range iterator. 79 if (min_idx >= max_idx) 80 return FilteredRowIndex(min_idx, min_idx); 81 82 if (!bounds.consumed) 83 bitvector_cs.emplace_back(i); 84 } 85 86 // Create an filter index and allow each of the columns filter on it. 87 FilteredRowIndex index(min_idx, max_idx); 88 for (const auto& c_idx : bitvector_cs) { 89 const auto& c = cs[c_idx]; 90 auto* value = argv[c_idx]; 91 92 const auto& schema_col = schema_.GetColumn(static_cast<size_t>(c.iColumn)); 93 schema_col.Filter(c.op, value, &index); 94 95 if (!index.error().empty()) 96 break; 97 } 98 return index; 99 } 100 101 std::pair<bool, bool> StorageTable::IsOrdered( 102 const std::vector<QueryConstraints::OrderBy>& obs) { 103 if (obs.size() == 0) 104 return std::make_pair(true, false); 105 106 if (obs.size() != 1) 107 return std::make_pair(false, false); 108 109 const auto& ob = obs[0]; 110 auto col = static_cast<size_t>(ob.iColumn); 111 return std::make_pair(schema_.GetColumn(col).HasOrdering(), ob.desc); 112 } 113 114 std::vector<QueryConstraints::OrderBy> StorageTable::RemoveRedundantOrderBy( 115 const std::vector<QueryConstraints::Constraint>& cs, 116 const std::vector<QueryConstraints::OrderBy>& obs) { 117 std::vector<QueryConstraints::OrderBy> filtered; 118 std::set<int> equality_cols; 119 for (const auto& c : cs) { 120 if (sqlite_utils::IsOpEq(c.op)) 121 equality_cols.emplace(c.iColumn); 122 } 123 for (const auto& o : obs) { 124 if (equality_cols.count(o.iColumn) > 0) 125 continue; 126 filtered.emplace_back(o); 127 } 128 return filtered; 129 } 130 131 std::vector<uint32_t> StorageTable::CreateSortedIndexVector( 132 FilteredRowIndex index, 133 const std::vector<QueryConstraints::OrderBy>& obs) { 134 PERFETTO_DCHECK(obs.size() > 0); 135 136 // Retrieve the index created above from the index. 137 std::vector<uint32_t> sorted_rows = index.ToRowVector(); 138 139 std::vector<StorageColumn::Comparator> comparators; 140 for (const auto& ob : obs) { 141 auto col = static_cast<size_t>(ob.iColumn); 142 comparators.emplace_back(schema_.GetColumn(col).Sort(ob)); 143 } 144 145 auto comparator = [&comparators](uint32_t f, uint32_t s) { 146 for (const auto& comp : comparators) { 147 int c = comp(f, s); 148 if (c != 0) 149 return c < 0; 150 } 151 return false; 152 }; 153 std::sort(sorted_rows.begin(), sorted_rows.end(), comparator); 154 155 return sorted_rows; 156 } 157 158 bool StorageTable::HasEqConstraint(const QueryConstraints& qc, 159 const std::string& col_name) { 160 size_t c_idx = schema().ColumnIndexFromName(col_name); 161 auto fn = [c_idx](const QueryConstraints::Constraint& c) { 162 return c.iColumn == static_cast<int>(c_idx) && sqlite_utils::IsOpEq(c.op); 163 }; 164 const auto& cs = qc.constraints(); 165 return std::find_if(cs.begin(), cs.end(), fn) != cs.end(); 166 } 167 168 StorageTable::Cursor::Cursor(StorageTable* table) 169 : Table::Cursor(table), table_(table) {} 170 171 int StorageTable::Cursor::Filter(const QueryConstraints& qc, 172 sqlite3_value** argv) { 173 iterator_ = table_->CreateBestRowIterator(qc, argv); 174 if (!iterator_) 175 return SQLITE_ERROR; 176 columns_ = table_->schema_.mutable_columns(); 177 return SQLITE_OK; 178 } 179 180 int StorageTable::Cursor::Next() { 181 iterator_->NextRow(); 182 return SQLITE_OK; 183 } 184 185 int StorageTable::Cursor::Eof() { 186 return iterator_->IsEnd(); 187 } 188 189 int StorageTable::Cursor::Column(sqlite3_context* context, int raw_col) { 190 size_t column = static_cast<size_t>(raw_col); 191 (*columns_)[column]->ReportResult(context, iterator_->Row()); 192 return SQLITE_OK; 193 } 194 195 } // namespace trace_processor 196 } // namespace perfetto 197