# MICRO: A Lightweight Middleware for Optimizing Cross-store Cross-model Graph-Relation Joins [Technical Report]

arXiv: https://arxiv.org/abs/2603.13835 · HTML: https://mlsanity.com/paper/2603.13835/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 58 references that are in the map.
- First posted on arXiv 14 Mar 2026.

## Builds on (most cited first, 20 of 20)

- [OpenAlex: A fully-open index of scholarly works, authors, venues, institutions, and concepts](https://mlsanity.com/paper/2205.01833/) (2022)
- [Neo: A Learned Query Optimizer](https://mlsanity.com/paper/1904.03711/) (2019)
- [Learned Cardinalities: Estimating Correlated Joins with Deep Learning](https://mlsanity.com/paper/1809.00677/) (2018)
- [Bao: Learning to Steer Query Optimizers](https://mlsanity.com/paper/2004.03814/) (2020)
- [An End-to-End Learning-based Cost Estimator](https://mlsanity.com/paper/1906.02560/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Lero: A Learning-to-Rank Query Optimizer](https://mlsanity.com/paper/2302.06873/) (2023)
- [FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation](https://mlsanity.com/paper/2011.09022/) (2020)
- [Are We Ready For Learned Cardinality Estimation?](https://mlsanity.com/paper/2012.06743/) (2020)
- [Balsa: Learning a Query Optimizer Without Expert Demonstrations](https://mlsanity.com/paper/2201.01441/) (2022)
- [Zero-Shot Cost Models for Out-of-the-box Learned Cost Prediction](https://mlsanity.com/paper/2201.00561/) (2022)
- [Data Integration in Causal Inference](https://mlsanity.com/paper/2110.01106/) (2021)
- [BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation](https://mlsanity.com/paper/2012.14743/) (2020)
- [A Unified Transferable Model for ML-Enhanced DBMS](https://mlsanity.com/paper/2105.02418/) (2021)
- [Efficient Deep Learning Pipelines for Accurate Cost Estimations Over Large Scale Query Workload](https://mlsanity.com/paper/2103.12465/) (2021)
- [AutoCE: An Accurate and Efficient Model Advisor for Learned Cardinality Estimation](https://mlsanity.com/paper/2409.16027/) (2024)
- [The BigDAWG Polystore System and Architecture](https://mlsanity.com/paper/1609.07548/) (2016)
- [Formalising opencypher Graph Queries in Relational Algebra](https://mlsanity.com/paper/1705.02844/) (2017)
- [Towards an Integrated Graph Algebra for Graph Pattern Matching with Gremlin (Extended Version)](https://mlsanity.com/paper/1908.06265/) (2019)
- [Joining Entities Across Relation and Graph with a Unified Model](https://mlsanity.com/paper/2401.18019/) (2024)

## Abstract (arXiv)

Modern data applications increasingly involve heterogeneous data managed in different models and stored across disparate database engines, often deployed as separate installs. Limited research has addressed cross-model query processing in federated environments. This paper takes a step toward bridging this gap by: (1) formally defining a class of cross-model join queries between a graph store and a relational store by proposing a unified algebra; (2) introducing one real-world benchmark and four semi-synthetic benchmarks to evaluate such queries; and (3) proposing a lightweight middleware, MICRO, for efficient query execution. At the core of MICRO is CMLero, a learning-to-rank-based query optimizer that selects efficient execution plans without requiring exact cost estimation. By avoiding the need to materialize or convert all data into a single model, which is often infeasible due to third-party data control or cost, MICRO enables native querying across heterogeneous systems. Experimental results on the benchmark workloads demonstrate that MICRO outperforms the state-of-the-art federated relational system XDB by up to 2.1x in total runtime across the full test set. On the 93 test queries of real-world benchmark, 14 queries achieve over 100 speedup, including 4 queries with more than 100x speedup; however, 4 queries experienced slowdowns of over 5 seconds, highlighting opportunities for future improvement of MICRO. Further comparisons show that CMLero consistently outperforms rule-based and regression-based optimizers, highlighting the advantage of learning-to-rank in complex cross-model optimization.