Chao -- yes, I believe you're right.
In an IPC message, if the node is required or has null_count == 0,
then the null bitmap can be omitted from the payload, but otherwise
it's there (this is similar to the Hive HS2 V6 protocol).
One alternative to this is that rather than omitting the bitmap, its
data header metadata can be included but the buffer size is zero.
- Wes
On Sun, Mar 6, 2016 at 12:33 PM, Chao Sun <sunc...@apache.org> wrote:
> Hi,
>
> Sorry if this is a n00b question. For the example that Jacques used in the
> previous thread, how does it work if the struct is nullable - shouldn't
> there
> be a is_null array between 1 and 2?
>
> For instance, with the example:
>
> list elem #0: { <f0: aaa, f1: 42>, null, <f0: null, f1: 28> }
> list elem #1: { <f0: bbb, f1: null> }
> list elem #2: null
> list elem #3: { <f0: null, f1: null> }
>
> what does the encoding look like?
>
> I'm thinking: (0 = false, 1 = true in is_null arrays):
>
> 0 (list is_null): 0 0 1 0
> 1 (list offset): 0 3 4 4 5
> 2 (struct is_null): 0 1 0 0 0
> 3 (struct field f0 is_null): 0 1 0 1
> 4 (struct field f0 offset): 0 3 3 6 6
> 5 (struct field f0 value): a a a b b b
> 6 (struct field f1 is_null): 1 1 0 0
> 7 (struct field f1 value): 42 28
>
> Let me know if this is wrong. Thanks!
>
> Best,
> Chao
>
> On Tue, Mar 1, 2016 at 1:13 PM, Wes McKinney <w...@cloudera.com> wrote:
>
>> Inline responses
>>
>> On Tue, Mar 1, 2016 at 8:24 AM, Jacques Nadeau <jacq...@apache.org> wrote:
>> > Wes, thanks for starting this conversation.
>> >
>> > Couple thoughts:
>> >
>> > For metadata, we have two models existing (one in the ValueVectors
>> approach
>> > and one in Parquet). It seems like we should start from one of those and
>> > then shape as appropriate. It seems like we have a richer physical
>> > capability that the core Dremel algorithm that Parquet implements so I
>> > think it would make sense to focus first on the logical model and then
>> > figure out the shared physical that exists below that.
>> >
>> > While the Data Headers item (2) in your description may come logically
>> > second, I think that it greatly informs 1.B as I believe 2 is something
>> > that should be an in-memory canonical representation (similar to the
>> > vectors themselves). I know Steven has been looking at moving the Java
>> > layer over to serialize the data headers using something similar to this:
>> >
>> > Data headers use a deterministic pre-order "tree" ordering of the memory
>> > buffers (https://en.wikipedia.org/wiki/Tree_traversal). The data
>> structures
>> > are simply an array of data headers consisting of a list of buffer
>> offsets
>> > and sizes.
>> >
>>
>> This makes sense, and is consistent with Parquet's depth-first
>> (pre-order) flattening of nested schemas into a flat
>> list<SchemaElement>
>> (
>> https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift#L556
>> ).
>>
>> > For example, consider this schema:
>> >
>> > List<Struct<String=List<UInt8>, Int32>>
>> >
>> > the pre-order buffer order is
>> >
>> > 0: nulls top level list
>> >
>> > 1: list offsets
>> >
>> > 2: struct field 0 nulls
>> >
>> > 3: struct field 0 list offsets
>> >
>> > 4: struct field 0 inner UInt8 values
>> >
>> > 5: struct field 1 nulls
>> >
>> > 6: struct field 1 Int32 values
>> >
>>
>> Regarding the buffers, we would want to embed the null count for each
>> logical array in some way, so that the null bitmap can be omitted.
>> This also spares having to compute the actual null counts when
>> receiving a row batch.
>>
>> For example, a List<T>, we could have a couple cases:
>>
>> List
>> - null_count > 0 -> 2 buffers, 1 for the null bitmap, 1 for the list
>> offsets
>> - null_count == 0 -> 1 buffer for the list offsets
>>
>> Recursively, the buffers for the type T child data would similarly
>> have its own null count, determining the actual number of memory
>> buffers. Let me know what you think.
>>
>> > The flatbuffer schema for the data header would then be:
>> >
>> > namespace DataHeaders;
>> >
>> > struct Buffer {
>> >
>> > data: long;
>> >
>> > length: int;
>> >
>> > }
>> >
>> > // Representing a single array (aka ValueVector), typically
>> >
>> > table BufferList {
>> >
>> > // With FBS it is not possible to know the length of an array
>> >
>> > n_buffers: int;
>> >
>> > buffers: [Buffer];
>> >
>> > }
>> >
>> > // Multiple arrays -- could be used for long arrays or a
>> >
>> > // whole table row batch
>> >
>> > table ArrayBatch {
>> >
>> > n_arrays: int;
>> >
>> > arrays: [BufferList];
>> >
>> > }
>>
>> I've been tinkering with flatbuffers, and array lengths are indeed
>> available in the generated IDL (see flatbuffers::Vector::size in the
>> C++ API, for example), so the n_buffers / n_arrays fields aren't
>> needed.
>>
>> Per the discussion above re: null counts, something like this may work:
>>
>> struct Buffer {
>> data: long;
>> length: int;
>> }
>>
>> table ArrayNode {
>> length: int;
>> null_count: int;
>>
>> /// The number of buffers would be inferred from the node type and actual
>> /// null_count
>> buffers: [Buffer];
>> }
>>
>> table RowBatch {
>> /// Nodes correspond to the depth-first flattened logical schema
>> nodes: [ArrayNode];
>> }
>>
>> So in an example schema:
>>
>> row batch schema {
>> f0: List<List<UInt8>>,
>> f1: Int32
>> }
>>
>> The flattened version of this schema contains 4 ArrayNodes, 3 for the
>> nested f0 column, and 1 for the flat f1 column.
>>
>> - Wes
>>
>> >
>> >
>> > On Mon, Feb 29, 2016 at 6:13 PM, Wes McKinney <w...@cloudera.com> wrote:
>> >
>> >> hello all,
>> >>
>> >> I wanted to kick-start the process of coming up with a standardized /
>> >> canonical metadata specification that we can use for describing Arrow
>> >> data to be moved between systems. This breaks down into at least two
>> >> distinct kinds of metadata
>> >>
>> >> 1) "Schemas": physical types, logical types, child array types, struct
>> >> field names, and so forth. Does not contain information about the size
>> >> of the actual physical data (which depends on the length of arrays and
>> >> the sizes of list/variable-length type dimensions).
>> >>
>> >> 2) "Data headers": a description of the shape of a physical chunk of
>> >> data associated with a particular schema. Array length, null count,
>> >> memory buffer offsets and sizes, etc. This is the information you need
>> >> to compute the right pointers into a shared memory region or IPC/RPC
>> >> buffer and reconstruct Arrow container classes.
>> >>
>> >> Since #2 will depend on some of the details of #1, I suggest we start
>> >> figuring out #1 first. As far as the type metadata is concerned, to
>> >> avoid excess bike shedding we should break that problem into:
>> >>
>> >> A) The general layout of the type metadata / schemas
>> >> B) The technology we use for representing the schemas (and data
>> >> headers) in an implementation-independent way for use in an IPC/RPC
>> >> setting (and even to "store" ephemeral data on disk)
>> >>
>> >> On Item B, from what I've seen with Parquet and such file formats with
>> >> embedded metadata, and in the spirit of Arrow's "deserialize-nothing"
>> >> ethos, I suggest we explore no-deserialization technologies like
>> >> Google's Flatbuffers (https://github.com/google/flatbuffers) as a more
>> >> CPU-efficient alternative to Thrift, Protobuf, or Avro. In large
>> >> schemas, technologies like Thrift can result in significant overhead
>> >> in "needle-in-haystack" problems where you are picking only a few
>> >> columns out of very wide tables (> 1000s of columns), and it may be
>> >> best to try to avoid this if at all possible.
>> >>
>> >> I would like some help stewarding the design process on this from the
>> >> Arrow PMC and in particular those who have worked on the design and
>> >> implementation of Parquet and other file formats and systems for which
>> >> Arrow is an immediate intended companion. Lot of things we can learn
>> >> from those past experiences.
>> >>
>> >> Thank you,
>> >> Wes
>> >>
>>
