* [164] Y. Mao, B. Clerckx, and V. O. K. Li, “Rate-splitting for multi-antenna non-orthogonal unicast and multicast transmission,” in _Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , 2018.
  * [165] Y. Mao and B. Clerckx, “Dirty paper coded rate-splitting for non-orthogonal unicast and multicast transmission with partial CSIT,” in _Proc. 54th Asilomar Conf. Signals, Syst. Comput._ , 2020.
  * [166] L. F. Abanto-Leon, M. Hollick, B. Clerckx, and G. H. A. Sim, “Sequential parametric optimization for rate-splitting precoding in non-orthogonal unicast and multicast transmissions,” _Proc. IEEE Int. Conf. Commun. (ICC)_ , 2022.
  * [167] O. Tervo, L. Trant, S. Chatzinotas, B. Ottersten, and M. Juntti, “Multigroup multicast beamforming and antenna selection with rate-splitting in multicell systems,” in _Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , 2018.
  * [168] L. Yin and B. Clerckx, “Rate-splitting multiple access for multigroup multicast and multibeam satellite systems,” _IEEE Trans. Commun._ , vol. 69, no. 2, pp. 976–990, Feb. 2021.
  * [169] A. Z. Yalcin, M. Yuksel, and B. Clerckx, “Rate splitting for multi-group multicasting with a common message,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 10, pp. 12 281–12 285, Oct. 2020.
  * [170] H. Chen, D. Mi, Z. Liu, P. Xiao, and R. Tafazolli, “Rate-splitting for overloaded multigroup multicast: Error performance evaluation,” in _Proc. IEEE Int. Conf. Commun. (ICC) Workshop_ , 2020.
  * [171] H. Chen, D. Mi, T. Wang, Z. Chu, Y. Xu, D. He, and P. Xiao, “Rate-splitting for multicarrier multigroup multicast: Precoder design and error performance,” _IEEE Trans. Broadcast._ , vol. 67, no. 3, pp. 619–630, Sept. 2021.
  * [172] H. Chen, D. Mi, B. Clerckx, Z. Chu, J. Shi, and P. Xiao, “Joint power and subcarrier allocation optimization for multigroup multicast systems with rate splitting,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 2, pp. 2306–2310, 2020.
  * [173] L. Zhao, Y. Cui, S. Yang, and S. Shamai, “An optimization framework for general rate splitting for general multicast,” _IEEE Trans. Wireless Commun._ , pp. 1–1, 2022.
  * [174] M. Caus, A. Pastore, M. Navarro, T. Ramirez, C. Mosquera, N. Noels, N. Alagha, and A. I. Perez-Neira, “Exploratory analysis of superposition coding and rate splitting for multibeam satellite systems,” in _Proc. IEEE Int. Symp. Wireless Commun. Syst. (ISWCS)_ , 2018.
  * [175] L. Yin and B. Clerckx, “Rate-splitting multiple access for multibeam satellite communications,” in _Proc. IEEE Int. Conf. Commun. (ICC) Workshop_ , 2020\.
  * [176] Z. W. Si, L. Yin, and B. Clerckx, “Rate-splitting multiple access for multigateway multibeam satellite systems with feeder link interference,” _IEEE Trans. Commun._ , vol. 70, no. 3, pp. 2147–2162, 2022.
  * [177] M. Vazquez, M. Caus, and A. Perez-Neira, “Rate splitting for MIMO multibeam satellite systems,” in _International ITG Workshop on Smart Antennas_ , 2018\.
  * [178] S. K. Singh, K. Agrawal, K. Singh, and C.-P. Li, “Outage probability and throughput analysis of UAV-assisted rate-splitting multiple access,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 11, pp. 2528–2532, Nov. 2021\.
  * [179] A. Rahmati, Y. Yapici, N. Rupasinghe, I. Guvenc, H. Dai, and A. Bhuyan, “Energy efficiency of RSMA and NOMA in cellular-connected mmWave UAV networks,” in _Proc. IEEE Int. Conf. Commun. (ICC) Workshop_ , 2019.
  * [180] W. Jaafar, S. Naser, S. Muhaidat, P. C. Sofotasios, and H. Yanikomeroglu, “Multiple access in aerial networks: From orthogonal and non-orthogonal to rate-splitting,” _IEEE Open J. of Veh. Technol._ , vol. 1, pp. 372–392, Oct. 2020.
  * [181] ——, “On the downlink performance of RSMA-based UAV communications,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 12, pp. 16 258–16 263, Dec. 2020\.
  * [182] L. Lu, Y. Hu, Y. Zhang, G. Jia, J. Nie, and M. Shikh-Bahaei, “Machine learning for predictive deployment of uavs with rate splitting multiple access,” in _Proc. IEEE Glob. Commun. Conf. (GLOBECOM)_ , 2020.
  * [183] Z. Xiao, Z. Han, A. Nallanathan, O. A. Dobre, B. Clerckx, J. Choi, C. He, and W. Tong, “Antenna array enabled space/air/ground communications and networking for 6G,” _IEEE J. Sel. Areas Commun._ , vol. 40, no. 10, pp. 2773–2804, 2022.
  * [184] L. Yin and B. Clerckx, “Rate-splitting multiple access for satellite-terrestrial integrated networks: Benefits of coordination and cooperation,” _IEEE Trans. Wireless Commun._ , pp. 1–1, 2022.
  * [185] Z. Lin, M. Lin, B. Champagne, W.-P. Zhu, and N. Al-Dhahir, “Secure and energy efficient transmission for RSMA-based cognitive satellite-terrestrial networks,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 2, pp. 251–255, Feb. 2021.
  * [186] A. Salem, C. Masouros, and B. Clerckx, “Rate splitting with finite constellations: The benefits of interference exploitation vs suppression,” _IEEE Open J. Commun. Soc._ , vol. 2, pp. 1541–1557, June 2021.
  * [187] A. Salem and C. Masouros, “Rate splitting approach under PSK signaling using constructive interference precoding technique,” in _Proc. IEEE Wireless Commun. Netw. Conf. (WCNC)_ , 2019.
  * [188] C. Xu, B. Clerckx, S. Chen, Y. Mao, and J. Zhang, “Rate-splitting multiple access for multi-antenna joint communication and radar transmissions,” in _Proc. IEEE Int. Conf. Commun. (ICC) Workshop_ , 2020.
  * [189] ——, “Rate-splitting multiple access for multi-antenna joint radar and communications,” _IEEE J. Sel. Top. Signal Process._ , vol. 15, no. 6, pp. 1332–1347, Nov. 2021.
  * [190] R. Cerna-Loli, O. Dizdar, and B. Clerckx, “A rate-splitting strategy to enable joint radar sensing and communication with partial CSIT,” in _Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , 2021.
  * [191] L. Yin and B. Clerckx, “Rate-splitting multiple access for dual-functional radar-communication satellite systems,” in _Proc. IEEE Wireless Commun. Netw. Conf. (WCNC)_ , 2022.
  * [192] H. Liu, T. A. Tsiftsis, B. Clerckx, K. J. Kim, K. S. Kwak, and H. V. Poor, “Rate splitting multiple access for semi-grant-free transmissions,” _arXiv preprint arXiv:2110.02127_ , 2021.
  * [193] E. J. D. Santos, R. D. Souza, and J. L. Rebelatto, “Rate-splitting multiple access for URLLC uplink in physical layer network slicing with eMBB,” _IEEE Access_ , vol. 9, pp. 163 178–163 187, 2021.
  * [194] Y. Liu, B. Clerckx, and P. Popovski, “Network slicing for eMBB, URLLC, and mMTC: An uplink rate-splitting multiple access approach,” _arXiv preprint arXiv:2208.10841_ , 2022.
  * [195] N. Devroye and P. Popovski, “Receiver-side opportunism in cognitive networks,” in _Proc. ICST CROWNCOM Conf._ , 2011.
  * [196] M. R. Camana Acosta, C. E. G. Moreta, and I. Koo, “Joint power allocation and power splitting for MISO-RSMA cognitive radio systems with SWIPT and information decoder users,” _IEEE Syst. J._ , vol. 15, no. 4, pp. 5289–5300, Dec. 2021.
  * [197] S. Naser, P. C. Sofotasios, L. Bariah, W. Jaafar, S. Muhaidat, M. Al-Qutayri, and O. A. Dobre, “Rate-splitting multiple access: Unifying NOMA and SDMA in MISO VLC channels,” _IEEE Open J. of Veh. Technol._ , vol. 1, pp. 393–413, Oct. 2020.
  * [198] S. Tao, H. Yu, Q. Li, Y. Tang, and D. Zhang, “One-layer rate-splitting multiple access with benefits over power-domain NOMA in indoor multi-cell visible light communication networks,” in _Proc. IEEE Int. Conf. Commun. (ICC) Workshop_ , 2020.
  * [199] S. Ma, H. Zhou, Y. Mao, X. Liu, Y. Wu, B. Clerckx, Y. Wang, and S. Li, “Robust beamforming design for rate splitting multiple access-aided MISO visible light communications,” _arXiv preprint arXiv:2108.07014_ , 2021.
  * [200] L. Li, K. Chai, J. Li, and X. Li, “Resource allocation for multicarrier rate-splitting multiple access system,” _IEEE Access_ , vol. 8, pp. 174 222–174 232, Sept. 2020.
  * [201] Y. Mao, B. Clerckx, and V. O. K. Li, “Rate-splitting for multi-user multi-antenna wireless information and power transfer,” in _Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , 2019.
  * [202] X. Su, L. Li, H. Yin, and P. Zhang, “Robust power- and rate-splitting-based transceiver design in $K$-user MISO SWIPT interference channel under imperfect CSIT,” _IEEE Commun. Lett._ , vol. 23, no. 3, pp. 514–517, Mar. 2019.
  * [203] R. Chen, F. Cheng, J. Lin, L. Liang, and Y. Sun, “Performance analysis of rate splitting multiple access based vortex wave communications,” _IEEE Wireless Commun. Lett._ , pp. 1–1, 2022.
  * [204] H. Liu, Y. Ye, Z. Bai, K. J. Kim, and T. A. Tsiftsis, “Rate splitting multiple access aided mobile edge computing in cognitive radio networks,” _arXiv preprint arXiv:2204.06208_ , 2022.
  * [205] S. Rezvani, E. A. Jorswieck, N. M. Yamchi, and M. R. Javan, “Optimal SIC ordering and power allocation in downlink multi-cell NOMA systems,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 6, pp. 3553–3569, 2022.
  * [206] A. Bansal, K. Singh, B. Clerckx, C.-P. Li, and M.-S. Alouini, “Rate-splitting multiple access for intelligent reflecting surface aided multi-user communications,” _IEEE Trans. Veh. Technol._ , vol. 70, no. 9, pp. 9217–9229, 2021.
  * [207] H. Bastami, M. Moradikia, A. Abdelhadi, H. Behroozi, B. Clerckx, and L. Hanzo, “Maximizing the secrecy energy efficiency of the cooperative rate-splitting aided downlink in multi-carrier UAV networks,” _IEEE Trans. Veh. Technol._ , pp. 1–17, 2022.
  * [208] A. D. Wyner, “The wire-tap channel,” _The Bell System Technical Journal_ , vol. 54, no. 8, pp. 1355–1387, 1975.
  * [209] M. Bloch, J. Barros, M. R. D. Rodrigues, and S. W. McLaughlin, “Wireless information-theoretic security,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 6, pp. 2515–2534, 2008.
  * [210] G. Durisi, T. Koch, and P. Popovski, “Toward massive, ultra-reliable, and low-latency wireless communication with short packets,” _Proc. IEEE_ , vol. 104, no. 9, pp. 1711–1726, 2016.
  * [211] H. Sato, “The capacity of the Gaussian interference channel under strong interference (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 27, no. 6, pp. 786–788, 1981.
  * [212] I. Sason, “On achievable rate regions for the Gaussian interference channel,” _IEEE Trans. Inf. Theory_ , vol. 50, no. 6, pp. 1345–1356, 2004\.
  * [213] A. G. Davoodi and S. A. Jafar, “Transmitter cooperation under finite precision CSIT: A GDoF perspective,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 9, pp. 6020–6030, Sept. 2017.
  * [214] ——, “Sum-set inequalities from aligned image sets: Instruments for robust GDoF bounds,” _IEEE Trans. Inf. Theory_ , vol. 66, no. 10, pp. 6458–6487, 2020.
  * [215] S. Yang and Z. Lit, “A constant-gap result on the multi-antenna broadcast channels with linearly precoded rate splitting,” in _Proc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , 2018.
  * [216] Z. Li and S. Yang, “A linearly precoded rate splitting approach and its optimality for mimo broadcast channels,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , 2018.
  * [217] J. Wang and S. A. Jafar, “Sum-GDoF of symmetric multi-hop interference channel under finite precision CSIT using aligned-images sum-set inequalities,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 7, pp. 4470–4490, 2022.
  * [218] A. Tajer, A. Steiner, and S. Shamai (Shitz), “The broadcast approach in communication networks,” _Entropy_ , vol. 23, no. 1, 2021. [Online]. Available: https://www.mdpi.com/1099-4300/23/1/120
  * [219] M. Vaezi and H. Vincent Poor, _NOMA: An Information-Theoretic Perspective_. Cham: Springer International Publishing, 2019, pp. 167–193.
  * [220] T. Cover, “Broadcast channels,” _IEEE Trans. Inf. Theory_ , vol. 18, no. 1, pp. 2–14, Jan. 1972.
  * [221] B. Makki, K. Chitti, A. Behravan, and M.-S. Alouini, “A survey of NOMA: Current status and open research challenges,” _IEEE Open J. Commun. Soc._ , vol. 1, pp. 179–189, 2020.
  * [222] J. G. Proakis, _Digital Communications_. New York, NY, USA: McGraw-Hill, 2008.
  * [223] L. Ping, L. Liu, K. Wu, and W. Leung, “Interleave division multiple-access,” _IEEE Trans. Wireless Commun._ , vol. 5, no. 4, pp. 938–947, 2006.
  * [224] H. Nikopour and H. Baligh, “Sparse code multiple access,” in _Proc. IEEE Int. Symp. Pers. Indoor Mobile Radio Commun. (PIMRC)_ , Sep. 2013, pp. 332–336.
  * [225] Nokia and Alcatel-Lucent Shanghai Bell, “Non-orthogonal multiple access for new radio,” 3rd Generation Partnership Project (3GPP), document R1-165019, 3GPP TSG RAN WG1 Meeting #85, May 2016.
  * [226] R. Hadani, S. Rakib, M. Tsatsanis, A. Monk, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” in _Proc. IEEE Wireless Commun. Netw. Conf. (WCNC)_ , 2017.
  * [227] R. Hadani, S. Rakib, S. Kons, M. Tsatsanis, A. Monk, C. Ibars, J. Delfeld, Y. Hebron, A. J. Goldsmith, A. F. Molisch, and R. Calderbank, “Orthogonal time frequency space modulation,” 2018, arXiv:1808.00519.
  * [228] P. Raviteja, K. T. Phan, and Y. Hong, “Embedded pilot-aided channel estimation for OTFS in delay–doppler channels,” _IEEE Trans. Veh. Technol._ , vol. 68, no. 5, pp. 4906–4917, 2019.
  * [229] Z. Wei, W. Yuan, S. Li, J. Yuan, G. Bharatula, R. Hadani, and L. Hanzo, “Orthogonal time-frequency space modulation: A promising next-generation waveform,” _IEEE Wireless Commun._ , vol. 28, no. 4, pp. 136–144, 2021.
  * [230] P. Raviteja, K. T. Phan, Y. Hong, and E. Viterbo, “Interference cancellation and iterative detection for orthogonal time frequency space modulation,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 10, pp. 6501–6515, 2018.
  * [231] T. Thaj and E. Viterbo, “Low complexity iterative rake decision feedback equalizer for zero-padded OTFS systems,” _IEEE Trans. Veh. Technol._ , vol. 69, no. 12, pp. 15 606–15 622, 2020.
  * [232] Q. Li, J. Yuan, and H. Lin, “Iterative mmse detection for orthogonal time frequency space modulation,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , 2022, pp. 1–6.
  * [233] H. Lin and J. Yuan, “Orthogonal delay-Doppler division multiplexing modulation,” _IEEE Trans. Wireless Commun._ , vol. 1, no. 10, pp. 6501–6515, 2022.
  * [234] H. Lin and J. Yuan, “Multicarrier modulation on delay-Doppler plane: Achieving orthogonality with fine resolutions,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , 2022, pp. 1–6.
  * [235] M. Qiu, Y.-C. Huang, S.-L. Shieh, and J. Yuan, “A lattice-partition framework of downlink non-orthogonal multiple access without SIC,” _IEEE Trans. Commun._ , vol. 66, no. 6, pp. 2532–2546, Jun. 2018.
  * [236] M. Qiu, Y.-C. Huang, J. Yuan, and C.-L. Wang, “Lattice-partition-based downlink non-orthogonal multiple access without SIC for slow fading channels,” _IEEE Trans. Commun._ , vol. 67, no. 2, pp. 1166–1181, Feb. 2019.
  * [237] M. Qiu, Y.-C. Huang, and J. Yuan, “Downlink non-orthogonal multiple access without SIC for block fading channels: An algebraic rotation approach,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 8, pp. 3903–3918, Aug. 2019\.
  * [238] ——, “Discrete signaling and treating interference as noise for the Gaussian interference channel,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 11, pp. 7253–7284, Nov. 2021.
  * [239] N. Q. Hieu, D. T. Hoang, D. Niyato, and D. I. Kim, “Optimal power allocation for rate splitting communications with deep reinforcement learning,” _IEEE Wireless Commun. Lett._ , vol. 10, no. 12, pp. 2820–2823, 2021.
  * [240] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Trans. Signal Process._ , vol. 37, no. 3, pp. 50–60, Mar. 2020.
  * [241] S.-H. Park and H. Lee, “Completion time minimization of fog-RAN-assisted federated learning with rate-splitting transmission,” _IEEE Trans. Veh. Technol._ , to appear, 2022.
  * [242] C. K. Au-Yeung and D. J. Love, “On the performance of random vector quantization limited feedback beamforming in a MISO system,” _IEEE Trans. Wireless Commun._ , vol. 6, no. 2, pp. 458–462, Feb. 2007.
  * [243] P. Ding, D. J. Love, and M. D. Zoltowski, “Multiple antenna broadcast channels with shape feedback and limited feedback,” _IEEE Trans. Signal Process._ , vol. 55, no. 7, pp. 3417–3428, July 2007.
  * [244] C. K. Au Yeung, D. J. Love, and S. Sanayei, “Trellis coded line packing: Large dimensional beamforming vector quantization and feedback transmission,” _IEEE Trans. Wireless Commun._ , vol. 10, no. 6, pp. 1844–1853, June 2011.

|  Bruno Clerckx is a Professor, the Head of the Wireless Communications and
Signal Processing Lab, and the Deputy Head of the Communications and Signal
Processing Group, within the Electrical and Electronic Engineering Department,
Imperial College London, London, U.K. He is also the Chief Technology Officer
(CTO) of Silicon Austria Labs (SAL) where he is responsible for all research
areas of Austria’s top research center for electronic based systems. He
received the MSc and Ph.D. degrees in Electrical Engineering from Université
Catholique de Louvain, Belgium, and the Doctor of Science (DSc) degree from
Imperial College London, UK. He has authored two books on “MIMO Wireless
Communications” and “MIMO Wireless Networks”, 250 peer-reviewed international
research papers, and 150 standards contributions, and is the inventor of 80
issued or pending patents among which 15 have been adopted in the
specifications of 4G standards and are used by billions of devices worldwide.
His research spans the general area of wireless communications and signal
processing for wireless networks. He served as an editor or guest editor for
the IEEE TRANSACTIONS ON COMMUNICATIONS, the IEEE TRANSACTIONS ON WIRELESS
COMMUNICATIONS, and the IEEE TRANSACTIONS ON SIGNAL PROCESSING, EURASIP
Journal on Wireless Communications and Networking, IEEE ACCESS, the IEEE
JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, the IEEE JOURNAL OF SELECTED
TOPICS IN SIGNAL PROCESSING, the PROCEEDINGS OF THE IEEE, and the IEEE Open
Journal of the Communications Society. He was an Editor for the 3GPP LTE-
Advanced Standard Technical Report on CoMP. He received the prestigious
Blondel Medal 2021 from France for exceptional work contributing to the
progress of Science and Electrical and Electronic Industries, the 2021 Adolphe
Wetrems Prize in mathematical and physical sciences from Royal Academy of
Belgium, multiple awards from Samsung, IEEE best student paper award, and the
EURASIP (European Association for Signal Processing) best paper award 2022. He
is a Fellow of the IEEE and the IET, and an IEEE Communications Society
Distinguished Lecturer 2021-2023.
---|---
|  Yijie Mao is an Assistant Professor at the School of Information Science
and Technology, ShanghaiTech University (Shanghai, China). She received the
B.Eng. degree from the Beijing University of Posts and Telecommunications
(Beijing, China), the B.Eng. degree (Hons.) from the Queen Mary University of
London (London, United Kingdom) in 2014, and the Ph.D. degree from the
Electrical and Electronic Engineering Department, the University of Hong Kong
(Hong Kong, China) in 2018. She was a Postdoctoral Research Fellow at the
University of Hong Kong from 2018 to 2019 and a postdoctoral research
associate with the Communications and Signal Processing Group, Department of
the Electrical and Electronic Engineering at the Imperial College London
(London, United Kingdom) from 2019 to 2021. Her research interests include the
design of future wireless communications and artificial intelligence-empowered
wireless networks. Dr. Mao receives the Best Paper Award of EURASIP Journal on
Wireless Communications and Networking 2022 and the Exemplary Reviewer for
IEEE Transactions on Communications 2021. She is currently serving as a guest
editor for special issues of IEEE Journal on Selected Areas in Communications
and IEEE Open Journal of the Communications Society. She has been a vice-chair
of IEEE ComSoc WTC SIG on rate-splitting multiple access (RSMA) and a workshop
co-chair for 2020-2022 IEEE ICC, 2021-2022 IEEE WCNC, 2020-2022 IEEE PIMRC,
and 2022 IEEE SECON, and she has been a Technical Program Committee member of
many symposia on wireless communication for several leading international IEEE
conferences.
---|---
|  Eduard A. Jorswieck is managing director of the Institute of Communications
Technology and the head of the Chair for Information Theory and Communications
Systems and Full Professor at Technische Universität Braunschweig, Brunswick,
Germany. From 2008 until 2019, he was the head of the Chair of Communications
Theory and Full Professor at TU Dresden, Germany. Eduard’s main research
interests are in the broad area of communications. He has co-authored some 160
journal papers, 15 book chapters, 4 monographs, and more than 300 conference
papers. Since 2017, he serves as Editor-in-Chief of the Springer EURASIP
Journal on Wireless Communications and Networking. He currently serves as
editor for IEEE Transactions on Communications. He has served on the editorial
boards for IEEE Transactions on Signal Processing, IEEE Transactions on
Wireless Communications, IEEE Signal Processing Letters, and IEEE Transactions
on Information Forensics and Security. In 2006, he received the IEEE Signal
Processing Society Best Paper Award.
---|---
|  Jinhong Yuan (M’02–SM’11–F’16) is a Professor and Head of Telecommunication
Group with the School of Electrical Engineering and Telecommunications, The
university of New South Wales, Sydney, Australia. He has published two books,
five book chapters, over 300 papers in telecommunications journals and
conference proceedings, and 50 industrial reports. He is a co-inventor of one
patent on MIMO systems and four patents on low-density-parity-check codes. He
has co-authored four Best Paper Awards and one Best Poster Award, including
the Best Paper Award from the IEEE International Conference on Communications,
Kansas City, USA, in 2018, the Best Paper Award from IEEE Wireless
Communications and Networking Conference, Cancun, Mexico, in 2011, and the
Best Paper Award from the IEEE International Symposium on Wireless
Communications Systems, Trondheim, Norway, in 2007. He is an IEEE Fellow and
currently serving as an Associate Editor for the IEEE Transactions on Wireless
Communications and IEEE Transactions on Communications. He served as the IEEE
NSW Chapter Chair of Joint Communications/Signal Processions/Ocean Engineering
Chapter during 2011-2014 and served as an Associate Editor for the IEEE
Transactions on Communications during 2012-2017. His current research
interests include error control coding and information theory, communication
theory, and wireless communications.
---|---
|  David J. Love (S’98 - M’05 - SM’09 - F’15) is the Nick Trbovich Professor
of Electrical and Computer Engineering at Purdue University. His research
interests are in the design and analysis of broadband wireless communication
systems, beyond 5G wireless systems, multiple-input multiple-output (MIMO)
communications, millimeter wave wireless, software defined radios and wireless
networks, coding theory, and MIMO array processing. He holds 32 issued US
patents. He served as a Senior Editor for IEEE Signal Processing Magazine,
Editor for the IEEE Transactions on Communications, Associate Editor for the
IEEE Transactions on Signal Processing, and Guest Editor for special issues of
the IEEE Journal on Selected Areas in Communications and the EURASIP Journal
on Wireless Communications and Networking. Since 2022, he is a Fellow of the
American Association for the Advancement of Science (AAAS). Along with his co-
authors, he won best paper awards from the IEEE Communications Society (2016
Stephen O. Rice Prize and 2020 Fred Ellersick Prize), the IEEE Signal
Processing Society (2015 IEEE Signal Processing Society Best Paper Award), and
the IEEE Vehicular Technology Society (2010 Jack Neubauer Memorial Award).
---|---
|  Elza Erkip is an Institute Professor in the Electrical and Computer
Engineering Department at New York University Tandon School of Engineering.
She received the B.S. degree in Electrical and Electronics Engineering from
Middle East Technical University, Ankara, Turkey, and the M.S. and Ph.D.
degrees in Electrical Engineering from Stanford University, Stanford, CA, USA.
Her research interests are in information theory, communication theory, and
wireless communications. Dr. Erkip is a member of the Science Academy of
Turkey and is a Fellow of the IEEE. She received the NSF CAREER award in 2001,
the IEEE Communications Society WICE Outstanding Achievement Award in 2016,
the IEEE Communications Society Communication Theory Technical Committee
(CTTC) Technical Achievement Award in 2018, and the IEEE Communications
Society Edwin Howard Armstrong Achievement Award in 2021. She was the Padovani
Lecturer of the IEEE Information Theory Society in 2022. Her paper awards
include the IEEE Communications Society Stephen O. Rice Paper Prize in 2004,
the IEEE Communications Society Award for Advances in Communication in 2013
and the IEEE Communications Society Best Tutorial Paper Award in 2019. She was
a member of the Board of Governors of the IEEE Information Theory Society
2012-2020, where she was the President in 2018. She was a Distinguished
Lecturer of the IEEE Information Theory Society from 2013 to 2014.
---|---
|  Dusit Niyato is the President’s Chair Professor in the School of Computer
Science and Engineering, at Nanyang Technological University, Singapore. He
received B.Eng. from King Mongkuts Institute of Technology Ladkrabang (KMITL),
Thailand in 1999 and Ph.D. in Electrical and Computer Engineering from the
University of Manitoba, Canada in 2008. His research interests are in the
areas of sustainability, edge intelligence, decentralized machine learning,
and incentive mechanism design.
---|---


11institutetext: University of Ottawa, 75 Laurier Ave E, Ottawa, ON K1N 6N5,
Canada 11email<EMAIL_ADDRESS>
# A Novel Technique for Query Plan Representation Based on Graph Neural Nets

Baoming Chang 11 0009-0005-7414-3631 Amin Kamali 11 0000-0003-2176-4088 Verena
Kantere 11 0000-0002-3586-9406

###### Abstract

Learning representations for query plans play a pivotal role in machine
learning-based query optimizers of database management systems. To this end,
particular model architectures are proposed in the literature to convert the
tree-structured query plans into representations with formats learnable by
downstream machine learning models. However, existing research rarely compares
and analyzes the query plan representation capabilities of these tree models
and their direct impact on the performance of the overall optimizer. To
address this problem, we perform a comparative study to explore the effect of
using different state-of-the-art tree models on the optimizer’s cost
estimation and plan selection performance in relatively complex workloads.
Additionally, we explore the possibility of using graph neural networks (GNN)
in the query plan representation task. We propose a novel tree model combining
directed GNN with Gated Recurrent Units (GRU) and demonstrate experimentally
that the new tree model provides significant improvements to cost estimation
tasks and relatively excellent plan selection performance compared to the
state-of-the-art tree models.

###### Keywords:

Query Plan Representation Tree Model Graph Neural Network.

##  1 Introduction

Query optimization is a critical component of a database management system due
to its difficulty and importance in query execution performance. The process
of accurately and efficiently estimating the cost of generated candidate query
execution plans and selecting the optimal plan is always a challenge in the
field of query optimization. A query execution plan is typically represented
as a tree, where the nodes contain information about operators used to access,
join, or aggregate data, and the edges contain dependencies between the parent
and child nodes. An optimal plan tree enables the database management system
to access and manipulate data efficiently. Traditional query optimizers employ
cost models to estimate the amount of processing data using plan trees. These
cost models rely heavily on statistical methods such as Histograms [5], which
are susceptible to large errors because of their inability to effectively
capture characteristics such as join-crossing correlations.

Figure 1: Machine learning-based query optimizer framework.

The development of machine learning provides a promising solution to improve
query optimization and has been proposed in a wide range of applications in
this field. Recent machine learning-based query optimizers employ a similar
structure, as shown in Fig. 1. In these frameworks, node information from a
query plan tree is first encoded into node features. Then, a tree model
transforms and aggregates these into graph-level representations for each
candidate query plan, and a cost estimator predicts execution costs based on
these representations, enabling the optimizer to select the most efficient
plan. The challenge in this process is to effectively transform the tree-
structured query plan into a graph-level vector while preserving as much of
the original node features and structural information as possible. The quality
of representation generated by the tree model is crucial to ensure the cost
estimator model makes accurate predictions and allows the optimizer to make
informed decisions on plan selection.

Current research in query optimization often lacks direct performance
comparisons of the representation abilities of these tree models, focusing
instead on the general performance of the whole query optimization process
[25]. Therefore, in this paper, we evaluate the mainstream tree models query
plan representation under more complex workloads, comparing and analyzing
their performance in cost estimation tasks. In addition, unlike previous
studies [25], instead of pairwise comparisons, we compare and analyze the tree
model’s plan selection capability in a way that is closer to actual usage
scenarios by selecting an optimal plan from multiple candidate query plans to
explore how different tree models affect the performance of plan selection.

Our research also explores the possibility of using Graph Neural Networks
(GNNs) [26] as tree models. Although GNNs are being developed and have
achieved success across various graph-based domains, their application within
query plan cost estimation remains insufficiently explored. In this context,
our paper explores the potential of employing GNNs for query execution plan
representation learning. We also propose a novel tree model architecture for
query plan representation based on directed GNN [18] and a GRU-based
Aggregation [1] method, which can capture the intricacies of query plan trees
more accurately and robustly, setting a new stage for query plan
representation learning.

To summarize, our main contributions are:

  * •

We conduct a comparative analysis of the performance of mainstream tree models
in cost estimation under complex conditions.

  * •

We evaluate the impact of tree models in the task of selecting the optimal
plan from multiple candidate plans, closely mirroring actual application
scenarios, and provide an intuitive comparison and analysis.

  * •

We thoroughly explore the possibility of using GNN as a query execution plan
tree model.

  * •

We propose a novel query plan tree model based on directed GNN and GRU,
demonstrating its superior representational capabilities and performance
compared to existing tree models.

In the rest of the paper: Section 2 presents the problem of query plan
representation and current tree models. Section 3 outlines related works along
with their merits and shortcomings. Section 4 introduces the proposed
architecture of a directed GNN-based tree model. Section 5 presents the
comparative study of existing and GNN-based tree models’ performance on cost
estimation and plan selection tasks, and Section 6 concludes the paper and
discusses future work.

##  2 Problem Statement

In a query optimizer based on machine learning, query plan representation is a
module that takes the physical query plan as input and uses a feature encoder
and a tree model to generate vectors that subsequent machine learning models
use for learning a downstream task. The generated query plan graph vector will
condense important information about the physical query plan. How to
accurately represent both structural and node information in the tree model’s
output can directly impact the overall performance of the query optimizer. In
this study, we focus on the representation capability of query plan tree
models in the same application scenario using the same structure of feature
encoder and cost estimator, so that the representation quality of a query plan
can entirely rely on the tree model, allowing us to compare the performance of
these tree models directly.

Due to the tree structure characteristics of the query plan, it is difficult
for tree models to use traditional machine learning methods to learn and
aggregate node information directly, for they usually cannot accept inputs in
the form of trees. Consequently, the database community has started developing
machine-learning models designed explicitly for tree structures [21, 14].
While the advanced models have marked performance improvements, they still
have two main limitations:

  * •

Information Dilution. As information traverses from the leaf nodes—where
specific relation-based operations are stored—towards the root, it tends to
get diluted. This dilution process may negatively impact the accuracy of
predictive cost estimations. The depth of the tree exacerbates this issue,
leading to possible loss or dilution of critical information as it is passed
upward or downward through the tree. The challenge of information dilution
becomes more noticeable for complex queries that result in deeply structured
trees.

  * •

Preserving Structural Information. The plan tree contains essential structural
and logical information. Preserving the integrity of this information while
aggregating data from the entire graph is crucial and challenging.

Therefore, the design of the tree model used for processing query plans should
consider the above two limitations to further improve the model’s
representation ability according to the structural characteristics of the
query plan tree.

##  3 Related Work

Query plan representation is mainly studied under one of the following
categories: studies proposing novel tree models and their comparative
analysis.

Tree models. RNN-based models like Long Short-Term Memory (LSTM) [20] and
Gated Recurrent Units (GRU) [3] are commonly used in query plan
representation. Some works apply the self-attention mechanism to tree models,
such as Saturn [10], which aggregates LSTM’s hidden layers based on attention
as a representation of the query plan, or QueryFormer [24], which uses a
Transformer to encode the query plan. However, these methods have to convert
tree structure plans into sequential nodes as input, inevitably leading to the
loss of tree structure information. Machine learning models designed
explicitly for tree structures, for instance, Tree-structured LSTM (Tree-LSTM)
[21], Tree Convolutional Neural Network (TCNN) [14], allow information
transfer between child nodes and parent node so that the learned node features
can also contain structural information. While these approaches improve upon
non-tree models, they still do not demonstrate good results in solving the
problem of information dilution and effective aggregation of node features.
Recently, some works [2, 6] attempt to apply GNNs in this context. However,
there is no GNN model specifically designed for query plan tree graphs yet;
relevant works use the GNNs only to capture the query’s join relationship in
order to assist the representation learning by other tree models rather than
being directly used for learning query plan trees.

Comparative study. A significant contribution to this field is a study by Yao
Z. et al. [25]. The researchers conducted a detailed analysis comparing the
performance of mainstream feature encoders and tree models under various
scenarios. However, their study asserts that the tree model has no obvious
impact on the overall performance of the optimizer, which is not confirmed by
the findings of the current research. Their analysis also has a limitation: it
lacks a comprehensive assessment of tree models in the plan selection task,
since their evaluation only relies on pairwise index selection [4], which does
not adequately reflect the complexities in practical query optimization
scenarios. Furthermore, they do not isolate the impact of the tree model
architectures on this downstream task’s performance.

##  4 Model Architecture

In this section, we first introduce the feature encoding method we used and
then describe our proposed tree model structure based on directed GNN and GRU.

###  4.1 Feature Encoding

A query execution plan consists of information on the operators used to access
and join data from various sources, including the physical implementation of
the operators, their sequence, and the tables and columns accessed at each
step. The amount of data flowing through each plan node, determined by the
cardinality, is a decisive factor of the execution cost. In addition, the
local and join predicates involved in the query plan may exhibit various
levels of skewness and pairwise correlations, which in turn impact the
accuracy of the cardinality estimates. To transform this complex information
into fixed-length node features as input to the tree model, we developed a
plan encoder inspired by RTOS [23], while making critical changes to suit our
experimental purposes. As shown in Fig. 2, each node feature in the query
execution plan tree is composed of three parts: Node Type Embedding, Table
Embedding, and Predicate Embedding.

Figure 2: Machine learning-based plan node representation learning

Node Type Embedding. The node contains a specific operator type, such as Hash
Join or Index Scan. We perform one-hot encoding on the node types and pass
through a Fully Connected (FC) layer to obtain the node type embedding.

Table Embedding. We apply one-hot encoding on all tables in the node’s
operation to obtain the Table Embedding.

Predicate Embedding. We consider the two main types of columns involved in the
predicate:

For numerical columns with values, the predicate operations in the node can be
classified into 6 cases: $\bowtie$, $=$, $>$, $\geq$, $<$, $\leq$. Each column
is represented by a feature vector of the same length. If the predicate
involves a specific operation on a certain column, the corresponding vector
will be encoded according to the specific predicate type. If the column exists
in a join predicate, the corresponding position will be 1 otherwise 0. For the
other five cases, the predicate value is normalized to [0, 1] using the
maximum and minimum values of the column in the database and plus 1 as the
value of the corresponding position. If the predicate value exceeds the value
range of the column in the database, according to the operator type, if there
is no tuple that satisfies the predicate, the corresponding position is set to
-1 otherwise 2. Uninvolved cases remain 0.

For other value-type columns, such as string, it cannot be mapped to a value
with interval meaning by a simple method (e.g. hash) [23]. Thus, the join
predicate is encoded in the same way as above. For the other five cases, we
use Word2vec [13] to translate characters into numerical values for their
respective positions in the column feature.

Each column has a dedicated FC layer to process its encoded feature vector and
generate learned column embeddings. Then, max pooling is performed on all
column embeddings belonging to the same table to obtain the embedding
expression of each table with the same length. Since we need to avoid
information loss when aggregating embeddings in the node feature encoding
stage, we directly concatenate embeddings of all tables as the predicate
embedding.

###  4.2 Directed GNN for Query Plan Tree

The basic idea of a GNN network is that nodes can capture the characteristics
and contextual information of neighbour nodes and their complex relationships
via edges in the graph. Acknowledging the benefits of GNN, due to query plans’
characteristics discussed above, we propose a new tree model based on directed
GNN and GRU, which effectively addresses the following two main issues:

  1. 1.

Information Transmission between tree nodes

  2. 2.

Information Aggregation from node-level to graph-level

Information Transmission. In GNN, message passing between nodes depends on
both the existence of edges in graphs and their directionality. In the tree
structure, this issue is mainly divided into two situations: single-directed
and undirected edges. If single-directional edges are used, such as from the
child node pointing to the parent node, information is always transmitted from
the child node to the parent node. A node in GNN can only learn the
information of its adjacent nodes in one layer, which means any node in the
tree will only learn information about its child nodes. When learning a deeper
tree, for the information of the leaf nodes to be transferred to the root
node, the same number of GNN layers as the depth of the tree is needed, which
is generally unacceptable. The single-directed edge also makes it challenging
to transfer the leaves’ information to the root node, passing the entire graph
without diluting or losing it, which makes using root node features as query
plan graph-level representation infeasible. It also lets child nodes never
learn the node feature and structural information about its parent node and
above nodes, so the relevant structural information will inevitably be lost in
the stage of aggregating node features.

Therefore, using bidirectional edges has the potential to significantly speed
up the information transfer between nodes. However, our experiments have
proven that using undirected edges only cannot perform well in tree graphs.
The reason is that it destroys the structural relationship between parent and
child nodes and makes the model unable to learn the hierarchical dependency
between them. Inspired by DirGNNConv [18], we innovatively treat the query
plan trees as two one-way graphs with opposite edge directions. In each layer
of our tree model, as shown in Fig. 3, we divide the original query plan into
two tree graphs with opposite edge directions as input to two independent
TransformerConv [19] layers respectively and integrate the corresponding nodes
from the two output learned graphs through a learnable parameter, which makes
it possible to transmit information in both directions while still utilizing
the direction information of the edges and retaining relevant structural
information. Given a query plan tree graph $G$ with $N$ nodes, $n$ as the
nodes in the node feature set $Nodes$, $E$ as the undirected edge index set,
$E_{\text{child to parent}}$ and $E_{\text{parent to child}}$ as the edge
index sets with opposite directions, $p$ as a learnable parameter, the
directed GNN layer is defined as Algorithm 1:

Figure 3: Framework of tree model using directed GNN with aggregation operator
GRU. Algorithm 1 Update node features in directed GNN

1:Input: $G=(Nodes,E)$

2:$Nodes=\\{n_{i}\mid\forall i\in\\{1,\ldots,N\\}\\}$

3:$E=E_{\text{child to parent}}\cup E_{\text{parent to child}}$

4:$Nodes_{\text{child to parent}}=\text{TransformerConv1}(Nodes,E_{\text{child
to parent}})$

5:$Nodes_{\text{parent to
child}}=\text{TransformerConv2}(Nodes,E_{\text{parent to child}})$

6:for $i=1$ to $N$ do

7: $n_{\text{new}_{i}}=p\times n_{\text{child to parent}_{i}}+(1-p)\times
n_{\text{parent to child}_{i}}$

8:end for

9:Output: $G=(Nodes_{\text{new}},E)$

Additionally, the graph attention mechanism [22] in TransformerConv can
further improve the model’s ability to capture the tree’s local graph topology
and global dependencies. To verify this perspective, our experiments also
evaluated the influence of undirected edges, single-directed edges, and
weighted directed edges on the model’s capability to represent query plans.

Information Aggregation. Conventional graph aggregation methods often produce
inferior results when processing tree structure graphs. These methods usually
simply aggregate node features by global pooling, which ignores the structural
information in the graph. In our model we innovated by applying GRU to
aggregate the GNN-learned query plan nodes after post traversal of the tree.
The rationale for this design decision is based on the observation that the
order in which DBMS executes the query plan tree nodes and the order of nodes
obtained by post-order traversal of the tree are similar [10]. This design
learns the dependencies between nodes while more closely conforming to the
actual execution sequence, thereby allowing our tree model to obtain the query
plan’s graph-level embedding while retaining the node features and structural
information in the query plan tree to a certain extent. Our experiments have
proven that GRU, as the aggregation operator, performs far better than other
aggregation methods in query plan representation.

##  5 Experimental Study

Cost estimation is a crucial step in the query optimizer, as it directly
determines how the model selects the optimal plan from candidate plans.
However, these cost estimates are subject to arbitrary errors rooted in
various sources, such as inaccurate cardinality estimates or simplifying
assumptions. Therefore, in this work, we opt to directly learn the plan
execution latency from runtime.

In addition to evaluating tree model cost estimation error and correlation,
model performance in plan selection is also crucial. In the plan selection
phase of query optimization, due to data and model uncertainties [6], the
model’s cost predictions may have inevitable errors, potentially affecting the
final optimal plan selection. In practical applications, if a model can select
the actual optimal plan is far more important than making more accurate
predictions. Therefore, we evaluate the model’s ability to correctly select
the optimal plan with the shortest actual execution latency among multiple
candidate query plans. We simulate real application scenarios to explore and
compare the impact of employing different tree models on the overall plan
selection accuracy of the optimizer.

To assess the impact of different tree models in query plan representation we
use the same feature encoding model described in Section 4.1 and the same MLP-
based cost estimator for all experiments. In this way, we can evaluate the
representation ability of different tree models through the accuracy of cost
estimates and plan selection.

###  5.1 Experimental Setup

The experiments are performed on a Linux server with 8-core Intel Silver 4216
Cascade Lake 2.1GHz CPU, 64GB memory, and a 32GB NVIDIA V100 Volta GPU.
PostgreSQL 15.1 is used as the RDBMS for compiling and executing the
workloads. The prototype code is written in Python 3.10 with the machine
learning library PyTorch [15]. All experimental results are the average after
10-fold cross-validation.

Selected Existing Tree Models. We select five state-of-the-art tree models for
further evaluation as follows:

  1. 1.

LSTM: LSTM is a variant of recurrent neural network (RNN) architecture
designed for sequences of data and capable of remembering long-term
dependencies [20]. Since it cannot directly handle the tree, we flatten the
query plan according to post-order traversal [10] as input. The hidden layer
of the last node is treated as a graph-level representation of the query plan.

  2. 2.

GRU: Gated Recurrent Unit (GRU) is a type of RNN that simplifies the LSTM
architecture by combining the forget and input gates into an update gate,
improving efficiency and performance on tasks involving sequential data [3].
Model input and output are obtained in the same way as LSTM.

  3. 3.

LSTM + Self Attention: Saturn [10] proposed an improvement of LSTM for query
plan representation by applying the Self Attention [22] mechanism to weigh
each hidden layer and aggregate all hidden layers according to their weight as
the plan-level representation.

  4. 4.

TreeLSTM: TreeLSTM is an adaptation of the conventional RNN for tree-
structured graphs, which can aggregate information from the leaf nodes to the
root across different tree branches by generalizing the traditional LSTM cell
by accepting inputs from multiple channels [21]. The root node representation
is treated as the graph-level representation of the query plan.

  5. 5.

TreeCNN: TreeCNN is designed to handle tree-structured data [14], and was
first applied to query plan representation in NEO [12]. It slides a triangular
kernel from the root to the leaf nodes, which allows learning relationships
between each combination of two child nodes and their parent node. Dynamic
pooling is used to aggregate all features into a graph-level representation of
the query plan [12]. This model can only be applied to binary trees. Non-
binary trees require preprocessing, involving adding more nodes and layers, to
become compatible with the model.

Dataset. We use workloads based on a 10 GB database generated by TPC-DS 3.2
[17], an industrial standard benchmark commonly used to evaluate the
performance of cost estimation with 25 tables and 429 columns. TPC-DS has more
relations and allows for more complex query patterns compared with other
benchmarks, such as IMDB(JOB) [8] and TPC-H [16]. Therefore, using TPC-DS we
can generate more complex join queries to evaluate the representation learning
performance of the tree models in more complex scenarios. Due to the limited
complexity of the query generation template that comes with TPC-DS, we used a
random query generator to generate queries based on TPC-DS relations. The
queries are determined by parameters provided to the query generator,
including the number of joins, join types (such as inner-join, outer-join,
left/right outer-join, anti-join), the number of local predicates, and the
types of operators used in join and local predicates. The following are the
datasets used in the two tasks:

  1. 1.

Dataset for cost estimation. We generated 22k queries and each query has up to
10 joins, sampled from referential integrity one-to-many and artificial many-
to-many joins, with each join having up to 3 join predicates and each table
with up to 5 local predicates. PostgreSQL’s default query plans for each query
and their execution time are seen as samples and labels. 18k of the query
plans are used for training, 2k for validation and 2k for testing.

  2. 2.

Dataset for plan selection. We generate 10k queries using the same query
generator for evaluating plan selection performance. Each query was compiled
in PostgreSQL using 13 different hint sets inspired by Bao [11]. These hint
sets introduced specific constraints on the join and access operators utilized
within the query plans. Each sample in the dataset is a collection of
candidate query plans generated based on the 13 hints from the same query. The
dataset contains 10k queries yielding about 130k query plan trees and is
divided into 8k queries for training, 1k for validation, and 1k for testing.

Evaluation Metrics. We employ four evaluation metrics for the experiment, as
shown in the following. Metrics 1-3 are applied to the cost estimation task,
while metric 4 is dedicated to the plan selection task.

  1. 1.

Prediction Error: We use Q-Error to evaluate the accuracy of estimated
latency. Given the estimated latency $y_{el}$ and actual latency $y_{al}$, the
Q-Error is defined as:

$Q\text{-}Error=\frac{\max(y_{el},y_{al})}{\min(y_{el},y_{al})}$ (1)

  2. 2.

Correlation: We use Spearman’s rank correlation to measure the relationship
between model-estimated latency and actual latency, with values closer to 1
indicating a stronger correlation. Unlike the widely used Pearson’s
coefficient, Spearman correlation is not such sensitive to outliers and data
scales for using a monotonic function, making it more suitable to evaluate
indicators such as latency that may have large orders-of-magnitude
differences.

  3. 3.

Inference Overheads: We measured the average time the tree model used to
predict a latency estimate for each encoded query plan during testing, which
can be used to compare the computational overhead of each tree model.

  4. 4.

Plan Suboptimality: Given a set of candidate execution plans $p$ generated
based on the same query, ranking these candidate plans according to the actual
execution latency $AL(.)$ and identifying the plan with the shortest execution
latency as the actual optimal plan, denoted as $p_{o}$. Concurrently, the
optimal plan selected by the optimizer with the shortest predicted latency is
donated as $p_{m}$. In this context, we define Plan Suboptimality as Equation
2 which takes a value in the range of $[1,\infty)$ and reflects the model’s
ability to identify the optimal plan among multiple options.

$\text{Plan Suboptimality}=\frac{AL(p_{m})}{AL(p_{o})}$ (2)

Loss Function. We used the Mean Squared Error algorithm based on the cost
estimator model’s output and labels after being preprocessed by natural log
transformation and min-max scaling. To reduce the significant skewness in
execution latency values, we first apply a natural log to all labels and make
them more suitable targets for a machine learning model to learn [6]. Then,
min-max scaling is performed based on the processed label to normalize it to
the range [0, 1] so that it is in the same range as the output of the Sigmoid
activation function used in the final layer of the cost estimator. Given all
the labels in the dataset after natural logarithmic transformation
$y_{\log_{e}}$, a cost estimator model output $y_{e}$, the corresponding
actual latency $y_{al}$, the loss function is defined as follows.

$\text{Loss}=\sum_{i=1}^{n}\left(\frac{\log_{e}(y_{{al}_{i}})-\min(y_{\log_{e}})}{\max(y_{\log_{e}})-\min(y_{\log_{e}})}-y_{e_{i}}\right)^{2}$
(3)

Model Training and Parameter Tuning. In the model training phase, the hyper-
parameters are individually tuned for each tree model. The learning rate and
other hyper-parameters of the remaining models, such as the feature encoder or
cost estimator, are jointly tuned. Parameter tuning is done using the
Asynchronous Successful Halving Algorithm (ASHA) [9]. Adaptive Moment
Estimation (ADAM) [7] is used as the optimizer for model training. Dropout and
Early stopping are used to avoid over-fitting.

###  5.2 Existing Tree Model Cost Estimation Performance

We evaluate the impact of using different tree models under the same framework
on the overall cost estimation performance of the query optimizer. We present
the results of the current state-of-the-art tree models in the upper part of
Table 1.

Even in workloads with larger scale and more complex join relationships, five
existing tree models, including GRU, LSTM, LSTM + Self-Attention, Tree-LSTM,
and TCNN, do not have a significant difference in query plan representation
capabilities as stated in the study by Yao Z. et al. [25]. However, in the
special scenario of representing complex query plans, the differences in
Q-Error and Spearman’s Correlation performance between different models become
more apparent. We outline interesting observations regarding the impacts of
various characteristics of the models on plan tree representation learning as
follows.

Observation: Tree-LSTM has the best performance. Compared with other models,
Tree-LSTM performs best in all evaluation indicators. The highest Spearman’s
Correlation and the lowest average Q-Error indicate that it can accurately
capture and express critical information in most cases, even when processing
complex query plans. In terms of Q-Error distribution, it has a significantly
smaller tail-end error than other tree models, indicating that it is more
robust in dealing with outliers and extreme situations. Experimental results
demonstrate the effectiveness of its hierarchical structure-aware processing
in accurately predicting complex query plan costs. However, this comes at the
cost of having the highest inference overheads, as shown in Fig. 4.

Observation: GRU has a better performance than LSTM. GRU and LSTM have similar
principles to capture long-term dependencies, and both demonstrate relatively
good and stable performance in the experiment. However, we observe that GRU,
which has a simpler architecture and fewer model parameters, has better
performance than LSTM across all performance metrics. Due to the reduced
overhead and enhanced performance, GRU may offer advantages in query-plan
representation tasks. On the one hand, due to its simplified design, it
requires less training data than LSTM to learn the dependencies between query
plan nodes. On the other hand, its mechanism of reset gate and update gate [3]
may enable GRU to more effectively forget unimportant information while
learning the query plan tree of post-order expansion, leading to more accurate
predictions.

Observation: Self-attention enhances LSTM. Comparing the results of LSTM and
LSTM+Self-Attention in the experiment, we observe that integrating LSTM and
self-attention as a tree model has better cost estimation performance than the
basic LSTM. This means that using the Self-attention mechanism to aggregate
hidden states of all nodes can more effectively aggregate node features and
better represent the query plan than relying solely on the final node’s state.
Such findings show the potential of self-attention mechanisms in improving the
tree model, demonstrating their capability to enrich model understanding and
performance in complex query plan representation tasks.

Table 1: Cost Estimation Accuracy (Q-Error) in TPC-DS workload. The first
block includes the state-of-the-art tree models we evaluated. The second block
includes the tree models based on GNN layers with different graph edge
directions and aggregation methods. The overall best results across blocks are
underlined.

Tree Model (+Aggregation Method) |  Graph Edge Direction |  Median Q-error |  90th Q-error |  99th Q-error |  Spearman’s Correlation |  Top 50% Mean Q-error |  Top 99% Mean Q-error
---|---|---|---|---|---|---|---
GRU | - | 1.895 | 22.582 | 296.242 | 0.776 | 1.378 | 5.727
LSTM | - | 1.954 | 21.979 | 311.205 | 0.765 | 1.398 | 5.824
LSTM + Self-Attention | - | 1.885 | 20.710 | 313.775 | 0.778 | 1.370 | 5.489
Tree-LSTM | - | 1.840 | 19.413 | 235.727 | 0.783 | 1.352 | 5.063
TCNN | - | 1.912 | 25.758 | 430.101 | 0.761 | 1.380 | 6.674
GNN + AddPool | Single directed | 1.971 | 25.184 | 471.242 | 0.765 | 1.403 | 6.697
GNN + GRU | Single directed | 1.884 | 20.960 | 324.524 | 0.776 | 1.369 | 5.684
GNN + GRU | Undirected | 1.880 | 20.320 | 298.524 | 0.775 | 1.371 | 5.409
Directed GNN + AddPool | Weighted directed | 1.882 | 23.387 | 459.604 | 0.771 | 1.370 | 6.502
Directed GNN + GRU | Weighted directed | 1.762 | 16.537 | 199.137 | 0.805 | 1.327 | 4.558

###  5.3 GNN-based Tree Model Cost Estimation Performance

We explore and evaluate the impact of using different edge structures and
aggregation methods on the representation ability of GNN-based tree models. We
present the experiment results of these models in the lower part of Table 1.

Observation: Using GRU as an aggregation method works better than conventional
methods. Compared with using global add pooling, the experiment results
indicate a significant improvement in the performance of GNN models across all
evaluation metrics by employing GRU as the aggregation operator. The
improvement verifies our perspective discussed in Section 4.2. Expanding the
tree structure graph through post-order traversal enables GRU to learn
dependencies between nodes in the actual order of how nodes are executed in
the DBMS and aggregate the node features utilizing GRU’s gating mechanism. By
leveraging the GRU for aggregation, the generated query plan representation
can preserve more structural information and more valuable node features,
thereby enhancing the model’s ability to predict cost estimation accurately.

Observation: Utilizing the direction of the edges in the query plan tree
improves the representation performance of GNN models. Our experiments
demonstrate that simply using single-directed or undirected edges does not
have a noticeable impact on the representation performance of the GNN-based
tree models. However, models employing weighted directed GNN all show
significant cost estimation performance improvements, which both promote
message passing between nodes in the tree structure graph and allow nodes to
learn the parent-child relationship through weighted directed edges, thereby
enabling the model to capture more accurately structural and logical
information of query plan even in complex workload representation tasks.

Observation: Directed TransformerConv + GRU Aggregation Operator performs much
better than other tree models. Our experimental findings confirm that the
novel architecture that we introduced, combining directed TransformerConv and
GRU as the aggregation operator, significantly outperforms other GNN-based as
well as the state-of-the-art non-GNN tree models. Although it requires a
higher inference overhead for running two complete GNN layers, it undoubtedly
demonstrates the great potential and research value of GNN technology in query
plan representation.

Figure 4: Performance comparison of different tree models of the cost
estimation task in TPC-DS workload. (a) is the inference time of each tree
model, (b) is Spearman’s rank correlation coefficient and (c) is the mean and
median Q-error experimental results.

###  5.4 Plan Selection Performance and Analysis

We evaluate the impact of different tree models on plan selection performance
when there are multiple candidate plans. The experimental results on Plan
Suboptimality are shown in Table 2.

Table 2: Plan Suboptimality performance of tree models in TPC-DS workloads.
The best results in each column are underlined.

Tree Model |  Median Plan Subopt |  90th Plan Subopt |  99th Plan Subopt |  Top 50% Mean Plan Subopt |  Top 90% Mean Plan Subopt |  Top 99% Mean Plan Subopt
---|---|---|---|---|---|---
GRU | 1.049 | 2.478 | 97.991 | 1.013 | 1.139 | 1.581
LSTM | 1.052 | 2.447 | 87.656 | 1.013 | 1.143 | 1.637
LSTM + Self-Attention | 1.051 | 2.593 | 102.315 | 1.013 | 1.146 | 1.881
Tree-LSTM | 1.047 | 2.551 | 72.518 | 1.012 | 1.137 | 1.824
TCNN | 1.054 | 2.610 | 93.157 | 1.014 | 1.161 | 1.923
GNN + AddPool | 1.052 | 2.543 | 100.953 | 1.013 | 1.148 | 1.700
Directed GNN + GRU | 1.045 | 2.094 | 85.441 | 1.011 | 1.122 | 1.516

Observation: The impact of tree models on the plan selection of the optimizer
is not significant. Experimental data shows that the impact of different tree
models on the plan selection task of the optimizer is not obvious. Although
the models employ various strategies to learn query plan representations, the
choice between pure tree models does not result in a sharp contrast in the
optimizer’s ability to select the plan closest to the optimal plan. This
subtle impact suggests that factors outside the tree model, such as the design
of other components within the optimizer or the specific optimizations based
on the workload’s characteristics, may also play a crucial role in the overall
robustness and effectiveness of the optimizer.

Observation: Improvements in cost estimation performance do not imply
improvements in plan selection. In the experimental results shown in Table 1,
the tree model we proposed based on directed GNN has a cost estimation
performance significantly ahead of other tree models. Although this trend is
still reflected in the plan selection evaluation metric, it can no longer
widen the gap with the performance of other models. This indicates that merely
enhancing the model’s cost estimation accuracy may not obviously improve the
optimizer’s real-world performance.

##  6 Conclusions and Future Work

We conducted a comparison and analysis of the performance and mechanisms of
the current tree models used in query plan representation in complex workloads
under tasks of cost estimation and plan selection. Subsequently, we introduced
an innovative tree model leveraging directed GNN to learn node representations
and a GRU as an aggregation operator. Through extensive experiments, our
proposed model was confirmed to markedly enhance the query plan representation
and cost estimation accuracy compared to existing models. The next phase of
our research will explore applying this model to a complete learning-based
query optimizer and further advancing its performance and robustness in plan
selection.

## References

  * [1] Buterez, D., Janet, J.P., Kiddle, S.J., Oglic, D., Liò, P.: Graph neural networks with adaptive readouts. Advances in Neural Information Processing Systems 35, 19746–19758 (2022)
  * [2] Chen, T., Gao, J., Chen, H., Tu, Y.: Loger: A learned optimizer towards generating efficient and robust query execution plans. Proceedings of the VLDB Endowment 16(7), 1777–1789 (2023)
  * [3] Cho, K., Van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y.: Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078 (2014)
  * [4] Ding, B., Das, S., Marcus, R., Wu, W., Chaudhuri, S., Narasayya, V.R.: Ai meets ai: Leveraging query executions to improve index recommendations. In: Proceedings of the 2019 International Conference on Management of Data. pp. 1241–1258 (2019)
  * [5] Ioannidis, Y.: The history of histograms (abridged). In: Proceedings 2003 VLDB Conference. pp. 19–30. Elsevier (2003)
  * [6] Kamali, A., Kantere, V., Zuzarte, C., Corvinelli, V.: Roq: Robust query optimization based on a risk-aware learned cost model. arXiv preprint arXiv:2401.15210 (2024)
  * [7] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [8] Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proceedings of the VLDB Endowment 9(3), 204–215 (2015)
  * [9] Li, L., Jamieson, K., Rostamizadeh, A., Gonina, E., Ben-Tzur, J., Hardt, M., Recht, B., Talwalkar, A.: A system for massively parallel hyperparameter tuning. Proceedings of Machine Learning and Systems 2, 230–246 (2020)
  * [10] Liu, S., Chen, X., Zhao, Y., Chen, J., Zhou, R., Zheng, K.: Efficient learning with pseudo labels for query cost estimation. In: Proceedings of the 31st ACM International Conference on Information & Knowledge Management. pp. 1309–1318 (2022)
  * [11] Marcus, R., Negi, P., Mao, H., Tatbul, N., Alizadeh, M., Kraska, T.: Bao: Making learned query optimization practical. In: Proceedings of the 2021 International Conference on Management of Data. pp. 1275–1288 (2021)
  * [12] Marcus, R., Negi, P., Mao, H., Zhang, C., Alizadeh, M., Kraska, T., Papaemmanouil, O., Tatbul, N.: Neo: A learned query optimizer. arXiv preprint arXiv:1904.03711 (2019)
  * [13] Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)
  * [14] Mou, L., Li, G., Zhang, L., Wang, T., Jin, Z.: Convolutional neural networks over tree structures for programming language processing. In: Proceedings of the AAAI conference on artificial intelligence. vol. 30 (2016)
  * [15] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al.: Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems 32 (2019)
  * [16] Poess, M., Floyd, C.: New tpc benchmarks for decision support and web commerce. ACM Sigmod Record 29(4), 64–71 (2000)
  * [17] Poess, M., Nambiar, R.O., Walrath, D.: Why you should run tpc-ds: A workload analysis. In: VLDB. vol. 7, pp. 1138–1149 (2007)
  * [18] Rossi, E., Charpentier, B., Di Giovanni, F., Frasca, F., Günnemann, S., Bronstein, M.: Edge directionality improves learning on heterophilic graphs. arXiv preprint arXiv:2305.10498 (2023)
  * [19] Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., Sun, Y.: Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509 (2020)
  * [20] Sun, J., Li, G.: An end-to-end learning-based cost estimator. arXiv preprint arXiv:1906.02560 (2019)
  * [21] Tai, K.S., Socher, R., Manning, C.D.: Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.00075 (2015)
  * [22] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Advances in neural information processing systems 30 (2017)
  * [23] Yu, X., Li, G., Chai, C., Tang, N.: Reinforcement learning with tree-lstm for join order selection. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE). pp. 1297–1308. IEEE (2020)
  * [24] Zhao, Y., Cong, G., Shi, J., Miao, C.: Queryformer: A tree transformer model for query plan representation. Proceedings of the VLDB Endowment 15(8), 1658–1670 (2022)
  * [25] Zhao, Y., Li, Z., Cong, G.: A comparative study and component analysis of query plan representation techniques in ml4db studies. Proceedings of the VLDB Endowment 17(4), 823–835 (2023)
  * [26] Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., Sun, M.: Graph neural networks: A review of methods and applications. AI open 1, 57–81 (2020)