PrestoSQL中WHERE过滤语句成本：两个查询的时间复杂度对比

时间复杂度差异 #

• 第二个查询（无WHERE过滤）：必须扫描TABLE1的全部N行数据，对每一行执行CASE表达式计算，最终输出所有结果，时间复杂度为O(N)（N为表的总行数）。
• 第一个查询（带WHERE过滤）：Presto的执行引擎会自动做谓词下推——也就是在读取数据阶段就过滤掉不符合col1=1或col1=2的行，实际只处理符合条件的M行（M远小于N），时间复杂度为O(M)。显然当M<N时，第一个查询的时间复杂度远低于第二个，耗时更短。

WHERE过滤的具体耗时情况 #

• 过滤操作本身的开销极低：
  • 如果col1有索引，Presto会直接通过索引定位目标行，过滤几乎不产生额外耗时；
  • 无索引时，每一行的过滤只是简单的数值比较操作，单条判断耗时可以忽略，相比全表扫描后处理大量行的CASE计算、数据传输开销，这点成本完全不值一提。
• 过滤的整体耗时主要由符合条件的行数M决定：M越小，后续需要处理和输出的数据量越少，查询整体速度提升越明显。

对疑惑的解答 #

带WHERE过滤的查询不会耗时更长——除非表中绝大多数行的col1都是1或2（M≈N），此时过滤的微小开销会抵消掉减少的处理量，两者耗时接近，但这种场景非常少见。正常情况下，过滤操作通过减少后续处理的数据量，能显著降低查询总耗时。

内容的提问来源于stack exchange，提问作者user98235