Understanding bevy's Query & dynamic queries

[nicopap]

Dynamic query is an extension of the bevy Query system.

How Query works

First, we need to understand how Query works to understand the interest of dynamic queries.

The base Query rely on types to create a set of instructions that will create pointers to data stored in the ECS. Those pointers are converted into rust references of the type of the query.

Query relies on the WorldQuery trait to create the set of instructions. WorldQuery has a lot of methods. Those methods are used in query iteration and query initialization code. In the WorldQuery implementations, you'll notice that most of those methods are implemented as a simple constant, or no code at all. This is important, because whenever you write an actual "concrete" Query (for example Query<&Transform, With<FooBar>>) the methods concrete codes (which are very small snippets or constants) will be inserted wherever the methods of WorldQuery are used (the initialization and iteration code). You may see relatively complex and difficult to grok code, but the compiler actually sees simple code. With simple code, the compiler is capable of doing very good optimizations. In the end, the generated assembly code looks very close to a classic for loop!

Archetypes

To further understand WorldQuery implementations. You have to understand how the ECS is implemented.

Each Entity has a given set of components. All entities with the exact same set of components are gathered in a single "Archetype". A Query such as Query<(&Transform, &mut Sprite), With<Player>>, when initializing, computes the set of archetypes it needs to access. At runtime, as new components are added and removed from entities, new archetypes will show up, and bevy will also update the queries so that they can account for new archetypes.

The archetypes the query iterates over are stored by index in a FixedBitset. Basically, it's a bunch of 1s and 0s, in a list, and the bit index of 1s corresponds to an archetype the query must visit.

When iterating over a Query, the query will fetch by ID a single archetype. The archetype tells the query where the components are stored and how many of them there are. The Query will iterate over all components of an archetype, and when the archetype is fully iterated, it will look for the next archetype, iterate over the components of the next archetype, repeat until there is no more archetypes to read.

QueryState

Gathering archetypes is a costly operations, so it is "cached" (the term is often used in the bevy community) using the QueryState struct. Basically, when you have the QueryState, all that is left to do is to iterate over the archetypes (and update it when new archetypes are added to the world).

The QueryState is static, but depends entirely on the Query type. For example, Query<(&Transform, &Sprite)> will have a different QueryState than Query<Entity, (With<Transform>, With<Sprite>)>. Each WorldQuery has its own individual state optimized for itself. Some don't even store any state. This allows QueryState to be as small as it needs to be, to avoid needless extra work.

Limitations

Now, all is well. But, say, you want to create a Query at runtime: you can't know at compile time what items the query will contain, therefore, you can't make a Query.

But runtime queries are very useful. It is a building block of relations which is a very useful ECS feature. It is also needed for scripting languages to be able to interact sensibly and without too much overhead with the bevy ECS.

History of dynamic queries

The first attempt at creating dynamic queries was #6240. It was judged too unsafe and error-prone, and a counterproposal was opened as #6390. The author of #6240 closed it in favor of the counterproposal. Then #6390 languished without being merged, due in no small parts to the complexity and verbosity of the API. The author of the first attempt created a more limited version of #6390 that would be easier to review, #8308, but it was still insufficient.

This was the status quo for the better part of six months, and suddenly, two people started working on dynamic queries at the exact same time.

First nicopap (me) as a fork of the #6390 POC as bevy_mod_dynamic_query. I didn't communicate on it. Meanwhile, james-j-obrien started work on the same base at around the same time. Now we have two concurrent implementations of dynamic queries, cross-pollinating each other.

flowchart LR
    6240["2022-10-11 Original attempt by Suficio #6240"]
    6390["2022-10-27 Jakobhellermann safer #6390"]
    8308["2023-04-06 Suficio second cleanup #8308"]
    9774["2023-09-12 James-j-Obrien term-based refactor #9774"]
    dmdq["2023-09-10 nicopap's fork"]
    6240 --> 6390
    6390 --> 8308 & 9774 & dmdq

Loading

Dynamic queries implementations

I've personally reviewed #8308 and #6390, I took a very cursory glance at #9774.

There are two lines of implementations:

• The "reproduce WorldQuery trait impls as enum variants" implementations. This is how QueryState::new_with_state #6240 was implemented. Allow configuration of WorldQuery with runtime values #6390, WorldQuery::Config for dynamic queries #8308 and Dynamic queries and builder API #9774 follow the same architecture
• The dynamic archetype approach of bevy_mod_dynamic_query

Reproduce WorldQuery

The idea is to copy/paste WorldQuery implementations for the different types of WorldQuery as-is, and wrap those in enums. If you are reviewing one of those PRs, you should have in your editor the bevy_ecs/src/query/fetch.rs.

The advantage of this approach is that the current Query implementation is known to work and be fairly efficient. The disadvantage is that the current approach is optimized (both in terms of performance and code readability) for usage as a trait in generic context, so the code can be difficult to follow.

Dynamic Archetypes

When I forked the #6390 POC and finally grasped how queries work, I felt very dirty. I'm minimalist at heart, and it was heartbreaking to see such a complex approach.

One of the many advantage of the current Query implementation in bevy is the flexibility. You can do silly things like:

#[derive(WorldQuery)]
struct FooBar {
    foo: &'static Foo,
    bar: Option<&'static Bar>,
}
Query<
   ((&Fetch1, &mut Fetch2), (Entity, Option<&Fetch3>, FooBar), AnyOf<(&Boo, &Bah, &Dee)>),
   (Or<(With<Bee>, Without<Doo>)>, (With<Dah>, Or<(Without<Deh>, Without<Blee>)>))>,
>

Basically, you can nest arbitrary tuples of WorldQuery into other WorldQuerys and construct arbitrary types.

Pretty good for a type-based API! But completely useless when the types are taken out of the equation!

Unlike the base tuple-based API, one would necessarily use a slice, Vec or array with a dynamic query. Any other use would imply you already know the type of what you want to query, and therefore should be using the base Query system. Furthermore, there is no point in supporting nested Vec<Vec<Vec<…>>> in a dynamic query context, it would be just additional overhead without any benefit.

So paradoxically, to have dynamic queries, what we need is to accept less flexibility on one side to enable more flexibility on another.

My approach limited the dynamic query type as follow:

• The fetches list (ie: list of components you can access using for comp in &query, the first generic parameter of Query) will be a single flat list
• The filters (ie: the With, Or, etc. stuff, 2nd generic parameter of Query) will be a single Or (a DNF), any filter can be translated into DNF, and the DNF has advantages when it comes to resolving archetypes.

With those limitations in mind, I rewrote from scratch the #6390 POC and got a much cleaner implementation.

My DynamicQuery is split in two: Fetches and Filters, the state is unified for every kind of query:

pub struct DynamicQuery {
    pub(crate) fetches: Fetches,
    pub(crate) filters: Filters,
}
pub struct Fetches {
    pub(crate) has_entity: bool,
    // Equivalent to a `Vec<Vec<FetchComponent>>`, but with less indirection.
    pub(crate) components: JaggedArray<FetchComponent>,
}
pub struct FetchComponent {
    id: ComponentId,
    from_ptr: ReflectFromPtr,
}

pub struct Filters(JaggedArray<Filter>);
#[repr(u32)]
enum FilterKind {
    With = 0,
    Changed = 1,
    Added = 2,
    Without = 3,
}
pub struct Filter {
    /// This is an optimized `enum` where the variant discriminant is stored in
    /// the most significant two bits of `component`.
    component: u32,
}

pub struct DynamicState {
    pub(crate) fetches: Fetches,
    pub(crate) filters: Filters,
    pub(crate) archetype_ids: MatchedArchetypes,
}

How can I help?

I think dynamic queries are very close to mature in bevy now. It is likely that it will be present in bevy 0.13 in one form or another. All that is left is more eyes on the James-j-Obrien PR (or bevy_mod_dynamic_query).

Reviewers familiar with the bevy ECS should have a special look on the safety aspect.

Reviewers not familiar with the bevy ECS should, but interested in dynamic queries should try to make their use-case (supposedly they are interested in dynamic queries because they have a use-case) work with the PR's bevy fork, (or bevy_mod_dynamic_query) and report to James-j-Obrien or myself anything that prevents them from applying the implementation to their use-case.

[badcodecat]

I just wanted to link to https://bevyengine.org/news/bevy-0-13/#dynamic-queries for anyone else looking.