Geodesic
Decomposition of intersection and join operations based on the domain-interval fragmented column indices
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 1, pp. 44-56 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper presents decomposition of relational operations based on distributed column indices and domain-interval fragmentation. This decomposition admits parallel executing the resource-in-tensive relational operations without data transfers. All column index fragments are stored in main memory in compressed form to conserve space. During the parallel execution of relational operations, compressed index fragments are loaded on different processor cores. These cores uncompress fragments, perform relational operations and compress fragments of partial result, which is a set of keys. Partial results are merged in the resulting set of keys. DBMS use the resulting set of keys for building the resulting table. Described approach allows efficient parallel query processing for very large databases on modern computing cluster systems with many-core accelerators.
Keywords: very large databases, parallel query processing, column indices, decomposition of relational operations.
Mots-clés : domain-interval fragmentation 
@article{VYURV_2015_4_1_a3,
     author = {E. V. Ivanova and L. B. Sokolinsky},
     title = {Decomposition of intersection and join operations based on the domain-interval fragmented column indices},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {44--56},
     year = {2015},
     volume = {4},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2015_4_1_a3/}
}
TY  - JOUR
AU  - E. V. Ivanova
AU  - L. B. Sokolinsky
TI  - Decomposition of intersection and join operations based on the domain-interval fragmented column indices
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2015
SP  - 44
EP  - 56
VL  - 4
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURV_2015_4_1_a3/
LA  - ru
ID  - VYURV_2015_4_1_a3
ER  - 
%0 Journal Article
%A E. V. Ivanova
%A L. B. Sokolinsky
%T Decomposition of intersection and join operations based on the domain-interval fragmented column indices
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2015
%P 44-56
%V 4
%N 1
%U http://geodesic.mathdoc.fr/item/VYURV_2015_4_1_a3/
%G ru
%F VYURV_2015_4_1_a3
E. V. Ivanova; L. B. Sokolinsky. Decomposition of intersection and join operations based on the domain-interval fragmented column indices. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 1, pp. 44-56. http://geodesic.mathdoc.fr/item/VYURV_2015_4_1_a3/

[1] V. Turner, J.F. Gantz, D. Reinsel, S. Minton, The Digital Universe of Opportunities: Rich Data and the creasing Value of the Internet of Things, White paper, , International Data Corporation, 2014 (data obrascheniya: 29.01.2015) http://idcdocserv.com/1678

[2] Sokolinsky L.B., “Parallel Database Machines”, Nature, 2001, no. 8, 10–17

[3] Sokolinsky L.B., Parallel Database Systems, Publishing of the Moscow State University, M., 2013, 184 pp.

[4] L.B. Sokolinsky, “Design and Evaluation of Database Multiprocessor Architecture with High Data Availability”, Proceedings of the 12th International workshop on database and expert systems applications, IEEE Computer Society, 2001, 115–120 | DOI

[5] C.S. Pan, M.L. Zymbler, “Taming Elephants, or How to Embed Parallelism into PostgreSQL”, Database and Expert Systems Applications, v. 1, Lecture Notes in Computer Science, 8055, 2013, 153–164 | DOI

[6] Kostenetsky P.S., Sokolinsky L.B., “Simulation of Hierarchical Multiprocessor Database Systems”, Programming, 39:1 (2013), 3–22 | MR

[7] H. Plattner, A. Zeier, In-Memory Data Management: An Inflection Point for Enterprise Applications, Springer, 2011, 254 pp.

[8] D.J. Abadi, S.R. Madden, N. Hachem, Column-Stores vs. Row-Stores: How Different Are They Really?, Proceedings of the 2008 ACM SIGMOD international conference on Management of data (June 9-12, 2008, Vancouver, BC, Canada), ACM, 2008, 967–980 | DOI

[9] J. Fang, A.L. Varbanescu, H. Sips, “Sesame: A User-Transparent Optimizing Framework for Many-Core Processors”, Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid2013) (May 13-16, 2013, Delft, Netherlands), IEEE, 2013, 70–73 | DOI

[10] S. Breß, F. Beier, H. Rauhe, et al., “Efficient Co-Processor Utilization in Database Query Processing”, Information Systems, 38:8 (2013), 1084–1096 | DOI

[11] M. Scherger, “Design of an In-Memory Database Engine Using Intel Xeon Phi Coprocessors”, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA-14) (July 21-24, 2014, Las Vegas, USA), CSREA Press, 2014, 21–27

[12] Besedin K.Y., Kostenetsky P.S., “Simulation of Query Processing on Hybrid Computing Systems with Multi-core Coprocessors and Graphic Accelerators”, Software Systems: Theory and Applications, 5:1-1 (19) (2014), 91–110

[13] Ivanova E.V., Sokolinsky L.B., “Using Distributed Column Indeces for Query Execution for Very Large Databases”, Proceedings of the International Conference Parallel Computational Technologies (PCT'2014), SUSU publishing center, Chelyabinsk, 2014, 270–275

[14] Ivanova E.V., “Using Distributed Column Hash Indices for the Query for Very Large Databases”, Proceedings of the International Scientific Conference Scientific Service on the Internet: the Variety of Supercomputing Worlds, Bulletin of publishing house of the Moscow university, M., 102–104

[15] Garcia-Molina H., Ullman J., Widom J., Database Systems: The Complete Book, Prentice Hall Press, 2008, 1248 pp.