Reproduce “Implementing Semantic Join Operators Efficiently” on OpenResearch

About this paper

Immanuel Trummer

Researchers at Cornell University present efficient algorithms for semantic join operators, specifically adapting the block nested loops join to reduce the prohibitive costs of Large Language Model (LLM) invocations. Their approach dramatically cuts processing expenses and execution time by orders of magnitude while preserving or enhancing the quality of join results, making LLM-powered semantic databases practically viable.

Key insights

• Maximizing the number of tokens processed per LLM invocation, up to its context window limit, is essential for minimizing total processing costs for LLM-based semantic joins.
• Batching tuples for LLM evaluation dramatically reduces token consumption and monetary costs by amortizing the fixed LLM invocation overhead across multiple potential matches within a single prompt.
• An adaptive strategy can effectively handle the unknown selectivity of natural language join predicates, achieving processing costs within a small factor of the true optimum without requiring prior knowledge.

Summary by alphaXiv.