osm-katana/examples/bboxcost.rs
//! **What the `covering.bbox` column costs, per variant — the evidence for
//! `spatial::COVERING_GRID_SHIFT`.**
//!
//! `nodes.parquet`'s covering column is 693.94 MB on the Sweden cut and half of it is
//! a byte-exact duplicate: for a Point `xmin == xmax` and `ymin == ymax`, bit for bit,
//! because the node coordinates the WKB carries are already exactly `f32`. This
//! re-encodes the REAL column through the REAL writer — parquet-rs 59, ZSTD, 8 192-row
//! groups, the row order left exactly as the packed file has it — so every number is
//! comparable to the per-column census rather than an estimate.
//!
//! | id | leaves | what it does |
//! |----------------|--------|-------------------------------------------------|
//! | `bss-nodict` | 4 | BYTE_STREAM_SPLIT, dictionary off (the SHIPPED encoding) |
//! | `plain-nodict` | 4 | PLAIN, dictionary off |
//! | `dict` | 4 | writer default (dictionary on) |
//! | `two-leaf` | 2 | drop `xmax`/`ymax` — the redundancy, exactly |
//! | `truncN` | 4 | keep the top N mantissa bits, rounded OUTWARD |
//! | `gridN` | 4 | snap onto an absolute `2^-N`° grid, OUTWARD |
//!
//! Measured 2026-08-31 on `nodes.parquet` (103 488 583 rows), compressed column bytes:
//! shipped 693.94 MB, PLAIN 1 002.38, dictionary-on 1 389.83, `two-leaf` 346.97,
//! `grid12` **344.55**. `two-leaf` and `grid12` cost the same bytes, but `two-leaf`
//! defeats korp's `mapquery::row_group_intersects` (it reads all four leaves by name
//! and returns `true` — scan — when one is missing), while `grid12` leaves the prune
//! bit-identical. That is the whole argument, and the numbers are why.
//!
//! `cargo run --release --example bboxcost -- <table.parquet> <outdir> [row_groups]`
use arrow::array::{Array, ArrayRef, Float32Array, Float32Builder, StructArray};
use arrow::datatypes::{DataType, Field, Fields, Schema};
use arrow::record_batch::RecordBatch;
use parquet::arrow::ArrowWriter;
use parquet::arrow::arrow_reader::ParquetRecordBatchReaderBuilder;
use parquet::basic::{Compression, Encoding};
use parquet::file::properties::WriterProperties;
use parquet::schema::types::ColumnPath;
use std::sync::Arc;
/// Keep the top `k` mantissa bits of an f32, rounding TOWARDS `-inf` (a bbox min).
fn trunc_down(v: f32, k: u32) -> f32 {
if !v.is_finite() {
return v;
}
let drop = 23 - k;
let mask = !((1u32 << drop) - 1);
let b = v.to_bits();
if v >= 0.0 {
f32::from_bits(b & mask)
} else {
// magnitude grows downward for negatives: round magnitude UP
let t = b & mask;
if t == b { v } else { f32::from_bits(t + (1 << drop)) }
}
}
/// Keep the top `k` mantissa bits of an f32, rounding TOWARDS `+inf` (a bbox max).
fn trunc_up(v: f32, k: u32) -> f32 {
if !v.is_finite() {
return v;
}
let drop = 23 - k;
let mask = !((1u32 << drop) - 1);
let b = v.to_bits();
if v >= 0.0 {
let t = b & mask;
if t == b { v } else { f32::from_bits(t + (1 << drop)) }
} else {
f32::from_bits(b & mask)
}
}
/// Round DOWN onto an absolute `2^-g` degree grid, then keep the f32 outward safety net.
fn grid_down(v: f32, g: u32) -> f32 {
let s = f64::from(v) * f64::from(1u32 << g);
let q = s.floor() / f64::from(1u32 << g);
let r = q as f32;
if f64::from(r) <= f64::from(v) { r } else { f32::from_bits(if r > 0.0 { r.to_bits() - 1 } else { r.to_bits() + 1 }) }
}
/// Round UP onto an absolute `2^-g` degree grid, then keep the f32 outward safety net.
fn grid_up(v: f32, g: u32) -> f32 {
let s = f64::from(v) * f64::from(1u32 << g);
let q = s.ceil() / f64::from(1u32 << g);
let r = q as f32;
if f64::from(r) >= f64::from(v) { r } else { f32::from_bits(if r >= 0.0 { r.to_bits() + 1 } else { r.to_bits() - 1 }) }
}
struct Variant {
id: &'static str,
leaves: &'static [&'static str],
encoding: Option<Encoding>,
dict: bool,
trunc: Option<u32>,
grid: Option<u32>,
}
fn field_for(leaves: &[&str]) -> Field {
Field::new(
"bbox",
DataType::Struct(Fields::from(
leaves
.iter()
.map(|n| Field::new(*n, DataType::Float32, true))
.collect::<Vec<_>>(),
)),
true,
)
}
fn main() -> Result<(), Box<dyn std::error::Error>> {
let mut a = std::env::args().skip(1);
let src = a.next().expect("usage: bboxcost <nodes.parquet> <outdir>");
let outdir = a.next().expect("usage: bboxcost <nodes.parquet> <outdir>");
let groups: Option<usize> = a.next().and_then(|s| s.parse().ok());
std::fs::create_dir_all(&outdir)?;
let variants = [
Variant { id: "bss-nodict", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: None },
Variant { id: "plain-nodict", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::PLAIN), dict: false, trunc: None, grid: None },
Variant { id: "dict", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: None, dict: true, trunc: None, grid: None },
Variant { id: "two-leaf", leaves: &["xmin", "ymin"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: None },
Variant { id: "trunc22", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: Some(22), grid: None },
Variant { id: "trunc20", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: Some(20), grid: None },
Variant { id: "trunc18", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: Some(18), grid: None },
Variant { id: "trunc16", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: Some(16), grid: None },
Variant { id: "trunc14", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: Some(14), grid: None },
Variant { id: "grid15", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: Some(15) },
Variant { id: "grid14", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: Some(14) },
Variant { id: "grid13", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: Some(13) },
Variant { id: "grid12", leaves: &["xmin", "ymin", "xmax", "ymax"], encoding: Some(Encoding::BYTE_STREAM_SPLIT), dict: false, trunc: None, grid: Some(12) },
];
let mut degenerate = 0u64;
let mut total_rows = 0u64;
for v in &variants {
let f = std::fs::File::open(&src)?;
let b = ParquetRecordBatchReaderBuilder::try_new(f)?;
let n_rg = b.metadata().num_row_groups();
let take: Vec<usize> = (0..groups.unwrap_or(n_rg).min(n_rg)).collect();
let mask = parquet::arrow::ProjectionMask::columns(b.parquet_schema(), ["bbox.xmin", "bbox.ymin", "bbox.xmax", "bbox.ymax"]);
let rdr = b.with_row_groups(take).with_projection(mask).with_batch_size(8192).build()?;
let schema = Arc::new(Schema::new(vec![field_for(v.leaves)]));
let mut pb = WriterProperties::builder()
.set_compression(Compression::ZSTD(Default::default()))
.set_max_row_group_row_count(Some(8192));
for leaf in v.leaves {
let p = ColumnPath::new(vec![String::from("bbox"), String::from(*leaf)]);
if let Some(e) = v.encoding {
pb = pb.set_column_encoding(p.clone(), e);
}
pb = pb.set_column_dictionary_enabled(p, v.dict);
}
let dst = format!("{outdir}/bbox-{}.parquet", v.id);
let mut w = ArrowWriter::try_new(std::fs::File::create(&dst)?, schema.clone(), Some(pb.build()))?;
let mut rows = 0u64;
let mut deg = 0u64;
for batch in rdr {
let batch = batch?;
let st = batch.column(0).as_any().downcast_ref::<StructArray>().expect("bbox is a struct");
let get = |n: &str| st.column_by_name(n).unwrap().as_any().downcast_ref::<Float32Array>().unwrap().clone();
let (xmin, ymin, xmax, ymax) = (get("xmin"), get("ymin"), get("xmax"), get("ymax"));
rows += xmin.len() as u64;
for i in 0..xmin.len() {
if !xmin.is_null(i) && xmin.value(i) == xmax.value(i) && ymin.value(i) == ymax.value(i) {
deg += 1;
}
}
let mut cols: Vec<ArrayRef> = Vec::new();
for leaf in v.leaves {
let (src_arr, is_max) = match *leaf {
"xmin" => (&xmin, false),
"ymin" => (&ymin, false),
"xmax" => (&xmax, true),
"ymax" => (&ymax, true),
_ => unreachable!(),
};
let mut bld = Float32Builder::with_capacity(src_arr.len());
for i in 0..src_arr.len() {
if src_arr.is_null(i) {
bld.append_null();
} else {
let x = src_arr.value(i);
let y = match v.trunc {
None => x,
Some(k) => if is_max { trunc_up(x, k) } else { trunc_down(x, k) },
};
bld.append_value(match v.grid {
None => y,
Some(g) => if is_max { grid_up(y, g) } else { grid_down(y, g) },
});
}
}
cols.push(Arc::new(bld.finish()) as ArrayRef);
}
let fields = match field_for(v.leaves).data_type().clone() {
DataType::Struct(f) => f,
_ => unreachable!(),
};
let st_out = StructArray::new(fields, cols, None);
w.write(&RecordBatch::try_new(schema.clone(), vec![Arc::new(st_out) as ArrayRef])?)?;
}
w.close()?;
if v.id == "bss-nodict" {
degenerate = deg;
total_rows = rows;
}
let bytes = std::fs::metadata(&dst)?.len();
println!("{:<14} leaves={} rows={rows:>11} file={:>12} B = {:>8.2} MB", v.id, v.leaves.len(), bytes, bytes as f64 / 1e6);
}
println!("\ndegenerate (xmin==xmax && ymin==ymax) rows: {degenerate} / {total_rows}");
Ok(())
}