DuckDB Extension
Lindel
Encode coordinates, dates and lat/lon as Hilbert or Morton keys in DuckDB. Sort rows by a space-filling curve so multi-column range queries skip more data.
On this page
Sample data for the examples
Each browser example starts with these sample tables; sample files are shared across examples on this page. Run this setup first when trying the examples in your own DuckDB session.
-- Fixtures for the lindel cookbook + technical-details + functions.json
-- examples. Small, deterministic, idempotent — re-running is a no-op.
-- A generic source table with every column the docs reach for: spatial
-- (lat, lon, alt), temporal (time as epoch seconds), and a categorical
-- id (symbol_id) for the Morton time-series example.
CREATE OR REPLACE TABLE source AS
SELECT
(40 + (i % 10) * 0.1)::DOUBLE AS lat,
(-74 + (i % 10) * 0.1)::DOUBLE AS lon,
(100 + i)::INTEGER AS alt,
(1700000000 + i * 60)::INTEGER AS time,
(i % 8)::INTEGER AS symbol_id
FROM range(0, 16) t(i);
-- Flight history fixture: same schema shape as the cookbook 4D example.
CREATE OR REPLACE TABLE flights AS
SELECT
(30 + (i % 12))::INTEGER AS lat,
(-100 + (i % 12))::INTEGER AS lon,
(10000 + i * 100)::INTEGER AS alt,
(1700000000 + i * 60)::INTEGER AS time
FROM range(0, 16) t(i);
-- 3D points fixture used by technical-details.
CREATE OR REPLACE TABLE points AS
SELECT
(i % 8)::INTEGER AS x,
((i * 3) % 8)::INTEGER AS y,
((i * 5) % 8)::INTEGER AS z
FROM range(0, 16) t(i);
Arrange rows for queries across several dimensions
Lindel maps coordinates to one integer using a Hilbert or Morton space-filling curve. Sorting by that integer places nearby points close together in the stored row order.
Use it when writing Parquet or loading tables for queries that filter several dimensions, such as location and time. A curve ordering makes row-group statistics more selective, so readers skip more data. Lindel also quantizes latitude/longitude and other bounded values onto a grid, accepts dates, timestamps and decimals as coordinates, decodes keys by type, and turns a box into key ranges for key-only stores.
Example
Sort points by a Hilbert key
A fixed-size two-element array becomes one sortable integer. All six sample points are included.
Tested with DuckDB 2.0.0. Browser examples use Haybarn-Wasm 2.0.0-rc12.
SET allow_extension_repositories = 'allowed';
CREATE EXTENSION REPOSITORY IF NOT EXISTS query_farm
WITH PREFIX 'https://duckdb-extensions.query.farm';
INSTALL lindel FROM query_farm;
LOAD lindel FROM query_farm;
SELECT x, y, hilbert_encode([x, y]::UINTEGER[2]) AS hilbert
FROM (VALUES (3, 5), (1, 1), (7, 0), (2, 6), (5, 3), (0, 4)) AS points(x, y)
ORDER BY hilbert;
SET allow_extension_repositories = 'allowed';
CREATE EXTENSION REPOSITORY IF NOT EXISTS query_farm
WITH PREFIX 'https://haybarn-extensions.query.farm';
INSTALL lindel FROM query_farm;
LOAD lindel FROM query_farm;
SELECT x, y, hilbert_encode([x, y]::UINTEGER[2]) AS hilbert
FROM (VALUES (3, 5), (1, 1), (7, 0), (2, 6), (5, 3), (0, 4)) AS points(x, y)
ORDER BY hilbert;
INSTALL lindel FROM community;
LOAD lindel;
SELECT x, y, hilbert_encode([x, y]::UINTEGER[2]) AS hilbert
FROM (VALUES (3, 5), (1, 1), (7, 0), (2, 6), (5, 3), (0, 4)) AS points(x, y)
ORDER BY hilbert;
Expected result
| x | y | hilbert |
|---|---|---|
| 1 | 1 | 2 |
| 7 | 0 | 21 |
| 5 | 3 | 28 |
| 2 | 6 | 50 |
| 3 | 5 | 52 |
| 0 | 4 | 58 |
The key provides an ordering, not a spatial index. Any benefit to Parquet range queries depends on how you write the file and filter it later.
Common tasks
Deep Dive
Technical Details
What you can do with one query
Replace a multi-column ORDER BY with one space-filling-curve sort key:
SELECT x, y, z, hilbert_encode([x, y, z]::UINTEGER[3]) AS hilbertFROM pointsORDER BY hilbert;Use that ordering when writing Parquet or loading a table so that nearby coordinates end up in the same row groups. Queries that filter several dimensions can then skip more data using min/max statistics. Sorting does not guarantee that every nearby pair becomes adjacent, or that every row group has tight bounds on every column.
Signed integers, floating-point numbers, dates, timestamps and decimals are mapped to order-preserving bits before encoding. A box that crosses zero stays a box on the curve, and the key of a one-dimensional input sorts exactly like the input. Decoding a signed key needs the matching signedness: use return_unsigned = false, or the typed form hilbert_decode(key, 'INTEGER[2]').
Hilbert vs Morton
Both hilbert_encode and morton_encode take coordinates and return one unsigned integer.
- Hilbert follows a space-filling curve with no long jumps between consecutive positions on its grid. It is a useful starting point for locality-oriented sorting.
- Morton / Z-order interleaves the coordinate bits. Its simpler mapping has jumps at quadrant boundaries.
Compare the resulting file layout and encoding cost on your own data. Neither curve guarantees better pruning for every distribution or query.
Type coverage and output width
Coordinates can be passed as a fixed-size array, hilbert_encode([x, y]::INTEGER[2]), or as two or more separate arguments, hilbert_encode(x, y). Separate arguments are cast to their common type, and a NULL argument gives a NULL key. Array elements cannot be NULL.
| Coordinate width | Types | Dimensions |
|---|---|---|
| 8 bits | TINYINT, UTINYINT, BOOLEAN, ENUM with up to 256 values |
1–16 |
| 16 bits | SMALLINT, USMALLINT, DECIMAL(1–4, s), ENUM with up to 65,536 values |
1–8 |
| 32 bits | INTEGER, UINTEGER, FLOAT, DATE, DECIMAL(5–9, s), larger ENUM types |
1–4 |
| 64 bits | BIGINT, UBIGINT, DOUBLE, TIME, TIMESTAMP (all precisions and WITH TIME ZONE), DECIMAL(10–18, s) |
1–2 |
HUGEINT, UHUGEINT and DECIMAL with more than 18 digits are not supported. The result is the smallest unsigned integer type that fits coordinate width × number of dimensions, up to 128 bits:
| Input | Total bits | Output type |
|---|---|---|
UTINYINT[2] |
16 | USMALLINT |
UINTEGER[2] |
64 | UBIGINT |
UINTEGER[3] |
96 | UHUGEINT |
DOUBLE[2] |
128 | UHUGEINT |
DATE, DATE |
64 | UBIGINT |
Cast arrays explicitly: [10, 20] is a LIST; [10, 20]::UINTEGER[2] is a fixed-size ARRAY.
Choose coordinate units and precision deliberately. A degree of latitude, a meter of altitude and a second of time are different measures, and Lindel does not decide their relative importance for you. Wide types also spread keys thinly: two DOUBLE coordinates use a 128-bit key even when the data covers a small area. For known value ranges, the bounded functions below give denser keys.
Bounded grids and latitude/longitude
hilbert_encode_bounded quantizes DOUBLE coordinates onto a grid of 2^bits cells per dimension between per-dimension minimum and maximum values, then encodes the cell:
SELECT hilbert_encode_bounded([12.5, 40.25]::DOUBLE[2], [0, 0], [100, 100], 16) AS key;-- 848669286The key is the smallest unsigned type that holds dimensions × bits. Every cell of the grid gets a distinct key from 0 to 2^(dimensions × bits) − 1. Values outside the bounds are clamped to the edge cells, and NaN is an error. hilbert_decode_bounded returns the centre of the key’s cell, which is within half a cell of the original value.
hilbert_encode_latlon is the same encoding with latitude and longitude bounds and 32 bits per axis by default (a UBIGINT key, roughly a centimetre of resolution). Out-of-range coordinates are an error rather than being clamped:
SELECT hilbert_encode_latlon(52.52, 13.405) AS berlin, hilbert_decode_latlon(hilbert_encode_latlon(52.52, 13.405)) AS decoded;-- 13413847537087438956, {'lat': 52.520000010263175, 'lon': 13.40500000398606}The bounded encoders also accept a GEOMETRY value with two-dimensional bounds and encode the centre of its bounding box. A point encodes as itself, and an empty geometry gives NULL.
Because grid keys of different resolutions nest, a key’s ancestor k levels up is key >> (dimensions × k). The keys inside a cell form the contiguous range from key << (dimensions × k) to ((key + 1) << (dimensions × k)) − 1.
Box queries as key ranges
hilbert_ranges is a table function that turns a box into the sorted, disjoint key ranges covering it:
SELECT * FROM hilbert_ranges([2, 3]::UTINYINT[2], [5, 6]::UTINYINT[2]);| lo | hi |
|---|---|
| 9 | 10 |
| 28 | 28 |
| 31 | 35 |
| 45 | 46 |
| 50 | 55 |
The ranges are exact when the max_ranges budget (64 by default) allows it. With a smaller budget, the function merges the closest ranges. The result then covers some keys outside the box, but never misses one inside it. hilbert_ranges_bounded does the same for keys from hilbert_encode_bounded.
These ranges are for systems that store or index only the key: key-value stores, other engines, or files partitioned by key. Inside DuckDB, sort by the key and filter on the original columns. In our benchmark, joining against hilbert_ranges was never faster than a plain coordinate filter on curve-sorted data, and up to 8× slower on large boxes.
Decoding
Decode straight into a named type with hilbert_decode(key, 'TYPE[n]'). The target type sets the coordinate width and the order-preserving transform, so it works for every type the encoders accept:
SELECT hilbert_decode(hilbert_encode(DATE '2024-03-01', DATE '1965-07-04'), 'DATE[2]');-- [2024-03-01, 1965-07-04]A bare type such as 'INTEGER' means one dimension. Keys that are too large for the target type, or that decode to an invalid BOOLEAN or ENUM value, are errors.
The original form takes three trailing arguments: the number of dimensions, whether to return floats, and whether to return unsigned integers:
SELECT hilbert_decode( hilbert_encode([5, 8]::UINTEGER[2]), 2, -- num_elements false, -- return_float true -- return_unsigned);-- [5, 8]For signed integers, use false, false. For floating-point values, use true, false. Preserve the encoded key’s original SQL type, because the decoder uses its width together with the dimension count to determine the coordinate width. If you shifted or quantized coordinates before encoding, decoding returns those transformed coordinates.
Why ordering can help Parquet
Parquet stores per-row-group min/max statistics, and DuckDB keeps the same zone maps for its own tables. For a query such as WHERE lat BETWEEN 40 AND 41 AND lon BETWEEN -74 AND -73, a reader can skip a row group if its statistics rule out either condition. Grouping points by a Hilbert or Morton key makes those ranges more selective across multiple columns.
In our benchmark of 20 million uniformly random points in 100,000-row groups, a small box query overlapped 2 of 200 row groups after Hilbert sorting, compared with all 200 in random order. Query time on Parquet dropped from 20 ms to 8 ms. The improvement depends on coordinate preparation, data distribution, row-group size and query predicates. Measure scanned rows or bytes, query time and file size against your existing layout.
This is a write-time ordering, not a runtime index. Use ORDER BY inside the query passed to COPY. For changing data, sort each rewritten file or batch. Queries still filter on the original columns.
Compared to alternatives
ORDER BY a, bprioritizesa, thenbwithin equal values ofa. It can be a better fit when queries mostly filter the leading column. A curve order balances multiple coordinates.- Partitioning by year or region separates data into files or directories. Curve sorting can complement partitioning by organizing rows inside each partition.
- A spatial index supports a different access pattern. Lindel computes keys and key ranges; it does not create an index.
Reference
Extension Contents
Quick reference to all available functions and settings organized by category.
| Name | Type | Description |
|---|---|---|
|
Hilbert
Hilbert-curve keys, grids and range decomposition. Consecutive Hilbert keys are always neighbouring cells, so sorting by a Hilbert key usually produces tighter row groups than Morton. |
||
| hilbert_decode() | Object type: Scalar function | Recover coordinates from a Hilbert curve key. |
| hilbert_decode_bounded() | Object type: Scalar function | Decode a key from hilbert_encode_bounded with the same bounds and bits into the centre of its grid cell, as a DOUBLE array. |
| hilbert_decode_latlon() | Object type: Scalar function | Decode a key from hilbert_encode_latlon with the same bits (default 32) into the centre of its grid cell, as STRUCT(lat DOUBLE, lon DOUBLE). |
| hilbert_encode() | Object type: Scalar function | Encode coordinates into one unsigned integer using the Hilbert curve. |
| hilbert_encode_bounded() | Object type: Scalar function | Scale each DOUBLE coordinate from [min, max] onto a grid of 2^bits cells and encode the cell with the Hilbert curve. |
| hilbert_encode_latlon() | Object type: Scalar function | Encode a latitude/longitude pair with the Hilbert curve over a grid of 2^bits cells per axis. |
| hilbert_ranges() | Object type: Table function | Table function returning the sorted, disjoint key ranges (lo, hi) of hilbert_encode that cover the box between min_point and max_point. |
| hilbert_ranges_bounded() | Object type: Table function | Table function returning the key ranges (lo, hi) of hilbert_encode_bounded, with the given bounds and bits, that cover the box between min_point and max_point. |
|
Morton (Z-order)
Morton-curve (Z-order) keys, grids and range decomposition. Morton interleaves coordinate bits: cheaper to compute, with jumps at quadrant boundaries. The classic Z-order layout that Delta Lake popularized. |
||
| morton_decode() | Object type: Scalar function | Recover coordinates from a Morton (Z-order) curve key. |
| morton_decode_bounded() | Object type: Scalar function | Decode a key from morton_encode_bounded with the same bounds and bits into the centre of its grid cell, as a DOUBLE array. |
| morton_decode_latlon() | Object type: Scalar function | Decode a key from morton_encode_latlon with the same bits (default 32) into the centre of its grid cell, as STRUCT(lat DOUBLE, lon DOUBLE). |
| morton_encode() | Object type: Scalar function | Encode coordinates into one unsigned integer by interleaving their bits (Morton / Z-order). |
| morton_encode_bounded() | Object type: Scalar function | Scale each DOUBLE coordinate from [min, max] onto a grid of 2^bits cells and encode the cell with the Morton (Z-order) curve. |
| morton_encode_latlon() | Object type: Scalar function | Encode a latitude/longitude pair with the Morton (Z-order) curve over a grid of 2^bits cells per axis. |
| morton_ranges() | Object type: Table function | Table function returning the sorted, disjoint key ranges (lo, hi) of morton_encode that cover the box between min_point and max_point. |
| morton_ranges_bounded() | Object type: Table function | Table function returning the key ranges (lo, hi) of morton_encode_bounded, with the given bounds and bits, that cover the box between min_point and max_point. |
No extension contents match that search.
API Reference
Function Reference
Practical Examples
Cookbook
Real-world recipes and patterns for common use cases.
What this is for
Lindel computes Hilbert and Morton sort keys from multi-dimensional values. Ordering rows by one of these keys groups related coordinates together when writing Parquet or loading a table, so readers can use min/max statistics to skip data for multi-column predicates. The benefit depends on the data, the coordinate transform and the row-group size.
Sort points by latitude and longitude
hilbert_encode_latlon quantizes valid latitude and longitude onto a grid with 32 bits per axis and returns a UBIGINT key:
SELECT lat, lon, hilbert_encode_latlon(lat, lon) AS hilbertFROM sourceORDER BY hilbert;Pass a third argument to change the resolution: hilbert_encode_latlon(lat, lon, 16) returns a UINTEGER. The grid is angular, so cells are narrower in metres near the poles. Coordinates outside [-90, 90] and [-180, 180] raise an error.
Write the sorted layout to Parquet
COPY ( SELECT * FROM source ORDER BY hilbert_encode_latlon(lat, lon)) TO 'spatial.parquet' (FORMAT PARQUET);Query the original columns normally:
SELECT * FROM 'spatial.parquet'WHERE lat BETWEEN 40 AND 41 AND lon BETWEEN -74 AND -73;A reader can skip a row group when its statistics cannot match the predicates. Curve sorting makes that pruning more effective, but it does not guarantee tight bounds for every group or column. Benchmark with enough rows to produce multiple row groups. You don’t need to store the key column unless another system will look rows up by it.
Quantize any numeric range
For other coordinates with known bounds, hilbert_encode_bounded maps each dimension onto 2^bits cells between a minimum and a maximum. This example uses 16 bits for altitude and time:
SELECT alt, time, hilbert_encode_bounded( [alt, time]::DOUBLE[2], [0, 1700000000], -- minimum per dimension [20000, 1800000000], -- maximum per dimension 16 -- bits per dimension ) AS hilbertFROM sourceORDER BY hilbert;Values outside the bounds are clamped to the edge cells. hilbert_decode_bounded returns the centre of a key’s cell.
Mix dates, timestamps and IDs
Pass the coordinates as separate arguments. They are cast to their common type, and keys sort like the values, including dates before 1970:
SELECT symbol_id, time, hilbert_encode(symbol_id, time) AS hilbertFROM sourceORDER BY hilbert;Arguments of different kinds, such as a TIMESTAMP and a BIGINT, have no common type. Cast them to one first, for example epoch(ts)::BIGINT.
Encode signed and floating-point values directly
Signed and floating-point coordinates are mapped to order-preserving bits, so negative values sort before positive ones:
SELECT x, hilbert_encode([x]::INTEGER[1]) AS keyFROM (VALUES (-2), (-1), (0), (1), (2)) t(x)ORDER BY key;Wide types spread keys thinly, so for spatial data with known bounds, hilbert_encode_bounded usually gives a better ordering than encoding DOUBLE values directly.
Use up to four 32-bit dimensions
Four UINTEGER coordinates produce a 128-bit UHUGEINT key:
SELECT hilbert_encode([10, 20, 30, 40]::UINTEGER[4]) AS hilbert;For inputs with different units, choose a consistent scaling and offset for each dimension before encoding. Four DOUBLE dimensions are not supported because their combined width exceeds 128 bits.
Try Morton / Z-order
Every function has a Morton equivalent:
SELECT lat, lon, morton_encode_latlon(lat, lon) AS mortonFROM sourceORDER BY morton;Morton interleaves bits and has a simpler mapping than Hilbert. Compare encoding time and the resulting query performance before choosing an ordering.
Decode keys
Name the type the key was encoded from:
SELECT hilbert_decode(hilbert_encode([-1.5, 2.25]::DOUBLE[2]), 'DOUBLE[2]') AS roundtrip;-- [-1.5, 2.25]The original form takes the dimension count and two type flags, return_float and return_unsigned:
SELECT hilbert_decode( hilbert_encode([10, 20]::UINTEGER[2]), /* num_elements */ 2, /* return_float */ false, /* return_unsigned */ true) AS unsigned_roundtrip;-- [10, 20]SELECT hilbert_decode( hilbert_encode([-10, 20]::INTEGER[2]), 2, false, false) AS signed_roundtrip;-- [-10, 20]Preserve the key’s original SQL type when storing or decoding it. The integer width and dimension count determine the decoded coordinate width. Decoding recovers the values passed to the encoder; it does not undo any earlier quantization or offsets.
Look up a box in a key-only store
When another system stores rows by key, hilbert_ranges_bounded turns a box into the key ranges to scan. Use the same bounds and bits that encoded the keys:
SELECT lo, hiFROM hilbert_ranges_bounded( [40, -74], -- box minimum [41, -73], -- box maximum [-90, -180], -- encoding bounds [90, 180], 16, -- bits per dimension 8 -- at most 8 ranges);With a small range budget, the ranges also cover some keys outside the box, so filter the fetched rows on their coordinates. Inside DuckDB, skip the ranges: a plain coordinate filter on curve-sorted data is faster.
Platform Support
Compatibility
Extension availability may vary by platform and DuckDB version. Check below to ensure this extension supports your environment before installation.
Quick Facts
Platforms
DuckDB 2.0.0
- Linux x86_64aarch64
- Linux (musl) Not available
- macOS Apple Silicon
- Windows x86_64x86_64 (MinGW)
- WASM Not available
Compiled binary sizes
| Platform | Architecture | Size |
|---|---|---|
| Linux | x86_64 | 5.05 MB |
| Linux | aarch64 | 4.38 MB |
| macOS | Apple Silicon | 2.99 MB |
| Windows | x86_64 | 10.28 MB |
| Windows | x86_64 (MinGW) | 19.08 MB |
Compressed download sizes for the release shown above.
DuckDB & Haybarn
Release calendar- DuckDB v2.0.0 Query.Farm repository Supported
- Haybarn v1.5.6 Built-in community repository Supported
Browser examples use Haybarn-Wasm 2.0.0-rc12.
Checked .
Learn and explore
Tutorials and articles
Writing about Lindel: how it works, what changed, and why.
-
Lindel for DuckDB 2.0: curve keys that sort like your data
Our Hilbert and Morton extension now keeps negative numbers, floats and dates in order, quantizes lat/lon onto a grid, and decomposes box queries into key ranges. Sorting 20 million points by a Hilbert key cut a Parquet box query from 200 row groups to 2. Joining on the key ranges never helped inside DuckDB.