Indexes on Expressions

[AlexJMohr]

I'm trying to filter a table of cells for all cells in a 16x16 chunk, addressed by (chunk_x, chunk_y). Here is my table:

#[spacetimedb::table(name = cell, public, index(name = position, btree(columns = [x, y])))]
pub struct Cell {
    x: i32,
    y: i32,
    value: Option<i8>,
}

This does not compile:

let chunk_cells = ctx.db.cell().position().filter((
    chunk_x..(chunk_x + CHUNK_SIZE),
    chunk_y..(chunk_y + CHUNK_SIZE),
));

I was thinking an index on expression would be useful. In PostgreSQL you can create a btree index like this:

create index cell_position_idx on cell ((x / 16), (y / 16)); -- chunk size of 16

which would support a query like:

-- select cells where chunk = (1, 0)
select * from cell where x / 16 = 1 and y / 16 = 0;

relevant PostgreSQL docs: https://www.postgresql.org/docs/current/indexes-expressional.html

If I'm missing some obvious way of doing what I'm trying to do, please let me know 😅. I've considered just storing chunk_x and chunk_y in the table but that seems wasteful when it's computable from x and y.

[gefjon]

A BTree index cannot answer this query with only a single probe, as values in the range you're asking for are not necessarily contiguous when using lexicographic order on the tuple (x, y) - e.g. when querying for (0..16), (0..16), you'd potentially have the index storing the sequence (0, 15), (0, 30), (1, 0), (1, 4) - note how (0, 30) does not match, but is sorted between two elements which do match. If you only need to perform this query from module code, and your chunk size is small, you may want to perform 16 index probes in a loop, one for each x value. If you also need to perform this query from SQL, or your chunk size is actually larger than 16, then I'd recommend storing a single extra column chunk_id: u64, whose value is ((chunk_x as u64) << 32) | (chunk_y as u64), and filtering on that.

Rather than indexes on expressions, I think your use-case would be best solved by our adding spatial indexes, which can efficiently answer multi-dimensional range queries like the one you've listed.