递归相关表达式如何加速不同的查询？

Question

我发现这篇文章是关于加快不同查询的速度的：

使用递归CTE的超快DISTINCT：

USE     tempdb;
GO
DROP    TABLE dbo.Test;
GO
CREATE  TABLE 
        dbo.Test 
        (
        data            INTEGER NOT NULL,
        );
GO
CREATE  CLUSTERED INDEX c ON dbo.Test (data);
GO
-- Lots of duplicated values
INSERT  dbo.Test WITH (TABLOCK)
        (data)
SELECT  TOP (5000000)
        ROW_NUMBER() OVER (ORDER BY (SELECT 0)) / 117329
FROM    master.sys.columns C1,
        master.sys.columns C2,
        master.sys.columns C3;
GO



SET     STATISTICS TIME ON;

-- 1591ms CPU
SELECT  DISTINCT 
        data
FROM    dbo.Test;

-15ms CPU

WITH    RecursiveCTE
AS      (
        SELECT  data = MIN(T.data)
        FROM    dbo.Test T
        UNION   ALL
        SELECT  R.data
        FROM    (
                -- A cunning way to use TOP in the recursive part of a CTE Smile
                SELECT  T.data,
                        rn = ROW_NUMBER() OVER (ORDER BY T.data)
                FROM    dbo.Test T
                JOIN    RecursiveCTE R
                        ON  R.data < T.data
                ) R
        WHERE   R.rn = 1
        )
SELECT  *
FROM    RecursiveCTE
OPTION  (MAXRECURSION 0);

SET     STATISTICS TIME OFF;
GO
DROP    TABLE dbo.Test;

递归CTE的效率是100倍：-)这种加速对我当前的项目非常有价值，但是我不确定这种方法在哪种情况下是有益的。

老实说：我不明白为什么这会大大加快查询速度，以及为什么数据库本身无法进行此优化。您能解释一下它是如何工作的以及为什么如此有效吗？

编辑：我在sybase上看到类似的效果，因此这种方法似乎仅对sql-server无效。

子问题：递归CTE对其他数据库系统也有用吗？

Answer 1

保罗·怀特（Paul White）在“ 查找不同的值”*
部分的“性能优化整个查询计划”一文中详细解释了该“技巧” 。
*

为什么数据库本身无法进行此优化？

递归CTE是否对其他数据库系统也有用？

优化器不是完美的，它没有实现所有可能的技术。人们要求微软实施它。请参阅此连接项“实施索引跳过扫描”。由于无法修复，因此已关闭，但这并不意味着将来不会解决。其他DBMS可能已经实现了它（Connect项目说Oracle实现了此优化）。如果在DBMS引擎中实现了这种优化，则不需要此“技巧”，优化器将根据可用统计信息选择计算结果的最佳方法。

我不明白为什么这会大大加快查询速度。

我不确定这种方法在哪种情况下是有益的

简单DISTINCT查询将扫描整个索引。“扫描”表示它从磁盘读取索引的每一页，并汇总内存（或tempdb）中的值以获取不同值的列表。

如果您知道表有很多行，但是只有几个不同的不同值，那么读取所有这些重复值将浪费时间。递归CTE强制服务器为第一个不同的值寻找索引，然后为第二个值寻找索引，依此类推。“搜索”表示服务器在索引中使用二进制搜索来找到该值。通常，一次查找仅需要从磁盘读取几页。“索引”是一棵平衡的树。

如果表只有几个不同的值，则查找几次的速度要比读取索引的所有页的速度快。另一方面，如果有很多不同的值，那么顺序地读取所有页面比寻找每个连续的值要快。这应该使您知道在什么情况下此方法是有益的。

显然，如果表很小，则扫描它会更快。只有当表格变得“足够大”时，您才开始看到性能上的差异。

dba.se上有一个相关的问题：是否有可能针对不同/分组依据获得基于搜索的并行计划？