Re: [sqlite] why does the recursive example sort alphabetically

[RSmith]

On 2015/02/04 15:45, Mark Summerfield wrote:

Hi,

In the documentation on page http://www.sqlite.org/lang_with.html
there is an example of a recursive query if you scroll down to the heading
"Controlling Depth-First Versus Breadth-First Search Of a Tree Using ORDER
BY".

The second example under that heading shows how to get a depth-first
search. Here's the query:

WITH RECURSIVE
   under_alice(name,level) AS (
 VALUES('Alice',0)
 UNION ALL
 SELECT org.name, under_alice.level+1
   FROM org JOIN under_alice ON org.boss=under_alice.name
  ORDER BY 2 *DESC*
   )
SELECT substr('..',1,level*3) || name FROM under_alice;


It turns out that this query not only provides a correctly indented output
of the tree, but it also sorts every branch alphabetically by name.

What I don't understand is *why* it sorts alphabetically by name.

I would have expected to need to change the query to have ORDER BY 2 DESC,
org.name
for it to work, but it works anyway.


It doesn't actually "work anyway", the result is not ordered at all - it just happens to be the order in which the rows are fetched 
which only happens to be in that order because of the default sort direction of the primary key (which is ascending).  If you do 
PRAGMA reverse_unordered_selects=1;  and then run the query again, it should pop out the opposite order.


(I haven't actually tested this, but trust it to the point of not feeling the need to test it, hoever, let us know if you test it 
and get a different result).




___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] why does the recursive example sort alphabetically

[Richard Hipp]

On 2/4/15, Mark Summerfield  wrote:
> Hi,
>
> In the documentation on page http://www.sqlite.org/lang_with.html
> there is an example of a recursive query if you scroll down to the heading
> "Controlling Depth-First Versus Breadth-First Search Of a Tree Using ORDER
> BY".
>
> The second example under that heading shows how to get a depth-first
> search. Here's the query:
>
> WITH RECURSIVE
>   under_alice(name,level) AS (
> VALUES('Alice',0)
> UNION ALL
> SELECT org.name, under_alice.level+1
>   FROM org JOIN under_alice ON org.boss=under_alice.name
>  ORDER BY 2 *DESC*
>   )
> SELECT substr('..',1,level*3) || name FROM under_alice;
>
>
> It turns out that this query not only provides a correctly indented output
> of the tree, but it also sorts every branch alphabetically by name.
>
> What I don't understand is *why* it sorts alphabetically by name.e


The ORDER BY clause within the recursive CTE determines the order of
recursion (depth-first or breadth-first), not the order of final
output.

The final output order, in this case, is the same as the PRIMARY KEY
order on the table.  (SQLite does not guarantee this - it just happens
to fall out because of the particular algorithm that SQLite chose in
this particular case.  The result might change at any time.)

If you change the table schema to say:

 name TEXT PRIMARY KEY DESC,

(Adding "DESC" after PRIMARY KEY) then you will observe that the
output is in the opposite order.

Emphasis:  There is ORDER BY clause on the final SELECT statement, and
so SQLite is free to output the results in any order it wants.  The
fact that is happens to come out in some particular order in the
current implementation is just a happy accident and is not something
you should rely upon.

>
> I would have expected to need to change the query to have ORDER BY 2 DESC,
> org.name
> for it to work, but it works anyway.
>
> Thanks!
>


-- 
D. Richard Hipp
d...@sqlite.org
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] why does the recursive example sort alphabetically

[Mark Summerfield]

Hi,

In the documentation on page http://www.sqlite.org/lang_with.html
there is an example of a recursive query if you scroll down to the heading
"Controlling Depth-First Versus Breadth-First Search Of a Tree Using ORDER 
BY".

The second example under that heading shows how to get a depth-first 
search. Here's the query:

WITH RECURSIVE
  under_alice(name,level) AS (
VALUES('Alice',0)
UNION ALL
SELECT org.name, under_alice.level+1
  FROM org JOIN under_alice ON org.boss=under_alice.name
 ORDER BY 2 *DESC*
  )
SELECT substr('..',1,level*3) || name FROM under_alice;


It turns out that this query not only provides a correctly indented output 
of the tree, but it also sorts every branch alphabetically by name.

What I don't understand is *why* it sorts alphabetically by name.

I would have expected to need to change the query to have ORDER BY 2 DESC, 
org.name
for it to work, but it works anyway.

Thanks!
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users