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

Problem

• The cross-model tax arises from decomposition, translation, data transfer, intermediate-result processing, and unifying-layer operations, which can dominate native query execution.Late filtering, independently retrieved join inputs, and redundant query-part exploration are identified as major avoidable costs.Source: §1 · pp. 2–3

Approach

• The proposed pipeline combines model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction using mappings, native capabilities, and unifying-layer costs.Lightweight query-driven cardinality estimates orient dependent joins, while mandatory kind patterns avoid equivalent insertion-order exploration.Source: §1 · pp. 3–5

Method

• Optimization transformations apply only when mappings provide required values and native query builders support complete conditions, while dependent restrictions can cross models, operators, databases, and native languages.Construction pruning removes only provably equivalent paths and preserves genuinely distinct physical alternatives.Source: §1 · p. 4

Implementation and scope

• The complete pipeline is implemented in MM-quecat and evaluated with PostgreSQL, MongoDB, Neo4j, and heterogeneous combinations across relational, document, and graph representations.MM-quecat separates conceptual processing, mapping selection, native query generation, database execution, and unifying-layer processing.Source: §1 · pp. 4–5

Results

• Predicate pushdown cuts latency by up to two orders of magnitude, eliminates all observed single-DBMS out-of-memory failures, dependent execution adds up to one order of magnitude, and planning falls from almost 600 milliseconds to several milliseconds.These results concern the evaluated MM-quecat architecture and its predicate, dependent-join, and non-redundant-construction techniques.Source: §1 · p. 5

Implication

• The approach shifts the unifying layer from centrally processing complete native results to coordinating database capabilities and retaining only operations that cannot be delegated.It reduces avoidable heterogeneity costs without removing the unavoidable cost of heterogeneous data management.Source: §1 · p. 6

2.1. Heterogeneous Data Models

• Different data models and DBMS capabilities determine which conceptual operations can be evaluated locally, requiring joint reasoning about representations and execution capabilities.Relational, document, and graph systems differ in data representation and in the operations they can delegate efficiently.Source: §2.1 · pp. 6, 8

2.2. Unified Schema and Mappings

• MM-cat separates a unified conceptual schema from physical representations through mappings whose model-specific properties enable different filtering, joining, and projection opportunities.Mappings connect conceptual fragments to DBMS-managed records, including scalar values, arrays, references, and nested structures.Source: §2.2 · pp. 8–9

2.3. Multi-Model Query Language

• MMQL lets users query the unified schema without selecting physical mappings, data models, DBMSs, or native query languages, then normalizes patterns and restrictions for planning.The language supports graph-inspired patterns, filters, optional patterns, set operations, aggregations, ordering, and result-size restrictions.Source: §2.3 · p. 10

2.4. Decomposition-Based Query Execution

• Decomposition-based execution identifies mappings, constructs candidate query parts and plans, runs translated SQL, MongoDB, or Cypher queries, and processes remaining operations in a unifying layer.Results are converted into a common hierarchical representation, requiring transfer and conversion when operations span heterogeneous DBMSs.Source: §2.4 · pp. 11–12, §2.3 · p. 11
• The proposed optimization targets late predicates, independent cross-model join retrieval, and redundant query-part construction through predicate pushdown, dependent joins, and non-redundant planning.These techniques move applicable filters into native query parts, introduce information flow between plan branches, and remove equivalent planning paths while preserving distinct physical alternatives.Source: §2.4 · p. 12

3. Cross-Model Query Optimization

• The unified pipeline applies predicate pushdown, dependent joins, and non-redundant query-part construction when mappings, capabilities, and conceptual semantics permit the optimization.Operators are expressed over a unified schema, assigned to mapped query parts, and translated into SQL, MongoDB aggregation pipelines, or Cypher.Source: §3 · p. 13

3.2. Model-Aware Predicate Pushdown

• Predicate pushdown moves filters toward native query parts, reducing transferred intermediate results and subsequent processing when required variables, mappings, and DBMS operators are supported.Filters move through model-independent operators before translation into SQL, MongoDB aggregation, or Cypher; otherwise they remain at the deepest valid unifying-layer position.Source: §3.2 · p. 14, §3.2.2 · p. 15

3.2.1. Transformation Rules

• Pushdown is restricted to semantics-preserving transformations, including inner joins when all filter variables belong to one input; outer-join movement is excluded.A filter may move into a subtree only when that subtree provides every referenced variable and the parent-operator transformation remains valid.Source: §3.2 · p. 14, §3.2.1 · pp. 14–15

3.3. Cross-Model Dependent Joins

• A dependent join evaluates one input first and uses distinct join values to restrict the other before retrieval, preserving the original join result while reducing remote work.The restriction can flow through a complete model-independent subtree and be translated at different native leaves; unsupported cases retain the original join.Source: §3.3 · pp. 16–17, §3.3.1 · p. 17

3.3.2. Orientation and Applicability

• Dependent joins choose the smaller estimated input as independent when possible and require equality joins, delegable restrictions, bounded independent results, and target-DBMS query-size compliance.Applicability is rechecked during execution, with fallback to the original join when estimates are inaccurate or restrictions become too large.Source: §3.3.2 · pp. 18–19

3.3.3. Cardinality Information

• Join orientation uses heterogeneous native estimates and prior execution observations to distinguish smaller from larger inputs without duplicating complete model-specific cost models.The lightweight estimator combines source-provided cardinality or cost signals with observations from structurally similar previous plans.Source: §3.3.3 · p. 19

3.4. Non-Redundant Query-Part Construction

• Non-redundant construction adds all mandatory kind patterns together, reducing exploration from up to k! equivalent insertion orders to one continuation while preserving distinct physical alternatives.Only patterns with redundancy score 1 are merged; candidates representing alternative mappings remain separate.Source: §3.4 · pp. 19–21

3.5. Optimization Scope

• The evaluated scope covers select–project–join queries over PostgreSQL, MongoDB, and Neo4j; projection, aggregation, sorting, limiting, broader cost models, and unsupported native operations remain outside scope.Pushdown and dependent joins require translatable native conditions, while non-redundant construction applies only to mandatory kind patterns with redundancy score 1.Source: §3.5 · p. 21

4. Implementation

• MM-quecat extends MM-cat’s bottom-up pipeline with mapping-aware QEP transformations, capability-aware native-query generation, and controlled top-down information flow across PostgreSQL, MongoDB, and Neo4j.The techniques share one QEP representation and one translation boundary between model-independent planning and native SQL, MongoDB, and Cypher execution.Source: §4 · pp. 21–22

4.1. Query-Plan Representation

• The extended QEP representation distinguishes unifying-layer filters from DBMS-executed filters, enabling predicate pushdown, dependent-join planning, and native-query generation within one mutable plan structure.Datasource nodes store patterns and delegated filters, while standalone filters remain in the unifying layer.Source: §4.1 · pp. 22–23

4.2. Native Query Generation

• Native builders translate complete supported conditions into SQL, MongoDB aggregation pipelines, or Cypher, delegating operations only when mappings provide required values and capabilities permit translation.The same interface handles statically pushed filters and dynamically generated dependent restrictions.Source: §4.2 · p. 23

4.3. Predicate Pushdown

• Predicate pushdown deterministically moves filters toward leaves when referenced variables are available and the target builder supports the complete condition, while preserving semantically valid positions otherwise.The evaluated implementation permits movement through inner joins but leaves optional joins, set operations, and null- or unmatched-record-dependent transformations unchanged.Source: §4.3 · pp. 23–24

4.4. Dependent Joins

• Dependent joins orient equality joins using estimated cardinalities, execute the smaller branch first, and propagate runtime restrictions through arbitrary dependent subtrees to suitable native query parts.If runtime results exceed the configured limit or no node can consume the restriction, execution safely falls back to the original non-dependent strategy.Source: §4.4 · p. 24

4.5. Query-Driven Cardinality Estimation

• The lightweight cardinality estimator combines cached observations with source-specific PostgreSQL, MongoDB, and Neo4j planning information solely to select the independent dependent-join input.Native signals are not treated as one comparable global cost because their semantics and scales differ.Source: §4.5 · pp. 24–25

4.6. Non-Redundant Query-Part Construction

• Non-redundant construction jointly adds all mandatory patterns with redundancy score 1, eliminating their insertion-order permutations while preserving branching for genuinely different alternatives.Planning improvements therefore come from joint mandatory-pattern addition rather than complete duplicate-state elimination.Source: §4.6 · pp. 25–26

4.7. Implemented Scope

• The evaluated scope covers select–project–join queries with filters, equality-based dependent joins, translatable restrictions, bounded independent results, and mandatory score-1 patterns; unsupported or unsafe cases remain or fall back to the original plan.The implementation is not a complete heterogeneous cost-based optimizer.Source: §4.7 · p. 26

5. Experimental Evaluation

• The evaluation covers end-to-end latency, processing phases, incremental optimization effects, and query or mapping properties within MM-quecat’s decomposition-based architecture.Results characterize the evaluated architecture, dataset, and supported MMQL subset rather than all multi-model database systems.Source: §5 · pp. 26–27

5.1.1. Dataset and Mappings

• The dataset uses a 70-object, 90-morphism Cal.com schema subset mapped completely to PostgreSQL, MongoDB, and Neo4j.The mappings contain 8 MongoDB, 25 PostgreSQL, and 55 Neo4j mappings; identifier properties are indexed, while other properties are not.Source: §5.1.1 · p. 27
• Four environments compare PostgreSQL-only, MongoDB-only, Neo4j-only, and heterogeneous execution over disjoint schema portions without redundant mappings.This isolates cross-system execution while avoiding additional mapping alternatives from replicated representations.Source: §5.1.1 · p. 27
• The synthetic dataset contains approximately 2,000,000 conceptual records but does not reproduce all correlations, skew, or irregularities of production Cal.com data.Records are transformed into each mapped physical representation and loaded into the corresponding DBMS.Source: §5.1.1 · p. 28

5.1.2. Workload

• The workload contains 20 predominantly parameterized MMQL select–project–join queries derived from Cal.com structures and manually extended with complex graph patterns.The final workload combines application-derived structures with controlled additions rather than constituting a directly generated benchmark.Source: §5.1.2 · p. 28
• Queries Q15, Q17, and Q18 failed in the heterogeneous environment because of prototype execution errors and were excluded from comparisons without estimated replacements.All other query–environment combinations completed without functional errors, although some unoptimized executions exhausted available memory.Source: §5.1.2 · pp. 28–29

5.1.3. Execution Protocol

• Measurements report mean latency after four warm-up and twenty measurement executions, covering planning, native execution and transfer, intermediate processing, and final result construction.Native execution and transfer are combined, so network transfer is not isolated from DBMS execution.Source: §5.1.3 · pp. 29–30
• The cumulative configurations enable the original implementation, predicate pushdown, dependent joins, and all implemented optimizations in sequence rather than as a factorial combination study.The reported dependent-join effect therefore assumes predicate pushdown is already enabled.Source: §5.1.3 · p. 30

Baseline latency

• Mean query latency ranged from less than ten milliseconds to more than ten seconds across the four pre-optimization environments.Figure 6 compares the environments, with missing values denoting failed executions.Source: Figure 6 · p. 31, §5.2 · p. 31
• Latency differences reflected physical decomposition, returned-data volume, and retained joining, while Neo4j was generally slower and the heterogeneous environment was not systematically faster.PostgreSQL and MongoDB were lowest for different queries; similar heterogeneous and single-DBMS latencies often used the same underlying DBMS.Source: §5.2 · p. 31

Execution failures

• Some Q15 and Q18 executions exhausted MM-quecat memory, while heterogeneous-environment executions of Q15, Q17, and Q18 failed in the original prototype path.These failures prevented those queries from being included in optimization comparisons.Source: §5.2 · p. 31, Table 5 · p. 31

Processing bottlenecks

• Native execution and transfer plus intermediate-result processing dominated phase time, whereas planning and final result construction were generally at least one order of magnitude smaller.Figure 7 illustrates these phase-level measurements for the unoptimized heterogeneous environment.Source: §5.2 · pp. 31–32, Figure 7 · p. 32

Optimization targets

• The dominant cross-model tax motivates predicate pushdown and dependent joins, while query-part construction matters for plans decomposed into many physical kinds.These optimizations target retrieved-data volume, transfer, conversion, and unifying-layer processing.Source: §5.2 · p. 32

5.3. Overall Optimization Impact

• Optimization effectiveness depends on physical decomposition: pushdown broadly helps, whereas dependent joins and non-redundant construction target plans retaining external joins or larger mandatory-kind groups.Figures 8–11 compare latency distributions across four cumulative configurations rather than matching queries point by point.Source: §5.3 · p. 32

5.3.1. Predicate Pushdown

• Predicate pushdown reduces latency by up to two orders of magnitude and eliminates all observed out-of-memory failures in the original single-DBMS experiments.It reduces native output and downstream transfer, conversion, joining, and result processing by incorporating restrictive predicates into native queries; gains are smaller when cross-model joins remain dominant.Source: §5.3.1 · pp. 32, 35

5.3.2. Dependent Joins

• Dependent joins improve selected MongoDB and heterogeneous plans by approximately one order of magnitude when small, selective join inputs restrict the other input.They do not affect PostgreSQL or Neo4j plans whose relevant joins are already native, and conservative limits retain ordinary joins when generated restrictions would be excessive.Source: §5.3.2 · p. 35

5.3.3. Non-Redundant Query-Part Construction

• Non-redundant construction improves largest Neo4j plans by approximately one order of magnitude, mainly through reduced planning time, while having little visible effect elsewhere.Its strongest effect occurs when mappings produce plans with up to eight kinds; PostgreSQL, MongoDB, and heterogeneous plans access at most 5, 3, and 6 kinds, respectively.Source: §5.3.3 · pp. 35–36

• Dependent joins primarily improve MongoDB queries Q10–Q19, except Q12 because its independent result is too large for the generated restriction.These queries require joins across multiple MongoDB kinds.Source: §5.4 · p. 36, Figure 12 · p. 36
• Different heterogeneous queries benefit because mappings induce different decompositions and cross-system joins, so applicability cannot be inferred from the conceptual query alone.Source: §5.4 · p. 36, Figure 13 · p. 37
• In Neo4j, the main additional benefit comes from non-redundant query-part construction.Source: §5.4 · p. 36, Figure 14 · p. 37
• Optimization applicability is determined by conceptual query properties, mapping structure, and native capabilities rather than the conceptual query alone.The same MMQL query may require different techniques under different mappings.Source: §5.4 · pp. 37–38
• Predicate pushdown favors restrictive translatable filters, dependent joins favor small-input equality joins with restrictive join values, and non-redundant construction favors many mandatory physical kinds.Source: §5.4 · pp. 37–38

5.5. Planning-Time Impact

• Almost 600 milliseconds for the evaluated eight-kind plan falls to several milliseconds after mandatory patterns are added jointly.Figure 15 compares planning time before and after non-redundant query-part construction.Source: §5.5 · p. 38, Figure 15 · p. 38
• Planning time rises substantially with the number of Neo4j kinds accessed, consistent with the analyzed combinatorial behavior.The optimized procedure removes redundant insertion-order permutations in the evaluated mandatory-pattern cases.Source: §5.5 · pp. 38–39
• Planning overhead is minor for smaller plans but becomes significant when one representation decomposes a conceptual query into many mandatory kinds.For smaller plans, saving several milliseconds may be hidden by longer execution time.Source: §5.5 · pp. 38–39
• Figure 15 compares evaluated plans rather than establishing a controlled scalability law because the queries differ in properties beyond their accessed-kind count.This limitation qualifies interpretation of the relationship between planning time and the number of Neo4j kinds.Source: Figure 15 · p. 38, §5.5 · p. 39

5.6. Performance after Optimization

• Most successful optimized executions require several milliseconds to several hundred milliseconds, although Q12 remains above one second in some environments.Figure 16 compares original and fully optimized configurations, with “old” denoting the original configuration and the remaining series denoting the fully optimized configuration.Source: §5.6 · p. 39, Figure 16 · p. 39
• Predicate pushdown can delegate complete operations to one DBMS, while more complex queries remain dominated by native execution and data transfer.The pipeline moves work from MM-quecat’s generic unifying layer to specialized engines closer to the data.Source: §5.6 · p. 39
• After optimization, each single-DBMS environment achieves the lowest latency for at least some queries, showing that physical model strengths depend on query structure.Relational, document, and graph representations can each be advantageous once excessive intermediate processing no longer obscures their native strengths.Source: §5.6 · p. 39
• Cross-part joining remains the main bottleneck when neither join input is small enough to support dependent restriction, particularly for Q12.Further improvements require broader join ordering, source and mapping selection, or alternative strategies for transferring and combining large intermediate results.Source: §5.6 · p. 40

5.7. Potential of Mapping Selection

• Approximately 20% lower workload-wide mean latency is achieved by a post-hoc oracle selecting the fastest single-DBMS environment per query.Figure 17 compares optimized single-DBMS performance with this oracle; the result is not an implemented runtime-selection strategy.Source: §5.7 · p. 40, Figure 17 · p. 40
• The oracle’s improvement is an upper bound from observed executions rather than achieved runtime-selection performance.No single evaluated physical representation is uniformly best, motivating cost-based selection among redundant mappings as a complementary next step.Source: §5.7 · p. 41
• Decomposition-based multi-model processors should minimize work after native query boundaries by reducing data early, using dependent restriction, and avoiding redundant alternatives.These principles complement the evaluated operator-placement and plan-construction techniques.Source: §5.7 · p. 41

Dataset and workload

• The workload comprises 20 read-only queries over a controlled application-inspired dataset and excludes updates, complex aggregations, optional joins, and analytical workloads.The data do not reproduce production Cal.com distributions, correlations, or irregularities, and the workload covers only the MMQL subset supported by MM-quecat.Source: §5.8 · p. 41

Experimental environment

• All systems run in Docker containers on one physical machine, so measurements include local overheads but not the higher, more variable latency of physical distribution.The single-machine setup may also create resource contention between MM-quecat and the participating DBMSs; measured values characterize the complete deployment rather than isolated DBMS performance.Source: §5.8 · p. 41

Measurement and optimization isolation

• Reported latencies are means over twenty measured executions after four warm-ups, without full latency distributions or confidence intervals.Observed standard deviations were small enough not to affect the qualitative conclusions.Source: §5.8 · p. 42
• Cumulative optimization configurations show incremental effects in one fixed order rather than a complete factorial analysis, and dependent-join effects assume predicate pushdown is enabled.Consequently, individual optimization effects are not isolated across all configuration combinations.Source: §5.8 · p. 42

Prototype limitations

• Three heterogeneous-environment queries fail from implementation errors, while several original single-DBMS executions fail from memory exhaustion and are excluded rather than estimated.The lightweight cardinality estimator and limited non-redundant construction further restrict conclusions to the evaluated implementation and successful query–environment combinations.Source: §5.8 · p. 42

6. Related Work

• MM-quecat integrates predicate pushdown, dependent execution, and search-space reduction across conceptual schemas, physical mappings, and native relational, document, and graph capabilities.Optimization decisions must preserve conceptual semantics while respecting mapping coverage and native DBMS capabilities.Source: §6 · p. 42, §6.4 · p. 45

6.1. Query-Plan Construction and Estimation

• MM-quecat uses task-specific observations and native estimates to orient dependent joins rather than constructing one global cost model across PostgreSQL, MongoDB, and Neo4j.Mandatory mapping-derived kinds are added jointly, eliminating redundant construction permutations while retaining candidates for genuinely different mappings.Source: §6.1 · p. 43

6.2. Predicate Pushdown and Dependent Joins

• Predicates are pushed into SQL, MongoDB aggregation, or Cypher only when mappings provide the needed values and native builders support the complete condition.Dependent restrictions propagate through heterogeneous QEP subtrees and retain the original join as a safe fallback; effectiveness depends on input size and selectivity.Source: §6.2 · pp. 43–44

6.3. Multi-Model Languages and Systems

• Unlike multi-model languages and polystore optimizers that coordinate heterogeneous engines, MM-quecat optimizes mapping-derived query parts over one conceptual schema before native translation.Its non-redundant construction operates over combinations of mappings, while pushdown and dependent execution remain constrained by mapping coverage and target capabilities.Source: §6.3 · pp. 44–45

6.4. Evaluation and Positioning

• The evaluation isolates three optimization mechanisms within one decomposition-based processor rather than introducing a benchmark or comparing complete multi-model systems.It separately measures planning, combined native execution and retrieval, intermediate-result processing, and final result construction.Source: §6.4 · p. 45

Optimization approach

• The pipeline combines model-aware predicate pushdown, cross-model dependent joins, and non-redundant query-part construction across mappings, capabilities, and execution boundaries.A lightweight query-driven cardinality estimator supports dependent-join orientation without replacing the heterogeneous cost models of underlying systems.Source: §7 · p. 46

Results

• Almost 600 milliseconds fell to several milliseconds for the largest evaluated Neo4j plans through non-redundant construction of mandatory kind patterns.The optimization avoids exploring equivalent insertion orders.Source: §7 · p. 46
• Up to two orders of magnitude lower latency, no observed single-DBMS out-of-memory failures, and previously unsuccessful executions becoming executable demonstrate the pipeline’s overall benefit.Predicate pushdown reduced native output, transfer, conversion, and unifying-layer processing; dependent joins added further improvements of up to one order of magnitude under strong restriction.Source: §7 · p. 46

Implications

• Established principles remain effective in multi-model processing, but their applicability depends on conceptual semantics, mapping coverage, native capabilities, and DBMS boundaries.The paper characterizes multi-model optimization as coordination across representations and execution domains rather than a collection of local heuristics.Source: §7 · pp. 46–47

Limitations and future work

• The study is limited to select–project–join queries with filters, synthetic transactional data, and one-machine prototype deployment, motivating broader cost-based, pushdown, workload, and distributed evaluation.Future work includes source and mapping selection, broader join ordering, projections, aggregations, sorting, result-size restrictions, real workloads, and distributed deployments.Source: §7 · p. 47