# Algorithmic complexity of bool queries

**URL:** <https://discuss.elastic.co/t/algorithmic-complexity-of-bool-queries/258084>\
**Category:** Elasticsearch\
**Created:** [December 9, 2020, 7:38am UTC](https://discuss.elastic.co/t/algorithmic-complexity-of-bool-queries/258084 "2020-12-09T07:38:54Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![rex-remind](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/rex-remind/32/46637_2.png) [@rex-remind](https://discuss.elastic.co/u/rex-remind)\
**Post date:** [December 9, 2020, 7:38am UTC](https://discuss.elastic.co/t/algorithmic-complexity-of-bool-queries/258084/1 "2020-12-09T07:38:54Z")

</div>

I've been searching all over the net to get an understanding of the algorithmic complexity / rough big-O of bool queries for Elasticsearch, but I have come up dry so I'm asking here. (Note: this is not a question about correct query syntax, I will use psuedo-code that basically matches with the dsl for expediency.)

My use case - I have a query that has essentially a series of _ors_ (shoulds) and _ands_ (musts). To simplify I'll create a toy example:

```auto
query name='name' and filter: (x=['<uuid_1>', ...] and y=['<uuid_2>', ...]) or z='[<uuid_3>', ...])
order by name desc

```

where `x`, `y`, and `z` are keywords and `name` is text, `name` is in a `sort.field` with `sort.order`. `name` may be absent from some queries where we just filter.

In my use case x, y, and z all could contain one or more of half-a-billion values i.e. cardinality is 500,000,000. The number of documents is 500,000,000 as well.

We expect in the worst case for each `=` relation to match ~1 million documents.

So my question is, how can I reason about the performance? If this was just filtering on x and nothing more I'd expect it to be an O(1) fetch of 1 million uuids and it would just return the top 50 docs out of 1 million for 1 page which is pretty straight forward.

But how will a bool query like this operate? 3 x O(1) fetches and then join? How does the join happen? Does it need re-iterate over all the hits in memory and combine based on the bool logic? I'm really not sure.

I appreciate any insight here,  
thanks!

---

<div class="post-metadata">

**Author:** ![Mark\_Harwood](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/mark_harwood/32/10538_2.png) [@Mark\_Harwood](https://discuss.elastic.co/u/Mark_Harwood)\
**Post date:** [December 9, 2020, 8:46am UTC](https://discuss.elastic.co/t/algorithmic-complexity-of-bool-queries/258084/2 "2020-12-09T08:46:15Z")

</div>

Adrien Grand has done a lot of great talks on Lucene internals. Here’s one: [https://youtu.be/p51vIDWHWqk](https://youtu.be/p51vIDWHWqk)

His more recent work on [Block max WAND](https://www.elastic.co/blog/faster-retrieval-of-top-hits-in-elasticsearch-with-block-max-wand) is also of interest.

---

<div class="post-metadata">

**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\
**Post date:** [January 6, 2021, 8:46am UTC](https://discuss.elastic.co/t/algorithmic-complexity-of-bool-queries/258084/3 "2021-01-06T08:46:19Z")

</div>

This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.