How find oldest "ancestor" in MySQL where each row has a parent or null?

Question

I have a set of data like this:

ID      NAME        PARENT
----    ------      -------
1       Obj #1      NULL
2       Obj #2      1
3       Obj #3      4
4       Obj #4      2
5       Obj #5      3
6       Obj #6      NULL
7       Obj #7      6

So if I wanted to get them with their oldest ancestor, I'd get results like this:

ID      NAME        OLDEST
----    ------      -------
1       Obj #1      NULL
2       Obj #2      1
3       Obj #3      1
4       Obj #4      1
5       Obj #5      1
6       Obj #6      NULL
7       Obj #7      6

How would I make a query to do this?

Answer 1

Because of lack of time, I'll just present you with one solution (which isn't the best one, but works with the logic of using repeated self-joins and only if you know the upper limit of your hierarchy tree).

Here's a working SQL Fiddle.

Test data generation (like yours, without "name" column):

create table tbl(id int, parent int);
insert into tbl values (1,null),(2,1),(3,4),(4,2),(5,3),(6,null),(7,6);

Query to find the oldest ancestor given a depth of 5 in hierarchy tree:

select
  t1.id, coalesce(t5.id, t4.id, t3.id, t2.id) as oldest
from tbl t1
left join tbl t2 on t1.parent = t2.id
left join tbl t3 on t2.parent = t3.id
left join tbl t4 on t3.parent = t4.id
left join tbl t5 on t4.parent = t5.id
order by 1;

Answer 2

Some comments recommend the "nested set" model, which was popularized in Joe Celko's SQL books. But I find that data model is hard to maintain, and it's complicated to modify the data.

I prefer a design I call "closure table" which I described in this well-received Stack Overflow answer: What is the most efficient/elegant way to parse a flat table into a tree?

Your query would look like this:

SELECT c.ID, c.NAME, a.ID AS OLDEST
FROM MyTable AS t
JOIN ClosureTable AS c ON t.ID = c.descendant 
JOIN MyTable AS a ON a.ID = c.ancestor
WHERE a.PARENT IS NULL;

I also cover this model (and other solutions) in my presentation Models for Hierarchical Data.

Here's the video recording of my delivering this presentation: Models for Hierarchical Data.

I also wrote a chapter about hierarchical data in my book, SQL Antipatterns Volume 1: Avoiding the Pitfalls of Database Programming.

---

If you need a query that works with your data as you currently store it, see Quassnoi's clever solution here: https://stackoverflow.com/a/8111762/20860

But admittedly, it's not a stable solution because it relies on undocumented behavior of MySQL. I'd stay away from it.

---

If you can't change the code or the table structure, and you need it today, you're going to have to go with the answer from Kamil G. even though it is limited to a fixed level of depth of the hierarchy. There's no other solution, sorry.

Answer 3

I usually re-design this in MySQL so that table looks like this:

id      name
10      Obj#1
1010    Obj#2 -- parent = 10
101020  Obj#6 -- parent = 1010 -- grandparent = 10 ... etc

And I have a lazy SQL for your current design: (6 levels of nested, you can add more if you have deeper nesting)

SELECT a.id, a.NAME,
  ifnull(p6.PARENT, ifnull(p5.PARENT, ifnull(p4.PARENT, ifnull(p3.PARENT, ifnull(p2.PARENT, ifnull(p.PARENT, p.id)))))) AS PARENT
FROM 0_a2 AS a
LEFT JOIN 0_a2 AS p  ON a.PARENT  = p.id
LEFT JOIN 0_a2 AS p2 ON p.PARENT  = p2.id
LEFT JOIN 0_a2 AS p3 ON p2.PARENT = p3.id
LEFT JOIN 0_a2 AS p4 ON p3.PARENT = p4.id
LEFT JOIN 0_a2 AS p5 ON p4.PARENT = p5.id
LEFT JOIN 0_a2 AS p6 ON p5.PARENT = p6.id
ORDER BY a.id