[MDEV-14015] Sudoku solver with recursive CTE seems to never finish (see MySQL Bug #88006) Created: 2017-10-06  Updated: 2017-10-12  Resolved: 2017-10-12

Status: Closed
Project: MariaDB Server
Component/s: Optimizer - CTE
Affects Version/s: 10.2.9
Fix Version/s: N/A

Type: Bug Priority: Major
Reporter: Valerii Kravchuk Assignee: Unassigned
Resolution: Not a Bug Votes: 0
Labels: upstream


 Description   

Looks like MariaDB 10.2.x is also affected by upstream https://bugs.mysql.com/bug.php?id=88006. When started with all default settings I do not see RSS growing for mysqld process (it's stabilized after some time):

top - 09:06:45 up 2 days, 14:11,  4 users,  load average: 1,01, 1,19, 1,41
Tasks: 223 total,   1 running, 222 sleeping,   0 stopped,   0 zombie
%Cpu(s): 49,8 us,  1,5 sy,  0,0 ni, 47,5 id,  1,2 wa,  0,0 hi,  0,0 si,  0,0 st
KiB Mem:   3861436 total,  3530408 used,   331028 free,   235588 buffers
KiB Swap:  4001788 total,   105732 used,  3896056 free.  1961032 cached Mem
 
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
17426 openxs    20   0 1769628 257460  14932 S  98,7  6,7  49:55.48 mysqld
...

But after many minutes of waiting I still do not get the result:

openxs@ao756:~/dbs/maria10.2$ bin/mysqld_safe --no-defaults --port=3308 &       [1] 17355
openxs@ao756:~/dbs/maria10.2$ 171006 08:12:57 mysqld_safe Logging to '/home/openxs/dbs/maria10.2/data/ao756.err'.
171006 08:12:57 mysqld_safe Starting mysqld daemon with databases from /home/openxs/dbs/maria10.2/data
 
openxs@ao756:~/dbs/maria10.2$ bin/mysql -uroot test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A
 
Welcome to the MariaDB monitor.  Commands end with ; or \g.
Your MariaDB connection id is 8
Server version: 10.2.9-MariaDB Source distribution
 
Copyright (c) 2000, 2017, Oracle, MariaDB Corporation Ab and others.
 
Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.
 
MariaDB [test]> WITH RECURSIVE
    ->   input(sud) AS (
    ->     SELECT '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
    ->   ),
    ->   digits(z, lp) AS (
    ->     SELECT '1', 1
    ->     UNION ALL SELECT
    ->     CAST(lp+1 AS CHAR), lp+1 FROM digits WHERE lp<9
    ->   ),
    ->   x(s, ind) AS (
    ->     SELECT sud, instr(sud, '.') FROM input
    ->     UNION ALL
    ->     SELECT
    ->       concat(substr(s, 1, ind-1) , z , substr(s, ind+1)),
    ->       instr( concat(substr(s, 1, ind-1) ,z ,substr(s, ind+1)), '.' )
    ->      FROM x, digits AS z
    ->     WHERE ind>0
    ->       AND NOT EXISTS (
    ->             SELECT 1
    ->               FROM digits AS lp
    ->              WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
    ->                 OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)
    ->                 OR z.z = substr(s, (((ind-1)/3) % 3) * 3
    ->                         + ((ind-1)/27) * 27 + lp
    ->                         + ((lp-1) / 3) * 6, 1)
    ->          )
    ->   )
    -> SELECT s FROM x WHERE ind=0;



 Comments   
Comment by Valerii Kravchuk [ 2017-10-12 ]

With the same fix as in upstream bug (replacing / with DIV) it works fast ,as expected:

MariaDB [test]> WITH RECURSIVE   input(sud) AS (     SELECT '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'   ),   digits(z, lp) AS (     SELECT '1', 1     UNION ALL SELECT     CAST(lp+1 AS CHAR), lp+1 FROM digits WHERE lp<9   ),   x(s, ind) AS (     SELECT sud, instr(sud, '.') FROM input     UNION ALL     SELECT       concat(substr(s, 1, ind-1) , z , substr(s, ind+1)),       instr( concat(substr(s, 1, ind-1) ,z ,substr(s, ind+1)), '.' )      FROM x, digits AS z     WHERE ind>0       AND NOT EXISTS (             SELECT 1               FROM digits AS lp              WHERE z.z = substr(s, ((ind-1) DIV 9)*9 + lp, 1)                 OR z.z = substr(s, ((ind-1)%9) + (lp-1)*9 + 1, 1)                 OR z.z = substr(s, (((ind-1) DIV 3) % 3) * 3                         + ((ind-1) DIV 27) * 27 + lp                         + ((lp-1) DIV 3) * 6, 1)          )   ) SELECT s FROM x WHERE ind=0;
+-----------------------------------------------------------------------------------+
| s                                                                                 |
+-----------------------------------------------------------------------------------+
| 534678912672195348198342567859761423426853791713924856961537284287419635345286179 |
+-----------------------------------------------------------------------------------+
1 row in set (0.25 sec)
 
MariaDB [test]> select version();
+-----------------+
| version()       |
+-----------------+
| 10.2.10-MariaDB |
+-----------------+
1 row in set (0.00 sec)

So, not a bug.

Generated at Thu Feb 08 08:10:15 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.