PaperlayerView exact revision on arXiv

Source-linked AI summary

Reducing the Cross-Model Tax: Query Optimization over Multi-Model Data

Jáchym Bártík, Filip Štrobl, Irena Holubová

arXiv:2609.05014v1cs.DB

TL;DR

Decomposition-based multi-model query processing can incur substantial cross-model tax from work performed outside underlying DBMSs. The paper develops a mapping- and capability-aware pipeline that moves applicable processing closer to the data, and reports major execution, memory, and planning improvements in its evaluated architecture.

  • Problem

    Cross-model query processing must coordinate heterogeneous mappings and native capabilities while limiting overhead from data transfer and unifying-layer processing.

  • Method

    The paper combines model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction in a unified optimization pipeline.

  • Results

    The evaluated pipeline reduces latency by up to two orders of magnitude, eliminates all observed single-DBMS out-of-memory failures, and cuts largest Neo4j planning times from almost 600 milliseconds to several milliseconds.

  • Takeaways & Limitations

    Established optimization principles can be generalized across data-model and DBMS boundaries by jointly considering conceptual semantics, mappings, and native capabilities.

  • Takeaways & Limitations

    The evaluation uses 20 read-only queries from a supported MMQL subset and excludes updates, complex aggregations, optional joins, and analytical workloads.

Abstract

from arXiv · show

Querying across heterogeneous data models incurs substantial overhead from query decomposition, data transfer, and processing outside the underlying database systems. We show that, in the evaluated decomposition-based architecture, a substantial part of this cross-model tax is not inherent to heterogeneity itself, but results from avoidable decisions made by the unifying query processor. We present a mapping- and capability-aware optimization approach that systematically moves processing closer to the data. It combines model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction within a unified optimization pipeline applicable across relational, document, and graph databases. The approach is implemented in MM-quecat and evaluated over PostgreSQL, MongoDB, Neo4j, and their heterogeneous combination. It reduces query latency by up to two orders of magnitude, eliminates all out-of-memory failures observed in the original single-DBMS experiments, provides further order-of-magnitude improvements through dependent execution, and reduces planning time for complex graph plans from hundreds of milliseconds to several milliseconds. The results demonstrate that established optimization principles can be generalized across data-model and system boundaries and can substantially improve the efficiency and robustness of decomposition-based multi-model query processing.

1. Introduction

Multi-model query processing must manage differences in physical representations, native capabilities, and cross-boundary data movement. The paper proposes a unified optimization pipeline that pushes work toward underlying databases and reduces avoidable overhead in decomposition-based execution.

  • Motivation: The cross-model tax arises from decomposition, data transfer, conversion, joining, and restructuring outside underlying DBMSs.It can become the dominant processing cost when intermediate results cross source boundaries.
  • Motivation: Late filtering, independently retrieved join inputs, and redundant query-part construction are identified as three avoidable overhead sources.These choices can transfer irrelevant records, materialize large intermediates, or repeatedly explore equivalent plans.
  • Approach: The proposed pipeline combines model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction.It connects conceptual plans with mapping coverage, native capabilities, and processing retained in the unifying layer.
  • Approach: Optimization decisions are made only when mappings provide required values and native query builders support the corresponding operations.Dependent restrictions can cross data-model and DBMS boundaries, while construction pruning preserves genuinely different physical alternatives.
  • Implementation and evaluation: MM-quecat implements the complete pipeline over relational, document, graph, and heterogeneous deployments.Its architecture separates conceptual processing, mapping selection, native query generation, DBMS execution, and unifying-layer processing.
  • Results: Predicate pushdown reduces latency by up to two orders of magnitude, dependent execution adds up to one order of magnitude, and graph-plan planning falls from almost 600 milliseconds to several milliseconds.The evaluation also eliminates all observed out-of-memory failures in the original single-DBMS experiments.
  • Implications: The unifying layer retains operations that cannot be delegated while coordinating the capabilities of underlying DBMSs.This reduces the avoidable portion of heterogeneity-related cost without removing unavoidable heterogeneity costs.

2. Preliminaries and Query-Processing Model

The paper models heterogeneous querying through a unified conceptual schema mapped to relational, document, and graph systems. MM-quecat normalizes MMQL queries, decomposes them into executable parts, and targets avoidable cross-model overhead through three optimization techniques.

  • 2.1. Heterogeneous Data Models: Relational, document, and graph models differ in how they represent records, relationships, and complex values, affecting which operations DBMSs can execute locally.
  • 2.2. Unified Schema and Mappings: A unified schema category represents entities, attributes, and relationship paths independently of their physical database representations.
  • 2.2. Unified Schema and Mappings: Mappings associate conceptual schema fragments with DBMS-managed record collections and expose model-specific representations such as scalar values, arrays, references, or nested structures.
  • 2.3. Multi-Model Query Language: MMQL lets users query the unified schema without selecting physical mappings, data models, DBMSs, or native query languages.
  • 2.3. Multi-Model Query Language: Before physical planning, MM-quecat normalizes composite morphisms, dual morphisms, and literal restrictions into a common representation.
  • 2.4. Optimization Overview: Predicate pushdown, dependent joins, and non-redundant construction address late filtering, independent cross-model retrieval, and equivalent planning paths, respectively.

3. Cross-Model Query Optimization

The section presents three integrated techniques that reduce avoidable cross-model overhead by moving processing closer to data and limiting redundant planning. Their applicability depends on semantic validity, physical mappings, and native DBMS capabilities.

  • Predicate pushdown: Predicate pushdown reduces retrieved data by moving filters toward native query parts when mappings and query builders support the complete condition.Otherwise, the filter remains at the deepest valid position in the unifying layer.
  • Dependent joins: Dependent joins reduce unifying-layer join inputs by using one branch’s values to restrict the other before retrieval.The approach introduces execution dependencies and top-down information flow across model and DBMS boundaries.
  • Non-redundant construction: Non-redundant construction reduces planning overhead by adding mandatory kind patterns without exploring equivalent insertion orders.For k mandatory patterns, the original procedure may explore up to k! equivalent orders, while the modified procedure creates one continuation.
  • Integrated pipeline: The pipeline combines unified-plan transformations with mapping coverage, native execution capabilities, and remaining unifying-layer processing costs.Operators are translated into SQL, MongoDB aggregation pipelines, or Cypher only when semantics, mappings, and target capabilities permit delegation.
  • Optimization scope: Predicate pushdown is restricted to semantically valid movements, with the evaluated implementation permitting movement through inner joins but not outer joins.Moving predicates across outer joins can change whether unmatched records are preserved.

4. Implementation

The implementation integrates non-redundant construction, predicate pushdown, and dependent execution through a shared mutable QEP representation and capability-aware native-query translation. Runtime safeguards preserve a fallback when estimates or native capabilities do not support dependent execution.

  • Pipeline integration: MM-quecat extends its bottom-up pipeline with mapping-aware QEP transformations, capability-aware native-query generation, and controlled top-down information flow.The techniques share one QEP representation and a translation boundary spanning SQL, MongoDB, and Cypher execution.
  • QEP representation: The QEP representation explicitly distinguishes filters evaluated in the unifying layer from filters delegated to underlying DBMSs.Datasource nodes store native-query filters, while standalone filter nodes remain in the unifying layer.
  • Native translation: Native builders translate supported conditions into SQL, MongoDB aggregation pipelines, or Cypher after verifying complete capability and mapping coverage.The same translation interface handles static pushed filters and dynamically generated dependent restrictions.
  • Dependent execution: Dependent execution selects an independent branch using lightweight cardinality estimates, then propagates distinct join values toward a consumable native query part.If the actual independent result exceeds the configured limit, the original non-dependent strategy is used.
  • Dependent execution: The implementation supports arbitrary dependent subtrees and retains a safe fallback when no node can consume the propagated restriction.The restriction may pass through model-independent operators before translation at a suitable native query part.
  • Cardinality estimation: The lightweight estimator selects dependent-join orientation rather than implementing a complete heterogeneous cost model.It is designed only to distinguish sufficiently between smaller and larger candidate inputs.

5. Experimental Evaluation

The evaluation measures latency, processing phases, cumulative optimizations, and workload-dependent effects in MM-quecat across single-DBMS and heterogeneous environments. It characterizes the approach within the evaluated architecture, dataset, and supported MMQL subset rather than benchmarking all multi-model systems.

  • The evaluation covers end-to-end latency, processing phases, incremental optimization effects, and query- and mapping-dependent effectiveness.
  • The experiments use PostgreSQL-only, MongoDB-only, Neo4j-only, and heterogeneous environments spanning the same selected schema.
  • The workload contains 20 predominantly parameterized select–project–join queries with equality, inequality, or set-membership predicates.
  • The physical mappings access different numbers of kinds, so one conceptual query can induce substantially different decompositions across environments.
  • Three heterogeneous-environment queries fail in the original prototype path and are excluded from corresponding optimization comparisons.
  • Successive cumulative configurations measure predicate pushdown, dependent joins, and all implemented optimizations, but not factorial combinations.

5.2. Baseline Performance and Bottlenecks

Before optimization, latency varies widely across queries and environments, while native execution or transfer and intermediate-result processing dominate the heterogeneous pipeline. Several executions fail through memory exhaustion or prototype functional errors.

  • Before optimization, mean query latency ranges from less than ten milliseconds to more than ten seconds.
  • Latency differences reflect physical decomposition, returned data volume, and joining retained in MM-quecat, not only conceptual query size.
  • Some single-DBMS executions exhaust MM-quecat memory, while Q15, Q17, and Q18 fail functionally in the heterogeneous prototype path.
  • Native query execution and transfer plus intermediate-result processing dominate, while planning and final result construction are generally at least one order of magnitude smaller.

5.3. Overall Optimization Impact

Cumulative optimization reduces cross-model overhead through predicate pushdown, dependent joins, and non-redundant construction, with effectiveness determined by physical decomposition and native capabilities. Pushdown has the broadest impact, while the other techniques target selected plans.

  • Predicate pushdown has a broad effect across environments, whereas dependent joins and non-redundant construction affect only plans retaining external joins or larger mandatory-kind groups.
  • Up to two orders of magnitude of latency reduction occurs for individual query–environment combinations with predicate pushdown.
  • Predicate pushdown prevents all out-of-memory failures observed in the original single-DBMS experiments.
  • Dependent joins provide approximately one additional order of magnitude improvement at maximum for selected MongoDB and heterogeneous queries.
  • Dependent execution is retained as an ordinary join when generated restrictions would exceed configured or DBMS-imposed limits.
  • Non-redundant construction improves the largest Neo4j plans by approximately one order of magnitude, mainly through reduced planning time.

5.4. Per-Query Behavior

Per-query effects vary with the environment because mappings induce different physical decompositions and native capabilities. Predicate pushdown, dependent joins, and non-redundant construction therefore apply to different query classes and plans.

  • MongoDB: Dependent joins primarily improve MongoDB queries Q10–Q19 that join multiple MongoDB kinds, except Q12 because its independent result is too large.
  • Heterogeneous environment: Heterogeneous mappings cause different queries to benefit from optimization because they induce different decompositions and cross-system joins.
  • Neo4j: Neo4j receives its main additional benefit from non-redundant query-part construction.
  • Applicability conditions: Predicate pushdown benefits restrictive filters that the selected native query builder can translate.
  • Applicability conditions: Dependent joins benefit external equality joins with one sufficiently small input and a restrictive set of join values.
  • Applicability conditions: Optimization applicability depends on the conceptual query together with its physical realization, so the same MMQL query may require different techniques under different mappings.

5.5. Planning-Time Impact

Non-redundant query-part construction sharply reduces planning time as the number of queried Neo4j kinds grows, although the comparison is limited to the evaluated plans.

  • Planning-time scaling: Almost 600 milliseconds of planning time for the evaluated eight-kind plan falls to several milliseconds after mandatory patterns are added jointly.The optimization removes redundant insertion-order permutations in the evaluated mandatory-pattern cases.
  • Planning-time scaling: Planning overhead becomes significant for queries decomposed into many mandatory kinds, whereas it is less important for smaller plans.For smaller plans, several milliseconds may be hidden by longer execution time.

5.6. Performance after Optimization

Optimization moves work closer to the underlying DBMSs, improving most successful executions while leaving cross-part joins as the main expensive cases. Selecting the best physical representation per query shows additional potential, but the reported oracle is not a runtime strategy.

  • Overall performance: Most successful optimized executions take several milliseconds to several hundred milliseconds, although Q12 remains above one second in some environments.Figure 16 compares the original and fully optimized configurations.
  • Operator placement: Predicate pushdown can delegate a complete operation to one DBMS, while more complex queries remain dominated by native execution and data transfer.The pipeline is designed to move work from the unifying layer to specialized engines closer to the data.
  • Physical representations: Each single-DBMS environment is fastest for at least some queries after optimization, indicating that physical representations have query-specific advantages.No single evaluated representation is uniformly best.
  • Remaining bottlenecks: Cross-part joining remains the main bottleneck when neither join input is sufficiently small to support dependent restriction.Further improvements require broader join ordering, source and mapping selection, or alternative strategies for large intermediate results.
  • Mapping selection: Approximately 20% lower workload-wide mean latency is achieved by a post-hoc oracle relative to the best fixed single-DBMS environment.The oracle selects the environment with the lowest measured mean latency for each query; this is an upper bound, not implemented runtime selection.
  • Design principle: The overall design principle is to minimize processing after native query boundaries by reducing data early, using dependent restrictions, and avoiding redundant plan alternatives.These techniques target work otherwise performed by the decomposition-based unifying processor.

5.8. Threats to Validity

The evaluation is bounded by a controlled read-only workload, a single-machine deployment, cumulative optimization configurations, and implementation-specific limitations. These constraints limit how broadly the measured results should be generalized.

  • Dataset and workload: The workload contains 20 read-only queries over a supported MMQL subset and omits updates, complex aggregations, optional joins, and analytical workloads.The data come from a real application schema but do not reproduce complete production distributions, correlations, or irregularities.
  • Dataset and workload: The workload is a controlled set inspired by application query structures rather than a trace of production executions.Initial language-model-generated queries were filtered and manually completed.
  • Experimental environment: All systems run in Docker containers on one physical machine, so the measurements exclude the higher and more variable latency of physically distributed deployment.The setup includes interprocess communication, driver overhead, conversion, and serialization.
  • Experimental environment: Single-machine resource contention means the measured values characterize the complete selected deployment rather than isolated DBMS performance.A physically distributed deployment could increase the importance of reducing transferred intermediate results.
  • Measurement: The figures report means after four warm-ups and twenty measured executions without full latency distributions or confidence intervals.Observed variability did not change the qualitative comparisons.
  • Optimization isolation: Cumulative configurations do not provide a complete factorial analysis, and the dependent-join effect assumes predicate pushdown is already enabled.Successive differences therefore represent incremental effects in one fixed order.
  • Prototype limitations: Three heterogeneous queries fail from implementation errors, while several original single-DBMS executions fail from memory exhaustion and are excluded rather than estimated.The reported conclusions therefore depend on successful executions.
  • Prototype limitations: The lightweight estimator and limited non-redundant construction restrict the conclusions to the evaluated implementation and successful query–environment combinations.Non-redundant construction covers only joint addition of mandatory patterns.

6. Related Work

The paper integrates established optimization principles into a mapping-driven, decomposition-based multi-model processor. Its distinction lies in applying these techniques across unified conceptual plans, explicit mappings, and heterogeneous native capabilities rather than introducing new standalone principles.

  • Positioning: Predicate pushdown, dependent execution, cardinality estimation, and search-space reduction are established techniques; the contribution is their integration in a decomposition-based multi-model processor.The processor expresses operators over a unified conceptual schema, assigns them to physical mappings, and translates them into native queries.
  • Optimization setting: Query optimization must account for rapidly growing plan alternatives as well as data placement, source capabilities, communication, and intermediate-result processing.These concerns extend beyond native execution cost in distributed and heterogeneous settings.
  • Cardinality estimation: MM-quecat uses a task-specific estimator to distinguish smaller and larger dependent-join inputs rather than constructing one global cost model across PostgreSQL, MongoDB, and Neo4j.It combines observations from structurally similar query parts with available native estimates.
  • Plan construction: Non-redundant construction jointly adds mandatory mapped kinds to eliminate equivalent insertion-order permutations while preserving candidates for genuinely different physical mappings.Its search space consists of mapping-derived kind-pattern combinations rather than only conventional physical operators.
  • Predicate pushdown: Predicate pushdown is applied only when mapping coverage and native support provide the required values, operators, data types, and structural access paths.Otherwise, the predicate remains in the unifying layer.
  • Dependent execution: Dependent restrictions are represented over unified-QEP variables and can propagate through heterogeneous subtrees before translation into native query parts.The dependent side may contain model-independent operators and several native query parts.
  • Architectural distinction: Unlike other unified-language and polystore systems, this architecture derives physical query parts from explicit mappings over one conceptual schema and optimizes mapping combinations.The paper addresses optimization after a unified query enters mapping-driven processing rather than introducing another query language.
  • Evaluation scope: The evaluation isolates three optimization mechanisms inside one decomposition-based processor rather than introducing a benchmark or comparing complete multi-model systems.It separately measures planning, native execution and retrieval, intermediate-result processing, and final result construction.

7. Conclusion

The evaluated architecture shows that a substantial part of the cross-model tax comes from avoidable unifying-layer decisions rather than heterogeneity itself. A mapping- and capability-aware pipeline reduces this overhead by delegating work, coordinating dependent execution, and avoiding redundant construction.

  • Optimization pipeline: The pipeline applies model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction across heterogeneous DBMS boundaries.Filters move into native queries, dependent joins restrict later retrieval, and mandatory kind patterns avoid equivalent insertion orders.
  • Evaluation results: Up to two orders of magnitude lower latency and elimination of all observed out-of-memory failures demonstrate the practical impact of predicate pushdown.These results were observed for individual query–environment combinations and in the single-DBMS experiments, respectively.
  • Evaluation results: Dependent execution provided further improvements of up to one order of magnitude when one externally evaluated join input strongly restricted the other.The improvement depended on the join input substantially restricting the other input before retrieval.
  • Evaluation results: Non-redundant construction reduced planning time for the largest evaluated Neo4j plans from almost 600 milliseconds to several milliseconds.The optimization removes redundant permutations of mandatory kind patterns during query-part construction.
  • Conclusion: The results indicate that a dominant part of the performance penalty came from work after DBMS boundaries, including native output, transfer, conversion, and unifying-layer processing.Moving filters and dependent restrictions closer to the data changed several previously unsuccessful executions into executable ones.
  • Generalization: These principles require coordination across representations and execution domains because applicability depends on semantics, mappings, native capabilities, and DBMS boundaries.The study frames multi-model optimization as coordinated application of established principles rather than a separate set of local heuristics.
  • Limitations: The study is limited to select–project–join queries with filters, synthetic transactional data, and a prototype deployed on one physical machine.The estimator is lightweight, and evaluation on real workloads and physically distributed deployments remains needed.
  • Implication: The cross-model tax is presented as an optimization problem that can exploit native database optimizers when semantics, mappings, capabilities, and boundaries are explicit.The conclusion treats unified access overhead as reducible rather than a fixed price of heterogeneity.
Loading 2609.05014v1…