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/sqlite/sqlite_table.h"
18
19 #include <string.h>
20 #include <algorithm>
21 #include <cinttypes>
22 #include <map>
23
24 #include "perfetto/base/logging.h"
25
26 namespace perfetto {
27 namespace trace_processor {
28
29 namespace {
30
TypeToString(SqlValue::Type type)31 std::string TypeToString(SqlValue::Type type) {
32 switch (type) {
33 case SqlValue::Type::kString:
34 return "TEXT";
35 case SqlValue::Type::kLong:
36 return "BIG INT";
37 case SqlValue::Type::kDouble:
38 return "DOUBLE";
39 case SqlValue::Type::kBytes:
40 return "BLOB";
41 case SqlValue::Type::kNull:
42 PERFETTO_FATAL("Cannot map unknown column type");
43 }
44 PERFETTO_FATAL("Not reached"); // For gcc
45 }
46
OpToString(int op)47 std::string OpToString(int op) {
48 switch (op) {
49 case SQLITE_INDEX_CONSTRAINT_EQ:
50 return "=";
51 case SQLITE_INDEX_CONSTRAINT_NE:
52 return "!=";
53 case SQLITE_INDEX_CONSTRAINT_GE:
54 return ">=";
55 case SQLITE_INDEX_CONSTRAINT_GT:
56 return ">";
57 case SQLITE_INDEX_CONSTRAINT_LE:
58 return "<=";
59 case SQLITE_INDEX_CONSTRAINT_LT:
60 return "<";
61 case SQLITE_INDEX_CONSTRAINT_LIKE:
62 return "like";
63 case SQLITE_INDEX_CONSTRAINT_ISNULL:
64 return "is null";
65 case SQLITE_INDEX_CONSTRAINT_ISNOTNULL:
66 return "is not null";
67 case SQLITE_INDEX_CONSTRAINT_GLOB:
68 return "glob";
69 default:
70 PERFETTO_FATAL("Operator to string conversion not impemented for %d", op);
71 }
72 }
73
QcDebugStr(const QueryConstraints & qc,const SqliteTable::Schema & schema)74 std::string QcDebugStr(const QueryConstraints& qc,
75 const SqliteTable::Schema& schema) {
76 std::string str_result;
77 str_result.reserve(512);
78
79 str_result.append("C");
80 str_result.append(std::to_string(qc.constraints().size()));
81 str_result.append(",");
82 for (const auto& cs : qc.constraints()) {
83 str_result.append(schema.columns()[static_cast<size_t>(cs.column)].name());
84 str_result.append(" ");
85 str_result.append(OpToString(cs.op));
86 str_result.append(",");
87 }
88 str_result.back() = ';';
89
90 str_result.append("O");
91 str_result.append(std::to_string(qc.order_by().size()));
92 str_result.append(",");
93 for (const auto& ob : qc.order_by()) {
94 str_result.append(schema.columns()[static_cast<size_t>(ob.iColumn)].name());
95 str_result.append(" ");
96 str_result.append(std::to_string(ob.desc));
97 str_result.append(",");
98 }
99 str_result.back() = ';';
100
101 str_result.append("U");
102 str_result.append(std::to_string(qc.cols_used()));
103
104 return str_result;
105 }
106
107 } // namespace
108
109 // static
110 bool SqliteTable::debug = false;
111
112 SqliteTable::SqliteTable() = default;
113 SqliteTable::~SqliteTable() = default;
114
OpenInternal(sqlite3_vtab_cursor ** ppCursor)115 int SqliteTable::OpenInternal(sqlite3_vtab_cursor** ppCursor) {
116 // Freed in xClose().
117 *ppCursor = static_cast<sqlite3_vtab_cursor*>(CreateCursor().release());
118 return SQLITE_OK;
119 }
120
BestIndexInternal(sqlite3_index_info * idx)121 int SqliteTable::BestIndexInternal(sqlite3_index_info* idx) {
122 QueryConstraints qc(idx->colUsed);
123
124 for (int i = 0; i < idx->nConstraint; i++) {
125 const auto& cs = idx->aConstraint[i];
126 if (!cs.usable)
127 continue;
128 qc.AddConstraint(cs.iColumn, cs.op, i);
129 }
130
131 for (int i = 0; i < idx->nOrderBy; i++) {
132 int column = idx->aOrderBy[i].iColumn;
133 bool desc = idx->aOrderBy[i].desc;
134 qc.AddOrderBy(column, desc);
135 }
136
137 int ret = ModifyConstraints(&qc);
138 if (ret != SQLITE_OK)
139 return ret;
140
141 BestIndexInfo info;
142 info.estimated_cost = idx->estimatedCost;
143 info.estimated_rows = idx->estimatedRows;
144 info.sqlite_omit_constraint.resize(qc.constraints().size());
145
146 ret = BestIndex(qc, &info);
147
148 // Although the SQLite documentation promises that if we return
149 // SQLITE_CONSTRAINT, it won't chose this query plan, in practice, this causes
150 // the entire query to be abandonned even if there is another query plan which
151 // would definitely work. For this reason, we reserve idxNum == INT_MAX for
152 // invalid constraints and just keep the default estimated cost (which should
153 // lead to the plan not being chosen). In xFilter, we can then return
154 // SQLITE_CONSTRAINT if this query plan is still chosen.
155 if (ret == SQLITE_CONSTRAINT) {
156 idx->idxNum = kInvalidConstraintsInBestIndexNum;
157 return SQLITE_OK;
158 }
159
160 if (ret != SQLITE_OK)
161 return ret;
162
163 idx->orderByConsumed = qc.order_by().empty() || info.sqlite_omit_order_by;
164 idx->estimatedCost = info.estimated_cost;
165 idx->estimatedRows = info.estimated_rows;
166
167 // First pass: mark all constraints as omitted to ensure that any pruned
168 // constraints are not checked for by SQLite.
169 for (int i = 0; i < idx->nConstraint; ++i) {
170 auto& u = idx->aConstraintUsage[i];
171 u.omit = true;
172 }
173
174 // Second pass: actually set the correct omit and index values for all
175 // retained constraints.
176 for (uint32_t i = 0; i < qc.constraints().size(); ++i) {
177 auto& u = idx->aConstraintUsage[qc.constraints()[i].a_constraint_idx];
178 u.omit = info.sqlite_omit_constraint[i];
179 u.argvIndex = static_cast<int>(i) + 1;
180 }
181
182 auto out_qc_str = qc.ToNewSqlite3String();
183 if (SqliteTable::debug) {
184 PERFETTO_LOG(
185 "[%s::BestIndex] constraints=%s orderByConsumed=%d estimatedCost=%f "
186 "estimatedRows=%" PRId64,
187 name_.c_str(), QcDebugStr(qc, schema()).c_str(), idx->orderByConsumed,
188 idx->estimatedCost, static_cast<int64_t>(idx->estimatedRows));
189 }
190
191 idx->idxStr = out_qc_str.release();
192 idx->needToFreeIdxStr = true;
193 idx->idxNum = ++best_index_num_;
194
195 return SQLITE_OK;
196 }
197
ModifyConstraints(QueryConstraints *)198 int SqliteTable::ModifyConstraints(QueryConstraints*) {
199 return SQLITE_OK;
200 }
201
FindFunction(const char *,FindFunctionFn *,void **)202 int SqliteTable::FindFunction(const char*, FindFunctionFn*, void**) {
203 return 0;
204 }
205
Update(int,sqlite3_value **,sqlite3_int64 *)206 int SqliteTable::Update(int, sqlite3_value**, sqlite3_int64*) {
207 return SQLITE_READONLY;
208 }
209
ReadConstraints(int idxNum,const char * idxStr,int argc)210 bool SqliteTable::ReadConstraints(int idxNum, const char* idxStr, int argc) {
211 bool cache_hit = true;
212 if (idxNum != qc_hash_) {
213 qc_cache_ = QueryConstraints::FromString(idxStr);
214 qc_hash_ = idxNum;
215 cache_hit = false;
216 }
217
218 // Logging this every ReadConstraints just leads to log spam on joins making
219 // it unusable. Instead, only print this out when we miss the cache (which
220 // happens precisely when the constraint set from SQLite changes.)
221 if (SqliteTable::debug && !cache_hit) {
222 PERFETTO_LOG("[%s::ParseConstraints] constraints=%s argc=%d", name_.c_str(),
223 QcDebugStr(qc_cache_, schema_).c_str(), argc);
224 }
225 return cache_hit;
226 }
227
Cursor(SqliteTable * table)228 SqliteTable::Cursor::Cursor(SqliteTable* table) : table_(table) {
229 // This is required to prevent us from leaving this field uninitialised if
230 // we ever move construct the Cursor.
231 pVtab = table;
232 }
233 SqliteTable::Cursor::~Cursor() = default;
234
RowId(sqlite3_int64 *)235 int SqliteTable::Cursor::RowId(sqlite3_int64*) {
236 return SQLITE_ERROR;
237 }
238
Column(size_t index,std::string name,SqlValue::Type type,bool hidden)239 SqliteTable::Column::Column(size_t index,
240 std::string name,
241 SqlValue::Type type,
242 bool hidden)
243 : index_(index), name_(name), type_(type), hidden_(hidden) {}
244
Schema(std::vector<Column> columns,std::vector<size_t> primary_keys)245 SqliteTable::Schema::Schema(std::vector<Column> columns,
246 std::vector<size_t> primary_keys)
247 : columns_(std::move(columns)), primary_keys_(std::move(primary_keys)) {
248 for (size_t i = 0; i < columns_.size(); i++) {
249 PERFETTO_CHECK(columns_[i].index() == i);
250 }
251 for (auto key : primary_keys_) {
252 PERFETTO_CHECK(key < columns_.size());
253 }
254 }
255
256 SqliteTable::Schema::Schema() = default;
257 SqliteTable::Schema::Schema(const Schema&) = default;
258 SqliteTable::Schema& SqliteTable::Schema::operator=(const Schema&) = default;
259
ToCreateTableStmt() const260 std::string SqliteTable::Schema::ToCreateTableStmt() const {
261 std::string stmt = "CREATE TABLE x(";
262 for (size_t i = 0; i < columns_.size(); ++i) {
263 const Column& col = columns_[i];
264 stmt += " " + col.name();
265
266 if (col.type() != SqlValue::Type::kNull) {
267 stmt += " " + TypeToString(col.type());
268 } else if (std::find(primary_keys_.begin(), primary_keys_.end(), i) !=
269 primary_keys_.end()) {
270 PERFETTO_FATAL("Unknown type for primary key column %s",
271 col.name().c_str());
272 }
273 if (col.hidden()) {
274 stmt += " HIDDEN";
275 }
276 stmt += ",";
277 }
278 stmt += " PRIMARY KEY(";
279 for (size_t i = 0; i < primary_keys_.size(); i++) {
280 if (i != 0)
281 stmt += ", ";
282 stmt += columns_[primary_keys_[i]].name();
283 }
284 stmt += ")) WITHOUT ROWID;";
285 return stmt;
286 }
287
288 } // namespace trace_processor
289 } // namespace perfetto
290