|
|
Incremental join view maintenance on distributed log-structured storage |
Huichao DUAN, Huiqi HU( ), Weining QIAN, Aoying ZHOU |
School of Data Science and Engineering, East China Normal University, Shanghai 200062, China |
|
|
Abstract Modern database systems desperate for the ability to support highly scalable transactions and efficient queries simultaneously for real-time applications. One solution is to utilize query optimization techniques on the on-line transaction processing (OLTP) systems. The materialized view is considered as a panacea to decrease query latency. However, it also involves the significant cost of maintenance which trades away transaction performance. In this paper, we examine the design space and conclude several design features for the implementation of a view on a distributed log-structured merge-tree (LSMtree), which is a well-known structure for improving data write performance. As a result, we develop two incremental view maintenance (IVM) approaches on LSM-tree. One avoids join computation in view maintenance transactions. Another with two optimizations is proposed to decouple the view maintenance with the transaction process. Under the asynchronous update, we also provide consistency queries for views. Experiments on TPC-H benchmark show our methods achieve better performance than straightforward methods on different workloads.
|
Keywords
materialized views
asynchronous maintenance
hybrid transaction and analytical process
LSM-tree
|
Corresponding Author(s):
Huiqi HU
|
Just Accepted Date: 09 May 2020
Issue Date: 27 January 2021
|
|
1 |
D J Abadi, S Madden, N Hachem. Column-stores vs. row-stores: how different are they really? In: Proceedings of 2008 ACM International Conference on Management of Data. 2008, 967–980
https://doi.org/10.1145/1376616.1376712
|
2 |
C Q Zhan, M M Su, C X Wei, X Q Peng, L Lin, S Wang, Z Chen, F F Li, Y Pan, F Zheng, C L Chai. Analyticdb: real-time OLAP database system at alibaba cloud. Proceedings of the VLDB Endowment, 2019, 12(12): 2059–2070
https://doi.org/10.14778/3352063.3352124
|
3 |
A Kemper, T Neumann. Hyper: a hybrid oltp&olap main memory database system based on virtual memory snapshots. In: Proceedings of the 27th IEEE International Conference on Data Engineering. 2011, 195–206
https://doi.org/10.1109/ICDE.2011.5767867
|
4 |
R Chirkova, J Yang. Materialized views. Foundations and Trends in Databases, 2012, 4(4): 295–405
https://doi.org/10.1561/1900000020
|
5 |
H C Duan, H Q Hu, W N Qian, H X Ma, X L Wang, A Y Zhou. Incremental materialized view maintenance on distributed log-structured mergetree. In: Proceedings of the 23rd International Conference on Database Systems for Advanced Applications. 2018, 682–700
https://doi.org/10.1007/978-3-319-91458-9_42
|
6 |
F Chang, J Dean, S Ghemawat, W C Hsieh, D A Wallach, M Burrows, T Chandra, A Fikes, R E Gruber. Bigtable: a distributed storage system for structured data. ACM Transactions on Computer Systems, 2008, 26(2): 4
https://doi.org/10.1145/1365815.1365816
|
7 |
A Lakshman, P Malik. Cassandra: a decentralized structured storage system. Operating Systems Review, 2010, 44(2): 35–40
https://doi.org/10.1145/1773912.1773922
|
8 |
G Huang, X T Cheng, J Y Wang, Y J Wang, D C He, T Y Zhang, F F Li, S Wang, W Cao, Q Li. X-engine: an optimized storage engine for largescale e-commerce transaction processing. In: Proceedings of the 2019 ACM International Conference on Management of Data. 2019, 651–665
https://doi.org/10.1145/3299869.3314041
|
9 |
S Ghemawat, H Gobioff, S Leung. The google file system. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles. 2003, 29–43
https://doi.org/10.1145/1165389.945450
|
10 |
J J Levandoski, D B Lomet, S Sengupta. The Bw-tree: a B-tree for new hardware platforms. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2013, 302–313
https://doi.org/10.1109/ICDE.2013.6544834
|
11 |
H Berenson, P A Bernstein, J Gray, J Melton, E J O’Neil, P E O’Neil. A critique of ANSI SQL isolation levels. In: Proceedings of the 1995 ACM International Conference on Management of Data. 1995, 1–10
https://doi.org/10.1145/568271.223785
|
12 |
H Garcia-Molina, J D Ullman, J Widom. Database System Implementation. New Jersey: Prentice Hall, 2000
|
13 |
C A Galindo-Legaria. Outerjoins as disjunctions. In: Proceedings of 1994 ACM International Conference on Management of Data. 1994, 348–358
https://doi.org/10.1145/191843.191908
|
14 |
R G Bello, K Dias, A Downing, J J F Jr, J L Finnerty, W D Norcott, H Sun, A Witkowski, M Ziauddin. Materialized views in oracle. In: Proceedings of the 24th International Conference on Very Large Data Bases. 1998, 659–664
|
15 |
M Zaharioudakis, R Cochrane, G Lapis, H Pirahesh, M Urata. Answering complex SQL queries using automatic summary tables. In: Proceedings of the 2000 ACM International Conference on Management of Data. 2000, 105–116
https://doi.org/10.1145/335191.335390
|
16 |
J Goldstein, P Larson. Optimizing queries using materialized views: a practical, scalable solution. In: Proceedings of the 2001 ACM International Conference on Management of Data. 2001, 331–342
https://doi.org/10.1145/376284.375706
|
17 |
S Agrawal, S Chaudhuri, V R Narasayya. Automated selection of materialized views and indexes in SQL databases. In: Proceedings of the 26th International Conference on Very Large Data Bases. 2000, 496–505
|
18 |
S Agrawal, E Chu, V R Narasayya. Automatic physical design tuning: workload as a sequence. In: Proceedings of 2006 ACMInternational Conference on Management of Data. 2006, 683–694
https://doi.org/10.1145/1142473.1142549
|
19 |
S Chaudhuri, V R Narasayya. Self-tuning database systems: a decade of progress. In: Proceedings of the 33rd International Conference on Very Large Data Bases. 2007, 3–14
|
20 |
J R Zhou, P Larson, H G Elmongui. Lazy maintenance of materialized views. In: Proceedings of the 33rd International Conference on Very Large Data Bases. 2007, 231–242
|
21 |
P Agrawal, A Silberstein, B F Cooper, U Srivastava, R Ramakrishnan. Asynchronous view maintenance for VLSD databases. In: Proceedings of 1994 ACM International Conference on Management of Data. 2009, 179–192
https://doi.org/10.1145/1559845.1559866
|
22 |
R K Lomotey, R Deters. Terms analytics service for CouchDB: a document-based NoSQL. International Journal of Big Data Intelligence, 2015, 2(1): 23–36
https://doi.org/10.1504/IJBDI.2015.067567
|
23 |
P Larson, J R Zhou. Efficient maintenance of materialized outer-join views. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2007, 56–65
https://doi.org/10.1109/ICDE.2007.367851
|
24 |
Y Katsis, K W Ong, Y Papakonstantinou, K K Zhao. Utilizing IDs to accelerate incremental view maintenance. In: Proceedings of 2015 ACM International Conference on Management of Data. 2015, 1985–2000
https://doi.org/10.1145/2723372.2750546
|
25 |
Y Ahmad, O Kennedy, C Koch, M Nikolic. Dbtoaster: higher-order delta processing for dynamic, frequently fresh views. Proceedings of the VLDB Endowment, 2012, 5(10): 968–979
https://doi.org/10.14778/2336664.2336670
|
26 |
M Nikolic, M Dashti, C Koch. How to win a hot dog eating contest: distributed incremental view maintenance with batch updates. In: Proceedings of 2016 ACM International Conference on Management of Data. 2016, 511–526
https://doi.org/10.1145/2882903.2915246
|
27 |
P O’Neil, E Cheng, D Gawlick, E O’Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33(4): 351–385
https://doi.org/10.1007/s002360050048
|
28 |
G DeCandia, D Hastorun, M Jampani, G Kakulapati, A Lakshman, A Pilchin, S Sivasubramanian, P Vosshall, W Vogels. Dynamo: amazon’s highly available key-value store. ACM SIGOPS Operating Systems Review, 2007, 41(6): 205–220
https://doi.org/10.1145/1323293.1294281
|
29 |
R Sears, R Ramakrishnan. BLSM: a general purpose log structured merge tree. In: Proceedings of 2012 ACM International Conference on Management of Data. 2012, 217–228
https://doi.org/10.1145/2213836.2213862
|
30 |
W Tan, S Tata, Y Z Tang, L L Fong. Diff-index: differentiated index in distributed log-structured data stores. In: Proceedings of the 17th International Conference on Extending Database Technology. 2014, 700–711
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|