Indexes over JSON data based on Fulltext index

Implementing MDEV-38306 (Optimizer support for Multi-Valued indexes over JSON data)
has MDEV-25848 (Support for Multi-Valued Indexes) as a prerequisite.

Until that is implemented, it's possible to index JSON data using the existing fulltext index, with custom fulltext parser.

See https://github.com/MariaDB/server/commit/9d9fd65b519 (denote POC-COMMIT-1) for the example

This MDEV covers what we need to do on top of that to provide JSON indexing functionality.
We will need to:

• Translate INDEX(json_col) into appropriate fulltext index.
• Provide a fulltext parser.
• Extract fulltext search commands from JSON conditions
• TODO: fulltext searches currently do not use cost-based searches. Anything we could/should do here?

How we use fulltext indexes

For a complete description of the full-text search syntax see https://mariadb.com/docs/server/ha-and-performance/optimization-and-tuning/optimization-and-indexes/full-text-indexes/full-text-index-overview

It is less expressive than regexp.

Specifically we can use the index to search for exact word matches:

-- Exact match

SELECT * FROM t WHERE MATCH(col) AGAINST ('search_word' IN BOOLEAN MODE);

Note that we can also use it to search for prefixes:

-- Prefix search

SELECT * FROM t WHERE MATCH(col) AGAINST ('search_word*' IN BOOLEAN MODE);

Basic JSON object member searches.

For a JSON object with members:

{

  "memb1": "val1",

  "memb2": 345,

  "memb3": true,

  "memb4": false,

  "memb5": null

}

according to the POC-COMMIT-1, we write "key=value" into the index:

  memb1=val1

  memb2=345

  memb3=true

  memb4=false

  memb5=null

This allows for exact searches like:

-- Use JSON_VALUE

select * from t where JSON_VALUE(col, '$.memb1')='val1'

-- Use JSON_EXTRACT

select * from t where JSON_EXTRACT(col, '$.memb1')='val1'

-- Another way : JSON_UNQUOTE(JSON_EXTRACT(...)))

select * from t where JSON_UNQUOTE(JSON_EXTRACT((col, '$.memb1')='val1';

-- Don't need JSON_UNQUOTE if we know the value doesn't need quoting:

select * from t where JSON_EXTRACT(col, '$.memb1')=123;

TODO: which collation does the comparison use?

Note that -> and ->> are aliases to JSON_EXTRACT and JSON_UNQUOTE(JSON_EXTRACT(...)) used with two arguments, respectively. JSON_VALUE and JSON_EXTRACT do slightly different things. For example JSON_VALUE cannot return a json array, and JSON_ARRAY can take multiple paths and return an json array:

MariaDB [test]> SELECT JSON_VALUE('{"a": [30, 40]}', '$.a');

+--------------------------------------+

| JSON_VALUE('{"a": [30, 40]}', '$.a') |

+--------------------------------------+

| NULL                                 |

+--------------------------------------+

1 row in set (0.001 sec)

MariaDB [test]> SELECT JSON_EXTRACT('{"a": [30, 40]}', '$.a');

+----------------------------------------+

| JSON_EXTRACT('{"a": [30, 40]}', '$.a') |

+----------------------------------------+

| [30, 40]                               |

+----------------------------------------+

1 row in set (0.001 sec)

MariaDB [test]> SELECT JSON_EXTRACT('[10, 20, [30, 40]]', '$[0]', '$[1]');

+----------------------------------------------------+

| JSON_EXTRACT('[10, 20, [30, 40]]', '$[0]', '$[1]') |

+----------------------------------------------------+

| [10, 20]                                           |

+----------------------------------------------------+

1 row in set (0.001 sec)

TODO: any issues with lax json processing? See below "note about boxing and unboxing" . We have incorrect behavior but indexing seems easier with it...

Nested JSON object members.

We can just write "foo.bar=value" for those and support fully-qualified paths like JSON_VALUE(..., '$.foo.bar').

Here we make a conscious decision to not support "search-anywhere" paths like $**.foo.

Handling JSON Arrays.

TODO: does it actually make sense to provide support for searches for "JSON_VALUE(..., '$.array[100]')=foo" ? These do not seem to be meaningful.

(Perhaps, if the array is something like "names of students ordered by exam marks", then one could use this to get the name of the 3rd best performing student)

It is meaningful to search for "$.array[*] contains value VAL". What condition do we use for this ? MySQL has MEMBER OF for this. We don't have it, do we have an alternative? Can JSON_CONTAINS be used? Yes, except there's no way to tell that the object is an array:

MariaDB [test]> select json_contains('{"a": 34}', '34', '$.a');

+-----------------------------------------+

| json_contains('{"a": 34}', '34', '$.a') |

+-----------------------------------------+

|                                       1 |

+-----------------------------------------+

1 row in set (0.001 sec)

MariaDB [test]> select json_contains('{"a": [12, 34, 56]}', '34', '$.a');

+---------------------------------------------------+

| json_contains('{"a": [12, 34, 56]}', '34', '$.a') |

+---------------------------------------------------+

|                                                 1 |

+---------------------------------------------------+

1 row in set (0.001 sec)

MariaDB [test]> select json_contains('{"a": [12, 34, 56]}', '34', '$.a[*]');

+------------------------------------------------------+

| json_contains('{"a": [12, 34, 56]}', '34', '$.a[*]') |

+------------------------------------------------------+

|                                                 NULL |

+------------------------------------------------------+

1 row in set, 1 warning (0.001 sec)

The implementation POC-COMMIT-1 translates

{

  "arr": [12, 34, 56]

}

to

  arr.0=12

  arr.1=34

  arr.2=56

General issues of the current ft json parser:

1. Index vs keys ambiguity. arr.1=val could match {"1": "val"}, or ["abc", "val", ...].
2. Type ambiguity: j.x=1 could match {"x": 1} or {"x": "1"}, true vs "true", null vs "null"
3. Delimiter ambiguity: "." and "=" could be part of keys or values
4. Different representations of the same numerical value: 1 vs 1.0 vs 1e1 are different

These ambiguities result in false positives, which can be fixed by two ways:

1. Verify and filter
2. Improve design of ft parser to increase precision:

• • For Index vs keys ambiguity, we could do arr[1]=val instead of arr.1=val (INDEX-WITH-BRACKET). Alternatively, if we do not care about the actual index of an element, do arr[]=val instead (INDEX-EMPTY-BRACKET)
  • For type ambiguity, we could quote json types (QUOTE-JSON-TYPES): {"x": "1"} => .x="1", {"x\"y": "a\"b"} => .x"y="a\"b". This also fixes index vs keys ambiguity and delimiter ambiguity on the rhs
  • For delimiter ambiguity, this can be fixed for the rhs by quoting, otherwise we could add escaping "." and "=" when they appear in the json documents: {"x.y=z": "a.b=c"} => {.x\.y\=z=a\.b\=c}

Translate MVI to fulltext parser

CREATE TABLE t (id, info JSON, INDEX ((CAST(info->'$.zipcode' AS UNSIGNED ARRAY))));

translates to, internally, creating fulltext json parser on info->'$.zipcode'.

In fact, the ft json index does not require casting to UNSIGNED ARRAY.

JSON function support

JSON_CONTAINS

Problem: depth ambiguities:

JSON_CONTAINS(col->'$.a', 123) => a.*=123 matches both {"a": [123, 456]} (correct) and {"a": {"b": [123, 456]}} (false positive)

Idea: prefix lhs with depth. So instead of a.0=123 we generate 2.a.0=123, and instead of a.b.1=456 we generate 3.a.b.1=456.

JSON_CONTAINS(col->'$.a', '123') => (2.a.*=123 OR 1.a=123)
JSON_CONTAINS(col->'$.a', '123', '$.b') => (3.a.b.*=123 OR 2.a.b=123)

TODO: is there an OR operator in ft search? if not then need to send each disjunct and then union results. same for AND below

Still false positives from index vs keys ambiguity:

JSON_CONTAINS(col->'$.a', '123') => 2.a.*=123 matches {"a": {"b": 123}}. Can be resolved with INDEX-WITH-BRACKET (2.a[*]=123) or INDEX-EMPTY-BRACKET (2.a[]=123). Below we assume INDEX-WITH-BRACKET

Containing an array or object: break the rhs into conjunction of tokens

JSON_CONTAINS(col->'$.a', '[123, 456]') => 2.a[*]=123 AND 2.a[*]=456
JSON_CONTAINS(col->'$.a', '{"b": [123, 456], "c": 789}') => 3.a.b[*]=123 AND 3.a.b[*]=456 AND (3.a.c[*]=789 OR 2.a.c=789)

MEMBER OF

123 MEMBER OF (col->'$.a') => 2.a.[*]=123

JSON_OVERLAPS

Break one of the two json arguments into disjoint tokens, then query the other one:

JSON_OVERLAPS(j1, '{"b": [123, 456], "c": 789}') => construct 2.b[0]=123, 2.b[1]=456, 1.c=789 => query j1 with (2.b[\*]=123 OR 2.b[\*]=456 OR 1.c=789)

JSON_EXISTS

JSON_EXISTS(j, '$.x[5].y.z) => *.x[5].y.z=* OR *.x[5].y.z.*

TODO: do we have to worry about escaping the "*" character?

JSON_CONTAINS_PATH

JSON_CONTAINS_PATH can be translated to disjunction ("one") or conjunction ("all") of JSON_EXISTS

JSON_SEARCH

JSON_SEARCH(j, 'all', 123) => *=123

TODO: optimization for 'one', that is, just find one match for one row?

JSON_EXTRACT(...) = ...

The rhs is a json document. We could break it into tokens like in JSON_CONTAINS and combine with the path in the lhs, but there could be plenty of false positives because we are looking for "exactly these tokens" which requires filtering.

JSON_EXTRACT(j, "$.a[1]", "$.b.c") = [\{"d": 123\}, "e"] => 3.a[1].d=123 AND 2.b.c=e

in this example we need to filter out rows that not only produce these tokens but also, say, 3.a[1].f=456

TODO: Is there anyway to prevent false positives?

JSON_VALUE(...) = ...

The rhs is a sql value, but there could be implicit cast which requires some special handling. For example, the following holds

JSON_VALUE('{"a": [true, 34, 56]}', '$.a[0]') = 1

JSON_VALUE('{"a": [1, 34, 56]}', '$.a[0]') = 1

JSON_VALUE('{"a": ["1", 34, 56]}', '$.a[0]') = 1

So we have to generate a disjunct of these possible casts: 2.a[0]=1 OR 2.a[0]=true OR (in case of QUOTE-JSON-TYPES) 2.a[0]="1"

Other functions

JSON_VALUE(...) with no rhs or JSON_EXTRACT(...) with no rhs can done by generating corresponding tokens N.path=*

TODO: other functions? I've taken a look at list of JSON_* functions and don't see anything obvious.

A note about boxing and unboxing.

See MDEV-40746: JSON Path computation doesn't do lax mode unboxing

Wildcard index

The ft json parser stores all path-value pairs of a json document, essentially giving us a wildcard index as described in MDEV-37288.

Hooking this into the optimizer.

Should we produce special kind of "ranges" from JSON predicates? Or fulltext searches? Or even ref accesses?

(Don't ranges need require a JSON comparator?)

Goal #1: Compatibility with ARRAY indexes in MySQL

See MDEV-40741: Study MySQL's ARRAY indexing

Implementing this in MariaDB

MEMBER OF predicate is coming to MariaDB: See MDEV-38591, https://github.com/MariaDB/server/pull/5278

Goal #2: Wildcard-like indexes

TODO