recursion - sqlite:递归查询中的排序方式如何工作？

Question

https://www.sqlite.org/lang_with.html#withorderby显示了一个示例，该示例说明了递归级别上的排序如何将树的深度优先顺序更改为宽度优先顺序。理查德·希普（Richard Hipp）
http://sqlite.1065341.n5.nabble.com/why-does-the-recursive-example-sort-alphabetically-td80404.html
表示递归顺序中的按顺序具有特殊含义：确定递归的顺序。

我在递归级别以外的其他字段上进行了排序，并且……我无法预测结果。 :(有人可以解释一下它是如何工作的吗？

基本上，让我们看一个与sqlite文档中的Alice / Bob / Cindy类似的示例（上面的第一个链接），但名称混在一起（不是按字母顺序排列在树中，而是以随机顺序插入），然后使用递归部分中的“按名称排序”（而不是递归级别）。

    CREATE TABLE child_parent(
    name TEXT PRIMARY KEY,
    parent TEXT
    );
    INSERT INTO child_parent VALUES('KKK','HHH');
    INSERT INTO child_parent VALUES('HHH','LLL');
    INSERT INTO child_parent VALUES('MMM','CCC');
    INSERT INTO child_parent VALUES('CCC','QQQ');
    INSERT INTO child_parent VALUES('QQQ','LLL');
    INSERT INTO child_parent VALUES('TTT','QQQ');
    INSERT INTO child_parent VALUES('AAA','HHH');
    INSERT INTO child_parent VALUES('EEE','TTT');
    INSERT INTO child_parent VALUES('UUU','CCC');
    INSERT INTO child_parent VALUES('FFF','MMM');
    INSERT INTO child_parent VALUES('LLL',NULL);

child_parent结构为：

    -- LLL -> QQQ
    --              -> TTT
    --                      -> EEE
    --              -> CCC
    --                      -> UUU
    --                      -> MMM
    --                              -> FFF
    --       -> HHH
    --              -> AAA
    --              -> KKK

首先选择-使用“ ORDER BY new_name asc”

    WITH RECURSIVE
    tree(name,level) AS (
        SELECT cp.name, 0
            FROM child_parent cp
            WHERE cp.parent IS NULL
        UNION ALL
        SELECT ch.name AS new_name, tree.level+1 AS new_lvl
            FROM child_parent ch
                 INNER JOIN tree ON ch.parent=tree.name
        ORDER BY new_name ASC
    )
    SELECT *, substr('...................',1,level*3) || name FROM tree;
    -- name        level       substr('...................',1,level*3) || name
    -- ----------  ----------  -----------------------------------------------
    -- LLL         0           LLL                                            
    -- HHH         1           ...HHH                                         
    -- AAA         2           ......AAA                                      
    -- KKK         2           ......KKK                                      
    -- QQQ         1           ...QQQ                                         
    -- CCC         2           ......CCC                                      
    -- MMM         3           .........MMM                                   
    -- FFF         4           ............FFF                                
    -- TTT         2           ......TTT                                      
    -- EEE         3           .........EEE                                   
    -- UUU         3           .........UUU                                   

首先选择-使用“ ORDER BY new_name desc”

    WITH RECURSIVE
    tree(name,level) AS (
        SELECT cp.name, 0
            FROM child_parent cp
            WHERE cp.parent IS NULL
        UNION ALL
        SELECT ch.name AS new_name, tree.level+1 AS new_lvl
            FROM child_parent ch
                 INNER JOIN tree ON ch.parent=tree.name
        ORDER BY new_name DESC
    )
    SELECT *, substr('...................',1,level*3) || name FROM tree;
    -- name        level       substr('...................',1,level*3) || name
    -- ----------  ----------  -----------------------------------------------
    -- LLL         0           LLL                                            
    -- QQQ         1           ...QQQ                                         
    -- TTT         2           ......TTT                                      
    -- HHH         1           ...HHH                                         
    -- KKK         2           ......KKK                                      
    -- EEE         3           .........EEE                                   
    -- CCC         2           ......CCC                                      
    -- UUU         3           .........UUU                                   
    -- MMM         3           .........MMM                                   
    -- FFF         4           ............FFF                                
    -- AAA         2           ......AAA                                      

基本上，问题是：如何考虑db行为以预测最后两个查询的结果将如上所述。您能否逐步描述发生的情况？在每个递归级别？

SQLite 3.15.2.0.37

Answer 1

documentation说：


计算递归表内容的基本算法如下：


运行初始选择并将结果添加到队列中。
当队列不为空时：
一个。从队列中提取一行。
b。将那一行插入递归表
C。假设刚提取的单行是递归表中的唯一行，然后运行递归选择，将所有结果添加到队列中。


[…]
如果存在ORDER BY子句，它将在步骤2a中确定从队列中提取行的顺序。


当将ORDER BY应用于树级列时，结果是广度优先或深度优先的搜索。 （使用ASC，首先提取“较旧”的行；使用DESC，首先提取最低级别的最新行。）

但是，当将其应用于其他列时，该顺序将不再与树的结构相关。