Least expected cost query optimization: what can we expect?
Least expected cost query optimization: what can we expect?
复制标题
最低预期成本查询优化：我们可以期待什么？
DOI：
10.1145/543613.543651
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
J. Gehrke
中科院分区：
文献类型：
--
作者：
Francis C. Chu;Joseph Y. Halpern;J. Gehrke
数据库查询优化文献中的一个标准假设是，足以优化“典型”情况---即各种参数（例如，可用内存的数量，谓词的选择性等）的情况。取代他们的“典型”值。在[CHS99]中据称，我们可以根据其预期成本选择计划来做得更好。在这里，我们更彻底地研究了这个问题。我们表明，在许多感兴趣的情况下，参数的“典型”价值通常确实给出了可接受的答案，前提是它是仔细选择的，并且我们只对最大程度地减少预期的运行时间感兴趣。但是，通过最大程度地减少预期的运行时间，我们实际上假设如果计划P1的运行时间是Plan P2的三倍，那么P1的恰好是P2的三倍。这样的假设并不总是合适的。我们表明，专注于最低预期的成本可能会导致许多感兴趣的成本功能可显着提高。
A standard assumption in the database query optimization literature is that it suffices to optimize for the "typical" case---that is, the case in which various parameters (e.g., the amount of available memory, the selectivities of predicates, etc.) take on their "typical" values. It was claimed in [CHS99] that we could do better by choosing plans based on their expected cost. Here we investigate this issue more thoroughly. We show that in many circumstances of interest, a "typical" value of the parameter often does give acceptable answers, provided that it is chosen carefully and we are interested only in minimizing expected running time. However, by minimizing the expected running time, we are effectively assuming that if plan p1 runs three times as long as plan p2, then p1 is exactly three times as bad as p2. An assumption like this is not always appropriate. We show that focusing on least expected cost can lead to significant improvement for a number of cost functions of interest.