High performance sorted queries
- Dominant language
- Rust
- Stars
- 48.2k
- Forks
- 4.8k
- Avg merge
- 3d 16h
- Merged PRs (30d)
- 171
Description
## What problem does this solve or what need does it fill?
#13417 adds sorting at an iterator level. These sorts:
- Do not persist across system runs (it will be common for sorted data to rarely be mutated).
- Make query iteration completely random access.
## What solution would you like?
1. Command to reorder tables.
2. Rearrange tables for sorted queries by default.
3. Make queries cache sorts & use change detection to early out of resorting.
4. Condense sorts to `low..=high` ranges for cache friendly iteration.
5. Optionally cache iteration position to allow suspending and resuming iteration between system runs. This is useful for ui scroll areas and any rhythm game.
Final API should look something like this:
```rs
fn cmp(left: FilteredEntityRef, right: FilteredEntityRef) -> std::cmp::Ordering {
left.get::().unwrap().cmp(&right.get::().unwrap())
}
fn sys(mut query: Query<(&A, &B)>) {
for (a, b) in query.sort(cmp)
// Optional call that will prevent tables from being reorderd.
// Useful if you have multiple systems requesting slightly different sorts or
// just completely opting out of reordering & doing multiple ordering manually.
// User could do multiple stable sorts to get dense iteration across multiple systems.
.no_reorder()
.iter()
{
// ..
}
}
#[derive(Component)]
struct Offset(pub f64);
fn sort_by_offset(left: FilteredEntityRef, right: FilteredEntityRef) -> std::cmp::Ordering {
left.get::().unwrap().0.cmp(&right.get::().unwrap().0)
}
fn seek_by_offset(entity: FilteredEntityRef, needle: f64) -> std::cmp::Ordering {
entity.get::().unwrap().0.cmp(&needle)
}
fn timeline(mut query: Query<(&Offset, &A, &B)>, time: Res
## What alternative(s) have you considered?
- Putting things in resources and doing these sorts myself. This is only viable when you've feature frozen your project and need no changes to data architecture. You completely lose the flexibility of ECS doing this.
- Despawning entities & reinserting them into tables. This first requires knowing all the components to take out of an entity and secondly relies on side effects. Table order is not part of the API contract.
## Additional context
Missing prerequisite features:
- `World::parallel_commands`/make the world command queue thread local by default (needed to allow queries to do `2.`).
- Archetype level change detection: #5097 (needed for `3.`).
Not required but helpful missing feature:
- Queries as entities (can avoid introducing the cache structure for queries that aren't sorted).
Contributor guide
Research direction
Start by reviewing #13417 and the listed prerequisites, especially World::parallel_commands and #5097. Assess how persistent table reordering, cached sorts, range condensation, and resumable seeking would fit the Query API. Done would require an agreed scope and API for these design points, followed by implementation and validation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- game-dev, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100