# Must\_not in bool filter much slower than must for same terms filter
**URL:** https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479
**Category:** Elasticsearch
**Created:** [May 28, 2015, 2:42pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479 "2015-05-28T14:42:09Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [May 28, 2015, 2:42pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/1 "2015-05-28T14:42:09Z")
Is there any reason that a `must_not` clause would run a lot slower than a `must` clause in the same `bool` filter?
```auto
{
"query": {
"filtered": {
"filter": {
"bool": {
"must_not": {
"terms": {
"cs_grp": [
"beauty"
],
"execution": "bool"
}
}
}
}
}
},
"timeout": "60s",
"size": 0
}
```
Runs consistently in around 700ms but when you change that filter to `must` instead, it runs between 12ms and 50ms:
```auto
{
"query": {
"filtered": {
"filter": {
"bool": {
"must": {
"terms": {
"cs_grp": [
"beauty"
],
"execution": "bool"
}
}
}
}
}
},
"timeout": "60s",
"size": 0
}
```
From the docs I cannot understand why this would be. Using a `bool` `must_not`filter should be fast because it should use bitsets right?
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 6, 2015, 5:45pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/2 "2015-06-06T17:45:50Z")
Bumping this to see if it gets any attention. Surely something is wrong here?
---
### Author:  [@teamamerica](https://discuss.elastic.co/u/teamamerica)
#### Post date: [June 6, 2015, 9:08pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/3 "2015-06-06T21:08:17Z")
My understanding is bitsets play more of a role when you are looking over multiple filters. But think in term mapping. It is possible to construct a reverse mapping between maybe value =\> items that contain that value. I'm not too familiar with ES or Lucene internals but if they use this inverted index setup, that could be one reason why the postive query (which inverted index are great for) can be quicker then negative.
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 7, 2015, 9:21am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/4 "2015-06-07T09:21:43Z")
But @teamamerica, as far as I'm aware, a bitset will have 1s and 0s for whether the filter matches. So would it not be a quick operation to not that bitset logically and get a list of documents for which the filter doesn't match?
---
### Author:  [@Christian\_Dahlqvist](https://discuss.elastic.co/u/Christian_Dahlqvist)
#### Post date: [June 7, 2015, 9:42am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/5 "2015-06-07T09:42:36Z")
Is there a difference in the number of hits these two queries return?
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 7, 2015, 11:09am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/6 "2015-06-07T11:09:33Z")
@Christian_Dahlqvist yes there is.
For the `must` query
```auto
{
"took": 13,
"timed_out": false,
"_shards": {
"total": 120,
"successful": 120,
"failed": 0
},
"hits": {
"total": 638764,
"max_score": 0,
"hits": []
}
}
```
and for the `must_not` query:
```auto
{
"took": 604,
"timed_out": false,
"_shards": {
"total": 120,
"successful": 120,
"failed": 0
},
"hits": {
"total": 29226733,
"max_score": 0,
"hits": []
}
}
```
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 7, 2015, 12:15pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/7 "2015-06-07T12:15:54Z")
But @Christian_Dahlqvist, I can select the same 29226733 documents from the `must_not` query by using all the other possible values for that field in the `must` query and that consistently takes around 90ms. So the number of documents returned doesn't seem to explain the difference.
---
### Author:  [@jprante](https://discuss.elastic.co/u/jprante)
#### Post date: [June 7, 2015, 12:59pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/8 "2015-06-07T12:59:00Z")
`must_not` is translated into a `not` filter surrounding a `must` filter.
And/or/not filters are not translated into bitsets, see
> **[All About Elasticsearch Filter BitSets
| Elastic](https://www.elastic.co/blog/all-about-elasticsearch-filter-bitsets)**
>
> WARNING: This article contains outdated information. We no longer recommend taking its advice. When building queries in Elasticsearch, you’ll often find yourself composing sets of filters. Say you nee...
What you see is Elasticsearch traversing the posting lists (all values of the field) to look for those field values that does not match. This takes time proportional to the cardinality of the field. Especially on high cardinalty fields, `must_not` is a challenge.
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 7, 2015, 9:33pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/9 "2015-06-07T21:33:37Z")
So essentially if you want fast `must_not`s it would probably be quicker to do that `not`ing in application code and query elasticsearch with a `must` with a list of all possible values excluding the ones in `must_not`s?
---
### Author:  [@nik9000](https://discuss.elastic.co/u/nik9000)
#### Post date: [June 8, 2015, 10:18am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/10 "2015-06-08T10:18:31Z")
It doesn't look like must\_not translates it "must": {"not":{}}. must\_not is natively part of Lucene's BoleanQuery. The only thing I see is that Elasticsearch adds a match\_all query to the must if the query is only must\_not clauses. Presumably because BooleanQuery will find no results if its just must\_not clauses. I'd expect match\_all to be quick though. How fast as a simple match\_all query?
Do you have anything else in your query except the bool?
I'm curious now.
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 8, 2015, 10:28am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/11 "2015-06-08T10:28:11Z")
@nik9000 that's interesting, the `match_all` thing makes sense in order to get results back in the absence of any other filter. The queries I've posted are the exact ones I'm using. The field is `non_analyzed`, would you be able to replicate it on your cluster I wonder?
---
### Author:  [@nik9000](https://discuss.elastic.co/u/nik9000)
#### Post date: [June 8, 2015, 10:46am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/12 "2015-06-08T10:46:28Z")
I just tried with no luck - the one where I listed all the values took a bit longer. Both took just about the same amount of time as a match\_all. But I'm on 1.3 in production so it might be a new thing.
---
### Author:  [@jpountz](https://discuss.elastic.co/u/jpountz)
#### Post date: [June 8, 2015, 12:24pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/13 "2015-06-08T12:24:53Z")
`must_not` does indeed not translate to `"must": {"not":{}}`.
If you run a bool query with `must`/`should` and `must_not` clauses, Lucene will first create an iterator that matches the `must`/`should` clauses, and then if you have `must_not` clauses, this iterator will be wrapped in order to exclude documents that match any of these `must_not` clauses.
Let me take an example: you have 1M documents in your index, and 1000 of them contain `bar` in the `foo` field. If you want to find all documents that match `foo:bar`, Lucene will just iterate over the postings list of `foo:bar` and call the collector on it. So you would decode 1000 documents from your postings list and call the collector 1000 times. Now if you execute the same clause as a `must_not` filter and have a `match_all` query as a `must` clause, Lucene will iterate over all documents matching the `match_all` query, and for each of them check if they match `foo:bar` and should be excluded. So you have to check 1M times if the document matches `foo:bar` and call the collector 999000 times.
This is why when you have a boolean field, it is more efficient to encode `true` and `false` explicitely instead of only building an index for `true` and then searching for documents that have `false` as a value by searching for documents that don't have `true`.
> So essentially if you want fast must\_nots it would probably be quicker to do that noting in application code and query elasticsearch with a must with a list of all possible values excluding the ones in must\_nots?
This depends on how many possible values you are. If there are only a handful of them then this could help, but if there are thousands of possible values, this would not be an option.
---
### Author:  [@bobbyrenwick](https://discuss.elastic.co/u/bobbyrenwick)
#### Post date: [June 8, 2015, 2:04pm UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/14 "2015-06-08T14:04:19Z")
@jpountz, thanks for the explanation that's really really helpful.
We had about 13 unique values for this `cs_grp` field so having a list of the possible values sped us up a little. As our more permanent solution we have added an extra boolean field in order to handle the same logic. This allows us to `must` the field value as `true` or `false. But it does mean we have to do more at index time (and so a reindex for all our current data), but it should speed us up hugely.
Thanks again for the responses everyone!
---
### Author:  [@system](https://discuss.elastic.co/u/system)
#### Post date: [July 6, 2017, 12:09am UTC](https://discuss.elastic.co/t/must-not-in-bool-filter-much-slower-than-must-for-same-terms-filter/1479/15 "2017-07-06T00:09:01Z")