mikerhodes commented on code in PR #4410: URL: https://github.com/apache/couchdb/pull/4410#discussion_r1091968959
########## src/docs/rfcs/018-mango-covering-json-index.md: ########## @@ -0,0 +1,360 @@ +--- +name: Formal RFC +about: Submit a formal Request For Comments for consideration by the team. +title: 'Support covering indexes when using Mango JSON (view) indexes' +labels: rfc, discussion +assignees: '' + +--- + +[NOTE]: # ( ^^ Provide a general summary of the RFC in the title above. ^^ ) + +# Introduction + +## Abstract + +[NOTE]: # ( Provide a 1-to-3 paragraph overview of the requested change. ) +[NOTE]: # ( Describe what problem you are solving, and the general approach. ) + +Covering indexes are used to reduce the time the database takes to respond to +queries. An index "covers" a query when the query only requires fields that are +in the index (in this way, "covering" is a property of index and query +combined). When this is the case, the database doesn't need to consult primary +data and can return results for the query from only the index. In more familiar +CouchDB terminology, this is equivalent to querying a view with +`include_docs=false`. + +When evaluating a query, Mango currently doesn't use the concept of covering +indexes; even if a query could be answered without reading each result's full +JSON document, Mango will still read it. This makes it impossible for Mango to +return data as quickly as the underlying view. + +My benchmarking shows that Mango can answer at the same rate as the underlying +view index. It currently runs at the same pace as calling the view with +`include_docs=true`. Preliminary modifications to Mango showed that, with +covering index support and a query that can use it, Mango can stream results +as quickly as the underlying view. Adding covering indexes therefore increases +the production use-cases Mango can support substantially. + +There are likely two phases to this: + +- Enable covering indexing processing for current indexes (ie, over view keys). +- Allow Mango view indexes to include extra data from documents, storing it in + the `value` of the view. Support use of this extra data within the covering + indexes feature. + +### Out of scope + +This proposal only covers adding covering indexes to JSON indexes and not text +indexes. The aim is to reduce the need for CouchDB users to run separate +processes, such as Lucene, to get improved querying performance and capability. + +We do not aim to replicate `reduce` functionality from views, only to bring +parity to non-reduced view execution speed (ie, when views are used to search +the document space) to Mango. + +## Requirements Language + +[NOTE]: # ( Do not alter the section below. Follow its instructions. ) + +The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", +"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this +document are to be interpreted as described in +[RFC 2119](https://www.rfc-editor.org/rfc/rfc2119.txt). + +## Terminology + +[TIP]: # ( Provide a list of any unique terms or acronyms, and their definitions here.) + +- Mango: CouchDB's Mongo inspired querying system. +- View / JSON index: Mango index that uses the same index as Cloudant views. +- Coordinator: the erlang process that handles doing a distributed query across + a CouchDB cluster. + +--- + +# Detailed Description + +[NOTE]: # ( Describe the solution being proposed in greater detail. ) +[NOTE]: # ( Assume your audience has knowledge of, but not necessarily familiarity ) +[NOTE]: # ( with, the CouchDB internals. Provide enough context so that the reader ) +[NOTE]: # ( can make an informed decision about the proposal. ) + +[TIP]: # ( Artwork may be attached to the submission and linked as necessary. ) +[TIP]: # ( ASCII artwork can also be included in code blocks, if desired. ) + +This would take place within `mango_view_cursor.erl`. The key functions +involved are the shard-level `view_cb/2`, the streaming result handler at the +coordinator end (`handle_message/2`) and the `execute/3` function. + +## Mango JSON index selection + +A Mango JSON index is implemented as a view with a complex key. The first field +in the index is the first entry in the complex key, the second field is the +second key and so on. Even indexes with one field use a complex key with length +`1`. + +When choosing a JSON index to use for a query, there are a couple of things that +are important to covering indexes. + +Firstly, note there are certain predicate operators that can be used with an +index, currently: `$lt`, $lte`, `$eq`, $gte` and `$gt`. These can easily be +converted to key operations within a key ordered index. For an index to be +chosen for a query, the first key within the indexes complex key MUST be used +with a predicate operator that can be converted into an operation on the index. + +Secondly, a quirk of Mango indexes is that for a document to be included in an +index it must contain all of the index's indexed fields. Documents without all +the fields will not be included. This means that when we are choosing an index +for a query, we must further choose an index where the predicates within the +`selector` imply `$exists=true` for all fields in the index's key. Without that, +we will have incomplete results. + +Why is this? Let's look at an index with these fields: + +```json +["age", "name"] +``` + +Now we index two documents. The first document is included in the index while the second is not (because it doesn't include `name`): + + +```json +{"_id": "foo", "age": 39, "name": "mike"} + +{"_id": "bar", "age": 39, "pet": "cat"} +``` + +The `selector` `{"age": {"$gt": 30}}` should return both documents. However, if +we use the index above, we'd miss out `bar` because it's not in the index. +Therefore we can't use the index. + +On the other hand, the `selector` `{"age": {"$gt": 30}, "name": +{"$exists"=true}}` requires that the `name` field exist so the index can be used +because the query predicates can only match documents containing both `age` and +`name`, just like the index. In both cases, note the predicate `"age": {"$gt": +30}` implies `"age": {"$exists"=true}`. + +## Phase 1: handle keys only covering indexes + +Within `execute/3` we will need to decide whether the view should be requested +to include documents. If the index is covering, this will not be required and +so the `include_docs` argument to the view fabric call will be `false`. We'll +need to add a helper method to return whether the index is covering. + +When selecting an index, we'll need to ensure that only fields in the `selector` +and not `fields` are used when choosing an index. This is because we need all +fields in the `selector` to be present per [Mango JSON index +selection](#mango-json-index-selection). This is because `fields` is only used +after we generate the result set, and none of the field names in `fields` need +to exist in result documents. + +As an example, an index `["age", "name"]` would still require the `selector` to +imply `$exists=true` for both `age` and `name` even if the `fields` were just +`["age"]` in order that correct results be returned. + +Of note, this means that if an index is unusable pre-covering-index support, it +will continue to be unusable after this implementation: whether an index covers +a query is only used to prefer one already usable index over another. + +Within `view_cb/2`, we'll need to know whether an index is covering. Without +that, `view_cb/2` will interpret the lack of included documents as an indicator +that it should do nothing, while in fact we want it to fully process the result +as it does when `include_docs` is used -- apart from when the user passes `r>=2` +in the Mango query because then the coordinator reads and processes documents. +(Aside: it'd be good to remove this `r` option to simplify things). + +In `handle_message/2` the main work is ensuring that we handle mixed cluster +version states -- ie, cluster state during upgrades. + +## Phase 2: add support for included fields in indexes + +I propose we add an `include` field into a Mango JSON index definition: + +```json +{ + "index": { + "fields": [ "age", "name" ], + "include": [ "occupation", "manager_id" ] + }, + "name": "foo-json-index", + "type": "json" +} +``` + +Behaviour requirements: + +- Unlike `fields`, the fields in `include` _do not have to exist_ in the source + document in order that the document be included in the index. This is to + allow the index to cover more queries. +- Including a deeply nested field would follow the same pattern as for other Review Comment: Goodness -- great point :tada: I think that we could validate the length of the list of fields when the ddoc is updated, rather than failing during indexing. We could also limit the depth by counting the `.` characters. One thing we can only validate at index time are things like the length of included strings. I think here that we might want to place a limit on the total size of the values, say 32kb. Even that's quite a few disk pages, though hopefully they are sequential on disk so the kernel's prefilling the page cache ahead of us. Given it's easier to start with limits and increase them later, perhaps we should think about this more deeply. In a view we allow ~anything I believe, but here potentially we could be more conservative. As an example, [postgres](https://www.postgresql.org/docs/current/limits.html) limits indexes to 32 columns. Its max field size is 1GB; I think we'd like something a little smaller 😬 Are there other limits here? My thought is that we do limit, and make it configurable, and perhaps start relatively low for the defaults: - `mango_json_index_include_fields_max=16` (why 16? Powers of two always sound nice) - `mango_json_index_include_depth_max=8` - `mango_json_index_include_size_bytes_max=32768` (32kb) We can enforce `mango_json_index_include_fields_max` and `mango_json_index_include_depth_max` in `_index`. (We may have to belt-and-braces this as the user can go behind Mango's back to upload views that are the "right shape"). `mango_json_index_include_size_bytes_max` would need to be checked per document at index time. I worry what the behaviour should be here -- I see options of marking the whole index bad; having rows with "missing" values fields, meaning complexity during query; skipping indexing the document entirely. I lean towards skipping the doc as the least likely to cause unpredictable behaviour, but what's the current behaviour for views if indexing a doc fails? -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
