Sudoku Recursive Common Table Expression Solver

Colin, from Percona, wrote a nice post demonstrating a funny use of common table expressions: solving a Sudoku Puzzle. Ok, that's not the type of problem which matters a lot to database users... but it still feels good when he mentions that MySQL's implementation (which I wrote), is the fastest of all three tested DBMSs 😊.

Commentaires

  1. Benoît St-Jean27 novembre 2017 à 11:14

    Dans le même ordre d'idée, j'ai autrefois écrit un article en 3 parties sur comment résoudre des sudokus en SQL. L'article est assez long, détaillé et, surtout, en français pour ceux que ça intéresse!!

    Partie 1 (https://endormitoire.wordpress.com/2012/01/07/comment-presser-un-citron-premiere-partie/),
    Partie 2 (https://endormitoire.wordpress.com/2012/01/08/comment-presser-un-citron-deuxieme-partie/)
    Partie 3 (https://endormitoire.wordpress.com/2013/05/27/comment-presser-un-citron-troisieme-partie/).

    Comment presser un citron? Vous le saurez en lisant l'article!

    RépondreSupprimer

Enregistrer un commentaire

Posts les plus consultés de ce blog

WITH RECURSIVE and MySQL

[2017 update: MySQL 8.0.1 now features SQL-standard CTE syntax; more information is here ; the entry below, from 2013, shows how to work around the absence of CTEs in older MySQL versions.] If you have been using certain DBMSs, or reading recent versions of the SQL standard, you are probably aware of the so-called "WITH clause" of SQL. Some call it Subquery Factoring . Others call it  Common Table Expression (CTE). In its simplest form, this feature is a kind of "boosted derived table". Assume that a table T1 has three columns: CREATE TABLE T1( YEAR INT, # 2000, 2001, 2002 ... MONTH INT, # January, February, ... SALES INT # how much we sold on that month of that year ); Now I want to know the sales trend (increase/decrease), year after year: SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND FROM (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D1, (SELECT YEAR, SUM(SALES) AS S FROM T1 GR
Lire la suite

Faster subqueries with materialization

In a previous post , I analyzed how a query of the famous DBT3 benchmark was optimized by MySQL. It was this query, named "Q16" in the DBT3 jargon: select p_brand, p_type, p_size, count(distinct ps_suppkey) as supplier_cnt from partsupp, part where p_partkey = ps_partkey and p_brand <> 'Brand#23' and p_type not like 'LARGE PLATED%' and p_size in (43, 1, 25, 5, 35, 12, 42, 40) and ps_suppkey not in ( select s_suppkey from supplier where s_comment like '%Customer%Complaints%' ) group by p_brand, p_type, p_size order by supplier_cnt desc, p_brand, p_type, p_size; Here is a brief recap of conclusions I had drawn: for this query, MySQL tranforms the IN condition to EXISTS and then evaluates it with the "unique_subquery" technique, which does an index lookup into the subquery's table. IN is evaluated 120,000 times (once per combined row of the outer tables). The total execution time of query Q16
Lire la suite