卢涛：以MySQL技能征服百万级数据，0.89秒的惊艳表现

参赛选手：卢涛

选手简介：ITPUB Oracle开发版版主

参赛数据库：MySQL

性能评测：百万级数据代码性能评测?0.89秒

综合得分：85.8

以下是卢涛选手的代码说明思路简介：

1. 采取查表法，预先用其他方法（（grubbyoo 编写的SQL ，552条6秒） （C语言566条0.3秒））生成4个数四则运算能算出24点的组合，包括点数从小到大排序拼接成字符串和输出结果，把它保存在SQL的CTE表中备查。

2. 为了解决采用拼接union select或values（）的长度超过10K字节限制的问题，主要采取了压缩空间的技巧。

3. 解决测试数据和已知结论对应关系。cards表包含数字1到10的全排列，共10000种。

4. 接下来的优化点主要在于建立更高效的关联字段。

以下是卢涛选手的算法说明，结尾附完整SQL：

---

算法说明

采取查表法，预先用其他方法（https://www.itpub.net/forum.php?mod=viewthread&tid=1061129&_dsign=2d19292d（grubbyoo 编写的SQL ，552条6秒） https://www.jb51.net/article/172480.htm （C语言566条0.3秒））生成4个数四则运算能算出24点的组合，包括点数从小到大排序拼接成字符串和输出结果，把它保存在SQL的CTE表中备查。

预处理数据

4个数四则运算能算出24点的组合：（一共有566种）

1118:(1+1+1)*8=24

1126:(1+1+2)*6=24

1127:(1+2)*(1+7)=24

1128:(1*1+2)*8=24

1129:(1+2)*(9-1)=24

11210:(1+1)*(2+10)=24

为了解决采用拼接union select或values（）的长度超过10K字节限制的问题，主要采取了以下压缩空间的技巧：

with a(s) as(values((

'1118:(1+1+1)*8')),((

'1126:(1+1+2)*6')),((

'1127:(1+2)*(1+7)')),((

'1128:(1*1+2)*8')),((

'1129:(1+2)*(9-1)')),((

'11210:(1+1)*(2+10)'))

因为点数10和其它数字长度不同，原数据采取字段分隔符“:”，所以用X代替10以便对齐，同时也节约了字段分隔符的开销。同时去掉换行符。

'78898-(7-9)*8','78808*0-7*8','78908*9/(0-7)','78000-(8-0)*7','88808-(8-0)*8']

方法1.将所有答案拼接成一个大字符串，然后根据每组答案之间的分隔符提取。

with recursive st as

(select?

'1118(1+1+1)*8,1126(1+1+2)*6,1127(1+2)*(1+7),1128(1*1+2)*8,1129(1+2)*(9-1),,88808-(8-0)*8,'

st)

,a1

as(

select 1 n, substr(st,1,instr(st,',')-1) s,instr(st,',')+1 p from st

union all?

select n+1 ,substr(st,p,regexp_instr(st,',',p)-p),regexp_instr(st,',',p)+1 from a1,st where n<566

)

方法2.用postgresql的数组保存每组答案，虽然代码长度比方法1的长度稍长，但实测效率更高，也没有超过10K字节限制。然后用unnest转换成CTE表。

with a1(s) as materialized(select unnest(array[

'1118(1+1+1)*8','1126(1+1+2)*6','1127(1+2)*(1+7)','1128(1*1+2)*8'

第二步是解决测试数据和已知结论对应关系。cards表包含数字1到10的全排列，共10000种。

因为算24点给出的数字顺序和算式的顺序可以不同，所以同样4个数字的组合，比如 1 3 6 1和1 1 3 6，都对应同样的结果。所以cards表和CTE表的行是多对一的关系。所以需要找到一种满足这个关系的关联条件。

把cards表的每组c1-c4按从小到大排序拼接成字符串，与上述CTE表做左外连接，用字符串前4个字符匹配作为连接条件，输出时把X替换回10，得出正确表达式。

排序的目的是重新排列card的点数顺序和CTE表的相同，比如 1 3 6 1的结果和1 1 3 6相同。

/*把每组c1-c4按从小到大排序拼接成字符串*/

,q as(select id,c1,c2,c3,c4,string_agg(case when a=10 then '0' else a::varchar end ,''order by a)::int s from (select id,c1,c2,c3,c4,unnest(array[c1,c2,c3,c4])a from poker24.cards)b group by id,c1,c2,c3,c4)

示例

select string_agg(a::varchar ,''order by a)::int s from unnest(array[1,1,3,6])t(a);

1136

select string_agg(a::varchar ,''order by a)::int s from unnest(array[1,3,6,1])t(a);

1136

接下来的优化点主要在于建立更高效的关联字段：

第1版，将对照表的4个字符的字符串和输出结果保存在一起，外连接条件是card的c1-c4字符串||'%' like CTE的点数和结果字符串，这是模糊查询，用时0.9秒。

第2版，将对照表的4个字符的字符串和输出结果分开保存，将外连接条件改为cards的c1-c4字符串 = CTE的点数字符串，用时0.1秒。

第3版，因为只有10一个数字是两位，把10替换为0不影响定位和恢复原样，所以把10替换为0，从而能把关联列数据类型改为int型，优化了0.03秒。

第4版，因为把cards表的每组c1-c4按从小到大排序拼接成字符串操作，需要先用数组unnest列转行，再string_agg排序拼接字符串，它的开销较大，所以用五进制位图保存4个点数，

它的思想是用五进制数的每一位表是c1-c4中出现某数字的次数，比如 1 1 3 6，就是5的1次方+5的1次方+5的3次方+5的6次方，这样 1 3 6 1的五进制位图结果和1 1 3 6相同，采用这个数字做关联字段就能够定位，从而省去了排序操作开销。

select (pow(5,1)+pow(5,1)+pow(5,3)+pow(5,6))::int bitmap; --1 1 3 6

15760

select (pow(5,1)+pow(5,3)+pow(5,6)+pow(5,1))::int bitmap; --1 3 6 1

15760

这一步优化了0.03秒。最后结果约为0.04秒。

为了检验计算出来的表达式，专门做了一个SQL：

select 'if eval(''24!='||replace(substr(a1.s,5),'0','10')||'''):print('''||replace(substr(a1.s,5),'0','10')||''')'from a1;

输出到文本文件

if eval('24!=(1+1+1)*8'):print('(1+1+1)*8')

if eval('24!=(1+1+2)*6'):print('(1+1+2)*6')

if eval('24!=(1+2)*(1+7)'):print('(1+2)*(1+7)')??

然后用python执行

D:\>python 24ev2.txt

8/(3-8/3) #经检验，是小数运算误差，不是错误

D:\>python

>>> 8/(3-8/3)

23.99999999999999

参赛完整SQL：

/*4个数能算24点的组合：（一共有566种），用0代替10以便对齐*/--create table t1 aswith recursive st as(select '1118(1+1+1)*8,1126(1+1+2)*6,1127(1+2)*(1+7),1128(1*1+2)*8,1129(1+2)*(9-1),1120(1+1)*(2+0),1134(1+1)*3*4,1135(1+3)*(1+5),1136(1*1+3)*6,1137(1*1+7)*3,1138(1-1+3)*8,1139(1+1)*(3+9),1130(0-(1+1))*3,1144(1+1+4)*4,1145(1*1+5)*4,1146(1-1+4)*6,1147(7-1*1)*4,1148(1+1)*(4+8),1149(4-1)*(9-1),1140(1+1)*0+4,11555*5-1*1,1156(5-1*1)*6,1157(1+1)*(5+7),1158(5-(1+1))*8,1166(1+1)*(6+6),11686*8/(1+1),1169(1+1)*9+6,1170(1+1)*7+0,1188(1+1)*8+8,1224(1+2)*2*4,1225(1+5)*(2+2),1226(1+2)*(2+6),1227(7-1)*(2+2),1228(2-1+2)*8,1229(1+2+9)*2,1220(1+2)*(0-2),1233(1+3)*2*3,1234(1+2+3)*4,1235(1+2)*(3+5),1236(3-1+2)*6,12371+2+3*7,1238(2-1)*3*8,12393*9-(1+2),1230(0-1*2)*3,1244(1+2)*(4+4),1245(5-1+2)*4,1246(2-1)*4*6,1247(1-2+7)*4,1248(1-2+4)*8,1249(9-(1+2))*4,12401*2*0+4,12551-2+5*5,1256(1-2+5)*6,12571*2*(5+7),1258(5-1*2)*8,1259(1+2)*5+9,12502*0-1+5,1266(1+2)*6+6,1267(7-(1+2))*6,1268(6-(1+2))*8,12691*2*9+6,1260(1+2)*0-6,1277(7*7-1)/2,1278(1+7)*2+8,12792*9-1+7,12701*2*7+0,12881*2*8+8,12898*9/(1+2),12800+(8-1)*2,1333(1+3)*(3+3),1334(1*3+3)*4,13351*3*(3+5),1336(6-1+3)*3,13371*3+3*7,1338(1+8)*3-3,1339(1+3)*(9-3),1330(1-3+0)*3,1344(4-1+3)*4,13451+3+4*5,13466/(1-3/4),13474*7-(1+3),1348(1+3)*4+8,1349(9-1*3)*4,1340(1+3)*(0-4),1356(1+5)*3+6,1357(3-1)*(5+7),1358(1-3+5)*8,13591*3*5+9,13503*0-(1+5),1366(1-3+6)*6,1367(7-1*3)*6,1368(6-1*3)*8,13696+(3-1)*9,13601*3*0-6,1377(7-1)*(7-3),1378(7-(1+3))*8,1379(1+7)*9/3,13700+(3-1)*7,1388(1+3)*8-8,13898*9/1/3,1380(0-1)/3*8,1399(9-1)/3*9,1390(1+0)*3-9,13001+3+0+0,1444(1+4)*4+4,14451*4+4*5,1446(1+6)*4-4,14474*7-1*4,14481*4*4+8,1449(1-4+9)*4,14401*4*(0-4),14554*5-(1-5),14566/(5/4-1),14571-5+4*7,1458(1+5)*(8-4),14599-(1-4)*5,1450(1-5)*(4-0),1466(1+4)*6-6,1467(1-4+7)*6,1468(1-4+6)*8,1469(9-(1+4))*6,1460(4-1)*0-6,1477(1+7)*(7-4),1478(7-1*4)*8,1479(1-9)*(4-7),1488(8-(1+4))*8,14898*9/(4-1),14901+4+9+0,14001*4+0+0,1555(5-1/5)*5,1556(1+5)*5-6,1559(1+5)*(9-5),1550(0-5)*5-1,15661*5*6-6,15671-7+5*6,1568(1-5+8)*6,1569(9-1*5)*6,1560(1+5)*(0-6),1578(1-5+7)*8,1579(1-7)*(5-9),15705*7-(1+0),1588(8-1*5)*8,1589(9-(1+5))*8,15801+5+8+0,15991+5+9+9,15901*5+9+0,1500(0+0)-(1-5),1666(6-1)*6-6,16686/(1-6/8),1669(1-6+9)*6,16601*6*(0-6),1679(1+7)*(9-6),16701+6+7+0,1688(1-6+8)*8,16891+6+8+9,16801*6+8+0,16991*6+9+9,1690(9+0)-(1-6),17791+7+7+9,1770(1+7)*(0-7),17881+7+8+8,17891*7+8+9,1780(8+0)-(1-7),1799(9+9)-(1-7),1790(1-9)*(7-0),18881*8+8+8,1889(8+9)-(1-8),1880(1-8+0)*8,2223(2+2)*2*3,2224(2+2+2)*4,2225(2*5+2)*2,2227(2*7-2)*2,2228(2+2)*(8-2),2229(2+9)*2+2,22202+2+2*0,2233(2+2)*(3+3),2234(2+2+4)*3,2235(2*5-2)*3,2236(2/2+3)*6,2237(2/2+7)*3,2238(2-2+3)*8,2239(2+2)*(9-3),2230(3+0)*2-2,2244(2*4-2)*4,22452+2+4*5,2246(2-2+4)*6,22474*7-(2+2),2248(2+2)*4+8,22492+4+2*9,2240(2+2)*(0-4),22555*5-2/2,2256(5-2/2)*6,22572*5+2*7,2258(5+8)*2-2,2259(9-(2-5))*2,2250(2+5)*2+0,2266(2+6)/2*6,2267(2+7)*2+6,2268(8-(2+2))*6,2269(6/2+9)*2,22602*0-(2-6),2277(7-(2-7))*2,2278(7-(2+2))*8,2270(0/2+7)*2,2288(2+2)*8-8,22892*9-(2-8),22802*8-2+0,22900-(2-9)*2,22002+2+0+0,2333(2+3+3)*3,2335(2+5)*3+3,2336(3-(2-3))*6,23372*3*(7-3),2338(2*3-3)*8,2339(2+3)*3+9,23303*0-2*3,2344(2+3)*4+4,2345(5-(2-3))*4,2346(3-2)*4*6,2347(2-3+7)*4,2348(2-3+4)*8,23492/3*4*9,23403*0-(2+4),23552-3+5*5,2356(2-3+5)*6,23573*7-(2-5),23582*8+3+5,23592*3*(9-5),2350(2+0)*(5-3),2366(2+3)*6-6,23676/2+3*7,2368(2+8)*3-6,2369(9-(2+3))*6,23602*3*(0-6),23772*7+3+7,2378(2+7)/3*8,2379(7+9)/2*3,23702*0-3+7,2388(8-(2+3))*8,2389(9-2*3)*8,23802*3+8+0,23992*3+9+9,23902+3+9+0,23000-(3-0)*2,2444(4-(2-4))*4,2445(2+5)*4-4,2446(2*4-4)*6,24472*4*(7-4),2448(2+4)*(8-4),2449(9-2)*4-4,24404-(2-4)*0,2455(5+5)*2+4,2456(2+4)*5-6,2457(5+7)/2*4,2458(2-4+5)*8,2459(2+4)*(9-5),24502*5+4+0,2466(2-4+6)*6,2467(2+6)*(7-4),24682/4*6*8,24692*4*(9-6),2460(2+4)*(0-6),2477(7+7)*2-4,2478(2*7-8)*4,24792*4+7+9,24700-(2-4)*7,24888-(2-4)*8,2489(9-(2+4))*8,24802+4+8+0,24992+4+9+9,24902*9-4+0,2400(4/0+2)*0,25572*7+5+5,2558(5/5+2)*8,25599-(2-5)*5,2550(5-2/0)*5,25666-(2-5)*6,2567(2-5+7)*6,2568(2-5+6)*8,25696/2*5+9,25602*6*0/5,25772*5+7+7,2578(2*5-7)*8,25795*7-(2+9),25702+5+7+0,25885*8-2*8,25892+5+8+9,2580(0-(2+5))*8,25902*0-5+9,2500(2+0)/5*0,26662*6+6+6,2667(7-6/2)*6,26682*6*(8-6),2669(2+6)*(9-6),26602+6+6+0,2678(2-6+7)*8,26792+6+7+9,2670(2+6)*(0-7),26882+6+8+8,26892/6*8*9,26802*6*(0-8),2699(6/9+2)*9,2690(2-0)*(6-9),2600(0+0)-(2-6),27782+7+7+8,2770(0/7+2)*7,2788(2-7+8)*8,2789(7+9)*2-8,2790(9+0)-(2-7),2700(2-0)*(7-0),28888/2*8-8,2889(2-8+9)*8,2880(8+0)-(2-8),2899(9+9)-(2-8),2890(2-9+0)*8,28008/2+0+0,29000/2+9+0,33333*3*3-3,3334(3*3-3)*4,33353*3+3*5,3336(3+3)*3+6,3337(3+3)*(7-3),3338(3+3-3)*8,3339(9-3/3)*3,33303*0-(3+3),33443*4+3*4,3345(3/3+5)*4,3346(3-3+4)*6,3347(7-3/3)*4,3348(3+3)*(8-4),33493*4+3+9,33555*5-3/3,3356(3+3)*5-6,3357(3*5-7)*3,3359(3+3)*(9-5),33503*3+5+0,3366(6/3+6)*3,33673*7-(3-6),3368(3*3-6)*8,33693*3+6+9,3360(3+3)*(0-6),3377(3/7+3)*7,33783*3+7+8,3379(3-7)*(3-9),33888/(3-8/3),3389(9-(3+3))*8,33803+3+8+0,33993+3+9+9,33903-9+3*0,3444(3+4)*4-4,3445(5-(3-4))*4,34463*4*(6-4),3447(3-4+7)*4,3448(3+4-4)*8,34494*9-3*4,3440(0-3)*4-4,34553-4+5*5,3456(3-4+5)*6,34573*4+5+7,3458(3+5)*4-8,3459(3*5-9)*4,34503*4/5*0,34663*4+6+6,34683*4*(8-6),3469(3-6+9)*4,34603*6-4+0,34773-7+4*7,34788-(3-7)*4,34793*4*(9-7),34703+4+7+0,34893+4+8+9,34803*4*(0-8),3499(9+9)/3*4,34003*0+4-0,3556(5+5)*3-6,3557(5-3)*(5+7),3558(3+5-5)*8,3559(9-5/5)*3,3566(3-5+6)*6,3567(5+7)/3*6,35686*8/(5-3),3569(3+5)*(9-6),35603+5+6+0,35783*7-5+8,35793+5+7+9,3570(3+5)*(0-7),35883+5+8+8,35893*9+5-8,35999/3*5+9,3590(3+9)/5*0,3500(0-0/5)*3,36666-(3-6)*6,36676*7-3*6,3668(3+6-6)*8,36693+6+6+9,3660(6-3)*0-6,3677(7-(6-7))*3,36783+6+7+8,36793*7-6+9,36707/3*6+0,36888/3*6+8,36898*9/(6-3),3680(6-8+0)*3,36993*9+6-9,3690(3-9)*(6-0),3600(3-6/0)*0,37773+7+7+7,3778(3+7-7)*8,3779(9-7/7)*3,37703*7-7+0,3788(7-3)*8-8,3789(7-8+9)*3,3799(3+9)*(9-7),37903*9+7-0,3700(0+0)-(3-7),3888(3+8-8)*8,38893*8*(9-8),3880(8*0-8)/3,38993*8+9-9,3890(9+0)-(3-8),38003*8+0-0,3999(9+9)-(3-9),3990(9+9-0)*3,3900(9-0/0)*3,44444+4+4*4,4445(4/4+5)*4,4446(4+4-4)*6,4447(4+4)*(7-4),4448(4+4)*4-8,44494-(4-9)*4,44404*0-4*4,44555*5-4/4,4456(5-4/4)*6,4457(4-5+7)*4,4458(4+4-5)*8,44504-(5-0)*4,4468(6-4)*(4+8),4469(4+4)*(9-6),44604+4+6+0,4477(4-4/7)*7,44784*7+4-8,44794+4+7+9,4470(4+4)*(0-7),44884+4+8+8,44894*9-(4+8),4480(4-8)*(4-0),4400(0*0-4)/4,45554-5+5*5,4556(4+5-5)*6,4557(7-5/5)*4,4558(4-5/5)*8,45594*5-5+9,45504+5+5+0,45664*6*(6-5),4567(6-4)*(5+7),4568(4+5-6)*8,45694+5+6+9,45604*5-6+0,45775*7-(4+7),45784+5+7+8,45799-(4-7)*5,45704-(5-7)*0,4588(5-8/4)*8,4589(5-8+9)*4,4580(4+8)/5*0,4599(9/9+5)*4,4590(4-0)*(5-9),45000/5*0+4,4666(4+6-6)*6,46674*6*(7-6),46684+6+6+8,46696-(4-6)*9,4660(6+0)/4*6,46774+6+7+7,4678(4+6-7)*8,4679(7+9)/4*6,46700-(4-6)*7,46888-(4-6)*8,46894*6*(9-8),46804-(6-8)*0,46994*6+9-9,46904*6*(0-9),46004*6+0-0,4777(7-7/7)*4,4778(4-7/7)*8,4788(4+7-8)*8,47898*9/(7-4),47808/4*7+0,4799(7-9/9)*4,47904*0-7-9,4700(7-0/0)*4,48888/4*8+8,4889(4+8-9)*8,4880(4+8)*(0-8),4899(4-9/9)*8,4890(4+9-0)*8,4800(0+0)-(4-8),4990(9+0)-(4-9),55555*5-5/5,55565*5+5-6,55595+5+5+9,5566(5+5-6)*6,55675*5+6-7,55685+5+6+8,55775+5+7+7,5578(5+5-7)*8,5570(5+7)/5*0,55885*5-8/8,55895*5+8-9,5580(5+0)/5*8,55995*5-9/9,55905*5+9-0,55005*5-0/0,5666(5-6/6)*6,56675+6+6+7,56686-(5-8)*6,56696*9-5*6,5660(6+6)/5*0,5677(5-7/7)*6,5678(5+7)*(8-6),56796-(5-7)*9,5688(5+6-8)*8,5689(6+9)/5*8,56805*6*8/0,56999-(6-9)*5,5690(5+9-0)*6,5600(0+0)/5*6,5779(5+7)*(9-7),57700-(5-7)*7,57888-(5-7)*8,5789(5+7-9)*8,5780(5+7)*(0-8),57909-(7-0)*5,57000/5*7+0,58885*8-8-8,58898*9/(8-5),5880(5+8-0)*8,5900(0+0)-(5-9),66666+6+6+6,6668(6+6)*(8-6),66696*6*6/9,66606*0-6*6,6679(6+6)*(9-7),66706-(7-0)*6,66886*8/(8-6),6689(6+6-9)*8,6680(6+6)*(0-8),6690(6+0)/6*9,6770(7+7-0)*6,67896*8/(9-7),67806*7-8-0,67996*7-9-9,6700(0-7)*0-6,68888-(6-8)*8,68898*9-6*8,68806*8/(0-8),6899(9+9)/6*8,68906-(8-0)*9,69900*9/6+9,6000(0+0)-(6-0),77900-(7-9)*7,78898-(7-9)*8,78808*0-7*8,78908*9/(0-7),78000-(8-0)*7,88808-(8-0)*8,'st),a1as(select 1 n, substr(st,1,instr(st,',')-1) s,instr(st,',')+1 p from stunion all select n+1 ,substr(st,p,regexp_instr(st,',',p)-p),regexp_instr(st,',',p)+1 from a1,st where n<566),a(s,result)as(select (pow(5,substr(a1.s,1,1))+pow(5,substr(a1.s,2,1))+pow(5,substr(a1.s,3,1))+pow(5,substr(a1.s,4,1))),replace(substr(a1.s,5),'0','10')from a1)/*把每组c1-c4按值保存到一个五进制的位图中*/,q as(select id,c1,c2,c3,c4,(pow(5,c1%10)+pow(5,c2%10)+pow(5,c3%10)+pow(5,c4%10)) s from poker24.cards)select id,c1,c2,c3,c4,result from q left join a on a.s = q.s;/*,x as(select id,c1,c2,c3,c4,result from q left join a on a.s = q.s)select count(distinct result),count(result) from x;*/

《数据库编程大赛》

下一次再聚！

感谢大家对本次《数据库编程大赛》的关注和支持，欢迎加入技术交流群，更多精彩活动不断，我们下次再相聚！地址：数据库编程大赛- SQL编程-数据库大赛-NineData-玖章算术