Article

Fast computation of database operations using graphics processors

Authors:

Naga K. Govindaraju,

Dinesh ManochaAuthors Info & Claims

SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data

Pages 215 - 226

https://doi.org/10.1145/1007568.1007594

Published: 13 June 2004 Publication History

Abstract

We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are essential computational components of typical database, data warehousing, and data mining applications. While graphics processing units (GPUs) have been designed for fast display of geometric primitives, we utilize the inherent pipelining and parallelism, single instruction and multiple data (SIMD) capabilities, and vector processing functionality of GPUs, for evaluating boolean predicate combinations and semi-linear queries on attributes and executing database operations efficiently. Our algorithms take into account some of the limitations of the programming model of current GPUs and perform no data rearrangements. Our algorithms have been implemented on a programmable GPU (e.g. NVIDIA's GeForce FX 5900) and applied to databases consisting of up to a million records. We have compared their performance with an optimized implementation of CPU-based algorithms. Our experiments indicate that the graphics processor available on commodity computer systems is an effective co-processor for performing database operations.

References

[1]

Pankaj Agarwal, Shankar Krishnan, Nabil Mustafa, and Suresh Venkatasubramanian. Streaming geometric optimization using graphics hardware. In 11th European Symposium on Algorithms, 2003.

[2]

A. Ailamaki, D. J. DeWitt, M. D. Hill, and M. Skounakis. Weaving relations for cache performance. In Proceedings of the Twenty-seventh International Conference on Very Large Data Bases 2001, pages 169--180, 2001.

Digital Library

[3]

A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a modern processor: Where does time go? In Proc. of VLDB, pages 266--277, 1999.

Digital Library

[4]

J. Bolz, I. Farmer, E. Grinspun, and P. Schröder. Sparse matrix solvers on the gpu: Conjugate gradients and multigrid. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH), 22(3), 2003.

Digital Library

[5]

Peter A. Boncz, Stefan Manegold, and Martin L. Kersten. Database architecture optimized for the new bottleneck: Memory access. In Proc. of VLDB, pages 54--65, 1999.

Digital Library

[6]

Census bureau databases. http://www.bls.census.gov/cps/.

[7]

Zhiyuan Chen, Nick Koudas, Flip Korn, and S. Muthukrishnan. Selectively estimation for boolean queries. In Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 216--225, 2000.

Digital Library

[8]

Ext_depth_bounds_test specification. http://www.nvidia.com/dev_content/nvopenglspecs/GL_EXT_depth_bounds_test.txt.

[9]

Michael Doggett. Programmability features of graphics hardware. ACM SIGGRAPH Course Notes # 11, 2003.

[10]

Lise Getoor, Benjamin Taskar, and Daphne Koller. Selectivity estimation using probabilistic models. In Timos Sellis and Sharad Mehrotra, editors, Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data 2001, Santa Barbara, California, United States, May 21--24, 2001, pages 461--472, 2001. ACM order number 472010.

Digital Library

[11]

N. Goodnight, C. Woolley, G. Lewin, D. Luebke, and G. Humphreys. A multigrid solver for boundary value problems using programmable graphics hardware. ACM SIGGRAPH/Eurographics Conference on Graphics Hardware, 2003.

Digital Library

[12]

N. Govindaraju, B. Lloyd, S. Yoon, A. Sud, and D. Manocha. Interactive shadow generation in complex environments. Proc. of ACM SIGGRAPH/ACM Trans. on Graphics, 22(3):501--510, 2003.

Digital Library

[13]

M. Harris, G. Coombe, G. Scheuermann, and A. Lastra. Physically-based visual simulation on graphics hardware. SIGGRAPH/Eurographics Workshop on Graphics Hardware, 2002.

Digital Library

[14]

C. A. R. Hoare. Algorithm 65: find. Commun. ACM, 4(7):321--322, 1961.

Digital Library

[15]

K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized voronoi diagrams using graphics hardw are. Proceedings of ACM SIGGRAPH, pages 277--286, 1999.

Digital Library

[16]

S. Krishnan, N. H. Mustafa, and S. Venkatasubramanian. Hardware-assisted computation of depth contours. In 13th ACM-SIAM Symposium on Discrete Algorithms, 2002.

Digital Library

[17]

J. Kruger and R. Westermann. Linear algebra operators for gpu implementation of numerical algorithms. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH), 22(3), 2003.

Digital Library

[18]

E. S. Larsen and D. K. McAllister. Fast matrix multiplies using graphics hardware. Proc. of IEEE Supercomputing, 2001.

Digital Library

[19]

M. Macedonia. The gpu enters computing's mainstream. Computer, October 2003.

Digital Library

[20]

S. Manegold, P. Boncz, and M L. Kersten. What happens during a join? Dissecting CPU and memory optimization effects. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14, 2000, Cairo, Egypt, pages 339--350, 2000.

Digital Library

[21]

Stefan Manegold, Peter A. Boncz, and Martin L. Kersten. Generic database cost models for hierarchical memory systems. In Proceedings of the Twenty-eighth International Conference on Very Large Data Bases 2002, pages 191--202, 2002.

Digital Library

[22]

D. Manocha. Interactive Geometric and Scientific Computations using Graphics Hardware. SIGGRAPH Course Notes # 11, 2003.

[23]

William R. Mark, R. Steven Glanville, Kurt Akeley, and mark J. Kilgard. Cg: A system for programming graphics hardware in a c-like language. In Proc. of ACM SIGGRAPH, 2003. http://developer.nvidia.com/page/cg_main.html.

Digital Library

[24]

Shintaro Meki and Yahiko Kambayashi. Acceleration of relational database operations on vector processors. Systems and Computers in Japan, 31(8):79--88, August 2000.

[25]

http://lava.cs.virgina.edu/bpred.html.

[26]

Nvidia geforce fx gpus: Intellisample technology. http://www.nvidia.com/object/intellisample_tb.html.

[27]

Nv_occlusion_query specification. http://www.nvidia.com/dev_content/nvopenglspecs/GL_NV_occlusion_query.txt.

[28]

Niki Pissinou. Towards and infrastructure for temporal databases---A workship report. SIGMOD Record (ACM Special Interest Group on Management of Data), 23(1):35--51, March 1994.

Digital Library

[29]

T. Purcell, I. Buck, W. Mark, and P. Hanrahan. Ray tracing on programmable graphics hardware. ACM Trans. on Graphics (Proc. of SIGGRAPH'02), 21(3):703--712, 2002.

Digital Library

[30]

T. Purcell, C. Donner, M. Cammarano, H. Jensen, and P. Hanrahan. Photon mapping on programmable graphics hardware. ACM SIGGRAPH/Eurographics Conference on Graphics Hardware, pages 41--50, 2003.

Digital Library

[31]

Jun Rao and Kenneth A. Ross. Cache conscious indexing for decision-support in main memory. In Proc. of VLDB, pages 78--89, 1999.

Digital Library

[32]

Kenneth A. Ross. Conjunctive selection conditions in main memory. In ACM, editor, Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems: PODS 2002, pages 109--120, 2002. ACM order number 475021.

Digital Library

[33]

J. Rossignac, A. Megahed, and B. D. Schneider. Interactive inspection of solids: cross-sections and interferences. In Proceedings of ACM Siggraph, pages 353--60, 1992.

Digital Library

[34]

Ambuj Shatdal, Chander Kant, and Jeffrey F. Naughton. Cache conscious algorithms for relational query processing. In 20th International Conference on Very Large Data Bases, 1994, pages 510--521, 1994.

Digital Library

[35]

Chengyu Sun, Divyakant Agrawal, and Amr El Abbadi. Hardware acceleration for spatial selections and joins. In ACM, editor, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pages 455--466, 2003.

Digital Library

[36]

C. J. Thompson, S. Hahn, and M. Oskin. Using modern graphics architectures for general-purpose computing: A framework and analysis. Proc. of IEEE/ACM International Symposium on Microarchitectures, pages 306--317, 2002.

Digital Library

[37]

Jingren Zhou and Kenneth A. Ross. Implementing database operations using simd instructions. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 145--156. ACM Press, 2002.

Digital Library

Cited By

Doraiswamy HKalagi VRamachandra KHaritsa J(2023)A Case for Graphics-Driven Query ProcessingProceedings of the VLDB Endowment10.14778/3603581.360359016:10(2499-2511)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603590
Gurumurthy BBroneske DDurand GPionteck TSaake G(2023)ADAMANT: A Query Executor with Plug-In Interfaces for Easy Co-processor Integration2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00093(1153-1166)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00093
Saied-Walker JGupta PYi RMarchal NSkubic MScott G(2023)GPU-accelerated PostgreSQL for Scalable Management and Processing of Irregular Time-Series Data using SPI2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386390(2541-2549)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386390
Show More Cited By

Recommendations

Relational query coprocessing on graphics processors

Graphics processors (GPUs) have recently emerged as powerful coprocessors for general purpose computation. Compared with commodity CPUs, GPUs have an order of magnitude higher computation power as well as memory bandwidth. Moreover, new-generation GPUs ...
Fast computation of database operations using graphics processors
SIGGRAPH '05: ACM SIGGRAPH 2005 Courses

We present new algorithms for performing fast computation of several common database operations on commodity graphics processors. Specifically, we consider operations such as conjunctive selections, aggregations, and semi-linear queries, which are ...
Mars: Accelerating MapReduce with Graphics Processors

We design and implement Mars, a MapReduce runtime system accelerated with graphics processing units (GPUs). MapReduce is a simple and flexible parallel programming paradigm originally proposed by Google, for the ease of large-scale data processing on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '04: Proceedings of the 2004 ACM SIGMOD international conference on Management of data

June 2004

988 pages

ISBN:1581138598

DOI:10.1145/1007568

Conference Chairs:
Arnd Christian König
Microsoft Research
,
Stefan Dessloch
University of Kaiserslautern, Germany
,
General Chair:
Patrick Valduriez
INRIA, France
,
Program Chair:
Gerhard Weikum
University of the Saarland

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS04

Sponsor:

SIGMOD

SIGMOD/PODS04: International Conference on Management of Data and Symposium on Principles Database and Systems

June 13 - 18, 2004

Paris, France

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

195
Total Citations
View Citations
1,591
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doraiswamy HKalagi VRamachandra KHaritsa J(2023)A Case for Graphics-Driven Query ProcessingProceedings of the VLDB Endowment10.14778/3603581.360359016:10(2499-2511)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.14778/3603581.3603590
Gurumurthy BBroneske DDurand GPionteck TSaake G(2023)ADAMANT: A Query Executor with Plug-In Interfaces for Easy Co-processor Integration2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00093(1153-1166)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00093
Saied-Walker JGupta PYi RMarchal NSkubic MScott G(2023)GPU-accelerated PostgreSQL for Scalable Management and Processing of Irregular Time-Series Data using SPI2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386390(2541-2549)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386390
Gurumurthy BBroneske DSchäler MPionteck TSaake G(2023)Novel insights on atomic synchronization for sort-based group-by on GPUsDistributed and Parallel Databases10.1007/s10619-023-07424-241:3(387-409)Online publication date: 24-Apr-2023
https://doi.org/10.1007/s10619-023-07424-2
Uchkunovna K(2022)Use of Graphics Processors in Data Compression AlgorithmsIndonesian Journal of Innovation Studies10.21070/ijins.v18i.58818Online publication date: 12-Apr-2022
https://doi.org/10.21070/ijins.v18i.588
Rosenfeld VBreß SMarkl V(2022)Query Processing on Heterogeneous CPU/GPU SystemsACM Computing Surveys10.1145/348512655:1(1-38)Online publication date: 17-Jan-2022
https://dl.acm.org/doi/10.1145/3485126
Lewis ZTu Y(2022)G-PICS: A Framework for GPU-Based Spatial Indexing and Query ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.299244034:3(1243-1257)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TKDE.2020.2992440
Glaser JAramburú FMalpica WHernández BBaker MAramburú R(2022)Scaling SQL to the Supercomputer for Interactive Analysis of Simulation DataDriving Scientific and Engineering Discoveries Through the Integration of Experiment, Big Data, and Modeling and Simulation10.1007/978-3-030-96498-6_19(327-339)Online publication date: 10-Mar-2022
https://doi.org/10.1007/978-3-030-96498-6_19
Gurumurthy BBroneske DSchaler MPionteck TSaake G(2021)An Investigation of Atomic Synchronization for Sort-Based Group-By Aggregation on GPUs2021 IEEE 37th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW53142.2021.00016(48-53)Online publication date: Apr-2021
https://doi.org/10.1109/ICDEW53142.2021.00016
Tirmazi MBen Basat RGao JYu MMaier DPottinger RDoan ATan WAlawini ANgo H(2020)Cheetah: Accelerating Database Queries with Switch PruningProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389698(2407-2422)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389698
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents