You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by uw...@apache.org on 2018/12/23 16:31:29 UTC
[22/51] [partial] arrow-site git commit: Upload nightly docs
http://git-wip-us.apache.org/repos/asf/arrow-site/blob/62ef7145/docs/latest/format/Layout.html
----------------------------------------------------------------------
diff --git a/docs/latest/format/Layout.html b/docs/latest/format/Layout.html
new file mode 100644
index 0000000..bf25c60
--- /dev/null
+++ b/docs/latest/format/Layout.html
@@ -0,0 +1,876 @@
+
+
+
+<!DOCTYPE html>
+<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
+<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
+<head>
+ <meta charset="utf-8">
+
+ <meta name="viewport" content="width=device-width, initial-scale=1.0">
+
+ <title>Physical memory layout — Apache Arrow v0.11.1.dev473+g6ed02454</title>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+ <link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
+ <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
+ <link rel="index" title="Index" href="../genindex.html" />
+ <link rel="search" title="Search" href="../search.html" />
+ <link rel="next" title="Metadata: Logical types, schemas, data headers" href="Metadata.html" />
+ <link rel="prev" title="Implementation guidelines" href="Guidelines.html" />
+
+
+ <script src="../_static/js/modernizr.min.js"></script>
+
+</head>
+
+<body class="wy-body-for-nav">
+
+
+ <div class="wy-grid-for-nav">
+
+
+ <nav data-toggle="wy-nav-shift" class="wy-nav-side">
+ <div class="wy-side-scroll">
+ <div class="wy-side-nav-search">
+
+
+
+ <a href="../index.html" class="icon icon-home"> Apache Arrow
+
+
+
+ </a>
+
+
+
+
+ <div class="version">
+ 0.11.1.dev473+g6ed02454
+ </div>
+
+
+
+
+<div role="search">
+ <form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
+ <input type="text" name="q" placeholder="Search docs" />
+ <input type="hidden" name="check_keywords" value="yes" />
+ <input type="hidden" name="area" value="default" />
+ </form>
+</div>
+
+
+ </div>
+
+ <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
+
+
+
+
+
+
+ <p class="caption"><span class="caption-text">Memory Format</span></p>
+<ul class="current">
+<li class="toctree-l1"><a class="reference internal" href="README.html">Arrow specification documents</a></li>
+<li class="toctree-l1"><a class="reference internal" href="Guidelines.html">Implementation guidelines</a></li>
+<li class="toctree-l1 current"><a class="current reference internal" href="#">Physical memory layout</a><ul>
+<li class="toctree-l2"><a class="reference internal" href="#definitions-terminology">Definitions / Terminology</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#requirements-goals-and-non-goals">Requirements, goals, and non-goals</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#goals-for-this-document">Goals (for this document)</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#non-goals-for-this-document">Non-goals (for this document)</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#byte-order-endianness">Byte Order (Endianness)</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#alignment-and-padding">Alignment and Padding</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#array-lengths">Array lengths</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#null-count">Null count</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#null-bitmaps">Null bitmaps</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#primitive-value-arrays">Primitive value arrays</a><ul>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-int32-array">Example Layout: Int32 Array</a></li>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-non-null-int32-array">Example Layout: Non-null int32 Array</a></li>
+</ul>
+</li>
+<li class="toctree-l2"><a class="reference internal" href="#list-type">List type</a><ul>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-list-char-array">Example Layout: <code class="docutils literal notranslate"><span class="pre">List<Char></span></code> Array</a></li>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-list-list-byte">Example Layout: <code class="docutils literal notranslate"><span class="pre">List<List<byte>></span></code></a></li>
+</ul>
+</li>
+<li class="toctree-l2"><a class="reference internal" href="#struct-type">Struct type</a><ul>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-struct-list-char-int32">Example Layout: <code class="docutils literal notranslate"><span class="pre">Struct<List<char>,</span> <span class="pre">Int32></span></code></a></li>
+</ul>
+</li>
+<li class="toctree-l2"><a class="reference internal" href="#dense-union-type">Dense union type</a><ul>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-dense-union">Example Layout: Dense union</a></li>
+</ul>
+</li>
+<li class="toctree-l2"><a class="reference internal" href="#sparse-union-type">Sparse union type</a><ul>
+<li class="toctree-l3"><a class="reference internal" href="#example-layout-sparseunion-u0-int32-u1-float-u2-list-char">Example layout: <code class="docutils literal notranslate"><span class="pre">SparseUnion<u0:</span> <span class="pre">Int32,</span> <span class="pre">u1:</span> <span class="pre">Float,</span> <span class="pre">u2:</span> <span class="pre">List<Char>></span></code></a></li>
+</ul>
+</li>
+<li class="toctree-l2"><a class="reference internal" href="#dictionary-encoding">Dictionary encoding</a></li>
+<li class="toctree-l2"><a class="reference internal" href="#references">References</a></li>
+</ul>
+</li>
+<li class="toctree-l1"><a class="reference internal" href="Metadata.html">Metadata: Logical types, schemas, data headers</a></li>
+<li class="toctree-l1"><a class="reference internal" href="IPC.html">Interprocess messaging / communication (IPC)</a></li>
+</ul>
+<p class="caption"><span class="caption-text">Languages</span></p>
+<ul>
+<li class="toctree-l1"><a class="reference internal" href="../cpp/index.html">C++ Implementation</a></li>
+<li class="toctree-l1"><a class="reference internal" href="../python/index.html">Python bindings</a></li>
+</ul>
+
+
+
+ </div>
+ </div>
+ </nav>
+
+ <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
+
+
+ <nav class="wy-nav-top" aria-label="top navigation">
+
+ <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
+ <a href="../index.html">Apache Arrow</a>
+
+ </nav>
+
+
+ <div class="wy-nav-content">
+
+ <div class="rst-content">
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+<div role="navigation" aria-label="breadcrumbs navigation">
+
+ <ul class="wy-breadcrumbs">
+
+ <li><a href="../index.html">Docs</a> »</li>
+
+ <li>Physical memory layout</li>
+
+
+ <li class="wy-breadcrumbs-aside">
+
+
+ <a href="../_sources/format/Layout.rst.txt" rel="nofollow"> View page source</a>
+
+
+ </li>
+
+ </ul>
+
+
+ <hr/>
+</div>
+ <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
+ <div itemprop="articleBody">
+
+ <div class="section" id="physical-memory-layout">
+<h1>Physical memory layout<a class="headerlink" href="#physical-memory-layout" title="Permalink to this headline">¶</a></h1>
+<div class="section" id="definitions-terminology">
+<h2>Definitions / Terminology<a class="headerlink" href="#definitions-terminology" title="Permalink to this headline">¶</a></h2>
+<p>Since different projects have used different words to describe various
+concepts, here is a small glossary to help disambiguate.</p>
+<ul class="simple">
+<li>Array: a sequence of values with known length all having the same type.</li>
+<li>Slot or array slot: a single logical value in an array of some particular data type</li>
+<li>Contiguous memory region: a sequential virtual address space with a given
+length. Any byte can be reached via a single pointer offset less than the
+region’s length.</li>
+<li>Contiguous memory buffer: A contiguous memory region that stores
+a multi-value component of an Array. Sometimes referred to as just “buffer”.</li>
+<li>Primitive type: a data type that occupies a fixed-size memory slot specified
+in bit width or byte width</li>
+<li>Nested or parametric type: a data type whose full structure depends on one or
+more other child relative types. Two fully-specified nested types are equal
+if and only if their child types are equal. For example, <code class="docutils literal notranslate"><span class="pre">List<U></span></code> is distinct
+from <code class="docutils literal notranslate"><span class="pre">List<V></span></code> iff U and V are different relative types.</li>
+<li>Relative type or simply type (unqualified): either a specific primitive type
+or a fully-specified nested type. When we say slot we mean a relative type
+value, not necessarily any physical storage region.</li>
+<li>Logical type: A data type that is implemented using some relative (physical)
+type. For example, Decimal values are stored as 16 bytes in a fixed byte
+size array. Similarly, strings can be stored as <code class="docutils literal notranslate"><span class="pre">List<1-byte></span></code>.</li>
+<li>Parent and child arrays: names to express relationships between physical
+value arrays in a nested type structure. For example, a <code class="docutils literal notranslate"><span class="pre">List<T></span></code>-type parent
+array has a T-type array as its child (see more on lists below).</li>
+<li>Leaf node or leaf: A primitive value array that may or may not be a child
+array of some array with a nested type.</li>
+</ul>
+</div>
+<div class="section" id="requirements-goals-and-non-goals">
+<h2>Requirements, goals, and non-goals<a class="headerlink" href="#requirements-goals-and-non-goals" title="Permalink to this headline">¶</a></h2>
+<p>Base requirements</p>
+<ul class="simple">
+<li>A physical memory layout enabling zero-deserialization data interchange
+amongst a variety of systems handling flat and nested columnar data, including
+such systems as Spark, Drill, Impala, Kudu, Ibis, ODBC protocols, and
+proprietary systems that utilize the open source components.</li>
+<li>All array slots are accessible in constant time, with complexity growing
+linearly in the nesting level</li>
+<li>Capable of representing fully-materialized and decoded / decompressed <a class="reference external" href="https://parquet.apache.org/documentation/latest/">Parquet</a>
+data</li>
+<li>It is required to have all the contiguous memory buffers in an IPC payload
+aligned at 8-byte boundaries. In other words, each buffer must start at
+an aligned 8-byte offset.</li>
+<li>The general recommendation is to align the buffers at 64-byte boundary, but
+this is not absolutely necessary.</li>
+<li>Any relative type can have null slots</li>
+<li>Arrays are immutable once created. Implementations can provide APIs to mutate
+an array, but applying mutations will require a new array data structure to
+be built.</li>
+<li>Arrays are relocatable (e.g. for RPC/transient storage) without pointer
+swizzling. Another way of putting this is that contiguous memory regions can
+be migrated to a different address space (e.g. via a memcpy-type of
+operation) without altering their contents.</li>
+</ul>
+</div>
+<div class="section" id="goals-for-this-document">
+<h2>Goals (for this document)<a class="headerlink" href="#goals-for-this-document" title="Permalink to this headline">¶</a></h2>
+<ul class="simple">
+<li>To describe relative types (physical value types and a preliminary set of
+nested types) sufficient for an unambiguous implementation</li>
+<li>Memory layout and random access patterns for each relative type</li>
+<li>Null value representation</li>
+</ul>
+</div>
+<div class="section" id="non-goals-for-this-document">
+<h2>Non-goals (for this document)<a class="headerlink" href="#non-goals-for-this-document" title="Permalink to this headline">¶</a></h2>
+<ul class="simple">
+<li>To enumerate or specify logical types that can be implemented as primitive
+(fixed-width) value types. For example: signed and unsigned integers,
+floating point numbers, boolean, exact decimals, date and time types,
+CHAR(K), VARCHAR(K), etc.</li>
+<li>To specify standardized metadata or a data layout for RPC or transient file
+storage.</li>
+<li>To define a selection or masking vector construct</li>
+<li>Implementation-specific details</li>
+<li>Details of a user or developer C/C++/Java API.</li>
+<li>Any “table” structure composed of named arrays each having their own type or
+any other structure that composes arrays.</li>
+<li>Any memory management or reference counting subsystem</li>
+<li>To enumerate or specify types of encodings or compression support</li>
+</ul>
+</div>
+<div class="section" id="byte-order-endianness">
+<h2>Byte Order (<a class="reference external" href="https://en.wikipedia.org/wiki/Endianness">Endianness</a>)<a class="headerlink" href="#byte-order-endianness" title="Permalink to this headline">¶</a></h2>
+<p>The Arrow format is little endian by default.
+The Schema metadata has an endianness field indicating endianness of RecordBatches.
+Typically this is the endianness of the system where the RecordBatch was generated.
+The main use case is exchanging RecordBatches between systems with the same Endianness.
+At first we will return an error when trying to read a Schema with an endianness
+that does not match the underlying system. The reference implementation is focused on
+Little Endian and provides tests for it. Eventually we may provide automatic conversion
+via byte swapping.</p>
+</div>
+<div class="section" id="alignment-and-padding">
+<h2>Alignment and Padding<a class="headerlink" href="#alignment-and-padding" title="Permalink to this headline">¶</a></h2>
+<p>As noted above, all buffers must be aligned in memory at 8-byte boundaries and padded
+to a length that is a multiple of 8 bytes. The alignment requirement follows best
+practices for optimized memory access:</p>
+<ul class="simple">
+<li>Elements in numeric arrays will be guaranteed to be retrieved via aligned access.</li>
+<li>On some architectures alignment can help limit partially used cache lines.</li>
+<li>64 byte alignment is recommended by the <a class="reference external" href="https://software.intel.com/en-us/articles/practical-intel-avx-optimization-on-2nd-generation-intel-core-processors">Intel performance guide</a> for
+data-structures over 64 bytes (which will be a common case for Arrow Arrays).</li>
+</ul>
+<p>Recommending padding to a multiple of 64 bytes allows for using <a class="reference external" href="https://software.intel.com/en-us/node/600110">SIMD</a> instructions
+consistently in loops without additional conditional checks.
+This should allow for simpler, efficient and CPU cache-friendly code.
+The specific padding length was chosen because it matches the largest known
+SIMD instruction registers available as of April 2016 (Intel AVX-512). In other
+words, we can load the entire 64-byte buffer into a 512-bit wide SIMD register
+and get data-level parallelism on all the columnar values packed into the 64-byte
+buffer. Guaranteed padding can also allow certain compilers
+to generate more optimized code directly (e.g. One can safely use Intel’s
+<code class="docutils literal notranslate"><span class="pre">-qopt-assume-safe-padding</span></code>).</p>
+<p>Unless otherwise noted, padded bytes do not need to have a specific value.</p>
+</div>
+<div class="section" id="array-lengths">
+<h2>Array lengths<a class="headerlink" href="#array-lengths" title="Permalink to this headline">¶</a></h2>
+<p>Array lengths are represented in the Arrow metadata as a 64-bit signed
+integer. An implementation of Arrow is considered valid even if it only
+supports lengths up to the maximum 32-bit signed integer, though. If using
+Arrow in a multi-language environment, we recommend limiting lengths to
+2 <sup>31</sup> - 1 elements or less. Larger data sets can be represented using
+multiple array chunks.</p>
+</div>
+<div class="section" id="null-count">
+<h2>Null count<a class="headerlink" href="#null-count" title="Permalink to this headline">¶</a></h2>
+<p>The number of null value slots is a property of the physical array and
+considered part of the data structure. The null count is represented in the
+Arrow metadata as a 64-bit signed integer, as it may be as large as the array
+length.</p>
+</div>
+<div class="section" id="null-bitmaps">
+<h2>Null bitmaps<a class="headerlink" href="#null-bitmaps" title="Permalink to this headline">¶</a></h2>
+<p>Any relative type can have null value slots, whether primitive or nested type.</p>
+<p>An array with nulls must have a contiguous memory buffer, known as the null (or
+validity) bitmap, whose length is a multiple of 64 bytes (as discussed above)
+and large enough to have at least 1 bit for each array
+slot.</p>
+<p>Whether any array slot is valid (non-null) is encoded in the respective bits of
+this bitmap. A 1 (set bit) for index <code class="docutils literal notranslate"><span class="pre">j</span></code> indicates that the value is not null,
+while a 0 (bit not set) indicates that it is null. Bitmaps are to be
+initialized to be all unset at allocation time (this includes padding).:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">is_valid</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-></span> <span class="n">bitmap</span><span class="p">[</span><span class="n">j</span> <span class="o">/</span> <span class="mi">8</span><span class="p">]</span> <span class="o">&</span> <span class="p">(</span><span class="mi">1</span> <span class="o"><<</span> <span class="p">(</span><span class="n">j</span> <span class="o">%</span> <span class="mi">8</span><span class="p">))</span>
+</pre></div>
+</div>
+<p>We use <a class="reference external" href="https://en.wikipedia.org/wiki/Bit_numbering">least-significant bit (LSB) numbering</a> (also known as
+bit-endianness). This means that within a group of 8 bits, we read
+right-to-left:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">values</span> <span class="o">=</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="n">null</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="n">null</span><span class="p">,</span> <span class="mi">3</span><span class="p">]</span>
+
+<span class="n">bitmap</span>
+<span class="n">j</span> <span class="n">mod</span> <span class="mi">8</span> <span class="mi">7</span> <span class="mi">6</span> <span class="mi">5</span> <span class="mi">4</span> <span class="mi">3</span> <span class="mi">2</span> <span class="mi">1</span> <span class="mi">0</span>
+ <span class="mi">0</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">0</span> <span class="mi">1</span> <span class="mi">1</span>
+</pre></div>
+</div>
+<p>Arrays having a 0 null count may choose to not allocate the null
+bitmap. Implementations may choose to always allocate one anyway as a matter of
+convenience, but this should be noted when memory is being shared.</p>
+<p>Nested type arrays have their own null bitmap and null count regardless of
+the null count and null bits of their child arrays.</p>
+</div>
+<div class="section" id="primitive-value-arrays">
+<h2>Primitive value arrays<a class="headerlink" href="#primitive-value-arrays" title="Permalink to this headline">¶</a></h2>
+<p>A primitive value array represents a fixed-length array of values each having
+the same physical slot width typically measured in bytes, though the spec also
+provides for bit-packed types (e.g. boolean values encoded in bits).</p>
+<p>Internally, the array contains a contiguous memory buffer whose total size is
+equal to the slot width multiplied by the array length. For bit-packed types,
+the size is rounded up to the nearest byte.</p>
+<p>The associated null bitmap is contiguously allocated (as described above) but
+does not need to be adjacent in memory to the values buffer.</p>
+<div class="section" id="example-layout-int32-array">
+<h3>Example Layout: Int32 Array<a class="headerlink" href="#example-layout-int32-array" title="Permalink to this headline">¶</a></h3>
+<p>For example a primitive array of int32s:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="n">null</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">8</span><span class="p">]</span>
+</pre></div>
+</div>
+<p>Would look like:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">1</span>
+<span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Byte</span> <span class="mi">0</span> <span class="p">(</span><span class="n">validity</span> <span class="n">bitmap</span><span class="p">)</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">1</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|-------------------------|-----------------------|</span>
+ <span class="o">|</span> <span class="mi">00011101</span> <span class="o">|</span> <span class="mi">0</span> <span class="p">(</span><span class="n">padding</span><span class="p">)</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Value</span> <span class="n">Buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">8</span><span class="o">-</span><span class="mi">11</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">12</span><span class="o">-</span><span class="mi">15</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">16</span><span class="o">-</span><span class="mi">19</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">20</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|------------|-------------|-------------|-------------|-------------|-------------|</span>
+ <span class="o">|</span> <span class="mi">1</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span> <span class="mi">2</span> <span class="o">|</span> <span class="mi">4</span> <span class="o">|</span> <span class="mi">8</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+</pre></div>
+</div>
+</div>
+<div class="section" id="example-layout-non-null-int32-array">
+<h3>Example Layout: Non-null int32 Array<a class="headerlink" href="#example-layout-non-null-int32-array" title="Permalink to this headline">¶</a></h3>
+<p><code class="docutils literal notranslate"><span class="pre">[1,</span> <span class="pre">2,</span> <span class="pre">3,</span> <span class="pre">4,</span> <span class="pre">8]</span></code> has two possible layouts:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">0</span>
+<span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span>
+
+ <span class="o">|</span> <span class="n">Byte</span> <span class="mi">0</span> <span class="p">(</span><span class="n">validity</span> <span class="n">bitmap</span><span class="p">)</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">1</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|--------------------------|-----------------------|</span>
+ <span class="o">|</span> <span class="mi">00011111</span> <span class="o">|</span> <span class="mi">0</span> <span class="p">(</span><span class="n">padding</span><span class="p">)</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Value</span> <span class="n">Buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">8</span><span class="o">-</span><span class="mi">11</span> <span class="o">|</span> <span class="nb">bytes</span> <span class="mi">12</span><span class="o">-</span><span class="mi">15</span> <span class="o">|</span> <span class="nb">bytes</span> <span class="mi">16</span><span class="o">-</span><span class="mi">19</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">20</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|------------|-------------|-------------|-------------|-------------|-------------|</span>
+ <span class="o">|</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">2</span> <span class="o">|</span> <span class="mi">3</span> <span class="o">|</span> <span class="mi">4</span> <span class="o">|</span> <span class="mi">8</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+</pre></div>
+</div>
+<p>or with the bitmap elided:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">*</span> <span class="n">Length</span> <span class="mi">5</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">0</span>
+<span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span> <span class="n">Not</span> <span class="n">required</span>
+<span class="o">*</span> <span class="n">Value</span> <span class="n">Buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">8</span><span class="o">-</span><span class="mi">11</span> <span class="o">|</span> <span class="nb">bytes</span> <span class="mi">12</span><span class="o">-</span><span class="mi">15</span> <span class="o">|</span> <span class="nb">bytes</span> <span class="mi">16</span><span class="o">-</span><span class="mi">19</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">20</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|------------|-------------|-------------|-------------|-------------|-------------|</span>
+ <span class="o">|</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">2</span> <span class="o">|</span> <span class="mi">3</span> <span class="o">|</span> <span class="mi">4</span> <span class="o">|</span> <span class="mi">8</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+</pre></div>
+</div>
+</div>
+</div>
+<div class="section" id="list-type">
+<h2>List type<a class="headerlink" href="#list-type" title="Permalink to this headline">¶</a></h2>
+<p>List is a nested type in which each array slot contains a variable-size
+sequence of values all having the same relative type (heterogeneity can be
+achieved through unions, described later).</p>
+<p>A list type is specified like <code class="docutils literal notranslate"><span class="pre">List<T></span></code>, where <code class="docutils literal notranslate"><span class="pre">T</span></code> is any relative type
+(primitive or nested).</p>
+<p>A list-array is represented by the combination of the following:</p>
+<ul class="simple">
+<li>A values array, a child array of type T. T may also be a nested type.</li>
+<li>An offsets buffer containing 32-bit signed integers with length equal to the
+length of the top-level array plus one. Note that this limits the size of the
+values array to 2 <sup>31</sup> -1.</li>
+</ul>
+<p>The offsets array encodes a start position in the values array, and the length
+of the value in each slot is computed using the first difference with the next
+element in the offsets array. For example, the position and length of slot j is
+computed as:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">slot_position</span> <span class="o">=</span> <span class="n">offsets</span><span class="p">[</span><span class="n">j</span><span class="p">]</span>
+<span class="n">slot_length</span> <span class="o">=</span> <span class="n">offsets</span><span class="p">[</span><span class="n">j</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">-</span> <span class="n">offsets</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">//</span> <span class="p">(</span><span class="k">for</span> <span class="mi">0</span> <span class="o"><=</span> <span class="n">j</span> <span class="o"><</span> <span class="n">length</span><span class="p">)</span>
+</pre></div>
+</div>
+<p>The first value in the offsets array is 0, and the last element is the length
+of the values array.</p>
+<div class="section" id="example-layout-list-char-array">
+<h3>Example Layout: <code class="docutils literal notranslate"><span class="pre">List<Char></span></code> Array<a class="headerlink" href="#example-layout-list-char-array" title="Permalink to this headline">¶</a></h3>
+<p>Let’s consider an example, the type <code class="docutils literal notranslate"><span class="pre">List<Char></span></code>, where Char is a 1-byte
+logical type.</p>
+<p>For an array of length 4 with respective values:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[[</span><span class="s1">'j'</span><span class="p">,</span> <span class="s1">'o'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span> <span class="n">null</span><span class="p">,</span> <span class="p">[</span><span class="s1">'m'</span><span class="p">,</span> <span class="s1">'a'</span><span class="p">,</span> <span class="s1">'r'</span><span class="p">,</span> <span class="s1">'k'</span><span class="p">],</span> <span class="p">[]]</span>
+</pre></div>
+</div>
+<p>will have the following representation:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">4</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">1</span>
+<span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span>
+
+ <span class="o">|</span> <span class="n">Byte</span> <span class="mi">0</span> <span class="p">(</span><span class="n">validity</span> <span class="n">bitmap</span><span class="p">)</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">1</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|--------------------------|-----------------------|</span>
+ <span class="o">|</span> <span class="mi">00001101</span> <span class="o">|</span> <span class="mi">0</span> <span class="p">(</span><span class="n">padding</span><span class="p">)</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Offsets</span> <span class="n">buffer</span> <span class="p">(</span><span class="n">int32</span><span class="p">)</span>
+
+ <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">8</span><span class="o">-</span><span class="mi">11</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">12</span><span class="o">-</span><span class="mi">15</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">16</span><span class="o">-</span><span class="mi">19</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">20</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|------------|-------------|-------------|-------------|-------------|-------------|</span>
+ <span class="o">|</span> <span class="mi">0</span> <span class="o">|</span> <span class="mi">3</span> <span class="o">|</span> <span class="mi">3</span> <span class="o">|</span> <span class="mi">7</span> <span class="o">|</span> <span class="mi">7</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Values</span> <span class="n">array</span> <span class="p">(</span><span class="n">char</span> <span class="n">array</span><span class="p">):</span>
+ <span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">7</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">0</span>
+ <span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span> <span class="n">Not</span> <span class="n">required</span>
+
+ <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">6</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">7</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|------------|-------------|</span>
+ <span class="o">|</span> <span class="n">joemark</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+</pre></div>
+</div>
+</div>
+<div class="section" id="example-layout-list-list-byte">
+<h3>Example Layout: <code class="docutils literal notranslate"><span class="pre">List<List<byte>></span></code><a class="headerlink" href="#example-layout-list-list-byte" title="Permalink to this headline">¶</a></h3>
+<p><code class="docutils literal notranslate"><span class="pre">[[[1,</span> <span class="pre">2],</span> <span class="pre">[3,</span> <span class="pre">4]],</span> <span class="pre">[[5,</span> <span class="pre">6,</span> <span class="pre">7],</span> <span class="pre">null,</span> <span class="pre">[8]],</span> <span class="pre">[[9,</span> <span class="pre">10]]]</span></code></p>
+<p>will be be represented as follows:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>* Length 3
+* Nulls count: 0
+* Null bitmap buffer: Not required
+* Offsets buffer (int32)
+
+ | Bytes 0-3 | Bytes 4-7 | Bytes 8-11 | Bytes 12-15 | Bytes 16-63 |
+ |------------|------------|------------|-------------|-------------|
+ | 0 | 2 | 5 | 6 | unspecified |
+
+* Values array (`List<byte>`)
+ * Length: 6, Null count: 1
+ * Null bitmap buffer:
+
+ | Byte 0 (validity bitmap) | Bytes 1-63 |
+ |--------------------------|-------------|
+ | 00110111 | 0 (padding) |
+
+ * Offsets buffer (int32)
+
+ | Bytes 0-27 | Bytes 28-63 |
+ |----------------------|-------------|
+ | 0, 2, 4, 7, 7, 8, 10 | unspecified |
+
+ * Values array (bytes):
+ * Length: 10, Null count: 0
+ * Null bitmap buffer: Not required
+
+ | Bytes 0-9 | Bytes 10-63 |
+ |-------------------------------|-------------|
+ | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | unspecified |
+</pre></div>
+</div>
+</div>
+</div>
+<div class="section" id="struct-type">
+<h2>Struct type<a class="headerlink" href="#struct-type" title="Permalink to this headline">¶</a></h2>
+<p>A struct is a nested type parameterized by an ordered sequence of relative
+types (which can all be distinct), called its fields.</p>
+<p>Typically the fields have names, but the names and their types are part of the
+type metadata, not the physical memory layout.</p>
+<p>A struct array does not have any additional allocated physical storage for its values.
+A struct array must still have an allocated null bitmap, if it has one or more null values.</p>
+<p>Physically, a struct type has one child array for each field. The child arrays are independent and need not be adjacent to each other in memory.</p>
+<p>For example, the struct (field names shown here as strings for illustration
+purposes):</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">Struct</span> <span class="o"><</span>
+ <span class="n">name</span><span class="p">:</span> <span class="n">String</span> <span class="p">(</span><span class="o">=</span> <span class="n">List</span><span class="o"><</span><span class="n">char</span><span class="o">></span><span class="p">),</span>
+ <span class="n">age</span><span class="p">:</span> <span class="n">Int32</span>
+<span class="o">></span>
+</pre></div>
+</div>
+<p>has two child arrays, one <code class="docutils literal notranslate"><span class="pre">List<char></span></code> array (layout as above) and one 4-byte
+primitive value array having <code class="docutils literal notranslate"><span class="pre">Int32</span></code> logical type.</p>
+<div class="section" id="example-layout-struct-list-char-int32">
+<h3>Example Layout: <code class="docutils literal notranslate"><span class="pre">Struct<List<char>,</span> <span class="pre">Int32></span></code><a class="headerlink" href="#example-layout-struct-list-char-int32" title="Permalink to this headline">¶</a></h3>
+<p>The layout for <code class="docutils literal notranslate"><span class="pre">[{'joe',</span> <span class="pre">1},</span> <span class="pre">{null,</span> <span class="pre">2},</span> <span class="pre">null,</span> <span class="pre">{'mark',</span> <span class="pre">4}]</span></code> would be:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>* Length: 4, Null count: 1
+* Null bitmap buffer:
+
+ |Byte 0 (validity bitmap) | Bytes 1-63 |
+ |-------------------------|-----------------------|
+ | 00001011 | 0 (padding) |
+
+* Children arrays:
+ * field-0 array (`List<char>`):
+ * Length: 4, Null count: 2
+ * Null bitmap buffer:
+
+ | Byte 0 (validity bitmap) | Bytes 1-63 |
+ |--------------------------|-----------------------|
+ | 00001001 | 0 (padding) |
+
+ * Offsets buffer:
+
+ | Bytes 0-19 |
+ |----------------|
+ | 0, 3, 3, 3, 7 |
+
+ * Values array:
+ * Length: 7, Null count: 0
+ * Null bitmap buffer: Not required
+
+ * Value buffer:
+
+ | Bytes 0-6 |
+ |----------------|
+ | joemark |
+
+ * field-1 array (int32 array):
+ * Length: 4, Null count: 1
+ * Null bitmap buffer:
+
+ | Byte 0 (validity bitmap) | Bytes 1-63 |
+ |--------------------------|-----------------------|
+ | 00001011 | 0 (padding) |
+
+ * Value Buffer:
+
+ |Bytes 0-3 | Bytes 4-7 | Bytes 8-11 | Bytes 12-15 | Bytes 16-63 |
+ |------------|-------------|-------------|-------------|-------------|
+ | 1 | 2 | unspecified | 4 | unspecified |
+</pre></div>
+</div>
+<p>While a struct does not have physical storage for each of its semantic slots
+(i.e. each scalar C-like struct), an entire struct slot can be set to null via
+the null bitmap. Any of the child field arrays can have null values according
+to their respective independent null bitmaps.
+This implies that for a particular struct slot the null bitmap for the struct
+array might indicate a null slot when one or more of its child arrays has a
+non-null value in their corresponding slot. When reading the struct array the
+parent null bitmap is authoritative.
+This is illustrated in the example above, the child arrays have valid entries
+for the null struct but are ‘hidden’ from the consumer by the parent array’s
+null bitmap. However, when treated independently corresponding
+values of the children array will be non-null.</p>
+</div>
+</div>
+<div class="section" id="dense-union-type">
+<h2>Dense union type<a class="headerlink" href="#dense-union-type" title="Permalink to this headline">¶</a></h2>
+<p>A dense union is semantically similar to a struct, and contains an ordered
+sequence of relative types. While a struct contains multiple arrays, a union is
+semantically a single array in which each slot can have a different type.</p>
+<p>The union types may be named, but like structs this will be a matter of the
+metadata and will not affect the physical memory layout.</p>
+<p>We define two distinct union types that are optimized for different use
+cases. This first, the dense union, represents a mixed-type array with 5 bytes
+of overhead for each value. Its physical layout is as follows:</p>
+<ul class="simple">
+<li>One child array for each relative type</li>
+<li>Types buffer: A buffer of 8-bit signed integers, enumerated from 0 corresponding
+to each type. A union with more then 127 possible types can be modeled as a
+union of unions.</li>
+<li>Offsets buffer: A buffer of signed int32 values indicating the relative offset
+into the respective child array for the type in a given slot. The respective
+offsets for each child value array must be in order / increasing.</li>
+</ul>
+<p>Critically, the dense union allows for minimal overhead in the ubiquitous
+union-of-structs with non-overlapping-fields use case (<code class="docutils literal notranslate"><span class="pre">Union<s1:</span> <span class="pre">Struct1,</span> <span class="pre">s2:</span>
+<span class="pre">Struct2,</span> <span class="pre">s3:</span> <span class="pre">Struct3,</span> <span class="pre">...></span></code>)</p>
+<div class="section" id="example-layout-dense-union">
+<h3>Example Layout: Dense union<a class="headerlink" href="#example-layout-dense-union" title="Permalink to this headline">¶</a></h3>
+<p>An example layout for logical union of:
+<code class="docutils literal notranslate"><span class="pre">Union<f:</span> <span class="pre">float,</span> <span class="pre">i:</span> <span class="pre">int32></span></code> having the values:
+<code class="docutils literal notranslate"><span class="pre">[{f=1.2},</span> <span class="pre">null,</span> <span class="pre">{f=3.4},</span> <span class="pre">{i=5}]</span></code>:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">4</span><span class="p">,</span> <span class="n">Null</span> <span class="n">count</span><span class="p">:</span> <span class="mi">1</span>
+<span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span>
+ <span class="o">|</span><span class="n">Byte</span> <span class="mi">0</span> <span class="p">(</span><span class="n">validity</span> <span class="n">bitmap</span><span class="p">)</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">1</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|-------------------------|-----------------------|</span>
+ <span class="o">|</span><span class="mi">00001101</span> <span class="o">|</span> <span class="mi">0</span> <span class="p">(</span><span class="n">padding</span><span class="p">)</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Types</span> <span class="n">buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Byte</span> <span class="mi">0</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">1</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">2</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|---------|-------------|----------|----------|-------------|</span>
+ <span class="o">|</span> <span class="mi">0</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span> <span class="mi">0</span> <span class="o">|</span> <span class="mi">1</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Offset</span> <span class="n">buffer</span><span class="p">:</span>
+
+ <span class="o">|</span><span class="n">Byte</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">4</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">8</span><span class="o">-</span><span class="mi">11</span> <span class="o">|</span> <span class="n">Byte</span> <span class="mi">12</span><span class="o">-</span><span class="mi">15</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">16</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|---------|-------------|-----------|------------|-------------|</span>
+ <span class="o">|</span> <span class="mi">0</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span> <span class="mi">1</span> <span class="o">|</span> <span class="mi">0</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+
+<span class="o">*</span> <span class="n">Children</span> <span class="n">arrays</span><span class="p">:</span>
+ <span class="o">*</span> <span class="n">Field</span><span class="o">-</span><span class="mi">0</span> <span class="n">array</span> <span class="p">(</span><span class="n">f</span><span class="p">:</span> <span class="nb">float</span><span class="p">):</span>
+ <span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="n">nulls</span><span class="p">:</span> <span class="mi">0</span>
+ <span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span> <span class="n">Not</span> <span class="n">required</span>
+
+ <span class="o">*</span> <span class="n">Value</span> <span class="n">Buffer</span><span class="p">:</span>
+
+ <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">7</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">8</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|-----------|-------------|</span>
+ <span class="o">|</span> <span class="mf">1.2</span><span class="p">,</span> <span class="mf">3.4</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+
+
+ <span class="o">*</span> <span class="n">Field</span><span class="o">-</span><span class="mi">1</span> <span class="n">array</span> <span class="p">(</span><span class="n">i</span><span class="p">:</span> <span class="n">int32</span><span class="p">):</span>
+ <span class="o">*</span> <span class="n">Length</span><span class="p">:</span> <span class="mi">1</span><span class="p">,</span> <span class="n">nulls</span><span class="p">:</span> <span class="mi">0</span>
+ <span class="o">*</span> <span class="n">Null</span> <span class="n">bitmap</span> <span class="n">buffer</span><span class="p">:</span> <span class="n">Not</span> <span class="n">required</span>
+
+ <span class="o">*</span> <span class="n">Value</span> <span class="n">Buffer</span><span class="p">:</span>
+
+ <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">0</span><span class="o">-</span><span class="mi">3</span> <span class="o">|</span> <span class="n">Bytes</span> <span class="mi">4</span><span class="o">-</span><span class="mi">63</span> <span class="o">|</span>
+ <span class="o">|-----------|-------------|</span>
+ <span class="o">|</span> <span class="mi">5</span> <span class="o">|</span> <span class="n">unspecified</span> <span class="o">|</span>
+</pre></div>
+</div>
+</div>
+</div>
+<div class="section" id="sparse-union-type">
+<h2>Sparse union type<a class="headerlink" href="#sparse-union-type" title="Permalink to this headline">¶</a></h2>
+<p>A sparse union has the same structure as a dense union, with the omission of
+the offsets array. In this case, the child arrays are each equal in length to
+the length of the union.</p>
+<p>While a sparse union may use significantly more space compared with a dense
+union, it has some advantages that may be desirable in certain use cases:</p>
+<ul class="simple">
+<li>A sparse union is more amenable to vectorized expression evaluation in some use cases.</li>
+<li>Equal-length arrays can be interpreted as a union by only defining the types array.</li>
+</ul>
+<div class="section" id="example-layout-sparseunion-u0-int32-u1-float-u2-list-char">
+<h3>Example layout: <code class="docutils literal notranslate"><span class="pre">SparseUnion<u0:</span> <span class="pre">Int32,</span> <span class="pre">u1:</span> <span class="pre">Float,</span> <span class="pre">u2:</span> <span class="pre">List<Char>></span></code><a class="headerlink" href="#example-layout-sparseunion-u0-int32-u1-float-u2-list-char" title="Permalink to this headline">¶</a></h3>
+<p>For the union array:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[{</span><span class="n">u0</span><span class="o">=</span><span class="mi">5</span><span class="p">},</span> <span class="p">{</span><span class="n">u1</span><span class="o">=</span><span class="mf">1.2</span><span class="p">},</span> <span class="p">{</span><span class="n">u2</span><span class="o">=</span><span class="s1">'joe'</span><span class="p">},</span> <span class="p">{</span><span class="n">u1</span><span class="o">=</span><span class="mf">3.4</span><span class="p">},</span> <span class="p">{</span><span class="n">u0</span><span class="o">=</span><span class="mi">4</span><span class="p">},</span> <span class="p">{</span><span class="n">u2</span><span class="o">=</span><span class="s1">'mark'</span><span class="p">}]</span>
+</pre></div>
+</div>
+<p>will have the following layout:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>* Length: 6, Null count: 0
+* Null bitmap buffer: Not required
+
+* Types buffer:
+
+ | Byte 0 | Byte 1 | Byte 2 | Byte 3 | Byte 4 | Byte 5 | Bytes 6-63 |
+ |------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
+ | 0 | 1 | 2 | 1 | 0 | 2 | unspecified (padding) |
+
+* Children arrays:
+
+ * u0 (Int32):
+ * Length: 6, Null count: 4
+ * Null bitmap buffer:
+
+ |Byte 0 (validity bitmap) | Bytes 1-63 |
+ |-------------------------|-----------------------|
+ |00010001 | 0 (padding) |
+
+ * Value buffer:
+
+ |Bytes 0-3 | Bytes 4-7 | Bytes 8-11 | Bytes 12-15 | Bytes 16-19 | Bytes 20-23 | Bytes 24-63 |
+ |------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
+ | 5 | unspecified | unspecified | unspecified | 4 | unspecified | unspecified (padding) |
+
+ * u1 (float):
+ * Length: 6, Null count: 4
+ * Null bitmap buffer:
+
+ |Byte 0 (validity bitmap) | Bytes 1-63 |
+ |-------------------------|-----------------------|
+ | 00001010 | 0 (padding) |
+
+ * Value buffer:
+
+ |Bytes 0-3 | Bytes 4-7 | Bytes 8-11 | Bytes 12-15 | Bytes 16-19 | Bytes 20-23 | Bytes 24-63 |
+ |-------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
+ | unspecified | 1.2 | unspecified | 3.4 | unspecified | unspecified | unspecified (padding) |
+
+ * u2 (`List<char>`)
+ * Length: 6, Null count: 4
+ * Null bitmap buffer:
+
+ | Byte 0 (validity bitmap) | Bytes 1-63 |
+ |--------------------------|-----------------------|
+ | 00100100 | 0 (padding) |
+
+ * Offsets buffer (int32)
+
+ | Bytes 0-3 | Bytes 4-7 | Bytes 8-11 | Bytes 12-15 | Bytes 16-19 | Bytes 20-23 | Bytes 24-27 | Bytes 28-63 |
+ |------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|
+ | 0 | 0 | 0 | 3 | 3 | 3 | 7 | unspecified |
+
+ * Values array (char array):
+ * Length: 7, Null count: 0
+ * Null bitmap buffer: Not required
+
+ | Bytes 0-7 | Bytes 8-63 |
+ |------------|-----------------------|
+ | joemark | unspecified (padding) |
+</pre></div>
+</div>
+<p>Note that nested types in a sparse union must be internally consistent
+(e.g. see the List in the diagram), i.e. random access at any index j
+on any child array will not cause an error.
+In other words, the array for the nested type must be valid if it is
+reinterpreted as a non-nested array.</p>
+<p>Similar to structs, a particular child array may have a non-null slot
+even if the null bitmap of the parent union array indicates the slot is
+null. Additionally, a child array may have a non-null slot even if
+the types array indicates that a slot contains a different type at the index.</p>
+</div>
+</div>
+<div class="section" id="dictionary-encoding">
+<h2>Dictionary encoding<a class="headerlink" href="#dictionary-encoding" title="Permalink to this headline">¶</a></h2>
+<p>When a field is dictionary encoded, the values are represented by an array of
+Int32 representing the index of the value in the dictionary. The Dictionary is
+received as one or more DictionaryBatches with the id referenced by a
+dictionary attribute defined in the metadata (Message.fbs) in the Field
+table. The dictionary has the same layout as the type of the field would
+dictate. Each entry in the dictionary can be accessed by its index in the
+DictionaryBatches. When a Schema references a Dictionary id, it must send at
+least one DictionaryBatch for this id.</p>
+<p>As an example, you could have the following data:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="nb">type</span><span class="p">:</span> <span class="n">List</span><span class="o"><</span><span class="n">String</span><span class="o">></span>
+
+<span class="p">[</span>
+ <span class="p">[</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">]</span>
+<span class="p">]</span>
+</pre></div>
+</div>
+<p>In dictionary-encoded form, this could appear as:</p>
+<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="n">data</span> <span class="n">List</span><span class="o"><</span><span class="n">String</span><span class="o">></span> <span class="p">(</span><span class="n">dictionary</span><span class="o">-</span><span class="n">encoded</span><span class="p">,</span> <span class="n">dictionary</span> <span class="nb">id</span> <span class="n">i</span><span class="p">)</span>
+<span class="n">indices</span><span class="p">:</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span><span class="p">]</span>
+
+<span class="n">dictionary</span> <span class="n">i</span>
+
+<span class="nb">type</span><span class="p">:</span> <span class="n">List</span><span class="o"><</span><span class="n">String</span><span class="o">></span>
+
+<span class="p">[</span>
+ <span class="p">[</span><span class="s1">'a'</span><span class="p">,</span> <span class="s1">'b'</span><span class="p">],</span>
+ <span class="p">[</span><span class="s1">'c'</span><span class="p">,</span> <span class="s1">'d'</span><span class="p">,</span> <span class="s1">'e'</span><span class="p">],</span>
+<span class="p">]</span>
+</pre></div>
+</div>
+</div>
+<div class="section" id="references">
+<h2>References<a class="headerlink" href="#references" title="Permalink to this headline">¶</a></h2>
+<p>Apache Drill Documentation - <a class="reference external" href="https://drill.apache.org/docs/value-vectors/">Value Vectors</a></p>
+</div>
+</div>
+
+
+ </div>
+
+ </div>
+ <footer>
+
+ <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
+
+ <a href="Metadata.html" class="btn btn-neutral float-right" title="Metadata: Logical types, schemas, data headers" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
+
+
+ <a href="Guidelines.html" class="btn btn-neutral" title="Implementation guidelines" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
+
+ </div>
+
+
+ <hr/>
+
+ <div role="contentinfo">
+ <p>
+ © Copyright 2016-2018 Apache Software Foundation
+
+ </p>
+ </div>
+ Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
+
+</footer>
+
+ </div>
+ </div>
+
+ </section>
+
+ </div>
+
+
+
+
+
+
+
+ <script type="text/javascript" id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
+ <script type="text/javascript" src="../_static/jquery.js"></script>
+ <script type="text/javascript" src="../_static/underscore.js"></script>
+ <script type="text/javascript" src="../_static/doctools.js"></script>
+
+
+
+
+ <script type="text/javascript" src="../_static/js/theme.js"></script>
+
+ <script type="text/javascript">
+ jQuery(function () {
+ SphinxRtdTheme.Navigation.enable(true);
+ });
+ </script>
+<script async src="https://www.googletagmanager.com/gtag/js?id=UA-107500873-1"></script>
+<script>
+ window.dataLayer = window.dataLayer || [];
+ function gtag(){dataLayer.push(arguments);}
+ gtag('js', new Date());
+
+ gtag('config', 'UA-107500873-1');
+</script>
+
+
+</body>
+</html>
\ No newline at end of file