apache / apache/couchdb

Inefficient `$regex` Mango `view` queries on indexed fields

Open
#4,775 1 comment 0 reactions 0 assignees View on GitHub
enhancement mango
Dominant language
Erlang
Stars
7k
Forks
1.1k
Avg merge
1d 16h
Merged PRs (30d)
9

Description

On the Mango query interface, when the `$regex` operator is used in a selector with a field that could be backed up by a `view` (`json`) index, it is not leveraged. The use of `$regex` in its current form rather implies a brute-force scan through all the documents of the underlying view, which makes the whole approach inefficient and resource-intensive.

The source of the problem is that no index ranges could be computed for `$regex` (to narrow down the scan) because regular expressions do not naturally generate an ordering on the set of strings, like for example comparisons do on integers. However, there is a prior art in for example, Lucene where it is possible to achieve that for specialized cases, such as "starts with"-type of expressions, i.e. `^foo.*`.

Some more links about how Lucene does it, just for inspiration:
- https://lucene.apache.org/core/4_2_0/core/org/apache/lucene/search/RegexpQuery.html
- https://lucene.apache.org/core/4_2_0/core/org/apache/lucene/search/AutomatonQuery.html
- https://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html
- https://www.slideshare.net/otisg/finite-state-queries-in-lucene

Another factor that can slow down the evaluation is that documents are included unconditionally, and `$regex` is not matched against the key itself first and only documents for the matched keys are fetched and returned. Something along the lines of [covering indexes](https://github.com/apache/couchdb/issues/4413).

Contributor guide

Open the contributing guide

Research direction

Start with the Mango query interface and the behavior of `$regex` against `view` (`json`) indexes. Review the Lucene examples and the linked covering-index issue, then define and test a bounded optimization for suitable prefix expressions while avoiding unconditional inclusion of unrelated documents.

Written by the indexing model from the issue text.

Assessment

Tech stack
erlang
Domain
databases, performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.