Full Chunk-based Computing

Presented by Chi Zhang (@skyzh)

Contents

• Motivation
• Developer Interface Changes
• Internal Changes
• Benchmark
• Future works

What is Chunk-based Computing

• Using TiDB Chunk format during computation in coprocessor framework
• Previously: Vec<Option<T>>

Motivation

• Many SQL functions handle “NULL” in the same way
• Memory allocation overhead of “Bytes” and “Json”
• Overhead in decoding and encoding data of TiDB
• Solution: use TiDB Chunk format in TiKV coprocessor framework

Changes in Developer Interface

For primitive types (Int, Decimal, etc.)

• add “nullable” to “rpn_fn” macro attributes
• “&Option<T>” to “Option<&T>”

Changes in Developer Interface

For “Bytes” and “Json”

• add “nullable” to “rpn_fn” macro attributes
• “&Option<Bytes>” to “Option<BytesRef>”
• “&Option<Json>” to “Option<JsonRef>”

Changes in Developer Interface

For functions that return “NULL” if any of the argument is “NULL”

• no attributes for “rpn_fn” macro
• remove “Option” in parameters

​

Changes in Developer Interface

For functions that may return large amounts of data

• Use writer-guard pattern to avoid allocation
• partial writer: begin ➡️ partial_write ➡️ finish

Changes in Developer Interface

For functions that may return large amounts of data

• Use writer-guard pattern to avoid allocation
• direct write: write(Some(Bytes)), write_ref(Some(BytesRef)), write(None)

Changes in Developer Interface

​

• using writer + Bytes / Json is recommended
• using “rpn_fn” without “nullable” is recommended

Internal Changes

• “Vec<Option<T>>” to “ChunkedVecSized<T>”
• append-only
• can only get reference to an element (&T)
• use “bitmap” to represent if cell is null or not
• more compact layout

Some(128)

Some(64)

None

Vec<Option<Int>>

(16 * 3 = 48 bytes)

128

64

0

(8 * 3 + 1 = 25 bytes)

ChunkedVecSized<T>

11000000

bitmap (BitVec)

lowest - highest bit

Internal Changes

• “Vec<Option<Bytes>>” to “ChunkedVecBytes”, “Vec<Option<Json>>” to “ChunkedVecJson”
• append-only
• can only get “BytesRef” or “JsonRef”
• data are stored adjacently in memory

abcd

efgh

ijkl

Vec<Option<Bytes>>

abcdefghijkl

ChunkedVecBytes

ptr

ptr

NULL

ptr

(Somewhere in memory)

offsets

0

4

8

8

12

11010000

bitmap (BitVec)

lowest - highest bit

Internal Changes

• “NULL”s are merged before evaluating for functions without “nullable”
• Previously: “add” receives Option<Int> and handles NULL inside RPN function

add(a: &Int, b: &Int)

11100111

bitmap of A

11011111

bitmap of B

bitwise and

11000111

merged bitmap

evaluate

Micro Benchmarks

• Significant improvement in processing Bytes data

Future works

• Speedup encode and decode speed
• efficiently tell if “logical_rows” are identical
• construct “ChunkedVec” directly from TiDB Chunk format
• construct TiDB Chunk “Column” directly from “ChunkedVec”
• Support “nullable” and NULL merging in variable argument RPN function #[rpn_fn(vargs)]
• Refactor existing vectorized functions to use new interface

Thank You !