Special Issue: Computer Architecture and Systems

• Articles • Previous Articles     Next Articles

Efficient Execution of Multiple Queries on Deep Memory Hierarchy

Yan Zhang1, Zhi-Feng Chen2, and Yuan-Yuan Zhou3   

  1. 1National Laboratory on Machine Perception, Peking University, Beijing 100871, China 2Google Inc., 1600 Amphitheatre Parkway, Mountain View, CA 94043, U.S.A. 3Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801, U.S.A.
  • Received:2006-05-01 Revised:2006-12-19 Online:2007-03-10 Published:2007-03-10

This paper proposes a complementary novel idea, called MiniTasking to further reduce the number of cache misses by improving the data {\it temporal locality} for {\it multiple} concurrent queries. Our idea is based on the observation that, in many workloads such as decision support systems (DSS), there is usually significant amount of data sharing among different concurrent queries. MiniTasking exploits such data sharing to improve data temporal locality by scheduling query execution at three levels: query level batching, operator level grouping and mini-task level scheduling. The experimental results with various types of concurrent TPC-H query workloads show that, with the traditional N-ary Storage Model (NSM) layout, MiniTasking significantly reduces the L2 cache misses by up to 83\%, and thereby achieves 24\% reduction in execution time. With the Partition Attributes Across (PAX) layout, MiniTasking further reduces the cache misses by 65\% and the execution time by 9\%. For the TPC-H throughput test workload, MiniTasking improves the end performance up to 20\%.

Key words: satisfiability problem; optimization algorithm; nonlinear programming; convergence ratio; time complexity;

[1] Ailamaki A, DeWitt D J, Hill M D \it et al. \rm DBMSs on a modern processor: Where does time go In -\it Proc. VLDB'99}, Edinburgh, Scotland, UK, 1999, pp.266--277.

[2] Lo J L, Barroso L A, Eggers S J \it et al. \rm An analysis of database workload performance on simultaneous multithreaded processors. In -\it Proc. ISCA'98}, IEEE Computer Society, Barcelona, Spain, 1998, pp.39--50.

[3] Trancoso P, Larriba-Pey J L, Zhang Z \it et al. \rm The memory performance of -DSS} commercial workloads in shared-memory multiprocessors. In -\it Proc. HPCA'97}, San Antonio, Texas, USA, 1997, pp.250--260.

[4] Ailamaki A, DeWitt D J, Hill M D. Data page layouts for relational databases on deep memory hierarchies. -\it The VLDB Journal}, 2002, 11(3): 198--215. %

[23] Lo J L, Barroso L A, Eggers S J, K.~Gharachorloo, H.~M. Levy, and S.~S. % Parekh. %\newblock An analysis of database workload performance on simultaneous % multithreaded processors. %\newblock In -\it ISCA'98, Barcelona, Spain}, pages 39--50. IEEE Computer % Society, 1998.

[5] Hankins R A, Patel J M. Data morphing: An adaptive, cache-conscious storage technique. In -\it Proc. VLDB'03}, Berlin, Germany, 2003, pp.417--428.

[6]Chen S, Gibbons P B, Mowry T C. Improving index performance through prefetching. In -\it Proc. SIGMOD'01}, Santa Barbara, CA, USA, ACM Press, 2001, pp.235--246.

[7] Wolf M E, Lam M S. A data locality optimizing algorithm. In -\it Proc. PLDI'91}, Toronto, Ontario, Canada, 1991, pp.30--44.

[8] Philbin J, Edler J, Anshus O J \it et al. \rm Thread scheduling for cache locality. In -\it Proc. ASPLOS'96}, Cambridge, Massachusetts, USA, ACM Press, 1996, pp.60--71.

[9] Zhou Y, Wang L, Clark D W \it et al. \rm Thread scheduling for out-of-core applications with memory server on multicomputers. In -\it Proc. IOPADS'99}, Atlanta, GA, USA, ACM Press, 1999, pp.57--67.

[10] IBM. Personal communication with -IBM}, Jan. 2005.

[11] Finkelstein S. Common expression analysis in database applications. In -\it Proc. SIGMOD'82}, Orlando, Florida, USA, ACM Press, 1982 pp.235--245.

[12] Sellis T K. Multiple-query optimization. -\it ACM Trans. Database Syst.}, 1998, 13(1): 23--52.

[13] Sellis T K, Ghosh S. On the multiple-query optimization problem. -\it IEEE TKDE}, 1990, 2(2): 262--266.

[14] Gupta A, Sudarshan S, Viswanathan S. Query scheduling in multi query optimization. In -\it Proc. IDEAS'01}, Grenoble, France, IEEE Computer Society, 2001, pp.11--19.

[15] Carey M J, e David J DeWitt. Shoring up persistent applications. In -\it Proc. SIGMOD'94}, Minneapolis, USA, ACM Press, 1994, pp.383--394.

[16] Park J, Segev A. Using common subexpressions to optimize multiple queries. In -\it Proc. ICDE'88}, Los Angeles, CA, USA, IEEE Computer Society, 1988, pp.311--319.

[17] Dalvi N N, Sanghai S K, Roy P, Sudarshan S. Pipelining in multi-query optimization. In -\it Proc. PODS'01}, Santa Barbara, CA, USA, ACM Press, 2001, pp.59--70.

[18] Roy P, Seshadri S, Sudarshan S, Bhobe S. Efficient and extensible algorithms for multi query optimization. In -\it Proc. SIGMOD'00}, Dallas, Texas, USA, ACM Press, 2000, pp.249--260.

[19] Harizopoulos S, Shkapenyuk V, Ailamaki A. Qpipe: A simultaneously pipelined relational query engine. In -\it Proc. SIGMOD'05}, Baltimore, Maryland, USA, 2005, pp.383--394.

[20] O'Gorman K, Agrawal D, Abbadi A E. Multiple query optimization by cache-aware middleware using query teamwork. In -\it Proc. ICDE'02}, San Jose, CA, USA, IEEE Computer Society, 2002, p.274.

[21] Boncz P A, Manegold S, Kersten M L. Database architecture optimized for the new bottleneck: Memory access. In -\it Proc. VLDB'99}, Edinburgh, Scotland, UK, 1999, pp.54--65.

[22] Chen S, Gibbons P B, Mowry T C \it et al. \rm Fractal prefetching B$+$-trees: Optimizing both cache and disk performance. In -\it Proc. SIGMOD'02}, Madison, USA, ACM Press, 2002, pp.157--168.

[23] Kim K, Cha S K, Kwon K. Optimizing multidimensional index trees for main memory access. In -\it Proc. SIGMOD'01}, Santa Barbara, CA, USA, ACM Press, 2001, pp.139--150.

[24] Ramamurthy R, DeWitt D J, Su Q. A case for fractured mirrors. In -\it Proc. VLDB'02}, Hong Kong, China, 2002, pp.430--441.

[25] Zhou J, Ross K A. Buffering accesses to memory-resident index structures. In -\it Proc. VLDB'03}, Berlin, Germany, 2003, pp.405--416.

[26] Rao J, Ross K A. Making $B+$-trees cache conscious in main memory. In -\it Proc. SIGMOD'00}, Dallas, Texas, USA, ACM Press, 2000, pp.475--486.

[27] Shatdal A, Kant C, Naughton J F. Cache conscious algorithms for relational query processing. In -\it Proc. VLDB'94}, Santiago de Chile, Chile, 1994, pp.510--521.

[28] Transaction processing performance council. http://www.tpc. org.

[29] Zhang Y, Chen Z, Zhou Y. Efficient execution of multiple queries on deep memory hierarchy (full version). http://www.cis.pku.edu.cn/teacher/system/zhangyan/paper /jcst-full.pdf.

[30] Intel Corporation. Intel Vtune performance analyzer. http:// www.intel.com/software/products/vtune/, 2004.
[1] Rong-Fei Cao, Xing-Ce Wang, Zhong-Ke Wu, Ming-Quan Zhou, Xin-Yu Liu. A Parallel Markov Cerebrovascular Segmentation Algorithm Based on Statistical Model [J]. , 2016, 31(2): 400-416.
[2] Amin Nikanjam and Adel Rahmani. Exploiting Bivariate Dependencies to Speedup Structure Learning in Bayesian Optimization Algorithm [J]. , 2012, 27(5): 1077-1090.
[3] Hong-Yu Liang (梁宏宇) and Jing He (何晶). Satisfiability with Index Dependency [J]. , 2012, 27(4): 668-677.
[4] Wen-Ling Wu, Wen-Tao Zhang, and Deng-Guo Feng. Impossible Differential Cryptanalysis of Reduced-Round ARIA and Camellia [J]. , 2007, 22(3): 449-456 .
[5] Xin Yao, and Yong Xu. Recent Advances in Evolutionary Computation [J]. , 2006, 21(1): 1-0.
[6] Jun He and Xin Yao. Time Complexity Analysis of an Evolutionary Algorithm for Finding Nearly Maximum Cardinality Matching [J]. , 2004, 19(4): 0-0.
[7] Luca Aceto, Jens A. Hansen, Anna Ingolfsdottir, Jacob Johnsen and John Knudsen. The Complexity of Checking Consistency of Pedigree Information and Related Problems [J]. , 2004, 19(1): 0-0.
[8] HE Simin; ZHANG Bo;. Solving SAT by Algorithm Transform of Wu s Method [J]. , 1999, 14(5): 468-480.
[9] HUANG Xiong; LI wei;. On k-Positive Satisfiability Problem [J]. , 1999, 14(4): 309-313.
[10] GU Jun; GU Qianping; DU Dingzhu;. On Optimizing the Satisfiability (SAT) Problem [J]. , 1999, 14(1): 1-17.
[11] Lu Weifeng; Zhang Yuping;. Experimental Study on Strategy of CombiningSAT Algorithms [J]. , 1998, 13(6): 608-614.
[12] Tao Xuehong; Sun Wei; Ma Shaohan;. A Practical Propositional Knowledge Base Revision Algorithm [J]. , 1997, 12(2): 154-159.
[13] Gao Qingshi;. A Unified O(log N) and Optimal Sorting Vector Algorithm [J]. , 1995, 10(5): 470-475.
Full text



[1] Ma Jun; Ma Shaohan;. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. , 1994, 9(1): 86 -91 .
[2] Ying Mingsheng;. Putting Consistent Theories Together in Institutions[J]. , 1995, 10(3): 260 -266 .
[3] Zhao Zhuxing; Min Yinghua; Li Zhongcheng;. Path Sensitization[J]. , 1997, 12(3): 271 -282 .
[4] Jin-Woo Kim, Ju-Hum Kwon, Young-Gab Kim, Chee-Yang Song, Hyun-Seok Kim, and Doo-Kwon Baik. EAFoC: Enterprise Architecture Framework Based on Commonality[J]. , 2006, 21(6): 952 -964 .
[5] Nam-Sup Park and Chong-Sun Hwang. Effective I/O Scheme Based on RTP for Multimedia Communication Systems[J]. , 2006, 21(6): 989 -996 .
[6] Dong-Xi Liu. CSchema: A Downgrading Policy Language for XML Access Control[J]. , 2007, 22(1): 44 -53 .
[7] Xiao-Min Hu, Jun Zhang, and Yun Li. Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems[J]. , 2008, 23(1): 2 -0 .
[8] Yi-Hong Wu (吴毅红), Tian Lan (兰 添), and Zhan-Yi Hu (胡占义). Degeneracy from Twisted Cubic Under Two Views[J]. , 2010, 25(5): 916 -924 .
[9] Chao-Sheng Lin (林朝圣), Chun-Hsien Lu (吕俊贤), Shang-Wei Lin (林尚威), Yean-Ru Chen (陈盈如), and Pao-Ann Hsiung (熊博安), Senior Member, ACM, IEEE. VERTAF/Multi-Core: A SysML-Based Application Framework for Multi-Core Embedded Software Development[J]. , 2011, 26(3): 448 -462 .
[10] Zhen-Hao Zhang (张栚滈), Xiao-Yin Wang (王箫音), Dong Tong (佟冬), Member, CCF, ACM, Jiang-Fang Yi (易江芳), Jun-Lin Lu (陆俊林), and Ke-Yi Wang (王克义). Active Store Window: Enabling Far Store-Load Forwarding with Scalability and Complexity-Efficiency[J]. , 2012, 27(4): 769 -780 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved