Skip to main content

Dynamic Fields for Quadtree Storage: How Sui's Object Model Enabled Our Spatial Hierarchy

· 7 min read
merca.earth
Team

A spatial index is, at first glance, just a mapping: coordinates go in, parcel IDs come out. The data structure is straightforward. On testnet, though, grid cell dynamic fields consumed 68% of per-parcel insertion cost. Storage was 94–96% of total transaction cost. The data structure was fine. The storage cost wasn't.

Why Mappings Don't Scale​

On EVM, a spatial index looks like nested mappings: mapping(uint => mapping(uint => address[])). Writing a new slot costs an SSTORE opcode — 20,000 gas. A parcel covering K cells writes K slots. A parcel spanning 36 grid cells pays 36 SSTOREs on the way in and 36 on the way out.

On Solana, the natural structure is a single account. The entire account loads into memory per transaction — there's no per-key access. A growing index eventually hits the 10 MB account size limit. You can't load one cell without loading all of them.

Both models pay for the full structure when you only need a slice.

Within Sui: Four Storage Models​

Static struct fields are declared at compile time. An index with 10,000 cells would need 10,000 declared fields — a compile-time impossibility.

Wrapped objects store child objects inline inside a parent. When the parent loads, all children load with it. An index with 10,000 entries forces loading all 10,000 on every registration, even if you only touch one cell. Cost grows with the collection, not the operation.

vector<T> is variable-length but deserializes entirely from the parent object. Read one cell, pay for deserializing all of them. Same scaling problem as wrapped objects, different syntax.

Dynamic fields store each entry as a separate child object, independent of the parent. Loading one entry doesn't load others. The parent has no size limit. You pay only for the keys you touch.

Sui's Table<K, V> is a typed wrapper around dynamic fields — each entry lives in its own storage slot, loaded only when accessed by key.

For a spatial index, this property is decisive. Whether the index holds 10 parcels or 10 million, registering one new parcel touches the same number of dynamic field slots — the cost of a write is independent of the collection's size.

The Index: One Shared Object, Unbounded Growth​

The Index is a shared object — the sole canonical record of all registered parcels on merca.earth. Every registration writes to it. It holds two Table fields that grow with every new parcel:

// onchain/protocol/sources/core/index.move, lines 68-82
public struct Index has key, store {
    id: object::UID,
    /// Maps depth-prefixed Morton keys to polygon IDs stored at that cell.
    cells: Table<u64, vector<ID>>,
    /// Maps polygon IDs to Polygon objects.
    polygons: Table<ID, Polygon>,
    /// Size of the finest-level cell in coordinate units.
    cell_size: u64,
    /// Maximum quadtree depth (finest level). World covers 2^max_depth cells.
    max_depth: u8,
    /// Total registered parcels.
    count: u64,
    config: Config,
    authorized_caps: VecSet<ID>,
}

Two Tables. cells maps spatial regions to parcel IDs. polygons stores geometry. Both grow with every registration. A transaction that registers one parcel touches exactly one cells entry and creates one polygons entry — two dynamic field operations, regardless of how many parcels already exist.

The Index has no upper bound on entries. Because Table stores each entry as a dynamic field rather than inline in the object, the Index can grow to hold every parcel on Earth without hitting Sui's object size limits.

(We covered the Index in our previous post.)

Depth-Prefixed Morton Keys: Unique Addresses Across Depths​

Morton codes map two-dimensional coordinates onto a single integer by interleaving the bits of X and Y. Spatially close cells get numerically close codes. We'll walk through the bit-interleaving mechanics in a future post — what matters here is the depth prefix.

// onchain/protocol/sources/math/morton.move, lines 52-60
public fun depth_prefix(morton_code: u64, depth: u8): u64 {
    assert!(depth <= MAX_DEPTH, EDepthTooLarge);
    if (depth == 0) {
        return 1
    };
    let d2: u8 = depth * 2;
    let sentinel = 1u64 << d2;
    sentinel | (morton_code & (sentinel - 1))
}

A raw Morton code is ambiguous — the same integer could address a cell at depth 3 or depth 7. The depth prefix resolves this with a sentinel bit: depth 0 produces key 1 (the root), depth 1 produces keys 4–7 (four quadrants), depth 2 produces keys 16–31 (sixteen cells). Every cell at every depth gets a unique integer.

The entire quadtree fits in one flat Table<u64, ...>. A single integer addresses any cell at any depth — no nested objects, no tree pointers.

Natural Depth: O(1) Placement​

Every parcel lands in exactly one cell. The natural_depth function finds it:

// onchain/protocol/sources/core/index.move, lines 834-853
public(package) fun natural_depth(
    min_x: u32,
    min_y: u32,
    max_x: u32,
    max_y: u32,
    max_depth: u8,
): u8 {
    let mut depth = max_depth;
    while (depth > 0) {
        let shift: u8 = max_depth - depth;
        if (
            (min_x >> shift) == (max_x >> shift)
                && (min_y >> shift) == (max_y >> shift)
        ) {
            return depth
        };
        depth = depth - 1;
    };
    0
}

At each depth, the algorithm shifts the bounding box corners to that depth's resolution. If both corners land in the same cell, the parcel fits there. A city block lands deep in the tree; a continental territory lands near the root. One pass finds the right level.

Natural depth makes both registration and removal O(1) in dynamic field operations. Insert writes one entry; remove deletes one entry. The parcel's geographic size doesn't change the operation count.

Every parcel uses exactly one cell, regardless of geographic size. One table::add call per registration. A 10 km × 10 km farm costs the same storage gas as a 10 m × 10 m house.

The Numbers: Cost Formula and Reduction​

The legacy grid stored each parcel in every cell it touched — up to 36. Testnet measurements produced this insertion cost formula:

$$ \text{Cost}_{\text{insert}} = 1\text{M} + 2.7\text{M} \times K + 3\text{M} + 0.5\text{M} \times m \quad (\text{MIST}) $$

K is cells covered, m is convex parts. Grid cell entries were the dominant term: 68% of insertion cost.

Under the legacy grid, a parcel spanning 36 cells paid 36 × 2.7M = 97.2M MIST in cell storage alone. Under the quadtree, the same parcel uses one cell. 2.7M MIST. A 97% reduction. The 2.7M × K term went from a variable scaling with parcel size to a constant.

Multi-Resolution Hierarchy On-Chain​

Google S2 solved multi-resolution spatial indexing with Hilbert curves — float projections, trigonometric math, none of it possible inside a Move smart contract. The depth-prefixed Morton key achieves the same structural result with pure integer bit manipulation: a unique key per cell per depth, computable in a handful of bit operations.

A flat table of integers replaces a recursive tree of objects. Dynamic fields make that table unbounded — an on-chain spatial index that scales with planet-sized data, not with the gas budget.

The data structure is still straightforward. Now the storage cost is too.