前言在新公司，经常会遇到几百行SQL代码，主要用于数据的获取和处理。因为公司用的是阿里的ADB，希望简化数据处理的逻辑，都在ADB上完成。这让我适应了一段时间。毕竟我以前的经验是尽量简化SQL，然后通过代码对获取的数据进行处理，所以我的SQL功底并不强。SQL不强，就学吧，所以在学习的过程中，突然想能不能用MySQL来解决算术题。这个过程遇到了很多坑，但是探索的过程还是很有趣的。大多数SQL语言细节或其他知识将在最后的参考部分给出相应的文章。这些文章是我学习SQL语法和解决具体问题的内容。八皇后棋中的皇后可以横、竖、斜走。所谓八皇后问题就是如何在一个8x8的棋盘上放置8个皇后，使得任意两个皇后不在同一水平线、垂直线或对角线上，从方向上来说，如下图所示，一个皇后放置在图中棋盘的(1,1)位置，图中绿色部分不能放置其他皇后。问题是：在一个8x8的棋盘上，8个皇后有多少种摆放方式？这是一个经典的回溯算法问题。回溯算法的本质就是递归遍历所有的情况，最终得到所有的情况。回溯算法的关键，顾名思义，就是做回溯操作。例如，一个女王连续尝试了8个格子，但都不能满足条件。操纵和修改那个操作，比如把那个操作的皇后放在一个新的位置。回溯算法非常适合用递归的方式来实现。递归的本质是函数帧的入栈出栈，即入栈出栈的操作符合回溯的特点。SQL的差异如果你聪明，遇到如何通过MySQL实现八皇后的问题，你肯定会谷歌一下以前的解决方案。不幸的是，我没有找到参考答案。与SQL相关的唯一答案是使用PL/SQL实现。SQL实际上是一种邻域语言(DDL)。它有自己的标准，但是不同的数据库对这套标准有不同的实现。SQL不能通用。PL/SQL是Oracle数据库对SQL标准的实现。它扩展了标准SQL，使其具有过程编程语言的能力。在PL/SQL中，可以轻松实现数组、循环、判断等操作。MySQL也有自己的SQL标准实现。事实上，MySQL实现的SQL比PL/SQL弱得多，它更擅长数据操作而不是过程编程。选择MySQL有几个原因：1、目前还没有找到通过MySQL解决八皇后问题的，也没有参考答案。2、MySQL的SQL语言，过程化支持较弱，有点挑战。3.MySQL是大多数程序员使用的数据库，大家都很熟悉（我安装的BI很容易理解）。因为之前没有人做过，对MySQL进程控制相关的语法也不熟悉，所以一开始也不确定，但是解决问题的过程很有意思。为了描述方便，用SQL来表示MySQL中的SQL，用MySQL来表示数据库。另外，不同版本的MySQL之间的SQL实现也可能不同。本文使用的MySQL版本为8.0.19。你可以通过selectversion();自行查看你的MySQL版本；我用Python解决问题的思路很简单。我使用长度为8的列表来存储皇后的位置。具体来说，列表的下标表示当前皇后所在的行，下标对应的值表示该行上的皇后。皇后所在的列，这样不同皇后所在的行就不会重复，所以只需要判断列和斜边会不会冲突。具体Python代码如下：num=0defis_ok(queen,row):forrinrange(1,row):#第r行和第row行的皇后在同一列，冲突ifqueen[r]==queen[row]:returnFalset=abs(queen[r]-queen[row])#r行和row行皇后在同一条斜杠上，冲突#如果两个皇后的行差和列差相同，则为onthesameslashift==abs(r-row):returnFalsereturnTruedeffind(queen,row):globalnum#从第一列到第八列的每一行都试forcolinrange(1,(8+1)):queen[row]=col#判断是否满足条件ifis_ok(queen,row):ifrow==8:num+=1return#如果没有到达第八行，继续递归find(queen,row+1)#Python列表下标从0开始，为了从1开始，所以这个queen=[0,1,2,3,4,5,6,7,8]find(queen,1)print('resultis',num)去掉注释，代码其实很短。当然还有更好的解决方案，大家可以去看看，我看了Python版的代码，感觉代码太多了。。。有Python版的解决方案，接下来就是把它翻译成SQL的形式，这个过程中遇到的问题还是挺多的。如果没有数组怎么办？MySQL实现的SQL中，没有容器类型的变量，即语言层面不支持数组和字典。我应该怎么办？通过谷歌搜索，我发现大多数人使用字符字符串来模拟数组，字符串之间用逗号分隔，然后通过字符相关的方法查找和更新字符串中的元素。有关详细信息，请参阅参考部分中给出的文章。经过试验，我发现这种方法并不好用。在我的MySQL上，运行的时候会报语法错误。经过简单的思考，我决定用临时表来解决数组。临时表主要用来临时保存一些数据。它的特点是只对创建表的用户可见。当会话结束时，MySQL会自动删除临时表。它的优点是创建和删除表的数据消耗极小，其创建语法为：CREATETEMPORARYTABLEtbl_name(...);即可以在普通的建表语句中加入TEMPORARY关键字，具体语句如下。--如果临时表存在，删除临时表DROPTABLEIFEXISTSqueen；--id模仿列表的下标，location存储列表中的值CREATETEMPORARYTABLEqueen(idINT,locationINT);回头看Python代码，可以发现默认设置了相应的值。queen=[0,1,2,3,4,5,6,7,8]为了模仿这个效果，临时表也要有对应的默认值，因为MySQL中表的下标是从1开始的是的，所以你只需要创建8行。这里我定义了一个存储过程来实现初始化临时表中值的效果。代码如下：--如果存储过程存在，删除PROCEDURE(procedure)DROPPROCEDUREIFEXISTInit_queen;--DefineProcedureCREATEPROCEDUREinit_queen()BEGIN--declarevariableDECLAREiintDEFAULT1;--loopWHILEi<=8DO--insertvalueintotableINSERTINOqueen(id,location)VALUES(i,-1);SETi=i+1;ENDWHILE;END;从评论中应该可以理解上面SQL的逻辑。需要注意的是MySQL的存储过程不是函数。所谓存储过程只是用户定义的一系列SQL语句的集合。当遇到需要复用的SQL语句时，可以定义为存储过程。在执行过程中，MySQL会对其进行相应的优化。存储过程由PROCEDURE关键字定义，可以接受多个参数，也可以返回多个参数，但没有return语句，返回值通过复制到同名参数实现。下面的代码应该明白我表达的意思了。因为后续八皇后算法的求解会涉及到列表元素的增删改查，所以我封装了多个存储过程来实现临时表的增删改查。DROPPROCEDUREIFEXISTSget_queen;--in_id为入参，out_lcation为出参CREATEPROCEDUREget_queen(INin_idINT,OUTout_locationINT)BEGIN--通过id获取对应的location，通过INTO关键字将获取的值赋值给out_location，从而返回查询结果SELECTlocationINTOout_locationFROMqueenWHEREid=in_id;END;--通过id更新对应的locationDROPPROCEDUREIFEXISTSupdate_queen;--多个传入参数CREATEPROCEDUREupdate_queen(INin_idINT,INnew_locationINT)BEGIN--更新值UPDATEqueenSETlocation=new_locationWHEREid=in_id;END;看get_queen方法，它的返回值方法是把要返回的值赋值给out_location参数。使用示例如下：--通过CALL关键字调用存储过程，使用@表示变量，@q1为用于接收结果的变量CALLget_queen(r,@q1);sorry不幸的是，MySQL对临时表的支持也是有限的。当你在实践中使用它们时，会出现“Can'treopentableerror”。这是MySQL特有的问题，即临时表不能被复用。这个问题存在很久了，一直没有解决。MariaDB（MySQL的另一个分支）已经解决了这个问题。一个简单的解决方案是复制临时表。如果表相对较小（通常是临时表），则效果很好。为了避免这种情况，我直接创建了一个普通表，它会被落盘，从而避免了这个问题。更改以下代码DROPTABLEIFEXISTSqueen；CREATETEMPORARYTABLEqueen(idINT,locationINT);至：DROPTABLEIFEXISTSqueen；CREATETABLEqueen(idINT,locationINT);相关讨论请见：参考4如何打印日志？在使用Python的时候，为了方便我们可以通过print方法打印一些内容来判断当前程序执行过程是否正常，那么在SQL中如何实现呢？目前，我在Navicat上编写和执行SQL。查询了一下，Navicat好像无法调试，MySQL也不知道怎么打印，很痛苦。毕竟在写很多SQL的时候，没有日志是很难看出代码中的bug的。为了查看执行过程，我想到了单独创建一个表来记录日志，然后定义一个存储过程将相关信息写入表中，从而达到查看执行日志的目的。--创建日志表DROPTABLEIFEXISTSqueen_log;CREATETABLEqueen_log(idINTUNSIGNEDNOTNULLPRIMARYKEYAUTO_INCREMENT,logVARCHAR(500)NOTNULL);--定义存储过程DROPPROCEDUREIFEXISTSadd_log;CREATEPROCEDUREadd_log(INin_logVARCHAR(500))RTinVAN(INTOlog)BEGIN(INTOlog)BEGIN(INTOlog)BEGIN(INTOLOG)BEGIN(INTOlog)将日志插入表中END;CALLadd_log('alog');定义判断函数在Python实现中，我们定义了is_ok方法来判断当前皇后的走法是否满足条件，这里通过SQL再次实现该方法。在实现之前，我们需要再讨论一下存储过程和函数的区别。在SQL中，存储过程肯定会执行里面的逻辑，不会中途跳出，也就是没有return方法，函数在执行过程中可以使用return方法退出函数，但是function是函数只能返回一个结果，而存储过程可以得到多个返回结果。回过头来看is_ok方法，这个方法只需要返回一个True或False的结果，就可以表明当前皇后是否可以出手。当条件满足时，is_ok方法通过return直接返回。简单思考一下，可以发现is_ok方法更适合使用MySQL函数来实现。--如果函数之前存在，删除DROPFUNCTIONIFEXISTSis_ok；--定义函数，函数名是_ok，函数的输入是in_rowCREATEFUNCTIONis_ok(in_rowINT)--函数是返回值，INT表示返回值的类型，DETERMINISTIC是需要的语法RETURNSINTDETERMINISTIC--函数注释COMMENT'判断当前放置位置是否满足条件'BEGIN--声明变量DECLAREtintDEFAULT-1;DECLAREtintDEFAULT1;WHILE(r<=(in_row-1))DO--queentablestorescolCALLget_queen(r,@q1);CALLget_queen(in_row,@q2);--第r行和第in_rowth行在同一列，冲突IF(@q1=@q2)THEN--函数返回-1RETURN-1;ENDIF;--减列数SETt=ABS(@q1-@q2);--第r行皇后与第rowth行在同一条斜杠上，冲突IF(t=ABS(r-in_row))THENRETURN-2;ENDIF;--加1SETr=r+1;ENDWHILE;RETURN1;END;SQL版is_ok函数的实现更直观，因为我们是通过表来实现队列的，所以不需要传入queen列表，表结构全局可见。递归极限在掌握了MySQL过程控制（IF、WHILE等）、存储过程、函数等的用法后，感觉很快就能用MySQL解决八皇后问题了。很快，我就用函数写了SQL版的find函数。find函数使用了is_ok函数，然后自己回调。代码如下：DROPFUNCTIONIFEXISTSfind;CREATEFUNCTIONfind(in_rowINT)RETURNSINTDETERMINISTICCOMMENT'判断当前放置位置是否满足条件'BEGINDECLAREcolintDEFAULT1;WHILEcol<=8DOCALLget_queen(in_row,@old_location);CALLupdate_queen(in_row,col);--满足条件IF(is_ok(in_row)=1)THENIF(in_row=8)THENSET@num=@num+1;--满足条件跳出递归RETURN0;ENDIF;--第8行还没找到，第一行查找SET@a=find(in_row+1);ENDIF;--恢复递归值CALLupdate_queen(in_row,@old_location);--下一个循环SETcol=col+1;ENDWHILE;RETURN0;END;但是在MySQL中，函数是不能被回调的……会出现“Recursivestoredfunctionsandtriggersarenotallowed”的错误信息。至此，我们就进退两难了：find之所以使用函数是为了满足条件后直接返回，结果发现该函数不支持递归，只有存储过程支持递归调用。如果您使用存储过程，则它没有return关键字。条件满足后，不能通过return返回。只能在所有逻辑执行完毕后自动结束，需要大量的代码改动。最后找到了LEAVE关键字，主要是用来跳出WHILE循环的，类似于Python中的break关键字。使用这个方法，当条件满足的时候，我直接跳出find方法的主循环，从而达到return返回的效果。find的最终代码如下：SET@num:=0;--设置递归查询的层深度上限SETmax_sp_recursion_depth=500;--计算八皇后的可能结果DROPPROCEDUREIFEXISTSfind;CREATEPROCEDURefind(INin_rowINT)BEGINDECLAREcolINTDEFAULT1;--添加日志CALLadd_log('findprocedureisrunning.');--loop,有loop1标识loop1:WHILEcol<=8DOCALLget_queen(in_row,@old_location);CALLupdate_queen(in_row,col);--满足条件SET@res=is_ok(in_row);--添加日志CALLadd_log(CONCAT('is_okrunning,in_row:',in_row,'col:',col,'res:',@res));IF(@res=1)THENIF(in_row=8)THENSET@num=@num+1;CALLadd_log(CONCAT('numis:',@num));--满足条件跳出递归LEAVEloop1;ENDIF;--第8行前继续递归CALLfind(in_row+1);--恢复递归值CALLupdate_queen(in_row,@old_location);ENDIF;--下一个循环SETcol=col+1;--循环处，有一个loop1标记ENDWHILEloop1;END;另外需要注意的是MySQL对递归的深度有严格的限制，所以我们需要设置max_sp_recursion_depth。--设置递归查询层数上限SETmax_sp_recursion_depth=500;实施过程中遇到的问题及解决办法。不允许从函数返回结果集错误此错误指出：不允许从函数返回结果集。即在你定义的函数中，不能使用SELECT打印数据，MySQL会认为方法中打印数据是返回相关结果集。不允许递归存储函数和触发器MySQL方法不支持递归调用，但存储过程可以。Recursivelimit0error需要修改max_sp_recursion_depth。这种修改涉及全局和会话级别的修改。全局修改需要超级权限：setglobalmax_sp_recursion_depth=2。对于session级别的修改，只对当前连接有效，不需要global。threadstackoverrunerror错误原因：thread_stack太小，默认128K。可以通过以下命令查看mysql>showvariableslike'%thread%';+----------------------------------------+----------------------------+|Variable_name|Value|+------------------------------------------+------------------------+|create_admin_listener_thread|OFF||innodb_parallel_read_threads|4||thread_handling|每连接一个线程||thread_stack|286720|+----------------------------------------+------------------------+18rowsinset(0.02sec)删除一些不相关的内容，缩小显示，看到thread_stack为286720Bytes或280KB。最终结果将上面的代码整理在一起，就获得了最终的SQL代码，完整代码如下：DROPTABLEIFEXISTSqueen;CREATETABLEqueen(idINT,locationINT);DROPTABLEIFEXISTSqueen_log;CREATETABLEqueen_log(idINTUNSIGNEDNOTNULLPRIMARYKEYAUTO_INCREMENT,logVARCHAR(500)NOTNULL);DROPPROCEDUREIFEXISTSadd_log;CREATEPROCEDUREadd_log(INin_logVARCHAR(500))BEGININSERTINTOqueen_log(log)VALUES(in_log);END;DROPPROCEDUREIFEXISTSinit_queen;CREATEPROCEDUREinit_queen()BEGINDECLAREiintDEFAULT1;WHILEi<=8DOINSERTINTOqueen(id,location)VALUES(i,i);SETi=i+1;ENDWHILE;END;DROPPROCEDUREIFEXISTSget_queen;CREATEPROCEDUREget_queen(INin_idINT,OUTout_locationINT)BEGINSELECTlocationINTOout_locationFROMqueenWHEREid=in_id;END;DROPPROCEDUREIFEXISTSupdate_queen;CREATEPROCEDUREupdate_queen(INin_idINT,INnew_locationINT)BEGINUPDATEqueenSETlocation=new_locationWHEREid=in_id;END;DROPFUNCTIONIFEXISTSis_ok;CREATEFUNCTIONis_ok(in_rowINT)RETURNSINTDETERMINISTICCOMMENT'判断当前落子位置是否满足条件'BEGINDECLAREtintDEFAULT-1;DECLARErintDEFAULT1;WHILE(r<=(in_row-1))DOCALLget_queen(r,@q1);CALLget_queen(in_row,@q2);IF(@q1=@q2)THENRETURN-1;ENDIF;SETt=ABS(@q1-@q2);IF(t=ABS(r-in_row))THENRETURN-2;ENDIF;SETr=r+1;ENDWHILE;RETURN1;END;SET@num:=0;SETmax_sp_recursion_depth=500;--计算八皇后的可能结果DROPPROCEDUREIFEXISTSfind;CREATEPROCEDURefind(INin_rowINT)BEGINDECLAREcolINTDEFAULT1;CALLadd_log('findprocedureisrunning.');loop1:WHILEcol<=8DOCALLget_queen(in_row,@old_location);CALLupdate_queen(in_row,col);SET@res=is_ok(in_row);CALLadd_log(CONCAT('is_okrunning,in_row:',in_row,'col:',col,'res:',@res));IF(@res=1)THENIF(in_row=8)THENSET@num=@num+1;CALLadd_log(CONCAT('numis:',@num));LEAVEloop1;ENDIF;CALLfind(in_row+1);CALLupdate_queen(in_row,@old_location);ENDIF;SETcol=col+1;ENDWHILEloop1;END;CALLinit_queen();CALLfind(1);SELECT@num;如果是难理解，在回文中解释代码的时候可以看到注释的最终效果如下：执行日志：查询计算过程：顺便说一句，这个程序跑了大概2.9分钟，很慢，可能是因为很多INSERT操作涉及递归过程。从运行速度也可以判断出这个程序没用，没错，没用，但我更乐意折腾，这就够了？？。广告算法的内容已经整理好了，记得看一看，下篇文章再见。
