trace_processor: improve costing algorithm to better account for sort
Up until now we've had a very simplistic algorithm for estimating cost
which only looked at filter constraints and ignored sorting. However, we
will need to consider sort constraints carefully as on real workloads
they dominate performance (if they exist).
Context: go/perfetto-tp-refactor
Bug: 135177627
Change-Id: Ie695a58b2c21055a862973bf0c1b72f941448f83
diff --git a/Android.bp b/Android.bp
index 47ad208..7ac370a 100644
--- a/Android.bp
+++ b/Android.bp
@@ -4692,6 +4692,7 @@
filegroup {
name: "perfetto_src_trace_processor_sqlite_unittests",
srcs: [
+ "src/trace_processor/sqlite/db_sqlite_table_unittest.cc",
"src/trace_processor/sqlite/query_constraints_unittest.cc",
"src/trace_processor/sqlite/sqlite3_str_split_unittest.cc",
],
diff --git a/src/trace_processor/sqlite/BUILD.gn b/src/trace_processor/sqlite/BUILD.gn
index 6f8c9e4..9eb0c78 100644
--- a/src/trace_processor/sqlite/BUILD.gn
+++ b/src/trace_processor/sqlite/BUILD.gn
@@ -40,6 +40,7 @@
perfetto_unittest_source_set("unittests") {
testonly = true
sources = [
+ "db_sqlite_table_unittest.cc",
"query_constraints_unittest.cc",
"sqlite3_str_split_unittest.cc",
]
diff --git a/src/trace_processor/sqlite/db_sqlite_table.cc b/src/trace_processor/sqlite/db_sqlite_table.cc
index 7c66bf1..5aa0a1c 100644
--- a/src/trace_processor/sqlite/db_sqlite_table.cc
+++ b/src/trace_processor/sqlite/db_sqlite_table.cc
@@ -115,7 +115,9 @@
int DbSqliteTable::BestIndex(const QueryConstraints& qc, BestIndexInfo* info) {
// TODO(lalitm): investigate SQLITE_INDEX_SCAN_UNIQUE for id columns.
- info->estimated_cost = static_cast<uint32_t>(EstimateCost(qc));
+ auto cost_and_rows = EstimateCost(*table_, qc);
+ info->estimated_cost = cost_and_rows.cost;
+ info->estimated_rows = cost_and_rows.rows;
return SQLITE_OK;
}
@@ -172,35 +174,72 @@
return SQLITE_OK;
}
-double DbSqliteTable::EstimateCost(const QueryConstraints& qc) {
+DbSqliteTable::QueryCost DbSqliteTable::EstimateCost(
+ const Table& table,
+ const QueryConstraints& qc) {
// Currently our cost estimation algorithm is quite simplistic but is good
// enough for the simplest cases.
- // TODO(lalitm): flesh out this algorithm to cover more complex cases.
+ // TODO(lalitm): replace hardcoded constants with either more heuristics
+ // based on the exact type of constraint or profiling the queries themselves.
- // If we have no constraints, we always return the size of the table as we
- // want to discourage the query planner from taking this road.
- const auto& constraints = qc.constraints();
- if (constraints.empty())
- return table_->size();
+ // We estimate the fixed cost of set-up and tear-down of a query in terms of
+ // the number of rows scanned.
+ constexpr double kFixedQueryCost = 1000.0;
- // This means we have at least one constraint. Check if any of the constraints
- // is an equality constraint on an id column.
- auto id_filter = [this](const QueryConstraints::Constraint& c) {
- uint32_t col_idx = static_cast<uint32_t>(c.column);
- const auto& col = table_->GetColumn(col_idx);
- return sqlite_utils::IsOpEq(c.op) && col.IsId();
- };
+ // Setup the variables for estimating the number of rows we will have at the
+ // end of filtering. Note that |current_row_count| should always be at least 1
+ // as otherwise SQLite can make some bad choices.
+ uint32_t current_row_count = table.size();
- // If we have a eq constraint on an id column, we return 0 as it's an O(1)
- // operation regardless of all the other constriants.
- auto it = std::find_if(constraints.begin(), constraints.end(), id_filter);
- if (it != constraints.end())
- return 1;
+ // If the table is empty, any constraint set only pays the fixed cost.
+ if (current_row_count == 0)
+ return QueryCost{kFixedQueryCost, 0};
- // Otherwise, we divide the number of rows in the table by the number of
- // constraints as a simple way of indiciating the more constraints we have
- // the better we can do.
- return table_->size() / constraints.size();
+ // Setup the variables for estimating the cost of filtering.
+ double filter_cost = 0.0;
+ const auto& cs = qc.constraints();
+ for (const auto& c : cs) {
+ const auto& col = table.GetColumn(static_cast<uint32_t>(c.column));
+ if (sqlite_utils::IsOpEq(c.op) && col.IsId()) {
+ // If we have an id equality constraint, it's a bit expensive to find
+ // the exact row but it filters down to a single row.
+ filter_cost += 100;
+ current_row_count = 1;
+ } else if (sqlite_utils::IsOpEq(c.op)) {
+ // If there is only a single equality constraint, we have special logic
+ // to sort by that column and then binary search if we see the constraint
+ // set often. Model this by dividing but the log of the number of rows as
+ // a good approximation. Otherwise, we'll need to do a full table scan.
+ filter_cost += cs.size() == 1
+ ? (2 * current_row_count) / log2(current_row_count)
+ : current_row_count;
+
+ // We assume that an equalty constraint will cut down the number of rows
+ // by approximate log of the number of rows.
+ double estimated_rows = current_row_count / log2(current_row_count);
+ current_row_count = std::max(static_cast<uint32_t>(estimated_rows), 1u);
+ } else {
+ // Otherwise, we will need to do a full table scan and we estimate we will
+ // maybe (at best) halve the number of rows.
+ filter_cost += current_row_count;
+ current_row_count = std::max(current_row_count / 2u, 1u);
+ }
+ }
+
+ // Now, to figure out the cost of sorting, multiply the final row count
+ // by |qc.order_by().size()| * log(row count). This should act as a crude
+ // estimation of the cost.
+ double sort_cost =
+ qc.order_by().size() * current_row_count * log2(current_row_count);
+
+ // The cost of iterating rows is more expensive than filtering the rows
+ // so multiply by an appropriate factor.
+ double iteration_cost = current_row_count * 2.0;
+
+ // To get the final cost, add up all the individual components.
+ double final_cost =
+ kFixedQueryCost + filter_cost + sort_cost + iteration_cost;
+ return QueryCost{final_cost, current_row_count};
}
std::unique_ptr<SqliteTable::Cursor> DbSqliteTable::CreateCursor() {
diff --git a/src/trace_processor/sqlite/db_sqlite_table.h b/src/trace_processor/sqlite/db_sqlite_table.h
index f6adf0f..5edf062 100644
--- a/src/trace_processor/sqlite/db_sqlite_table.h
+++ b/src/trace_processor/sqlite/db_sqlite_table.h
@@ -62,6 +62,10 @@
std::vector<Constraint> constraints_;
std::vector<Order> orders_;
};
+ struct QueryCost {
+ double cost;
+ uint32_t rows;
+ };
static void RegisterTable(sqlite3* db,
const Table* table,
@@ -78,9 +82,10 @@
int ModifyConstraints(QueryConstraints*) override;
int BestIndex(const QueryConstraints&, BestIndexInfo*) override;
- private:
- double EstimateCost(const QueryConstraints& qc);
+ // static for testing.
+ static QueryCost EstimateCost(const Table& table, const QueryConstraints& qc);
+ private:
const Table* table_ = nullptr;
};
diff --git a/src/trace_processor/sqlite/db_sqlite_table_unittest.cc b/src/trace_processor/sqlite/db_sqlite_table_unittest.cc
new file mode 100644
index 0000000..1228c28
--- /dev/null
+++ b/src/trace_processor/sqlite/db_sqlite_table_unittest.cc
@@ -0,0 +1,105 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "src/trace_processor/sqlite/db_sqlite_table.h"
+
+#include "test/gtest_and_gmock.h"
+
+namespace perfetto {
+namespace trace_processor {
+namespace {
+
+class TestTable : public Table {
+ public:
+ TestTable(uint32_t size) : Table(&pool_, nullptr) {
+ row_maps_.emplace_back(RowMap(0, size));
+ size_ = size;
+
+ columns_.emplace_back(Column::IdColumn(this, 0u, 0u));
+ columns_.emplace_back(
+ Column("a", &a_, Column::Flag::kNoFlag, this, 1u, 0u));
+ }
+
+ private:
+ StringPool pool_;
+ SparseVector<uint32_t> a_;
+};
+
+TEST(DbSqliteTableTest, EstimateCostEmpty) {
+ TestTable table(0u);
+
+ auto cost = DbSqliteTable::EstimateCost(table, QueryConstraints());
+ ASSERT_EQ(cost.rows, 0u);
+
+ // The cost should be 1000 (fixed cost).
+ ASSERT_DOUBLE_EQ(cost.cost, 1000.0);
+}
+
+TEST(DbSqliteTableTest, EstimateCostSmoke) {
+ TestTable table(1234u);
+
+ auto cost = DbSqliteTable::EstimateCost(table, QueryConstraints());
+ ASSERT_EQ(cost.rows, 1234u);
+
+ // The cost should be 1000 (fixed cost) + 2468 (iteration cost).
+ ASSERT_DOUBLE_EQ(cost.cost, 3468);
+}
+
+TEST(DbSqliteTableTest, EstimateCostFilterId) {
+ TestTable table(1234u);
+
+ QueryConstraints qc;
+ qc.AddConstraint(0u, SQLITE_INDEX_CONSTRAINT_EQ, 0u);
+
+ auto cost = DbSqliteTable::EstimateCost(table, qc);
+ ASSERT_EQ(cost.rows, 1u);
+
+ // The cost should be 1000 (fixed cost) + 100 (filter cost) + 2 (iteration
+ // cost).
+ ASSERT_DOUBLE_EQ(cost.cost, 1102);
+}
+
+TEST(DbSqliteTableTest, EstimateCostEqualityConstraint) {
+ TestTable table(1234u);
+
+ QueryConstraints qc;
+ qc.AddConstraint(1u, SQLITE_INDEX_CONSTRAINT_EQ, 0u);
+
+ auto cost = DbSqliteTable::EstimateCost(table, qc);
+ ASSERT_EQ(cost.rows, 120u);
+
+ // The cost should be 1000 (fixed cost) + 240.332 (filter cost) + 240
+ // (iteration cost).
+ ASSERT_DOUBLE_EQ(round(cost.cost), 1480);
+}
+
+TEST(DbSqliteTableTest, EstimateCostSort) {
+ TestTable table(1234u);
+
+ QueryConstraints qc;
+ qc.AddOrderBy(1u, false);
+
+ auto cost = DbSqliteTable::EstimateCost(table, qc);
+ ASSERT_EQ(cost.rows, 1234u);
+
+ // The cost should be 1000 (fixed cost) + 12672.102 (sort cost) + 2468
+ // (iteration cost).
+ ASSERT_DOUBLE_EQ(round(cost.cost), 16140);
+}
+
+} // namespace
+} // namespace trace_processor
+} // namespace perfetto
diff --git a/src/trace_processor/sqlite/sqlite_table.cc b/src/trace_processor/sqlite/sqlite_table.cc
index 8456ad2..d42e34d 100644
--- a/src/trace_processor/sqlite/sqlite_table.cc
+++ b/src/trace_processor/sqlite/sqlite_table.cc
@@ -17,6 +17,7 @@
#include "src/trace_processor/sqlite/sqlite_table.h"
#include <ctype.h>
+#include <inttypes.h>
#include <string.h>
#include <algorithm>
#include <map>
@@ -87,6 +88,7 @@
idx->orderByConsumed = qc.order_by().empty() || info.sqlite_omit_order_by;
idx->estimatedCost = info.estimated_cost;
+ idx->estimatedRows = info.estimated_rows;
// First pass: mark all constraints as omitted to ensure that any pruned
// constraints are not checked for by SQLite.
@@ -106,9 +108,10 @@
auto out_qc_str = qc.ToNewSqlite3String();
if (SqliteTable::debug) {
PERFETTO_LOG(
- "[%s::BestIndex] constraints=%s orderByConsumed=%d estimatedCost=%d",
+ "[%s::BestIndex] constraints=%s orderByConsumed=%d estimatedCost=%f "
+ "estimatedRows=%" PRId64,
name_.c_str(), out_qc_str.get(), idx->orderByConsumed,
- info.estimated_cost);
+ idx->estimatedCost, static_cast<int64_t>(idx->estimatedRows));
}
idx->idxStr = out_qc_str.release();
@@ -137,9 +140,13 @@
qc_hash_ = idxNum;
cache_hit = false;
}
- if (SqliteTable::debug) {
- PERFETTO_LOG("[%s::ParseConstraints] constraints=%s argc=%d cache_hit=%d",
- name_.c_str(), idxStr, argc, cache_hit);
+
+ // Logging this every ReadConstraints just leads to log spam on joins making
+ // it unusable. Instead, only print this out when we miss the cache (which
+ // happens precisely when the constraint set from SQLite changes.)
+ if (SqliteTable::debug && !cache_hit) {
+ PERFETTO_LOG("[%s::ParseConstraints] constraints=%s argc=%d", name_.c_str(),
+ idxStr, argc);
}
return cache_hit;
}
diff --git a/src/trace_processor/sqlite/sqlite_table.h b/src/trace_processor/sqlite/sqlite_table.h
index 2564ebc..a1a831e 100644
--- a/src/trace_processor/sqlite/sqlite_table.h
+++ b/src/trace_processor/sqlite/sqlite_table.h
@@ -167,7 +167,11 @@
bool sqlite_omit_order_by = false;
// Stores the estimated cost of this query.
- uint32_t estimated_cost = 0;
+ double estimated_cost = 0;
+
+ // Estimated row count. The default is set to 25 to match the SQLite
+ // default.
+ uint32_t estimated_rows = 25;
};
template <typename Context>