[Feature] Lazy deserializer for complex type data
- Dominant language
- C++
- Stars
- 177
- Forks
- 107
- Avg merge
- 3d 10h
- Merged PRs (30d)
- 49
Description
### Feature Category
Performance Optimization
### Problem / Use Case
In ML workloads, complex types are commonly used to store embeddings and tensors. These data are typically not involved in computation, but are carried throughout the entire execution pipeline. During operations such as shuffle, spill, or join, they are often serialized or copied. Due to the structural complexity of complex types, their serialization and copy operations are relatively expensive.
If these unnecessary overheads can be avoided, the overall job execution time can be significantly improved. Based on this observation, a Lazy Deserialization optimization can be applied to complex type data.
### Proposed Solution
For sql like this
```SQL
select t1.a, b, c
from t1 join t2
on t1.a=t1.b
```
The diagram contrasts Standard Execution with Lazy Deserialization for handling complex types (e.g., arrays/tensors).
* Left (Standard): The engine eagerly deserializes and re-serializes complex columns (b, c) at every stage (Shuffle, Join), even though they are not used in the computation logic.
* Right (Optimized): The engine identifies unused columns and treats them as "Lazy" binary data. Deserialization is strictly deferred until the final TableSink, bypassing expensive overhead during intermediate steps.
**Key Improvements**
1. Eliminates Redundant Computation: Skips costly serialization/deserialization (SerDe) for data that serves only as payload.
2. Optimizes Resource Usage: Reduces CPU load and memory copying by transmitting raw bytes during Shuffle and Join phases.
3. Accelerates ML Workloads: Significantly lowers latency for jobs carrying heavy embedding or tensor data.
### Exsisting Row Format
#### Spark UnsafeRow
Spark's UnsafeRow is designed for CPU-efficient in-memory computation. Its crucial feature is the separation of fixed-width data pointers from variable-width payload data, allowing O(1) random access to any field.
Scenario Data: Schema: { id: Int, name: String, scores: Array } Value: { id: 1, name: "abc", scores: [10, 20] }
```
+-----------------------------------------------------------------------------------------------+
| Spark UnsafeRow Memory Layout |
+-----------------------------------------------------------------------------------------------+
| [Null Bitset Header] | [Fixed-Length Region] | [Variable-Length Region] |
| (Tracks null values) | (8 bytes per field, contiguously) | (Heap / Payload Data) |
+----------------------+-----------------------------------------+------------------------------+
| | | |
| | Field 0 (id: Int) | |
| [000...] | Value: 1 (padded to 8 bytes) | |
| | --------------------------------------- | |
| | Field 1 (name: String) | |
| | [Pointer: Offset=32, Length=3] | ---> Points to "abc" bytes |
| | --------------------------------------- | |
| | Field 2 (scores: Array) | |
| | [Pointer: Offset=40, Length=16] | ---> Points to array bytes |
| | | |
+----------------------+-----------------------------------------+------------------------------+
| | | Memory at Offset 32: |
| | | | a | b | c | |
| | | |
| | | Memory at Offset 40: |
| | | | Header | 10 | 20 | |
+----------------------+-----------------------------------------+------------------------------+
```
#### CompactRow
The Compact Row format is optimized for storage efficiency and network transmission. Unlike UnsafeRow, which prioritizes random access via offsets, Compact Row eliminates metadata overhead (offsets and padding) to minimize the data footprint.
```
+-----------------------------------------------------------------------------------+
| Compact Row Layout |
+-----------------------------------------------------------------------------------+
| [NullBits] | [FixType0] | [FixType1] | [Var Size] [Var Data] | [Var Size] [Var Data] ... |
+------------+------------+------------+-----------------------+---------------------------+
| | | | | |
| Bitset | Value | Value | Length Payload | Length Payload |
| | | | (int) (bytes) | (int) (bytes) |
+------------+------------+------------+-----------------------+---------------------------+
| <--- Fixed Region ---> | <--------------- Variable Region (Packed) ------------------> |
+-----------------------------------------------------------------------------------+
```
#### Apache Avro
Avro is designed for efficient storage and network transmission. It is highly compact because it does not store field names or types with the data (relying on an external schema writer/reader). It heavily uses variable-length encoding (like ZigZag for integers), meaning data boundaries are not fixed.
Scenario Data: Schema: { id: Int, name: String, scores: Array } Value: { id: 1, name: "abc", scores: [10, 20] }
```
+-----------------------------------------------------------------------------------+
| Apache Avro Continuous Binary Stream |
+-----------------------------------------------------------------------------------+
| [Field 0: id] | [Field 1: name] | [Field 2: scores] |
+-----------------+-------------------------+---------------------------------------+
| | | |
| (ZigZag Int) | (Length Prefix)+(Bytes) | (Block Count)+(Values...)+(End Block) |
| | | |
| Byte: [0x02] | Bytes: [0x06] [a,b,c] | Bytes: [0x04] [0x14, 0x28] [0x00] |
| (Value=1) | (Len=3) ("abc") | (Count=2) (10, 20) (End) |
| | | |
+-----------------+-------------------------+---------------------------------------+
| <--- No clear boundaries. Must be parsed sequentially from the beginning. ----> |
+-----------------------------------------------------------------------------------+
```
### Bolt Lazy Row Format Design
#### Core Design Principles
1. In-Band Nullability: Null status is encoded directly within the data value, eliminating the need for a separate NullBitset header. This maximizes data locality and removes the overhead of maintaining two separate memory cursors (validity buffer vs. data buffer).
* Implementation: Use Shifted Values for integers (e.g., 0 = Null, Val+1 = Value), Canonical NaN for floating-point numbers, and Length Markers for variable-length types.
2. Shifted Varint Encoding: All integers use ZigZag Varint encoding for compactness. To support In-Band Nulls, integer values are logically "shifted":
* Raw 0 → Represents SQL NULL.
* Raw n (n>0) → Represents the value n−1.
* Benefit: A stream of small integer data becomes a highly compressible stream.
* Use bmi2's pdep and pext to do encoding
3. No Offsets (Sequential Access): Data is packed sequentially without an offset table. To access field N, the reader must sequentially read (and skip) fields 0 to N−1. This trades random access speed for maximum storage density.
4. Encoding-Aware Arrays: Arrays include an explicit Encoding byte to support specialized compression strategies.
* Plain: Standard sequential In-Band storage.
* RLE (Run-Length Encoding): Compresses repeated values (including Nulls, e.g., [Count: 50, Value: NULL]) to handle sparse data efficiently.
#### Format
```
// for { id: NULL, score: 1.5 (Double), name: "Bolt" }
+-----------------------------------------------------------------------------------------------+
| Row Layout (Sequential) |
+-----------------------------------------------------------------------------------------------+
| Field 0 (id: Int) | Field 1 (score: Double) | Field 2 (name: String) |
+-------------------------------+---------------------------------+-----------------------------+
| | | |
| [0x00] | [0x3F, 0xF8, ... (IEEE 754)] | [Len: 4] [B, o, l, t] |
| | | |
| (Value = 0) | (Standard 8 bytes) | (Varint Len) + (Bytes) |
| -> Decodes to SQL NULL | -> Decodes to 1.5 | |
| | | |
+-------------------------------+---------------------------------+-----------------------------+
| <--- No Row Header! Starts immediately with Field 0 ----------------------------------------> |
+-----------------------------------------------------------------------------------------------+
// for array [10, NULL, -5]
+---------------------------------------------------------------------------------------+
| Array Layout (Encoding = PLAIN / 0x00) |
+---------------------------------------------------------------------------------------+
| Size (Varint) | Encoding | Payload (Sequential Stream) |
+----------------+----------+-----------------------------------------------------------+
| | | |
| 3 | 0x00 | [Varint: 21] [Varint: 0] [Varint: 10] |
| | | (Val: 10) (Val: NULL) (Val: -5) |
| | | |
+----------------+----------+-----------------------------------------------------------+
| <--- Header ---> | <----------------------- No Bitset ------------------------------> |
+---------------------------------------------------------------------------------------+
// for array [NULL, NULL, ..., NULL (50 times), 99]
+---------------------------------------------------------------------------------------+
| Array Layout (Encoding = RLE / 0x01) |
+---------------------------------------------------------------------------------------+
| Size (Varint) | Encoding | Payload (Run-Length Pairs) |
+----------------+----------+-----------------------------------------------------------+
| | | | |
| 51 | 0x01 | [Run: 50] [Val: 0]| [Run: 1] [Val: 199] |
| (Logical Len) | | (NULL) | (Shifted 99) |
| | | | |
+----------------+----------+--------------------+--------------------------------------+
| | <--- Huge space saving for Nulls (2 bytes vs 50 bytes) -> |
+---------------------------------------------------------------------------------------+
```
Task breakdown
1. Implement an optimized row-format encoding and SerDe for complex types.
2. Integrate the complex row format into RowBased shuffle. Optional: replace PrestoSerde in the Bolt shuffle writer as well.
3. Add configuration options to automatically transform complex columns into a lazy format, and enable lazy-format support in operators (e.g., join/agg/shuffle).
4. Add a plan detector in Gluten, and only enable the lazy deserializer for complex types when those columns are not accessed by the plan.
### References / Prior Art
_No response_
### Importance
High (Needed for production)
### Willingness to Contribute
Yes, I can submit a PR
Contributor guide
Assessment
This issue has not been assessed yet.