SIMD filtering on large compressed data arraysome Software

Contract: thrust-based SIMD filter library for compressed data. This document describes the interface and functionality of a CUDA/thrust-based library for same-instruction-multiple-data (SIMD) filtering on large compressed data arrays. Introduction: In columnar databases, a data table is decomposed by column, such that the set of corresponding rows across the columns represents a record from the original table. Large-scale data analytics on columnar databases requires the computation of predicates against these columns, such as the comparison of each element in a column against a literal. Further, these columns are often stored on disk in compressed form. In order to optimize analytics performance, we require a means of acting on compressed columns in such databases, without decompression and on the GPU. Such a modular library is described below: Types of compression: Frame-of-reference (FOR) compression: integer (long int) and float columns are stored in this format, which for compression relies on the common attribute that the range of data within a column is much smaller generally than the standard long int encodes. For example if data within a column range from 100 to 4000 each element should require only 12 bits. Rounding up this bit count to byte-alignment, that means 4 2-byte (16 bit) numbers (unsigned short) can be packed within each 64-bit standard long int. Meta information required to reconstruct the column include the number of bytes per record (bpr), total number of records represented, and the minimum value M seen within the column. Each element X in the original column is stored as (unsigned short) (X-100), and the reconstruction of element i from the compressed stream S is given by (long int) (S[i/bpr + i%bpr]) + M. Dictionary compression: string columns are stored in this format. The format consists of a dictionary of all unique string records found within the column, followed by a list of integer indexes into that dictionary. Further, the index list is FOR-compressed. FORInfo class: this class contains meta information about a compressed data array that represents integer or floating point data. DICTInfo class: meta information associated with a dictionary-compressed string column. API: template<T> thrust::iterator<bool> filterLiteral(void * cdata, T literal, FORInfo x, Predicate pred): returns a boolean iterator representing the predicate value “cdata[i] pred literal” for each packed element in the compressed cdata array. pred is a binary operator, and x is a FORInfo struct. template<T> thrust::iterator<bool> compareColumns(void *cdataA, void *cdataB, T aInfo, T bInfo, Predicate pred): returns a boolean iterator representing the predicate value “cdataA[i] pred cdataB[i]” for corresponding elements in the compressed source arrays. pred is a binary operator, and the template T is either FORInfo or DICTInfo. thrust::iterator<bool> AND (thrust::iterator<bool> A, thrust::iterator<bool> B): returns a boolean iterator where each element in the sequence is the result of a logical and, A[i] AND B[i] thrust::iterator<bool> OR (thrust::iterator<bool> A, thrust::iterator<bool> B): returns a boolean iterator where each element in the sequence is the result of a logical and, A[i] OR B[i] thrust::iterator<bool> NOT (thrust::iterator<bool> A): returns a boolean iterator where each element in the sequence is the result of a logical not, ~A[i] The contractor must also implement the Predicate structs as well, for ==, !=, <, <=, >, >=, and like, not_like for string types.