Struct List

pub struct List {
    pub offsets: Option<Box<ArrayEncoding>>,
    pub null_offset_adjustment: u64,
    pub num_items: u64,
}

An array encoding for variable-length list fields

Fields

offsets: Option<Box<ArrayEncoding>>

An array containing the offsets into an items array.

This array will have num_rows items and will never have nulls.

If the list at index i is not null then offsets[i] will contain base + len(list) where base is defined as: i == 0: 0 i > 0: (offsets[i-1] % null_offset_adjustment)

To help understand we can consider the following example list: [ [A, B], null, [], [C, D, E] ]

The offsets will be [2, ?, 2, 5]

If the incoming list at index i IS null then offsets[i] will contain base + len(list) + null_offset_adjustment where base is defined the same as above.

To complete the above example let’s assume that null_offset_adjustment is 7. Then the offsets will be [2, 9, 2, 5]

If there are no nulls then the offsets we write here are exactly the same as the offsets in an Arrow list array (except we omit the leading 0 which is redundant)

The reason we do this is so that reading a single list at index i only requires us to load the indices at i and i-1.

If the offset at index i is greater than `null_offset_adjustment`` then the list at index i is null.

Otherwise the length of the list is offsets\[i\] - base where base is defined the same as above.

Let’s consider our example offsets: [2, 9, 2, 5]

We can take any range of lists and determine how many list items are referenced by the sublist.

0..3: [, 5] -> items 0..5 (base = 0* and end is 5) 0..2: [, 2] -> items 0..2 (base = 0* and end is 2) 0..1: [_, 9] -> items 0..2 (base = 0* and end is 9 % 7) 1..3: [2, 5] -> items 2..5 (base = 2 and end is 5) 1..2: [2, 2] -> items 2..2 (base = 2 and end is 2) 2..3: [9, 5] -> items 2..5 (base = 9 % 7 and end is 5)

• When the start of our range is the 0th item the base is always 0 and we only need to load a single index from disk to determine the range.

The data type of the offsets array is flexible and does not need to match the data type of the destination array. Please note that the offsets array is very likely to be efficiently encoded by bit packing deltas.

null_offset_adjustment: u64

If a list is null then we add this value to the offset

This value must be greater than the length of the items so that (offset + null_offset_adjustment) is never used by a non-null list.

Note that this value cannot be equal to the length of the items because then a page with a single list would store [ X ] and we couldn’t know if that is a null list or a list with X items.

Therefore, the best choice for this value is 1 + # of items. Choosing this will maximize the bit packing that we can apply to the offsets.

num_items: u64

How many items are referenced by these offsets. This is needed in order to determine which items pages map to this offsets page.

Trait Implementations

impl Clone for List

fn clone(&self) -> List

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for List

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

Formats the value using the given formatter.

impl Default for List

fn default() -> Self

Returns the “default value” for a type.

impl Message for List

fn encoded_len(&self) -> usize

Returns the encoded length of the message without a length delimiter.

fn clear(&mut self)

Clears the message, resetting all fields to their default.

fn encode(&self, buf: &mut impl BufMut) -> Result<(), EncodeError>

where Self: Sized,

Encodes the message to a buffer.

fn encode_to_vec(&self) -> Vec<u8>

where Self: Sized,

Encodes the message to a newly allocated buffer.

fn encode_length_delimited( &self, buf: &mut impl BufMut, ) -> Result<(), EncodeError>

where Self: Sized,

Encodes the message with a length-delimiter to a buffer.

fn encode_length_delimited_to_vec(&self) -> Vec<u8>

where Self: Sized,

Encodes the message with a length-delimiter to a newly allocated buffer.

fn decode(buf: impl Buf) -> Result<Self, DecodeError>

where Self: Default,

Decodes an instance of the message from a buffer.

fn decode_length_delimited(buf: impl Buf) -> Result<Self, DecodeError>

where Self: Default,

Decodes a length-delimited instance of the message from the buffer.

fn merge(&mut self, buf: impl Buf) -> Result<(), DecodeError>

where Self: Sized,

Decodes an instance of the message from a buffer, and merges it into self.

fn merge_length_delimited(&mut self, buf: impl Buf) -> Result<(), DecodeError>

where Self: Sized,

Decodes a length-delimited instance of the message from buffer, and merges it into self.

impl Name for List

const NAME: &'static str = "List"

Simple name for this Message. This name is the same as it appears in the source .proto file, e.g. FooBar.

const PACKAGE: &'static str = "lance.encodings"

Package name this message type is contained in. They are domain-like and delimited by ., e.g. google.protobuf.

fn full_name() -> String

Fully-qualified unique name for this Message. It’s prefixed with the package name and names of any parent messages, e.g. google.rpc.BadRequest.FieldViolation. By default, this is the package name followed by the message name. Fully-qualified names must be unique within a domain of Type URLs.

fn type_url() -> String

Type URL for this Message, which by default is the full name with a leading slash, but may also include a leading domain name, e.g. type.googleapis.com/google.profile.Person. This can be used when serializing into the google.protobuf.Any type.

impl PartialEq for List

fn eq(&self, other: &List) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl StructuralPartialEq for List