JoinBoost: Grow Trees Over Normalized Data Using Only SQL

• URL: http://arxiv.org/abs/2307.00422v1
• Date: Sat, 1 Jul 2023 20:18:45 GMT
• Title: JoinBoost: Grow Trees Over Normalized Data Using Only SQL
• Abstract summary: JoinBoost is a Python library that rewrites tree training algorithms over normalized databases into pure SQL. It offers performance competitive with specialized ML libraries, and scales with the underlying capabilities. Our experiment shows that JoinBoost is 3x faster for random forests (gradient boosting) than LightGBM, and over an order magnitude faster than state-of-the-art In-DB ML systems.
• Score: 10.919507523061888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Although dominant for tabular data, ML libraries that train tree models over normalized databases (e.g., LightGBM, XGBoost) require the data to be denormalized as a single table, materialized, and exported. This process is not scalable, slow, and poses security risks. In-DB ML aims to train models within DBMSes to avoid data movement and provide data governance. Rather than modify a DBMS to support In-DB ML, is it possible to offer competitive tree training performance to specialized ML libraries...with only SQL? 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 $Y$ variable to the residual in the non-materialized join result. Although this view update problem is generally ambiguous, we identify addition-to-multiplication preserving, the key property of variance semi-ring to support rmse, the most widely used criterion. System-wise, we identify residual updates as a performance bottleneck. Such overhead can be natively minimized on columnar DBMSes by creating a new column of residual values and adding it as a projection. We validate this with two implementations on DuckDB, with no or minimal modifications to its internals for portability. Our experiment shows that JoinBoost is 3x (1.1x) faster for random forests (gradient boosting) compared to LightGBM, and over an order magnitude faster than state-of-the-art In-DB ML systems. Further, JoinBoost scales well beyond LightGBM in terms of the # features, DB size (TPC-DS SF=1000), and join graph complexity (galaxy schemas).

Related papers

• Can LLMs Normalize Databases? A Benchmark and Multi-Agent Framework for Schema Normalization [5.32197677925365]
  Large Language Models (LLMs) are increasingly used to generate structured outputs, but their reliability remains unclear.<n>We study this issue through database normalization, involving reasoning about functional dependencies, join decompositions, and inter-table constraints.<n>We introduce a Database Normalization Benchmark (DNBENCH), comprising 3,275 samples for evaluating LLM-driven database normalization from 1NF to BCNF.
  arXiv  Detail & Related papers  (2026-09-10T06:34:35Z)
• Relational In-Context Learning via Synthetic Pre-training with Structural Prior [60.404256960057545]
  RDB-PFN is the first relational foundation model trained purely via $textbfsynthetic$.<n>Inspired by Prior-Data Fitted Networks (PFNs) where synthetic data generated from Structural Causal Models (SCMs) enables reasoning on single tables.<n>Experiments verify RDB-PFN achieves strong few-shot performance on 19 real-world prediction tasks.
  arXiv  Detail & Related papers  (2026-03-04T07:30:54Z)
• NGDB-Zoo: Towards Efficient and Scalable Neural Graph Databases Training [55.35217340229661]
  We present NGDB-Zoo, a unified framework that resolves bottlenecks by synergizing operator-level training with semantic augmentation.<n>We demonstrate that NGDB-Zoo maintains high GPU utilization across diverse logical patterns and significantly mitigates friction in hybrid neuro-symbolic reasoning.
  arXiv  Detail & Related papers  (2026-02-25T05:46:42Z)
• CORE-T: COherent REtrieval of Tables for Text-to-SQL [91.76918495375384]
  CORE-T is a scalable, training-free framework that enriches tables with purpose metadata and pre-computes a lightweight table-compatibility cache.<n>Across Bird, Spider, and MMQA, CORE-T improves table-selection F1 by up to 22.7 points while retrieving up to 42% fewer tables.
  arXiv  Detail & Related papers  (2026-01-19T14:51:23Z)
• Scaling Text2SQL via LLM-efficient Schema Filtering with Functional Dependency Graph Rerankers [38.94000136647706]
  Most modern Text2 systems prompt large language models (LLMs) with entire schemas alongside the user's question.<n>toolname is an open-source framework that compacts Text2 prompts by ranking columns with a query-aware re-ranking.<n>Experiments show that toolname achieves near-perfect recall and higher precision than CodeS, encoderExP, Qwen rerankers, and embedding retrievers.
  arXiv  Detail & Related papers  (2025-12-18T01:59:06Z)
• Text-to-SQL as Dual-State Reasoning: Integrating Adaptive Context and Progressive Generation [54.53145282349042]
  We introduce DSR-sourced, a textbfDual-textbfS textbfReasoning framework that models Text-to-context as an interaction between an adaptive context state and a progressive generation state.<n>Without any post-training or in-context examples, DSR-sourced achieves competitive performance, reaching 35.28% execution accuracy on Spider 2.0-Snow and 68.32% on BIRD development set.
  arXiv  Detail & Related papers  (2025-11-26T13:52:50Z)
• CRED-SQL: Enhancing Real-world Large Scale Database Text-to-SQL Parsing through Cluster Retrieval and Execution Description [15.080310729603466]
  CRED- is a framework designed for large-scale databases that integrates Cluster Retrieval and Execution Description.<n>It bridges the gap between natural language questions (NLQs) and their correspondingsql queries.<n>CRED- achieves new state-of-git-the-art (SOTA) performance, validating its effectiveness and scalability.
  arXiv  Detail & Related papers  (2025-08-18T09:43:07Z)
• Graph-Reward-SQL: Execution-Free Reinforcement Learning for Text-to-SQL via Graph Matching and Stepwise Reward [15.448159172903138]
  Reinforcement learning (RL) has been widely adopted to enhance the performance of large language models (LLMs) on Text-to- tasks.<n>Existing methods often rely on execution-based or LLM-based Bradley-Terry reward models.<n>We propose a novel Text-to- RL fine-tuning framework named Graph-Reward-Reward, which employs the GMNScore outcome reward model.
  arXiv  Detail & Related papers  (2025-05-18T11:53:01Z)
• LinkAlign: Scalable Schema Linking for Real-World Large-Scale Multi-Database Text-to-SQL [14.677024710675838]
  LinkAlign is a novel framework that can effectively adapt existing baselines to real-world environments. We evaluate our method performance on the SPIDER and BIRD benchmarks. LinkAlign ranks highest among models excluding those using long chain-of-thought reasoning LLMs.
  arXiv  Detail & Related papers  (2025-03-24T11:53:06Z)
• Transformers Boost the Performance of Decision Trees on Tabular Data across Sample Sizes [135.68092471784516]
  We propose a simple and lightweight approach for fusing large language models and gradient-boosted decision trees. We name our fusion methods LLM-Boost and PFN-Boost, respectively. We demonstrate state-of-the-art performance against numerous baselines and ensembling algorithms.
  arXiv  Detail & Related papers  (2025-02-04T19:30:41Z)
• RSL-SQL: Robust Schema Linking in Text-to-SQL Generation [51.00761167842468]
  We propose a novel framework called RSL- that combines bidirectional schema linking, contextual information augmentation, binary selection strategy, and multi-turn self-correction. benchmarks demonstrate that our approach achieves SOTA execution accuracy among open-source solutions, with 67.2% on BIRD and 87.9% on GPT-4ocorrection. Our approach outperforms a series of GPT-4 based Text-to-Seek systems when adopting DeepSeek (much cheaper) with same intact prompts.
  arXiv  Detail & Related papers  (2024-10-31T16:22:26Z)
• LR-SQL: A Supervised Fine-Tuning Method for Text2SQL Tasks under Low-Resource Scenarios [1.4387218083918762]
  Large language models revolutionize Text2 through supervised fine-tuning. Yet a crucial limitation is overlooked: the complexity of databases leads to an increased context length. We propose LR-Thought to reduce total GPU memory usage by 40% compared to existing fine-tuning methods.
  arXiv  Detail & Related papers  (2024-10-15T10:02:55Z)
• Turning Trash into Treasure: Accelerating Inference of Large Language Models with Token Recycling [53.58854856174773]
  Speculative decoding is an approach to accelerate inference through a guess-and-verify paradigm. Token Recycling stores candidate tokens in an adjacency matrix and employs a breadth-first search algorithm. It significantly outperforms existing train-free methods by 30% and even a training method by 25%.
  arXiv  Detail & Related papers  (2024-08-16T12:20:56Z)
• In-Context Data Distillation with TabPFN [11.553950697974825]
  In-context data distillation (ICD) is a novel methodology that effectively eliminates these constraints by optimizing TabPFN's context. ICD efficiently enables TabPFN to handle significantly larger datasets with a fixed memory budget, improving TabPFN's quadratic memory complexity but at the cost of a linear number of tuning steps.
  arXiv  Detail & Related papers  (2024-02-10T15:23:45Z)
• Scaling Sparse Fine-Tuning to Large Language Models [67.59697720719672]
  Large Language Models (LLMs) are difficult to fully fine-tune due to their sheer number of parameters. We propose SpIEL, a novel sparse finetuning method which maintains an array of parameter indices and the deltas of these parameters relative to their pretrained values. We show that SpIEL is superior to popular parameter-efficient fine-tuning methods like LoRA in terms of performance and comparable in terms of run time.
  arXiv  Detail & Related papers  (2024-01-29T18:43:49Z)
• RDBench: ML Benchmark for Relational Databases [38.96429447951739]
  We introduce RDBench, a standardized benchmark to promote reproducible machine learning (ML) research on relational databases (RDBs) RDBench offers diverse RDB datasets of varying scales, domains, graphs and relational structures, organized into 4 levels. For the first time, RDBench enables meaningful comparisons between ML methods from diverse domains, ranging from XBoostG to Graph Neural Networks, under RDB prediction tasks.
  arXiv  Detail & Related papers  (2023-10-25T17:59:34Z)
• Uni-Parser: Unified Semantic Parser for Question Answering on Knowledge Base and Database [86.03294330305097]
  We propose a unified semantic element for question answering (QA) on both knowledge bases (KB) and databases (DB) We introduce the primitive (relation and entity in KB, table name, column name and cell value in DB) as an essential element in our framework. We leverage the generator to predict final logical forms by altering and composing topranked primitives with different operations.
  arXiv  Detail & Related papers  (2022-11-09T19:33:27Z)
• Efficient and Accurate In-Database Machine Learning with SQL Code Generation in Python [0.0]
  We describe a novel method for In-Database Machine Learning (IDBML) in Python using template macros in Jinja2. Our method was 2-3% less accurate than the best current state-of-the-art methods we found (decision trees and random forests) and 2-3 times slower for one in-memory dataset.
  arXiv  Detail & Related papers  (2021-04-07T16:23:19Z)
• Bridging Textual and Tabular Data for Cross-Domain Text-to-SQL Semantic Parsing [110.97778888305506]
  BRIDGE represents the question and DB schema in a tagged sequence where a subset of the fields are augmented with cell values mentioned in the question. BRIDGE attained state-of-the-art performance on popular cross-DB text-to- relational benchmarks. Our analysis shows that BRIDGE effectively captures the desired cross-modal dependencies and has the potential to generalize to more text-DB related tasks.
  arXiv  Detail & Related papers  (2020-12-23T12:33:52Z)
• ConvBERT: Improving BERT with Span-based Dynamic Convolution [144.25748617961082]
  BERT heavily relies on the global self-attention block and thus suffers large memory footprint and computation cost. We propose a novel span-based dynamic convolution to replace these self-attention heads to directly model local dependencies. The novel convolution heads, together with the rest self-attention heads, form a new mixed attention block that is more efficient at both global and local context learning.
  arXiv  Detail & Related papers  (2020-08-06T07:43:19Z)
• Exploiting Database Management Systems and Treewidth for Counting [22.315022989618594]
  A canonical counting problem is #SAT, which asks to count the assignments of a Boolean formula. Recent work shows that benchmarking instances for #SAT often have reasonably small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems.
  arXiv  Detail & Related papers  (2020-01-13T12:45:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.