基于评分函数的等规模文本分组SQL查询优化求助

需求回顾 #

• 基于带类型命名项的表创建物化视图，优化UI选择体验
• 同类型N个元素生成sqrt(N)个分组，每组规模约sqrt(N)（例如N=400时每组约20个）
• 分组名以名称范围标识（如A-B、C-EG），最长3字符
• 需支持二级层级分组，接受分组规模合理偏差
• 依赖物化视图保证查询性能与分组稳定性
• 当前问题：现有分组逻辑生成1-2个元素的小分组，不符合预期

核心问题分析 #

当前采用的「相邻首字符匹配数+振荡sqrt(N)次的SIN平方」评分函数，可能在局部最小值处误选边界，导致拆分出过小的分组。需在评分逻辑中加入约束，或通过后处理合并小分组。

优化方案 #

1. 调整评分函数，增加最小分组规模约束 #

在计算边界评分时，加入小分组惩罚项，避免在元素数量未达阈值的位置拆分：

WITH type_counts AS (
    SELECT item_type, sqrt_total = SQRT(COUNT(*)) 
    FROM your_table 
    GROUP BY item_type
),
ranked_items AS (
    SELECT
        t.item_type,
        t.item_name,
        rn = ROW_NUMBER() OVER (PARTITION BY t.item_type ORDER BY t.item_name),
        prev_first_char = LEFT(LAG(t.item_name) OVER (PARTITION BY t.item_type ORDER BY t.item_name), 1),
        c.sqrt_total
    FROM your_table t
    JOIN type_counts c ON t.item_type = c.item_type
)
SELECT
    item_type,
    item_name,
    -- 调整后的评分：原评分 + 小分组惩罚
    adjusted_score = 
        -- 原评分逻辑：首字符不匹配加1，结合SIN振荡项
        (CASE WHEN prev_first_char = LEFT(item_name,1) THEN 0 ELSE 1 END) 
        + POWER(SIN(rn * 2 * PI() / sqrt_total), 2)
        -- 惩罚项：距离上一个边界不足最小规模时，大幅提高评分
        + CASE WHEN rn - COALESCE(LAG(rn) OVER (PARTITION BY item_type ORDER BY rn), 0) < sqrt_total * 0.5 THEN 100 ELSE 0 END
FROM ranked_items

2. 后处理合并小分组 #

若调整评分后仍有小分组，在物化视图的最终查询中加入合并逻辑：

WITH original_groups AS (
    -- 原分组查询结果，需包含：item_type, group_id, group_name, item_count, sqrt_total
    SELECT ...
),
group_ranks AS (
    SELECT
        *,
        -- 标记连续的小分组
        merge_grp = SUM(CASE WHEN item_count >= sqrt_total * 0.5 THEN 1 ELSE 0 END) 
                    OVER (PARTITION BY item_type ORDER BY group_id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
    FROM original_groups
)
SELECT
    item_type,
    -- 合并后分组名称：拼接首尾分组的范围
    CONCAT(MIN(LEFT(group_name, CHARINDEX('-', group_name)-1)), '-', MAX(RIGHT(group_name, LEN(group_name)-CHARINDEX('-', group_name)))) AS merged_group_name,
    SUM(item_count) AS merged_item_count
FROM group_ranks
GROUP BY item_type, merge_grp

3. 二级层级分组实现 #

在一级分组基础上，对每个一级分组内的元素再次应用分组逻辑：

CREATE MATERIALIZED VIEW mv_item_groups AS
WITH type_counts AS (
    SELECT item_type, sqrt1 = SQRT(COUNT(*)), sqrt2 = SQRT(SQRT(COUNT(*)))
    FROM your_table GROUP BY item_type
),
first_level AS (
    -- 生成一级分组，逻辑同上述优化后的分组代码
    SELECT item_type, first_group_name, item_name, sqrt2
    FROM ...
)
SELECT
    item_type,
    first_group_name,
    -- 对每个一级分组内的元素生成二级分组
    CONCAT(MIN(LEFT(item_name, 1)), '-', MAX(RIGHT(item_name, 1))) AS second_group_name,
    COUNT(*) AS second_group_count
FROM first_level
GROUP BY item_type, first_group_name, FLOOR(ROW_NUMBER() OVER (PARTITION BY item_type, first_group_name ORDER BY item_name) / sqrt2)

4. 物化视图稳定性保障 #

• 为分组添加固定标识：基于分组名称范围生成哈希值（如HASHBYTES('SHA2_256', CONCAT(item_type, merged_group_name))），避免刷新时分组边界频繁变动
• 采用增量刷新（若数据库支持），仅更新新增/修改的元素对应的分组，减少全量刷新开销

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