1 /*
2 * Copyright (C) 2024 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/perfetto_sql/intrinsics/operators/interval_intersect_operator.h"
18
19 #include <sqlite3.h>
20 #include <algorithm>
21 #include <cerrno>
22 #include <cstddef>
23 #include <cstdint>
24 #include <iterator>
25 #include <memory>
26 #include <optional>
27 #include <string>
28 #include <utility>
29
30 #include "perfetto/base/logging.h"
31 #include "perfetto/base/status.h"
32 #include "perfetto/ext/base/flat_hash_map.h"
33 #include "perfetto/ext/base/hash.h"
34 #include "perfetto/ext/base/status_or.h"
35 #include "perfetto/ext/base/string_utils.h"
36 #include "perfetto/trace_processor/basic_types.h"
37 #include "perfetto/trace_processor/status.h"
38 #include "src/trace_processor/containers/interval_tree.h"
39 #include "src/trace_processor/perfetto_sql/engine/perfetto_sql_engine.h"
40 #include "src/trace_processor/sqlite/bindings/sqlite_result.h"
41 #include "src/trace_processor/sqlite/module_lifecycle_manager.h"
42 #include "src/trace_processor/sqlite/sqlite_utils.h"
43 #include "src/trace_processor/util/status_macros.h"
44
45 namespace perfetto::trace_processor {
46 namespace {
47
48 using Op = IntervalIntersectOperator;
49 using Cursor = Op::Cursor;
50 using Manager = sqlite::ModuleStateManager<Op>;
51 using ColumnsMap = Op::SchemaToTableColumnMap;
52
53 constexpr char kSliceSchema[] = R"(
54 CREATE TABLE x(
55 tab TEXT HIDDEN,
56 exposed_cols_str TEXT HIDDEN,
57 ts BIGINT,
58 ts_end BIGINT,
59 id BIGINT,
60 c0 ANY,
61 c1 ANY,
62 c2 ANY,
63 c3 ANY,
64 c4 ANY,
65 c5 ANY,
66 c6 ANY,
67 c7 ANY,
68 c8 ANY,
69 PRIMARY KEY(id)
70 ) WITHOUT ROWID
71 )";
72
73 enum SchemaColumnIds {
74 kTableName = 0,
75 kExposedCols = 1,
76 kTs = 2,
77 kTsEnd = 3,
78 kId = 4,
79 kAdditional = 5,
80 kMaxCol = 13
81 };
82
83 constexpr uint32_t kArgsCount = 2;
84
HashSqlValue(base::Hasher & h,const SqlValue & v)85 inline void HashSqlValue(base::Hasher& h, const SqlValue& v) {
86 switch (v.type) {
87 case SqlValue::Type::kString:
88 h.Update(v.AsString());
89 break;
90 case SqlValue::Type::kDouble:
91 h.Update(v.AsDouble());
92 break;
93 case SqlValue::Type::kLong:
94 h.Update(v.AsLong());
95 break;
96 case SqlValue::Type::kBytes:
97 PERFETTO_FATAL("Wrong type");
98 break;
99 case SqlValue::Type::kNull:
100 h.Update(nullptr);
101 break;
102 }
103 return;
104 }
105
ColIdForName(const Table * t,const std::string & col_name,const std::string & table_name)106 base::StatusOr<uint32_t> ColIdForName(const Table* t,
107 const std::string& col_name,
108 const std::string& table_name) {
109 auto x = t->ColumnIdxFromName(col_name);
110 if (!x.has_value()) {
111 return base::ErrStatus("interval_intersect: No column '%s' in table '%s'",
112 col_name.c_str(), table_name.c_str());
113 }
114 return *x;
115 }
116
CreateIntervalTrees(const Table * t,const std::string & table_name,const ColumnsMap & cols)117 base::StatusOr<Cursor::TreesMap> CreateIntervalTrees(
118 const Table* t,
119 const std::string& table_name,
120 const ColumnsMap& cols) {
121 uint32_t ts_col_idx = 0;
122 ASSIGN_OR_RETURN(ts_col_idx, ColIdForName(t, "ts", table_name));
123 uint32_t ts_end_col_idx = 0;
124 ASSIGN_OR_RETURN(ts_end_col_idx, ColIdForName(t, "ts_end", table_name));
125 uint32_t id_col_idx = 0;
126 ASSIGN_OR_RETURN(id_col_idx, ColIdForName(t, "id", table_name));
127
128 std::vector<Op::SchemaCol> cols_for_tree;
129 for (const auto& c : cols) {
130 if (c) {
131 cols_for_tree.push_back(*c);
132 }
133 }
134
135 base::FlatHashMap<Cursor::TreesKey, std::vector<IntervalTree::Interval>>
136 sorted_intervals;
137 for (Table::Iterator it = t->IterateRows(); it; ++it) {
138 IntervalTree::Interval i;
139 i.start = static_cast<uint64_t>(it.Get(ts_col_idx).AsLong());
140 i.end = static_cast<uint64_t>(it.Get(ts_end_col_idx).AsLong());
141 i.id = static_cast<uint32_t>(it.Get(id_col_idx).AsLong());
142
143 base::Hasher h;
144 for (const auto& c : cols_for_tree) {
145 SqlValue v = it.Get(c);
146 HashSqlValue(h, v);
147 }
148 sorted_intervals[h.digest()].push_back(i);
149 }
150
151 Cursor::TreesMap ret;
152 for (auto it = sorted_intervals.GetIterator(); it; ++it) {
153 IntervalTree x(it.value());
154 ret[it.key()] = std::make_unique<IntervalTree>(std::move(x));
155 }
156 return std::move(ret);
157 }
158
GetRhsValue(sqlite3_index_info * info,SchemaColumnIds col)159 base::StatusOr<SqlValue> GetRhsValue(sqlite3_index_info* info,
160 SchemaColumnIds col) {
161 sqlite3_value* val = nullptr;
162
163 int ret = -1;
164 for (int i = 0; i < info->nConstraint; ++i) {
165 auto c = info->aConstraint[i];
166 if (sqlite::utils::IsOpEq(c.op) && c.iColumn == col)
167 ret = sqlite3_vtab_rhs_value(info, i, &val);
168 }
169 if (ret != SQLITE_OK) {
170 return base::ErrStatus("Invalid RHS value.");
171 }
172
173 return sqlite::utils::SqliteValueToSqlValue(val);
174 }
175
GetTableFromRhsValue(PerfettoSqlEngine * engine,sqlite3_index_info * info)176 base::StatusOr<const Table*> GetTableFromRhsValue(PerfettoSqlEngine* engine,
177 sqlite3_index_info* info) {
178 ASSIGN_OR_RETURN(SqlValue table_name_val, GetRhsValue(info, kTableName));
179 if (table_name_val.type != SqlValue::kString) {
180 return base::ErrStatus("Table name is not a string");
181 }
182
183 const std::string table_name = table_name_val.AsString();
184 const Table* t = engine->GetTableOrNull(table_name);
185 if (!t) {
186 return base::ErrStatus("Table not registered");
187 }
188 return t;
189 }
190
GetExposedColumns(const std::string & exposed_cols_str,const Table * tab)191 base::StatusOr<ColumnsMap> GetExposedColumns(
192 const std::string& exposed_cols_str,
193 const Table* tab) {
194 ColumnsMap ret;
195 for (const std::string& col : base::SplitString(exposed_cols_str, ",")) {
196 std::string col_name = base::TrimWhitespace(col);
197 auto table_i = tab->ColumnIdxFromName(col_name);
198 if (!table_i) {
199 return base::ErrStatus("Didn't find column '%s'", col_name.c_str());
200 }
201 uint32_t schema_idx =
202 *base::CStringToUInt32(
203 std::string(col_name.begin() + 1, col_name.end()).c_str()) +
204 kAdditional;
205 ret[schema_idx] = static_cast<uint16_t>(*table_i);
206 }
207 return ret;
208 }
209
CreateCursorInnerData(Cursor::InnerData * inner,PerfettoSqlEngine * engine,const std::string & table_name,const ColumnsMap & cols)210 base::Status CreateCursorInnerData(Cursor::InnerData* inner,
211 PerfettoSqlEngine* engine,
212 const std::string& table_name,
213 const ColumnsMap& cols) {
214 // Build the tree for the runtime table if possible
215 const Table* t = engine->GetTableOrNull(table_name);
216 if (!t) {
217 return base::ErrStatus("interval_intersect operator: table not found");
218 }
219 ASSIGN_OR_RETURN(inner->trees, CreateIntervalTrees(t, table_name, cols));
220 return base::OkStatus();
221 }
222
CreateCursorOuterData(const Table * t,Cursor::OuterData * outer,const std::string & table_name)223 base::Status CreateCursorOuterData(const Table* t,
224 Cursor::OuterData* outer,
225 const std::string& table_name) {
226 outer->it = std::make_unique<Table::Iterator>(t->IterateRows());
227
228 ASSIGN_OR_RETURN(outer->additional_cols[kId],
229 ColIdForName(t, "id", table_name));
230 ASSIGN_OR_RETURN(outer->additional_cols[kTs],
231 ColIdForName(t, "ts", table_name));
232 ASSIGN_OR_RETURN(outer->additional_cols[kTsEnd],
233 ColIdForName(t, "ts_end", table_name));
234
235 return base::OkStatus();
236 }
237
238 } // namespace
239
Connect(sqlite3 * db,void * raw_ctx,int,const char * const * argv,sqlite3_vtab ** vtab,char **)240 int IntervalIntersectOperator::Connect(sqlite3* db,
241 void* raw_ctx,
242 int,
243 const char* const* argv,
244 sqlite3_vtab** vtab,
245 char**) {
246 // No args because we are not creating vtab, not like mipmap op.
247 if (int ret = sqlite3_declare_vtab(db, kSliceSchema); ret != SQLITE_OK) {
248 return ret;
249 }
250
251 // Create the state to access the engine in Filter.
252 auto ctx = GetContext(raw_ctx);
253 auto state = std::make_unique<State>();
254 state->engine = ctx->engine;
255
256 std::unique_ptr<Vtab> res = std::make_unique<Vtab>();
257 res->state = ctx->manager.OnCreate(argv, std::move(state));
258 *vtab = res.release();
259 return SQLITE_OK;
260 }
261
Disconnect(sqlite3_vtab * vtab)262 int IntervalIntersectOperator::Disconnect(sqlite3_vtab* vtab) {
263 std::unique_ptr<Vtab> tab(GetVtab(vtab));
264 sqlite::ModuleStateManager<IntervalIntersectOperator>::OnDestroy(tab->state);
265 return SQLITE_OK;
266 }
267
BestIndex(sqlite3_vtab * t,sqlite3_index_info * info)268 int IntervalIntersectOperator::BestIndex(sqlite3_vtab* t,
269 sqlite3_index_info* info) {
270 int n = info->nConstraint;
271
272 // Validate `table_name` constraint. We expect it to be a constraint on
273 // equality and on the kTableName column.
274 base::Status args_status =
275 sqlite::utils::ValidateFunctionArguments(info, kArgsCount, [](int c) {
276 return c == SchemaColumnIds::kTableName ||
277 c == SchemaColumnIds::kExposedCols;
278 });
279
280 PERFETTO_CHECK(args_status.ok());
281 if (!args_status.ok()) {
282 return SQLITE_CONSTRAINT;
283 }
284
285 // Find real rows count
286 PerfettoSqlEngine* engine = Manager::GetState(GetVtab(t)->state)->engine;
287 SQLITE_ASSIGN_OR_RETURN(t, const Table* tab,
288 GetTableFromRhsValue(engine, info));
289 if (!t) {
290 return sqlite::utils::SetError(t, "Table not registered");
291 }
292 uint32_t rows_count = tab->row_count();
293 info->estimatedRows = rows_count;
294
295 // Count usable constraints among args and required schema.
296 uint32_t count_usable = 0;
297 for (int i = 0; i < n; ++i) {
298 auto c = info->aConstraint[i];
299 if (c.iColumn < kAdditional) {
300 count_usable += c.usable;
301 }
302 }
303
304 // There is nothing more to do for only args constraints, which happens for
305 // the kOuter operator.
306 if (count_usable == kArgsCount) {
307 info->idxNum = kOuter;
308 info->estimatedCost = rows_count;
309 return SQLITE_OK;
310 }
311
312 // For inner we expect all constraints to be usable.
313 PERFETTO_CHECK(count_usable == 4);
314 if (count_usable != 4) {
315 return SQLITE_CONSTRAINT;
316 }
317
318 info->idxNum = kInner;
319
320 // Cost of querying centered interval tree.
321 info->estimatedCost = log2(rows_count);
322
323 // We are now doing BestIndex of kInner.
324
325 auto ts_found = false;
326 auto ts_end_found = false;
327 int argv_index = kAdditional;
328 auto* s = Manager::GetState(GetVtab(t)->state);
329
330 for (int i = 0; i < n; ++i) {
331 const auto& c = info->aConstraint[i];
332
333 // Ignore table_name constraints as we validated it before.
334 if (c.iColumn == kTableName || c.iColumn == kExposedCols) {
335 continue;
336 }
337
338 // We should omit all constraints.
339 // TODO(mayzner): Remove after we support handling other columns.
340 auto& usage = info->aConstraintUsage[i];
341 usage.omit = true;
342
343 // The constraints we are looking for is `A.ts < B.ts_end AND A.ts_end >
344 // B.ts`. That is why for `ts` column we can only have `kLt` operator and
345 // for `ts_end` only `kGt`.
346
347 // Add `ts` constraint.
348 if (c.iColumn == kTs && !ts_found) {
349 ts_found = true;
350 if (!sqlite::utils::IsOpLt(c.op)) {
351 return sqlite::utils::SetError(
352 t, "interval_intersect operator: `ts` columns has wrong operation");
353 }
354 // The index is moved by one.
355 usage.argvIndex = kTs + 1;
356 continue;
357 }
358
359 // Add `ts_end` constraint.
360 if (c.iColumn == kTsEnd && !ts_end_found) {
361 ts_end_found = true;
362 if (!sqlite::utils::IsOpGt(c.op)) {
363 return sqlite::utils::SetError(t,
364 "interval_intersect operator: `ts_end` "
365 "columns has wrong operation");
366 }
367 usage.argvIndex = kTsEnd + 1;
368 continue;
369 }
370
371 if (c.iColumn >= kAdditional) {
372 if (!sqlite::utils::IsOpEq(c.op)) {
373 return sqlite::utils::SetError(t,
374 "interval_intersect operator: `ts_end` "
375 "columns has wrong operation");
376 }
377 usage.argvIndex = argv_index++;
378 s->argv_to_col_map[static_cast<size_t>(c.iColumn)] = usage.argvIndex;
379 continue;
380 }
381
382 return sqlite::utils::SetError(
383 t, "interval_intersect operator: wrong constraint");
384 }
385
386 return SQLITE_OK;
387 }
388
Open(sqlite3_vtab *,sqlite3_vtab_cursor ** cursor)389 int IntervalIntersectOperator::Open(sqlite3_vtab*,
390 sqlite3_vtab_cursor** cursor) {
391 std::unique_ptr<Cursor> c = std::make_unique<Cursor>();
392 *cursor = c.release();
393 return SQLITE_OK;
394 }
395
Close(sqlite3_vtab_cursor * cursor)396 int IntervalIntersectOperator::Close(sqlite3_vtab_cursor* cursor) {
397 std::unique_ptr<Cursor> c(GetCursor(cursor));
398 return SQLITE_OK;
399 }
400
Filter(sqlite3_vtab_cursor * cursor,int idxNum,const char *,int,sqlite3_value ** argv)401 int IntervalIntersectOperator::Filter(sqlite3_vtab_cursor* cursor,
402 int idxNum,
403 const char*,
404 int,
405 sqlite3_value** argv) {
406 auto* c = GetCursor(cursor);
407 c->type = static_cast<OperatorType>(idxNum);
408
409 auto* t = GetVtab(c->pVtab);
410 PerfettoSqlEngine* engine = Manager::GetState(t->state)->engine;
411
412 // Table name constraint.
413 auto table_name_sql_val = sqlite::utils::SqliteValueToSqlValue(argv[0]);
414 if (table_name_sql_val.type != SqlValue::kString) {
415 return sqlite::utils::SetError(
416 t, "interval_intersect operator: table name is not a string");
417 }
418 std::string table_name = table_name_sql_val.AsString();
419
420 // Exposed columns constraint.
421 auto exposed_cols_sql_val = sqlite::utils::SqliteValueToSqlValue(argv[1]);
422 if (exposed_cols_sql_val.type != SqlValue::kString) {
423 return sqlite::utils::SetError(
424 t, "interval_intersect operator: exposed columns is not a string");
425 }
426 std::string exposed_cols_str = exposed_cols_sql_val.AsString();
427
428 // If the cursor has different table cached or differenct cols reset the
429 // cursor.
430 if (c->table_name != table_name || exposed_cols_str != c->exposed_cols_str) {
431 c->inner.trees.Clear();
432 c->outer.it.reset();
433 }
434 c->exposed_cols_str = exposed_cols_str;
435
436 if (c->type == kOuter) {
437 // We expect this function to be called only once per table, so recreate
438 // this if needed.
439 c->table = engine->GetTableOrNull(table_name);
440 c->table_name = table_name;
441 SQLITE_ASSIGN_OR_RETURN(t, c->outer.additional_cols,
442 GetExposedColumns(c->exposed_cols_str, c->table));
443 SQLITE_RETURN_IF_ERROR(
444 t, CreateCursorOuterData(c->table, &c->outer, table_name));
445 return SQLITE_OK;
446 }
447
448 PERFETTO_DCHECK(c->type == kInner);
449 const auto argv_map = Manager::GetState(GetVtab(t)->state)->argv_to_col_map;
450
451 // Create inner cursor if tree doesn't exist.
452 if (c->inner.trees.size() == 0) {
453 c->table = engine->GetTableOrNull(table_name);
454 c->table_name = table_name;
455 Op::SchemaToTableColumnMap exposed_cols_map;
456 SQLITE_ASSIGN_OR_RETURN(t, exposed_cols_map,
457 GetExposedColumns(c->exposed_cols_str, c->table));
458 SchemaToTableColumnMap new_map;
459 for (uint32_t i = 0; i < Op::kSchemaColumnsCount; i++) {
460 if (argv_map[i]) {
461 new_map[i] = exposed_cols_map[i];
462 }
463 }
464
465 SQLITE_RETURN_IF_ERROR(
466 c->pVtab,
467 CreateCursorInnerData(&c->inner, engine, table_name, new_map));
468 }
469
470 // Query |c.tree| on the interval and materialize the results.
471 auto ts_constraint = sqlite::utils::SqliteValueToSqlValue(argv[kTs]);
472 if (ts_constraint.type != SqlValue::kLong) {
473 return sqlite::utils::SetError(
474 t, "interval_intersect operator: `ts` constraint has to be a number");
475 }
476
477 auto ts_end_constraint = sqlite::utils::SqliteValueToSqlValue(argv[kTsEnd]);
478 if (ts_end_constraint.type != SqlValue::kLong) {
479 return sqlite::utils::SetError(
480 t,
481 "interval_intersect operator: `ts_end` constraint has to be a number");
482 }
483
484 uint64_t end = static_cast<uint64_t>(ts_constraint.AsLong());
485 uint64_t start = static_cast<uint64_t>(ts_end_constraint.AsLong());
486
487 base::Hasher h;
488 for (uint32_t i = 0; i < argv_map.size(); i++) {
489 if (argv_map[i]) {
490 uint32_t x = *argv_map[i];
491 HashSqlValue(h, sqlite::utils::SqliteValueToSqlValue(argv[x - 1]));
492 }
493 }
494
495 c->inner.Query(start, end, h.digest());
496
497 return SQLITE_OK;
498 }
499
Next(sqlite3_vtab_cursor * cursor)500 int IntervalIntersectOperator::Next(sqlite3_vtab_cursor* cursor) {
501 auto* c = GetCursor(cursor);
502
503 switch (c->type) {
504 case kInner:
505 c->inner.index++;
506 break;
507 case kOuter:
508 ++(*c->outer.it);
509 break;
510 }
511
512 return SQLITE_OK;
513 }
514
Eof(sqlite3_vtab_cursor * cursor)515 int IntervalIntersectOperator::Eof(sqlite3_vtab_cursor* cursor) {
516 auto* c = GetCursor(cursor);
517
518 switch (c->type) {
519 case kInner:
520 return c->inner.index >= c->inner.query_results.size();
521 case kOuter:
522 return !(*c->outer.it);
523 }
524 PERFETTO_FATAL("For GCC");
525 }
526
Column(sqlite3_vtab_cursor * cursor,sqlite3_context * ctx,int N)527 int IntervalIntersectOperator::Column(sqlite3_vtab_cursor* cursor,
528 sqlite3_context* ctx,
529 int N) {
530 auto* c = GetCursor(cursor);
531
532 if (c->type == kInner) {
533 PERFETTO_DCHECK(N == kId);
534 sqlite::result::Long(ctx, c->inner.GetResultId());
535 return SQLITE_OK;
536 }
537
538 PERFETTO_CHECK(c->type == kOuter);
539
540 switch (N) {
541 case kTs:
542 sqlite::result::Long(ctx, c->outer.Get(kTs).AsLong());
543 break;
544 case kTsEnd:
545 sqlite::result::Long(ctx, c->outer.Get(kTsEnd).AsLong());
546 break;
547 case kId:
548 sqlite::result::Long(ctx, c->outer.Get(kId).AsLong());
549 break;
550 case kExposedCols:
551 case kTableName:
552 return sqlite::utils::SetError(
553 GetVtab(cursor->pVtab),
554 "interval_intersect operator: invalid column");
555 default:
556 PERFETTO_DCHECK(N >= kAdditional && N <= kMaxCol);
557 sqlite::utils::ReportSqlValue(ctx, c->outer.Get(N));
558 break;
559 }
560
561 return SQLITE_OK;
562 }
563
Rowid(sqlite3_vtab_cursor *,sqlite_int64 *)564 int IntervalIntersectOperator::Rowid(sqlite3_vtab_cursor*, sqlite_int64*) {
565 return SQLITE_ERROR;
566 }
567
568 } // namespace perfetto::trace_processor
569