Flash-Aware Storage of the Column Oriented Databases

• Autorzy: Macyna Wojciech , Kukowski Michal

Identyfikatory

DOI

10.3233/FI-2020-1915

• Języki publikacji: EN

Abstrakty

EN

Solid state disks become the very popular storage devices. Nonetheless, their architecture based on flash memory has some limitations. They suffer from poor random write performance, as the flash memory blocks must be erased before write. Nowadays, among many database models, the column-oriented databases have attracted the attention. In this model, the data from the particular columns of the database table are stored separately in the memory blocks. As a consequence, only such columns are derived from the memory which are necessary for query execution. In this way, I/O number is reduced, what drastically increases the database performance. This paper proposes a new storage method for the column oriented databases on solid state disks. In this method, the data from each column is stored as a separated structure, called Column-Flash tree (CF-tree). The table is always sorted by a particular column (or a set of columns). Due to utilizing fractional cascading and tree-like structure, the efficiency of update and search is obtained. The storage may be adjusted to the altering query pattern and disk characteristics by changing the height of the CF-tree and the capacity of its levels. In contrast to the other models, the approach may be applied to both read and write optimized databases.

Słowa kluczowe

EN

column oriented database; data storage; solid state disk

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 173, nr 1
• Strony: 47--72
• Opis fizyczny: Bibliogr. 36 poz., rys., tab., wykr.

Twórcy

autor

Macyna Wojciech

• Institute of Computer Science, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, 50-370 Wroclaw, Poland

autor

Kukowski Michal

• Institute of Computer Science, Wroclaw University of Technology, Wybrzeze Wyspianskiego 27, 50-370 Wroclaw, Poland

Bibliografia

• [1] Cho H, Shin D, Eom YI. KAST: K-associative sector translation for NAND flash memory in real-time systems. In: DATE’09. 2009 pp. 507-512. doi:10.1109/DATE.2009.5090717.
• [2] Park D, Debnath BK, Du DHC. A Dynamic Switching Flash Translation Layer Based on Page-Level Mapping. IEICE Transactions, 2016. 99-D(6):1502-1511. URL http://search.ieice.org/bin/summary.php?id=e99-d\_6\_1502.
• [3] Wang Y, Qin Z, Chen R, Shao Z, Wang Q, Li S, Yang LT. A Real-Time Flash Translation Layer for NAND Flash Memory Storage Systems. IEEE Trans. Multi-Scale Computing Systems, 2016. 2(1):17-29. doi:10.1109/TMSCS.2016.2516015.
• [4] Lee J, Roh H, Park S. External Mergesort for Flash-Based Solid State Drives. IEEE Trans. Computers, 2016. 65(5):1518-1527. doi:10.1109/TC.2015.2451631.
• [5] Wu CH, Kuo TW, Chang LP. An efficient B-tree layer implementation for flash-memory storage systems. ACM Trans. Embedded Comput. Syst., 2007. 6(3).
• [6] Li Y, He B, Yang RJ, Luo Q, Yi K. Tree Indexing on Solid State Drives. Proc. VLDB Endow., 2010. 3(1-2):1195-1206. doi:10.14778/1920841.1920990.
• [7] Agrawal D, Ganesan D, Sitaraman R, Diao Y, Singh S. Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices. Proc. VLDB Endow., 2009. 2(1):361-372. doi:10.14778/1687627.1687669.
• [8] Athanassoulis M, Ailamaki A. BF-tree: Approximate Tree Indexing. Proc. VLDB Endow., 2014. 7(14):1881-1892. doi:10.14778/2733085.2733094.
• [9] Byun S, Jang S. A Column-Aware Index Management Using Flash Memory for Read-Intensive Databases. JIPS, 2015. 11(3):389-405. doi:10.3745/JIPS.04.0017.
• [10] Jørgensen MV, Rasmussen RB, Šaltenis S, Schjønning C. FB-tree: A B+-tree for Flash-based SSDs. In: Proceedings of the 15th Symposium on International Database Engineering & Applications, IDEAS ’11. ACM, New York, NY, USA. ISBN: 978-1-4503-0627-0, 2011 pp. 34-42. doi:10.1145/2076623.2076629.
• [11] Jabarov E, On B, Choi GS, Park M. R-Tree for phase change memory. Comput. Sci. Inf. Syst., 2017. 14(2):347-367. URL http://doiserbia.nb.rs/Article.aspx?id=1820-02141700008J.
• [12] Stonebraker M, Abadi DJ, Batkin A, Chen X, Cherniack M, Ferreira M, Lau E, Lin A, Madden S, O’Neil E, O’Neil P, Rasin A, Tran N, Zdonik S. C-store: a column-oriented DBMS. In: Proceedings of the 31st international conference on Very large data bases, VLDB ’05. VLDB Endowment. ISBN: 1-59593-154-6, 2005 pp. 553-564. URL http://dl.acm.org/citation.cfm?id=1083592.1083658.
• [13] Abadi D, Boncz P, Harizopoulos S, Idreos S, Madden S. The Design and Implementation of Modern Column-Oriented Database Systems. Foundations and Trends in Databases, 5(3): 197-280, 2013.
• [14] Héman S, Zukowski M, Nes NJ, Sidirourgos L, Boncz P. Positional Update Handling in Column Stores. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD’10. ACM, New York, NY, USA. ISBN: 978-1-4503-0032-2, 2010 pp. 543-554. doi:10.1145/1807167.1807227.
• [15] Yu F, Matacic T, Latronica BJ, Hou W. OB-tree: a new write optimisation index on out-of-core column-store databases. IJIIDS, 2018. 11(1):46-66. doi:10.1504/IJIIDS.2018.10012700.
• [16] Ivanova EV, Sokolinsky LB. Parallel processing of very large databases using distributed column indexes. Programming and Computer Software, 2017. 43(3):131-144. doi:10.1134/S0361768817030069.
• [17] Boissier M, Djürken T, Schlosser R, Faust M. A Cost-Aware and Workload-Based Index Advisor for Columnar In-Memory Databases. In: Information and Software Technologies - 22nd International Conference, ICIST 2016, Druskininkai, Lithuania, October 13-15, 2016, Proceedings. 2016 pp. 285-299. doi:10.1007/978-3-319-46254-7\_23.
• [18] Tsirogiannis D, Harizopoulos S, Shah MA, Wiener JL, Graefe G. Query processing techniques for solid state drives. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009. 2009 pp. 59-72. doi:10.1145/1559845.1559854.
• [19] Boncz PA, Zukowski M, Nes N. MonetDB/X100: Hyper-Pipelining Query Execution. In: CIDR. 2005 pp. 225-237.
• [20] Shim HJ, Li XS, Yoon SK, Kim SD. Locality Aware Management on NAND Flash-based Main Memory for In-memory Database Systems. In: Proceedings of the Sixth International Conference on Emerging Databases: Technologies, Applications, and Theory, EDB ’16. ACM, New York, NY, USA. ISBN: 978-1-4503-4754-9, 2016 pp. 90-94. doi:10.1145/3007818.3007830.
• [21] Abadi D, Madden S, Ferreira M. Integrating Compression and Execution in Column-oriented Database Systems. In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD ’06. ACM, New York, NY, USA. ISBN: 1-59593-434-0, 2006 pp. 671-682. doi:10.1145/1142473.1142548.
• [22] Binnig C, Hildenbrand S, Färber F. Dictionary-based Order-preserving String Compression for Main Memory Column Stores. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD ’09. ACM, New York, NY, USA. ISBN: 978-1-60558-551-2, 2009 pp. 283-296. doi:10.1145/1559845.1559877.
• [23] Waage T. A Framework for Property-preserving Encryption in Wide Column Store Databases. Ph.D. thesis, University of Göttingen, Germany, 2017. URL http://nbn-resolving.de/urn:nbn:de:gbv:7-11858/00-1735-0000-0023-3ED6-D-8.
• [24] Hildebrandt J, Habich D, Lehner W. Model-Driven Integration of Compression Algorithms in Column-Store Database Systems. In: Proceedings of the Conference ”Lernen, Wissen, Daten, Analysen”, Potsdam, Germany, September 12-14, 2016. 2016 pp. 30-41. URL http://ceur-ws.org/Vol-1670/paper-18.pdf.
• [25] Boissier M, Jendruk M. Workload-Driven and Robust Selection of Compression Schemes for Column Stores. In: Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019. 2019 pp. 674-677. doi:10.5441/002/edbt.2019.84.
• [26] Sridhar KT, Johnson J. Entropy Aware Adaptive Compression for SQL Column Stores. In: Beyond Databases, Architectures and Structures. Facing the Challenges of Data Proliferation and Growing Variety - 14th International Conference, BDAS 2018, Held at the 24th IFIP World Computer Congress, WCC 2018, Poznan, Poland, September 18-20, 2018, Proceedings. 2018 pp. 90-104. doi:10.1007/978-3-319-99987-6\_7.
• [27] Kastrati F, Moerkotte G. Optimization of Disjunctive Predicates for Main Memory Column Stores. In: Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017. 2017 pp. 731-744. doi:10.1145/3035918.3064022.
• [28] Xu W, Feng Z, Lo E. Fast Multi-Column Sorting in Main-Memory Column-Stores. In: Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016. 2016 pp. 1263-1278. doi:10.1145/2882903.2915205.
• [29] Wang P, Li S, Sun G, Wang X, Chen Y, Li H, Cong J, Xiao N, Zhang T. RC-NVM: Enabling Symmetric Row and Column Memory Accesses for In-memory Databases. In: IEEE International Symposium on High Performance Computer Architecture, HPCA 2018, Vienna, Austria, February 24-28, 2018. 2018 pp. 518-530. doi:10.1109/HPCA.2018.00051.
• [30] Ryu C, Lee S, Kim K, Park K, Kwon YS, Cha SK, Song C, Ziegler E, Muench S. Optimizing Scalar User-Defined Functions in In-Memory Column-Store Database Systems. In: Database Systems for Advanced Applications - 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30, 2017, Proceedings, Part II. 2017 pp. 568-580. doi:10.1007/978-3-319-55699-4\_35.
• [31] Cao Q, Liang Z, Fan Y, Meng X. A Flash-based Decomposition Storage Model. In: Proceedings of the 17th International Conference on Database Systems for Advanced Applications, DASFAA’12. Springer-Verlag, Berlin, Heidelberg. ISBN: 978-3-642-29022-0, 2012 pp. 73-80. doi:10.1007/978-3-642-29023-7_8.
• [32] Barata M, Bernardino J, Furtado P. An Overview of Decision Support Benchmarks: TPC-DS, TPC-H and SSB, pp. 619-628. Springer International Publishing, Cham. ISBN: 978-3-319-16486-1, 2015. doi:10.1007/978-3-319-16486-1_61.
• [33] Abadi DJ, Madden SR, Hachem N. Column-stores vs. Row-stores: How Different Are They Really? In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD’08. ACM, New York, NY, USA. ISBN: 978-1-60558-102-6, 2008 pp. 967-980. doi:10.1145/1376616.1376712.
• [34] Shah MA, Harizopoulos S, Wiener JL, Graefe G. Fast Scans and Joins Using Flash Drives. In: Proceedings of the 4th International Workshop on Data Management on New Hardware, DaMoN ’08. ACM, New York, NY, USA. ISBN: 978-1-60558-184-2, 2008 pp. 17-24. doi:10.1145/1457150.1457154.
• [35] Zukowski M, Boncz PA. Vectorwise: Beyond Column Stores. IEEE Data Eng. Bull., 2012. 35(1):21-27. URL http://sites.computer.org/debull/A12mar/vectorwise.pdf.
• [36] Dewitt DJ, Madden SR, Abadi DJ, Abadi DJ, Myers DS, Myers DS. Materialization strategies in a column-oriented dbms. In: In Proc. of ICDE. 2007. doi:10.1109/ICDE.2007.367892.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).