SQL Pattern to get "root/ start" of uneven hierarchy dataset

Question

I feel this is a common problem and I've seen it in some SQL challenges even but for the life of me, cannot think clearly about a solution.

Say you have an uneven hierarchy. Elements that belong to other elements but you don't know the top.

Let's say it's a Company Org Chart to keep it simple (really it's task dependencies but eh).

So there's a table. Employee Name and Boss Name.

Employee name: Bob .... Boss Name: Dora
Employee name Dora .... Boss Name: Kim

And on and on. In my case there is an added piece of information. One person only reports to one person ever. One-to-one relationship.

There are N elements at the top of the chain that have Name: Whoever Boss: Null.

So I was doing something as follows:

select employee_name, boss_name
from boss_table b1
left join boss_table b2 on b1.boss_name = b2.employee_name
left join boss_table b3 on b2.boss_name = b3.employee_name

And on and on to attempt to find the 'Root Boss' or 'Top Boss' of each employee. However some of these nested elements are VERY deep -- I don't want to do 20 joins ... or at least type them out -- I feel a recursive function is the obvious answer, but can't figure it out -- thoughts?

Answer 1

What you're looking for is called a Recursive CTE. This is one of the most common constructs for implementing recursion in a database system. A recursive CTE is a temporary named result set that is self-referencing to produce the results, akin to how a traditional recursive function works.

Recursive CTEs and Hierarchical Data

Recursive CTEs enable you to process hierarchical data, such as a parts explosion (component, sub-components) or a management hierarchy (manager, employees).

Org Chart example from the above docs:

WITH RECURSIVE managers
  (indent, employee_ID, manager_ID, employee_title)
 AS
   (

     SELECT '' AS indent, employee_ID, manager_ID, title AS employee_title
       FROM employees
       WHERE title = 'President'

    UNION ALL

   SELECT indent || '--- ',
       employees.employee_ID, employees.manager_ID, employees.title
     FROM employees JOIN managers
       ON employees.manager_ID = managers.employee_ID
 )

SELECT indent || employee_title AS Title, employee_ID, manager_ID
  FROM managers
;

Here's some other examples of implementing recursive CTEs in Snowflake.