Core Architecture Cost Mapping Systems

pandas merge vs Recursive CTE for BOM Resolution

This page helps a food-tech developer choose how to resolve a recipe bill-of-materials tree into a flat set of leaf quantities: expand it in the database with a recursive common table expression, or pull the edges into the application and traverse them with pandas or graphlib. It is a decision companion to designing recipe BOM databases; read that for the schema, then use this to pick a traversal that fits your workload — the audience actively chooses between these two, and the wrong choice shows up as either a slow nightly job or a chatty database.

Both approaches give the same leaves-first result. The difference is where the recursion runs, and that determines throughput, cycle-safety, and how much data crosses the wire.

Prerequisites and Data Contract

  • A recipe_bom_edges table of (parent_id, child_id, quantity) forming a directed acyclic graph, with temporal validity columns.
  • PostgreSQL 12+ for the CTE path; Python 3.11+ with pandas 2.x (and the standard-library graphlib) for the application path.
  • The output contract is identical for both: one row per leaf child_id with the accumulated total_quantity for a given root menu item, in canonical units.
Recursive CTE versus application-layer traversal A comparison of two BOM resolution strategies. The recursive CTE path runs the traversal inside PostgreSQL, keeping computation next to the data, avoiding shipping the edge table, and feeding SQL materialized views, with a depth predicate as its cycle guard. The application path pulls the edge set once and traverses it with pandas or graphlib, fitting a batch pipeline that also performs ingestion, substitution and structured logging, using a topological sort as its cycle guard. Recursive CTE (in DB) pandas / graphlib (in app) • traversal runs next to the data • no edge table shipped over the wire • feeds materialized views directly • cycle guard: depth predicate • best when output is a SQL report • edges pulled once, reused in-process • traversal alongside ingest + logging • vectorized cost math in pandas • cycle guard: topological sort • best inside a batch pipeline

Step-by-Step Implementation

Step 1 — Resolve in the database with a recursive CTE

Keep the traversal where the edges live when the consumer is a SQL report or a materialized view.

WITH RECURSIVE bom_tree AS (
    SELECT parent_id, child_id, quantity, 1 AS depth
    FROM recipe_bom_edges
    WHERE parent_id = $1
      AND (valid_to IS NULL OR valid_to > CURRENT_DATE)
    UNION ALL
    SELECT e.parent_id, e.child_id,
           e.quantity * bt.quantity AS quantity,
           bt.depth + 1
    FROM recipe_bom_edges e
    JOIN bom_tree bt ON e.parent_id = bt.child_id
    WHERE (e.valid_to IS NULL OR e.valid_to > CURRENT_DATE)
      AND bt.depth < 12                       -- cycle guard
)
SELECT child_id, SUM(quantity) AS total_quantity
FROM bom_tree
GROUP BY child_id;

Step 2 — Resolve in the application with graphlib

When resolution is one stage of a larger Python batch that also ingests, substitutes, and logs, pull the edges once and traverse them leaves-first with a topological sort.

from __future__ import annotations

from collections import defaultdict
from decimal import Decimal
from graphlib import TopologicalSorter

import pandas as pd


def resolve_bom(edges: pd.DataFrame, root: str) -> pd.DataFrame:
    """Accumulate leaf quantities for one root, leaves-first."""
    graph: dict[str, set[str]] = defaultdict(set)
    qty: dict[tuple[str, str], Decimal] = {}
    for e in edges.itertuples():
        graph[e.parent_id].add(e.child_id)
        qty[(e.parent_id, e.child_id)] = Decimal(str(e.quantity))

    order = list(TopologicalSorter(graph).static_order())   # raises on a cycle
    acc: dict[str, Decimal] = defaultdict(Decimal)
    acc[root] = Decimal("1")
    for node in reversed(order):
        for child in graph.get(node, ()):
            acc[child] += acc[node] * qty[(node, child)]

    leaves = [n for n in acc if n not in graph]
    return pd.DataFrame({"child_id": leaves,
                         "total_quantity": [acc[n] for n in leaves]})

Step 3 — Choose by workload, not by preference

Pick the CTE when the traversal result is consumed by SQL — a materialized view, a report query, a dashboard fed directly from the database — because it avoids shipping the whole edge table to the app and lets Postgres optimize the join. Pick the application traversal when resolution is one step in a Python batch that also does unit canonicalization, substitution, and structured logging in one process, because keeping the tree in memory avoids a database round trip per stage and the cost math is already vectorized there.

Verification and Validation

  • Agreement. Run both against the same root and assert identical leaf quantities with pd.testing.assert_frame_equal after sorting. Any divergence is a multiplicity-accumulation bug in one path.
  • Cycle safety. Insert a deliberate A -> B -> A edge. The CTE must terminate via the depth guard; graphlib must raise CycleError. A silent hang or infinite result means the guard is missing.
  • Temporal correctness. Expire an edge with a past valid_to and confirm it drops from both resolutions.
  • Throughput. Time both on a realistic estate. If the CTE wins, your consumer is probably SQL; if the app path wins, you were likely shipping the edge table needlessly.

Gotchas and Edge Cases

  • Multiplicity accumulation. Both paths must multiply quantity down the tree (child_qty * parent_qty), not add. A dish using 2 sauces each needing 3 tomatoes needs 6 tomatoes; a path that forgets to multiply undercounts.
  • Missing cycle guard. A real DAG should never cycle, but a data-entry bug can. The CTE needs the depth < predicate and the app needs the topological sort to raise — never rely on the data being clean.
  • Shipping the whole edge table. The application path is only fast if you pull the relevant edge subset, not every edge in the catalog, per root. Filter to reachable edges or batch roots together.
  • Float in the accumulator. Keep accumulated quantities in Decimal; a float accumulator drifts over deep trees and later multiplies into cost error.

For engine specifics, see the official PostgreSQL recursive query documentation and the Python graphlib documentation.