CS Paper Radar

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

cs.CE ·submitted 2026-10-15 06:31 UTC · v1

Abstract

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.

Comment
24 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Non-Linear Pricing Restores Tractability for a Data Seller

cs.GT ·2026-09-29 ·Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma, Jiaxin Song
top venue similarity 0.63
Abstract · Accepted to NeurIPS 2026

We consider a data seller who designs pricing mechanisms over multiple datasets to maximize revenue from budget-constrained buyers. The seller offers multiple datasets and assigns each a pricing function that maps the quantity purchased to a total payment. The goal is to design these pricing functions to maximize revenue, anticipating that buyers---who trade off accuracy gains against cost---choose bundles optimally subject to their budget constraints. Prior work [Chaudhury et al., 2026] studies such optimal pricing under the restriction that each dataset is assigned a linear price, and shows that computing optimal linear prices is computationally intractable. In contrast, we allow each dataset to be priced via a general function and show that this additional flexibility can not only increase the revenue but also restore tractability, yielding a surprising simultaneous improvement in economic performance and computational efficiency. Even when pricing functions are only required to be monotone and lower-continuous, optimal pricing admits a highly structured and simple form: each pricing function is piecewise linear and convex (PLC), and the optimal solution can be computed in polynomial time. Moreover, the total number of kinks across all pricing functions is bounded by the number of buyers. Consequently, when datasets significantly outnumber buyers, most pricing functions are effectively linear. We further empirically study the structure of optimal pricing by analyzing the number of kinks and the revenue gap between optimal nonlinear pricing and optimal linear pricing on simulations generated from a real dataset.

0.32

DAGSmith: Dependency-Aware Rewriting for dbt-Style SQL Pipelines

cs.DB ·2026-08-23 ·Jie Liu, Lin Ma, Barzan Mozafari
code/data similarity 0.55
Abstract

Modern analytics is increasingly organized as recurring SQL pipelines rather than isolated SQL statements. Tools such as dbt, which have gained extreme popularity in recent years, allow teams to write each transformation as SQL and make dependencies between transformations explicit, producing directed acyclic graphs (DAGs) with hundreds or thousands of interdependent SQL models. Traditional query optimizers and source-to-source query rewriters operate on one query at a time, while materialized-view selection and multi-query optimization address narrower forms of reuse. They do not exploit the pipeline-level information exposed by explicit dependencies: how intermediate results are consumed, which downstream outputs depend on each computation, where expensive work sits relative to data reduction, which results are worth persisting, and how refresh schedules relate to input change and output demand. We introduce DAGSmith, to the best of our knowledge the first holistic dependency-aware source-to-source rewriting system for SQL pipeline DAGs. DAGSmith treats explicit dependencies as optimization signals. It analyzes each transformation with its upstream inputs, downstream consumers, and position in the pipeline DAG, uses an LLM to propose pipeline-level refactorings, separates SQL generation and equivalence checking to reject unsafe rewrites, retunes persistence choices with a learned cost model, and selects a globally compatible, conflict-free set of rewrites. This enables dependency-edge simplification, non-local semantic reuse, downstream-aware pruning, pipeline-aware work placement, rewrite-materialization co-optimization, and frequency-aware optimization. On the open-source Tuva dbt project, DAGSmith reduces elapsed time by 42.6% and warehouse compute cost by 67.7%, 98.1%/348.3% larger than state-of-the-art single-query rewriting.

0.39

Simpler Methods Work Better for L1 Penalized Logistic Models and Large Datasets

cs.LG ·2026-09-21 ·Edward Raff, James Holt
publishedunusual similarity 0.53
Abstract · To appear in The 13th IEEE International Conference on Data Science and Advanced Analytics (DSAA 2026)

Linear models with an $L_1$-norm penalty remain state-of-the-art for high-dimensional ($d > 1,000,000$) tasks, offering a straightforward method for solving real-world industry problems. Despite their widespread use in industry and utility, many $L_1$ solvers are not effective for general use, are prohibitively slow, and are ineffective in parallelization. This makes them difficult to train in an MLOps pipeline on large industry-scale corpora. In this work, we test several proposed ``state-of-the-art'' solutions from the literature and find that older methods are currently far superior for general use. We also identify several recommendations for academics to perform research that avoids erroneously overconfident results, which can prevent the transition to production use. Equally surprising, we find that a new and simple baseline, using LBFGS on a sub-gradient, is highly effective with minor tweaks, despite being dismissed in the literature for theoretical non-convergence. In practice, we find it is an easier-to-support and easier-to-scale method for production use.

0.37

Batched Pandora's Box

cs.DS cs.GT ·2026-09-03 ·Shaddin Dughmi, Yusuf Hakan Kalayci, Vasilis Livanos, Aditya Prasad
similarity 0.53
Abstract

Motivated by numerous parallelizable stochastic search problems, most notable and timely among them being LLM inference-time scaling, we propose and study batched versions of the Pandora's Box problem of Weitzman. In particular, boxes are opened in capacity-constrained batches, each batch has a setup cost, and all rewards in a batch are revealed together. We consider two different variants, motivated by different application environments: one where boxes are reusable (i.e., can provide multiple i.i.d.~samples) and another where they are not. For both variants we rule out most ``simple'' natural heuristics, and also formally prove NP-hardness of approximation in the traditional sense. We then relax the problem to allow bi-criteria approximations, with respect to both rewards and setup costs, where we exhibit constant approximation algorithms for both the reusable and non-reusable settings. This is obtained through a linear-programming relaxation of Pandora's Box problem, followed by randomized or Pipage rounding.

0.35

Convolution Sum-Product Queries

cs.DB ·2026-09-03 ·Kyle Deeds, Timo Camillo Merkl, Dan Suciu
similarity 0.52
Abstract

We study query evaluation for an extension of sum-product queries (SPQ) that allows atoms with linear combinations of variables (e.g. $A(2X+3Y-Z, Y+Z)$), which we call convolution sum-product queries (CSPQs). These queries arise in both practical settings (e.g. image processing workloads) and theoretical ones (e.g. the $(\min,+)$-convolution and $k$-SUM conjectures), and capture SPQs with added linear equality constraints. While prior work has considered the impact of linear in- and dis-equality constraints on query evaluation, the techniques developed in that setting are asymptotically sub-optimal for CSPQs. To address this, we describe several evaluation algorithms for CSPQs that leverage linear algebra techniques like rank analysis, quotient spaces, and variable substitution. First, we adapt Worst-Case Optimal Joins to CSPQs, achieving a runtime similar in spirit to that for conjunctive queries. Then, we extend the definition of tree decompositions (TDs) to CSPQs, and describe a factorized execution. In this extension, linear combinations are first-class citizens and play the same role as variables in traditional TDs. We define three width measures that bound the complexity of this execution with respect to the size of the domain values, of the active domain, and of the relation's support. Lastly, we show how these methods can be applied to arbitrary fields beyond the rationals.

0.24

Learning Early-to-Final Solution Consistency for MILP Acceleration

cs.AI ·2026-08-20 ·Guanlin Li, Chengrui Gao, Chenguang Wang, Haopu Shang, Zherong Zhang +4 more
similarity 0.52
Abstract

Mixed-Integer Linear Programming (MILP) is a fundamental problem class in operations research and combinatorial optimization, with broad applications to industrial decision-making. Owing to their NP-hardness, however, modern solvers may struggle to find high-quality solutions for challenging MILP instances within practical time limits. Recent learning-based approaches seek to accelerate MILP solving by directly predicting high-quality solutions from static instance-level features, such as variable-constraint bipartite graphs. Yet accurate solution prediction from instance features alone is difficult, and these methods largely overlook the information revealed during the solver's search process. In this paper, we find that solutions produced at the early search stage of MILP solvers, which are computationally cheap to obtain, are often structurally close to the solutions found after full-budget search. Motivated by this observation, we propose a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency: for each variable, we predict whether its early-stage assignment should persist in full-budget solutions. The predicted consistency naturally guides downstream search, for instance by fixing the assignments deemed consistent. At inference time, we further ensemble consistency predictions across multiple early-stage solutions to improve robustness. Experiments across four MILP benchmarks show our method improves prediction-guided search across diverse downstream pipelines. With Gurobi, our proposed method reduces the primal gap by 56.9% on average and closes it completely on combinatorial auction instances. Besides, we transferred the Gurobi-trained model zero-shot to SCIP without adaptation, achieving a 36.4% average gap reduction across benchmarks.

0.24

Approximation Algorithms for Product Query Optimization

cs.DS ·2026-11-18 ·Macéo Ottavy, Avijeet Ghosh, Pascal Koiran, Alantha Newman, François Schwarzentruber +2 more
theory similarity 0.52
Abstract

We study database query optimization for Cartesian products. This problem is equivalent to finding an optimal plan for multiplying non-negative integers. We call this problem multiplication ordering. We show that the problem has an FPTAS when the cost of a plan is the sum of all intermediate products; both in the case when the overall final product is counted and when it is not. We show that using the optimal solution to the well-known product partition problem does not always lead to an optimal plan, but we establish connections between the product partition and multiplication ordering problems. Finally, we prove that multiplication ordering is in PTIME (resp. \NP-complete) when integers are powers of a same base where the exponents are written in unary (resp. in binary).

0.37

DBRepro: Automated Database Synthesis via a Hybrid Constraint-Solving Approach for Reproducing Slow Queries

cs.DB cs.SE ·2026-08-28 ·Zhaoyang Zhang, Shuang Liu, Dengfeng Xu, Wei Lu, Jianquan Leng +2 more
top venue similarity 0.52
Abstract · 13 pages, 10 figures, and 3 tables. Accepted for publication in the Industry Showcase Track of the 41st IEEE/ACM International Conference on…

Slow queries frequently cause severe performance bottlenecks in database management systems. Diagnosing their root causes online risks exacerbating resource contention, while data privacy regulations often prohibit copying production data to test environments. Synthesizing a proxy database from non-intrusive metadata that induces the query optimizer to generate the same physical execution plans is therefore critical for offline diagnosis. High-fidelity reproduction requires preserving global statistical distributions while enforcing exact local cardinalities. Existing data-driven and workload-aware approaches cannot satisfy both requirements simultaneously. We present DBRepro, an automated end-to-end framework that formulates database generation as a constrained distribution synthesis problem. DBRepro initializes a global distribution from lightweight column statistics, extracts execution constraints from target queries, and progressively adjusts the distribution to satisfy these constraints while preserving the global distribution. Experiments on TPC-H and SSB show that DBRepro reduces cardinality error by up to 20.3% over a data-driven baseline while maintaining identical plan consistency. Compared with a workload-aware baseline, it reproduces 15% more consistent execution plans and reduces latency proportion error by 21.5%. We further validate DBRepro on a nearly 1 TB real-world dataset managed by KingbaseES, where it reproduces the execution performance of complex slow queries with high fidelity.

0.37