PaperlayerView exact revision on arXiv

Source-linked AI summary

Direct-Operable SIMD Bit-Slicing: A Framework for Memory-Efficient Predicate Evaluation

Arunkumar Mathiyazhagan

arXiv:2608.26368v1cs.PF

TL;DR

Data-intensive Java systems face memory overhead and a gap between compressed storage and direct predicate evaluation. The paper introduces JVM-native SIMD evaluation over bit-sliced compressed data without decompression, reporting broad speedups and memory reductions across workloads and data types. Its scope excludes variable-length data and becomes less advantageous for very high-cardinality strings.

  • Problem

    Java object overhead and decompress-then-compute execution limit memory efficiency for data-intensive analytical predicate evaluation.

  • Method

    The framework stores data in bit-sliced compressed form and evaluates predicates directly with Project Panama SIMD operations within the JVM.

  • Results

    2.4–10.8× speedup over scalar scans across five filter-heavy TPCDS-modeled query patterns at 50M rows, with 1.5–43× speedups across extended types.

  • Takeaways & Limitations

    Bit-plane representation can combine compact storage with direct SIMD predicate evaluation for JVM-based analytical query processing.

  • Takeaways & Limitations

    Very high-cardinality variable-length strings reduce compression and throughput advantages, while variable-length arrays, maps, and nested structs are out of scope.

Abstract

from arXiv · show

Traditional Java object models introduce significant memory overhead due to object headers and internal padding, often leading to performance bottlenecks in data-intensive distributed systems. This paper presents a novel framework that utilizes the Project Panama Vector API to perform predicate evaluation directly over bit-sliced, compressed data streams. By transposing standard row-oriented data into parallel bit-planes, we demonstrate a mechanism to evaluate complex filters using SIMD (Single Instruction, Multiple Data) instructions without requiring prior decompression. The framework supports integers, longs (timestamps), doubles (via IEEE 754 order-preserving transformation), and strings (via dictionary encoding). Our benchmarks indicate a reduction in memory footprint by up to 8x while maintaining or exceeding the throughput of uncompressed standard Java collections. End-to-end evaluation on TPCDS-modeled data at 50M rows demonstrates 2.4-10.8x speedup over scalar scans across five representative filter-heavy query patterns, with extended type benchmarks on TPCDS columns showing 1.5-43x speedups for timestamps, decimals, and dictionary-encoded strings.

1 Introduction

The paper targets memory pressure in Java analytics by evaluating predicates directly on compressed bit-sliced data with SIMD, avoiding decompression. It reports substantial memory reductions and speedups across types and TPCDS-modeled workloads.

  • Motivation: Memory bandwidth and latency, rather than computation, dominate analytical scans over billions of rows.Main memory latency improved roughly 7% annually versus over 50% annual compute-throughput growth.
  • Motivation: Java object overhead compounds in boxed integer collections, increasing heap use, garbage-collection pressure, and cache evictions.An Integer carrying 4 bytes of payload consumes 16 bytes, while 1 million boxed integers occupy about 20 MB versus 4 MB for int[].
  • Approach: The Zero-Decompression model evaluates predicates directly over compressed bit-sliced representations using Project Panama SIMD instructions within the JVM.Bit-planes map to SIMD registers, reducing predicate evaluation to bitwise AND, OR, and NOT operations.
  • Approach: The framework defines SIMD bit-plane predicates for equality, ranges, comparisons, IN-list, and BETWEEN operations.These predicates are expressed as compositions of SIMD bitwise operations over bit-planes.
  • Results: Up to 8× memory reduction is achieved for low-cardinality integer columns while maintaining or exceeding uncompressed-baseline scan throughput.The framework also extends to timestamps, doubles, and dictionary-encoded strings, with reported speedups of 1.8–43× across types.
  • Results: TPCDS-modeled benchmarks at 50M rows demonstrate 2.4–10.8× speedup over scalar scans across five filter-heavy query patterns.The evaluation combines JMH microbenchmarks with end-to-end validation.

2 Background and Related Work

The paper extends bit-slicing from an indexing technique to a primary compressed representation that supports direct SIMD predicate evaluation. It positions this JVM-native approach against decompression-based formats and native engines while relying on Vector API mask composition.

  • 2.1 Bit-Sliced Indexes: Bit-slicing transposes an N-value, b-bit integer column into b bitmaps, each representing one bit position across all values.This converts row-major storage into a column-major bit-plane representation.
  • 2.1 Bit-Sliced Indexes: Earlier bit-sliced indexes accelerated aggregate queries and range scans by 2–5× over traditional B-tree indexes on historical datasets.Their original use scanned relevant planes from the most significant bit and could short-circuit when results were determined.
  • 2.1 Bit-Sliced Indexes: This work stores values exclusively in bit-sliced form and evaluates predicates without materializing conventional integers.The extension changes bit-slicing from an indexing structure into a primary data representation.
  • 2.2 SIMD and Compression: Prior SIMD compression systems accelerate decoding or compute after decompression, whereas this framework executes predicates directly on compressed bit-planes.This distinction is stated relative to PFOR-style compression, SIMD decoding, and related columnar compression work.
  • 2.3 Columnar Formats and In-Memory Processing: Parquet and ORC reverse their encodings at read time, while Arrow Java exposes materialized values for predicate evaluation.These approaches address storage or zero-copy transport but do not preserve the paper’s direct compressed-form evaluation model.
  • 2.4 Native Execution Engines: Photon and Velox provide native SIMD execution but require leaving the JVM ecosystem, unlike this JVM-native framework.The paper identifies migration costs for Java codebases and JVM-oriented operational tooling.
  • 2.5 Positioning of Our Work: Project Panama’s Vector API supplies hardware-mapped vector types and composable VectorMask operations that align with bit-plane predicates.The API supports species corresponding to 128-, 256-, and 512-bit SIMD widths, with scalar fallback on unsupported hardware.
  • 2.5 Positioning of Our Work: The framework combines zero-decompression evaluation, SIMD acceleration, JVM-native execution, and off-heap memory management.The paper presents this combination as its distinguishing position among prior approaches.

3 Methodology

The methodology transposes values into contiguous bit-planes whose adaptive bit-width reduces memory use while enabling SIMD predicate evaluation without decompression.

  • Adaptive bit-width encoding: The encoder selects bit-width b per block from the maximum value and writes aligned bit-planes with a header storing b and block size N.Per-block adaptation lets narrower value ranges use fewer bits, while padding aligns planes to the SIMD register width.
  • Bit-sliced representation: Bit-slicing transposes each value block into b bit-planes, where each plane stores one bit position across all N values.The j-th plane contains Pj[i] = (xi ≫ j) ∧ 1 for each value position i.
  • Adaptive bit-width encoding: 8× compression results when b = 4 for values 0–15, compared with the 32-bit representation.The general compression ratio is 32/b, yielding 4× at b = 8 and 2× at b = 16.
  • SIMD execution model: A predicate over a block requires b · (N/W) SIMD operations, and is fewer operations than scalar scanning when b < W.With W ≥128 and b ≤32, the stated condition holds for the supported integer widths.
  • SIMD execution model: The bit-sliced representation occupies b/32 of uncompressed data, allowing more working data to fit in cache; a b = 4 block occupies 512 bytes.The cited 512-byte block fits within a typical 32 KB L1 data cache.
  • NULL handling: NULL handling uses a separate validity plane, intersects each predicate mask with it, and adds one SIMD AND per block; NULL-free columns omit the plane.NULL data bits may be stored as zero because the validity mask removes them from results.

4 Implementation

The implementation uses Java’s Vector API and off-heap MemorySegment allocations, and its architecture is organized around encoding, predicate evaluation, and memory management.

  • Implementation architecture: The framework is implemented in Java 21 using the jdk.incubator.vector module and off-heap MemorySegment allocations.The stated implementation uses Project Panama Vector API facilities and keeps data outside the Java heap.
  • Implementation architecture: The implementation consists of three layers: encoding, predicate evaluation, and memory management.Figure 2 presents the framework’s end-to-end architecture.

4.1 Encoding Layer

The encoding layer converts contiguous integer arrays into adaptive, aligned bit-sliced blocks stored off-heap for direct SIMD processing.

  • Encoding layer: The encoder accepts a contiguous integer array and produces a bit-sliced block by transposing values into sequentially written bit-planes.Shift and mask operations perform the transposition into an output MemorySegment.
  • Pipeline: The architecture encodes column data into off-heap bit-sliced blocks, then evaluates predicates directly on planes to produce a downstream selection vector without decompression.This pipeline is summarized in Figure 2’s framework architecture.
  • Encoding layer: The encoder computes block bit-width from the maximum value and allocates off-heap storage for the resulting planes.The implementation uses a preferred SIMD species and returns a BitSlicedBlock containing the off-heap planes.
  • Encoding layer: Listing 1’s encoder iterates over bit positions and words, setting each plane’s values at calculated MemorySegment offsets.The implementation writes each plane sequentially using native integer layout operations.
  • Encoding layer: The resulting BitSlicedBlock records the input length, bit-width, and words per plane.These parameters are returned alongside the allocated segment.

4.2 Predicate Evaluation Layer

The predicate layer evaluates comparisons and compound filters directly on bit-planes using SIMD bitwise operations, returning composable bitmask results.

  • Comparison predicates: Bit-sliced comparisons reduce to SIMD AND, OR, and NOT operations over bit-planes processed from most significant to least significant bits.Greater-than evaluation maintains masks for values already greater and values still equal at examined bits.
  • Comparison predicates: Equality retains candidates only when every bit-plane matches the corresponding bit of the constant.The implementation starts with all result bits set and removes mismatches plane by plane.
  • Range and membership predicates: The BETWEEN predicate evaluates lower- and upper-bound masks and combines them with a SIMD AND.It implements lo ≤ x ≤ hi for all values in a block.
  • Range and membership predicates: An IN-list is computed as the OR of equality masks for its constants, with a Bloom-filter pre-check able to skip blocks for large lists.The text describes the OR construction as efficient for small k.
  • Compound predicates: All predicates return same-shaped int[] bitmasks, allowing compound predicates to combine per-column results with SIMD Boolean operations.A query combining age > 25 with salary BETWEEN 50000 and 100000 uses a final AND.

4.3 Memory Management

The framework stores bit-sliced data off-heap, separating data buffers from JVM heap management while supporting cache-friendly access and exact memory accounting.

  • Bit-sliced data resides off-heap in MemorySegment allocations managed by automatic or confined arenas.The design supports garbage-collected arenas and deterministic deallocation.
  • The garbage collector does not scan data buffers; only small wrapper objects remain on-heap.These wrappers contain block metadata and arena references.
  • Contiguous bit-plane storage maximizes spatial locality for sequential SIMD loads.
  • MemorySegment.byteSize() provides exact usage measurements for enforcing memory limits without JVM heap heuristics.

4.4 Thread Safety

Immutable bit-sliced blocks support concurrent predicate evaluation without synchronization, while parallel scans merge independent thread results according to Boolean composition.

  • Immutable encoded blocks can be read concurrently by multiple threads without synchronization.The MemorySegment is written once and then accessed read-only.
  • Parallel scans partition blocks across threads and merge independent result masks with OR for disjunctions or AND for conjunctions.

5 Experimental Evaluation

The evaluation measures memory, throughput, garbage collection, cache behavior, and predicate types across controlled datasets and baselines. Results show strong compression and throughput advantages, especially for narrow columns and larger scans, with end-to-end gains across representative TPCDS patterns.

  • Experimental design: The evaluation covers memory footprint, predicate throughput, garbage collection, CPU cache behavior, and predicate type comparison.Measurements use JMH with warmup and measurement iterations, reporting means and 95% confidence intervals.
  • Datasets and baselines: D1 is the best case with narrow bit-width and high compression, D3 is the worst case with wide bit-width and minimal compression, and D2 is intermediate.The datasets derive from TPC-H scale factor 10 column distributions.
  • Datasets and baselines: The comparison includes int[], ArrayList<Integer>, Arrow Java, and Parquet-MR, with all baselines evaluating median-threshold predicates selecting approximately 50% of rows.
  • Memory footprint: 5.3× compression over int[] is achieved for D1, while D3 still provides 1.2× compression because six of 32 bit-planes are eliminated.The compression ratio follows 32/b.
  • Predicate throughput: 10.7× faster than int[] is achieved on D1 for greaterThan, decreasing to 4.3× on D2 and 3.4× on D3 as bit-width increases.The comparison uses scalar int[] scans and also reports larger gains over ArrayList<Integer>.
  • GC impact: 10.9× faster than int[] is achieved for a full 10M-element D1 scan, while bit-sliced data contributes zero GC pressure and result masks account for 2.8 MB/op.
  • Cache behavior: 11.4× faster throughput on D1 corresponds to 0.75 B/element versus 4 B/element, with the compact dataset fitting within L2 cache.The bit-sliced 1M-element dataset occupies approximately 750 KB versus 4 MB for int[].
  • Predicate types: Equality is fastest, greaterThan is slightly slower, between is roughly half as fast, and large IN-lists may favor hashing materialized values.

5.10 Experiment 7: Extended Type Support

The framework extends bit-sliced SIMD evaluation to timestamps, floating-point values, and strings through type-specific transformations into unsigned integer representations. Results show memory and range-predicate benefits, with especially large gains for dictionary-encoded strings.

  • Extended type design: Additional types are transformed into unsigned integer representations and evaluated with the same SIMD bit-plane machinery.The supported extensions are 64-bit timestamps, floating-point decimals, and strings.
  • Long timestamp support: Per-block timestamp biasing reduces a one-day window to approximately 17 bits versus approximately 41 bits for raw epoch milliseconds.The support targets timestamp columns with narrow per-partition ranges.
  • Long timestamp support: 1.5–2.1× speedup is achieved for bit-sliced long range comparisons, while DL2 uses 2.13 B/element versus 8 B/element for long[].Equality is faster with scalar long comparisons because long equality is a single CPU instruction.
  • Floating-point support: IEEE 754 sign-magnitude values are transformed so double ordering is preserved by unsigned-long comparisons.
  • Floating-point support: Mixed-sign double columns use unbiased full 64-bit encoding, while all-positive columns use per-block biasing for better compression.The strategy avoids constant overflow at the sign boundary.
  • Floating-point support: 9.4× speedup is achieved for DD1 ss_net_profit BETWEEN $1000 AND $5000, while single greaterThan reaches only 1.0–1.1×.The range predicate benefits from two SIMD greaterThan passes, whereas full-width encoding limits single comparisons.
  • String support: Dictionary encoding maps strings to compact integer codes, using b=5 for i_category and b=6 for s_state.
  • String support: 28–43× speedups are achieved for string predicates, while DS1 uses 0.63 B/element versus approximately 40 B/element for String[] storage.Bit-sliced equality operates on integer codes instead of String.equals() comparisons.

6 Discussion

The framework offers memory-efficient, SIMD-native predicate evaluation within the JVM, but its benefits depend on data types, bit-width, workload shape, and deployment conditions. The discussion also identifies integration boundaries, operational costs, and baseline limitations.

  • Limitations: High-cardinality strings reduce compression and throughput advantages because dictionary codes require wide bit-widths, typically b ≥20.Floating-point predicates also incur a one-time IEEE 754 ordering transformation during encoding.
  • Limitations: Variable-length data falls outside the scope of bit-plane transposition, while arbitrary-precision decimals may lose precision after fixed-point scaling.These types require structural encoding or preprocessing beyond the fixed-width SIMD approach.
  • When Not to Use Bit-Slicing: Columns with effective bit-width near 32 approach 1× compression, while random point lookups favor hash indexes or B-trees over full scans.Bit-plane transposition may not justify its encoding overhead in these cases.
  • When Not to Use Bit-Slicing: Bit-slicing is most effective for low-to-medium-cardinality columns, scan-heavy selective workloads, and environments where memory or GC overhead matters.The paper gives b ≤16 as a practical guideline.
  • Deployment and Integration: The framework operates independently within each distributed worker, preserving existing parallelism and shuffle semantics while replacing per-node column representations.Integration targets include Parquet readers and Spark or Trino column-vector interfaces.
  • Multi-Column Predicate Composition: Compound predicates combine same-shape bitmasks with SIMD AND/OR passes, and their merge cost O(N/W) is negligible relative to per-column scan costs.TPCDS Q5 reports 5.4× speedup for a conjunctive predicate on columns with b=7 and b=15.
  • Operational Considerations: Cold starts incur approximately 200–500 ms of JIT compilation cost, which is amortized across subsequent queries.Preferred SIMD species selection occurs at class load time, avoiding per-invocation dispatch overhead.
  • Evaluation Scope: The baselines use simple scalar implementations, so comparisons with production systems using native predicate pushdown or hand-tuned C++ SIMD remain incomplete.The authors identify Arrow, Parquet, Photon, and Velox as stronger comparison points.

7 Conclusion

The framework combines compact bit-sliced representation with direct SIMD predicate evaluation inside the JVM, reducing memory use while accelerating scans across integer and extended data types. End-to-end and type-specific evaluations report substantial speedups, though broader integrations and larger-scale validation remain future work.

  • The framework performs predicate evaluation directly over bit-sliced compressed data within the JVM, without decompression.Bit-plane transposition serves as both a compact primary representation and a SIMD-operable execution format.
  • Up to 5.3× memory reduction over int[] and up to 32× over ArrayList<Integer> were measured for low-cardinality columns.The reported reductions target primitive arrays and boxed Java collections, respectively.
  • 10.7× higher predicate throughput than int[] scans on narrow columns and 3.4× on wide columns were reported, with 11.4× gains attributed to cache utilization.The narrow-column result uses b=6, while the wide-column result uses b=26.
  • At 50M rows, five TPCDS filter-heavy query patterns achieved 2.4–10.8× speedup over scalar scans, including compound multi-column predicates.The evaluation positions the framework as a predicate pushdown strategy for distributed query engines.
  • Type-specific benchmarks reported 1.5–2.1× speedup for timestamps, 9.4× for floating-point ranges, and 28–43× for dictionary-encoded strings.String predicates also achieved memory savings of up to 64× through compact integer-code operations.
  • The results were measured on ARM64 NEON 128-bit hardware, while Parquet integration, broader competitive comparisons, roofline analysis, and 1B+ row multi-node evaluation remain future work.The paper states that wider AVX-512 SIMD widths are expected to amplify the advantages.
Loading 2608.26368v1…