We present JoinBoost, a Python library that rewrites tree training algorithms over normalized databases into pure SQL. It is portable to any DBMS, offers performance competitive with specialized ML libraries, and scales with the underlying DBMS capabilities. JoinBoost extends prior work from both algorithmic and systems perspectives. Algorithmically, we support factorized gradient boosting, by updating the
Tree-based models-ranging from decision trees, random forests, and gradient boosting-are recursive space-partitioning algorithms for classification and regression [48]. They have shown exceptional effectiveness for tabular datasets, outperforming popular neural network models [31]. In fact, random forests and gradient boosting were rated the most popular model from 2019 to 2021 on Kaggle [8]. In response, the ML community has developed optimized tree-training libraries like LightGBM [42] and XGBoost [25], that offer user-friendly API, superior single-node performance, and compatibility with distributed frameworks like Dask [59] or Spark [70].
In practice, however, almost all tabular datasets are normalized and stored in a DBMS. Using ML libraries introduces performance, usability, and privacy drawbacks. First, the libraries expect a single (typically CSV) training dataset. Thus, a developer must denormalize the database into a "wide table" , materialize and export , and load it into the library. The join materialization cost is prohibitive for all but the simplest schemas and smallest databasesthe 1.2 IMDB dataset (Figure 3) is well over 1 when fully materialized due to N-to-N relationships. Second, managing the exported data as well as the separate execution frameworks adds considerable operational complexity and is error-prone [64,66]. Third, exporting sensitive data can raise privacy concerns [10].
Ideally, we would "move computation to the data" and train treebased models directly within the DBMS. This would let developers manage the entire data lifecycle-preparation, cleaning, analysis, and modeling-within a single DBMS, and benefit from the DBMSes' excellent security, performance, and scalability. To be broadly useful, we believe an initial In-DB solution should meet three criteria: (C1) be easily portable to any DBMS by translating ML algorithms into vanilla SQL queries, (C2) offer training performance comparable with the SOTA ML libraries (e.g., LightGBM), and (C3) scale to massive data warehouse sizes and complexity. Unfortunately, these criteria are often in tension. Common wisdom and prior results suggest that training tree models via SQL queries is portable but notoriously slow [32,68,70] as DBMSes do not employ modelspecific optimizations. However, specialized optimizations [25,42] or GPU acceleration [19,33,54] achieve competitive performance at the expense of portability to general DBMSes.
To optimize training over normalized schemas common in DBM-Ses, recent works in factorized ML [43,44,51,61] avoid materializing joins by treating ML as semi-ring aggregation queries over the join graph; the aggregations can then be pushed through the joins. This approach potentially provides DBMSes with an edge over conventional ML libraries that face significant expenses for join materialization and export during training. Thus, it is intriguing to investigate the potential of training tree models in DBMSes using vanilla SQL, with factorized ML optimizations.
Nevertheless, the current applicability of factorized ML to treebased models is restricted due to both algorithmic and systemrelated limitations. LMFAO [61] describes a factorized algorithm that is limited to decision trees, and does not support the widely used gradient boosting models. It rewrites the tree node split algorithm into a batch of group-by aggregations, and uses multi-query optimization to share work between the aggregations. Unfortunately, it does not support the residual updates needed for gradient boosting models. Even for single decision tree training, LMFAO fails to exploit considerable work-sharing between parent-child tree nodes. Finally, LMFAO lacks portability because its performance is tied to a compilation engine specially designed for its batch-wise query execution. In our experiments, despite using an off-the-shelf DBMS (DuckDB [57]), we train decision trees 1.9× faster than LMFAO.
To this end, we present JoinBoost, the first In-DB ML system designed for tree-based models (decision trees, random forests, and gradient boosting) that fulfill C1-3. Our main contribution lies in the system design and implementation: we study the feasibility of implementing JoinBoost as a Python library that translates ML algorithms into simple Select-Project-Join-Aggregation (SPJA) queries and employs factorized ML as pure query rewriting. Such design ensures portability (C1) and scalability (C3), as the translated SQL queries can run on any single node or cloud-based DBMS. Nonetheless, this design poses significant challenges. Algorithmically, previous factorized ML systems do not support gradient boosting. Furthermore, while earlier factorized ML systems have demonstrated good performance, their success is closely linked to specialized execution engines. It's unclear whether implementing factorized ML as pure query rewriting can enable existing DBMSes to deliver performance (C2) competitive to specialized ML libraries.
To support factorized gradient boosting, each iteration trains a decision tree on the residuals of the prior tree, requiring updates to in the denormalized relation ; however, is not materialized in factorized ML, and the view update generally requires ( ) [1]. To address this, for snowflake schema, we exploit 1-1 mapping between with the fact table , to update in directly. For the more complex galaxy schema, we found that despite challenges in directly updating in , the tree training only relies on aggregates of (e.g., count, sum) that could be updated efficiently. Our technique identifies addition-to-multiplication preserving, the key property to efficiently update aggregates, by rewriting residual updates over in into a join with an update relation . However, each boosting iteration generates a new update relation that may create cycles and doesn't scale with the number of iterations. To address this, we introduce Clustered Predicate Tree (CPT) that restricts the tree splits to attributes within the same cluster. This enables us to train gradient boosting on IMDB datasets, which was previously prohibitive due to the large size of (>1 ). To assess the viability of implementing factorized ML with pure SQL, we conduct extensive experiments on DuckDB and a popular commercial DBMS. Although columnar DBMS has the potential to compete with specialized ML libraries, we find residual updates as the major bottleneck for gradient boosting in current columnar DBMSes: Residual updates require sequential writes to all values in a column. However, this process is not efficient in existing DBMSes due to a combination of columnar compression, write-ahead-log (WAL), and concurrency control (CC); these are fundamental to DBMSes but unnecessary for gradient boosting. Disabling WAL, CC, and compression in existing DBMSes directly is challenging as they are deeply integrated into the codes. To match the performance of LightGBM, update performance must be similar to a parallelized write to an in-memory byte array.
To minimize DBMS overheads for residual updates (C2) without compromising portability (C1), we explore the approach to create a new column of residual values and adding it as a projection [67] on columnar DBMSes. We emulate this on DuckDB in two ways, with no or little modification to its internals. First, by leveraging DuckDB Pandas API [7], we store the fact table in a Pandas dataframe, use DuckDB for joins and aggregations, and update the residual by creating a new Pandas dataframe column. This results in a ∼15× improvement in updates, making gradient boosting competitive without modifying DuckDB. However, one drawback is a ∼1.6× slowdown in aggregations due to the DuckDB-Pandas interop overhead. To explore the full potential, we further modify DuckDB internals to support column swaps between DuckDB tables. We update residuals by swapping the existing residual column with the newly created one, making JoinBoost 1.1× faster than LightGBM. Lastly, we simulate column swap on a commercial DBMS, and see a potential 15× improvement. Such modifications, being both feasible (< 100 LOC on DuckDB) and effective, provide direction for other closed-source columnar DBMSes to support in-DB gradient boosting efficiently.
Finally, we apply optimizations to further improve JoinBoost performance. Algorithmically, we enhance prior batch optimization [61] by sharing intermediate results (materialized as tables in DBMSes) across batches (tree nodes), leading to a 3× improvement. System-wise, we leverage inter-query parallelism among SQL queries, accelerating the gradient boosting training by 28% and random forest by 35%. We conduct extensive experiments with JoinBoost on various DBMS backends (local and cloud), using datasets with varying feature numbers, sizes (TPC-DS with SF 10→1000), and join graph complexity (galaxy schemas), against SOTA ML libraries (LightGBM,XGBoost,Sklearn) and In-DB systems (LMFAO,MADLib). On a single node, JoinBoost trains a gradient boosting model with 100 trees 1.1× faster than LightGBM, and is 3× faster for random forests. On multiple nodes, JoinBoost outperforms the Dask [59] versions of LightGBM and XGBoost by >9×. JoinBoost easily scales in the # of features, join graph complexity, and dataset size (TPC-DS SF=1000 in Section 6.2), whereas LightGBM encounters memory limitations. Note: The paper is self-contained and references to appendices can be skipped, or can be found in the technical report [35].
and XGBoost [25], both of which are highly optimized and outperform others as per previous benchmarks [18]. According to Kaggle 2021 surveys [8], among all the commonly used ML libraries, XGBoost and LightGBM are ranked 4 ℎ and 6 ℎ respectively for popularity (while all the top 3 also support Tree-based ML). However, none of them apply factorized ML for normalized datasets. In-DB ML systems. Most in-DB ML works [28,32,68] focus on extending DBMSes (e.g., PostgreSQL for MADLib) to support linear algebra using UDFs and user-defined types. However, these are not needed for tree-based models that only rely on simple aggregations.
Other work optimizes ML training by leveraging specialized features (distributed execution [20,38,39,45,70] or GPU acceleration [19,33,46,54]) of a specific DBMS. Although we focus on optimizing the single-node CPU setting via SQL rewrites, JoinBoost can run on any DBMS and benefit from its optimizer and executor. For instance, Section 6.2 scales decision tree training on TPC-DS SF=1000 using a cloud DBMS. We leave further DBMS-, data-, and model-specific optimizations to future work.
In practice, cloud vendors (Azure [11], Redshift [14], BigQuery [47], Snowflake [13]) offer SQL syntax to train tree models. Under the covers, however, they still materialize and export join results to an external library (LightGBM or XGBoost). Thus, we do not consider them in-DB ML from a performance or portability standpoint. Factorized ML systems. Factorized ML is optimized to train models over normalized databases. It translates ML models as aggregations over an appropriately designed semi-ring, and pushes aggregations through joins to achieve asymptotically lower time complexity. They support many popular models (ridge regression [61], SVM [43], factorization machine [61]), and approximate others (kmeans [27], GLM [37]). Of these, only LMFAO [61] supports decision trees, albeit in a limited way (see Section 6.4). Further, most factorized ML works build specialized query optimizers and executors from scratch, which hinders portability (of the systems and performance wins) to existing DBMSes. JoinBoost extends factorized ML to tree models via vanilla SQL queries, and shows competitive performance with LightGBM.
We provide the background of factorized tree-based models.
This section provides an overview of annotated relations and message passing fundamental to factorized query execution [17,52]. Data Model. We use the traditional relational data model with the following notations: Given relation , let uppercase be an attribute, ( ) be its domain, = [ 1 , • • • , ] be its schema, ∈ as a tuple of , and [ ] be tuple 's value of attribute . For clarity, we include the schema in the square bracket followed by the relation
Annotated Relations. The annotated relational model [30,40,50] maps each ∈ to a commutative semi-ring ( , ⊕, ⊗, 0, 1), where is a set, ⊕ and ⊗ are commutative binary operators closed over , and 0/1 are the zero/unit elements. These annotations form the basis of provenance semi-rings [30], and are amenable query optimizations based on algebraic manipulation. Different semi-ring definitions support different aggregation functions, ranging from standard statistical functions to ML models. For instance, the natural numbers semi-ring (N, +, ×, 0, 1) allows for integer addition and multiplication, and supports the COUNT aggregate. For an annotated relation , let ( ) denote tuple 's annotation. Semi-ring Aggregation Query. Semi-ring aggregation queries can now be re-expressed over annotated relations by translating group-by (general projection) and join operations respectively into + and × operations over the semi-ring annotations:
(1) Each group-by result annotation in A sums all the annotations in its input group. (2) In , the annotation of each join result is the product of annotations from corresponding tuples in and . Aggregation Pushdown. The key optimization in factorized query execution [17,62] is to distribute aggregations (additions) through joins (multiplications). Consider ( [ , ] [ , ]
[ , ]). The naive execution first materializes the join and then computes the aggregation. This costs ( 3 ) where is each relation's cardinality. An alternative evaluation could apply aggregation (addition) to before joining (multiplication) with , aggregate again before joining with , and then apply a final aggregation. The largest intermediate result, and thus the join complexity, is now ( ).
Message Passing. Given a join graph, the above optimization can be viewed as Message Passing [55]. While Message Passing supports general SPJA queries [36], it is sufficient for tree models to restrict ourselves to SPJA queries with zero ( ) or one ( ) group-by attribute. Message passing operates over a tree that spans the join graph. For the root, we can pick any relation (taking cost models into account) that contains the grouping attribute. Then we direct all the edges of the join graph toward the root to form a tree. Starting from the leaf, we send messages along its path to the root. Each message is computed as: (1) Join the relation with all incoming messages from children relations, if any. This blocks until all children have emitted messages. Then (2) let A be the attributes in the current relation that are also contained in the remaining relations in the path to the root. Compute A over the previous join result, and emit the result to the parent relation.
[ , ]) along the join graph: --. If we choose T as the root, then the directed join graph is → → and the messages are:
Once the root receives and joins with all messages, it performs absorption, which simply applies the final group-by: ( → [ , ]). In some cases, the aggregate result is already part of the semi-ring (e.g., COUNT and the natural numbers semi-ring); in other cases, such as tree-based models, the semi-ring decomposes the training metric into their constituent statistics, so we combine them in the final annotation to restore the metric (see next section).
(1, 0, ..., = 1, ..., 0)
In this section, we describe the traditional tree-based models. The algorithms are based on CART [22], and its extensions (e.g., bagging and boosting) follow standard ML textbooks [48]. Decision Tree. Decision tree maps (predicts) target variable from a set of features X. Internally, it maintains a tree structure of selection predicates, with each edge containing a predicate and selecting data based on the conjunction of predicates along the path from the root. Leaf nodes associate with a prediction value ∈ ( ). The selection predicates by leaves are mutually exclusive and collectively exhaustive in (X). For ∈ (X), decision tree predicts by traversing the edges where meets the edge predicate until a leaf is reached, then outputs its prediction .
Training a Decision Tree over relation with features X and target variable where X ∪ ⊆ involves recursively splitting to minimize a criterion (•). For regression, the popular criterion is Variance for root mean square error ( ), while Gini Impurity, Entropy, and Chi-Square are common for classification. Numerical attribute splits use inequality ( > , ¯ ≤ ), and categorical attribute splits use equality ( = , ¯ ≠ ) or set-based ( ∈ , ¯ ∉ ) predicates. Given the criteria (•) and split , the reduction of criteria after the split is ( ) -( ( ( )) + ( ¯( ))). Tree growth could be depth-wise or best-first [65]. Depth-wise growth splits the tree node with the least depth, and best-first growth splits the tree node greedily with the largest criteria reduction. Finally, each leaf prediction is the average for regression or mode for classification.
Algorithm 1 presents the training algorithm. Given relation (with encoded in annotations), features X, and the maximum number of leaves, the algorithm iteratively calls GetBestSplit to find the best next split (L3,8,9). GetBestSplit iterates through all features, evaluates its best split (based on reduction of criteria), and returns the best split across all features (L11-16). For best-first growth, a priority queue (L2) sorts leaf nodes descendingly based on reduction of criteria. In each iteration, the algorithm splits the best leaf node (L7), creating two tree nodes that partition the parent node. It then finds the best split for each new node and pushes them to the queue (L8,9). Training ends when the number of leaves reaches the maximum (L5). Leaf node predictions are computed, and the tree is returned (L10). During training, evaluating the best split (L14) is the most computationally expensive. Bagging and Boosting. Big, deep decision trees risk overfitting. Ensemble methods combine multiple smaller or shallower decision trees to create a more robust model. Popular tree-based ensemble models include random forests [21] (bagging) and gradient boosting [29] (boosting). Random forests parallelly train decision trees on samples of and features and aggregate their predictions (e.g., Algorithm 1: Decision tree training algorithm. L14 (underlined) is the most computationally expensive.
1 Function DecisionTree( , X, )
ℎ( , , , , ); 5 while ++ < do 6 // get the best split with the highest among leaves; 7 _, , , , ← . (); 8
. ℎ(GetBestSplit( , X, , ));
We now introduce factorized decision trees over joins. The training process follows Algorithm 1, but we optimize the computation of criteria reduction (L14), the most computationally intensive part, by avoiding join materialization. We consider a database with a set of relations R = { 1 , 2 , ..., }, and aim to train a decision tree over = 1 2 ... with a set of features X and target variable . Let be the relation that contains (or pick one if is in many relations as a join key). For simplicity, we will assume natural join, set semantics, and the Variance split criterion; Appendix B describes extensions to theta and outer joins, bag semantics, and formulas for classification semi-rings. Factorized learning avoids materializing by expressing the criterion as semi-ring aggregation queries, and applying aggregation pushdown over join. We first describe semiring annotations for trees and then the computation of criterion. Tree Semi-rings. We now illustrate how to use variance semiring (Table 1) to compute the Variance for regression. Each semiring defines a (•) function [50] that annotates a base tuple with its appropriate semi-ring element. Variance semi-ring lifts ∈ with (1, [ ], [ ] 2 ), and from the remaining relations with the 1 element (1, 0, 0). During message passing, the annotations are combined via ⊕ and ⊗ as defined in Table 1. The aggregated semi-ring ( ) then forms a 3-tuple ( , , ) that denotes the count, sum of , and the sum of squares of . The variance statistic can be derived from this aggregated semi-ring as = -foot_1 / . Thus, any filter aggregation query over the join graph can be expressed using message passing and lightweight post-processing. 1a with variance semi-ring, join graph -and target variable = . To compute the variance over , the naive solution is to materialize (Figure 1b), then compute the variance (=4) over . Instead, we compute ( , , ) = ( ) = (8, 16, 36) and = -2 / =4.
To find the best split, we similarly use variance semi-ring compute the reduction in variance (Appendix A). Message Caching. Training a decision stump requires computing the set of aggregation queries grouped by each feature: { ( )| ∈ X}. Executing each independently via message passing is wasteful due to reusable messages. Consider the example in Figure 1:
Example 2. Let X = { , }, and suppose we first aggregate on (Figure 1c). We choose S as the message passing root because it contains ; we then pass messages 1 from R to S and 2 from T to S, and absorb the messages into . We then aggregate on (Figure 1d). We choose T as the message passing root, pass 1 from R to S, 3 from S to T, and absorb into T. The two queries can reuse 1 .
Recent work [36] shows that a simple caching scheme that materializes all messages between relations in the join graph (in both directions) is effective in various analytical workloads. The factorized learning system LMFAO [61] also optimizes batch queries for splitting a single decision tree node. For decision trees, where each query groups by ≤1 feature, its optimizations are equivalent to this simple caching scheme. However, LMFAO optimizes a single decision tree node's batch of queries, missing work-sharing across tree nodes and not supporting residual updates for boosting.
This section delves into the algorithms for factorized gradient boosting, which iteratively trains the next tree to predict the residuals from preceding trees. Recall from Section 3.2 that, each leaf in the decision tree is associated with a predicate . and prediction . . We aim to update, for each leaf , the target variable of ∈ . ( ) to the residual [E]= [ ]-. . The fundamental challenge is to train decision tree over the updated in without materializing . One tempting approach is to treat this as a view update problem: we update in the view, translate it into updates over base relations, re-lift the updated base relations, and train the next factorized decision tree. However, view updates are susceptible to "side-effects" [1]: for ∈ , = [ ] can be duplicated in due to 1-N (or M-N) joins. If one duplicate is updated to a new value ′ , updating [ ] = ′ in would inadvertently cause other duplicates to be updated as well (as "side-effects"). To address it, new tuples are created in base relations for new mappings. These "side-effects" are particularly problematic for "residual updates", as the full column in is updated, requiring (| |) new tuples. We address these issues for snowflake (a single fact table) and galaxy schemas (multiple fact tables)-arguably the most common database schema forms. Snowflake schemas exhibit a 1-to-1 relationship between the fact table and , and we exploit this to efficiently updates over . We then discuss the system challenges when performing full-column updates. These techniques do not apply to galaxy schemas due to the M-N relationships between the fact tables. While directly updating in remains challenging, we identify the addition-over-multiplication preserving property that allows us to directly update semi-ring aggregates derived from updated , and use this to efficiently support the popular .
Snowflake schemas have one fact table and N-to-1 paths along the dimension tables; this means that is 1-1 with 1 and we can directly update . Let us first assume that is in (i.e., = ). The main challenge is to translate a leaf 's predicate . , which may refer to dimension attributes, into one over . We do so by translating . as semi-join predicates 2 over . Given join path -1 -... -, and ( ), we "move" the predicate to be ′ ( -1 ):
where ′ is over the join keys J = -1 ∩ . Note that doesn't have to be equality-based but can be of any arbitrary type: is applied to J ( ( )) to identify the matching join keys for the semi-join. If is in a dimension table (i.e., ≠ ), we join the relations along the path from to and project all attributes in along with . This reduces to the first case above. System Challenge: Since | | = | |, factorized gradient boosting does not offer an asymptotic advantage over specialized ML libraries. Theoretically, if the performance is comparable, it could still benefit from the parallelization, scaling, and administrative features of DBMSes. However, in practice, we find that bulk updates to . are a major bottleneck (Section 5.3.2) for existing DBMSes. The next section dives into these system challenges, and explores system design, logical, and physical optimizations to address them.
Galaxy schemas model M-N relationships between multiple fact tables. They are prevalent in enterprise settings [60]; the recent "semantic layers" trend [5,12,24,34] (pre-defined denormalized views) have made analysis and ML over galaxy schemas more accessible. However, galaxy schemas induce the 1-N relationship between and that causes side-effects [1] during residual updates. We observe that individual values are not needed for trainingthe split criteria only refers to semi-ring aggregates over the updated values (Section 3.3), and can potentially be updated efficiently. For instance, for a leaf with original aggregates = 1, = over . ( ), we can directly update the sum of residuals as ( -. ) = -. = -× . , without referencing individual values. Unfortunately, this approach is not efficient for arbitrary split criteria. To review, factorized ML maps (via (•)) in the real number semi-ring R(R, +, ×, 0, 1) (for base relation) to another semi-ring S(S, ⊕, ⊗, 0 ′ , 1 ′ ) (e.g., variance semi-ring for ), and computes ( ) over with aggregation pushdown. To directly update aggregates given leaf , we want to find a function :(S, R) → S, such that takes the original aggregates ( ) (without referencing individual ) and additive inverse of prediction . 3 as input, and outputs updated aggregates: ( ( ), -. ) = ( -. ). To maintain our asymptotic benefits, both and semi-ring operation/annotation should be of constant time/size. Such does not exist for all semi-rings. For example, mean absolute error ( ) relies on the count and sum of signs: 1, ( ). The naive semi-ring would track ( ) = ( 1, ( )). However, doesn't exist because given the leaf , ( -. ) cannot be solely decided by 1, ( ), -. , as it depends on individual -. . A naive solution uses a semi-ring that collects all values, but its annotation size will be (| |) and defeats the purpose of factorization. To this end, we identify a sufficient property for constant sized semi-ring S to construct : Definition 1. Addition-to-Multiplication Preserving. Given two semi-rings R(R, +, ×, 0, 1), S(S, ⊕, ⊗, 0 ′ , 1 ′ ), a lift function (•) : R→S is addition-to-multiplication preserving from R to S if
for any 1 , 2 ∈ .
3 Additive inverse of . exists because R is also a ring.
Based on the property, we can construct as:
It is easy to verify that, the variance semi-ring (and lift) in Table 1 satisfies the property:
). In contrast, there is no known and constant-sized semi-ring with this property for . A possible future direction using polynomial approximations [37] of the semi-ring aggregates. To keep the text concrete, the subsequent text will refer to the criteria.
For decision tree and each of its leaf , we apply the corresponding that multiplies aggregates over . ( ) with (-. ). We model this as an Update Relation joins with . is constructed as follows: let A be the set of attributes referenced by . for any leaf , and be the projection A ( ), along with a columnof the additive inverse of leaf prediction (unique as leaf predicates are non-overlapping). Naively, the next boosting lifts the residual using -(
) 4 , where has to be materialized. Instead, we rewrite this into ( ) -( ):
Unfortunately, can introduce cycles in the join graph over time (e.g., Figure 2c shows cycle → → ); whereas Message Passing requires acyclic join graphs. Standard hypertree decomposition [17,41] removes cycles by joining the relations in a cycle, materializing their join result ′ (e.g.,
), and replacing these relations in the join graph with ′ . However, as the number of trees in model increases, the number of referenced attributes is likely to span the entire join graph-| | will thus converge to | |.
To address this, we propose Clustered Predicate Tree (CPT): each boosted tree restricts split on features that can be pushed to the same fact table. To do so, we cluster relations such that within each cluster, a single fact table maintains N-to-1 relationships with all other relations. Predicates in this cluster can be rewritten as semi-joins to the same fact table (Section 4.1) and won't create cycles [17]. During training, while the root decision tree node can split on any feature, subsequent splits are confined to attributes within the same cluster. Although this might affect model accuracy, 4 When is applied to a column , we denote it as . . Each tuple in has the same annotation as the materialized lifted on E. Therefore, the materialization of can be avoided.
Figure 3: Clusters for IMDB dataset. Each cluster is enclosed by dotted lines and its fact table is filled.
it allows efficient residual updates over join graphs, which would otherwise be untrainable using existing techniques.
Example 4. Figure 3 shows the join graph of IMDB datasets [2], which was previously prohibitive to train gradient boosting due to the large join size ( is >1 ). The five clusters are enclosed by dotted lines and the cluster's fact table is highlighted. If the current tree initially splits on Person's age (in Person Info), the rest of the tree can only split on attributes in Person or Person Info.
We now present the system overview and optimizations.
As described in Section 1, our design goals are portability, performance, and scalability. We evaluate performance and scalability in the experiments, so focus on portability below. Portability: Our design deviates from prior factorized ML works [25,42,44,61], which build (fast) custom execution engines. In contrast, JoinBoost is implemented as a Python library that transparently generates SQL queries to the user's DBMS backend (Figure 4). JoinBoost internally translates the ML algorithms into CREATE TABLE and SELECT SQL queries. Compared to in-DB systems like MADLib [32], JoinBoost generates pure SQL and does not require user-defined types or functions. This enables portability (criteria C2): JoinBoost runs on embedded databases, single-node databases, cloud data warehouses, and even Pandas and R dataframes [7].
The compiler fully supports decision trees, random forests, and gradient boosting with all learning parameters that LightGBM supports. Currently, regression with objective supports galaxy schema with Clustered Predicate Trees; other objectives (e.g., , ℎ , ...) require snowflake schema. We are actively extending capabilities to support pruning, dropout, and early stopping, which build on the techniques in the preceding sections.
One usability challenge is that JoinBoost end users are typically domain scientists who lack expertise in data access and schema, commonly handled by data engineers. While addressing is beyond the scope, we highlight the recent trend of "semantic layer" [5,6,12,24] as a means to bridge the knowledge gap. In the "semantic layer, " data engineers employ SQL-based recipes to transform and preprocess raw data into tables containing meaningful attributes to domain scientists, and can be queried by JoinBoost using SQL. Safety: Training shall never modify user data. To achieve that, JoinBoost creates temporary tables in a specified namespace or with a unique prefix. By default, JoinBoost deletes these tables after training, but users can keep them for provenance or debugging.
The ML Compiler runs the ML logics (Algorithm 1) to train treebased models in Python and translates the most computational intensive L14, which identifies the best split across features for tree nodes, into SQL queries to be executed by DBMS. At this stage, the compiler treats the join graph as a single "wide" table, with the SQL query operating on this table, and factorization is applied in a later step. After training, it returns a reference to the trained model. The Semi-ring Library stores semi-ring definitions and translates math expressions in the compiler-generated queries (×, +,
) into SQL aggregation functions.
( ) creates a copy of a base relation that contains an additional attribute for each component in the semi-ring (e.g., c, s, q in the variance semi-ring). This also ensures that any update in-place will not modify user data. In addition to the variance (for regression) and the class count (for classification) semi-rings, JoinBoost implements semi-rings for a wide range of popular objectives; it supports for snowflake and galaxy schemas, and mae, huber loss, fair loss, log loss, softmax and more for snowflake schemas (see Appendix B for full list).
The Factorizer decomposes each aggregation query into message passing and absorption queries. It also materializes each message as a database table, and re-uses them when possible. After choosing a node split, the factorizer keeps messages that can be reused in descendent nodes (Section 5.5.1) and drops the rest.
Finally, the Connector takes our internal SQL representation, and translates them into the appropriate SQL string or dataframe API calls. Although DBMSes are notorious for incompatible SQL variants, JoinBoost only uses a subset of SQL that is generally consistent across vendors. For instance, it generates standard nonnested SPJA queries with simple algebra expressions.
Although correct, the residual update technique in Section 4 is still expensive to implement naively. For simplicity, if we assume a single join attribute between the fact table and update table , and the variance semiring, the SQL query would be:
where , , are semiring components, and the remaining columns in are copied over (shown as . . . ). Unfortunately, this is >50× slower than LightGBM's residual update procedure (see experiments below), because can potentially be as large as the materialized .
To this end, we present an optimization for snowflake and galaxy schemas that completely avoids materializing as well as .
We directly UPDATE 's semiring annotations. Let us start with a snowflake schema. Each decision tree leaf logically corresponds to a separate join graph containing a set of messages (Figure 6), with . as its predicate and . as its prediction. Using the semi-join optimization (Section 4), we translate predicates over (e.g., . ) into semi-joins between and relevant incoming messages M. A message ∈ M is relevant if it is along a join path from a relation containing an attribute in . to . For each leaf node , we execute the following query where . is the join attribute with its relevant incoming message : In some databases, updates in place can be very slow. Thus an alternative is to create a new fact table with the updated semi-ring annotations. Let be the ℎ leaf in the decision tree, and , , , be the ℎ message and its join attribute with in 's join graph:
TABLE F_updated AS SELECT CASE WHEN F.a_ij IN (SELECT a_ij FROM m_ij) AND ... THEN s -l_j.p*c WHEN ... // Other leaves END AS s, ... // other semi-ring components ... // copy other attributes in F FROM F
The same ideas apply to galaxy schemas, where corresponds to the fact table of the current tree's cluster. Further, we show in the technical report [35] that and are not necessary to materialize; thus only is needed for the variance semi-ring.
When should we perform in-place updates as compared to creating new tables? On which DBMSes? We now report a microbenchmark to understand the performance tradeoffs, and use them to motivate a new optimization. We used an Azure VM, with 16 cores, 128 GB memory, and an SSD. Workloads. We create a synthetic fact table ( , , 1 , ..., ) with 100 rows to simulate residual updates in a decision tree with 8 leaves. is the semi-ring column to update, ∈ [1,10 ] is the join key, and are simply extra columns that would need to be duplicated in a new table. For the ℎ leaf node, its prediction is a random float, and we construct its semi-join message ( ) to contain all values in (1250 × ( -1), 1250 × ]. Methods. We evaluate three approaches. Naive materializes Update Relation , then re-create fact table: ′ = A as discussed in Section 4. SET and CREATE use the update-in-place and create table optimizations in the preceding subsubsection. CREATE-k denotes the number of extra columns in , where ∈ {0, 5, 10}; we set = 0 for Naive, and does not affect SET. DBMSes. We evaluate two systems. DBMS-X is a popular commercial RDBMS that supports both column-oriented (X-col) and roworiented (X-row) storage and query processing. DBMS-X is diskbased only, and we set the isolation and recovery to the lowest level (read uncommitted and minimum logging). DuckDB [57] is a popular embedded column-oriented OLAP DBMS and is highly performant [9]. DuckDB has disk-based (D-disk) and memory-based (D-mem) modes. As a reference, we also use LightGBM to train 1 iteration of gradient Boosting with the same training settings, and report residual update time. Experiment Results. Figure 5 shows that Naive incurs high materialization and join costs. CREATE is ∼ 2× faster for DBMS-X and ∼ 4× faster for DuckDB, but its cost grows linearly with . SET mainly depends on the DBMS-it is prohibitive for DBMS-X, but more efficient than CREATE when > 5 for DuckDB. All DBMS approaches take >3 for updating residuals. In contrast, LightGBM stores the target variable in a C++ array and performs parallel writes; its residual update takes ∼0.2 . These poor results are due to four main factors.
• Compression: CREATE in X-col incurs high compression costs: the database is 1 in X-col as compared to 2.6 for DuckDB. This also penalizes SET due to decompression.
• Write-ahead Log (WAL) introduces costly disk writes.
• Concurrency Control (CC): In-memory DuckDB doesn't use WAL, but incurs MVCC [49] overheads, including versioning, and logging for undo and validation. • Implementation: DuckDB's update is currently single-threaded.
Logical rewrites are effective but still much slower than LightGBM's residual updates, even when existing CC mechanisms are lowered. We observe that JoinBoost does not need durability and concurrency control, since it writes to private tables, performs applicationlevel concurrency control (Section 5.5), and can simply re-run upon failure. Compression is also unnecessary for the heavily updated columns. Unfortunately, WAL, CC, and compression are deeply integrated into DBMS designs, and nontrivial to fully disable.
We note that columnar engines are well suited to avoid these costs by adding the new residual column as a projection [67], but is not generally supported (e.g., by DuckDB, DBMS-X). We thus evaluate its benefits using three methods: one that uses DuckDB's existing APIs to swap columns in Pandas dataframe, one that adds "column swapping" to DuckDB, and one that simulates it in DBMS-X.
The first solution, called DP (DuckDB + Pandas), uses the existing DuckDB Relational API [7] to directly access Pandas dataframes [53] -an in-memory data structure that stores columns in contiguous uncompressed C arrays. Internally, it uses a custom scan operator for Pandas's matrix format, and DuckDB's executor for the rest of the query. We store the fact table as a dataframe, and the remaining tables in DuckDB, and join them via the relational API during training. For residual update, we submit a query over Pandas and native relations to compute the semi-ring annotations for the updated residuals, and store the result in a NumPy array. Then using Pandas, we replace the old column in with the new NumPy array (a pointer swap). This is fast because it avoids WAL or CC overhead, and reduces residual updates to 0.72 -competitive with LightGBM (Figure 5). The drawback is that the scan overhead slows down the join-aggregation query, and increases training time by ∼1.6× as compared to querying only native relations (Section 6.3).
The second approach, D-Swap, modifies DuckDB internals slightly (<100 LOC) to support pointer-based column swapping between two DuckDB tables. DuckDB stores tables in row groups, with each group containing pointers to the column data. D-Swap iterates through the row groups of the two relations and swaps the column pointers. Such column swap is a schema-level modification, so it is very fast and side-steps decompression, CC, and WAL overheads. It achieves similar residual update performance to DP (Figure 5) without degrading aggregations (Section 6.3).
Finally, to extend beyond DuckDB, we also simulate column swapping's impact on DBMS-X in Section 6.3, and see a potential 15× improvement. We believe that implementing such column swap in closed-source DBMSes is both feasible and effective for residual updates. We encourage columnar DBMS developers to incorporate this operation for efficient In-DB gradient boosting.
We implement various optimizations and features in JoinBoost for performance and usability. Due to space limit, we only discuss the most critical ones here, while the rest can be found in Appendix D.
Previous factorized ML algorithms [44,61] rely on batch optimization of aggregation queries, suitable for models with closed-form solutions (e.g., ridge regression [61]). However, tree-based model training is iterative: queries for child nodes depend on the parent node's split, making batching ahead impossible. Consequently, previous algorithms either miss work-sharing opportunities between tree nodes or batch all possible splits, which is impractical due to exponential growth in tree depth. Our key observation is that messages as intermediate results can also be shared among tree nodes. Consider the example: Example 6. Following Example 2, suppose the best root split is >1 . The split applies and ¬ to (as it contains ), creating two leaf nodes with relations: ( ) and ¬ ( ). Then, for each leaf node, we compute the batch of aggregation queries and identify the next split through Message Passing. As shown in Figure 6, messages (dotted blue) along the path → → are the same for both leaf and root nodes. We only need to recompute message → in each tree leaf, skipping → as 's attributes aren't used in this model.
In general, after a split on , all messages along the path to can be re-used. This is orthogonal to prior batch optimization work [61] as we can cache and reuse messages after batching for future nodes, further improving batch optimization by >3× (Section 6.4). data and features, and aggregates (e.g., averages) their predictions during inference. Feature sampling can be easily implemented by using a random subset of X ′ ⊆X features for Algorithm 1. The main challenge is efficiently sampling over non-materialized : Naively sampling each relation is ( 1) not uniform and independent, and (2) may produce non-joinable and hence empty samples. To address these, we use ancestral sampling [23,63,71] over join. Minor Optimizations. First, we coalesce the messages for COUNT query with those for the tree criterion. For instance, the element in Variance Semi-ring captures the COUNT statistics. Second, for snowflake schemas where the fact table has N-to-1 relationships with the rest of the tables, we sample the fact table directly [69].
Parallelism is widely used in ML libraries like LightGBM, which implements parallelized sorting, aggregation, residual updates, and split candidate evaluations. For JoinBoost, most DBMSes offer intra-query parallelism, but there can be diminishing returns for individual queries or operations. Thus, JoinBoost also aggressively parallelizes across trees, leaf nodes, candidate splits, and messages. However, there are dependencies between these queries: a message's query relies on upstream messages, absorption depends on incoming messages, tree nodes depend on ancestor node queries, and gradient boosting trees rely on preceding trees. To handle this, JoinBoost employs a simple scheduler. Each query tracks its dependent queries, and when finishes, it sets the ready bit for these dependencies. If all dependencies for a query are set, it's added to a FIFO run queue. Empirically, 4 threads work best for intra-query parallelism, while the rest are used for inter-query parallelism. This reduces gradient boosting training time by 28% and random forest by 35% (Appendix C).
We focus on the fastest alternative: ML libraries (XGBoost, LightGBM, Sklearn). We start with a single-node setting, and then evaluate scalability to the number of features, types of joins, and database size on multiple nodes. Finally, we compare with factorized (LMFAO) and non-factorized (MADLib) in-DB ML techniques. Datasets. We primarily report results using the Favorita [3] dataset used in prior factorized ML work [61,62] (Figure 7). Sales is the fact table (2.7 , 80M rows), and has N-to-1 relationships with the other dimensions (<2 each). There are 13 features. We report TPC-DS results for scalability experiments and use IMDB for galaxy schema experiments; additional TPC-H/DS results are in the Appendix C. Preprocess. Although Favorita and TPC-H/DS are standard benchmarks in prior factorized learning evaluations [61], their features are non-predictive and lead to highly unbalanced trees. This artificially favors JoinBoost since all but one leaf node in the decision tree would contain very few records, and thus take negligible training time-the performance differences with other systems are fully dominated by join materialization. To ensure balanced trees and fair comparison, we impute one feature attribute in each of the 5 dimension tables with random integers drawn from [1,1000]. Then we impute the target variable as sum of transformed features 5 . Finally, we dictionary encode strings into 32-bit unsigned integers [16,58] to avoid parsing errors in ML libraries like LightGBM. Models. We evaluate decision tree, random forest, and gradient boosting. JoinBoost is intended to complement other DBMS workloads, so all experiments start with data persistent on disk but not in memory. We assume by default that data are already persisted in the disk-based DBMSes (DBMS-X and disk-based DuckDB). We report the end-to-end training time for decision tree of max depth 10, and vary the number of trees (iterations) in the random forest and gradient boosting. For JoinBoost, the main cost is from DBMSes, and the Python codes introduce negligible (<0.1 ) overhead. Methods. We evaluate JoinBoost with different DBMS backends. DBMS-X (X-col and X-row for column and row-oriented storage and execution engines) and DuckDB-disk (D-disk) are disk-based and directly execute queries on the base DBMS, whereas memory-based DuckDB (D-mem) first loads the DBMS from disk. DP refers to the diskbased DuckDB backend using Pandas updates through the DuckDB's relational API, and D-Swap refers to the modified memory-based DuckDB for efficient residual updates (Section 5.4). By default, we use D-Swap as the backend as it has the best performance (Section 6.3). ML libraries 6 (LightGBM, XGBoost, Sklearn) expect a single CSV as input, so incur the cost to materialize and export the join result (∼7 for Favorita), load the CSV, and train the model. DuckDB joins and exports the data faster than DBMS-X, so we report its numbers. Hardware: We use Azure VM: 16 cores, 128 GB memory, and SSD.
We compare with SOTA ML libraries for training tree-based models (LightGBM [42], XGBoost [25] and Sklearn [56]). Sklearn implements the standard and histogram-based gradient boosting with algorithms similar to LightGBM, so we report both implementations. We set the number of bins to 1000 for LightGBM and XGBoost, and 255 for Sklearn (its limit). By default, we train gradient boosting and random forest with best-first growth, with a maximum of 8 leaves per tree. The gradient boosting learning rate is 0.1. The random forest data sampling rate without replacement is 10%, and feature sampling rate is 80%. We report up to 100 iterations. The 0 ℎ iteration reports the join materialization, export, and load costs.
Figure 8a shows random forest results. JoinBoost is ∼3× faster than LightGBM by avoiding materialization and export costs (dotted black line), and loading costs; it also parallelizes across trees. In fact, JoinBoost finishes 100 iterations before the export is done. Sklearn also parallelizes across trees, but is so slow that we terminate after 32 iterations. The final model error (
) is nearly identical (∼2350) for JoinBoost, LightGBM and XGBoost.
Figure 8b shows gradient boosting results. JoinBoost is ∼1.1× faster than LightGBM, and is ∼1.2× faster than XGBoost by avoiding materialization and export costs. Figure 8c shows the model . JoinBoost and LightGBM have equivalent as both employ the same algorithm, while the final is similar across all. Note that 5 Favorita applies: = ( ) + ( ) -10 -10 + 2 6 Python version LightGBM and XGBoost have memory issues [4] so we use CLI version. the models begin to converge ∼ 60 iterations; JoinBoost converges by the time LightGBM and XGBoost have loaded their data.
To interpret the JoinBoost cost, we zoom in on the 1 iteration of JoinBoost gradient boosting in Figure 9, which displays the total number of queries for passing messages (orange) and finding the best split (blue) along with a histogram for the query execution time distribution. With a tree of 8 leaves and 15 nodes, there are 270 = 15 × 18 (number of features) queries for feature split, and 75 = 15 × 5 (number of join edges) queries for message passing, as expected. All feature split queries are efficient, taking < 10 . The performance bottlenecks are the queries passing messages from the fact table, which require join-aggregation, result materialization, and take > 200 . This highlights the importance of aggressively reusing messages across nodes (Section 5.5.1).
We now study scalability to DB size, and join complexity. Single-node Scalability. Favorita is a fixed dataset, so we use TPC-DS (145 features) to scale the database ( ∈ [10, 25]). Figure 10 shows that both systems scale linearly, but JoinBoost has a lower slope (∼10× lower at 10 ℎ iteration, and ∼2× lower at 50 ℎ ). LightGBM runs out of memory at = 25. Multi-node Scalability. We use the Dask version [59] of LightGBM and XGBoost, and Dask-SQL for JoinBoost to train gradient boosting on multiple machines for 10 iterations on TPC-DS ∈[30, 40]. We use 4 n1-highmem-16 GCP instances (16 vCPUs, 104 GB RAM each) with data replicated across all instances; at least 4 machines are needed for LightGBM to run on
= 30 due to large join sizes and inefficient memory usage [4]. Figure 11 (a) shows that, on 4 machines, all systems scale linearly , but JoinBoost is >9× faster with a ∼5× lower slope. For =40, LightGBM runs out of memory even on 4 machines. In contrast, Figure 11 (b) shows that for =40, JoinBoost can train on a single machine, outperforms XGBoost (using 4 machines), and speeds up with more machines. Cloud-warehouse Scalability. We use a cloud data warehouse DW-X train a decision tree with max depth 3 over TPC-DS SF=1000, and study multi-machine scalability. Each machine has 74 cores, 300GB of memory, and SSDs. We replicate dimensional tables across the machines, and hash-partition the fact table. Figure 12 shows that 2 machines introduce a shu e stage that slows training, and increasing to 4 (6) machines reduces training by 10% (25%). Galaxy Schemas. Galaxy schemas have N-to-N relationships that are prohibitive to materialize. We use clustered predicate trees (Section 4.2.2) to train gradient boosting on the IMDB dataset (Figure 3).
and the total DB is 1.2 . JoinBoost scales linearly with the number of iterations (Figure 13); it trains one tree and updates residuals in each cluster's fact table within ∼5 . LightGBM cannot run because the join result is >1 .
We now use Favorita to train 1 iteration of gradient boosting, and compare train and update costs for different DBMSes (DBMS-X and DuckDB). To study the potential benefits of column swap (Section 5.4) in commercial DBMSes, X-Swap* reports the theoretical cost using the time to create the updated column as a new table (since column swap is then "free").
Figure 14 breaks down train and update costs. Decision trees and random forests only require training (blue bar), which is dominated by columnar execution: X-col and DuckDB take 3.2 -3.9 versus 14.5 for X-row. Gradient boosting introduces high update costs across all of the baseline DBMSes. We see that using Pandas to perform the update (DP) reduces residual updates by ∼15× (17.8 →1.2 ), but slows training by 60% (3.2 →5.1 ) due to DuckDB-Pandas interop overhead. D-opt implements column swapping inside DuckDB and improves training. We also see that adding column swapping to DBMS-X (X-Swap*) leads to respectable gradient boosting performance (∼3× of D-Swap) but can benefit from its out-of-memory and multi-node scalability features.
We first compare with the dominant factorized approach (LMFAO [61]), followed by the non-factorized approach (MADLib). Factorized ML. We first compare with LMFAO [61], which supports decision trees (but not gradient boosting or random forests). We train a decision tree (max depth=10) with best-first growth; the trained tree is balanced and has 1024 leaves. Via correspondence, the LMFAO authors shared a version that compiles a program for the queries used to split the root tree node, and reuses it for growing the rest of the tree. We set the highest optimization level for LMFAO, and exclude the time for query compilation (∼15 ) and data loading. To separate algorithmic vs implementation differences, we implement two variations of JoinBoost. Naive materializes the join result without factorized ML. Batch implements LMFAO's core logical optimizations (Multi Root, Aggregate Push-down and Merge View) for decision tree; this corresponds to message passing with message re-use within, but not between tree nodes. Figure 15a reports the training time. Even with the custom engine and specialized optimizations, LMFAO is still ∼1.9× slower than JoinBoost due to the lack of message caching (Section 5.5.1). By eliminating the implementation differences, Batch demonstrates that message caching improves training by ∼3×. The improvement is because half the messages across tree nodes are cached, and the sizes of the cached messages tend to be much larger; the intuition is that the messages outgoing from the relation containing the split attribute will be smaller, since the split predicate has been applied. In theory, two-pass semi-join reduction [17,52] could reduce message sizes, but the high overheads outweigh benefits [16]. Batch is ∼2× faster than Naive due to factorization and shared work. Non-Factorized ML. MADLib [32] is a PostgreSQL extension that supports ML using user-defined types and functions. MADLib doesn't apply factorized ML, so the join has to be materialized. MADLib times out after 1 hour when training a decision tree model (max depth=10) on the full Favorita, so we reduced the training data size to 10k rows; for JoinBoost, we reduced the fact table to 10k rows. Figure 15b shows that JoinBoost is ∼16× faster than MADLib.
JoinBoost is the first In-DB factorized ML system for tree models (decision trees, random forests, and gradient boosting) with only SQL. JoinBoost is comparable or faster than the SOTA LightGBM ML library on in-memory datasets, but scales well beyond LightGBM's capabilities in terms of # of features, database size, and join graph complexity. JoinBoost exposes a Python API that mimics LightGBM's API and is portable to any DBMS and dataframe library.
We assume no missing join keys, or use left outer join to maintain 1-to-1 relationship.
We treat left semi-joins as filters over the left relation so its annotations don't change.