Query Rewriting Based on Meta-Granular Aggregation

• Autorzy: Wiśniewski P. , Stencel K.

Identyfikatory

DOI

10.3233/FI-2014-1139

• Języki publikacji: EN

Abstrakty

EN

Analytic database queries are exceptionally time consuming. Decision support systems employ various execution techniques in order to accelerate such queries and reduce their resource consumption. Probably the most important of them consists in materialization of partial results. However, any introduction of derived objects into the database schema increases the cost of software development, since programmers must take care of their usage and synchronization. In this article we consider using partial aggregations materialized in additional tables. The idea is based on the concept of metagranules that represent the information on grouping and used aggregations. Metagranules have a natural partial order that guides the optimisation process. We present solutions to two problems. Firstly, we assume that a set of stored metagranules is given and we optimize a query. We present a novel query rewriting method to make analytic queries use the information stored in metagranules. We also describe our proof-of-concept implementation of this method and perform an extensive experimental evaluation using databases of the size up to 0:5 TiB and 6 billions rows. Secondly, we assume that a database workload is given and we want to select the optimal set of metagranules to materialize. Although each metagranule accelerates some queries, it also imposes a significant overhead on updates. Therefore, we propose a cost model that includes both benefits for queries and penalties for updates. We experiment with the complete search in the space of sets of metagranules to find the optimum. Finally, we empirically verify identified optimal sets against database instances up to 0:5 TiB with billions of rows and hundreds millions of aggregated rows.

Słowa kluczowe

EN

querying; meta-analysis; database searching; decision support systems; computer programmers; synchronization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 4
• Strony: 537--551
• Opis fizyczny: Bibliogr. 25 poz., rys., tab.

Twórcy

autor

Wiśniewski P.

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland

autor

Stencel K.

• Institute of Informatics, University of Warsaw, Warsaw, Poland

Bibliografia

• [1] Boncz, P. A., Manegold, S., Kersten, M. L.: Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct, PVLDB, 2(2), 2009, 1648–1653.
• [2] Boniewicz, A., Gawarkiewicz, M.,Wiśniewski, P.: Automatic Selection of Functional Indexes for Object Relational Mappings System, accepted to International Journal of Software Engineering and Its Applications, 7, 2013.
• [3] Bruno, N., Chaudhuri, S., Gravano, L.: STHoles: A Multidimensional Workload-Aware Histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001 (S. Mehrotra, T. K. Sellis, Eds.), ACM, 2001, ISBN 1-58113-332-4.
• [4] Chaudhuri, S., Narasayya, V. R.: Self-Tuning Database Systems: A Decade of Progress, Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007 (C. Koch, J. Gehrke, M. N. Garofalakis, D. Srivastava, K. Aberer, A. Deshpande, D. Florescu, C. Y. Chan, V. Ganti, C. Kanne, W. Klas, E. J. Neuhold, Eds.), ACM, 2007, ISBN 978-1-59593-649-3.
• [5] Deshpande, A., Ives, Z. G., Raman, V.: Adaptive Query Processing, Foundations and Trends in Databases, 1(1), 2007, 1–140.
• [6] Flexviews: Incrementally refreshable materialized views for MySQL, January 2012.
• [7] Gawarkiewicz, M., Wiśniewski, P.: Partial Aggregation Using Hibernate, in: Kim et al. [14], 90–99.
• [8] Hindshaw, F., Metzger, J., Zane, B.: Optimized Database Appliance, Patent No. U.S. 7,010,521 B2, Assignee: Netezza Corporation, Framingham, MA, issued March 7, 2006.
• [9] Ioannidis, Y. E.: The History of Histograms (abridged), VLDB, 2003.
• [10] Ivanova, M., Kersten, M. L., Nes, N. J., Goncalves, R.: An architecture for recycling intermediates in a column-store, ACM Trans. Database Syst., 35(4), 2010, 24.
• [11] Ives, Z. G., Halevy, A. Y.,Weld, D. S.: Adapting to Source Properties in Processing Data Integration Queries, in: Weikum et al. [24], 395–406.
• [12] Kabra, N., DeWitt, D. J.: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans, SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA. (L. M. Haas, A. Tiwary, Eds.), ACM Press, 1998, ISBN 0-89791-995-5.
• [13] Kalyvianaki, E., Wiesemann, W., Vu, Q. H., Kuhn, D., Pietzuch, P.: SQPR: Stream query planning with reuse, Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11-16, 2011, Hannover, Germany (S. Abiteboul, K. Böhm, C. Koch, K. Tan, Eds.), IEEE Computer Society, 2011, ISBN 978-1-4244-8958-9.
• [14] Kim, T.-H., Adeli, H., Slezak, D., Sandnes, F. E., Song, X., Chung, K.-I., Arnett, K. P., Eds.: Future Generation Information Technology - Third International Conference, FGIT 2011 in Conjunction with GDC 2011, Jeju Island, Korea, December 8-10, 2011. Proceedings, vol. 7105 of Lecture Notes in Computer Science, Springer, 2011, ISBN 978-3-642-27141-0.
• [15] Markl, V., Raman, V., Simmen, D. E., Lohman, G. M., Pirahesh, H.: Robust Query Processing through Progressive Optimization, in: Weikum et al. [24], 659–670.
• [16] Melnik, S., Adya, A., Bernstein, P. A.: Compiling mappings to bridge applications and databases, ACM Trans. Database Syst., 33(4), 2008.
• [17] Mumick, I. S., Quass, D., Mumick, B. S.: Maintenance of Data Cubes and Summary Tables in a Warehouse, SIGMOD Conference (J. Peckham, Ed.), ACM Press, 1997.
• [18] O’Neil, E. J.: Object/relational mapping 2008: Hibernate and the Entity Data Model (EDM), SIGMOD Conference (J. T.-L. Wang, Ed.), ACM, 2008, ISBN 978-1-60558-102-6.
• [19] Salem, K., Beyer, K., Lindsay, B., Cochrane, R.: How to roll a join: asynchronous incremental view maintenance, SIGMOD Rec., 29(2), May 2000, 129–140, ISSN 0163-5808.
• [20] Slezak, D., Synak, P., Borkowski, J., Wroblewski, J., Toppin, G.: A Rough-Columnar RDBMS Engine – A Case Study of Correlated Subqueries, IEEE Data Eng. Bull., 35(1), 2012, 34–39.
• [21] Slezak, D., Synak, P., Wojna, A., Wroblewski, J.: Two Database Related Interpretations of Rough Approximations: Data Organization and Query Execution, Fundam. Inform., 127(1-4), 2013, 445–459.
• [22] Slezak, D., Wroblewski, J., Eastwood, V., Synak, P.: Brighthouse: an analytic data warehouse for ad-hoc queries, PVLDB, 1(2), 2008, 1337–1345.
• [23] Szumowska, A., Burzańska, M., Wiśniewski, P., Stencel, K.: Efficient Implementation of Recursive Queries in Major Object Relational Mapping Systems, in: Kim et al. [14], 78–89.
• [24] Weikum, G., König, A. C., Deßloch, S., Eds.: Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, ACM, 2004, ISBN 1-58113-859-8.
• [25] Wisniewski, P., Stencel, K.: Query Rewriting Based on Meta-Granular Aggregation, CS&P (M. S. Szczuka, L. Czaja, M. Kacprzak, Eds.), 1032, CEUR-WS.org, 2013.