SQL Server 2005 素數計算效能優化：CTE 與 T-SQL 實作比較

前言

在 SQL Server 2005 環境下計算大量素數（質數）一直是測試資料庫程式設計能力與效能調校的經典課題。本文將深入探討兩種主流實作方式——Common Table Expression (CTE) 遞迴查詢與傳統 T-SQL 迴圈——的優缺點、效能表現與適用場景，並提供優化建議。

一、傳統 T-SQL 迴圈實作

使用表變數搭配 WHILE 迴圈是最直觀的方法。核心邏輯為：維護一個已知素數表，依序測試候選數字是否能被現有素數整除，若無法整除則為新素數。

程式碼範例

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 VALUES (@number);
        SET @pc += 1;
    END

    -- 跳過能被 2,3,5,7,11 整除的數字以加速
    SET @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 AS PrimeCount;

效能分析

• 優點：邏輯清晰，易於理解與除錯；可精確控制迴圈流程。
• 缺點：執行 100 萬個素數約需 7 分鐘；表變數缺乏統計資訊，查詢最佳化器難以產生最佳執行計畫；頻繁的 INSERT 與 EXISTS 子查詢造成大量 I/O 與 CPU 開銷。

二、CTE 遞迴查詢實作

SQL Server 2005 引入的 CTE 支援遞迴查詢，可用集合導向思維替代逐行處理。

程式碼範例

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);

效能分析

• 優點：語法簡潔，符合 SQL 集合操作範式；避免顯式迴圈與暫存表維護。
• 缺點：MAXRECURSION 預設上限 100，雖可調高至 32767，但仍無法支援百萬級素數；遞迴查詢在大量資料時記憶體壓力大，且缺乏索引支援，效能隨資料量呈指數級惡化。

三、優化建議與替代方案

1. 改用暫存表（#temp）替代表變數

暫存表擁有統計資訊，查詢最佳化器能產生更佳執行計畫；並可建立索引加速 EXISTS 子查詢。

2. 採用埃拉托斯特尼篩法（Sieve of Eratosthenes）

將「逐一試除」改為「批次標記合數」，時間複雜度從 O(n√n) 降為 O(n log log n)。在 SQL Server 中可透過 CROSS JOIN 或 MERGE 陳述式實作集合式篩選。

3. 利用 CLR 整合

撰寫 C# 組件部署至 SQL Server，以 managed code 執行高效能素數演算法，再透過 SqlPipe 串流回傳結果，可突破 T-SQL 語言本身的效能瓶頸。

四、結語

雖然 CTE 與 T-SQL 迴圈皆可完成素數計算，但在百萬級資料量下，兩者均受限於關聯式引擎的集合操作特性與遞迴深度限制。實務上建議：

1. 小規模測試（< 10 萬）可用優化後的 T-SQL 迴圈；
2. 大規模計算優先考慮 CLR 整合或應用層預計算後匯入；
3. 若必須在 T-SQL 內完成，請採用篩法演算法並搭配暫存表與索引。

素數計算雖屬教學範例，但其效能優化思維——集合導向、索引策略、演算法複雜度權衡——完整對應至實際業務中的大量資料處理場景。