Implementing Semantic Join Operators Efficiently

• URL: http://arxiv.org/abs/2510.08489v1
• Date: Thu, 09 Oct 2025 17:30:01 GMT
• Title: Implementing Semantic Join Operators Efficiently
• Authors: Immanuel Trummer,
• Abstract summary: This paper proposes a novel algorithm for evaluating semantic joins.<n>The proposed algorithm integrates batches of rows from both input tables into a single prompt.<n>An adaptive variant of the proposed algorithm refers to cases in which the size of the output is difficult to estimate.
• Score: 28.123361615101444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semantic query processing engines often support semantic joins, enabling users to match rows that satisfy conditions specified in natural language. Such join conditions can be evaluated using large language models (LLMs) that solve novel tasks without task-specific training. Currently, many semantic query processing engines implement semantic joins via nested loops, invoking the LLM to evaluate the join condition on row pairs. Instead, this paper proposes a novel algorithm, inspired by the block nested loops join operator implementation in traditional database systems. The proposed algorithm integrates batches of rows from both input tables into a single prompt. The goal of the LLM invocation is to identify all matching row pairs in the current input. The paper introduces formulas that can be used to optimize the size of the row batches, taking into account constraints on the size of the LLM context window (limiting both input and output size). An adaptive variant of the proposed algorithm refers to cases in which the size of the output is difficult to estimate. A formal analysis of asymptotic processing costs, as well as empirical results, demonstrates that the proposed approach reduces costs significantly and performs well compared to join implementations used by recent semantic query processing engines.

Related papers

• Beyond Linear LLM Invocation: An Efficient and Effective Semantic Filter Paradigm [17.52767415071768]
  Clustering-Sampling-Voting (CSV) is a framework that reduces invocations to sublinear complexity while providing error guarantees.<n>CSV embeds semantic clusters into semantic clusters, samples a small subset for evaluation, and infers cluster-level labels via two proposed voting strategies.
  arXiv  Detail & Related papers  (2026-03-05T04:37:15Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• Hint-Augmented Re-ranking: Efficient Product Search using LLM-Based Query Decomposition [20.966359103135762]
  We show that LLMs can uncover latent intent behind superlatives in e-commerce queries.<n>Our approach decomposes queries into attribute-value hints generated concurrently with retrieval.<n>Our method improves search performanc eby 10.9 points in MAP and ranking by 5.9 points in MRR over baselines.
  arXiv  Detail & Related papers  (2025-11-17T23:53:25Z)
• Efficient Context Selection for Long-Context QA: No Tuning, No Iteration, Just Adaptive-$k$ [13.173467492641485]
  We present Adaptive-$k$, a simple and effective single-pass method that adaptively selects the number of passages based on the similarity scores between the query and the candidate passages.<n>It does not require model fine-tuning, extra LLM inferences or changes to existing retriever-reader pipelines.<n>It improves accuracy across five LCLMs and two embedding models, highlighting that dynamically adjusting context size leads to more efficient and accurate QA.
  arXiv  Detail & Related papers  (2025-06-10T06:11:01Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  evaluating constraint on every token can be prohibitively expensive.<n> LCD can distort the global distribution over strings, sampling tokens based only on local information.<n>We show that our approach is superior to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-04-07T18:30:18Z)
• TETRIS: Optimal Draft Token Selection for Batch Speculative Decoding [76.23719557942917]
  TETRIS actively selects the most promising draft tokens (for every request in a batch) to be accepted when verified in parallel.<n>We show theoretically and empirically that TETRIS outperforms baseline speculative decoding and existing methods that dynamically select draft tokens.
  arXiv  Detail & Related papers  (2025-02-21T04:19:24Z)
• LLM-assisted Vector Similarity Search [0.0]
  This paper explores a hybrid approach combining vector similarity search with Large Language Models (LLMs) to enhance search accuracy and relevance.<n> Experiments on structured datasets demonstrate that while vector similarity search alone performs well for straightforward queries, the LLM-assisted approach excels in processing complex queries involving constraints, negations, or conceptual requirements.
  arXiv  Detail & Related papers  (2024-12-25T08:17:37Z)
• BATON: Enhancing Batch-wise Inference Efficiency for Large Language Models via Dynamic Re-batching [4.610983384440473]
  We propose BATON, an efficient batch-wise LLM inference scheme by dynamically adjusting processing batch. Compared to the state-of-the-art solution Orca, BATON improves query processing by up to 1.75 times.
  arXiv  Detail & Related papers  (2024-10-24T12:53:39Z)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• JoinGym: An Efficient Query Optimization Environment for Reinforcement Learning [58.71541261221863]
  Join order selection (JOS) is the problem of ordering join operations to minimize total query execution cost. We present JoinGym, a query optimization environment for bushy reinforcement learning (RL) Under the hood, JoinGym simulates a query plan's cost by looking up intermediate result cardinalities from a pre-computed dataset.
  arXiv  Detail & Related papers  (2023-07-21T17:00:06Z)
• SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
  We propose a new satisfiability-aided language modeling (SatLM) approach for improving the reasoning capabilities of large language models (LLMs) We use an LLM to generate a declarative task specification rather than an imperative program and leverage an off-the-shelf automated theorem prover to derive the final answer. We evaluate SATLM on 8 different datasets and show that it consistently outperforms program-aided LMs in the imperative paradigm.
  arXiv  Detail & Related papers  (2023-05-16T17:55:51Z)
• DeepJoin: Joinable Table Discovery with Pre-trained Language Models [10.639106014582756]
  Existing approaches target equi-joins, the most common way of combining tables for creating a unified view. Deepjoin is a deep learning model for accurate and efficient joinable table discovery. Deepjoin is even more accurate than an exact solution to semantic joins when evaluated with labels from experts.
  arXiv  Detail & Related papers  (2022-12-15T02:40:57Z)

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.