# GLX v1 specification > The .glx version 1 file format: header, sections, term dictionary, postings, documents, spatial and id indexes, and what a conforming reader must do. > Generated from `spec/v1/spec.md` in the geolith/glx repository at commit `561a984`. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). --- Please refer to the [change log](/glx/changelog) for a documentation of changes to this specification. Small sample files and the values they hold are in [`fixtures/`](/glx/fixtures/fixtures.json). ## 1 Abstract GLX is geolith's single-file format for map data that is queried, not rendered. A file holds one or more _parts_, each an independent byte range for one service: - the _search part_: a geocoding index for full-text search over place names and addresses, autocomplete, reverse geocoding and lookup by id (Chapters 3 to 8); - the _routing part_: a road graph cut into tiles, for routing (Chapter 10). Each part is answered from the file while a reader holds only a small part of it in memory and reads the rest with HTTP range requests. A reader for one part never reads the bytes of another. The recommended file extension is `.glx`. The recommended MIME type is `application/vnd.glx`. ## 2 Overview A GLX file starts with a fixed 256-byte _file header_ that lists its parts (2.6). The rest of this overview and Chapters 3 to 8 describe the search part; Chapter 10 describes the routing part. The search part consists of a fixed 256-byte _search header_ (Chapter 3) followed by thirteen sections (Chapters 4 and 5). Each section is a contiguous byte range; the search header's section table gives the offset and length of each, counted from the start of the part. Seven sections are the _boot sections_: a reader loads them once, right after the header, and keeps them in memory. The other six hold the bulk of the data, cut into independently compressed blocks that a reader fetches one range at a time, as a query needs them. ``` <------------------ boot span ------------------> +--------+------+-------+-------+------+------+-------+------+------+------+------+-------+-----+--------+ | Search | term | spat. | doc | chun-| id | shape | rec. | dict-| post-| docu-| spat- | ids | shapes | | header | idx | dir | index | ks | dir | dir | dict | ion- | ings | ments| ial | | | | | | | | | | | | ary | | | | | | +--------+------+-------+-------+------+------+-------+------+------+------+------+-------+-----+--------+ P P+256 (P: where the search part starts in the file) <------------- in memory ------------------> <--------- fetched block by block ---------> ``` A file stores each place once, as a _record_ in a _document block_. Places are numbered `0` to `N - 1` in the order the writer added them; this number is the _document number_ (or _document_) and is how every other section refers to a place. ### 2.1 Byte order and integer encodings All fixed-width integers and floats are **little-endian**. `u8`, `u16`, `u32`, `u64` are unsigned; `i32`, `i64` are two's-complement signed; `f32` is an IEEE 754 binary32. **varint**: an unsigned integer in LEB128: seven bits per byte, least significant group first, the high bit of each byte set when more bytes follow. `0` is `0x00`, `127` is `0x7F`, `128` is `0x80 0x01`, `300` is `0xAC 0x02`. A varint in this format holds at most 64 bits (10 bytes). A reader MUST refuse a varint that is cut short by the end of its buffer or that runs past 64 bits. **zigzag varint**: a signed integer `v` mapped to an unsigned one, `(v << 1) ^ (v >> 63)` (arithmetic shift), then written as a varint, so small magnitudes take one byte: `0 → 0`, `-1 → 1`, `1 → 2`, `-2 → 3`. Decoding is `(u >> 1) ^ -(u & 1)`. **gap list**: a list of ascending unsigned integers written as the first value, then each value minus the one before, each a varint. **delta list**: a list of signed integers written as each value minus the one before (the first minus `0`), each a zigzag varint. ### 2.2 Text All text is UTF-8. A _string_ stored with an explicit length is a varint byte count followed by that many bytes; it is not terminated. Term order (Chapter 5.6) is the order of the strings' UTF-8 bytes compared lexicographically as unsigned bytes, which is the order of their Unicode code points. ### 2.3 Coordinates A coordinate is stored as a _fixed-point_ `i32` of millionths of a degree (1e-6 degree, about 11 cm): `round(clamp(degrees, -L, L) * 1_000_000)`, rounding half away from zero, where `L` is `180` for a longitude and `90` for a latitude. Decoding is `value / 1_000_000`. A _box_ is four fixed-point `i32` in the order west (minimum longitude), south (minimum latitude), east (maximum longitude), north (maximum latitude): 16 bytes. ### 2.4 Layers and countries A place's _layer_ is one of the strings `venue`, `address`, `street`, `locality`, `county`, `region`, `country`, or another string. Where a section stores a layer as a code, it is a `u8`: | Code | Layer | | ---: | :---------------- | | `0` | any other or none | | `1` | `venue` | | `2` | `address` | | `3` | `street` | | `4` | `locality` | | `5` | `county` | | `6` | `region` | | `7` | `country` | A _country code_ is an ISO 3166-1 alpha-2 code. Where a section stores it as a code, it is a `u16` whose little-endian bytes are the code's two ASCII bytes as written in the record (so `IN` is `0x49 0x4E`, the `u16` value `0x4E49`). Any string that is not exactly two bytes long is code `0`. ### 2.5 Compression Every block a reader fetches from a block section is exactly one [zstd](https://www.rfc-editor.org/rfc/rfc8878) frame, decompressed on its own. A reader MUST NOT assume a frame states its content size, but writers SHOULD write it (the reference writer does). Document blocks are compressed with the _record dictionary_ (Chapter 5.12) when that section is not empty, and without a dictionary when it is empty. Every other block is compressed without a dictionary. The compression level is the writer's choice. The reference writer uses zstd level 3 for posting, spatial and id blocks and level 19 for dictionary, document and shape blocks. ### 2.6 File header and parts Every GLX file starts with this 256-byte file header: | Offset | Size | Type | Field | | -----: | ---: | :----------- | :----------- | | `0` | 4 | bytes | Magic number | | `4` | 4 | `u32` | Version | | `8` | 4 | `u32` | Part count | | `12` | 4 | bytes | Reserved | | `16` | 224 | 7 × 32 bytes | Part table | | `240` | 16 | bytes | Padding | - _Magic number_: always `GLX0` in ASCII (`0x47 0x4C 0x58 0x30`). The `0` is part of the magic, not a version number. - _Version_: always `1`. - _Part count_: the number of part entries in use, `1` to `7`. - _Reserved_ and _padding_: writers MUST write zero; readers MUST ignore them. Unused part entries are all zero. Each part entry is 32 bytes: | Offset | Size | Type | Field | | -----: | ---: | :---- | :------- | | `0` | 4 | bytes | Kind | | `4` | 4 | `u32` | Reserved | | `8` | 8 | `u64` | Offset | | `16` | 8 | `u64` | Length | | `24` | 8 | `u64` | Checksum | - _Kind_: four ASCII bytes naming the part: `SRCH` for the search part (Chapter 3), `ROUT` for the routing part (Chapter 10). A file holds at most one part of each kind. - _Offset_ and _length_: the part's byte range in the file. Parts do not overlap each other or the file header. - _Checksum_: the XXH3-64 hash (seed `0`) of the part's bytes. A reader that serves queries over HTTP does not read whole parts and so does not check it; a tool that copies a part from one file to another MUST check it, and a reader MAY. Every offset inside a part is counted from the start of that part, so a part's bytes are the same in any file that holds it: a writer adds a part to a file, or merges the parts of several files into one, by copying each part's bytes unchanged and writing a new file header. The first part starts at offset `256`, right after the file header. A file that holds a search part lists it first, so that its search header is in the first 512 bytes. Further parts follow with no gaps, in part-table order; a reader MUST locate them through the part table only. A reader MUST refuse a file whose magic is not `GLX0`, whose version is not `1`, whose part count is `0` or above `7`, that lists a kind twice, or whose parts overlap each other or the file header. A reader for one kind of part MUST refuse a file that holds no part of that kind, and MUST ignore parts of other kinds, including kinds this specification does not name. The reference reader refuses a file without the part it needs with a message naming the kinds the file does hold. ## 3 Search header The search header is 256 bytes long and is always at the start of the search part. Every offset in it, and in the sections it locates, is counted from the start of the search part. ### 3.1 Overview ``` Offset 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 000000 | Kind | Reserved | Documents | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 000010 | Avg field length | Importance wt. | Features | Reserved | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 000020 | Section 0 offset | Section 0 length | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ ... sections 1 to 11 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 0000E0 | Section 12 offset | Section 12 length | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 0000F0 | Padding | +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ ``` | Offset | Size | Type | Field | | -----: | ---: | :------------------ | :------------------- | | `0` | 4 | bytes | Kind | | `4` | 4 | bytes | Reserved | | `8` | 8 | `u64` | Documents | | `16` | 4 | `f32` | Average field length | | `20` | 4 | `f32` | Importance weight | | `24` | 4 | `u32` | Features | | `28` | 4 | bytes | Reserved | | `32` | 208 | 13 × (`u64`, `u64`) | Section table | | `240` | 16 | bytes | Padding | ### 3.2 Fields #### Kind Always `SRCH` in ASCII (`0x53 0x52 0x43 0x48`), the kind of the part's entry in the file header (2.6). A reader MUST refuse a search part whose kind field is not `SRCH`. #### Reserved Four bytes at offset `4`. Writers MUST write zero. Readers MUST ignore them. #### Documents A `u64`: the number of places in the file, `N`. Document numbers are `0` to `N - 1` and are stored as `u32`, so `N` MUST NOT exceed `2^32 - 1`. A reader MUST refuse a header whose `N` exceeds `2^32 - 1`. #### Average Field Length An `f32`: the average _field length_ (Chapter 6.5) over all documents, computed as the sum of every document's field length divided by `N` in 64-bit floating point, then rounded to `f32`; `1.0` when `N` is `0`. A reader uses it for BM25 length normalisation. #### Importance Weight An `f32`: the weight of a place's importance in its rank, chosen by the writer. It is used by readers when ranking (Chapter 8) and by the writer to choose head lists (Chapter 5.6.4). The reference writer is given it by its caller; the fixtures use `10.0`. #### Features A `u32` bit field. Each bit says how part of the file is encoded. Chapter 3.3 lists the bits and the rules for readers and writers. #### Reserved Four bytes at offset `28`. Writers MUST write zero. Readers MUST ignore them. #### Section Table Thirteen entries, one per section in section-number order. Entry `n` is at offset `32 + 16 n`: the section's offset from the start of the search part (`u64`), then its length in bytes (`u64`). A section of length `0` is empty; its offset is still where it would start. Every section lies inside the search part; a reader MUST refuse a search header whose section table points past the part's length. | Number | Section | Chapter | | -----: | :---------------- | :------ | | `0` | Term index | 5.1 | | `1` | Spatial directory | 5.2 | | `2` | Document index | 5.3 | | `3` | Chunks | 5.4 | | `4` | Dictionary | 5.6 | | `5` | Postings | 5.6.3 | | `6` | Documents | 5.7 | | `7` | Spatial | 5.8 | | `8` | Id directory | 5.5 | | `9` | Ids | 5.9 | | `10` | Shape directory | 5.10 | | `11` | Shapes | 5.11 | | `12` | Record dictionary | 5.12 | #### Padding Sixteen bytes after the section table. Writers MUST write zero. Readers MUST ignore them. ### 3.3 Feature bits Bits `0` to `14` are _required_: every version 1 file has all of them set, and each one names an encoding that this specification describes as the only one. Bits `15` and `16` are _optional_: each selects between two encodings of one section, both described here. Bits `17` to `31` are _reserved_: they name nothing in this specification. | Bit | Value | Name | Kind | Meaning | | --: | --------: | :------------------- | :------- | :------------------------------------------------------------------------------------------------------- | | 0 | `0x00001` | `NAME_TEXT` | required | Records hold the place's names in `name_text` (5.7). | | 1 | `0x00002` | `DISTINCT_WORDS` | required | Each word counts once per place, in the term frequency and the field length (6.4, 6.5). | | 2 | `0x00004` | `SCRIPT_FOLD` | required | Words keep the combining marks of scripts that write letters with them; only diacritics fold away (6.1). | | 3 | `0x00008` | `WRITTEN_LENGTH` | required | The field length counts written words, not segmenter tokens (6.5). | | 4 | `0x00010` | `UNPLACED_POSTINGS` | required | Postings hold no word positions (5.6.2). | | 5 | `0x00020` | `UNSIGNED_POSTINGS` | required | Postings hold no word or prefix signatures (5.6.2). | | 6 | `0x00040` | `COLUMNAR_RECORDS` | required | Document blocks are stored column by column (5.7). | | 7 | `0x00080` | `DELTA_SPATIAL` | required | Spatial blocks store documents and coordinates as deltas (5.8.3). | | 8 | `0x00100` | `SHAPES` | required | The shape sections exist (5.10, 5.11); set even when both are empty. | | 9 | `0x00200` | `RECORD_DICTIONARY` | required | The record dictionary section exists (5.12); set even when it is empty. | | 10 | `0x00400` | `ID_FINGERPRINTS` | required | Id blocks hold a 16-bit fingerprint of each id (5.9.3). | | 11 | `0x00800` | `MICRODEGREES` | required | Coordinates are fixed-point at 1e-6 degree (2.3). | | 12 | `0x01000` | `PLACE_DETAILS` | required | Records hold neighbourhood, borough, category, names by language and box (5.7). | | 13 | `0x02000` | `APOSTROPHE_WORDS` | required | A word with an apostrophe is indexed without it and by its parts (6.2). | | 14 | `0x04000` | `CJK_PAIRS` | required | Runs of Chinese and Japanese characters are indexed as adjacent pairs (6.3). | | 15 | `0x08000` | `SHORT_PREFIX_LISTS` | optional | Prefixes of 2 to 6 characters all have posting lists; there are no head-only entries (5.6.5). | | 16 | `0x10000` | `COMPACT_DOC_INDEX` | optional | The document index is in its compact form (5.3.2). Clear: the wide form (5.3.1). | The required bits together are `0x7FFF`. A file written by the reference writer with both optional bits set has features `0x1FFFF`. A writer MUST set every required bit. A writer MUST set an optional bit exactly when the section it governs is in the encoding the bit selects. A writer MUST NOT set a reserved bit. A reader MUST refuse a search part whose features lack any required bit, or whose features set any bit the reader does not know (for a reader of this specification, any reserved bit): such a part was written to another layout and its records would not decode, or its words would be folded differently, so reading it would give empty or wrong answers rather than an error. The reference reader refuses it with the message "not a .glx file, or one built by an older or newer glx writer: rebuild it with the current geolith". A reader MUST support both encodings of each optional bit. A bit added by a later revision is therefore refused by every reader that predates it, whether the revision calls it required or optional; files that leave it clear stay readable by those readers. ## 4 File layout The search header is at offset `0` of the search part. Sections follow it with no gaps, in this order, which is not section-number order: | Position | Number | Section | Boot | | -------: | -----: | :---------------- | :--: | | 1 | 0 | Term index | yes | | 2 | 1 | Spatial directory | yes | | 3 | 2 | Document index | yes | | 4 | 3 | Chunks | yes | | 5 | 8 | Id directory | yes | | 6 | 10 | Shape directory | yes | | 7 | 12 | Record dictionary | yes | | 8 | 4 | Dictionary | | | 9 | 5 | Postings | | | 10 | 6 | Documents | | | 11 | 7 | Spatial | | | 12 | 9 | Ids | | | 13 | 11 | Shapes | | The _boot span_ runs from the term index's offset to the end of the record dictionary. A writer MUST place the seven boot sections in it, back to back in the order above, starting at part offset `256`, so that one range request after the header fetches all of them. The six block sections SHOULD follow in the order above; a reader MUST locate them through the section table only, never by position. The part SHOULD end at the end of its last section. ## 5 Sections ### 5.1 Term index The index of the dictionary's blocks, one entry per dictionary block in term order. | Field | Type | Meaning | | :--------- | :----- | :------------------------------------------------------------------------ | | count | varint | Number of dictionary blocks | | _count ×_ | | | | first term | string | The first term of the block (5.6.1) | | offset | varint | Offset of the block's zstd frame from the start of the dictionary section | | length | varint | Length of the frame in bytes | Entries are in ascending term order, and so are the blocks they point to. The block that may hold a term `t` is the last block whose first term is less than or equal to `t`; when there is none, `t` is in no block. ### 5.2 Spatial directory The top level of the two-level spatial directory: one _node_ per group of 64 consecutive spatial blocks (Chapter 5.8), in block order. | Offset | Size | Type | Field | | -----: | ---: | :---- | :-------------------------------------- | | `0` | 16 | box | Box of every place in the node's blocks | | `16` | 4 | `u32` | Index of the node's first block | | `20` | 4 | `u32` | Number of the node's blocks | 24 bytes per node. Node `k` covers blocks `64 k` to `64 k + count - 1`; every node but the last has `count = 64`. The sum of `count` over all nodes is the number of spatial blocks, `B`. ### 5.3 Document index The offset of every document block in the documents section, relative to the start of that section, followed by the section's length: `D + 1` offsets for `D = ceil(N / 256)` blocks. Block `i` runs from offset `i` to offset `i + 1`. Offsets MUST be non-decreasing; the first is `0`. #### 5.3.1 Wide form Used when feature bit 16 is clear: `D + 1` offsets, each a `u64`. #### 5.3.2 Compact form Used when feature bit 16 is set. | Field | Type | Meaning | | :----------- | :--------------------- | :-------------------------------------------------------------------------------- | | blocks | `u32` | `D` | | escapes | `u32` | `E`, the number of escaped lengths | | anchors | `(D / 64 + 1)` × `u64` | Offsets `0`, `64`, `128`, …: offset `64 j` for every `j` with `64 j ≤ D` | | lengths | `D` × `u16` | Length of each block; `0xFFFF` means the length is in the escapes | | escape table | `E` × (`u32`, `u32`) | Block number, then its length; one per `0xFFFF` length, by ascending block number | `D / 64` is integer division. The section's length MUST be exactly `8 + 8 (D / 64 + 1) + 2 D + 8 E`. The length of block `i` is its `u16` when that is below `0xFFFF`, else the length its escape gives. A block of `2^32` bytes or more cannot be written in this form. Offset `i` is anchor `i / 64` plus the lengths of blocks `64 (i / 64)` to `i - 1`. A reader MUST refuse the section when its length does not match its counts, the anchors decrease, the escapes are not in ascending block order, or the escape table does not hold exactly one entry for each `0xFFFF` length. ### 5.4 Chunks One 5-byte entry per _chunk_ of 1024 consecutive documents (the last chunk may be shorter): `ceil(N / 1024)` entries. | Offset | Size | Type | Field | | -----: | ---: | :---- | :------------------------------------------------------ | | `0` | 4 | `f32` | The highest importance of the chunk's documents | | `4` | 1 | `u8` | The lowest field-norm id (6.5) of the chunk's documents | A reader MAY use chunks to bound the rank of any document from a given number on. ### 5.5 Id directory The top level of the two-level id directory: one node per group of 64 consecutive id blocks (Chapter 5.9), in block order. | Offset | Size | Type | Field | | -----: | ---: | :---- | :--------------------------------------------------------------- | | `0` | 8 | `i64` | Lowest id in the node's blocks (the first id of its first block) | | `8` | 4 | `u32` | Index of the node's first block | | `12` | 4 | `u32` | Number of the node's blocks | 16 bytes per node; as in Chapter 5.2, node `k` covers blocks `64 k` on, and the counts sum to the number of id blocks, `I`. ### 5.6 Dictionary and postings The dictionary section is a sequence of _dictionary blocks_, each a zstd frame, located through the term index (5.1). #### 5.6.1 Terms A _term_ is either a _word_, a folded index token (Chapter 6), or a _prefix key_: the character `U+0001` followed by the first 2 to 6 characters (Unicode scalar values) of a word. Prefix keys sort before every word that starts with a letter or a digit. Each term appears in the dictionary exactly once, in ascending term order across all blocks. A decompressed dictionary block is: | Field | Type | Meaning | | :------ | :------------------- | :---------------------- | | count | varint | Number of entries | | entries | _count ×_ term entry | In ascending term order | The reference writer closes a block once its entries pass 32 KiB (256 KiB when feature bit 15 is clear); readers MUST NOT depend on block sizes. #### 5.6.2 Term entry | Field | Type | Meaning | | :--------- | :---------------------- | :-------------------------------------------------------------------------------------------------------------------- | | term | string | The word, or `U+0001` and the prefix | | doc freq | varint | Number of documents holding the term | | max tf | `u8` | Highest stored term frequency (below) over the term's documents, the name flag set when any document has it | | kind | `u8` | `0` inline, `1` external, `2` head only | | postings | | Kind `0`: one posting block (5.6.3), not separately compressed. Kind `1`: an external list (5.6.3). Kind `2`: nothing | | head count | varint | Number of head entries, at most 32 | | head | _head count ×_ 12 bytes | Head entries (5.6.4) | Kinds above `2` are reserved: writers MUST NOT write them, and a reader MUST refuse an entry that has one, since nothing says what follows it. A _stored term frequency_ is a `u8`: the low seven bits are the number of times the word occurs in the place, which is always `1` (feature bit 1); the high bit (`0x80`) is the _name flag_, set when the word is one of the place's name words (Chapter 6.4). For prefix keys `max tf` is `1`. Prefix keys hold no term frequencies. Whether an entry is a word or a prefix key is told by its first character, not by its kind. #### 5.6.3 Posting blocks A _posting block_ lists documents holding a term, ascending, with what a reader needs to rank and filter them without reading their records. A word's posting block: | Field | Type | Meaning | | :--------------- | :---------------------- | :----------------------------------------------- | | count | varint | Number of postings, `n` | | documents | gap list of `n` varints | Document numbers, strictly ascending | | term frequencies | `n` × `u8` | Stored term frequency per document | | lengths | `n` × `u8` | Field length per document, capped at `255` (6.5) | | importances | `n` × `u8` | Quantized importance per document (below) | | layers | `n` × `u8` | Layer code per document (2.4) | | countries | `n` × `u16` | Country code per document (2.4) | A prefix key's posting block is the same without the term frequencies and the lengths: count, documents, importances, layers, countries. The _quantized importance_ of a place of importance `x` is the smallest `q` in `0..=255` with `q / 255 ≥ min(max(x, 0), 1)` (computed in binary32): `ceil(x × 255)` raised until it is not below `x`, so `q / 255` is an upper bound on the importance. A term's list is _inline_ (kind `0`) when its whole posting block is in the term entry. Otherwise it is _external_ (kind `1`): the list is cut into posting blocks of at most 512 postings, each compressed into its own zstd frame, stored one after another in the postings section. The reference writer stores a list inline when it holds at most 16,384 documents and its posting block is at most 16,384 bytes; readers MUST accept either kind for any list. An external list in the term entry: | Field | Type | Meaning | | :--------- | :---------------------- | :---------------------------------------------------------------------- | | offset | varint | Offset of the list's first frame from the start of the postings section | | skip count | varint | Number of posting blocks | | skips | _skip count ×_ 20 bytes | One skip entry per block, in document order | A skip entry: | Offset | Size | Type | Field | | -----: | ---: | :---- | :------------------------------------------------- | | `0` | 4 | `u32` | First document in the block | | `4` | 4 | `u32` | Last document in the block | | `8` | 8 | `u64` | Offset of the block's frame from the list's offset | | `16` | 4 | `u32` | Length of the frame | The frame of block `b` is at postings offset + list offset + skip offset. Blocks of one list are in ascending document order and do not overlap. #### 5.6.4 Head lists A _head_ is a short list of a term's best documents, so that a one-word query can be answered without walking the term's postings. Each entry is 12 bytes: | Offset | Size | Type | Field | | -----: | ---: | :---- | :------------------------------------- | | `0` | 4 | `u32` | Document | | `4` | 4 | `f32` | The term's text score for the document | | `8` | 4 | `f32` | The document's importance | Inline entries have an empty head. The reference writer gives an external word the up to 32 documents of highest `score + weight × importance` (weight from the header), best first, earliest document first on ties, where the score is the BM25 of the word alone (Chapter 8), plus the name weight `3.0` when the name flag is set. For an external prefix key the score is `0` and the order is by importance. The choice and order of head documents is implementation-defined; a reader MAY use a head only as a set of documents that hold the term together with their stored scores. #### 5.6.5 Prefix layout Prefix keys are written for every word of a place as written (Chapter 6.4; not the name initials), for each length from 2 to 6 characters the word reaches. A place appears at most once in each prefix key's list. When feature bit 15 is set, every prefix key of 2 to 6 characters has an inline or external list. When feature bit 15 is clear, prefix keys of 4 to 6 characters have lists as above, while prefix keys of 2 or 3 characters are kind `2` (head only): `doc freq` is the number of documents holding the prefix, `max tf` is `1`, and the head holds the up to 32 most important of them, most important first, earliest first on ties, with score `0`. A reader of such a file answers a 2- or 3-character prefix from its head alone. ### 5.7 Documents The documents section is a sequence of _document blocks_, each one zstd frame (compressed with the record dictionary when there is one, 2.5), located through the document index (5.3). Block `i` holds documents `256 i` to `256 i + 255` (fewer in the last block), in order; document `d` is entry `d mod 256` of block `d / 256`. A decompressed document block is stored column by column: | Field | Type | Meaning | | :---------- | :----------------------------------- | :-------------------------------------------------------------------------------------------------- | | count | varint | Number of records, `n` | | ids | delta list of `n` zigzag varints | Record ids, in 64-bit wrapping arithmetic | | coordinates | `n` × (zigzag varint, zigzag varint) | Longitude, then latitude, fixed-point (2.3), each minus the previous record's (the first minus `0`) | | importances | `n` × `f32` | Importance of each record, `0` to `1` | | columns | 16 string columns | Below, in column order | A _plain_ string column is `n` varint lengths followed by the `n` entries' bytes, one after another. A _table_ column is the number of distinct entries `m` (varint), their `m` varint lengths, their bytes one after another, then `n` varint indices into the distinct entries, one per record. The reference writer lists distinct entries in order of first appearance. A reader MUST refuse an index of `m` or more. | Column | Field | Form | Content | | -----: | :------------ | :---- | :------------------------------------------------------ | | 0 | name | plain | Display name | | 1 | layer | table | Layer name (2.4), as text | | 2 | country code | table | ISO 3166-1 alpha-2 code | | 3 | country | table | Country name | | 4 | region | table | Region | | 5 | county | table | County | | 6 | locality | table | Locality | | 7 | street | table | Street | | 8 | postcode | table | Postcode | | 9 | search text | plain | Tagged, below | | 10 | name text | plain | Tagged, below | | 11 | neighbourhood | table | Neighbourhood, suburb or quarter | | 12 | borough | table | Borough or city district | | 13 | category | table | Category (`college`, `railway station`), empty for none | | 14 | languages | plain | Names by language, below | | 15 | box | plain | Empty, or the box of the place's outline, below | Every entry of every column except 9, 10 and 15 is UTF-8 text, empty when the place has no such field. The block ends with column 15. #### 5.7.1 Name text `name_text` is every name of the place (its name, translations and other names), space-separated. Column 10's entry is a tag byte, then: - tag `0` (_derived_): bytes `r`; `name_text` is the name (column 0) followed by `r`; - tag `1` (_literal_): `name_text` is the remaining bytes. Tag `0` is only possible when `name_text` starts with the name; the reference writer then always uses it. #### 5.7.2 Search text `search_text` is the text the place is indexed by (Chapter 6). Column 9's entry is a tag byte, then: - tag `1` (_literal_): `search_text` is the remaining bytes; - tag `0` (_derived_): a varint `k`, which MUST end the entry. The name text MUST be derived; let `r` be its bytes after the tag. Then `search_text` is the concatenation of 1. the name (column 0), 2. `r` without its last `k` bytes, 3. when `A` is not empty, a space and `A`, 4. the last `k` bytes of `r`, 5. when `S` is not empty, the character `U+001F` and `S`, where `A` is the non-empty ones of street, locality, county, region and country, in that order, joined by single spaces, and `S` is the non-empty ones of neighbourhood and borough, joined by a single space. `k` MUST NOT exceed the length of `r`, and the split MUST fall on a character boundary. A writer MAY use tag `0` whenever some `k` rebuilds `search_text` exactly; the reference writer uses the smallest such `k`. `U+001F` in `search_text` is the _language mark_: the words after it are indexed but not counted in the field length (6.5). #### 5.7.3 Languages Column 14 holds the place's names by language: entries of a language code (an OpenStreetMap `name:` code), the character `U+001F`, and the name, joined by `U+001E`. Empty when there are none. #### 5.7.4 Box Column 15 is empty, or four zigzag varints: the outline's west, south, east and north in fixed-point, each minus the record's own longitude, latitude, longitude and latitude respectively. A reader MUST refuse an entry that has bytes after the fourth varint. ### 5.8 Spatial Every place, in _Hilbert order_, cut into _spatial blocks_ of at most 512 places: the answer to reverse geocoding and to box restrictions. Spatial blocks are numbered `0` to `B - 1` in order. #### 5.8.1 Order The reference writer orders places by the Hilbert index (5.8.4) of their quantized position (Chapter 6.6), then by document number, and fills every block but the last with 512 places. Readers MUST NOT depend on the order or the block size: a block's box, below, is all a reader relies on. #### 5.8.2 Section layout | Field | Type | Meaning | | :------ | :-------------- | :------------------------------------------------ | | entries | `B` × 28 bytes | The directory's second level: one entry per block | | blocks | `B` zstd frames | The spatial blocks, one after another | `B` is the sum of the spatial directory's node counts (5.2). An entry: | Offset | Size | Type | Field | | -----: | ---: | :---- | :--------------------------------------------------------------------------------------------- | | `0` | 16 | box | Box of the block's places | | `16` | 8 | `u64` | Offset of the block's frame from the start of the blocks, that is from section offset `+ 28 B` | | `24` | 4 | `u32` | Length of the frame | A block's box MUST hold every place in the block; a node's box MUST hold the boxes of its blocks. The entries of node `k` are entries `first` to `first + count - 1`, at section offset `+ 28 first`. #### 5.8.3 Spatial block A decompressed spatial block of `n` places: | Field | Type | Meaning | | :---------- | :----------------------------------- | :------------------------------------------------------------------------------------------ | | count | varint | `n` | | documents | delta list of `n` zigzag varints | Document numbers | | coordinates | `n` × (zigzag varint, zigzag varint) | Longitude then latitude, fixed-point, each minus the previous place's (the first minus `0`) | | layers | `n` × `u8` | Layer codes | | countries | `n` × `u16` | Country codes | A reader MUST refuse a block whose counts run past its end, or whose deltas leave the `u32` range of a document or the `i32` range of a coordinate. The coordinates are the record's (5.7) exactly. #### 5.8.4 Hilbert index The Hilbert index of a cell `(x, y)` of the 65,536 × 65,536 grid, both `u16`, is the `u32` `d` computed as: ``` d = 0 for s in 32768, 16384, ..., 1: rx = 1 if x & s else 0 ry = 1 if y & s else 0 d += s * s * ((3 * rx) ^ ry) if ry == 0: if rx == 1: x = 65535 - x y = 65535 - y swap(x, y) ``` ### 5.9 Ids Every (id, document) pair, sorted by id as a signed `i64` and then by document, cut into _id blocks_ of at most 1024 pairs: lookup of a place by the id of its record. Ids need not be unique: every place with the id is found. Id blocks are numbered `0` to `I - 1`. #### 5.9.1 Section layout | Field | Type | Meaning | | :------ | :-------------- | :------------------------------------------------ | | entries | `I` × 20 bytes | The directory's second level: one entry per block | | blocks | `I` zstd frames | The id blocks | An entry: | Offset | Size | Type | Field | | -----: | ---: | :---- | :-------------------------------------------------------------------------------- | | `0` | 8 | `i64` | The block's lowest id | | `8` | 8 | `u64` | Offset of the block's frame from the start of the blocks, section offset `+ 20 I` | | `16` | 4 | `u32` | Length of the frame | The entries of id-directory node `k` (5.5) are entries `first` to `first + count - 1`. #### 5.9.2 Finding an id Because ids repeat, the pairs of one id may span blocks. The blocks that may hold id `v` are: the last block whose lowest id is below `v`, and every block whose lowest id equals `v`. The same rule over the nodes' lowest ids gives the nodes whose entries to read. #### 5.9.3 Id block A decompressed id block of `n` pairs: | Field | Type | Meaning | | :----------- | :---------- | :---------------------------------------- | | count | varint | `n` | | fingerprints | `n` × `u16` | Low 16 bits of each id (two's complement) | | documents | `n` × `u32` | Document of each pair | The block MUST end after the documents. The full ids are not in the block: a reader takes every pair whose fingerprint is that of the asked id, reads the documents' records, and keeps those whose record id (5.7) is the asked id. ### 5.10 Shape directory One 16-byte entry per shape block, in block order: | Offset | Size | Type | Field | | -----: | ---: | :---- | :--------------------------------------------------------------- | | `0` | 4 | `u32` | The block's first document | | `4` | 8 | `u64` | Offset of the block's frame from the start of the shapes section | | `12` | 4 | `u32` | Length of the frame | Entries are in ascending first-document order. The shape of document `d`, if it has one, is in the last block whose first document is at most `d`. A file whose places have no shapes has an empty shape directory and an empty shapes section. ### 5.11 Shapes A sequence of _shape blocks_, each one zstd frame. A shape is a place's outline as polygons; only some places have one. The reference writer closes a block once its shapes pass 128 KiB. A decompressed shape block: | Field | Type | Meaning | | :----- | :--------------------- | :-------------------------------------------------------------------------------------------------------- | | count | varint | Number of shapes, `n` | | heads | `n` × (varint, varint) | Document number as a gap from the previous shape's (the first from `0`), then the shape's length in bytes | | shapes | | The `n` shapes' bytes, one after another | Documents in a block are strictly ascending. The block MUST end with the last shape. A shape: | Field | Type | Meaning | | :------------------ | :--------------------------- | :------------------------------------------------------------------------------------------------------------------------------------------ | | polygons | varint | Number of polygons | | _per polygon_ rings | varint | Number of rings: the outer ring, then its holes | | _per ring_ points | varint | Number of points; a ring is closed (its last point repeats its first) | | _per point_ | zigzag varint, zigzag varint | Longitude then latitude in fixed-point (2.3), each minus the previous point's, carried across rings and polygons (the very first minus `0`) | The shape MUST end after its last point. A reader MUST refuse a shape with a coordinate beyond ±180 degrees. ### 5.12 Record dictionary A zstd dictionary, as defined by RFC 8878 §5, with which every document block is compressed; or empty, in which case document blocks are plain zstd frames. The reference writer trains the dictionary (at most 110 KiB) on a sample of the file's own raw document blocks when there are at least 8 blocks, and leaves the section empty otherwise. Feature bit 9 is set in both cases. ## 6 Text processing What a place is found by: how a writer turns `search_text` and `name_text` into terms. Everything in this chapter is normative for writers, because readers look terms up by their exact bytes; the query-side rules of Chapter 6.7 are what a reader needs to find them. The Unicode algorithms named here are those of the Unicode version of the reference implementation (the Rust crates `unicode-segmentation` 1.13 and `unicode-normalization` 0.1.25). A writer on another Unicode version MAY fold or segment rare characters differently. ### 6.1 Folding `fold(w)`: 1. Lowercase every character (full Unicode lowercase mapping). 2. Decompose to NFD. 3. Walk the characters with a flag _diacritics_, initially true. A combining mark (General Category `Mn`, `Mc` or `Me`) is dropped when _diacritics_ is true and kept otherwise. Any other character is kept and sets _diacritics_ to whether its code point is in `U+0000–U+08FF`, `U+1D00–U+1FFF`, `U+2C60–U+2C7F`, `U+A640–U+A69F`, `U+A720–U+A7FF` or `U+FB00–U+FDFF` (Latin, Greek, Cyrillic, Armenian, Hebrew, Arabic and their extensions). So `Café` folds to `cafe`, while an Indic vowel sign, which tells words apart (`दिल्ली`, `दुल्लु`), is kept. The result is not recomposed. ### 6.2 Index tokens `index_tokens(text)` walks the words of `text` by Unicode word boundaries (UAX #29, words that hold at least one letter or digit), keeping a pending _Chinese and Japanese run_ (a list of units) and a pending _initials_ string: 1. A word all of whose characters are _CJK_ (below) joins the run: when the word does not start where the previous CJK word ended, the run is first flushed (6.3). Each character becomes a unit of its own, except `U+3099` and `U+309A`, which join the unit before them. Go to the next word. 2. Otherwise flush the run. 3. If the word is one ASCII letter (an _initial_), append `fold(word)` to the initials string and continue at step 6. 4. Else, if the word contains `.` and every part between dots is an initial: flush the initials (below); emit `fold` of each part, then the folded parts joined; go to the next word. 5. Else flush the initials. 6. If the word contains an apostrophe (`'` or `U+2019`): emit `fold` of each part between apostrophes that has 2 characters or more (when not empty), then `fold` of the word with its apostrophes removed. Else emit `fold(word)`. At the end, flush the run, then the initials. _Flushing the initials_ emits the initials string when it has 2 characters or more, and empties it. Empty tokens are dropped. `M G Road` gives `m`, `g`, `mg`, `road`; `D.Y. Patil` gives `d`, `y`, `dy`, `patil`; `Swensen's` gives `swensen`, `swensens`; `Rue de l'Église` gives `rue`, `de`, `eglise`, `leglise`. ### 6.3 Chinese and Japanese pairs A character is _CJK_ when its code point is `U+3005`, `U+3007`, `U+3021–U+3029`, `U+3040–U+30FF`, `U+31F0–U+31FF`, `U+3400–U+4DBF`, `U+4E00–U+9FFF`, `U+F900–U+FAFF` or `U+20000–U+3FFFF`. Flushing a run of `u` units emits nothing when `u = 0`, `fold` of the unit when `u = 1`, and otherwise `fold` of each pair of adjacent units (the `u - 1` pairs, in order). The run is then empty. `東京タワー` gives `東京`, `京タ`, `タワ`, `ワー`. ### 6.4 A place's terms For a place with search text `s`, name text `t`, name `m` and layer `l`: - Its _words_ are `index_tokens(s)` with repeats removed, the first of each kept. - Its _name initials_: when `l` is neither `address` nor `street`, split `m` at every character that is not alphanumeric, drop empty pieces and the pieces `of`, `and`, `the`, `for` (compared lowercased); when 3 to 6 pieces remain and each starts with an ASCII letter, the initials are those letters lowercased, joined (`State Bank of India` gives `sbi`). When the initials are not already one of its words, they are added as a word after the others. - A word's name flag (5.6.2) is set when it is one of `index_tokens(t)` or the name initials. The place is in the posting list of each of its words, with stored term frequency `1` plus the name flag, and in the list of each prefix key (5.6.1) of 2 to 6 characters of each of its words other than the name initials. ### 6.5 Field length The _field length_ of a place is the number of distinct written words in its search text before the first language mark `U+001F`: 1. Take the text before the first `U+001F`. 2. Remove each apostrophe (`'`, `U+2019`) that has a word character just before and just after it. 3. Split at every character that is not a _word character_ (a letter, a digit, or a combining mark of General Category `Mn`, `Mc` or `Me`). 4. Fold each piece; count the distinct non-empty results. So a run of ideographs counts as one word, and names after the language mark do not lengthen the field. The _field-norm id_ is the index of the largest entry not above the field length in tantivy's 256-entry field-norm table (`tantivy/src/fieldnorm/code.rs`), whose entries are `0` to `40` exactly and then grow geometrically. The posting length byte is the field length capped at `255`. ### 6.6 Quantized position The reference writer orders spatial blocks (5.8.1) by the Hilbert index of the cell `(x, y)` with `x = round((clamp(lon, -180, 180) + 180) / 360 × 65534)` and `y = round((clamp(lat, -90, 90) + 90) / 180 × 65534)`, each `0` for a NaN coordinate. ### 6.7 Query side A reader SHOULD turn query text into terms the same way the writer did: 1. Remove each possessive `'s` (an apostrophe after a word character, then `s` or `S`, then the end or a non-word character). 2. Remove each apostrophe between two word characters. 3. Split at non-word characters (6.5); keep at most 12 pieces. 4. A piece with any CJK character gives `index_tokens(piece)`; any other gives `fold(piece)`. The word terms are looked up as they are; a prefix of the last query word (autocomplete) is looked up as the prefix key of its first 2 to 6 characters. ## 7 Reading over HTTP A reader that holds the file in object storage reads it with HTTP range requests (`Range: bytes=a-b`), and MAY merge requests for nearby ranges. The order below is what this format is laid out for. ### 7.1 Opening 1. Fetch bytes `0` to `511`: the file header and, since a file with a search part lists it first (2.6), the search header. Check the file header (2.6), find the `SRCH` entry, then check the search header's kind, feature bits and document count (3.2, 3.3). 2. Fetch the boot span (Chapter 4): from the term index's offset to the end of the record dictionary, both counted from the start of the search part. Keep the seven boot sections in memory. A reader MAY instead fetch a fixed first range (for example the first 64 KiB) and fetch the rest of the boot span only when the header shows it is longer. The boot span is small for small files, and tens of megabytes for a planet. ### 7.2 Search and autocomplete 1. _Dictionary_: for each query term, find its dictionary block in the term index and fetch the blocks (one wave, in parallel). 2. _Postings_: for external terms, fetch the posting blocks the query needs, located by the skips, in as many waves as the reader's strategy takes. 3. _Records_: fetch the document blocks of the candidates, located by the document index, to read their records. ### 7.3 Reverse geocoding and boxes 1. Choose the spatial-directory nodes whose box meets the search area and fetch their second-level entries. 2. Fetch the spatial blocks whose box meets the area. 3. Fetch the document blocks of the places kept. ### 7.4 Lookup by id 1. Choose the id-directory nodes that may hold the ids (5.9.2) and fetch their second-level entries. 2. Fetch the id blocks that may hold the ids. 3. Fetch the document blocks of the matching fingerprints, and, for shapes, the shape blocks (5.10), in the same wave. ## 8 Ranking (informative) Ranking is implementation-defined. This chapter describes the reference reader so that the fields above make sense; nothing here constrains a conforming reader. The reference reader ranks a place by `BM25 + name bonus + phrase bonus + importance weight × importance`. BM25 is tantivy's (`k1 = 1.2`, `b = 0.75`, length normalised by the field-norm id against the header's average field length, `idf = ln(1 + (N - df + 0.5) / (df + 0.5))`); terms in a tenth of the documents or more score zero. The name bonus is `3.0` times the share of query words found with the name flag; the phrase bonus is `2.0` times the share of neighbouring query-word pairs found next to each other, in order, in the name. Every query word is required first; if that finds too few places, about three quarters of them. Posting lengths, importances and the chunks bound a candidate's rank so that most candidates are ruled out without their records; records give the exact rank. ## 9 Conformance A conforming **writer**: - writes the file header of 2.6, with each part's checksum; - writes the search header of Chapter 3 with every required feature bit, and an optional bit exactly when the governed section uses that encoding; - lays the sections out as Chapter 4 orders; - writes each section in the layout of Chapter 5, and every term by the rules of Chapter 6. A conforming **reader**: - refuses files as 2.6 and Chapter 3 require, and supports both encodings of each optional bit; - locates its part through the part table, every section through the section table, and every block through its directory; - decodes every block of Chapter 5, refusing a block that is cut short or inconsistent where this specification says so, rather than reading it as empty; - does not depend on the reference writer's block sizes, orders or head choices where this specification marks them as the writer's choice. The files in [`fixtures/`](/glx/fixtures/fixtures.json) are written by the reference writer. [`fixtures/fixtures.json`](/glx/fixtures/fixtures.json) lists, for each, its header, its section table, the number of dictionary and document blocks, the first records of its first document block, and queries with the ids the reference reader answers them with. `fixtures/describe.ts` (`node spec/v1/fixtures/describe.ts`) produces that file from the bytes with a decoder written from this document alone. ### 9.1 Notes - The magic ends in `0` while the version is `1`: the magic names the format, the version field names the specification (2.6). - Feature bits 8 (`SHAPES`) and 9 (`RECORD_DICTIONARY`) mean the sections exist, not that they are non-empty: a file without shapes, or too small to train a dictionary, still sets them. ## 10 Routing part The routing part holds a road graph cut into _graph tiles_: each tile holds the nodes, directed edges, edge shapes and names, access rules and turn restrictions of one cell of a grid. Each tile is stored as fixed-size _blocks_, each its own zstd frame, so a router reads only the parts of a tile a route touches and keeps the tile index in memory. A part may also hold a customizable contraction hierarchy per costing profile (10.5). ### 10.1 Graph tiles A graph tile is a byte string in the graph tile format of Valhalla 3.9.1 (commit `2085e78a517a0680a39d3b89efb7eff1f5cf9201`): a 272-byte tile header, then its records and sections in that format's order. This specification does not repeat that layout; the `geolith-routing` crate is the reference codec and is tested to reproduce reference tiles byte for byte. The tile header holds the offset of every section, and nodes, directed edges, transitions, access restrictions and signs are fixed-size records, so a reader that has the first block of a tile can compute the byte range of any record. Tiles sit on three grids, the _levels_: level `0` of 4° cells, level `1` of 1° cells and level `2` of 0.25° cells, each covering longitudes −180 to 180 and latitudes −90 to 90, with cells numbered row by row from the south-west. A tile's _key_ is the `u32` `level | cell << 3`, the low 25 bits of the format's graph id; the key orders tiles by level, then cell. ### 10.2 Layout The routing header is at offset `0` of the routing part. It is 64 bytes, or 80 when the part sets feature bit `0`: | Offset | Size | Type | Field | | -----: | ---: | :----------------- | :---------------------------- | | `0` | 4 | bytes | Kind | | `4` | 4 | `u32` | Block size | | `8` | 4 | `u32` | Features | | `12` | 4 | `u32` | Tile count | | `16` | 48 | 3 × (`u64`, `u64`) | Section table | | `64` | 16 | (`u64`, `u64`) | CCH directory (feature bit 0) | - _Kind_: always `ROUT` in ASCII. A reader MUST refuse a routing part whose kind field is not `ROUT`. - _Block size_: the bytes of tile data per block, `B`. It MUST be a power of two from `4096` (4 KiB) to `16777216` (16 MiB); a reader MUST refuse any other value. The reference writer uses `65536` (10.4). - _Features_: bit `0` (`CCH`) means the part holds a customizable contraction hierarchy (10.5) and the header ends with the CCH directory's (offset, length). No other bit is defined; writers MUST write `0` for them and readers MUST refuse a part that sets any. A reader that only routes over tiles MAY ignore the CCH sections, but it MUST still read the 80-byte header to find the boot span. - _Tile count_: the number of tiles, `T`. - _Section table_: three (offset, length) pairs, each counted from the start of the routing part, for the sections below in this order. Every section MUST lie inside the part. | Number | Section | Boot | | -----: | :-------------- | :--: | | `0` | Tile index | yes | | `1` | Tile dictionary | yes | | `2` | Tiles | | The boot sections follow the routing header back to back: the tile index, the tile dictionary and, with feature bit `0`, the CCH directory, so that one range request fetches the header and the boot span; the tiles follow them, then the CCH sections. A reader MUST refuse a part whose CCH directory does not directly follow the tile dictionary. A reader that does not yet know the features fetches the first 80 bytes. **Tile index**: `T` entries of 16 bytes, in ascending key order with no key twice: | Offset | Size | Type | Field | | -----: | ---: | :---- | :----------------- | | `0` | 4 | `u32` | Key | | `4` | 4 | `u32` | Tile length | | `8` | 4 | `u32` | First frame length | | `12` | 4 | `u32` | Stored length | - _Tile length_: the graph tile's length in bytes, `L`. The tile has `N = ceil(L / B)` blocks. - _First frame length_: the length of block `0`'s frame; `0` if and only if `L` is `0`. - _Stored length_: the length of the tile's stored bytes (below); `0` when `L` is `0`, and otherwise at least `4 N` plus the first frame length. A reader MUST refuse an index whose length is not `16 T`, whose keys do not ascend, or whose entry breaks a rule above. Tiles are stored in index order with no gaps, so a tile's offset in the tiles section is the sum of the stored lengths before it; a reader computes these sums once, when it opens the part, and MUST refuse an index whose stored lengths do not add up to the tiles section's length. **Tile dictionary**: a zstd dictionary that every block frame is compressed with; empty when the tiles use none. **Tiles**: for each tile, its _block directory_, then its `N` block frames in block order with no gaps. - _Block directory_: `N` `u32` values, the length of each block's frame. Every length is at least `1`. A reader MUST refuse a directory whose lengths, plus `4 N`, do not add up to the stored length, or whose first length differs from the index's first frame length. - _Block `b`_ holds tile bytes `b B` up to `min((b + 1) B, L)`: every block but the last holds exactly `B` bytes. Its frame is one zstd frame (2.5), with the tile dictionary when it is not empty, and MUST decompress to exactly those bytes; a reader MUST refuse a frame that decompresses to any other length. The directory and the first frame are adjacent, so one range request fetches both: the _head_ of a tile, at the tile's offset with length `4 N` plus the first frame length. Block `0` holds the 272-byte tile header because `B` is at least 4096. ### 10.3 Reading 1. Fetch the file header (2.6) and find the `ROUT` entry. 2. Fetch the routing header and the boot span; check the kind, the block size, the features and the tile index, and keep the index and the dictionary in memory. 3. For each tile a route search needs, find its key in the index (binary search) and fetch its head. A missing key means the cell has no roads. Block `0` gives the tile header and so the offset of every section. 4. To read tile bytes `s` up to `s + n`, fetch and decompress the blocks `floor(s / B)` to `floor((s + n − 1) / B)` the reader does not hold; their frames lie at the tile's offset plus `4 N` plus the sum of the directory lengths before them. A reader MAY drop blocks it no longer needs and fetch them again later, and MAY coalesce the frames of adjacent blocks into one range request. A reader MUST treat every graph tile as untrusted input: a record that points outside the tile, or past the end of a section, is refused, never read in part. ### 10.4 Block size (informative) A Cloudflare Worker has 128 MB per isolate. Valhalla maps whole tiles into memory, which needs the page cache of a server; a Worker has no file to map, so a router that decompresses whole tiles holds them whole on its heap. Berlin's largest tiles are 47 MB and 53 MB; with one frame per tile, a route over Berlin held a median of 121 MB of tile bytes (157 MB at most) plus up to 50 MB of frames, and 87 of 100 test routes ran out of memory. The search part solves the same problem with blocks behind a directory (5.4), and PMTiles with a directory of independently compressed tiles fetched by range; this chapter applies the same pattern inside a tile. Measured over the 100 auto routes of the router's reference test (Berlin, seed 42), counting every byte the router reads: snapping touches a few hundred kilobytes of a tile (edge bins, nearby nodes and edges, under 1% of edge info), but the search touches up to 81% of the nodes and directed edges of the largest tile, and trip building reads at most 30 KB of edge info and 1.5 KB of names. Splitting a tile into a _graph_ frame (every section before edge info) and paged edge info therefore does not bound memory: the graph sections of the tiles a route touches reach 130 MB. Paging the whole tile does: | Block size | Blocks per route (median / max) | Tile bytes held (median / max) | Part size vs one frame per tile | | ---------: | ------------------------------: | -----------------------------: | ------------------------------: | | 4 KiB | 5,084 / 9,937 | 19.9 / 38.8 MiB | +13.5 % | | 16 KiB | 1,470 / 2,747 | 23.0 / 42.9 MiB | +2.8 % | | 64 KiB | 444 / 781 | 27.7 / 48.7 MiB | −0.1 % | | 256 KiB | 146 / 233 | 36.3 / 58.0 MiB | −1.3 % | At 64 KiB the part is as small as with one frame per tile, a route holds at most 48.7 MiB of decompressed blocks (under 64 MiB, with room for the frames in flight), and the blocks of a tile are adjacent, so a reader coalesces them into few requests. Readers that need a tighter bound drop blocks (10.3, step 4). ### 10.5 Customizable contraction hierarchy With feature bit `0`, a routing part also holds, for each of one or more costing _profiles_ (`auto`, `pedestrian`, `bicycle`), a customizable contraction hierarchy (CCH; Dibbelt, Strasser and Wagner, ACM JEA 21, 2016) of that profile's metric over the part's graph, so a router answers a route by reading the records of the endpoints' ancestors instead of searching the tiles. Every profile is independent: its own vertices, order and sections. **Vertices and weights.** A profile's vertices are the directed edges it may use, one per internal-turn state a search label on the edge can carry, plus a copy of each edge on the via chain of a complex turn restriction; an arc is a turn the profile's forward search may take, weighted by the transition cost plus the entered edge's cost. A vertex's _rank_ is its position in a nested-dissection order; ranks number the vertices `0` to `V − 1`. Weights are the costs in units of the profile's _weight scale_ milli cost units, rounded up, at least `1`; the hierarchy is exact on these weights. The cost of a route is recomputed from the graph tiles; the weights only choose it. **CCH directory** (a boot section): | Offset | Size | Type | Field | | -----: | ------: | :----------------------- | :------------------ | | `0` | 4 | `u32` | Profile count `P` | | `4` | 4 | `u32` | Tile count `T` | | `8` | 4 (T+1) | `u32` | Tile edge positions | | | 88 P | profile entries | Profiles | | | 8 × all | (`u32`, `u32`) per block | Block tables | - _Tile count_ MUST equal the routing header's. - _Tile edge positions_: for each tile in index order, the _edge position_ of its directed edge `0`, then the total number of directed edges `E`; ascending. Edge `i` of the tile at index position `k` has edge position `positions[k] + i`. - _Profile entry_: the name (16 bytes ASCII, padded with zero bytes, at least one byte), `u32` vertex count `V`, `u32` weight scale, `u32` block counts of its three sections (vertex map, records, road lists), `u32` reserved `0`, then each section's (`u64` offset, `u64` length) from the start of the part. - _Block tables_: for each profile in order and each of its three sections, one (`u32` first item, `u32` frame length) per block. The _items_ are edge positions for the vertex map and ranks otherwise. The first items MUST start at `0` and ascend, each below the section's item count (`E`, or `V`); block `b` holds items from its first item to the next block's (or the item count). Frames are stored in block order with no gaps and MUST add up to the section's length. A reader refuses a directory whose lengths do not add up or that has bytes left over. Each block is one zstd frame without a dictionary that decompresses to at most 16 MiB; the reference writer ends a block after the item that brings it to 64 KiB. A block's items are encoded back to back as LEB128 varints; _zig-zag_ maps a signed delta `d` to `(d << 1) ^ (d >> 63)`. **Vertex map**, one entry per edge position: the number of ranks `k` (`0` when the profile cannot use the edge); then the first rank (the edge's own vertex, no internal turn, not a copy) and `k − 1` zig-zag deltas of the others; then, when `k > 0`, the _ancestor runs_: the union of the elimination-tree ancestors of those ranks, each rank included, as a run count and per run the gap from the previous run's end (from `0` for the first; at least `1` after it) and the run length minus one. **Records**, one per rank `r`: the _kept_ up directions (the reduced query graph after perfect customization: the arcs to higher ranks a shortest path may take, travelled `r → h`), then the kept down directions (travelled `h → r`). Each list is a count, then per arc the head's delta from the previous head (from `r` for the first; at least `1`) and the weight. **Road lists**, per rank `r`: the counts of its kept up and down directions, then for each of them in record order the directed edges entered along it, start excluded, in travel order: a count, then the first raw graph id and zig-zag deltas of the rest. **Reading a route.** Snap the endpoints to edges (10.3); read their vertex-map entries; read the records of every rank in the sources' ancestor runs and in the targets' (one parallel wave), search upwards from both sides and take the best common ancestor; read the road lists of the path's arcs (a second wave); read the tiles for those edges (a third wave). A reader MUST treat every CCH block as untrusted: a head that does not ascend, a rank outside `V`, a run that overflows or a list cut short is refused.