The multi-core trend in CPUs and general purpose graphics processing
units (GPUs) offers new opportunities for the database community. The
increase of cores at exponential rates is likely to affect virtually
every server and client in the coming decade, and presents database
management systems with a huge, compelling disruption that will
radically change how processing is done. This paper presents a new
parallel indexing data structure for answering queries that takes full
advantage of the increasing thread-level parallelism emerging in
multi-core architectures. In our approach, our Data Parallel Bin-based
Index Strategy (DP-BIS) first bins the base data, and then partitions
and stores the values in each bin as a separate, bin-based data
cluster. In answering a query, the procedures for examining the bin
numbers and the bin-based data clusters offer the maximum possible level
of concurrency; each record is evaluated by a single thread and all
threads are processed simultaneously in parallel.
We implement and demonstrate the effectiveness of DP-BIS on two
multicore architectures: a multi-core CPU and a GPU. The concurrency
afforded by DP-BIS allows us to fully utilize the thread-level
parallelism provided by each architecture -- for example, our GPU-based
DP-BIS implementation simultaneously evaluates over 12,000 records with
an equivalent number of concurrently executing threads. In comparing
DP-BIS's performance across these architectures, we show that the
GPU-based DP-BIS implementation requires significantly less computation
time to answer a query than the CPU-based implementation.We also
demonstrate in our analysis that DP-BIS provides better overall
performance than the commonly utilized CPU and GPU-based projection
index. Finally, due to data encoding, we show that DP-BIS accesses
significantly smaller amounts of data than index strategies that operate
solely on a column's base data; this smaller data footprint is critical
for parallel processors that possess limited memory resources
(e.g. GPUs).