Source-linked AI summary
Product Costing in Data Pipelines
Li Peng, Jie You, Feng Shi, Yihang Wu, Jianxin Wang, Weiran Liu, Xinyu Peng, Junhua Wang, Lei Zhang, Lin Qu, Xiaohui Yu, Kui Ren, Jinfei Liu
TL;DR
Enterprises need to allocate pipeline costs to products, but reusable data and massive, complex pipelines make accurate costing challenging. The paper formalizes MCDP and introduces CostApp, which isolates cyclic dependencies and solves a reduced system exactly. CostApp handles a production pipeline with over 28 million entities within an hour and supports pipelines up to 102× larger than the direct matrix-based baseline.
Problem
Product-level cost allocation matters for pricing and cost recovery, but non-rivalrous data and massive pipeline graphs complicate complete, tractable costing.
Source: §1 · pp. 2–4Method
CostApp isolates cyclic dependencies with auxiliary vertices, aggregates costs onto a compact set, and solves the resulting reduced linear system exactly.
Source: §1 · p. 4, §4.1 · p. 12Results
Over 28 million entities are costed within an hour while preserving exactness, supporting pipelines up to 102× larger than the direct matrix-based baseline.
Source: §7 · p. 24Takeaways & Limitations
CostApp has been deployed at Alibaba for costing and pricing data in production environments for years.
Source: §1 · p. 4On cyclic graphs, RollUpApp requires a superstep threshold to terminate, which yields approximate rather than exact results.
Source: §3.3.1 · p. 10
Abstract
from arXiv · showhide
Large data-intensive enterprises spend millions of dollars monthly running data pipelines. Apportioning this cost back to individual products, known as product costing, is a prerequisite for data pricing and cost recovery. However, this process is fundamentally more challenging than physical manufacturing costing due to the unique characteristics of data pipelines, including the non-rivalrous nature of data that complicates the costing formulation, the prevalence of cyclic dependencies that distort the accuracy of results, and the massive scale of pipelines that leads to computational intractability. In this paper, for the first time, we formalize the problem of product costing in data pipelines as a manufacturing cost of data products (MCDP) problem to overcome the non-rivalrous nature of data. To solve MCDP, we propose CostApp, a hybrid algorithm that achieves both exactness and scalability, even for cyclic and massive-scale pipelines. CostApp performs a dimensionality reduction by isolating cyclic dependencies via a feedback arc set (FAS). It aggregates costs onto a compact set of key vertices using a scalable iterative approach, transforming the intractable computational problem into a reduced linear system that can be solved exactly and efficiently by a basic matrix-based method. Experiments on both real-world data and synthetic data show that CostApp scales to process a production pipeline with over 28 million entities within an hour while preserving exactness, supporting pipelines up to 10^2 larger than the direct matrix-based baseline.
1 Introduction
Data pipelines incur substantial recurring costs, yet allocating them to final data products is difficult because data is reusable, dependencies can be cyclic, and consolidated graphs are massive. The paper formalizes product costing as MCDP and proposes CostApp, which combines scalable aggregation with an exact reduced-system solution.
1 Introduction
- Final data products are the natural financial-accountability unit because they deliver business value, and accurate cost attribution supports pricing and cost recovery.The paper notes that product costing remains largely unexplored despite its financial importance.Source: §1 · p. 3
- Because data is non-rivalrous, marginal-cost allocation can under-cost products, while charging each consumer the full cost duplicates costs.Both approaches violate completeness, the requirement that consumed resources be fully accounted for without duplication.Source: §1 · p. 3
- Periodic workloads create time-versioned dependencies and cycles, where costs can circulate indefinitely and distort product costing.Basic cost roll-up methods can fail on these cycles, potentially misleading pricing strategies.Source: §1 · p. 3
- Consolidated enterprise pipelines can contain tens of millions of entities, making direct matrix inversion with O(|V|^3) time computationally prohibitive.Alibaba’s example has 28 million vertices.Source: §1 · pp. 3–4
- MCDP formalizes data-pipeline product costing with a ratio-based model governed by cost conservation, avoiding the under- or over-costing pitfalls of consumption-based allocation.RollUpApp scales but is approximate, while MatrixApp is exact but limited to small pipelines.Source: §1 · p. 4
- CostApp isolates cycles using a feedback arc set, aggregates costs onto auxiliary vertices, then solves a reduced linear system exactly.The reduced matrix is sized in proportion to feedback arcs, reported as less than 0.05% of |V|.Source: §1 · p. 4
- Over 28 million entities can be costed in an hour with CostApp, which preserves exactness and has been deployed at Alibaba.The experiments use real-world Alibaba and synthetic data.Source: §1 · p. 4
2 Preliminaries
The preliminaries define the consolidated pipelines, graph representation, billing snapshot, and distributed computation model used by the paper.
2.1 Data Pipelines
- Consolidated pipelines combine transformation tasks across business domains, with operations converting input entities into outputs and producing source data, intermediate data, and final data products.Intermediate data is materialized for reuse; final products are not processed further.Source: §2.1 · p. 5
- Pipelines are modeled as weighted directed cyclic graphs: vertices are data entities, arcs are transformation flows, and arc weights are static cost-allocation ratios.Roots represent source data, leaves represent products, and internal vertices represent intermediate data.Source: §2.1 · p. 5
- Costing uses a billing-period snapshot that combines versions’ resource costs at logical-entity vertices and records observed dependencies as arcs.Dependencies on earlier versions appear as feedback arcs.Source: §2.1 · p. 5
2.2 Pregel-based Distributed Graph Computation
- Pregel computation partitions the graph across workers and proceeds in synchronized supersteps, with vertices processing messages and updating local state.RollUpApp sends cost messages, FindFAS propagates labels, and GetMatrix propagates keyed cost maps.Source: §2.2 · p. 6
3 Problem Formulation and Basic Solutions
The section defines manufacturing costs and formalizes product costing as computing each data product’s share of pipeline costs. It presents two basic algorithms with complementary limits: RollUpApp is scalable on acyclic graphs, while MatrixApp is exact but computationally prohibitive at scale.
3.1 Data Cost in Data Pipelines
- An entity’s manufacturing cost combines its direct resource cost with allocated costs inherited from upstream inputs.Direct cost includes CPU, memory, and storage expenditures; allocation ratios can reflect strategies such as equal split, usage, or value.Source: §3.1 · pp. 6–7
3.2 Product Costing in Data Pipelines as an MCDP Problem
- Under cost conservation, the total manufacturing cost of leaf data products equals the pipeline’s total direct cost, making product costing a completeness-preserving allocation problem.Completeness avoids both under-allocation and duplicated costs when intermediate data is reused.Source: §3.2 · pp. 7–8
- The MCDP problem computes the manufacturing cost of each leaf data product from the pipeline graph, edge allocation ratios, and entity direct costs.Source: §3.2 · pp. 7–8
3.3 Basic Solutions
- The two basic solutions, RollUpApp and MatrixApp, do not each meet both exactness and scalability goals, but serve as building blocks for the hybrid approach.Source: §3.3 · p. 8, §3.2 · p. 8
3.3.1 The RollUpApp Algorithm.
- RollUpApp repeatedly propagates each non-leaf vertex’s cost downstream in proportion to edge weights, then resets that vertex’s cost to zero.Its Pregel-style distributed implementation terminates with exact results on DAGs, in at most the longest-path length P supersteps.Source: §3.3.1 · pp. 8–9
- On cyclic graphs, RollUpApp’s costs circulate indefinitely; a superstep threshold can force termination but yields approximate results.Source: §3.3.1 · p. 10
3.3.2 The MatrixApp Algorithm.
- MatrixApp formulates cyclic cost dependencies as a global linear system and computes the exact, unique MCDP solution under cost conservation.The system uses the direct-cost vector and cost-allocation matrix: c = d + W^T c.Source: §3.3.2 · p. 10
- MatrixApp’s matrix inversion requires O(|V|^3) time and O(|V|^2) space, making it computationally and memory-prohibitive for pipelines with millions of entities.Source: §3.3.2 · p. 10
4 The Improved Algorithm: CostApp
This section presents CostApp’s approach to preserving exact product costs while scaling to cyclic, large data pipelines by aggregating costs on an acyclic graph and reducing the remaining linear solve to a compact system. It also establishes the algorithm’s correctness, weight-independent guarantees, and complexity across distributed graph processing and a centralized solve.
4.1 Overview of CostApp
- CostApp combines scalable graph processing with an exact compact-system solution, shifting matrix inversion from the full graph to a tiny system that is often less than 0.05% of |V| in size.Its two phases aggregate costs on acyclic portions of the pipeline and then resolve the remaining cyclic dependencies.Source: §4 · p. 11, §4.1 · p. 11
4.2.1 (1.a) Identifying Cycles via Finding an FAS.
- FindFAS identifies feedback arcs using hierarchical labels: an arc is selected when its destination label is a prefix of its source label, yielding a valid feedback arc set.A minimum feedback arc set is NP-hard to find, but any efficiently computed valid set suffices; removing the selected arcs makes the graph acyclic.Source: §4.2.1 · pp. 13–14
4.2.2 (1.b) Isolating Cycles via Graph Editing.
- GraphEdit replaces each feedback arc with a path through auxiliary sink and source vertices, preserving the manufacturing cost of every original data product.The sink retains intercepted cost during Phase 1, and the paired source marks where it resumes downstream flow in Phase 2.Source: §4.2.2 · p. 14
4.2.3 (1.c) Aggregating Costs on the Acyclic Graph.
- On the resulting acyclic graph, RollUpApp consolidates costs from internal vertices onto terminal vertices while preserving each original data product’s manufacturing cost.The terminal set comprises the original data products and the newly created sink vertices; this is Phase 1’s aggregation step.Source: §4.2 · p. 13, §4.2.3 · p. 15
4.3.1 Formulating the Reduced Linear System.
- Phase 2 resolves cyclic flows using terminal costs as direct costs in a closed system that accounts for repeated traversals of the original cycles.The reduced system has a unique solution because its allocation matrix retains the required nonnegativity and row-sum properties.Source: §4.3 · p. 15, §4.3.1 · pp. 15–16
4.3.2 (2.a) Getting the Cost Allocation Matrix.
- GetMatrix constructs the reduced allocation matrix by injecting unit costs at all source vertices and propagating source-keyed cost maps through the acyclic graph in one Pregel job.The terminal cost maps provide the matrix columns; GetMatrix and RollUpApp can be merged into one Pregel workload to avoid duplicated overhead.Source: §4.3.2 · p. 16
4.3.3 (2.b) Solving the Reduced Linear System.
- Because the reduced allocation matrix is block upper triangular, CostApp inverts only the sink block and obtains data-product costs by matrix-vector multiplication.The block structure follows from data products being leaves that do not propagate costs.Source: §4.3.3 · p. 16
- O(|V_sk|^3) is the dominant inversion cost for MatrixApp*, and production pipelines have |V_sk| = |A_FAS| < 0.05%|V|.The reduced system is followed by a matrix-vector multiplication.Source: §4.3.3 · p. 17
4.4 Analysis
- CostApp exactly matches MatrixApp for graphs satisfying cost conservation when costs start at C_dc(v), through cost-preserving graph edits, roll-up, and a reduced solve.The proof traces preservation from GraphEdit and RollUpApp to solving the remaining terminal-vertex system.Source: §4.4 · pp. 17–18
- Exactness and asymptotic complexity hold for any fixed nonnegative weights satisfying Definition 1; neither depends on the numerical values of w.FindFAS depends on graph topology, while RollUpApp and GetMatrix depend on paths and arcs.Source: §4.4 · p. 18
- O(L_p·(|V|+|A|)) + O(|A_FAS|^3 + |A_FAS|·|DPs|) is CostApp’s total complexity, combining near-linear distributed processing with the compact MatrixApp* solve.The distributed term handles the bulk of computation and dominates overall runtime.Source: §4.4 · p. 18
5 Experiments
The experiments evaluate CostApp’s exactness and scalability, its component-level performance, and its practicality on Alibaba production pipelines. Across synthetic and production graphs, CostApp preserves exactness while scaling beyond direct matrix-based methods.
5.2.1 Exactness.
- CostApp maintains an MRE around 10^-15 across graph scales, while RollUpApp's MRE exceeds 40% because cyclic dependencies remain unresolved.The CostApp result is consistent with standard floating-point roundoff and matches the exact solution to machine precision.Source: §5.2.1 · p. 20, Figure 8 · p. 20
- On G1, CostApp reaches machine precision in 36 minutes, while RollUpApp does not reach machine precision within the measured time.RollUpApp's costs circulate within cycles, requiring extensive execution merely to approach the exact solution asymptotically.Source: §5.2.1 · p. 20
5.2.2 Scalability.
- CostApp processes graphs with 10^7 vertices with near-linear scalability, while MatrixApp-D runs out of memory beyond 10^4 vertices and MatrixApp-S takes more than two days beyond 10^6 vertices.Runtime also scales linearly with arc count when |V| = 10^6.Source: Figure 10 · p. 20, §5.2.2 · p. 21
5.3 Modular Evaluation
- FindFAS and S&G scale near-linearly with vertex count and use at most 12GB per worker at 10^7 vertices, though S&G takes nearly twice as long above 10^5 vertices.S&G propagates key-value maps, whose serialization, merging, and network payload grow with the number of source entries.Source: §5.3 · p. 21, Figure 11 · p. 21
- MatrixApp* handles 10^7 vertices within 360 seconds, while MatrixApp-D fails beyond 10^4 vertices and MatrixApp-S exceeds two days at |V| ≥ 10^6.CostApp reduces the solver's matrix from |V| × |V| to |A_FAS| × |A_FAS|, with |A_FAS| = 312 when |V| = 10^6.Source: §5.3 · p. 22, Figure 12 · p. 22
5.4 Real-world Pipeline Evaluation
- The identified FAS is below 0.05% of arcs in each of G1–G4, supporting the efficiency of the reduced matrix step.FindFAS uses randomized label initialization, so the reported FAS size is the average across 10 runs.Source: §5.4 · p. 22, Figure 13 · p. 23
- CostApp preserves exactness and completes within one hour on all four Alibaba production graphs, each containing millions of vertices.On the largest graph, G1, end-to-end execution takes approximately 2250 seconds, within the daily billing-cycle time window.Source: §5.4 · p. 22, Figure 14 · p. 23
5.5 Discussion
- On G1, SCC-based processing is 5.2× slower than CostApp under the same production configuration.SCC processing alternates graph propagation and local solves; CostApp completes graph propagation before solving one compact residual system.Source: §5.5 · p. 23
6 Related Work
Related work covers data pipelines, the cost structure of digital products, and value and cost allocation. The paper distinguishes its focus on pipeline-wide resource-cost apportionment from work on digital-product pricing and value allocation.
6.1 Data Pipelines
- Prior data-pipeline work studies ETL workflows, scheduled execution, and pipelines as infrastructure for warehousing and analytics.The cited examples include pipelines at Meta, Alibaba, and Google.Source: §6.1 · p. 23
6.2 Cost of Digital Product in Economy
- Digital-product research examines cost structures and pricing strategies, whereas this work addresses product costing in pipelines as a prerequisite for pricing and orthogonal to cost structure.Digital products can have near-zero unit production cost through sharing when reuse and sales volume are sufficient.Source: §6.2 · pp. 23–24
6.3 Value and Cost Allocation
- Shapley-value methods allocate value by marginal contribution, while CostApp computes pipeline-wide costs implied by business-selected allocation weights.A value-based rule, including one derived from Shapley values, may determine those weights.Source: §6.3 · p. 24
7 Conclusion and Future Work
The conclusion presents CostApp as an exact, scalable approach to product costing in large data pipelines. It also identifies explainable costing and applications beyond data pipelines as future directions.
7 Conclusion and Future Work
- CostApp preserves exactness on a production pipeline with over 28 million entities within an hour, supporting pipelines up to 10^2 times larger than the direct matrix-based baseline.The approach isolates cyclic dependencies to reduce exact-costing complexity from cubic to near-linear relative to graph size.Source: §7 · p. 24
- Future work includes tracing each product's exact cost breakdown to upstream origins and applying the cyclic sparse-linear-system capability beyond data pipelines.The paper names Markov Decision Processes and Leontief inverse calculations in economic modeling as possible domains.Source: §7 · p. 24
A.1 Proof of Theorem 2
- Theorem 2's proof uses cost conservation to show that total manufacturing cost at the leaves equals the sum of direct costs across the graph.The proof derives that equality by summing costs over vertices and applying the conservation property for non-leaf nodes.Source: §A.1 · p. 28
A.2 Proof of Theorem 3
The proof establishes that cost propagation on a DAG terminates after a bounded number of supersteps and yields exact manufacturing costs at the leaves.
A.2 Proof of Theorem 3
- Propagation on a DAG terminates in at most P supersteps, where P is the longest path length, because all costs reach leaves by then.At superstep P + 1, no non-leaf vertex can receive another message.Source: §A.2 · p. 29
- For each vertex, the total cost is its direct cost plus weighted costs received from upstream neighbors, defining a linear system identical to the manufacturing-cost system.Because the graph is a DAG, that system has a unique solution and C*(v) equals C_mc(v) for every vertex.Source: §A.2 · p. 29
- A leaf's final cost equals its accumulated C*(p), confirming that the algorithm computes each data product's manufacturing cost exactly.Leaves accumulate cost but do not distribute it.Source: §A.2 · p. 30
A.3 Proof of Theorem 4
The proof shows that MatrixApp exactly solves MCDP by implementing the unique closed-form solution for entity costs and extracting the costs of terminal data products.
A.3 Proof of Theorem 4
- The linear system (I−W^T)c = d has a unique solution, so MatrixApp’s closed-form inversion returns the true manufacturing costs of terminal data products.The proof derives this system from the recursive cost relation and uses invertibility of (I−W^T) to establish existence and uniqueness.Source: §A.3 · p. 30
A.4 Proof of Matrix Invertibility
The matrix proof establishes that the cost-allocation system is invertible and has a unique solution. The following lemma proof shows that removing the identified feedback arcs leaves an acyclic graph.
A.4 Proof of Matrix Invertibility
- Since ρ(W) < 1 and W and W^T share eigenvalues, (I−W^T) is invertible and the cost system has a unique solution.The proof first establishes ρ(W) ≤ 1, then excludes modulus-1 eigenvalues.Source: §A.4 · pp. 30–31
- Every row of W sums to at most 1, with leaf rows summing to less than 1, giving the spectral-radius proof its starting bound.The proof uses non-negativity and conservation of outgoing weights for non-leaf vertices.Source: §A.4 · p. 30
- The proof rules out eigenvalues of W with modulus 1 by propagating a maximal-modulus eigenvector value to a reachable leaf, whose zero row forces a contradiction.Every non-leaf vertex has a positive-weight path to a leaf in a valid data pipeline.Source: §A.4 · p. 31
A.5 Proof of Lemma 2
- Every directed cycle contains a feedback arc, so removing the feedback-arc set makes the transformed graph a DAG.After labels stabilize, each vertex stores the smallest label proposed along its incoming paths; the cycle argument identifies an arc removed by the feedback-arc set.Source: §A.5 · p. 32
A.6 Proof of Theorem 5
The proof shows that replacing each feedback arc with a path through auxiliary vertices preserves the cost equations and therefore the manufacturing costs of original vertices, including data products.
A.6 Proof of Theorem 5
- GraphEdit replaces each feedback arc u→v with u→v_sk→v_sr→v, assigning zero initial costs to the auxiliary vertices and preserving the original arc weight.The other upstream neighbors of v remain unchanged, with u replaced by v_sr.Source: §A.6 · p. 32
- Substitution makes the transformed cost equation for each original vertex identical to its original equation, preserving the unique costs of all data products.The proof states that the transformed system’s aggregated cost formulations remain equivalent for every original vertex.Source: §A.6 · p. 33
A.7 Proof of Theorem 6
The proof relates the two cost systems by expressing DAG cost propagation as a finite sum along paths. This establishes equality of the terminal cost vectors.
A.7 Proof of Theorem 6
- RollUpApp’s propagation on the DAG is expressed as a finite sum through P−1 powers of the block weight matrix, where P is the longest path length.The proof uses the finite geometric-sum identity to simplify the block-system expression.Source: §A.7 · p. 33
- The solution to the linear system corresponding to (G1, CDAG) is unique, and the equality c22 = c12 therefore implies the conclusion of Theorem 6.Source: §A.7 · p. 33
A.8 Proof of Theorem 7
The proof shows that CostApp preserves the original exact product costs through cycle isolation, acyclic cost aggregation, and solution of a reduced linear system. The accompanying subsections describe the matrix formulation and algorithm variants used in this process.
A.8 Proof of Theorem 7
- CostApp preserves the original exact product costs through cycle isolation, acyclic aggregation, and exact solution of the reduced terminal-node system.The proof argues that each transformation preserves the original manufacturing costs for final data products.Source: §A.8 · pp. 33–34
B Matrix Form Derivation
- The matrix formulation represents each vertex’s manufacturing cost as its direct cost plus allocated costs from predecessor vertices.The derivation defines cost and direct-cost vectors and a weighted adjacency matrix, then expresses the scalar relationships in vector form.Source: B Matrix Form Derivation · pp. 34–35
C The label Algorithm
- The Label algorithm initializes roots with unique labels, propagates smaller candidate labels downstream, and stops when labels no longer change.Updated labels carry an outgoing-edge suffix to downstream neighbors.Source: C The label Algorithm · p. 35
D A Formulation of GraphEdit
- GraphEdit replaces each feedback arc with auxiliary sink and source vertices connected by three replacement arcs.The replacement arc weights are assigned as specified by the algorithm.Source: D A Formulation of GraphEdit · pp. 35–36
E The RollUpApp∗Algorithm
- RollUpApp∗ aggregates incoming cost maps at each active vertex and propagates weighted maps downstream, handling multiple cost dimensions in one graph pass.Each vertex maintains a stateful cost map that accumulates costs for multiple keys.Source: E The RollUpApp∗Algorithm · p. 36
F Extended Future Work
The future-work discussion identifies explainable costing and broader applications of CostApp as directions for further study. It notes that explainability entails additional storage and communication overhead, while describing potential uses in sparse Markov decision processes and input-output economic models.
F Extended Future Work
- Explainable product costing could track how upstream entities contribute to each product’s cost, but its design and optimization are left for future work.The proposed component-level breakdown would incur additional storage and communication overhead.Source: F Extended Future Work · p. 37
- CostApp may apply to sparse Markov decision process Bellman equations and large-scale input-output economic models with cyclic dependencies.The paper identifies both as potential applications for future exploration.Source: F Extended Future Work · p. 37