SQL Server 2005 素數計算挑戰：CTE 遞迴 vs T-SQL 迴圈效能比較與優化思路

挑戰背景

尋求 SQL Server 計算素數最高效方法。作者嘗試兩種方案：

• CTE 遞迴：受限 MAXRECURSION 32767，無法產生大量素數。
• T-SQL 迴圈 + 表變數：產生 100 萬個素數耗時 7 分鐘，效能不理想。

方案一：T-SQL 迴圈（表變數 @prime）

SET NOCOUNT ON;
DECLARE @prime TABLE (prime INT NOT NULL PRIMARY KEY);
DECLARE @number INT = 13, @pc INT = 1;

WHILE @pc < 1000000
BEGIN
    IF NOT EXISTS (SELECT 1 FROM @prime WHERE @number % prime = 0 AND prime < SQRT(@number))
    BEGIN
        INSERT INTO @prime SELECT @number;
        SET @pc = @pc + 1;
    END
    SET @number = @number + 
        CASE 
            WHEN @number % 2 = 1 THEN 2
            WHEN @number % 3 = 2 THEN 2
            WHEN @number % 5 = 4 THEN 2
            WHEN @number % 7 = 6 THEN 2
            WHEN @number % 11 = 10 THEN 2
            ELSE 1
        END;
END
SELECT @pc;

方案二：CTE 遞迴（受限 32767 層）

WITH seq AS (
    SELECT 13 AS number
    UNION ALL
    SELECT s.number + 
        CASE 
            WHEN s.number % 2 = 1 THEN 2
            WHEN s.number % 3 = 2 THEN 2
            WHEN s.number % 5 = 4 THEN 2
            WHEN s.number % 7 = 6 THEN 2
            WHEN s.number % 11 = 10 THEN 2
            ELSE 1
        END
    FROM seq s
    WHERE number < 32767
),
prime AS (
    SELECT s.number
    FROM seq s
    WHERE NOT EXISTS (
        SELECT 1 FROM seq s2 
        WHERE s2.number < s.number AND s.number % s2.number = 0
    )
)
SELECT * FROM prime
OPTION (MAXRECURSION 32767);

效能瓶頸分析

1. 集合式運算缺失：關聯子查詢 NOT EXISTS (SELECT ... FROM @prime) 對每個候選數掃描整個素數表，複雜度 O(N²)。
2. 表變數無統計資料：最佳化器無法產生有效執行計畫，傾向 Nested Loop。
3. 遞迴深度限制：CTE 受限 MAXRECURSION，不適合大量產生。
4. 缺乏篩選法優化：未使用埃拉托斯特尼篩選法，仍在逐一試除。

優化方向建議

• 改用 暫存表 (#temp) 取代表變數，擁有統計資料、支援索引。
• 實作 篩選法 (Sieve of Eratosthenes)：建立候選數表，批次標記合數，集合式操作極大優於逐一試除。
• 利用 BULK INSERT 或 Table-Valued Parameters 減少往返。
• 考慮 CLR 整合（C# 實作篩選法）獲得數量級效能提升。
• 若僅需少量素數（<10,000），CTE 遞迴可接受；大量計算請移至應用層或 CLR。