$or and $in operators do not seem to be using indices

[roedoejet]

Description

This seems similar to #2236, #1852, #1552 and #1549 but the solutions there don't seem to fix anything for me.

I have a small test database full of French conjugations (7300 records). Each conjugation should be able to be queried on the verb root, pronoun (aka agent), and some temporal option.

Here is a reasonable example query:

{
   "selector": {
      "input.root": "aimer",
      "input.agent": {
         "$in": [
            "2-sg",
            "1-sg"
         ]
      },
      "input.option": {
         "$in": [
            "conditionnel-present",
            "indicatif-present"
         ]
      }
   },
   "use_index": "foo-json-index"
}

If I run this without any indexing, the performance is (expectedly) bad and I get this helpful message:

So, I'm indexing on verb root like so:

 "type": "json",
 "partitioned": false,
 "def": {
  "fields": [
   {
    "input.root": "asc"
   }
  ]
 }

If I run the query again, this dramatically improves the search time:

However, if I then use the $in operator (I also tried the $or operator) then the search time skyrockets to 4-6 seconds:

Steps to Reproduce

I supplied the steps above - I am using Fauxton for all of my testing/debugging.

Here is the explain json for the query:

{
 "dbname": "data",
 "index": {
  "ddoc": "_design/3d80683e2f768bc271c5998a4bd8f03f7fe3802c",
  "name": "foo-json-index",
  "type": "json",
  "partitioned": false,
  "def": {
   "fields": [
    {
     "input.root": "asc"
    }
   ]
  }
 },
 "partitioned": false,
 "selector": {
  "$and": [
   {
    "input.root": {
     "$in": [
      "aimer",
      "etre"
     ]
    }
   },
   {
    "input.agent": {
     "$in": [
      "2-sg",
      "1-sg"
     ]
    }
   },
   {
    "input.option": {
     "$in": [
      "conditionnel-present",
      "indicatif-present"
     ]
    }
   }
  ]
 },
 "opts": {
  "use_index": [],
  "bookmark": "nil",
  "limit": 25,
  "skip": 0,
  "sort": {},
  "fields": "all_fields",
  "partition": "",
  "r": [
   49
  ],
  "conflicts": false,
  "stale": false,
  "update": true,
  "stable": false,
  "execution_stats": false
 },
 "limit": 25,
 "skip": 0,
 "fields": "all_fields",
 "mrargs": {
  "include_docs": true,
  "view_type": "map",
  "reduce": false,
  "partition": null,
  "start_key": [],
  "end_key": [
   "<MAX>"
  ],
  "direction": "fwd",
  "stable": false,
  "update": true,
  "conflicts": "undefined"
 }
}

Note that the start_key is empty and the end_key is <MAX>. If it's just one root being looked up, I instead get

"start_key": [
   "aimer"
  ],
  "end_key": [
   "aimer",
   "<MAX>"
  ]

Expected Behaviour

I would expect that there would be some interpretation of the query to first pull each indexed root and then run the remaining option and agent conditions on those indices, but instead, it appears to just run all of these conditions on every record in the database.

To hack my way around this (following #2236 (comment)), if my api receives multiple root values, I split them up, run individual queries and then join them before returning the response, but surely there must be a more relaxing way :)

Your Environment

couchdb: "Welcome",
version: "3.0.0",
git_sha: "03a77db6c",
uuid: "35461b15ec6019d5ff392ef60b9d8a82",
features: [
"access-ready",
"partitioned",
"pluggable-storage-engines",
"reshard",
"scheduler"
],
vendor: {
name: "The Apache Software Foundation"
}
}

• Browser name and version: Chrome Version 81.0.4044.129
• Operating system and version: Mac OS 10.14.6

[wohali]

Can you share your specific index definition?

[wohali]

This looks like a duplicate of #2236 on further reflection. @willholley 's response there is accurate:

The query engine will iterate through the index with include_docs=true and evaluate each document individually against the query selector in series.

And as @garrensmith says:

An $or operator also can't always use an index unless both sides of the $or have the same fields.

I don't think we can improve this, but I'll leave it open for a bit to see if anyone has any ideas.

[roedoejet]

Can you share your specific index definition?

{
   "index": {
      "fields": [
         "input.root"
      ]
   },
   "name": "foo-json-index",
   "type": "json"
}

[roedoejet]

An $or operator also can't always use an index unless both sides of the $or have the same fields.

Unless I'm misunderstanding something, I thought that's what I tried with $or:

{
   "selector": {
      "$or": [
         {
            "input.root": "aimer"
         },
         {
            "input.root": "etre"
         }
      ],
      "input.agent": {
         "$in": [
            "2-sg",
            "1-sg"
         ]
      },
      "input.option": {
         "$in": [
            "conditionnel-present",
            "indicatif-present"
         ]
      }
   }
}

But the same thing happens, it appears to be searching through each record:

[wohali]

Every field in your query must be contained in the index.

[roedoejet]

Every field in your query must be contained in the index.

In order to use $or or $in every field in the query must be indexed?

If I change my index to:

{
   "index": {
      "fields": [
         "input.root",
         "input.agent",
         "input.option"
      ]
   },
   "name": "root-agent-option-json-index",
   "type": "json"
}

It still doesn't use my index:

[wohali]

I can't speak to the or/in portion specifically (I believe the comments from the other devs indicate you'll never get this work for those), but I can say that if your selector included input.root, input.agent, and input.option (as static single values) your index must also include all 3 of those fields for it to be selected at query time. If I understand correctly, that is :)

[roedoejet]

your index must also include all 3 of those fields for it to be selected at query time

Hm, OK, in that case I guess I'm confused as to why adding the index for just input.root made such a drastic improvement on my initial query:

Index

{
   "index": {
      "fields": [
         "root.input"
      ]
   },
   "name": "foo-json-index",
   "type": "json"
}

Before adding Index above

After adding Index above

[wohali]

I'll hand it over to @garrensmith or @willholley who are in UTC-ish timezones and will respond tomorrow.

[roedoejet]

I'll hand it over to @garrensmith or @willholley who are in UTC-ish timezones and will respond tomorrow.

Thanks, I really appreciate your time looking at this!

[willholley]

@roedoejet json indexes basically don't have any support for the $in operator today - they require some kind of range query in the selector in order to use an index.

One option is to install the text index plugin, which will give you native $in support via Lucene indexes.

[roedoejet]

@roedoejet json indexes basically don't have any support for the $in operator today - they require some kind of range query in the selector in order to use an index.

One option is to install the text index plugin, which will give you native $in support via Lucene indexes.

OK, thanks for this. I would love to see this documented here. There is already a note about the regex operator not accepting indices, so I assumed that was the only operator to note wrt indices.

What about my example with $or?

[willholley]

The basic behaviour for json indexes is that if an $or operator is used and there is no other operator that allows an index to be selected, a full database scan is performed. There is no support for parallel or even multiple index scans when servicing a single query.

iirc (@garrensmith can confirm, there is an optimization, whereby if all of the $or clauses reference the same field (or set of fields), then an index containing exactly those fields will be used in preference to a full database scan. This is because the index is guaranteed to include all the documents in the database with those fields present.

Text indexes can again be more efficient for this as they have richer support for disjoint selectors.

[nkev]

For reference, I found this by @garrensmith where he says the $in operator does use an index in some cases. It would be nice to get an update on this.

[garrensmith]

The $in can be used in an index. Say for the example of the index:

{
   "index": {
      "fields": [
         "root.input"
      ]
   },
   "name": "foo-json-index",
   "type": "json"
}

With selector:

{
   selector: {
     input.root: "aimer",
     input.option: {
       $in: ["option1", "option2"]
    }
   }
}

Mango will choose the above index because you have input.root in your selector. Then when it reads the docs from the index it will filter them out based on your fields in the $in section.

In another case if you had an index like this:

{
   "index": {
      "fields": [
         "input.option"
      ]
   },
   "name": "foo-json-index",
   "type": "json"
}

And the same query:

{
   selector: {
     input.root: "aimer",
     input.option: {
       $in: ["option1", "option2"]
    }
   }
}

Then mango will read everything from the input.option index and then filter each document with the full selector.
The better option is to have the first index as it will reduce the number of documents that need to be fetched from the index.
Hope that clears it up a bit more.

[nkev]

Thanks for the clarification Garren. One thing though, you have root.input in the first code snippet and input.root afterwards. Is that a typo?
Also, will this all be the same in CouchDB V4?

[garrensmith]

Yes it will Get Outlook for iOS<https://aka.ms/o0ukef>

…

________________________________ From: Nuri <[email protected]> Sent: Friday, July 17, 2020 7:26:11 AM To: apache/couchdb <[email protected]> Cc: garren smith <[email protected]>; Mention <[email protected]> Subject: Re: [apache/couchdb] $or and $in operators do not seem to be using indices (#2856) Thanks for the clarification Garren. Will this all be the same in CouchDB V4? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#2856 (reply in thread)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AABL2ATO7LA5VNYVI6Y6IADR37OHHANCNFSM4O5R4YAA>.