What is the Most Efficient/Elegant Way to Parse a Flat Table into a Tree?

Sometimes you may need to hierarchically organize data in a relational database. The data will be stored in a flat table where each row has its parent as a reference. There are some methods by which you can query the flat table into a tree structure, like Recursive CTE, Nested Set model, and loops with temporary. Querying data into a tree structure is quite challenging, but you can handle the recursion with better performance by learning these techniques. In this blog, you will learn in detail the most efficient way to parse a flat table into a tree. 

Table of Contents: 

• Why Do We Need To Parse a Flat Table into a Tree?
• Method to Efficiently Parse a Flat Table into a Tree in SQL
  • Using Recursive Common Table Expression in MySQL
• Alternative Methods to Parse a Flat Table into a Tree
  • Without CTE Using Loops and Temporary Tables in SQL Server
  • Nested Set Model in SQL Server
  • Using Materialized Path (Path Enumeration) in SQL Server
• Pros and Cons of the Various Methods
• Real-World Examples
• Conclusion

Why Do We Need To Parse a Flat Table into a Tree?

We need to parse a flat table into a tree because it is necessary to represent a relationship in a tree structure or like categories, menus in a hierarchical format in SQL. This will be really helpful to find the structure of the data, and retrieving data will be easier. It is useful when we need to understand the parent-child relationship. 

Method to Efficiently Parse a Flat Table into a Tree in SQL

Various techniques can be used to parse a flat table into a tree by Recursive Common Table Expression (CTE), which is very efficient and one of the best ways to parse a tree in a MySQL Server. 

Using Recursive Common Table Expression in MySQL

The Recursive CTE in MySQL is best suited for converting flat table values into a parse tree. As a recursive CTE has its built-in recursion, it will be useful to avoid complex loops. It is very efficient and can handle a large hierarchy. 

Syntax:

WITH RECURSIVE cte_name AS (
    -- Anchor (Base) Query: Select root nodes (entries with no parent)
    SELECT column1, column2, ..., parent_column, 1 AS level
    FROM table_name
    WHERE parent_column IS NULL  
    UNION ALL  
    -- To Join CTE with the main table to get child nodes
    SELECT t.column1, t.column2, ..., t.parent_column, cte.level + 1
    FROM table_name t
    JOIN cte_name cte ON t.parent_column = cte.column1
)
SELECT * FROM cte_name;

Example:

-- Using Recursive CTE 
CREATE TABLE categories (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL,
    FOREIGN KEY (parent_id) REFERENCES categories(id)
);
INSERT INTO categories (id, name, parent_id) VALUES
(1, 'Electronics', NULL),
(2, 'Laptops', 1),
(3, 'Phones', 1),
(4, 'Gaming Laptops', 2),
(5, 'Accessories', NULL),
(6, 'Chargers', 5);
WITH RECURSIVE category_tree AS (
    -- Base case: Root nodes (parent_id IS NULL)
    SELECT id, name, parent_id, 1 AS level, CAST(id AS CHAR(500)) AS path
    FROM categories
    WHERE parent_id IS NULL
    UNION ALL
    -- To Join with the table to find child nodes
    SELECT c.id, c.name, c.parent_id, ct.level + 1, CONCAT(ct.path, '->', c.id)
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT * FROM category_tree ORDER BY path;

Output:

Explanation: Here, “c.id, c.name, c.parent_id, ct.level + 1, CONCAT(ct.path, ‘->’, c.id)” this query will parse the tree from the flat table. The ORDER BY path command will give the structured view. 

Alternative Methods to Parse a Flat Table into a Tree

Some alternative methods can be used other than Recursive CTE such as Using loops and the nested set model, etc. 

Without CTE Using Loops and Temporary Tables in SQL Server

Most of the databases allow the user to do procedural logic using stored procedures or loops. It is very efficient while using a SQL server. 

Syntax:

-- Create a Temporary Table for the Tree Structure
IF OBJECT_ID('tempdb..#Tree') IS NOT NULL
    DROP TABLE #Tree;
CREATE TABLE #Tree (
    id INT,
    name VARCHAR(100),
    parent_id INT,
    level INT,
    path NVARCHAR(500)  -- Stores hierarchy path
);
-- Insert Root Nodes 
INSERT INTO #Tree (id, name, parent_id, level, path)
SELECT id, name, parent_id, 1, CAST(id AS NVARCHAR(500))
FROM table_name
WHERE parent_id IS NULL;
-- Step 3: Initialize Loop Variables
DECLARE @level INT = 1;
-- Loop to Insert Child Nodes Until No More Are Found
WHILE @@ROWCOUNT > 0
BEGIN
    SET @level = @level + 1;
    INSERT INTO #Tree (id, name, parent_id, level, path)
    SELECT t.id, t.name, t.parent_id, @level, CONCAT(p.path, '->', t.id)
    FROM table_name t
    INNER JOIN #Tree p ON t.parent_id = p.id
    WHERE p.level = @level - 1;
END;
-- Retrieve the Hierarchical Tree
SELECT * FROM #Tree ORDER BY path;
-- Drop Temporary Table
DROP TABLE #Tree;

Example: 

-- Create Categories Table
IF OBJECT_ID('categories', 'U') IS NOT NULL
    DROP TABLE categories;
CREATE TABLE categories (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL
);
-- Insert Sample Data
INSERT INTO categories (id, name, parent_id) VALUES
(1, 'Electronics', NULL),
(2, 'Laptops', 1),
(3, 'Phones', 1),
(4, 'Gaming Laptops', 2),
(5, 'Accessories', NULL),
(6, 'Chargers', 5);
-- Create a Temporary Table to Store the Hierarchy
IF OBJECT_ID('tempdb..#Tree') IS NOT NULL
    DROP TABLE #Tree;
CREATE TABLE #Tree (
    id INT,
    name VARCHAR(100),
    parent_id INT,
    level INT,
    path NVARCHAR(500)  -- NVARCHAR to support larger paths safely
);
-- Insert Root Nodes (parent_id IS NULL)
INSERT INTO #Tree
SELECT id, name, parent_id, 1, CAST(id AS NVARCHAR(500))
FROM categories
WHERE parent_id IS NULL;
-- Build the Tree Using a Loop
DECLARE @level INT = 1;
WHILE @@ROWCOUNT > 0  -- Loop until no more children are found
BEGIN
    SET @level = @level + 1;
    INSERT INTO #Tree
    SELECT c.id, c.name, c.parent_id, @level, CONCAT(t.path, '->', c.id)
    FROM categories c
    INNER JOIN #Tree t ON c.parent_id = t.id
    WHERE t.level = @level - 1;
END;
-- Retrieve the Tree Structure
SELECT * FROM #Tree ORDER BY path;
-- Cleanup: Drop Temporary Table
DROP TABLE #Tree;

Output:

Explanation: Here, the #Tree table in the query will store the hierarchical values like name, id, parent_id, etc. FROM #Tree ORDER BY path will parse the tree in a structured way.

Nested Set Model in SQL Server

The nested set model in the SQL Server allows for a fast, recursion-free, hierarchical tree with left and right tree boundaries. It does not need any recursion. However, it is difficult to maintain when we need to delete or add a node. 

Syntax:

CREATE TABLE categories (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    lft INT NOT NULL,
    rgt INT NOT NULL
);
INSERT INTO categories (id, name, lft, rgt) VALUES
(1, 'Root', 1, 10),
(2, 'Child1', 2, 5),
(3, 'Child2', 6, 9),
(4, 'SubChild1', 3, 4);
SELECT name, lft, rgt FROM categories ORDER BY lft;
SELECT p.* FROM categories c
JOIN categories p ON c.lft BETWEEN p.lft AND p.rgt
WHERE c.id = @node_id AND c.id <> p.id;
SELECT c.* FROM categories p
JOIN categories c ON c.lft BETWEEN p.lft AND p.rgt
WHERE p.id = @parent_id AND c.id <> p.id;
UPDATE categories SET rgt = rgt + 2 WHERE rgt >= @new_lft;
UPDATE categories SET lft = lft + 2 WHERE lft > @new_lft;
INSERT INTO categories (id, name, lft, rgt) VALUES (@new_id, @new_name, @new_lft, @new_lft + 1);

Example:

CREATE TABLE categories_nested (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    lft INT,
    rgt INT
);
INSERT INTO categories_nested (id, name, lft, rgt) VALUES
(1, 'Electronics', 1, 6),
(2, 'Laptops', 2, 3),
(3, 'Phones', 4, 5),
(4, 'Accessories', 7, 10),
(5, 'Chargers', 8, 9);
SELECT parent.name AS parent, child.name AS child
FROM categories_nested parent
JOIN categories_nested child 
ON child.lft BETWEEN parent.lft AND parent.rgt
ORDER BY child.lft;

Output:

Explanation: Here, the left nodes will have rgt = lft + 1 value, COUNT(c2.id) AS level will count the nodes, and ORDER BY c1.lft  will give a structured tree.

Using Materialized Path (Path Enumeration) in SQL Server

The Materialized path will make sure that you store the full path of the tree, like in (1/3/6), in a column, which makes it easier to query without recursion. 

Syntax:

CREATE TABLE TableName (
    Id INT PRIMARY KEY,
    Name NVARCHAR(255) NOT NULL,
    Path NVARCHAR(500) UNIQUE NOT NULL
);
INSERT INTO TableName (Id, Name, Path) VALUES (?, ?, ?);
SELECT * FROM TableName WHERE Path LIKE ?;

Example:

CREATE TABLE categories_path (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL,
    path VARCHAR(500)
);
INSERT INTO categories_path (id, name, parent_id, path) VALUES
(1, 'Electronics', NULL, '1'),
(2, 'Laptops', 1, '1/2'),
(3, 'Phones', 1, '1/3'),
(4, 'Gaming Laptops', 2, '1/2/4'),
(5, 'Accessories', NULL, '5'),
(6, 'Chargers', 5, '5/6');
SELECT * FROM categories_path WHERE path LIKE '1/2/%';

Output:

Explanation: Here, the WHERE path LIKE ‘1/2/%,’ the query fetched the value of the path 1/2/4 from the tree. 

To get the ancestors of a category

DECLARE @CategoryPath NVARCHAR(500) = '/1/3/';
SELECT * 
FROM categories_path
WHERE CHARINDEX(Path, @CategoryPath) > 0;

Output:

Explanation: @CategoryPath NVARCHAR(500) = ‘/1/3/’; this query fetched the values of parent node 1 and their child node 3 from the tree.

When you want to move from one path to another, you may need to update the path. 

UPDATE categories_path
SET Path = REPLACE(Path, '/1/2/', '/1/5/') 
WHERE Path LIKE '/1/2/%';
SELECT * FROM categories_path;

Output:

Explanation: Here, after changing the node path, you have to keep updating the path of the tree for better performance. Using this REPLACE(Path, ‘/1/2/’, ‘/1/5/’), you have to replace the updated path with the existing one. 

Pros and Cons of the Various Methods 

Real-World Examples

Case 1: Website navigation using MySQL Server

To navigate the user through the features of the company website. 

CREATE TABLE website_menu (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    parent_id INT NULL,
    FOREIGN KEY (parent_id) REFERENCES website_menu(id)
);
INSERT INTO website_menu (id, name, parent_id) VALUES
(1, 'Home', NULL),  
(2, 'About Us', 1),
(3, 'Our Team', 2),
(4, 'Careers', 2),
(5, 'Services', 1),
(6, 'Web Development', 5),
(7, 'Frontend', 6),
(8, 'Backend', 6),
(9, 'Digital Marketing', 5),
(10, 'Contact', 1);
WITH RECURSIVE menu_tree AS (
    SELECT id, name, parent_id, 1 AS level, CAST(id AS CHAR(500)) AS path
    FROM website_menu
    WHERE parent_id IS NULL
    UNION ALL
    SELECT m.id, m.name, m.parent_id, mt.level + 1, CONCAT(mt.path, '->', m.id)
    FROM website_menu m
    JOIN menu_tree mt ON m.parent_id = mt.id
)
SELECT * FROM menu_tree ORDER BY path;

Output:

Explanation: Here, the recursive CTE fetched the hierarchical path details of all the menus that are present on the website. 

Case 2: To get an organization hierarchy chart using SQL Server.

-- Drop temporary table if it already exists
IF OBJECT_ID('tempdb..#OrgTree') IS NOT NULL
    DROP TABLE #OrgTree;
-- Create the Employees Table
CREATE TABLE Employees (
    id TINYINT PRIMARY KEY, 
    name VARCHAR(30), 
    position VARCHAR(30),  
    manager_id TINYINT NULL,
    FOREIGN KEY (manager_id) REFERENCES Employees(id)
);
-- Insert Sample Data
INSERT INTO Employees (id, name, position, manager_id) VALUES
(1, 'Alice', 'CEO', NULL),
(2, 'Bob', 'CTO', 1),
(3, 'Charlie', 'CFO', 1),
(4, 'David', 'Eng Manager', 2),
(5, 'Eve', 'Software Eng', 4),
(6, 'Frank', 'Software Eng', 4),
(7, 'Grace', 'Finance Mgr', 3),
(8, 'Heidi', 'Accountant', 7);
-- Create a Temporary Table for the Hierarchy
CREATE TABLE #OrgTree (
    id TINYINT, 
    name VARCHAR(30),
    position VARCHAR(30),
    manager_id TINYINT NULL,
    level TINYINT, 
    path NVARCHAR(100)  
);
-- Insert Root Nodes (Top-Level Employees)
INSERT INTO #OrgTree (id, name, position, manager_id, level, path)
SELECT id, name, position, manager_id, 1, CAST(id AS NVARCHAR(100))
FROM Employees
WHERE manager_id IS NULL;
-- Declare a variable for loop control
DECLARE @level TINYINT = 1;
-- Iteratively insert child nodes until no more are found
WHILE @@ROWCOUNT > 0
BEGIN
    SET @level = @level + 1;
    INSERT INTO #OrgTree (id, name, position, manager_id, level, path)
    SELECT e.id, e.name, e.position, e.manager_id, @level, CONCAT(t.path, '->', e.id)
    FROM Employees e
    INNER JOIN #OrgTree t ON e.manager_id = t.id
    WHERE t.level = @level - 1;
END;
-- Retrieve the Hierarchical Tree with Formatted Output
SELECT 
    RIGHT('0' + CAST(id AS VARCHAR), 2) AS id,  -- Formats ID as 01, 02, etc.
    LEFT(name, 10) AS name,  -- Reduced column size
    LEFT(position, 15) AS position,  -- Reduced column size
    COALESCE(CAST(manager_id AS VARCHAR), 'NULL') AS mgr_id, 
    path
FROM #OrgTree
ORDER BY path;
-- Cleanup: Drop Temporary Table
DROP TABLE #OrgTree;

Output:

Explanation: Here, using loops and temporary tables, the function created a hierarchy tree of the employees. 

Conclusion

The most efficient way to parse a flat table into a tree is by using recursive CTEs and alternative methods like loops with temporary tables, which work well for procedural logic in SQL Server. Nested Set Models will query faster, but it is very complex to maintain the tree. Whereas, the Materialized Path method is cost-efficient, and it makes finding the path easier. In this blog, you have gained knowledge on the most efficient way to parse a flat table into a tree.

Take your skills to the next level, by enrolling in the SQL Training Course today and gain hands-on experience. Also, prepare for job interviews with our SQL interview questions, prepared by industry experts. 

What is the most efficient/elegant way to parse a flat table into a tree – FAQs