Algorithm Performance Optimization for Supply Chain Reconciliation Permalink to this section#

↑ Part of Matching & Reconciliation Algorithms.

Reconciliation pipelines degrade predictably as transaction volume scales, vendor ecosystems expand, and SKU granularity increases. The match criteria are rarely the bottleneck — the cost is in how those criteria are executed against millions of purchase orders, goods receipts, and supplier invoices inside a fixed overnight batch window. When a run that finished in twelve minutes last quarter takes ninety this quarter on the same hardware, the regression is almost never in the business rules; it is an algorithmic-complexity mismatch against dataset cardinality that only surfaces once the data grows.

This is an engineering trade-off problem, not a tuning chore. The match rules defined in the rest of the Matching & Reconciliation Algorithms reference are correctness contracts — they must produce the same matched ledger regardless of how fast they run — so optimization work has to leave their output byte-identical while changing only how the work is scheduled, vectorized, and indexed. The patterns below cover where the time actually goes (complexity, not logic), how to collapse the candidate space before expensive comparisons run, and how to keep the engine deterministic and replayable when a node dies mid-batch.

Core Concept & Decision Criteria Permalink to this section#

Performance bottlenecks rarely originate from flawed business logic; they emerge when an algorithm’s complexity class is wrong for the data volume it is handed. Row-wise iteration across purchase orders, invoices, and receiving logs — a for loop calling extractOne per record, or a nested-loop join — introduces $O(n^2)$ or worse behaviour that is invisible at ten thousand rows and catastrophic at ten million. The governing rule is: reduce the candidate space with cheap deterministic operations before you spend cycles on expensive comparisons, and express every stage as a set operation rather than a Python loop.

For a pure pairwise comparison of two feeds the work is the product of their sizes, $C_{\text{naive}} = |A| \times |B|$. A blocking key that partitions both feeds into $k$ disjoint buckets collapses that to the sum of within-bucket products:

for roughly even buckets. Choosing a blocking key with high cardinality (vendor id × fiscal period, normalized SKU prefix) is the single highest-leverage decision on this page — it is what turns a quadratic fuzzy stage into a near-linear one. The same logic underpins the tiered design in Exact vs Fuzzy Matching Strategies: run the cheap deterministic join first, and only the unmatched residual ever reaches the costly probabilistic stage.

The decision signals below tell you which lever to pull for a given symptom rather than optimizing blindly.

Treat the rightmost column as the reason each lever is worth the engineering cost: every row converts a complexity class, not a constant factor, which is what keeps the engine inside its SLA as volume compounds.

Implementation Permalink to this section#

The reference pattern is a tiered, set-based pass: build a blocking key, use a Bloom filter to discard records that cannot possibly match, then run the deterministic join vectorized — never row-by-row. Keeping each stage a pure function of its input is what preserves replay determinism: the same input frame yields the same candidate set and the same matched output, which is the precondition for the idempotent recovery covered below. Structured logging at each stage emits the audit fields the recovery section depends on.

import logging
from typing import Iterable

import pandas as pd
from rbloom import Bloom

logger = logging.getLogger("recon.match.optimize")


def build_blocking_key(df: pd.DataFrame, cols: list[str]) -> pd.Series:
    """Vectorized composite blocking key over normalized columns.

    Partitions both feeds into disjoint buckets so downstream joins
    compare only within-bucket candidates, converting an O(n^2) cross
    product into roughly O(n^2 / k) work for k buckets.
    """
    # Operate on whole columns, never per-row; .str ops are vectorized.
    key = df[cols[0]].astype("string").str.strip().str.upper()
    for col in cols[1:]:
        key = key.str.cat(df[col].astype("string").str.strip().str.upper(), sep="|")
    logger.debug("blocking_key_built cols=%s rows=%d", cols, len(df))
    return key


def bloom_prefilter(
    candidates: pd.DataFrame, reference_keys: Iterable[str], key_col: str
) -> pd.DataFrame:
    """Drop candidate rows whose key cannot exist in the reference set.

    A Bloom filter answers 'definitely absent' in O(1) with negligible
    memory, so doomed pairs never reach the expensive join. False
    positives are harmless here: they simply pass through to the exact
    join, which rejects them deterministically.
    """
    bloom = Bloom(max(1, sum(1 for _ in iter(reference_keys))), 0.01)
    for k in reference_keys:
        bloom.add(k)

    mask = candidates[key_col].map(lambda k: k in bloom)
    kept = candidates.loc[mask]
    logger.info(
        "bloom_prefilter rows_in=%d rows_kept=%d dropped_pct=%.1f",
        len(candidates),
        len(kept),
        100.0 * (1 - len(kept) / max(1, len(candidates))),
    )
    return kept


def optimized_exact_join(
    po_df: pd.DataFrame, inv_df: pd.DataFrame, key_cols: list[str]
) -> pd.DataFrame:
    """Set-based hash join on a composite key — no Python iteration.

    pandas merge dispatches to a vectorized hash join; this is the
    deterministic first tier whose unmatched residual feeds the
    costlier fuzzy stage.
    """
    po_df = po_df.assign(_bk=build_blocking_key(po_df, key_cols))
    inv_df = inv_df.assign(_bk=build_blocking_key(inv_df, key_cols))

    inv_df = bloom_prefilter(inv_df, po_df["_bk"].tolist(), key_col="_bk")

    matched = po_df.merge(inv_df, on="_bk", how="inner", suffixes=("_po", "_inv"))
    logger.info("exact_join_done matched=%d", len(matched))
    return matched.drop(columns="_bk")

For workloads that exceed RAM, swap the eager pandas frames for a columnar lazy engine so the same logic streams out-of-core instead of materializing every intermediate. Converting CSV/JSON payloads to a columnar layout first cuts scan I/O and enables predicate pushdown; the contiguous memory model behind that speedup is documented in the Apache Arrow Columnar Format specification.

import logging

import polars as pl

logger = logging.getLogger("recon.match.lazy")


def lazy_tolerance_join(
    po_path: str, inv_path: str, qty_tol: float = 0.02
) -> pl.DataFrame:
    """Streaming, out-of-core join with a vectorized tolerance mask.

    LazyFrames defer execution and let the engine push the filter into
    the scan and stream batches, so RAM stays bounded regardless of
    feed size. The tolerance comparison is a boolean expression, not a
    per-row branch, so it vectorizes (and SIMD-accelerates) cleanly.
    """
    po = pl.scan_parquet(po_path)
    inv = pl.scan_parquet(inv_path)

    joined = po.join(inv, on=["vendor_id", "sku"], how="inner")
    within_tol = joined.filter(
        ((pl.col("qty_inv") - pl.col("qty_po")).abs() / pl.col("qty_po")) <= qty_tol
    )

    result = within_tol.collect(streaming=True)
    logger.info("lazy_tolerance_join matched=%d qty_tol=%.3f", result.height, qty_tol)
    return result

Expressing tolerance checks as boolean masks rather than iterative conditionals is what eliminates branch-misprediction penalties and unlocks SIMD acceleration; the window semantics those masks encode are defined in Setting Quantity and Price Tolerance Windows. The same vectorized discipline keeps the bundled-shipment grouping in Multi-SKU Grouping Logic from collapsing into per-group Python loops.

Configuration & Threshold Calibration Permalink to this section#

Optimization parameters are environment- and vendor-tier specific: a small set of clean ERP feeds tolerates an eager in-memory path, while multi-tenant exports joined with WMS telemetry demand streaming execution and aggressive blocking. The defaults below are deliberately conservative so a volume spike surfaces as a tuned parameter rather than an OOM kill at 03:00.

Two calibration rules dominate. First, pick the blocking key for bucket evenness, not convenience — a key that leaves one giant bucket (a dominant vendor) reintroduces the quadratic cost you were trying to remove, so salt or sub-partition skewed buckets. Second, keep compute_budget_ms a hard ceiling rather than an aspiration: a record that cannot be matched within budget should be dead-lettered with a reason code, never allowed to blow the batch window for every other record behind it.

Orchestration & Integration Permalink to this section#

This stage sits between ingestion and the final matched ledger, and it must guarantee that its output is identical to an unoptimized run — optimization changes throughput, never the result set. Upstream, it consumes already-validated, columnar-friendly records: the parsing and contract-validation boundary is owned by Schema Validation Using Pydantic, so the optimizer never wastes cycles repairing malformed rows. When the volume itself is the problem at the front door, the concurrency patterns in Async Batch Processing for High-Volume Feeds keep ingestion from becoming the new bottleneck.

Downstream, the matched ledger and the unmatched residual feed finance and procurement consumers, so the stage must be idempotent: re-running the same batch produces the same delta with no double-counting. That is enforced with a deterministic composite key and an upsert keyed on identity, the same discipline the parent Matching & Reconciliation Algorithms pipeline relies on for exactly-once writes. Because each tier is a pure function of its immutable input, a replay of yesterday’s staged partition reproduces yesterday’s matched ledger byte for byte — which is what makes the recovery path below safe to trigger automatically. Any access controls and audit isolation around the intermediate stores follow the boundaries in Data Security Boundaries for Procurement Systems.

Debugging & Pipeline Recovery Permalink to this section#

Performance work is only safe if failure is deterministic, so the goal is a self-clearing queue and reproducible recovery rather than a manual hunt through partial outputs. Checkpoint intermediate match state after each tier, make every write idempotent, and route anything that exceeds its budget to a structured DLQ that carries enough context to replay the decision.

• DLQ payload contract. Each entry stores the blocking key, the tier reached (exact / tolerance / fuzzy), the candidate-pool size at entry, elapsed compute, and the exception or budget overrun. Without the candidate-pool size, an engineer cannot tell a skew problem from a genuinely hard record.
• Failure-reason taxonomy. Tag every record with one of COMPUTE_BUDGET_EXCEEDED (ran past compute_budget_ms), MEMORY_SPILL (join spilled to disk / OOM-adjacent), BLOCKING_SKEW (one bucket dominated the run), INDEX_MISS (planner chose a full scan), or TRANSIENT_DEPENDENCY (upstream feed/API stall). This single field turns a flat queue into a triage dashboard.
• Monitoring signals & alert thresholds. Track per-batch wall-clock, peak RSS, join-spill events, Bloom drop-rate, and DLQ depth by reason. A Bloom drop-rate falling toward zero means the filter has stopped paying for itself (keys diverged upstream); a climbing BLOCKING_SKEW count means a vendor now dominates a bucket and the key needs sub-partitioning. Alert on a sustained rise, not a single spike — overnight transients are expected.
• Audit log fields. Emit batch_id, tier, rows_in, rows_matched, candidate_pool, elapsed_ms, peak_rss_mb, and recon_status to append-only storage for every batch so SOX and internal reviews can replay any performance decision and confirm the optimized run matched the reference output.

FAQ Permalink to this section#

Does optimizing the algorithm risk changing which records match? Permalink to this section#

No — that is the constraint that defines the work. Blocking, Bloom pre-filtering, indexing, and vectorization only change which comparisons are skipped or how they are scheduled; they must never relax a match rule. Bloom false positives pass through to the deterministic exact join, which rejects them, and blocking only removes pairs that share no key. Validate by diffing the optimized ledger against an unoptimized reference run on a sample partition — it should be byte-identical.

When should I move off pandas to Polars or DuckDB? Permalink to this section#

Switch before RAM becomes the bottleneck, not after. pandas is fine for sub-million-row, single-feed workloads, but once multi-tenant ERP exports joined with WMS telemetry approach available RAM you get garbage-collection thrash and swap-induced latency that no amount of rule tuning fixes. Columnar lazy engines stream out-of-core with bounded memory, so the same logic keeps a stable runtime as volume grows.

Why is my fuzzy matching stage so slow even after adding more CPU? Permalink to this section#

Because unblocked similarity scoring is $O(n^2)$ — throwing cores at a quadratic stage buys you a constant factor while the cost grows with the square of volume. The fix is algorithmic, not hardware: introduce a high-cardinality blocking key so similarity is only computed within buckets, and only on the residual that the exact tier failed to match. That converts the dominant cost from $O(n^2)$ to roughly $O(n^2/k)$.

How big should the Bloom filter be and what false-positive rate? Permalink to this section#

Size it to the reference key count with a 1% false-positive rate (bloom_fp_rate = 0.01) as a default. That keeps memory negligible while discarding 80–95% of doomed candidates in typical feeds. Lowering the rate to 0.1% cuts pass-through to the exact join at the cost of more RAM per filter; raising it toward 5% saves memory but lets more false positives reach the join. Since false positives are corrected deterministically downstream, err toward the cheaper, smaller filter.

What happens to a record that can’t be matched within its compute budget? Permalink to this section#

It is dead-lettered with COMPUTE_BUDGET_EXCEEDED, never allowed to overrun the batch window. A single pathological record — a vendor with thousands of near-identical line items in one bucket — must not starve every record behind it. Capping per-record compute and routing overruns to the DLQ keeps the batch deterministic and bounded, and the failure-reason tag makes the root cause (usually BLOCKING_SKEW) visible for the next run.

Related Permalink to this section#

• Exact vs Fuzzy Matching Strategies — the tiered design whose cheap-first ordering this page exploits
• Setting Quantity and Price Tolerance Windows — the boolean masks that vectorize instead of branch
• Multi-SKU Grouping Logic — keeping bundled-shipment grouping set-based at scale
• ↑ Parent: Matching & Reconciliation Algorithms