SemJoin: Semantic Join Optimization

• URL: http://arxiv.org/abs/2606.29532v1
• Date: Sun, 28 Jun 2026 17:57:10 GMT
• Title: SemJoin: Semantic Join Optimization
• Abstract summary: A semantic join can be evaluated with a large language model (LLM), but comparing every pair of predicates requires O(M x N) invocations and is cost-prohibitive at scale.<n>We propose an LLM-agent-based decision pipeline that optimize semantic joins by matching the execution strategy of the underlying tables.
• Score: 5.770286315818393
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Integrating unstructured data into relational database systems is increasingly important as demand grows for natural language querying and analysis. A semantic join, joining two tables under a natural-language predicate, can be evaluated with a large language model (LLM), but comparing every pair of tuples requires O(M x N) LLM invocations and is cost-prohibitive at scale. Existing systems reduce this cost but typically commit to a single fixed strategy (e.g., embedding similarity or one batched scheme) regardless of the data or the join predicate. We propose an LLM-agent-based decision pipeline that optimizes semantic joins by matching the execution strategy to the characteristics of the underlying tables. An LLM advisor routes each join to one of two strategies: a Cluster Join, which prunes candidates via unsupervised embedding clustering and sample-based filtering, or a Classifier strategy for predicates that reduce to a shared discrete label set. Across three diverse datasets (IMDb reviews, email contradictions, and Stack Overflow tags), the advisor consistently identifies the optimal execution strategy for each workload. This dynamic routing proves decisive: it outperforms adaptive block join (ABJ) by 20-33 F1 points across all datasets while consuming fewer tokens on two of the three, and achieves higher F1 scores than featurized-decomposition join (FDJ) at one to two orders of magnitude lower token cost.

Related papers

• SAGE: A Unified Algebra and Self-Adaptive Execution for AI Functions in SQL [28.278393183168845]
  sql systems increasingly expose AI functions for tasks such as classification, extraction, filtering, ranking, retrieval, joining, and summarization.<n>We present SAGE, a unified logical and physical framework that captures these roles with three typed primitives.<n>SAGE achieves the strongest overall SemBench performance and, on a representative factorable join, reduces pairwise model calls by more than two orders of magnitude.
  arXiv  Detail & Related papers  (2026-08-21T00:12:41Z)
• Larch: Learned Query Optimization for Semantic Predicates [16.10994668093723]
  We introduce Larch, a framework for optimizing the execution of semantic filters in AI SQL queries.<n>Based on two key observations, we present two Larch variants: Larch-A2C and Larch-Sel.<n>Our results demonstrate that Larch is robust across diverse workloads, reducing total token cost overhead by 3x-19x compared to Palimpzest and Quest.
  arXiv  Detail & Related papers  (2026-06-06T01:16:58Z)
• Agentic Clustering: Controllable Text Taxonomies via Multi-Agent Refinement [3.5066696167442775]
  Recent text-clustering methods use large language models to propose a cluster taxonomy from a corpus and then assign each text to it.<n>We propose an agentic alternative in which an orchestrator LLM inspects the state of the discovery process at each step and dispatches one of a small set of specialised agents.<n>On seven public text-clustering benchmarks the method achieves state-of-the-art performance, beating the strongest prior LLM baseline by up to 32% in ARI.
  arXiv  Detail & Related papers  (2026-05-31T14:18:18Z)
• F-GRPO: Factorized Group-Relative Policy Optimization for Unified Candidate Generation and Ranking [79.49893545611779]
  Large Language Models (LLMs) can generate a subset and order it within a single autoregressive pass.<n>This flexibility introduces a new optimization challenge: the model must search an output space while receiving utility feedback only after the full ranked list is generated.<n>This credit assignment gap makes end-to-end optimization unstable and sample-inefficient.<n>We propose a unified framework that performs both within a single autoregressive rollout and optimize them end-to-end via factorized group-relative policy optimization.
  arXiv  Detail & Related papers  (2026-05-13T04:52:33Z)
• HCRE: LLM-based Hierarchical Classification for Cross-Document Relation Extraction with a Prediction-then-Verification Strategy [54.91468501159335]
  Cross-document relation extraction (RE) aims to identify relations between the head tail entities located in different documents.<n>We propose an inference strategy that improves reliability through multi-view verification at each level.
  arXiv  Detail & Related papers  (2026-04-09T07:55:27Z)
• 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)
• Bootstrapping MLLM for Weakly-Supervised Class-Agnostic Object Counting [59.37613121962146]
  We propose WS-COC, the first MLLM-driven weakly-supervised framework for class-agnostic object counting.<n> WS-COC matches or even surpasses many state-of-art fully-supervised methods while significantly reducing annotation costs.
  arXiv  Detail & Related papers  (2026-02-13T09:58:35Z)
• SimpleMem: Efficient Lifelong Memory for LLM Agents [73.74399447715052]
  We introduce SimpleMem, an efficient memory framework based on semantic lossless compression.<n>We propose a three-stage pipeline designed to maximize information density and token utilization.<n> Experiments on benchmark datasets show that our method consistently outperforms baseline approaches in accuracy, retrieval efficiency, and inference cost.
  arXiv  Detail & Related papers  (2026-01-05T21:02:49Z)
• LLM-guided Hierarchical Retrieval [54.73080745446999]
  LATTICE is a hierarchical retrieval framework that enables an LLM to reason over and navigate large corpora with logarithmic search complexity.<n>A central challenge in such LLM-guided search is that the model's relevance judgments are noisy, context-dependent, and unaware of the hierarchy.<n>Our framework achieves state-of-the-art zero-shot performance on the reasoning-intensive BRIGHT benchmark.
  arXiv  Detail & Related papers  (2025-10-15T07:05:17Z)
• Implementing Semantic Join Operators Efficiently [28.123361615101444]
  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.
  arXiv  Detail & Related papers  (2025-10-09T17:30:01Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• 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)

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.