Standard
Implementing the Comparison-Based External Sort. / Polyntsov, Michael; Grigorev, Valentin; Smirnov, Kirill; Chernishev, George.
New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: DOING, K-GALS, MADEISD, MegaData, SWODCH, Turin, Italy, September 5–8, 2022, Proceedings. ed. / Silvia Chiusano; Tania Cerquitelli; Robert Wrembel; Kjetil Nørvåg; Barbara Catania; Genoveva Vargas-Solar; Ester Zumpano. Vol. 1652 Communications in Computer and Information Science. ed. Cham : Springer Nature, 2022. p. 500-511 (Communications in Computer and Information Science; Vol. 1652 CCIS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Polyntsov, M, Grigorev, V, Smirnov, K & Chernishev, G 2022,
Implementing the Comparison-Based External Sort. in S Chiusano, T Cerquitelli, R Wrembel, K Nørvåg, B Catania, G Vargas-Solar & E Zumpano (eds),
New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: DOING, K-GALS, MADEISD, MegaData, SWODCH, Turin, Italy, September 5–8, 2022, Proceedings. Communications in Computer and Information Science edn, vol. 1652, Communications in Computer and Information Science, vol. 1652 CCIS, Springer Nature, Cham, pp. 500-511, European Conference on Advances in Databases and Information Systems, Turin, Italy,
5/09/22.
https://doi.org/10.1007/978-3-031-15743-1_46
APA
Polyntsov, M., Grigorev, V., Smirnov, K., & Chernishev, G. (2022).
Implementing the Comparison-Based External Sort. In S. Chiusano, T. Cerquitelli, R. Wrembel, K. Nørvåg, B. Catania, G. Vargas-Solar, & E. Zumpano (Eds.),
New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: DOING, K-GALS, MADEISD, MegaData, SWODCH, Turin, Italy, September 5–8, 2022, Proceedings (Communications in Computer and Information Science ed., Vol. 1652, pp. 500-511). (Communications in Computer and Information Science; Vol. 1652 CCIS). Springer Nature.
https://doi.org/10.1007/978-3-031-15743-1_46
Vancouver
Polyntsov M, Grigorev V, Smirnov K, Chernishev G.
Implementing the Comparison-Based External Sort. In Chiusano S, Cerquitelli T, Wrembel R, Nørvåg K, Catania B, Vargas-Solar G, Zumpano E, editors, New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: DOING, K-GALS, MADEISD, MegaData, SWODCH, Turin, Italy, September 5–8, 2022, Proceedings. Communications in Computer and Information Science ed. Vol. 1652. Cham: Springer Nature. 2022. p. 500-511. (Communications in Computer and Information Science).
https://doi.org/10.1007/978-3-031-15743-1_46
Author
Polyntsov, Michael ; Grigorev, Valentin ; Smirnov, Kirill ; Chernishev, George. /
Implementing the Comparison-Based External Sort. New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: ADBIS 2022 Short Papers, Doctoral Consortium and Workshops: DOING, K-GALS, MADEISD, MegaData, SWODCH, Turin, Italy, September 5–8, 2022, Proceedings. editor / Silvia Chiusano ; Tania Cerquitelli ; Robert Wrembel ; Kjetil Nørvåg ; Barbara Catania ; Genoveva Vargas-Solar ; Ester Zumpano. Vol. 1652 Communications in Computer and Information Science. ed. Cham : Springer Nature, 2022. pp. 500-511 (Communications in Computer and Information Science).
BibTeX
@inproceedings{bb02b967475440a4b3cf3d80556a00d5,
title = "Implementing the Comparison-Based External Sort",
abstract = "In the age of big data, sorting is an indispensable operation for DBMSes and similar systems. Having data sorted can help produce query plans with significantly lower run times. It also can provide other benefits like having non-blocking operators which will produce data steadily (without bursts), or operators with reduced memory footprint. Sorting may be required on any step of query processing, i.e., be it source data or intermediate results. At the same time, the data to be sorted may not fit into main memory. In this case, an external sort operator, which writes intermediate results to disk, should be used. In this paper we consider an external sort operator of the comparison-based sort type. We discuss its implementation and describe related design decisions. Our aim is to study the impact on performance of a data structure used on the merge step. For this, we have experimentally evaluated three data structures implemented inside a DBMS. Results have shown that it is worthwhile to make an effort to implement an efficient data structure for run merging, even on modern commodity computers which are usually disk-bound. Moreover, we demonstrated that using a loser tree is a more efficient approach than both the naive approach and the heap-based one.",
keywords = "External sort, Query engines, Query processing",
author = "Michael Polyntsov and Valentin Grigorev and Kirill Smirnov and George Chernishev",
year = "2022",
month = aug,
day = "29",
doi = "10.1007/978-3-031-15743-1_46",
language = "English",
isbn = "978-3-031-15742-4",
volume = "1652",
series = "Communications in Computer and Information Science",
publisher = "Springer Nature",
pages = "500--511",
editor = "Silvia Chiusano and Tania Cerquitelli and Robert Wrembel and Kjetil N{\o}rv{\aa}g and Barbara Catania and Genoveva Vargas-Solar and Ester Zumpano",
booktitle = "New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops",
address = "Germany",
edition = "Communications in Computer and Information Science",
note = "null ; Conference date: 05-09-2022 Through 08-09-2022",
url = "https://adbis2022.polito.it/conference/",
}
RIS
TY - GEN
T1 - Implementing the Comparison-Based External Sort
AU - Polyntsov, Michael
AU - Grigorev, Valentin
AU - Smirnov, Kirill
AU - Chernishev, George
PY - 2022/8/29
Y1 - 2022/8/29
N2 - In the age of big data, sorting is an indispensable operation for DBMSes and similar systems. Having data sorted can help produce query plans with significantly lower run times. It also can provide other benefits like having non-blocking operators which will produce data steadily (without bursts), or operators with reduced memory footprint. Sorting may be required on any step of query processing, i.e., be it source data or intermediate results. At the same time, the data to be sorted may not fit into main memory. In this case, an external sort operator, which writes intermediate results to disk, should be used. In this paper we consider an external sort operator of the comparison-based sort type. We discuss its implementation and describe related design decisions. Our aim is to study the impact on performance of a data structure used on the merge step. For this, we have experimentally evaluated three data structures implemented inside a DBMS. Results have shown that it is worthwhile to make an effort to implement an efficient data structure for run merging, even on modern commodity computers which are usually disk-bound. Moreover, we demonstrated that using a loser tree is a more efficient approach than both the naive approach and the heap-based one.
AB - In the age of big data, sorting is an indispensable operation for DBMSes and similar systems. Having data sorted can help produce query plans with significantly lower run times. It also can provide other benefits like having non-blocking operators which will produce data steadily (without bursts), or operators with reduced memory footprint. Sorting may be required on any step of query processing, i.e., be it source data or intermediate results. At the same time, the data to be sorted may not fit into main memory. In this case, an external sort operator, which writes intermediate results to disk, should be used. In this paper we consider an external sort operator of the comparison-based sort type. We discuss its implementation and describe related design decisions. Our aim is to study the impact on performance of a data structure used on the merge step. For this, we have experimentally evaluated three data structures implemented inside a DBMS. Results have shown that it is worthwhile to make an effort to implement an efficient data structure for run merging, even on modern commodity computers which are usually disk-bound. Moreover, we demonstrated that using a loser tree is a more efficient approach than both the naive approach and the heap-based one.
KW - External sort
KW - Query engines
KW - Query processing
UR - https://www.mendeley.com/catalogue/b76006a7-3a35-3a77-8430-5d4a9bfbb419/
UR - http://www.scopus.com/inward/record.url?scp=85137992346&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-15743-1_46
DO - 10.1007/978-3-031-15743-1_46
M3 - Conference contribution
SN - 978-3-031-15742-4
VL - 1652
T3 - Communications in Computer and Information Science
SP - 500
EP - 511
BT - New Trends in Database and Information Systems - ADBIS 2022 Short Papers, Doctoral Consortium and Workshops
A2 - Chiusano, Silvia
A2 - Cerquitelli, Tania
A2 - Wrembel, Robert
A2 - Nørvåg, Kjetil
A2 - Catania, Barbara
A2 - Vargas-Solar, Genoveva
A2 - Zumpano, Ester
PB - Springer Nature
CY - Cham
Y2 - 5 September 2022 through 8 September 2022
ER -