BitWeaving is an efficient scan primitive that is being developed in the Computer Sciences Department at the University of Wisconsin.
The BitWeaving project focuses on running scans in a main memory data processing system at "bare metal" speed. Essentially, this means that the system must aim to process data at or near the speed of the processor. Scans are common in main memory data processing environments, and with the state-of-the-art techniques it still takes many cycles per input tuple to apply simple predicates on a single column of a table. BitWeaving is proposed to exploit the parallelism available at the bit level in modern processors. BitWeaving operates on multiple bits of data in a single cycle, processing bits from different columns in each cycle. Thus, bits from a batch of tuples are processed in each cycle, allowing BitWeaving to drop the cycles per column to below one in some case. BitWeaving comes in two flavors: BitWeaving/V which looks like a columnar organization but at the bit level, and BitWeaving/H which packs bits horizontally.
See Jignesh's blog for a more detailed introduction on BitWeaving.
People
Publications
-
WideTable: An Accelerator for Analytical Data Processing, Yinan Li and Jignesh M. Patel, VLDB 2014.
-
BitWeaving: Fast Scans for Main Memory Data Processing, Yinan Li and Jignesh M. Patel, SIGMOD 2013.
Support
Quickstep is supported by the National Science Foundation under grants IIS-0963993 and IIS-1250886, and by Google.
