Implementation Guide

This page gives guidance for building an encoder or a decoder. The wire format is defined by the v1 and v2 specifications, not here.

Choosing an Encoding¶

Encodings cascade: the integer codes produced by dictionary encoding are themselves compressed with an integer encoding. A brute-force search over every combination is too costly. Use the selection strategy from the BTRBlocks paper:

• Calculate data metrics to exclude unsuitable encodings early (e.g., exclude RLE if the average run length is less than 2).
• Use a sampling-based algorithm: randomly select parts of the data totaling ~1% of the full dataset and apply the candidate encodings left after the first step. Choose the scheme that produces the smallest output.

Compare stored bytes, not an estimate. Do not assume a later gzip pass changes which candidate wins.

The v1 encoding pool was selected for compression ratio and decoding speed on the OpenMapTiles and Bing Maps tilesets:

SIMD-FastPFOR usually gives smaller output and faster decoding than Varint. Varint is simpler and can come out smaller once a heavyweight compressor like gzip runs over the tile.

Sort Order¶

Choosing which column to sort features by can shrink a layer considerably, since sorting lengthens runs and shrinks deltas. Testing every column of every layer is too costly, so the same sampling applies.

In-Memory Format¶

The record-oriented, array-of-structures in-memory model used by libraries that process Mapbox Vector Tiles incurs considerable overhead. It comes from creating many small objects, which increases memory allocation load and strains garbage collectors in browsers.

MLT uses a columnar memory layout (data-oriented design) for its in-memory format to overcome these issues. This approach improves cache utilization for subsequent data access and enables the use of fast SIMD instructions. The MLT in-memory format incorporates ideas from analytical in-memory formats like Apache Arrow, Velox, and the DuckDB execution format, tailored for visualization use cases. It is also designed for future parallel processing on the GPU within compute shaders.

The main design goals are:

• Define a platform-agnostic representation to avoid costly materialization, especially for strings.
• Maximize CPU throughput by optimizing memory layout for cache locality and SIMD instructions.
• Allow random (preferably constant-time) access to all data for parallel processing on GPUs (compute shaders).
• Provide compressed data structures that can be processed directly without full decoding.
• Provide tile geometries in a representation that can be loaded into GPU buffers with minimal additional processing.

Data is stored in contiguous memory buffers called vectors, accompanied by metadata and an optional null bitmap. An auxiliary offset buffer enables random access to variable-sized data types like strings or lists. The supported vector types are:

• Flat Vectors
• Constant Vectors
• Sequence Vectors
• Dictionary Vectors
• FSST Dictionary Vectors
• Shared Dictionary Vectors
• Run-End Encoded (REE) Vectors

Using a compressed vector where possible makes the conversion from storage to in-memory format essentially a zero-copy operation.

Following Apache Arrow's approach and the Intel performance guide, decoders should allocate memory at 64-byte-aligned addresses where possible.