Recursive Categories

Hook: Recursive category queries are like following a breadcrumb trail down a store aisle: interviewers love this because it checks whether you can move from one row to a whole tree.

Question: How do you fetch an entire category hierarchy, not just one level, in SQL?

Answer: Use a recursive CTE. The first SELECT grabs the starting category, called the anchor member, and the second SELECT keeps joining each row to its children until no more rows are found. This is the standard way to walk parent-child structures like categories, menus, and org charts.

Interview-Ready Answer: I’d use a recursive CTE, because it lets me start from one category and repeatedly join to its children until the tree is exhausted. The anchor query gives me the root row, and the recursive part follows parent_id to collect every descendant. I’d also add an index on parent_id, and if the data might contain bad cycles, I’d protect the recursion so it cannot loop forever.

Detailed Explanation: A recursive CTE is a query that feeds its own output back into itself. For category trees, the usual table shape is an adjacency list, which simply means each row stores its own id and a parent_id pointing to its parent.

How it works under the hood

1. The anchor member runs first and returns the starting rows, such as a root category or a chosen node.
2. The database stores those rows in an intermediate working set.
3. The recursive member runs next, joining the current working rows to the base table to find the next level of children.
4. Each new batch is added to the final result and also becomes the next input batch.
5. This repeats until the recursive member returns zero rows. That stopping point is called the fixpoint, meaning the result no longer changes.
6. If bad data could create a loop, you add a visited-path check so the same node is not visited forever.

When and why to use it

Use recursive CTEs when the depth is not known in advance: product categories, menus, permission trees, bill of materials, comment threads, and breadcrumbs. A normal self-join only works when you know the number of levels ahead of time; recursive SQL keeps going as long as there are more children.

Performance and edge cases

• An index on parent_id is the first thing to add. Without it, each recursion step may scan the whole table again.
• For a subtree with 1,000 rows, the logical work is close to O(n), but a wide, unindexed tree can feel much slower because every level keeps searching for children.
• Some engines impose recursion limits. For example, SQL Server defaults to 100 levels unless you change MAXRECURSION; other databases stop when no rows remain, but they can still time out or run out of memory on very deep trees.
• Cycle protection is important. One bad parent pointer can turn a safe tree walk into an infinite loop or a timeout storm.

Memory hook: think anchor = first step, recursive member = keep climbing, and stop when there are no more stairs.

Real-World Story: In an e-commerce catalog service, category trees power the left-nav menu, search filters, and SEO landing pages. A developer once used a simple self-join, so only the first child level appeared; deeper categories like Laptops > Gaming Laptops were missing from the site, and users thought inventory was gone. In a worse incident, a bad admin import created a cycle between two categories, and the recursive query without a visited-path guard kept looping until the database hit a recursion limit or timeout. The symptoms were ugly: catalog API latency jumped from milliseconds to seconds, CPU on the primary database spiked, logs filled with timeout errors, and the checkout funnel lost traffic because people could not browse to products. The fix was to add a proper recursive CTE, add an index on parent_id, and guard against cycles so one bad row could not take down the whole page.

Follow-up & Tricky Questions:

• How do you return only descendants at a certain depth? Add a depth column and filter it in the outer query, for example WHERE depth <= 2. That keeps the recursion simple and lets you control how much of the tree you expose.
• How do you find the ancestors of a category instead of its children? Reverse the join: start from the leaf node and join the table where c.id = current.parent_id. The recursion then walks upward to the root and naturally produces a breadcrumb trail.
• Why do interviewers like UNION ALL here? Because recursion usually wants every row produced by each step, including rows that happen to look similar. UNION removes duplicates and adds extra sorting/dedup work, which can hide data problems and slow the query down.
• How do you control ordering? Use a depth column for breadth-first style output, or a path column for a tree-like depth-first order. The order is not automatic just because the query is recursive.
• What index matters most? parent_id. The recursive step repeatedly looks up children by parent, so that index usually gives the biggest win.
• Can I join other tables inside the recursive member? Yes, as long as you keep the recursion logic clear. For example, you can join category metadata or product counts, but heavy joins inside every recursion step can get expensive fast.
• Gotcha: does a recursive CTE always prevent infinite loops? No. A recursive CTE is just a mechanism; if your data contains a cycle and you do not guard against it, the query can keep producing rows until the engine stops it.
• Gotcha: is a recursive CTE always faster than application code? Not always, but it usually wins when the hierarchy is in the database because the engine can optimize the set-based work and avoid many round trips.

Common Mistakes:

• Using a plain self-join for unknown depth. Correction: self-joins are only good when the number of levels is fixed; use a recursive CTE when the tree can grow.
• Forgetting the anchor member. Correction: every recursive CTE needs a starting query, or the recursion has nothing to build from.
• Using UNION by default. Correction: use UNION ALL unless you have a specific deduplication reason; it is the standard pattern for recursion.
• Not indexing parent_id. Correction: the recursive step depends on that lookup, so the index is often the difference between fast and painful.
• Ignoring cycles and bad data. Correction: add a visited-path guard or another cycle check if the hierarchy is not perfectly trusted.

Memory Hook: Anchor plants the seed, recursion grows the tree, and the query stops when the tree has no more branches.

Cheat Sheet:

• Recursive CTE = a CTE that references itself.
• Anchor member = starting rows.
• Recursive member = next wave of rows.
• UNION ALL is the normal choice.
• parent_id index helps a lot.
• Cycles need protection; empty anchor means empty result.

Practice Tasks:

• Write a recursive CTE that lists all descendants of a chosen category.
• Rewrite it to return ancestors and build a breadcrumb path.
• Add a cycle guard and then test what happens when the root category does not exist.