title: Select from a table that uses materialized path to encode a tree, ordered by depth-first (no recursive/ltree)
body: <p>I have a table in a relational database, in which I encode a tree using the technique known as <a href="http://en.wikipedia.org/wiki/Materialized_path" rel="nofollow noreferrer">Materialized path</a> (also known as Lineage column). That is, for each node in my tree I have a row in the table, and for each row I have a string column named <code>ancestry</code> where I store the path from the root node to the node represented by this row.</p>
  
  <p>Is it possible, and if yes - how, to <strong>select the rows in the table orderd by preorder</strong>, that is they should appear in the result set in the order that would result by visiting the tree <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">depth-first</a>. I use MySQL - so <strong>no recursive queries and no ltree extension</strong>.</p>
  
  <p>For example, a tree, it's table, and selected ordered by preorder:</p>
  
  <pre><code> 1        SELECT * FROM nodes   SELECT * FROM nodes ORDER BY ?depth_first_visit_order?
  | \       id | ancestry         id | ancestry
  2   3     -------------         -------------
  |  | \    1  | NULL             1  | NULL           NOTE: I don't care about the
  4  5  6   2  | 1                2  | 1                    order of siblings!
     |      3  | 1                4  | 1/2
     7      4  | 1/2              3  | 1
            5  | 1/3              5  | 1/3
            6  | 1/3              7  | 1/3/5
            7  | 1/3/5            6  | 1/3
  </code></pre>
  
  <p>Note: I am interested explicitly in doing this over a materialized path encoding!<br>
  Related: <a href="https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database">What are the options for storing hierarchical data in a relational database?</a></p>