将NineData第三届数据库编程大赛冠军郑凌云的数独求解SQL改写为DuckDB
官方公众号终于公布了前三名的解题思路和程序源代码，其中郑凌云的文章地址是：https://mp.weixin.qq.com/s/2Aoz3CiDqkNEYkvXCa4NoA
这个SQL在postgresql上毫无疑问地比二、三名还快。我好奇它在DuckDB上性能如何，毕竟前面的改写都是变慢了。
主要修改部分
- 将
数组||元素改为数组||[元素] - 将convert_to函数去掉
- 将set_byte函数改为字符串拼接，注意前者索引从0开始到length-1，后者索引从1开始到length。
- 将
LEFT JOIN LATERAL (右表) ON 左表条件，改为LEFT JOIN LATERAL (右表 where 左表条件) ON True，消除Binder Error:Join condition for non-inner LATERAL JOIN must be a comparison between the left and right side。 - 将
FROM generate_subscripts(todo, 1) i改为FROM (select generate_subscripts(todo, 1) i)t(i)。 - 将#运算符改为xor函数。
- 将16进制数字0x??改为10进制。
- 用//运算符代替/做整除。
- 用length函数代替cardinality
完整修改结果如下
WITH RECURSIVE
bs_t AS MATERIALIZED (
SELECT id, replace(puzzle, E'
', '') AS bs
FROM sudoku9_9
)
--from bs_t limit 1;
,
init_t AS (
SELECT id, row_can, col_can, box_can, todo, bs AS done
FROM bs_t
CROSS JOIN LATERAL (
WITH board_t AS (
SELECT
array_agg(mask ORDER BY i) AS bd,
COALESCE(array_agg(((i // 9 + 1) << 8) | ((i % 9 + 1) << 4) | (i // 27 * 3 + i % 9 // 3 + 1))
FILTER (WHERE mask = 0), ARRAY[]::int[]) AS todo
FROM (
SELECT i, (1 << (ascii(substr(bs, i+1, 1)) - 49)) & 511 mask
FROM generate_series(0, 80) g(i)
) AS bd_t
)
SELECT
ARRAY[
xor(511, (bd[1] | bd[2] | bd[3] | bd[4] | bd[5] | bd[6] | bd[7] | bd[8] | bd[9])),
xor(511, (bd[10] | bd[11] | bd[12] | bd[13] | bd[14] | bd[15] | bd[16] | bd[17] | bd[18])),
xor(511, (bd[19] | bd[20] | bd[21] | bd[22] | bd[23] | bd[24] | bd[25] | bd[26] | bd[27])),
xor(511, (bd[28] | bd[29] | bd[30] | bd[31] | bd[32] | bd[33] | bd[34] | bd[35] | bd[36])),
xor(511, (bd[37] | bd[38] | bd[39] | bd[40] | bd[41] | bd[42] | bd[43] | bd[44] | bd[45])),
xor(511, (bd[46] | bd[47] | bd[48] | bd[49] | bd[50] | bd[51] | bd[52] | bd[53] | bd[54])),
xor(511, (bd[55] | bd[56] | bd[57] | bd[58] | bd[59] | bd[60] | bd[61] | bd[62] | bd[63])),
xor(511, (bd[64] | bd[65] | bd[66] | bd[67] | bd[68] | bd[69] | bd[70] | bd[71] | bd[72])),
xor(511, (bd[73] | bd[74] | bd[75] | bd[76] | bd[77] | bd[78] | bd[79] | bd[80] | bd[81]))
]::int[] AS row_can,
ARRAY[
xor(511, (bd[1] | bd[10] | bd[19] | bd[28] | bd[37] | bd[46] | bd[55] | bd[64] | bd[73])),
xor(511, (bd[2] | bd[11] | bd[20] | bd[29] | bd[38] | bd[47] | bd[56] | bd[65] | bd[74])),
xor(511, (bd[3] | bd[12] | bd[21] | bd[30] | bd[39] | bd[48] | bd[57] | bd[66] | bd[75])),
xor(511, (bd[4] | bd[13] | bd[22] | bd[31] | bd[40] | bd[49] | bd[58] | bd[67] | bd[76])),
xor(511, (bd[5] | bd[14] | bd[23] | bd[32] | bd[41] | bd[50] | bd[59] | bd[68] | bd[77])),
xor(511, (bd[6] | bd[15] | bd[24] | bd[33] | bd[42] | bd[51] | bd[60] | bd[69] | bd[78])),
xor(511, (bd[7] | bd[16] | bd[25] | bd[34] | bd[43] | bd[52] | bd[61] | bd[70] | bd[79])),
xor(511, (bd[8] | bd[17] | bd[26] | bd[35] | bd[44] | bd[53] | bd[62] | bd[71] | bd[80])),
xor(511, (bd[9] | bd[18] | bd[27] | bd[36] | bd[45] | bd[54] | bd[63] | bd[72] | bd[81]))
]::int[] AS col_can,
ARRAY[
xor(511, (bd[1] | bd[2] | bd[3] | bd[10] | bd[11] | bd[12] | bd[19] | bd[20] | bd[21])),
xor(511, (bd[4] | bd[5] | bd[6] | bd[13] | bd[14] | bd[15] | bd[22] | bd[23] | bd[24])),
xor(511, (bd[7] | bd[8] | bd[9] | bd[16] | bd[17] | bd[18] | bd[25] | bd[26] | bd[27])),
xor(511, (bd[28] | bd[29] | bd[30] | bd[37] | bd[38] | bd[39] | bd[46] | bd[47] | bd[48])),
xor(511, (bd[31] | bd[32] | bd[33] | bd[40] | bd[41] | bd[42] | bd[49] | bd[50] | bd[51])),
xor(511, (bd[34] | bd[35] | bd[36] | bd[43] | bd[44] | bd[45] | bd[52] | bd[53] | bd[54])),
xor(511, (bd[55] | bd[56] | bd[57] | bd[64] | bd[65] | bd[66] | bd[73] | bd[74] | bd[75])),
xor(511, (bd[58] | bd[59] | bd[60] | bd[67] | bd[68] | bd[69] | bd[76] | bd[77] | bd[78])),
xor(511, (bd[61] | bd[62] | bd[63] | bd[70] | bd[71] | bd[72] | bd[79] | bd[80] | bd[81]))
]::int[] AS box_can,
todo
FROM board_t
) AS rcb_t
)
--from init_t;
,
infer_t AS (
SELECT id, row_can, col_can, box_can, todo, done, TRUE AS expand
FROM init_t
UNION ALL
SELECT
id,
CASE
WHEN expand_ IS NOT NULL
THEN row_can[:r - 1] ||[ xor(row_can[r] , candidates)] || row_can[r + 1:]
ELSE row_can
END,
CASE
WHEN expand_ IS NOT NULL
THEN col_can[:c - 1] ||[ xor(col_can[c] , candidates)] || col_can[c + 1:]
ELSE col_can
END,
CASE
WHEN expand_ IS NOT NULL
THEN box_can[:b - 1] ||[ xor(box_can[b] , candidates)] || box_can[b + 1:]
ELSE box_can
END,
CASE
WHEN expand_ IS NOT NULL
THEN todo[:i - 1] || todo[i + 1:]
ELSE todo
END,
CASE
WHEN expand_ IS NOT NULL
--THEN set_byte(done, (r << 3) + r + c - 10, bit_count((candidates - 1))::int + 49)
THEN substr(done,1, (r << 3) + r + c - 10)|| chr( bit_count((candidates - 1))::int + 49)||substr(done, (r << 3) + r + c - 8)
ELSE done
END,
expand_
FROM infer_t
LEFT JOIN LATERAL (
SELECT i, r, c, b, candidates, TRUE AS expand_
FROM (select generate_subscripts(todo, 1) i)t(i)
CROSS JOIN LATERAL (
SELECT todo[i] >> 8 AS r, (todo[i] >> 4) & 15 AS c, todo[i] & 15 AS b
) AS infer_rcb_t
CROSS JOIN LATERAL (
SELECT row_can[r] & col_can[c] & box_can[b] AS candidates
) AS infer_can_t
WHERE bit_count(candidates) = 1
LIMIT 1
) AS infer_next_t ON TRUE
WHERE expand IS NOT NULL
),
infer_rst_t AS (
SELECT id, row_can, col_can, box_can, todo, done
FROM infer_t
WHERE expand IS NULL
)
--SELECT count(*) FROM infer_rst_t WHERE length(todo) = 0 ;
,
search_t AS (
SELECT
id,
0 AS deep,
FALSE AS back,
0 AS back_can,
row_can,
col_can,
box_can,
todo,
done,
ARRAY[]::int[][] stack,
CASE WHEN length(todo) = 0 THEN TRUE ELSE NULL::boolean END AS status
FROM infer_rst_t
UNION ALL
SELECT
id,
deep + 1,
CASE WHEN candidate != 0 THEN FALSE ELSE TRUE END,
s_cand,
CASE
WHEN candidate != 0
THEN row_can[:r - 1] || [xor(row_can[r] , candidate)] || row_can[r + 1:]
ELSE
row_can[:s_r - 1] ||[xor(row_can[s_r] , (s_cand & -s_cand))] ||row_can[s_r + 1:]
END,
CASE
WHEN candidate != 0
THEN col_can[:c - 1] || [xor(col_can[c] , candidate)] || col_can[c + 1:]
ELSE
col_can[:s_c - 1] ||[xor(col_can[s_c] , (s_cand & -s_cand))] ||col_can[s_c + 1:]
END,
CASE
WHEN candidate != 0
THEN box_can[:b - 1] || [xor(box_can[b] , candidate)] || box_can[b + 1:]
ELSE
box_can[:s_b - 1] ||[xor(box_can[s_b] , (s_cand & -s_cand))] ||box_can[s_b + 1:]
END,
CASE
WHEN candidate != 0
THEN todo[:i - 1] || todo[i + 1:]
ELSE [stack[sp][1]] || todo
END,
CASE
WHEN candidate != 0
--THEN set_byte(done, (r << 3) + r + c - 10, bit_count((candidate - 1))::int + 49)
THEN substr(done,1, (r << 3) + r + c - 10)|| chr( bit_count((candidate - 1))::int + 49)||substr(done, (r << 3) + r + c - 8)
ELSE done
END,
CASE
WHEN candidate != 0
THEN stack || ARRAY[ARRAY[(r << 8) | (c << 4) | b, candidates]]
ELSE stack[:sp - 1]
END,
CASE
WHEN candidate != 0
THEN CASE WHEN length(todo) <= 1 THEN TRUE ELSE NULL END
WHEN length(stack) = 0 THEN FALSE
-- 示例题库中最大检索深度只用459就够了，这里设定超65000才放弃
-- 应该完全足够解出所有题目了，正确率比速度更重要，慢就慢点
WHEN deep >= 6000 THEN FALSE
ELSE NULL
END
FROM search_t
LEFT JOIN LATERAL (
(
-- 先找1比sort limit 1更快
SELECT i AS i_, r_, c_, b_, candidates_
FROM (select generate_subscripts(todo, 1) i)t(i)
CROSS JOIN LATERAL (
SELECT todo[i] >> 8 AS r_, (todo[i] >> 4) & 15 AS c_, todo[i] & 15 AS b_
) AS search1_rcb_t
CROSS JOIN LATERAL (
SELECT row_can[r_] & col_can[c_] & box_can[b_] AS candidates_
) AS search1_can_t
WHERE bit_count(candidates_) = 1
LIMIT 1
)
UNION ALL
(
WITH mrv_t AS (
SELECT i AS i_, r_, c_, b_, candidates_, bit_count(candidates_) AS cnt
FROM (select generate_subscripts(todo, 1) i)t(i)
CROSS JOIN LATERAL (
SELECT todo[i] >> 8 AS r_, (todo[i] >> 4) & 15 AS c_, todo[i] & 15 AS b_
) AS search2_rcb_t
CROSS JOIN LATERAL (
SELECT row_can[r_] & col_can[c_] & box_can[b_] AS candidates_
) AS search2_can_t
),
-- 找min值比sort limit 1更快
mrv_min_t AS (
SELECT min(cnt) AS cnt FROM mrv_t
)
SELECT i_, r_, c_, b_, candidates_
FROM mrv_t
JOIN mrv_min_t
ON mrv_t.cnt = mrv_min_t.cnt
where back = FALSE LIMIT 1
)
LIMIT 1
) AS forward_t on true --ON back = FALSE
LEFT JOIN LATERAL (
SELECT
1 AS i_,
todo[1] >> 8 AS r_,
(todo[1] >> 4) & 15 AS c_,
todo[1] & 15 AS b_,
back_can & (back_can - 1) AS candidates_
where back = TRUE
) AS backward_t on true
CROSS JOIN LATERAL (
SELECT
COALESCE(backward_t.i_, forward_t.i_) AS i,
COALESCE(backward_t.r_, forward_t.r_) AS r,
COALESCE(backward_t.c_, forward_t.c_) AS c,
COALESCE(backward_t.b_, forward_t.b_) AS b,
COALESCE(backward_t.candidates_, forward_t.candidates_) AS candidates,
(COALESCE(backward_t.candidates_, forward_t.candidates_) &
-COALESCE(backward_t.candidates_, forward_t.candidates_)) AS candidate,
-- 这俩可能为NULL，为NULL时会判定为不可解，所以即使生成了一些NULL中间数据，会丢弃掉。我已确认不影响程序正确性
array_length(stack, 1) AS sp,
stack[array_length(stack, 1)][2] AS s_cand
) AS final_t
LEFT JOIN LATERAL (
SELECT
stack[sp][1] >> 8 AS s_r,
(stack[sp][1] >> 4) & 15 AS s_c,
stack[sp][1] & 15 s_b
where candidate = 0
) AS extra_t on true --ON candidate = 0
WHERE status IS NULL
)
--select * from search_t ;
SELECT
t.id AS id,
puzzle,
substr(done, 1, 9) || E'
' ||
substr(done, 10, 9) || E'
' ||
substr(done, 19, 9) || E'
' ||
substr(done, 28, 9) || E'
' ||
substr(done, 37, 9) || E'
' ||
substr(done, 46, 9) || E'
' ||
substr(done, 55, 9) || E'
' ||
substr(done, 64, 9) || E'
' ||
substr(done, 73, 9)
AS result
FROM sudoku9_9 t
LEFT JOIN search_rst_t USING(id)
;
中间有两个插曲。
1.由于马虎图省事复制粘贴，把本来是容易的事，变成一个排查不出的错误，算出的结果有一部分对，一部分错。问了郑凌云本人才知道，我把candidate错写成candidates, 这是不同的两个变量，前一个用于搜索，后一个用于推理。
2.由于SQL基本功不扎实，以为可以用CROSS JOIN LATERAL代替LEFT JOIN LATERAL, 结果也是一部分能算出来，还以为找到了优化点，结果是改错了。原理见文章。
最后测试性能，1000行数据，单线程要3秒，多线程要18秒，比postgresql中执行时间长了几十倍，和前面改写后程宁的SQL结果一个数量级，究竟是哪部分引起的，是JOIN LATERAL还是递归，还需要进一步研究。
