Sketches: Fast Membership Scans for Continuous Variable Predicate Workloads

We consider workloads reducible to membership checks against predicates over continuous variables, for which a scan is required. We explore trading-off storage of re-usable components to avoid repeated computation for each entry of a full scan. Our method renders effective the storage of reusable results in smaller faster memory. Upon receipt of data, a build step produces a compressed representation. Subsequently, upon receipt of a query, a compilation step constructs lookup tables which are used to determine membership, with "one-sided" error guarantees; when misses occur, the full predicate evaluation is performed. We mitigate the exponential complexity by providing a recursive decomposition generating compressed representation reusable across numerous queries, useful e.g. for quantile membership checks. We experiment with a number of knobs, distributions and selectivity rates. We develop an analytic performance model that relies on metrics measurable on a workload sample, specify analytically the conditions for which speedups are achievable, and demonstrate concordance with the empirical evaluation. The key advantages of the proposed methods are: (1) Unlocking the value of GPU massive parallelism; (2) Lossy compression which enables loading into memory a much larger number of entries as compared to using the raw data; (3) The size and speed are superior to Bloom Filters with similar miss-rates; and (4) Predictable query latency regardless of the width of the raw data or predicate computation cost or workload distribution or selectivity.