Struct datafusion::common::arrow::row::RowConverter

pub struct RowConverter { /* private fields */ }

Converts ArrayRef columns into a row-oriented format.

Note: The encoding of the row format may change from release to release.

Overview

The row format is a variable length byte sequence created by concatenating the encoded form of each column. The encoding for each column depends on its datatype (and sort options).

The encoding is carefully designed in such a way that escaping is unnecessary: it is never ambiguous as to whether a byte is part of a sentinel (e.g. null) or a value.

Unsigned Integer Encoding

A null integer is encoded as a 0_u8, followed by a zero-ed number of bytes corresponding to the integer’s length.

A valid integer is encoded as 1_u8, followed by the big-endian representation of the integer.

              ┌──┬──┬──┬──┐      ┌──┬──┬──┬──┬──┐
   3          │03│00│00│00│      │01│00│00│00│03│
              └──┴──┴──┴──┘      └──┴──┴──┴──┴──┘
              ┌──┬──┬──┬──┐      ┌──┬──┬──┬──┬──┐
  258         │02│01│00│00│      │01│00│00│01│02│
              └──┴──┴──┴──┘      └──┴──┴──┴──┴──┘
              ┌──┬──┬──┬──┐      ┌──┬──┬──┬──┬──┐
 23423        │7F│5B│00│00│      │01│00│00│5B│7F│
              └──┴──┴──┴──┘      └──┴──┴──┴──┴──┘
              ┌──┬──┬──┬──┐      ┌──┬──┬──┬──┬──┐
 NULL         │??│??│??│??│      │00│00│00│00│00│
              └──┴──┴──┴──┘      └──┴──┴──┴──┴──┘

             32-bit (4 bytes)        Row Format
 Value        Little Endian

Signed Integer Encoding

Signed integers have their most significant sign bit flipped, and are then encoded in the same manner as an unsigned integer.

       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐
    5  │05│00│00│00│       │05│00│00│80│       │01│80│00│00│05│
       └──┴──┴──┴──┘       └──┴──┴──┴──┘       └──┴──┴──┴──┴──┘
       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┐       ┌──┬──┬──┬──┬──┐
   -5  │FB│FF│FF│FF│       │FB│FF│FF│7F│       │01│7F│FF│FF│FB│
       └──┴──┴──┴──┘       └──┴──┴──┴──┘       └──┴──┴──┴──┴──┘

 Value  32-bit (4 bytes)    High bit flipped      Row Format
         Little Endian

Float Encoding

Floats are converted from IEEE 754 representation to a signed integer representation by flipping all bar the sign bit if they are negative.

They are then encoded in the same manner as a signed integer.

Fixed Length Bytes Encoding

Fixed length bytes are encoded in the same fashion as primitive types above.

For a fixed length array of length n:

A null is encoded as 0_u8 null sentinel followed by n 0_u8 bytes

A valid value is encoded as 1_u8 followed by the value bytes

Variable Length Bytes (including Strings) Encoding

A null is encoded as a 0_u8.

An empty byte array is encoded as 1_u8.

A non-null, non-empty byte array is encoded as 2_u8 followed by the byte array encoded using a block based scheme described below.

The byte array is broken up into fixed-width blocks, each block is written in turn to the output, followed by 0xFF_u8. The final block is padded to 32-bytes with 0_u8 and written to the output, followed by the un-padded length in bytes of this final block as a u8. The first 4 blocks have a length of 8, with subsequent blocks using a length of 32, this is to reduce space amplification for small strings.

Note the following example encodings use a block size of 4 bytes for brevity:

                      ┌───┬───┬───┬───┬───┬───┐
 "MEEP"               │02 │'M'│'E'│'E'│'P'│04 │
                      └───┴───┴───┴───┴───┴───┘

                      ┌───┐
 ""                   │01 |
                      └───┘

 NULL                 ┌───┐
                      │00 │
                      └───┘

"Defenestration"      ┌───┬───┬───┬───┬───┬───┐
                      │02 │'D'│'e'│'f'│'e'│FF │
                      └───┼───┼───┼───┼───┼───┤
                          │'n'│'e'│'s'│'t'│FF │
                          ├───┼───┼───┼───┼───┤
                          │'r'│'a'│'t'│'r'│FF │
                          ├───┼───┼───┼───┼───┤
                          │'a'│'t'│'i'│'o'│FF │
                          ├───┼───┼───┼───┼───┤
                          │'n'│00 │00 │00 │01 │
                          └───┴───┴───┴───┴───┘

This approach is loosely inspired by COBS encoding, and chosen over more traditional byte stuffing as it is more amenable to vectorisation, in particular AVX-256.

Dictionary Encoding

Dictionaries are hydrated to their underlying values

Struct Encoding

A null is encoded as a 0_u8.

A valid value is encoded as 1_u8 followed by the row encoding of each child.

This encoding effectively flattens the schema in a depth-first fashion.

For example

┌───────┬────────────────────────┬───────┐
│ Int32 │ Struct[Int32, Float32] │ Int32 │
└───────┴────────────────────────┴───────┘

Is encoded as

┌───────┬───────────────┬───────┬─────────┬───────┐
│ Int32 │ Null Sentinel │ Int32 │ Float32 │ Int32 │
└───────┴───────────────┴───────┴─────────┴───────┘

List Encoding

Lists are encoded by first encoding all child elements to the row format.

A “canonical byte array” is then constructed by concatenating the row encodings of all their elements into a single binary array, followed by the lengths of each encoded row, and the number of elements, encoded as big endian u32.

This canonical byte array is then encoded using the variable length byte encoding described above.

The lengths are not strictly necessary but greatly simplify decode, they may be removed in a future iteration.

For example given:

[1_u8, 2_u8, 3_u8]
[1_u8, null]
[]
null

The elements would be converted to:

    ┌──┬──┐     ┌──┬──┐     ┌──┬──┐     ┌──┬──┐        ┌──┬──┐
 1  │01│01│  2  │01│02│  3  │01│03│  1  │01│01│  null  │00│00│
    └──┴──┘     └──┴──┘     └──┴──┘     └──┴──┘        └──┴──┘

Which would be grouped into the following canonical byte arrays:

                        ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
 [1_u8, 2_u8, 3_u8]     │01│01│01│02│01│03│00│00│00│02│00│00│00│02│00│00│00│02│00│00│00│03│
                        └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
                         └──── rows ────┘   └───────── row lengths ─────────┘  └─ count ─┘

                        ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
 [1_u8, null]           │01│01│00│00│00│00│00│02│00│00│00│02│00│00│00│02│
                        └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

With [] represented by an empty byte array, and null a null byte array.

These byte arrays will then be encoded using the variable length byte encoding described above.

Ordering

Float Ordering

Floats are totally ordered in accordance to the totalOrder predicate as defined in the IEEE 754 (2008 revision) floating point standard.

The ordering established by this does not always agree with the PartialOrd and PartialEq implementations of f32. For example, they consider negative and positive zero equal, while this does not

Null Ordering

The encoding described above will order nulls first, this can be inverted by representing nulls as 0xFF_u8 instead of 0_u8

Reverse Column Ordering

The order of a given column can be reversed by negating the encoded bytes of non-null values

Implementations

impl RowConverter

pub fn new(fields: Vec<SortField>) -> Result<RowConverter, ArrowError>

Create a new RowConverter with the provided schema

pub fn supports_fields(fields: &[SortField]) -> bool

Check if the given fields are supported by the row format.

pub fn convert_columns( &self, columns: &[Arc<dyn Array>] ) -> Result<Rows, ArrowError>

Convert ArrayRef columns into Rows

See Row for information on when Row can be compared

Panics

Panics if the schema of columns does not match that provided to RowConverter::new

pub fn append( &self, rows: &mut Rows, columns: &[Arc<dyn Array>] ) -> Result<(), ArrowError>

Convert ArrayRef columns appending to an existing Rows

See Row for information on when Row can be compared

Panics

Panics if

• The schema of columns does not match that provided to RowConverter::new
• The provided Rows were not created by this RowConverter

let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
let a1 = StringArray::from(vec!["hello", "world"]);
let a2 = StringArray::from(vec!["a", "a", "hello"]);

let mut rows = converter.empty_rows(5, 128);
converter.append(&mut rows, &[Arc::new(a1)]).unwrap();
converter.append(&mut rows, &[Arc::new(a2)]).unwrap();

let back = converter.convert_rows(&rows).unwrap();
let values: Vec<_> = back[0].as_string::<i32>().iter().map(Option::unwrap).collect();
assert_eq!(&values, &["hello", "world", "a", "a", "hello"]);

pub fn convert_rows<'a, I>( &self, rows: I ) -> Result<Vec<Arc<dyn Array>>, ArrowError>

where I: IntoIterator<Item = Row<'a>>,

Convert Rows columns into ArrayRef

Panics

Panics if the rows were not produced by this RowConverter

pub fn empty_rows(&self, row_capacity: usize, data_capacity: usize) -> Rows

Returns an empty Rows with capacity for row_capacity rows with a total length of data_capacity

This can be used to buffer a selection of Row

let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
let array = StringArray::from(vec!["hello", "world", "a", "a", "hello"]);

// Convert to row format and deduplicate
let converted = converter.convert_columns(&[Arc::new(array)]).unwrap();
let mut distinct_rows = converter.empty_rows(3, 100);
let mut dedup: HashSet<Row> = HashSet::with_capacity(3);
converted.iter().filter(|row| dedup.insert(*row)).for_each(|row| distinct_rows.push(row));

// Note: we could skip buffering and feed the filtered iterator directly
// into convert_rows, this is done for demonstration purposes only
let distinct = converter.convert_rows(&distinct_rows).unwrap();
let values: Vec<_> = distinct[0].as_string::<i32>().iter().map(Option::unwrap).collect();
assert_eq!(&values, &["hello", "world", "a"]);

pub fn parser(&self) -> RowParser

Returns a RowParser that can be used to parse Row from bytes

pub fn size(&self) -> usize

Returns the size of this instance in bytes

Includes the size of Self.

Trait Implementations

impl Debug for RowConverter

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.