6 ms·

I would very much like to see a blog post or some other explanation of how a GPU speeds up a database query. Most traditional SQL databases are I/O-bound, mean

by ccleve 9y ago

I would very much like to see a blog post or some other explanation of how a GPU speeds up a database query. Most traditional SQL databases are I/O-bound, meaning that the cost of pulling index pages from disk into memory overwhelms everything else, and adding more CPU doesn't do much good. Even for in-memory databases the cost of pulling a page into GPU memory is likely to be high. The calculations you do are pretty simple -- you mostly traverse arrays of pointers and do intersections and accumulations. No floating point, just increment and compare integers. GPUs really shine when you can parallelize operations on blocks of data that are already in GPU memory. That's why they're great for graphics and games. I'm not seeing how they help with database queries over large volumes of data which cannot fit in GPU memory. I'd really love to read some kind of tutorial on the topic. There's likely some kind of magic here that I don't see.

imaginenore 9y ago
Your claim of I/O bound is probably only true for very large databases where indexes don't fit into tens/hundreds of GB of RAM typically available. Modern SSDs, even at the consumer level are already doing 2.5GB/s reads and 100K IOPs. I'd say most database setups are CPU limited.
dtnewman 9y ago
From their product page [1]: > MapD Core is an in-memory, column store, SQL relational database that was designed from the ground up to run on GPUs. However, memory is getting cheaper and cheaper these days. [1] https://www.mapd.com/products/core/ https://www.mapd.com/products/core/
arnon 9y ago
The GPU may help in compressing and decompressing data, encrypting and decrypting as well as sorting it (block-wise) ahead of heavy operations. Compressing and decompressing are examples of reducing I/O, and shifting it over to compute instead - and the GPU is ideal for that. Most decent columnar databases are compute bound. I/O is less of a bottleneck compared to OLTP style databases.
- deleted 9y ago
  [deleted]
Bedon292 9y ago
To my understanding it makes improvements in a few areas. The first being the tiered approach to where the data is stored. So for instance geospatial data may only store coordinates, and datetime info in the actual gpu memory. So you get massive speed ups on that. Then the next most interesting fields are in main memory, for a bit better performance. And than the rest, is on disk. I believe they also designed ways of indexing the data which perform better on GPUs with massive parallelization. And then the other major improvement is using the GPUs to render visualizations of the data you are trying to understand. That way what gets passed from the server could only be an image and not tens of millions of points of data.
fulafel 9y ago
Most SQL databases fit in RAM cheaply (and most GPUs share memory with the CPU).
- rubatuga 9y ago
  Most discrete GPUs do not share memory
  - valarauca1 9y ago
    Actually all GPUs do. PCIe is DMA (Direct Memory Access). The Vulkan API's have specific constructs for building a "shared" memory space between the native application, and its shaders on GPU. Then the driver will manage prefetching and caching from RAM to NVRAM on the GPU.. --- OFC Vulkan is only supported on newer cards. But OpenCL has had this feature for nearly a decade.
  - fulafel 9y ago
    There's a good argument that server GPU acceleration is more likely to become mainstream through integrated GPUs than through discrete GPUs.
tmostak 9y ago
These are relatively old but might be helpful: https://www.mapd.com/blog/2015/06/04/mapd/ https://www.mapd.com/blog/2015/06/04/mapd/ and https://www.mapd.com/blog/2015/06/25/mapd-massive-throughput-database-queries-with-llvm-on-gpus/ https://www.mapd.com/blog/2015/06/25/mapd-massive-throughput....
paulmd 9y ago
They don't help on large volumes of data which cannot fit into GPU memory. Obviously. PCIe is even slower than standard CPU memory, pulling non-trivial amounts of data across the PCIe bus is catastrophic for any GPU program. GPUs shine because their VRAM has enormous volumes of bandwidth (up to ~512 GB/s for high-end modern GPUs). That's an order of magnitude more than CPU memory. So basically you throw indexes and perhaps a few key columns in VRAM, but as little actual data as possible, and just return the row IDs (or ranges) of interesting data. That lets you cross-reference back into host memory, and at that point you would perhaps perform some further limitation criteria based on something that's not available in GPU memory. GPU memory isn't super-abundant, but high-end cards have up to 24 GB, and if you stack a bunch of them in a rack then you are talking about a reasonable amount of memory for most use-cases. Four cards in a box is easy, and you can put four cards in a 1U chassis if you use GP100 mezzanine cards. So now we're talking 96GB of VRAM per box or per 1U, which works out to quite a bit of index data. The other use-case would be something that's really computationally intensive to perform, but for some reason cannot be pre-computed and cached. So - for example find me all rows where "sha256(INTEGER my_table.my_val AND now() AS INTEGER) > 256". Which as you can imagine mostly trends towards crypto kinds of stuff.
- dogma1138 9y ago
  Pascal supports upto 49bit memory addressing which covers 512TB worth of addresses, AST between the GPU and system memory addresses is done in hardware which means prefetches via usage hints / branch prediction and page faults are handled by the GPU. In this case you are only bound by PCIE bandwidth (or NVLINK if you are using a supporting GPU) and performance wise it's pretty near native speeds. You can also access network and other types of storage from within the GPU since MIMO is universal these days. AMD will add similar functionality starting with VEGA. This means that with both vendors you are no longer bound by the GPU onboard memory. And if PCIE x16 isn't enough then NVLINK comes with upto 200GT/s these days and has an infiniband end point.
  - paulmd 9y ago
    The problem is "PCIe bandwidth" is really bad. PCIe 3.0x16 is only 16 GB/s, which again is less than half of you would get from any old DDR4 memory. You might as well do that on the CPU then. NVLink is fine as far as it goes... the problem is it's a two-party transaction, NVLink still has to be fed by something and that's either another GPU or the CPU or something like a SSD via DMA. With a database type program, the CPU and GPU use-cases are pointless because you could just be doing the search there and returning results directly instead of device-to-device DMA. And NVMe SSDs are usually limited to PCIe 2.0x4 which is 2 GB/s. Absolute maximum, 16 GB/s, same as any other PCIe-attached device. Remember, GPUs aren't always used on compute-bound tasks. There is a very valid use-case for I/O bound tasks where you are just using it as a super-cache. GPU database programs often (but not always) fall into that category. You are just searching indexes/target columns like crazy and throwing the resulting row IDs back over the wall to the CPU.
gopalv 9y ago
> Most traditional SQL databases are I/O-bound, meaning that the cost of pulling index pages from disk into memory overwhelms everything else, and adding more CPU doesn't do much good. A traditional database is somewhat tied to a disk for persistence, particularly if it is transactional, but this is more of a top fuel dragster with a mile to run. The first assumption is that you can fit the current working set into memory - this might not be a raw stream of data, but perhaps hundreds of data-points per cellphone tower which probably occupies around 60-100Gb. Something like Postgres would be stuck on a single core at this point mostly waiting on memory bandwidth (with associated NUMA bandwidth issues of picking 1 core). Being able to use the memory bandwidth of the GPUs, plus being forced to write code which is entirely branch independent (CPUs are good, but they still have silicon to expect branches), gives you a massive scan speedup once your data fits within the scale-up single node situation. If you're willing to shard out your data across multiple machines and never do joins across the shards, you can get distributed scans. This is never going to be your primary system of record, but just something that can hold a cube/matrix and slice/dice through it faster than a CPU based system can. If you replace the "GPU and open-source" with "custom silicon and proprietary", you might be looking at something which is very much like Netezza.
- anarazel 9y ago
  > A traditional database is somewhat tied to a disk for persistence, particularly if it is transactional, but this is more of a top fuel dragster with a mile to run. Sure, for writing that's somewhat true (in many traditional RDBMs you can relax guarantees e.g. with UNLOGGED tables in postgres). But for reads, not really. Most databases have a buffer layer in front of the disk / os. > Something like Postgres would be stuck on a single core at this point mostly waiting on memory bandwidth (with associated NUMA bandwidth issues of picking 1 core). Obviously depends on the type of query (filtering, aggregation, joins ...) you're doing, but postgres can actually parallelize things to multiple cores these days (since 9.6, a lot more to be released with v10). Unfortunately, if you're forced to use a single core, memory bandwidth is seldomly the actual bottleneck. In many cases postgres will be CPU bound elsewhere ("tuple deforming", evaluating filters / aggregation expressions), or for other types of queries memory latency will be much more important due to random access nature (think of hash-joins/aggs or nested-loop joins). We're working on that. > Being able to use the memory bandwidth of the GPUs That only really helps you if a significant portion of the working set fits onto GPUs. Which'll usually not if we're talking 60-100GB of main memory resident data. If you're reading sequentially through all that data you'll be bound by the main memory latency (including those NUMA issues etc you mentioned).
goldenshale 9y ago
The benefits would come from running query kernels in parallel on thousands of GPU cores simultaneously, which necessarily only have access to memory on the card. Of course pre-computation is always preferable, but that's not feasible for data exploration and many types of queries. My guess is they start with databases or i dexes that can sit entirely in GPU RAM, and then later versions will support streaming this data from main memory and disk. Some types of queries that would likely benefit from this strategy would be reductions (sum, avg, count), filtering (find items matching a particular value or predicate), and geospatial queries against geometry. These all require iterating over all or most of the data, and so doing that massively parallel will result in major speedups. To support larger datasets you can always shard across GPUs and machines. This is how the google index is structured, for example. I bet real-time metrics will be a good application.

by ccleve 9y ago

imaginenore 9y ago

Your claim of I/O bound is probably only true for very large databases where indexes don't fit into tens/hundreds of GB of RAM typically available. Modern SSDs, even at the consumer level are already doing 2.5GB/s reads and 100K IOPs. I'd say most database setups are CPU limited.

dtnewman 9y ago

From their product page [1]: > MapD Core is an in-memory, column store, SQL relational database that was designed from the ground up to run on GPUs. However, memory is getting cheaper and cheaper these days. [1] https://www.mapd.com/products/core/ https://www.mapd.com/products/core/

arnon 9y ago

The GPU may help in compressing and decompressing data, encrypting and decrypting as well as sorting it (block-wise) ahead of heavy operations. Compressing and decompressing are examples of reducing I/O, and shifting it over to compute instead - and the GPU is ideal for that. Most decent columnar databases are compute bound. I/O is less of a bottleneck compared to OLTP style databases.

deleted 9y ago
[deleted]

Bedon292 9y ago

To my understanding it makes improvements in a few areas. The first being the tiered approach to where the data is stored. So for instance geospatial data may only store coordinates, and datetime info in the actual gpu memory. So you get massive speed ups on that. Then the next most interesting fields are in main memory, for a bit better performance. And than the rest, is on disk. I believe they also designed ways of indexing the data which perform better on GPUs with massive parallelization. And then the other major improvement is using the GPUs to render visualizations of the data you are trying to understand. That way what gets passed from the server could only be an image and not tens of millions of points of data.

fulafel 9y ago

Most SQL databases fit in RAM cheaply (and most GPUs share memory with the CPU).

rubatuga 9y ago
Most discrete GPUs do not share memory
- valarauca1 9y ago
  Actually all GPUs do. PCIe is DMA (Direct Memory Access). The Vulkan API's have specific constructs for building a "shared" memory space between the native application, and its shaders on GPU. Then the driver will manage prefetching and caching from RAM to NVRAM on the GPU.. --- OFC Vulkan is only supported on newer cards. But OpenCL has had this feature for nearly a decade.
- fulafel 9y ago
  There's a good argument that server GPU acceleration is more likely to become mainstream through integrated GPUs than through discrete GPUs.

tmostak 9y ago

These are relatively old but might be helpful: https://www.mapd.com/blog/2015/06/04/mapd/ https://www.mapd.com/blog/2015/06/04/mapd/ and https://www.mapd.com/blog/2015/06/25/mapd-massive-throughput-database-queries-with-llvm-on-gpus/ https://www.mapd.com/blog/2015/06/25/mapd-massive-throughput....

paulmd 9y ago

They don't help on large volumes of data which cannot fit into GPU memory. Obviously. PCIe is even slower than standard CPU memory, pulling non-trivial amounts of data across the PCIe bus is catastrophic for any GPU program. GPUs shine because their VRAM has enormous volumes of bandwidth (up to ~512 GB/s for high-end modern GPUs). That's an order of magnitude more than CPU memory. So basically you throw indexes and perhaps a few key columns in VRAM, but as little actual data as possible, and just return the row IDs (or ranges) of interesting data. That lets you cross-reference back into host memory, and at that point you would perhaps perform some further limitation criteria based on something that's not available in GPU memory. GPU memory isn't super-abundant, but high-end cards have up to 24 GB, and if you stack a bunch of them in a rack then you are talking about a reasonable amount of memory for most use-cases. Four cards in a box is easy, and you can put four cards in a 1U chassis if you use GP100 mezzanine cards. So now we're talking 96GB of VRAM per box or per 1U, which works out to quite a bit of index data. The other use-case would be something that's really computationally intensive to perform, but for some reason cannot be pre-computed and cached. So - for example find me all rows where "sha256(INTEGER my_table.my_val AND now() AS INTEGER) > 256". Which as you can imagine mostly trends towards crypto kinds of stuff.

dogma1138 9y ago
Pascal supports upto 49bit memory addressing which covers 512TB worth of addresses, AST between the GPU and system memory addresses is done in hardware which means prefetches via usage hints / branch prediction and page faults are handled by the GPU. In this case you are only bound by PCIE bandwidth (or NVLINK if you are using a supporting GPU) and performance wise it's pretty near native speeds. You can also access network and other types of storage from within the GPU since MIMO is universal these days. AMD will add similar functionality starting with VEGA. This means that with both vendors you are no longer bound by the GPU onboard memory. And if PCIE x16 isn't enough then NVLINK comes with upto 200GT/s these days and has an infiniband end point.
- paulmd 9y ago
  The problem is "PCIe bandwidth" is really bad. PCIe 3.0x16 is only 16 GB/s, which again is less than half of you would get from any old DDR4 memory. You might as well do that on the CPU then. NVLink is fine as far as it goes... the problem is it's a two-party transaction, NVLink still has to be fed by something and that's either another GPU or the CPU or something like a SSD via DMA. With a database type program, the CPU and GPU use-cases are pointless because you could just be doing the search there and returning results directly instead of device-to-device DMA. And NVMe SSDs are usually limited to PCIe 2.0x4 which is 2 GB/s. Absolute maximum, 16 GB/s, same as any other PCIe-attached device. Remember, GPUs aren't always used on compute-bound tasks. There is a very valid use-case for I/O bound tasks where you are just using it as a super-cache. GPU database programs often (but not always) fall into that category. You are just searching indexes/target columns like crazy and throwing the resulting row IDs back over the wall to the CPU.

gopalv 9y ago

> Most traditional SQL databases are I/O-bound, meaning that the cost of pulling index pages from disk into memory overwhelms everything else, and adding more CPU doesn't do much good. A traditional database is somewhat tied to a disk for persistence, particularly if it is transactional, but this is more of a top fuel dragster with a mile to run. The first assumption is that you can fit the current working set into memory - this might not be a raw stream of data, but perhaps hundreds of data-points per cellphone tower which probably occupies around 60-100Gb. Something like Postgres would be stuck on a single core at this point mostly waiting on memory bandwidth (with associated NUMA bandwidth issues of picking 1 core). Being able to use the memory bandwidth of the GPUs, plus being forced to write code which is entirely branch independent (CPUs are good, but they still have silicon to expect branches), gives you a massive scan speedup once your data fits within the scale-up single node situation. If you're willing to shard out your data across multiple machines and never do joins across the shards, you can get distributed scans. This is never going to be your primary system of record, but just something that can hold a cube/matrix and slice/dice through it faster than a CPU based system can. If you replace the "GPU and open-source" with "custom silicon and proprietary", you might be looking at something which is very much like Netezza.

anarazel 9y ago
> A traditional database is somewhat tied to a disk for persistence, particularly if it is transactional, but this is more of a top fuel dragster with a mile to run. Sure, for writing that's somewhat true (in many traditional RDBMs you can relax guarantees e.g. with UNLOGGED tables in postgres). But for reads, not really. Most databases have a buffer layer in front of the disk / os. > Something like Postgres would be stuck on a single core at this point mostly waiting on memory bandwidth (with associated NUMA bandwidth issues of picking 1 core). Obviously depends on the type of query (filtering, aggregation, joins ...) you're doing, but postgres can actually parallelize things to multiple cores these days (since 9.6, a lot more to be released with v10). Unfortunately, if you're forced to use a single core, memory bandwidth is seldomly the actual bottleneck. In many cases postgres will be CPU bound elsewhere ("tuple deforming", evaluating filters / aggregation expressions), or for other types of queries memory latency will be much more important due to random access nature (think of hash-joins/aggs or nested-loop joins). We're working on that. > Being able to use the memory bandwidth of the GPUs That only really helps you if a significant portion of the working set fits onto GPUs. Which'll usually not if we're talking 60-100GB of main memory resident data. If you're reading sequentially through all that data you'll be bound by the main memory latency (including those NUMA issues etc you mentioned).

goldenshale 9y ago

The benefits would come from running query kernels in parallel on thousands of GPU cores simultaneously, which necessarily only have access to memory on the card. Of course pre-computation is always preferable, but that's not feasible for data exploration and many types of queries. My guess is they start with databases or i dexes that can sit entirely in GPU RAM, and then later versions will support streaming this data from main memory and disk. Some types of queries that would likely benefit from this strategy would be reductions (sum, avg, count), filtering (find items matching a particular value or predicate), and geospatial queries against geometry. These all require iterating over all or most of the data, and so doing that massively parallel will result in major speedups. To support larger datasets you can always shard across GPUs and machines. This is how the google index is structured, for example. I bet real-time metrics will be a good application.