从一个游戏SQL的优化说起‐5 - l1t1/note GitHub Wiki

经过与程宁同学的讨论，我发现按数组逆序排序和位图对应的二进制数排序是等价的，所以把所有涉及数组的代码都改写为位图，在duckdb中速度有所提升，但在kingbase中，因为它不包含array_sort函数，用array_agg改写后（把select array_sort(array[3,1,5]);改写为select array_agg(a order by a)from unnest(array[3,1,5])t(a)），速度很慢，现在也很快了。生产中要慎用数组。

WITH 
games as(with t as (select chr(126983+i::int) pic from generate_series(0,26)t(i))select 2, string_agg(pic,''order by pic)j from t,generate_series(1,4) ),
-- 将108张牌分配给4个人，用轮流、顺序分配的方案
tmp0 AS (
    SELECT 
        a.i AS category,
        b.i AS seq,
        SUBSTRING(c.j, (a.i * 27) + b.i, 1) AS chr,
        ASCII(chr) - 126982 AS n,
        floor((n - 1)/ 9)::int AS hs,
        CASE n % 9 WHEN 0 THEN 9 ELSE n % 9 END AS pd
    FROM 
        generate_series(0,3) a(i),
        generate_series(1, 27) b(i),
        games c
),
-- 第一步，能凑成对子、2张顺子情况
tmp1 AS (
    SELECT 
        a.*,
        MIN(b.seq) FILTER (where a.pd = b.pd AND b.seq > a.seq) AS dz,
        MIN(b.seq) FILTER (where a.pd = b.pd + 1 AND b.seq > a.seq) AS sz1,
        MIN(b.seq) FILTER (where a.pd = b.pd - 1 AND b.seq > a.seq) AS sz2
    FROM 
        tmp0 a
    LEFT JOIN 
        tmp0 b ON a.category = b.category AND a.hs = b.hs
    GROUP BY 
        a.category, a.seq, a.chr, a.n, a.hs, a.pd
    ORDER BY 
        a.category, a.seq
),
-- 第二步，加能凑成三张顺子的情况
tmp2 AS (
    SELECT 
        a.*,
        MIN(b.seq) FILTER (where a.pd = b.pd + 2 AND b.seq > a.seq AND sz1 IS NOT NULL) AS sz11,
        MIN(b.seq) FILTER (where a.pd = b.pd - 2 AND b.seq > a.seq AND sz2 IS NOT NULL) AS sz22,
        MIN(b.seq) FILTER (where a.pd = b.pd AND b.seq > a.dz AND dz IS NOT NULL) AS sz
    FROM 
        tmp1 a
    LEFT JOIN 
        tmp0 b ON a.category = b.category AND a.hs = b.hs
    GROUP BY 
        a.category, a.seq, a.chr, a.n, a.hs, a.pd, a.dz, a.sz1, a.sz2
    ORDER BY 
        a.category, a.seq
),
-- 生成所有可以形成3张组合的牌
tmp_3z AS (
    SELECT 
        category, 
        (1<<seq)+(1<<sz1)+(1<<sz11) AS b 
    FROM 
        tmp2 
    WHERE 
        sz11 IS NOT NULL
    UNION  
    SELECT 
        category, 
        (1<<seq)+(1<<sz2)+(1<<sz22) AS b 
    FROM 
        tmp2 
    WHERE 
        sz22 IS NOT NULL
    UNION 
    SELECT 
        category, 
        (1<<seq)+(1<<dz)+(1<<sz) AS b 
    FROM 
        tmp2 
    WHERE 
        sz IS NOT NULL
),
-- 生成所有对子组合
tmp_dz AS (
    SELECT 
        category, 
        (1<<seq)+(1<<dz) as b 
    FROM 
        tmp1 
    WHERE 
        dz IS NOT NULL
)
-- 生成所有可能的组合
,tmp_all AS (
    SELECT
        a.category,
        a.b AS bsz1,
        b.b AS bsz2,
        c.b AS bsz3,e.b AS bsz4,
        d.b AS bdz,
        a.b+b.b+c.b+d.b+e.b as b
    FROM
        tmp_3z a
    JOIN
        tmp_3z b ON a.category = b.category and a.b < b.b and a.b & b.b =0
    JOIN
        tmp_3z c ON a.category = c.category and a.b & c.b =0 and b.b & c.b =0 and b.b < c.b
    JOIN
        tmp_3z e ON a.category = e.category and a.b & e.b =0 and b.b & e.b =0 and c.b & e.b =0 and c.b<e.b
    JOIN
        tmp_dz d ON a.category = d.category and a.b & d.b =0 and b.b & d.b =0 and c.b & d.b =0 and e.b & d.b =0
)
-- 用最少摸牌次数能胡牌的组合
,tmp_min AS (
    SELECT
        row_number()over(partition by category order by b,category) as rn,*
    FROM
        tmp_all order by 1 limit 1
),
-- 最终结果
final_result AS (
    SELECT
        STRING_AGG(a.chr, '' ORDER BY a.chr) AS ret,
        STRING_AGG(a.chr, '' ORDER BY a.chr) FILTER (where (1<<a.seq)& bsz1 <>0) AS k1,
        STRING_AGG(a.chr, '' ORDER BY a.chr) FILTER (where (1<<a.seq)& bsz2 <>0) AS k2,
        STRING_AGG(a.chr, '' ORDER BY a.chr) FILTER (where (1<<a.seq)& bsz3 <>0) AS k3,
        STRING_AGG(a.chr, '' ORDER BY a.chr) FILTER (where (1<<a.seq)& bsz4 <>0) AS k4,
        STRING_AGG(a.chr, '' ORDER BY a.chr) FILTER (where (1<<a.seq)& bdz <>0) AS d

    FROM
        tmp1 a
    JOIN
        tmp_min m ON a.category = m.category and (1<<a.seq)& m.b <>0
)
SELECT * FROM  final_result;