数据库编程大赛：一条SQL计算扑克牌24点题解

这是 Ninedata 的一个有趣的比赛，题目是用一条SQL给出扑克牌24点的计算表达式
我的解法更多是一种Hack的办法，向那些在SQL中实际搜索的实现学习。

分析

这个题目，如果使用程序求解，本质上是一个搜索题，可以再加上记忆化来优化。
需要处理多行，所以时间复杂度为 O(n*X)，X就是每个组合的计算时间。搜索复杂度不低，使用SQL的话，处理并不简单。
然而，这里有个不错的切入点，我们发现题目的答案其实并不多，去重后的正确解实际上只有566种。所以，可以预先把答案计算出来，直接放到SQL里。

尝试

正好MySQL支持JSON操作，所以答案可以用JSON存放，然后通过Key查询。此外，因为给出的4个数字顺序是不确定的，所以还需要做个排序。
这里采用的办法就是将4个数字排序。MySQL没有排序函数所以这里有点麻烦。
好在只有4个数字，可以直接输出最小值，除了最小值以外的最小值，除了最大值以外的最大值，最大值来解决排序问题。
一开始，我是直接将答案使用 JSON_EXTRA 输出，但发现性能并没有非常好，应该是因为MySQL没有过多优化JSON的处理。所以后续还做了一些别的尝试。

优化

LEFT JOIN

使用 JSON_TABLE 将JSON转成一张临时表，然后LEFT JOIN主表。但这样的性能依然没有起色，这是因为MySQL优化器的处理问题，使用了NLB。
解决办法是，将临时表 Group By一下。LEFT JOIN 才会使用HASH JOIN。

SQL过长

第二个问题是SQL过长，答案的长度已经接近10K，加上其它部分，就超过10k了。所以还需要对答案压缩编码，然后在SQL中解压。

编码处理

数字比字符串的匹配要快，数值大小为1-10，将有序的数字用10进制处理再相加，进一步优化了速度。

答案

以下是最终的答案，为了方便阅读，这里结果集编码就不放了。

SELECT `cards`.*,
       v AS result
  FROM `cards`
  LEFT JOIN(
    SELECT k,
           v
      FROM JSON_TABLE(CONVERT(UNCOMPRESS(UNHEX('结果集编码')),CHAR),'$[*]' COLUMNS(k int PATH '$.k',v varchar(32) PATH '$.v')) AS tp
     GROUP BY k
    ) AS kv ON((LEAST(c1,c2,c3,c4) -1) *1000+(IF(LEAST(c1,c2,c3,c4)=c1,LEAST(c2,c3,c4),IF(LEAST(c1,c2,c3,c4)=c2,LEAST(c1,c3,c4),IF(LEAST(c1,c2,c3,c4)=c3,LEAST(c1,c2,c4),LEAST(c1,c2,c3)))) -1) *100+(IF(GREATEST(c1,c2,c3,c4)=c1,GREATEST(c2,c3,c4),IF(GREATEST(c1,c2,c3,c4)=c2,GREATEST(c1,c3,c4),IF(GREATEST(c1,c2,c3,c4)=c3,GREATEST(c1,c2,c4),GREATEST(c1,c2,c3)))) -1) *10+GREATEST(c1,c2,c3,c4) -1)=k;

更近一步的优化

本身SQL方面的造诣确实是有所欠缺，也确实没有再在编码上下功夫。
其实可以在编码上做个加速。POW(4,c1)+POW(4,c2)+POW(4,c3)+POW(4,c4)就是个不错的办法。而如果使用WITH AS以及CASE WHEN应该可以减少POW的计算。
除此之外，将原先答案展开再JOIN，可能在数据量更大的情况下会更有利。

文章版权归作者所有，未经允许请勿转载。

THE END