Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

邮发代号 80-970

2019 Impact Factor: 1.275

Frontiers of Computer Science  2021, Vol. 15 Issue (4): 154607   https://doi.org/10.1007/s11704-020-9310-y
  本期目录
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
 全文: PDF(1502 KB)  
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.

Key wordsmaterialized views    asynchronous maintenance    hybrid transaction and analytical process    LSM-tree
收稿日期: 2019-08-21      出版日期: 2021-01-27
Corresponding Author(s): Huiqi HU   
 引用本文:   
. [J]. Frontiers of Computer Science, 2021, 15(4): 154607.
Huichao DUAN, Huiqi HU, Weining QIAN, Aoying ZHOU. Incremental join view maintenance on distributed log-structured storage. Front. Comput. Sci., 2021, 15(4): 154607.
 链接本文:  
https://academic.hep.com.cn/fcs/CN/10.1007/s11704-020-9310-y
https://academic.hep.com.cn/fcs/CN/Y2021/V15/I4/154607
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
[1] Highlights Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed