Low Rank Learning for Offline Query Optimization

• URL: http://arxiv.org/abs/2504.06399v1
• Date: Tue, 08 Apr 2025 19:41:19 GMT
• Title: Low Rank Learning for Offline Query Optimization
• Abstract summary: Recent deployments of learned queryvolutions use expensive neural networks and ad-hoc search policies.<n>We introduce textscLimeQO, a framework for offline query optimization leveraging low-rank learning.<n>By modeling the workload as a partially observed, low-rank matrix, we predict unobserved query plan latencies using purely linear methods.
• Score: 9.66585417707793
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent deployments of learned query optimizers use expensive neural networks and ad-hoc search policies. To address these issues, we introduce \textsc{LimeQO}, a framework for offline query optimization leveraging low-rank learning to efficiently explore alternative query plans with minimal resource usage. By modeling the workload as a partially observed, low-rank matrix, we predict unobserved query plan latencies using purely linear methods, significantly reducing computational overhead compared to neural networks. We formalize offline exploration as an active learning problem, and present simple heuristics that reduces a 3-hour workload to 1.5 hours after just 1.5 hours of exploration. Additionally, we propose a transductive Tree Convolutional Neural Network (TCNN) that, despite higher computational costs, achieves the same workload reduction with only 0.5 hours of exploration. Unlike previous approaches that place expensive neural networks directly in the query processing ``hot'' path, our approach offers a low-overhead solution and a no-regressions guarantee, all without making assumptions about the underlying DBMS. The code is available in \href{https://github.com/zixy17/LimeQO}{https://github.com/zixy17/LimeQO}.

Related papers

• Adaptive Re-Ranking [9.210588331263503]
  We propose Adaptive Re-Ranking, a utility-based labeling framework for cost-aware routing.<n>We train a routing classifier with 3 strategies: sparse retrieval (BM25), dense re-ranking (MiniLM-L6-v2), and heavy neural re-ranking (BGE-v2-m3)<n>Compared to BGE our method achieves 1.15-53x lower median latency and 1.11-5.22x lower mean latency across all datasets we have tested, while delivering -17.5% to +4.0% nDCG@10.
  arXiv  Detail & Related papers  (2026-06-24T00:12:44Z)
• Efficient Event-based Delay Learning in Spiking Neural Networks [0.1350479308585481]
  Spiking Neural Networks (SNNs) compute using sparse communication and are attracting increased attention.<n>We propose a novel event-based training method for SNNs with delays, grounded in the EventProp formalism.<n>Our method supports multiple spikes per neuron and, to the best of our knowledge, is the first delay learning algorithm to be applied to recurrent SNNs.
  arXiv  Detail & Related papers  (2025-01-13T13:44:34Z)
• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  In this paper, we study the optimality gap between two-layer ReLULU networks regularized with weight decay and their convex relaxations. Our study sheds new light on understanding why local methods work well.
  arXiv  Detail & Related papers  (2024-02-06T01:29:35Z)
• On Statistical Learning of Branch and Bound for Vehicle Routing Optimization [3.6922704509753084]
  We train neural networks to emulate the decision-making process of the computationally expensive Strong Branching strategy. We find that this approach can match or improve upon the performance of the branch and bound algorithm.
  arXiv  Detail & Related papers  (2023-10-15T23:59:57Z)
• Learning RL-Policies for Joint Beamforming Without Exploration: A Batch Constrained Off-Policy Approach [1.0080317855851213]
  We consider the problem of network parameter cancellation optimization for networks. We show that deploying an algorithm in the real world for exploration and learning can be achieved with the data without exploring.
  arXiv  Detail & Related papers  (2023-10-12T18:36:36Z)
• Unsupervised Learning for Solving the Travelling Salesman Problem [28.62497359169851]
  We propose UTSP, an unsupervised learning framework for solving the Travelling Salesman Problem (TSP) We train a Graph Neural Network (GNN) using a surrogate loss. The GNN outputs a heat map representing the probability for each edge to be part of the optimal path. We then apply local search to generate our final prediction based on the heat map.
  arXiv  Detail & Related papers  (2023-03-19T02:30:27Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  We propose L2Dive to learn specific diving structurals with graph neural networks. We train generative models to predict variable assignments and leverage the duality of linear programs to make diving decisions.
  arXiv  Detail & Related papers  (2023-01-24T12:01:45Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Training Overparametrized Neural Networks in Sublinear Time [14.918404733024332]
  Deep learning comes at a tremendous computational and energy cost. We present a new and a subset of binary neural networks, as a small subset of search trees, where each corresponds to a subset of search trees (Ds) We believe this view would have further applications in analysis analysis of deep networks (Ds)
  arXiv  Detail & Related papers  (2022-08-09T02:29:42Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Algorithms for Efficiently Learning Low-Rank Neural Networks [12.916132936159713]
  We study algorithms for learning low-rank neural networks. We present a provably efficient algorithm which learns an optimal low-rank approximation to a single-hidden-layer ReLU network. We propose a novel low-rank framework for training low-rank $textitdeep$ networks.
  arXiv  Detail & Related papers  (2022-02-02T01:08:29Z)
• Neural Capacitance: A New Perspective of Neural Network Selection via Edge Dynamics [85.31710759801705]
  Current practice requires expensive computational costs in model training for performance prediction. We propose a novel framework for neural network selection by analyzing the governing dynamics over synaptic connections (edges) during training. Our framework is built on the fact that back-propagation during neural network training is equivalent to the dynamical evolution of synaptic connections.
  arXiv  Detail & Related papers  (2022-01-11T20:53:15Z)
• Gradient and Projection Free Distributed Online Min-Max Resource Optimization [26.681658600897688]
  We consider distributed online min-max resource allocation with a set of parallel agents. We propose a novel online strategy called Distributed Online resource Re-Alggler (DORA) DORA does not require calculation or projection operation, unlike most existing online strategies.
  arXiv  Detail & Related papers  (2021-12-07T18:42:07Z)
• Optimal Stopping via Randomized Neural Networks [6.677219861416146]
  This paper presents the benefits of using randomized neural networks instead of standard basis functions or deep neural networks. Our approaches are applicable to high dimensional problems where the existing approaches become increasingly impractical. In all cases, our algorithms outperform the state-of-the-art and other relevant machine learning approaches in terms of time.
  arXiv  Detail & Related papers  (2021-04-28T09:47:21Z)
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
  We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. We propose a likelihood matching algorithm that is resilient to catastrophic forgetting and is completely online.
  arXiv  Detail & Related papers  (2021-02-07T14:19:07Z)
• RNN Training along Locally Optimal Trajectories via Frank-Wolfe Algorithm [50.76576946099215]
  We propose a novel and efficient training method for RNNs by iteratively seeking a local minima on the loss surface within a small region. We develop a novel RNN training method that, surprisingly, even with the additional cost, the overall training cost is empirically observed to be lower than back-propagation.
  arXiv  Detail & Related papers  (2020-10-12T01:59:18Z)

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.