sqlite recursive ancestor query

Question

I'm trying to figure out how to use a recursive query with a hierarchical table. I need to get the ancestors of a given record, and the records should be sorted in order of their level in the hierarchy. That is, the first record should be the top node, the next should be a child, then its child, down to the record being queried.

Consider a table called "food" with the following data. It's a simple hierarchy, with every record except the top record having a parent record.

id         | parent
-----------+---------
top        |
fruit      | top
red        | fruit
cherry     | red
apple      | red
orange     | fruit
clementine | orange
mandarin   | orange

Trying to understand the various web pages on the topic, I cobbled together the following query which gives all the ancestors for the "mandarin" record, including the mandarin record itself.

with recursive
    child_record(id) as (
        values('mandarin')

        union

        select parent
        from food, child_record
        where food.id = child_record.id
    )
select id from food
    where food.id in child_record;

However, that query returns the record in what appears to me to be an arbitrary order:

fruit
mandarin
orange
top

I'd like the records to be sorted with the top record first, down the levels to the mandarin record.

top
fruit
orange
mandarin

How do I structure that query to give the records in the order I want?

Answer 1

I think I've got it? I'm hesitant to say I do because I still don't quite understand the syntax, but the following query produces the results I want.

with recursive
    child_record(level, id) as (
        values(0, 'mandarin')

        union

        select child_record.level+1, food.parent
        from food, child_record
        where food.id = child_record.id
    )
select child_record.level, food.id
from  food, child_record
where food.id = child_record.id
order by child_record.level desc;

Answer 2

By combining this answer and yours, I found two likely speedups (that I haven't yet measured):

1. A regular join instead of a cross-join (the from food, child_record part of your query).
2. union all instead of union - the results are already deduplicated.

In addition, I think this query naturally orders its results, but I re-added the level field to ensure it.

with recursive ancestor(id, parent, level) as (
   select id, parent, 0
   from food
   where id = 'mandarin' -- this is the starting point you want in your recursion
   union all
   select f.id, f.parent, a.level + 1
   from food f
     join ancestor a on a.parent = f.id  -- this is the recursion
) 
select id
from ancestor
order by level;

┌──────────┐
│    id    │
├──────────┤
│ mandarin │
│ orange   │
│ fruit    │
│ top      │
└──────────┘

Answer 3

I suggest ordering by rowid:

with recursive
    child_record(id) as (
        select 'mandarin'

        union

        select parent
        from food, child_record
        where food.id = child_record.id
    )
select id from food
    where food.id in child_record 
    order by food.rowid;