  Query re-optimization is an adaptive query processing technique that
re-invokes the optimizer at certain points in query execution. The goal is to
dynamically correct the cardinality estimation errors using the statistics
collected at runtime to adjust the query plan to improve the overall
performance. We identify a key weakness in existing re-optimization algorithms:
their subquery division and re-optimization trigger strategies rely heavily on
the optimizer's initial plan, which can be far away from optimal. We,
therefore, propose QuerySplit, a novel re-optimization algorithm that skips the
potentially misleading global plan and instead generates subqueries directly
from the logical plan as the basic re-optimization units. By developing a cost
function that prioritizes the execution of less "damaging" subqueries,
QuerySplit successfully postpones (sometimes avoids) the execution of complex
large joins to maximize their probability of having smaller input sizes. We
implemented QuerySplit in PostgreSQL and compared our solution against four
state-of-the-art re-optimization algorithms using the Join Order Benchmark. Our
experiments show that QuerySplit reduces the benchmark execution time by 35%
compared to the second-best alternative. The performance gap between QuerySplit
and an optimal optimizer is within 4%.
