nodedb_array/tile/
layout.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Tile layout — mapping cell coordinates to tile boundaries.
4//!
5//! Tile coordinates are cell coordinates integer-divided by the
6//! schema's `tile_extents`. The space-filling-curve prefix is computed
7//! over the *tile* coordinates (not cell coordinates), so cells in the
8//! same tile share a [`TileId::hilbert_prefix`].
9
10use crate::coord::encode::encode_tile_prefix_with_order;
11use crate::coord::normalize::{bits_per_dim, normalize_coord};
12use crate::error::{ArrayError, ArrayResult};
13use crate::schema::ArraySchema;
14use crate::schema::dim_spec::{DimSpec, DimType};
15use crate::types::TileId;
16use crate::types::coord::value::CoordValue;
17use crate::types::domain::DomainBound;
18
19/// Compute the per-dim tile index for one cell coordinate.
20pub fn tile_indices_for_cell(schema: &ArraySchema, coord: &[CoordValue]) -> ArrayResult<Vec<u64>> {
21    if coord.len() != schema.arity() {
22        return Err(ArrayError::CoordArityMismatch {
23            array: schema.name.clone(),
24            expected: schema.arity(),
25            got: coord.len(),
26        });
27    }
28    let mut out = Vec::with_capacity(schema.arity());
29    for (i, dim) in schema.dims.iter().enumerate() {
30        let extent = schema.tile_extents[i];
31        let cell = &coord[i];
32        let lo = &dim.domain.lo;
33        let off = match (dim.dtype, cell, lo) {
34            (DimType::Int64, CoordValue::Int64(v), DomainBound::Int64(lo))
35            | (DimType::TimestampMs, CoordValue::TimestampMs(v), DomainBound::TimestampMs(lo)) => {
36                if v < lo {
37                    return out_of_domain(schema, dim.name.as_str(), "below domain_lo");
38                }
39                let delta = (*v as i128) - (*lo as i128);
40                (delta as u128 / u128::from(extent)) as u64
41            }
42            (DimType::Float64, CoordValue::Float64(v), DomainBound::Float64(lo)) => {
43                if !v.is_finite() || v < lo {
44                    return out_of_domain(
45                        schema,
46                        dim.name.as_str(),
47                        "below domain_lo or non-finite",
48                    );
49                }
50                ((v - lo) as u64) / extent
51            }
52            (DimType::String, CoordValue::String(s), DomainBound::String(_)) => {
53                // Strings have no natural tile-extent semantics — bucket
54                // by hash modulo extent for stable grouping.
55                crate::coord::string_hash::hash_string_modulo(s, extent.max(1))
56            }
57            _ => {
58                return Err(ArrayError::CoordOutOfDomain {
59                    array: schema.name.clone(),
60                    dim: dim.name.clone(),
61                    detail: "coord variant does not match dim dtype".to_string(),
62                });
63            }
64        };
65        out.push(off);
66    }
67    Ok(out)
68}
69
70/// Compute the [`TileId`] for one cell coordinate at a given system
71/// time. Non-bitemporal callers pass `system_from_ms = 0`; bitemporal
72/// writes supply the leader-stamped HLC component.
73pub fn tile_id_for_cell(
74    schema: &ArraySchema,
75    coord: &[CoordValue],
76    system_from_ms: i64,
77) -> ArrayResult<TileId> {
78    let tile_indices = tile_indices_for_cell(schema, coord)?;
79    let prefix = tile_prefix(schema, &tile_indices)?;
80    Ok(TileId::new(prefix, system_from_ms))
81}
82
83/// The space-filling-curve key of the tile at `tile_indices`.
84///
85/// The memtable, the segment index, the transaction overlay and retention
86/// group cells by this key. A cluster routes a tile by the top bits of
87/// `fmix64(key)` (`nodedb_types::array_route::prefix_bucket`), not by the
88/// key's own top bits. Every cell inside a group stays addressed by its
89/// full coordinate: a lookup matches the coordinate within the group
90/// (`TileBuffer::get_cell_bytes`, `extract_cell_bytes`), and a tile's MBR
91/// is built from the cells it holds. Two tiles that share a key therefore
92/// share one group and one route, and lose no cell.
93///
94/// A dimension whose tile count fits its share of the key bits scales each
95/// index over that count to the full bit width. Its tiles keep distinct,
96/// ordered keys. A dimension with more tiles than its bits can number, such
97/// as one with the default full-range domain, keeps the low bits of the
98/// index instead. Nearby tiles then keep distinct keys, and tiles `2^bits`
99/// apart share one. Such keys can share their top bits, and the routing mix
100/// still spreads them over buckets.
101pub fn tile_prefix(schema: &ArraySchema, tile_indices: &[u64]) -> ArrayResult<u64> {
102    if tile_indices.len() != schema.arity() {
103        return Err(ArrayError::CoordArityMismatch {
104            array: schema.name.clone(),
105            expected: schema.arity(),
106            got: tile_indices.len(),
107        });
108    }
109    let bits = bits_per_dim(schema.arity());
110    let scaled: Vec<u64> = tile_indices
111        .iter()
112        .zip(schema.dims.iter().zip(schema.tile_extents.iter()))
113        .map(|(index, (dim, extent))| scale_tile_index(*index, tiles_per_dim(dim, *extent), bits))
114        .collect();
115    encode_tile_prefix_with_order(schema, &scaled, bits)
116}
117
118/// The key of the tile that holds the cell at `coord`: the key every
119/// cluster path routes the cell by. Fails when `coord` lies outside the
120/// schema's domain.
121pub fn cell_tile_prefix(schema: &ArraySchema, coord: &[CoordValue]) -> ArrayResult<u64> {
122    normalize_coord(schema, coord, bits_per_dim(schema.arity()))?;
123    tile_prefix(schema, &tile_indices_for_cell(schema, coord)?)
124}
125
126/// The number of tiles along `dim` for tile extent `extent`. Mirrors how
127/// [`tile_indices_for_cell`] numbers them: a cell in the domain has a tile
128/// index below this count.
129pub fn tiles_per_dim(dim: &DimSpec, extent: u64) -> u128 {
130    let extent = u128::from(extent.max(1));
131    match (dim.dtype, &dim.domain.lo, &dim.domain.hi) {
132        (DimType::Int64, DomainBound::Int64(lo), DomainBound::Int64(hi))
133        | (DimType::TimestampMs, DomainBound::TimestampMs(lo), DomainBound::TimestampMs(hi)) => {
134            let span = ((*hi as i128) - (*lo as i128)).max(0) as u128;
135            span / extent + 1
136        }
137        (DimType::Float64, DomainBound::Float64(lo), DomainBound::Float64(hi)) => {
138            if hi.is_finite() && lo.is_finite() && hi > lo {
139                u128::from((hi - lo) as u64) / extent + 1
140            } else {
141                1
142            }
143        }
144        (DimType::String, DomainBound::String(_), DomainBound::String(_)) => extent,
145        _ => 1,
146    }
147}
148
149/// Map tile index `index` of `tiles` tiles to `[0, 2^bits)`.
150///
151/// With `tiles <= 2^bits` the index is scaled over the tile count, so
152/// distinct indices keep distinct, ordered values. An index past the last
153/// tile, a cell above the domain, takes the top value. With more tiles the
154/// index keeps its low `bits` bits.
155fn scale_tile_index(index: u64, tiles: u128, bits: u32) -> u64 {
156    let limit: u128 = 1u128 << bits.min(64);
157    let max = limit - 1;
158    if tiles > limit {
159        return u64::try_from(u128::from(index) & max).unwrap_or(u64::MAX);
160    }
161    if tiles <= 1 {
162        return if index == 0 { 0 } else { max as u64 };
163    }
164    let scaled = (u128::from(index) * max / (tiles - 1)).min(max);
165    u64::try_from(scaled).unwrap_or(u64::MAX)
166}
167
168fn out_of_domain<T>(schema: &ArraySchema, dim: &str, detail: &str) -> ArrayResult<T> {
169    Err(ArrayError::CoordOutOfDomain {
170        array: schema.name.clone(),
171        dim: dim.to_string(),
172        detail: detail.to_string(),
173    })
174}
175
176#[cfg(test)]
177mod tests {
178    use super::*;
179    use crate::schema::ArraySchemaBuilder;
180    use crate::schema::attr_spec::{AttrSpec, AttrType};
181    use crate::schema::dim_spec::DimSpec;
182    use crate::types::domain::Domain;
183    use nodedb_types::array_route::prefix_bucket;
184
185    fn schema() -> ArraySchema {
186        ArraySchemaBuilder::new("g")
187            .dim(DimSpec::new(
188                "x",
189                DimType::Int64,
190                Domain::new(DomainBound::Int64(0), DomainBound::Int64(99)),
191            ))
192            .dim(DimSpec::new(
193                "y",
194                DimType::Int64,
195                Domain::new(DomainBound::Int64(0), DomainBound::Int64(99)),
196            ))
197            .attr(AttrSpec::new("v", AttrType::Int64, false))
198            .tile_extents(vec![10, 10])
199            .build()
200            .unwrap()
201    }
202
203    #[test]
204    fn tile_indices_floor_by_extent() {
205        let s = schema();
206        let t = tile_indices_for_cell(&s, &[CoordValue::Int64(7), CoordValue::Int64(15)]).unwrap();
207        assert_eq!(t, vec![0, 1]);
208    }
209
210    #[test]
211    fn cells_in_same_tile_share_prefix() {
212        let s = schema();
213        let t1 = tile_id_for_cell(&s, &[CoordValue::Int64(0), CoordValue::Int64(0)], 0).unwrap();
214        let t2 = tile_id_for_cell(&s, &[CoordValue::Int64(9), CoordValue::Int64(9)], 0).unwrap();
215        assert_eq!(t1.hilbert_prefix, t2.hilbert_prefix);
216    }
217
218    #[test]
219    fn cells_in_different_tiles_have_different_prefixes() {
220        let s = schema();
221        let t1 = tile_id_for_cell(&s, &[CoordValue::Int64(0), CoordValue::Int64(0)], 0).unwrap();
222        let t2 = tile_id_for_cell(&s, &[CoordValue::Int64(50), CoordValue::Int64(50)], 0).unwrap();
223        assert_ne!(t1.hilbert_prefix, t2.hilbert_prefix);
224    }
225
226    #[test]
227    fn tile_keys_spread_over_routing_buckets() {
228        let s = schema();
229        let buckets: std::collections::BTreeSet<u32> = (0..10)
230            .flat_map(|x| (0..10).map(move |y| (x * 10, y * 10)))
231            .map(|(x, y)| {
232                let key = tile_id_for_cell(&s, &[CoordValue::Int64(x), CoordValue::Int64(y)], 0)
233                    .unwrap()
234                    .hilbert_prefix;
235                prefix_bucket(key, 8)
236            })
237            .collect();
238        // 100 tiles over 256 buckets: well over half of them distinct.
239        assert!(
240            buckets.len() >= 60,
241            "the tiles of one array route to {} buckets",
242            buckets.len()
243        );
244    }
245
246    fn full_range_2d() -> ArraySchema {
247        ArraySchemaBuilder::new("open")
248            .dim(DimSpec::new(
249                "x",
250                DimType::Int64,
251                Domain::new(DomainBound::Int64(i64::MIN), DomainBound::Int64(i64::MAX)),
252            ))
253            .dim(DimSpec::new(
254                "y",
255                DimType::Int64,
256                Domain::new(DomainBound::Int64(i64::MIN), DomainBound::Int64(i64::MAX)),
257            ))
258            .attr(AttrSpec::new("v", AttrType::Int64, false))
259            .tile_extents(vec![1, 1])
260            .build()
261            .unwrap()
262    }
263
264    /// The tiles of coordinates 0..64 x 0..64 in a full-range 2-D array
265    /// share their key's top bits, yet spread over the routing buckets.
266    #[test]
267    fn full_range_tiles_near_zero_spread_over_routing_buckets() {
268        let s = full_range_2d();
269        let keys: Vec<u64> = (0..64)
270            .flat_map(|x| (0..64).map(move |y| (x, y)))
271            .map(|(x, y)| {
272                cell_tile_prefix(&s, &[CoordValue::Int64(x), CoordValue::Int64(y)]).unwrap()
273            })
274            .collect();
275        let distinct: std::collections::BTreeSet<u64> = keys.iter().copied().collect();
276        assert_eq!(distinct.len(), 4096, "every tile keeps a distinct key");
277        let buckets: std::collections::BTreeSet<u32> =
278            keys.iter().map(|&k| prefix_bucket(k, 8)).collect();
279        // 4096 distinct keys over 256 buckets reach at least 7/8 of them.
280        assert!(
281            buckets.len() >= 224,
282            "4096 tiles route to only {} of 256 buckets",
283            buckets.len()
284        );
285    }
286
287    #[test]
288    fn every_tile_keeps_a_distinct_key() {
289        let s = schema();
290        let keys: std::collections::BTreeSet<u64> = (0..10)
291            .flat_map(|x| (0..10).map(move |y| (x * 10, y * 10)))
292            .map(|(x, y)| {
293                tile_id_for_cell(&s, &[CoordValue::Int64(x), CoordValue::Int64(y)], 0)
294                    .unwrap()
295                    .hilbert_prefix
296            })
297            .collect();
298        assert_eq!(keys.len(), 100);
299    }
300
301    #[test]
302    fn a_cell_routes_by_its_tile_key() {
303        let s = schema();
304        let coord = [CoordValue::Int64(37), CoordValue::Int64(81)];
305        assert_eq!(
306            cell_tile_prefix(&s, &coord).unwrap(),
307            tile_id_for_cell(&s, &coord, 0).unwrap().hilbert_prefix
308        );
309        assert_eq!(
310            cell_tile_prefix(&s, &[CoordValue::Int64(30), CoordValue::Int64(89)]).unwrap(),
311            cell_tile_prefix(&s, &coord).unwrap(),
312            "cells of one tile route together"
313        );
314    }
315
316    #[test]
317    fn a_cell_outside_the_domain_has_no_route() {
318        let s = schema();
319        assert!(cell_tile_prefix(&s, &[CoordValue::Int64(100), CoordValue::Int64(0)]).is_err());
320    }
321
322    #[test]
323    fn a_cell_above_the_domain_takes_the_last_key() {
324        let s = schema();
325        let above = tile_id_for_cell(&s, &[CoordValue::Int64(150), CoordValue::Int64(0)], 0)
326            .unwrap()
327            .hilbert_prefix;
328        let last = tile_id_for_cell(&s, &[CoordValue::Int64(99), CoordValue::Int64(0)], 0)
329            .unwrap()
330            .hilbert_prefix;
331        assert_eq!(above, last);
332    }
333
334    #[test]
335    fn nearby_tiles_of_a_full_range_dimension_keep_distinct_keys() {
336        let s = ArraySchemaBuilder::new("open")
337            .dim(DimSpec::new(
338                "x",
339                DimType::Int64,
340                Domain::new(DomainBound::Int64(i64::MIN), DomainBound::Int64(i64::MAX)),
341            ))
342            .dim(DimSpec::new(
343                "y",
344                DimType::Int64,
345                Domain::new(DomainBound::Int64(i64::MIN), DomainBound::Int64(i64::MAX)),
346            ))
347            .attr(AttrSpec::new("v", AttrType::Int64, false))
348            .tile_extents(vec![10, 10])
349            .build()
350            .unwrap();
351        let keys: std::collections::BTreeSet<u64> = (0..10)
352            .flat_map(|x| (0..10).map(move |y| (x * 10, y * 10)))
353            .map(|(x, y)| {
354                tile_id_for_cell(&s, &[CoordValue::Int64(x), CoordValue::Int64(y)], 0)
355                    .unwrap()
356                    .hilbert_prefix
357            })
358            .collect();
359        assert_eq!(keys.len(), 100, "a schema with any domain builds");
360    }
361
362    #[test]
363    fn system_from_ms_propagates() {
364        let s = schema();
365        let t = tile_id_for_cell(&s, &[CoordValue::Int64(0), CoordValue::Int64(0)], 1234).unwrap();
366        assert_eq!(t.system_from_ms, 1234);
367    }
368}
nodedb_array/tile/layout.rs

nodedb_array/tile/
layout.rs
