v2 optimization and feature ideas

[nyurik]

Here we will try to keep track of all MLT optimization ideas for v2.
🛑 Add one idea per comment. Discuss the idea using the reply box, not the add a comment box.

See also MLT v2 specification proposal #1322 based on these ideas.
See also MLT 3D proposal #1182 for 3D-specific discussion

Size optimizations

• duplicate metadata sizes, e.g. count of features + RLE count + fastpfor count in the header
• float optimization - ALP (DuckDB?)
• make it possible to share presence columns between unrelated properties and/or ID field
• do not include stream Length(Geometries) when empty even if tessellation is enabled

Performance

• use SIMD version of the FastPFOR codec
• use little-endian format for FastPFOR

Other Changes

• merge metadata with data
• FastPFOR actually uses two codecs - block-based FastPFOR128 for evenly-divided block data, followed by VariableByte encoding for the remainder. The VariableByte remainder is 1) not very efficient, and 2) reverses the meaning of MSB (Most Significant Bit) compared with protobuf spec - making encoding a bit more convoluted. We may want to consider Stream VByte or similar SIMD-optimized approaches.

New Features

• per-vertex "M-values"
• lists of values (scalars, strings?, lists of lists?)

TBD

• Make geometry optional #312 - not clear if this is needed, and if so, what it would look like

[CommanderStorm]

An alternative to the hard to maintain FastPFOR code might be fastlanes (paper, rust port).

@mactrem
Curious: Did you consider/benchmark this?

[mactrem]

Yes, this is an interesting paper that I’ve read and considered for future work. However, since the reported results of FastPfor were already quite strong, I did not perform additional benchmarking, mainly because it would require porting the implementation to Java for my setup.

One reason I did not prioritize FastLanes is that our primary concern was data size. Techniques like those used in FastLanes (e.g., resolving data dependencies in delta encoding) can lead to larger deltas, especially for ordered sequences such as coordinate data in line strings.

Additionally, a key insight during the design of MLT is that a vector tile format must remain compatible across a wide range of platforms. Support for advanced SIMD remains limited on mobile devices and in browser environments (e.g., WebAssembly currently supports 128-bit SIMD, with potential extensions in the future).

[CommanderStorm]

the good thing about fastlates is that it mostly (if not all) relies on autovectorisation, so should not cause an issue there.

Data size likely being larger is a non starter though.

[TimSylvester]

Re: FastPFOR, the Java encoder uses block size 256, and apparently it should really be 128, so v2 should switch and/or have an optional way to specify a block size, assuming it's still being used.

[TimSylvester]

Also on the FastPFOR front, I think the encoded stream should not be byte-swapped, as most supported architectures are little-endian.

[nyurik]

• I also noticed the LE-BE byte swap but forgot to add it, thx for remanding! Added.
• I am not certain we want to overcomplicate it with multiple block sizes. I guess page-size is purely decoding perf optimization rather than the format.
• Per @mactrem some CPUs and WASM do not support 256, falling back to 128 instructions?

[TimSylvester]

I suspect the support issue is only relevant with SIMD

[TimSylvester]

In a previous discussion we landed on "list" as a good, simple property type to prove out complex type support beyond MVT limitations.

[nyurik]

What types can lists hold? scalars, strings, other lists? What would be the binary representation?

[TimSylvester]

I don't know, I wasn't able to find any spec. I would guess treat it like JSON and allow any of the other supported types. But homogenous lists could be encoded more efficiently like columns.

[TimSylvester]

The Overture data seems to use lists for two things: lists of structs and pairs. I don't see any longer lists of primitives, but I'm not seeing all the data. Mostly, list/struct seems to be basically equivalent to JSON having [] and {} at the top level, and both need to support heterogeneous nested collections.

speed_limits : [{max_speed={unit=mph, value=20}, between=[0.0, 0.080302388]}, ...

width_rules : [{value=0.64, between=[0.0, 0.034721275]}, {value=0.98, between=[0.034721275, 0.046723026]}, ...

Internally, that seems to be done with indexes into a table of all the unique keys and values. Similarly, we might have a stream/column per data type used (ints, doubles, strings, ...), and a stream of indexes into the combined set of those values. I can see how a hierarchical data structure could be encoded into a stream of ints with a couple of special values for framing, similar to protobuf.

[TimSylvester]

@mactrem Have you considered how to encode nested data structures of mixed types?

[mactrem]

@TimSylvester yes, the foundation is a length/presence stream pair-based encoding which we already using for the other nested types like geometry. For describing the structure of the neseted types i used in my POC the external proto schema see https://github.com/mactrem/mlt-evaluation/blob/8158fe677ede969adce4e4fd8a75757ad71096af/spec/schema/mlt_tileset_metadata.proto and tested it for example with Overture Maps data

[TimSylvester]

We're currently using "struct" for column-mapping complex type, but that's easily confused with nested/structured property values. Perhaps we should change the name in the code, without changing anything in the format, of course.

[nyurik]

In rust we have been calling these Shared Dictionaries -- its an implementation change, so OK to modify for v1 as well, and possibly update the spec for clarity

[CommanderStorm]

Segment dictionaries for multi-value strings

values like a|b|c (tile-join, OSM ;) are lists crammed into strings.
The string dictionary only dedups whole values, so the parts get stored over and over.
FSST barely helps (8-byte symbols, 255 entries).

As an Example from an OSM extract:
one z8 tile has 2907 unique relation_symbol_urls values => 781KB of corpus, but only ~1000 distinct segments = 71KB.

Proposed alternative:
a second dictionary of segments.
Each dictionary value is a list of segment indices (2 extra streams: per-value counts + flattened indices).
This means we can let this doubles as the storage for the real list<string> type (elements = segments, separators disappear), and can also sit behind plain string cokls for MVT data where re-typing to arrays would change what styles see.

I Prototyped this in the Rust encoder, competing per column against plain/dict/FSST:
The osm-wogibtes archive drops from 1.23x to 1.05x of the gzipped MVT input, encode time +35%, decode is one extra concat pass over the dictionary.

We will have to see if this is something we still want when we get to lists and structs.