search

clockworklabs / SpacetimeDB

Multiplayer at the speed of light
https://spacetimedb.com
Other
4.07k stars 100 forks source link

Optimize expression evaluation #1113

Open joshua-spacetime opened 1 week ago

joshua-spacetime commented 1 week ago

Expression evaluation accounts for over a third of incremental query evaluation for certain performance benchmarks

Image

We should introduce a more optimized version of ColumnOp. This more optimal representation should have (1) row positions instead of field names, and (2) a flatter structure.

enum Expr {
    Pos(u32),
    Val(AlgebraicValue),
    BinStatic(u32, OpCmp, AlgebraicValue)
    BinDyn(Box<Expr>, OpCmp, Box<Expr>),
    Log(OpLogic, Vec<Expr>),
}

Every variant of Query that contains references to ColumnOp, we should replace with this new representation. Specifically the IndexJoin and Select variants.

Centril commented 1 week ago

We can also add a variant LogCmp(OpLogic, OpCmp, ColList, Vec<AlgebraicValue>), which is even more optimal for the common case of a = x && b = y, ... case.