{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:37:31Z","timestamp":1778279851429,"version":"3.51.4"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["61925205,62232009,62102215"],"award-info":[{"award-number":["61925205,62232009,62102215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003816","name":"Huawei Technologies","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003816","id-type":"DOI","asserted-by":"crossref"}]},{"name":"TAL education"},{"DOI":"10.13039\/501100017582","name":"Beijing National Research Center For Information Science And Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100017582","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Database partitioning is a fundamental but challenging task in distributed databases, which selects specific columns as a partitioning key for each table and uses the partitioning key to allocate the table data into different compute nodes in order to maximize the performance. However, this problem is NP-hard and existing distributed databases require users to manually specify the partitioning keys, which may cause potential performance degradation. Although reinforcement learning based methods have been proposed, they have several limitations. First, they do not capture the complex data distributions and query access patterns, and thus involve high computation cost across different compute nodes to answer a query. Second, they involve an expensive step to repetitively partition the data into different compute nodes in order to train a learned key-selection model, which is a waste of time and resources. To address these limitations, we propose a practical learned database partitioning system Grep. We first adopt a graph model to encode data and query features, where vertices are columns, edges are query relations, and the weights of columns are computed based on the localized graph structures (e.g., data diversity, joined columns). We then utilize graph neural networks to embed the partitioning factors into embedding vectors in order to capture the data and query correlations. Next we propose a key-selection model to select appropriate partitioning keys based on the graph model. Finally, we propose an evaluation model to estimate the partitioning performance without actually partitioning the database. We have implemented Grep in a commercial distributed database, and experiments show the effectiveness of our system (e.g., 68% higher throughput for 30K queries in a real banking scenario).<\/jats:p>","DOI":"10.1145\/3588948","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-24","source":"Crossref","is-referenced-by-count":13,"title":["Grep: A Graph Learning Based Database Partitioning System"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2285-7836","authenticated-orcid":false,"given":"Xuanhe","family":"Zhou","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1398-0621","authenticated-orcid":false,"given":"Guoliang","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0537-7083","authenticated-orcid":false,"given":"Jianhua","family":"Feng","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-1198-9985","authenticated-orcid":false,"given":"Luyang","family":"Liu","sequence":"additional","affiliation":[{"name":"Huawei, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5952-3515","authenticated-orcid":false,"given":"Wei","family":"Guo","sequence":"additional","affiliation":[{"name":"Huawei, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"[n. d.]. aws.amazon.com\/cn\/blogs\/big-data\/amazon-redshift-engineerings-advanced-table-design-playbook-distribution-styles-and-distribution-keys."},{"key":"e_1_2_2_2_1","unstructured":"[n. d.]. docs.microsoft.com\/en-us\/azure\/synapse-analytics\/sql-data-warehouse\/sql-data-warehouse-tables-distribute."},{"key":"e_1_2_2_3_1","unstructured":"[n. d.]. https:\/\/www.ibm.com\/docs\/en\/db2-warehouse?topic=database-choosing-hash-distribution-key."},{"key":"e_1_2_2_4_1","unstructured":"[n. d.]. https:\/\/www.snowflake.com\/wp-content\/uploads\/2014\/10\/A-Detailed-View-Inside-Snowflake.pdf."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469--8.50097--8"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","unstructured":"Joy Arulraj Andrew Pavlo and Prashanth Menon. 2016. Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads. In SIGMOD. 583--598. https:\/\/doi.org\/10.1145\/2882903.2915231","DOI":"10.1145\/2882903.2915231"},{"key":"e_1_2_2_7_1","unstructured":"Stephen Bazen and Xavier Joutard. 2013. The Taylor decomposition: A unified generalization of the Oaxaca method to nonlinear models. tech. rep. (2013)."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","unstructured":"Martin Boissier and Kurzynski Daniel. 2018. Workload-Driven Horizontal Partitioning and Pruning for Large HTAP Systems. In ICDE. https:\/\/doi.org\/10.1109\/ICDEW.2018.00026","DOI":"10.1109\/ICDEW.2018.00026"},{"key":"e_1_2_2_9_1","volume-title":"Handbook of combinatorial optimization","author":"Bomze Immanuel M","unstructured":"Immanuel M Bomze, Marco Budinich, Panos M Pardalos, and Marcello Pelillo. 1999. The maximum clique problem. In Handbook of combinatorial optimization. Springer, 1--74."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517882"},{"key":"e_1_2_2_11_1","volume-title":"Narasayya","author":"Chaudhuri Surajit","year":"2007","unstructured":"Surajit Chaudhuri and Vivek R. Narasayya. 2007. Self-Tuning Database Systems: A Decade of Progress. In VLDB. ACM, 3--14. http:\/\/www.vldb.org\/conf\/2007\/papers\/special\/p3-chaudhuri.pdf"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","unstructured":"Carlo Curino Yang Zhang Evan P. C. Jones and et al. 2010. Schism: a Workload-Driven Approach to Database Replication and Partitioning. VLDB (2010). https:\/\/doi.org\/10.14778\/1920841.1920853","DOI":"10.14778\/1920841.1920853"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565857"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--30278--8_16"},{"key":"e_1_2_2_15_1","unstructured":"David Duvenaud Dougal Maclaurin Jorge Aguilera-Iparraguirre and et al. 2015. Convolutional Networks on Graphs for Learning Molecular Fingerprints. In NIPS. http:\/\/papers.nips.cc\/paper\/5954-convolutional-networks-on-graphs-for-learning-molecular-fingerprints"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376727"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1953122.1953146"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012088469--8.50052--8"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749438"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","unstructured":"Herodotos Herodotou Nedyalko Borisov and Shivnath Babu. 2011. Query optimization techniques for partitioned tables. In SIGMOD. https:\/\/doi.org\/10.1145\/1989323.1989330","DOI":"10.1145\/1989323.1989330"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","unstructured":"Benjamin Hilprecht Carsten Binnig and Uwe R\u00f6hm. 2019. Towards learning a partitioning advisor with deep reinforcement learning. In aiDM@SIGMOD. https:\/\/doi.org\/10.1145\/3329859.3329876","DOI":"10.1145\/3329859.3329876"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"Benjamin Hilprecht Carsten Binnig and Uwe R\u00f6hm. 2020. Learning a Partitioning Advisor for Cloud Databases. In SIGMOD. https:\/\/doi.org\/10.1145\/3318464.3389704","DOI":"10.1145\/3318464.3389704"},{"key":"e_1_2_2_24_1","volume-title":"Huawei Technologies Co","year":"2022","unstructured":"Ltd. Huawei Technologies Co. 2022. Basic Knowledge of Database. In Database Principles and Technologies--Based on Huawei GaussDB. Springer, 41--86."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3314034"},{"key":"e_1_2_2_26_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017","unstructured":"Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR. https:\/\/openreview.net\/forum?id=SJU4ayYgl"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","unstructured":"Miroslaw Kordos and Andrzej Rusiecki. 2016. Reducing noise impact on MLP training - Techniques and algorithms to provide noise-robustness in MLP network training. Soft Comput. (2016). https:\/\/doi.org\/10.1007\/s00500-015--1690--9","DOI":"10.1007\/s00500-015--1690--9"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","unstructured":"Mayuresh Kunjir and Shivnath Babu. 2020. Black or White? How to Develop an AutoTuner for Memory-based Analytics. In SIGMOD. ACM 1667--1683. https:\/\/doi.org\/10.1145\/3318464.3380591","DOI":"10.1145\/3318464.3380591"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-020-00149--7"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3363574"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","unstructured":"Guoliang Li Xuanhe Zhou and Lei Cao. 2021. AI Meets Database: AI4DB and DB4AI. In SIGMOD. ACM 2859--2866. https:\/\/doi.org\/10.1145\/3448016.3457542","DOI":"10.1145\/3448016.3457542"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352129"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476380"},{"key":"e_1_2_2_35_1","unstructured":"Tie-Yan Liu. 2009. Learning to Rank for Information Retrieval. Found. Trends Inf. Retr. (2009)."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055551"},{"key":"e_1_2_2_37_1","volume-title":"Spectral-based Graph Convolutional Network for Directed Graphs. CoRR abs\/1907.08990","author":"Ma Yi","year":"2019","unstructured":"Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. 2019. Spectral-based Graph Convolutional Network for Directed Graphs. CoRR abs\/1907.08990 (2019). arXiv:1907.08990 http:\/\/arxiv.org\/abs\/1907.08990"},{"key":"e_1_2_2_38_1","unstructured":"Volodymyr Mnih Nicolas Heess Alex Graves and et al. 2014. Recurrent Models of Visual Attention. In NIPS. http:\/\/papers.nips.cc\/paper\/5542-recurrent-models-of-visual-attention"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","unstructured":"Gr\u00e9goire Montavon Sebastian Lapuschkin and Alexander Binder et al. 2017. Explaining nonlinear classification decisions with deep Taylor decomposition. Pattern Recognit. (2017). https:\/\/doi.org\/10.1016\/j.patcog.2016.11.008","DOI":"10.1016\/j.patcog.2016.11.008"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","unstructured":"Federico Monti Davide Boscaini Jonathan Masci and et al. 2017. Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In CVPR. https:\/\/doi.org\/10.1109\/CVPR.2017.576","DOI":"10.1109\/CVPR.2017.576"},{"key":"e_1_2_2_41_1","volume-title":"ICML (JMLR Workshop and Conference Proceedings). JMLR.org. http:\/\/proceedings.mlr.press\/v48\/niepert16","author":"Niepert Mathias","year":"2016","unstructured":"Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016. ICML (JMLR Workshop and Conference Proceedings). JMLR.org. http:\/\/proceedings.mlr.press\/v48\/niepert16.html"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00580-x"},{"key":"e_1_2_2_43_1","volume-title":"Christos Faloutsos, and Michalis Petropoulos.","author":"Parchas Panos","year":"2020","unstructured":"Panos Parchas, Yonatan Naamad, Peter Van Bouwel, Christos Faloutsos, and Michalis Petropoulos. 2020. Fast and Effective Distribution-Key Recommendation for Amazon Redshift. VLDB (2020), 2411--2423. http:\/\/www.vldb.org\/pvldb\/vol13\/p2411-parchas.pdf"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476411"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064052"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564757"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","unstructured":"Idan Schwartz Seunghak Yu and Tamir Hazan et al. 2019. Factor Graph Attention. In CVPR. https:\/\/doi.org\/10.1109\/CVPR.2019.00214","DOI":"10.1109\/CVPR.2019.00214"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3025111.3025125"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368296"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485459"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","unstructured":"Liwen Sun Michael J. Franklin Sanjay Krishnan and et al. 2014. Fine-grained partitioning for aggressive data skipping. In SIGMOD. https:\/\/doi.org\/10.1145\/2588555.2610515","DOI":"10.1145\/2588555.2610515"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","unstructured":"Immanuel Trummer. 2019. Exact Cardinality Query Optimization with Bounded Execution Cost. In SIGMOD Peter A. Boncz Stefan Manegold Anastasia Ailamaki and et al (Eds.). https:\/\/doi.org\/10.1145\/3299869.3300087","DOI":"10.1145\/3299869.3300087"},{"key":"e_1_2_2_53_1","unstructured":"Petar Velickovic Guillem Cucurull and Arantxa Casanova et al. 2018. Graph Attention Networks. In ICLR. https:\/\/openreview.net\/forum?id=rJXMpikCZ"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485458"},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"Junxiong Wang Immanuel Trummer and et al. 2021. Demonstrating UDO: A Unified Approach for Optimizing Transaction Code Physical Design and System Parameters via Reinforcement Learning. In SIGMOD. 2794--2797.","DOI":"10.1145\/3448016.3452754"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-022-00186--4"},{"key":"e_1_2_2_57_1","volume-title":"Yu","author":"Wu Zonghan","year":"2019","unstructured":"Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2019. A Comprehensive Survey on Graph Neural Networks. CoRR abs\/1901.00596 (2019). arXiv:1901.00596 http:\/\/arxiv.org\/abs\/1901.00596"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565846"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00116"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","unstructured":"Erfan Zamanian Carsten Binnig and Abdallah Salama. 2015. Locality-aware Partitioning in Parallel Database Systems. In SIGMOD. https:\/\/doi.org\/10.1145\/2723372.2723718","DOI":"10.1145\/2723372.2723718"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","unstructured":"Lixi Zhang Chengliang Chai Xuanhe Zhou and Guoliang Li. 2022. LearnedSQLGen: Constraint-aware SQL Generation using Reinforcement Learning. In SIGMOD. ACM 945--958. https:\/\/doi.org\/10.1145\/3514221.3526155","DOI":"10.1145\/3514221.3526155"},{"key":"e_1_2_2_62_1","doi-asserted-by":"crossref","unstructured":"Muhan Zhang Zhicheng Cui and Marion Neumann et al. 2018. An End-to-End Deep Learning Architecture for Graph Classification. In AAAI. https:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI18\/paper\/view\/17146","DOI":"10.1609\/aaai.v32i1.11782"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3266893"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2994641"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485456"},{"key":"e_1_2_2_66_1","volume-title":"AutoIndex: An Incremental Index Management System for Dynamic Workloads","author":"Zhou Xuanhe","unstructured":"Xuanhe Zhou, Luyang Liu, Wenbo Li, Lianyuan Jin, Shifu Li, Tianqing Wang, and Jianhua Feng. 2022. AutoIndex: An Incremental Index Management System for Dynamic Workloads. In ICDE. IEEE, 2196--2208."},{"key":"e_1_2_2_67_1","volume-title":"Query Performance Prediction for Concurrent Queries using Graph Embedding. VLDB","author":"Zhou Xuanhe","year":"2020","unstructured":"Xuanhe Zhou, Ji Sun, Guoliang Li, and Jianhua Feng. 2020. Query Performance Prediction for Concurrent Queries using Graph Embedding. VLDB (2020). http:\/\/www.vldb.org\/pvldb\/vol13\/p1416-zhou.pdf"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588948","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588948","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:38Z","timestamp":1750178858000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588948"],"URL":"https:\/\/doi.org\/10.1145\/3588948","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}