PaperlayerView exact revision on arXiv

Source-linked AI summary

Factorized and Vectorized Execution: Optimizing Analytical and Semantic Queries over Relations

Sunny Yasser, Anas Dorbani, Amine Mhedhbi

arXiv:2609.09002v1cs.DB

TL;DR

Join-heavy analytical and semantic workloads can generate intermediates far larger than their inputs, while factorized representations are difficult to execute in flat vectorized processors. FFX unifies arbitrary factorization with vectorized execution and factorized semantic processing, achieving substantial join speedups and reducing semantic prompt sizes by up to 18.83× with little to no quality degradation.

  • Problem

    Many-to-many joins can create oversized intermediates, but existing vectorized systems struggle to execute hierarchical factorized representations while preserving their compactness and generality.

  • Method

    FFX uses packed factorized vectors and cascade-update operators to propagate arbitrary factorized intermediates through vectorized pipelines and serialize them directly for semantic operators.

  • Results

    Up to 18.83× smaller prompt sizes than Lotus were achieved with little to no degradation in semantic output quality, while join-heavy workloads received substantial speedups over prior systems.

  • Takeaways & Limitations

    Factorization and vectorization can be complementary end-to-end, including for join-heavy analytical queries augmented with LLM-powered semantic operators.

  • Takeaways & Limitations

    FFX is a research prototype, so its absolute performance numbers are not directly comparable with mature production systems such as DuckDB and Kuzu.

Abstract

from arXiv · show

Many-to-many joins are central to analytical and semantic workloads such as fraud detection, network analysis, and recommendation, where insights arise from relationships between entities. These workloads often suffer from an explosion of intermediate results, sometimes orders of magnitude larger than the inputs. Factorized representations address this problem by exploiting conditional independence among attributes to encode intermediates more compactly. In some cases, they can reduce the output size asymptotically below the worst-case output size. However, adopting factorization in modern vectorized query processors remains challenging: factorized representations are hierarchical, whereas vectorized execution is built around flat, block-oriented processing. Prior approaches either rely on full materialization or support only restricted factorization layouts, sacrificing much of the benefits of both factorization and vectorization. We present FFX, a novel engine for Fast Factorized eXecution. FFX is the first pipelined engine to support arbitrary factorization schemes while preserving full vectorization. The engine introduces packed factorized vectors and operators that maintain cache-friendly, contiguous layouts. Beyond analytics, FFX also co-optimizes semantic operators by serializing factorized intermediates into compact prompts for large language models (LLMs), substantially reducing token usage and inference cost while maintaining output quality and, in some cases, improving it. Together, these contributions enable efficient execution of join-heavy analytical queries, including queries augmented with semantic operators.

1 Introduction

Many-to-many joins support important analytical and semantic workloads but can produce intermediates far larger than their inputs. FFX addresses the resulting tension between compact factorization and flat vectorized execution by propagating packed factorized intermediates through a unified pipeline.

  • Motivation: Many-to-many joins underpin analytical tasks involving relationship structures and increasingly provide context for LLM inference.Examples include network substructure enumeration, social recommendation, traffic-flow analysis, recommendation, and network diagnosis.
  • Motivation: Join evaluation becomes a scalability bottleneck when intermediate results exceed input sizes by orders of magnitude, especially when intermediates are serialized into LLM prompts.For semantic systems, inference cost is directly proportional to serialized intermediate size.
  • Factorization: Factorized representations exploit shared attribute-value prefixes and independence to encode relational results compactly, potentially below the AGM output-size bound.They rewrite flat tuples as nested unions and products, combining subexpressions that vary independently under shared prefixes.
  • Challenge: Factorization is difficult to integrate with vectorized engines because hierarchical, dynamically changing results conflict with flat fixed-size blocks.Selections can trigger cascading updates across dependent hierarchy levels rather than reducing tuples locally.
  • Existing approaches: Prior systems either restrict factorization layouts, produce sparsely populated vectors, or apply factorization only to specialized optimizations rather than as a general intermediate representation.The missing model must preserve both compact intermediates and cache-efficient vectorized execution across operators.
  • FFX contributions: FFX introduces packed factorized vectors, vectorized operators with fallback, cascade updates, and factorized semantic processing for end-to-end co-optimization.Its semantic operators consume serialized factorized vectors and materialize Cartesian combinations in their output.

2 Background

Factorized representations compact join results by exploiting shared prefixes and conditional independence, but existing engines trade off pipelining, vectorization, or layout flexibility. LBP integrates factorization into vectorized pipelines, yet sparse vectors and restricted f-trees limit its benefits.

  • Factorized representations: Factorized representations replace flat tuple unions with nested unions and products, avoiding or delaying Cartesian expansion.They can reduce intermediate size below the worst-case AGM bound by exploiting conditional independence.
  • Factorized representations: An f-tree specifies attribute grouping, with branching representing independent subrelations under a shared prefix.More branching and smaller height generally yield more compact encodings.
  • Factorized representations: The example two-hop join has 13 flat tuples, while f-trees T1 and T2 encode it using 22 and 15 atomic values, respectively.T2 is more compact because it branches on the shared attribute a2 and separates conditionally independent subrelations.
  • Factorized engines: FDB evaluates factorized queries but fully materializes a fresh multi-level trie after every operator, while later optimizations preserve this execution model.This avoids complex in-place hierarchical updates but reconstructs complete factorized intermediates repeatedly.
  • List-based processing: LBP pipelines factorized vectors aligned to adjacency lists, but its fixed-width vectors are often sparsely populated and incur interpretation overhead.In the illustrated pipeline, vectors represent parent bindings and conditioned child lists rather than fully packed flat batches.
  • List-based processing: LBP supports only restricted f-trees, preventing the most compact layouts for deep path queries and leaving compression benefits unattainable.For the four-join path, LBP realizes layouts with worst-case size N^3 instead of the compact layout with worst-case size N^2.

3 System Overview

FFX unifies factorized and vectorized execution by combining packed factorized vectors, hierarchy-aware updates, and structure-aware serialization. This design targets arbitrary factorization layouts while preserving contiguous vector processing and avoiding flattening for semantic operators.

  • Motivation: FFX revisits unified factorized and vectorized execution because LBP underutilizes CPUs and supports only limited factorization layouts.The system overview positions these limitations as the motivation for a new pipelined execution model.
  • System overview: FFX addresses the gap between hierarchical factorization and flat vectorized execution with packed factorized vectors, cascade updates, and structure-aware semantic serialization.These mechanisms encode f-tree groupings contiguously, propagate tuple reductions across hierarchy levels, and serialize factorized intermediates without flattening.

4 Packed Factorized Vectors

FFX represents factorized intermediates with packed, contiguous vectors that preserve hierarchical groupings through explicit state and offsets. This layout supports arbitrary f-trees while avoiding LBP’s sparse vectors and repeated interpretation overhead.

  • 4.1 Vector Representation: Packed factorized vectors extend standard vectors with contiguous values plus state encoding slices, selectors, and parent-child offsets.Offsets map each parent entry to its child slice, while start/end positions and selectors track active values.
  • 4.1 Vector Representation: Many-to-many joins append matches contiguously and update offsets so each grouping entry maps to its corresponding child range.This preserves packed vectors while retaining the f-tree associations required by factorized execution.
  • 4.1.2 Packed Factorized Vectors: FFX keeps parent and child values packed and uses offsets to delimit each parent’s child slice instead of materializing separate child lists.Selectors track invalidations while operators scan contiguous ranges.
  • 4.1.3 Arbitrary Factorizations: 3× as many operator calls are required by LBP for the evaluation example because it backtracks across three bindings.The paper reports that larger datasets can amplify this interpretation overhead by orders of magnitude.
  • 4.1.3 Arbitrary Factorizations: FFX represents intermediates over any valid f-tree, removing LBP’s branching restriction while preserving vector packing.The Fig. 5 example demonstrates a branching layout supported without full materialization.

5 Query Execution

FFX adapts joins and reducing operators to packed factorized vectors, including fanout expansion, multi-way execution, and dependency-aware reduction propagation. Its Cascade Update operator maintains hierarchical validity while allowing standard vectorized fallback when factorization offers no benefit.

  • 5.1 Query Execution: FFX chooses grouping attributes and builds valid f-trees as query attribute orderings extend, placing new attributes beneath the lowest applicable join key.All input join keys must lie on one root-to-leaf path for multi-way joins.
  • 5.2 Cascade Update: Cascade Update propagates tuple reductions across the factorized hierarchy using a dependency tree derived from the current f-tree.AGG nodes invalidate ancestors when child slices become empty, while SCATTER nodes push invalidations into dependent subtrees.
  • 5.1 Query Execution: FFX supports non-expanding and fanout-expanding joins, updating shared state for the former and offsets, slices, and selectors for the latter.Fanout joins append matches contiguously and may contract active input slices.
  • 5.1 Query Execution: FFX falls back to standard vectorized execution for non-expanding joins when factorization provides no additional benefit.In this case, input and output vectors share state and no offset updates are required.
  • 5.2 Cascade Update: Delta-driven AGG limits parent checks to bindings identified by newly invalidated child positions through the offset array.This avoids scanning unchanged parent slices while preserving correct reduction propagation.

6 Factorized Semantic Processing

FFX extends factorized execution to LLM-powered semantic processing without flattening intermediates during prompt construction. Its structure-aware iterator and serializer preserve shared prefixes and represent Cartesian expansion compactly.

  • 6 Factorized Semantic Processing: Flattening factorized intermediates before prompt construction would forfeit their compactness benefits.LLM operators ordinarily consume text representations of flat tuples, creating a mismatch with factorized vectors.
  • 6 Factorized Semantic Processing: FFX serializes factorized intermediates directly and instructs the LLM to perform the implied Cartesian expansion.The operator produces one prediction per logical tuple without first flattening the input.
  • 6.1 Semantic Operator Model: The implemented semantic primitive is llm_map; llm_reduce, llm_filter, and llm_rerank remain future work.This defines the current scope of FFX’s semantic operator support.
  • 6.1 Semantic Operator Model: FFX reconstructs outputs by aligning model predictions with a fixed tuple enumeration order and inserting predictions into factorized vectors.Missing predictions are assigned NULL, with retries noted as an alternative.
  • 6.1 Semantic Operator Model: Windowed iteration controls the trade-off between compactness and flatness by emitting shared ancestor prefixes once across multiple logical tuples.Window size 1 degenerates to flat-tuple iteration, while larger windows preserve common prefixes.
  • 6.1 Semantic Operator Model: The serializer follows the f-tree, nesting descendant bindings under parents and supporting JSON or XML surface syntax.The syntax is separate from the core structure-aware serialization idea.

7 Evaluation

The evaluation examines FFX’s vector representation against prior systems, its overhead when factorization is unhelpful, and its token-use and accuracy effects for factorized semantic processing. Comparisons include DuckDB, Kuzu, and multi-core scalability on large datasets.

  • 7 Evaluation: The evaluation asks how FFX compares with LBP, whether packed vectors add overhead without factorization benefits, and how factorized prompts affect token usage and accuracy.These questions cover both analytical execution and semantic processing.
  • 7 Evaluation: FFX is compared against DuckDB and Kuzu, with multi-core scalability evaluated on large datasets.DuckDB is the relational vectorized baseline, while Kuzu is LBP-based.

7.1 Setup

The evaluation uses network datasets and conjunctive equi-join/self-join queries spanning varied graph shapes, with experiments run under controlled hardware and repeated-measurement settings.

  • Hardware and software: All experiments run on an 8-vCPU Google Cloud instance with 30 GB memory and an Intel Xeon Platinum 8581C CPU unless otherwise stated.Binaries use clang 15.0.6 with -O3, and builds are generated with CMake 3.25.1.
  • Datasets: Experiments use datasets from OGB, a 2010 Twitter crawl, and SNAP, represented as base relations R(src, dst).The datasets cover citation, social, web, and product networks with varying scale, degree distributions, and skew.
  • Queries: Queries consist exclusively of equi-joins and self-joins over one base relation R, written in Datalog-style conjunctive form.The study includes path, star, and tree join-graph shapes, focusing mainly on acyclic graphs.
  • Measurement protocol: Each query runs three times with the median reported, while caches are manually cleared after each query to reduce execution-order bias.Figure 7 reports runtime in seconds on a logarithmic scale across all plans for Q1–Q9 on Google.

7.2 Factorization and Vectorization Benefits

FFX combines packed factorized vectors with vectorized execution to preserve compact branching layouts and reduce redundant work. Across plans, packed execution generally outperforms unpacked processing, including when factorization itself provides no compactness benefit.

  • Overall comparison: 96.53% of Google plans favor packed vectors, with a 2.08× mean speedup across all queries and plans.Packed execution outperforms unpacked execution on 1883 plans and underperforms on 68 Q5 plans with runtimes below 100 ms.
  • Plan selection: Packed execution is 4.94× faster on average when packed and unpacked representations share the same best ordering.This applies to Q1 and Q9, which comprise 22% of the nine queries.
  • Design implication: FFX supports arbitrary f-trees while retaining packed vectors, reducing interpretation overhead and redundant computation together.The packed layout also supports cache-efficient processing and compiler autovectorization.

7.3 End-to-End Join Benchmark Evaluation

End-to-end benchmarks show FFX is often substantially faster than DuckDB and Kuzu on join workloads, especially when join orders produce compact factorized intermediates. Comparisons are indicative rather than directly comparable because FFX is a research prototype optimized for the studied problem.

  • Caveat: FFX’s absolute benchmark numbers are not directly comparable with DuckDB and Kuzu because those systems are mature production systems while FFX is a focused research prototype.The comparisons remain indicative of potential gains from integrating factorization and vectorization.
  • LSQB: FFX is consistently competitive and often substantially faster than Kuzu and DuckDB on LSQB queries Q1–Q6.Q7–Q9 are omitted because FFX does not support outer and anti-joins.
  • JOB: FFX is fastest on JOB queries when orderings yield succinct, often star-like f-trees that avoid enumerating large flat-tuple sets.Less selective predicates in variant c increase intermediate sizes and reduce speedups.
  • Amazon: 102×–105× speedups over both DuckDB and Kuzu occur across the nine Amazon queries, with 105× on star-shaped Q5.Factorized vectors process shared central join keys once instead of repeatedly reproducing associated data.
  • Execution mechanism: 2.98B tuples would be materialized by a baseline plan, whereas FFX pushes projection and aggregation to intermediates totaling 63.2M tuples.This illustrates how factorization avoids generating the large final join result.

7.4 Multi-core Scalability

FFX scales nearly linearly across cores on a many-to-many join while remaining faster than the compared systems. Scaling benefits diminish beyond 16 cores on this workload.

  • Scalability: FFX scales by up to 13.2× on LiveJournal and 13.8× on Twitter using up to 32 cores.The query is evaluated fully in memory, enabling embarrassingly parallel execution.
  • System comparison: All systems exhibit near-linear speedup, but FFX remains faster than Kuzu and DuckDB through combined factorized and vectorized execution.Twitter comparisons with the baselines are omitted because its larger scale causes frequent baseline timeouts.
  • Scaling limit: Beyond 16 cores, this workload shows fewer additional scalability benefits.The observation is specific to the evaluated workload.

7.5 Evaluation of Factorized Semantic Processing

The evaluation compares factorized and flat semantic processing for keyword generation over 2-hop citation chains. FFX-Fact substantially reduces prompt tokens, preserves competitive retrieval quality, and supports larger batches, although Cartesian-product output generation remains a bottleneck.

  • Evaluation setup: The evaluation applies llm_map to many-to-many join outputs, generating five keywords to summarize each 2-hop citation chain.The dataset contains 2,028 abstract triplets spanning 232 papers, and keyword quality is evaluated with Recall@5 and Recall@10 retrieval.
  • Compared systems: FFX-Fact serializes packed factorized vectors directly, while FFX-Flat independently serializes fully enumerated flat tuples for prompts.The comparison uses GPT-5.2, GPT-4o, and GPT-4o-mini, with GPT-5.2 results reported for brevity.
  • Token efficiency: 1.70× to 15.67× fewer input tokens: FFX-Fact consistently reduces prompt size relative to FFX-Flat across comparable batch sizes.At batch size 256, FFX-Fact uses 0.09M input tokens versus 1.41M for FFX-Flat.
  • Retrieval quality: At batch size 256, FFX-Fact reaches 0.5439 Recall@5 and 0.6154 Recall@10, while FFX-Flat falls to 0.3319 and 0.3669.Flat prompting performs better at moderate batch sizes, but its quality degrades more sharply as batches grow because of missing output tuples.
  • Scalability: FFX-Fact operates up to batch size 2048, whereas FFX-Flat cannot be evaluated beyond 256 because its prompts exceed the context window.At batch sizes 512 and 2048, FFX-Fact uses 70.14K and 62.56K input tokens, respectively, but missing output tuples increase substantially.
  • Overall findings: Factorized semantic processing saves tokens and avoids the sharper large-batch quality collapse of flat prompting, but reliable Cartesian-product output generation remains the main bottleneck.Both approaches degrade beyond batch size 128, while factorized prompting degrades more gradually.
  • Comparison with Lotus: Compared with Lotus, FFX-Fact uses 18.83× fewer input tokens at batch size 128 while achieving essentially the same Recall@5.At batch size 64, FFX-Fact exceeds Lotus on both reported recall metrics while using about 12.55× fewer input tokens.

8 Conclusion

FFX unifies arbitrary factorization with fully vectorized execution through packed factorized vectors, cascade updates, and factorized semantic processing. Across join-heavy and semantic workloads, it reduces overhead and prompt size while preserving a fallback to standard vectorized execution when factorization is not beneficial.

  • System design: FFX unifies factorized and vectorized execution in one engine using packed vectors, cascade updates, and factorized semantic processing.These components preserve packed layouts, propagate reductions across dependent bindings, and serialize factorized intermediates without first flattening them.
  • Analytical execution: Across join-heavy workloads, FFX preserves tight inner loops, reduces interpretation overhead, and achieves substantial speedups over prior systems.When factorization offers little or no benefit, it falls back to standard vectorized execution without additional overhead.
  • Semantic processing: Factorized semantic processing reduces prompt sizes by up to 18.83× compared with Lotus with little to no degradation in output quality.This extends FFX's benefits from analytical execution to semantic query processing.
Loading 2609.09002v1…