  Modern database systems rely on cost-based query optimizers to come up with
good execution plans for input queries. Such query optimizers rely on cost
models to estimate the costs of candidate query execution plans. A cost model
represents a function from a set of cost units to query execution cost, where
each cost unit specifies the unit cost of executing a certain type of query
processing operation (such as table scan or join). These cost units are
traditionally viewed as constants, whose values only depend on the platform
configuration where the database system runs on top of but are invariant for
queries processed by the database system. In this paper, we challenge this
classic view by thinking of these cost units as variables instead. We show
that, by varying the cost-unit values one can obtain query plans that
significantly outperform the default query plans returned by the query
optimizer when viewing the cost units as constants. We term this cost-unit
tuning process "query tuning" (QT) and show that it is similar to the
well-known hyper-parameter optimization (HPO) problem in AutoML. As a result,
any state-of-the-art HPO technologies can be applied to QT. We study the QT
problem in the context of anytime tuning, which is desirable in practice by
constraining the total time spent on QT within a given budget -- we call this
problem budget-aware query tuning. We further extend our study from tuning a
single query to tuning a workload with multiple queries, and we call this
generalized problem budget-aware workload tuning (WT), which aims for
minimizing the execution time of the entire workload. WT is more challenging as
one needs to further prioritize individual query tuning within the given time
budget. We propose solutions to both QT and WT and experimental evaluation
using both benchmark and real workloads demonstrates the efficacy of our
proposed solutions.
