[couchdb] 01/01: mango: add $beginsWith operator

[wi...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

willholley pushed a commit to branch mango-beginswith
in repository https://gitbox.apache.org/repos/asf/couchdb.git

commit 85e8a9d647ae5f3a11d43df311176ec2e7490507
Author: Will Holley <wi...@uk.ibm.com>
AuthorDate: Mon Oct 16 14:07:55 2023 +0000

    mango: add $beginsWith operator
    
    Adds a `$beginsWith` operator to selectors, with json and text index
    support. This is a compliment / precursor to optimising `$regex`
    support as proposed in https://github.com/apache/couchdb/pull/4776.
    
    For `json` indexes, a $beginsWith operator translates into a key
    range query, as is common practice for _view queries. For example,
    to find all rows with a key beginning with "W", we can use a range
    `start_key="W", end_key="W\ufff0"`. Given Mango uses compound keys,
    this is slightly more complex in practice, but the idea is the same.
    As with other range operators (`$gt`, `$gte`, etc), `$beginsWith`
    can be used in combination with equality operators and result sorting
    but must result in a contiguous key range. That is, a range of
    `start_key=[10, "W"], end_key=[10, "W\ufff0", {}]` would be valid,
    but `start_key=["W", 10], end_key=["W\ufff0", 10, {}]` would not,
    because the second element of the key may result in a non-contiguous
    range.
    
    For text indexes, `$beginsWith` translates to a Lucene query on
    the specified field of `W*`.
    
    If a non-string operand is provided to `$beginsWith`, the request will
    fail with a 400 / `invalid_operator` error.
---
 src/mango/src/mango_idx_view.erl      |   6 ++
 src/mango/src/mango_selector.erl      |  32 ++++++++++
 src/mango/src/mango_selector_text.erl |   3 +
 src/mango/test/03-operator-test.py    |  16 +++++
 src/mango/test/25-beginswith-test.py  | 112 ++++++++++++++++++++++++++++++++++
 5 files changed, 169 insertions(+)

diff --git a/src/mango/src/mango_idx_view.erl b/src/mango/src/mango_idx_view.erl
index 25d75d55d..d1650e987 100644
--- a/src/mango/src/mango_idx_view.erl
+++ b/src/mango/src/mango_idx_view.erl
@@ -306,6 +306,8 @@ indexable({[{<<"$gt">>, _}]}) ->
     true;
 indexable({[{<<"$gte">>, _}]}) ->
     true;
+indexable({[{<<"$beginsWith">>, _}]}) ->
+    true;
 % This is required to improve index selection for covering indexes.
 % Making `$exists` indexable should not cause problems in other cases.
 indexable({[{<<"$exists">>, _}]}) ->
@@ -412,6 +414,10 @@ range(_, _, LCmp, Low, HCmp, High) ->
 % operators but its all straight forward once you figure out how
 % we're basically just narrowing our logical ranges.
 
+% beginsWith requires both a high and low bound
+range({[{<<"$beginsWith">>, Arg}]}, LCmp, Low, HCmp, High) ->
+    {LCmp0, Low0, HCmp0, High0} = range({[{<<"$gte">>, Arg}]}, LCmp, Low, HCmp, High),
+    range({[{<<"$lte">>, <<Arg/binary, 16#10FFFF>>}]}, LCmp0, Low0, HCmp0, High0);
 range({[{<<"$lt">>, Arg}]}, LCmp, Low, HCmp, High) ->
     case range_pos(Low, Arg, High) of
         min ->
diff --git a/src/mango/src/mango_selector.erl b/src/mango/src/mango_selector.erl
index 59be7a6eb..c1b4d7c28 100644
--- a/src/mango/src/mango_selector.erl
+++ b/src/mango/src/mango_selector.erl
@@ -135,6 +135,8 @@ norm_ops({[{<<"$text">>, Arg}]}) when
     {[{<<"$default">>, {[{<<"$text">>, Arg}]}}]};
 norm_ops({[{<<"$text">>, Arg}]}) ->
     ?MANGO_ERROR({bad_arg, '$text', Arg});
+norm_ops({[{<<"$beginsWith">>, Arg}]} = Cond) when is_binary(Arg) ->
+    Cond;
 % Not technically an operator but we pass it through here
 % so that this function accepts its own output. This exists
 % so that $text can have a field name value which simplifies
@@ -514,6 +516,11 @@ match({[{<<"$mod">>, [D, R]}]}, Value, _Cmp) when is_integer(Value) ->
     Value rem D == R;
 match({[{<<"$mod">>, _}]}, _Value, _Cmp) ->
     false;
+match({[{<<"$beginsWith">>, Prefix}]}, Value, _Cmp) when is_binary(Prefix), is_binary(Value) ->
+    string:prefix(Value, Prefix) /= nomatch;
+% When Value is not a string, do not match
+match({[{<<"$beginsWith">>, Prefix}]}, _, _Cmp) when is_binary(Prefix) ->
+    false;
 match({[{<<"$regex">>, Regex}]}, Value, _Cmp) when is_binary(Value) ->
     try
         match == re:run(Value, Regex, [{capture, none}])
@@ -1054,4 +1061,29 @@ fields_nor_test() ->
     },
     ?assertEqual([<<"field1">>, <<"field2">>], fields_of(Selector2)).
 
+match_beginswith_test() ->
+    Doc =
+        {[
+            {<<"_id">>, <<"foo">>},
+            {<<"_rev">>, <<"bar">>},
+            {<<"user_id">>, 11}
+        ]},
+    Check = fun(Field, Prefix) ->
+        Selector = {[{Field, {[{<<"$beginsWith">>, Prefix}]}}]},
+        % Call match_int/2 to avoid ERROR for missing metric; this is confusing
+        % in the middle of test output.
+        match_int(mango_selector:normalize(Selector), Doc)
+    end,
+    [
+        % matching
+        ?assertEqual(true, Check(<<"_id">>, <<"f">>)),
+        % no match (user_id is not a binary string)
+        ?assertEqual(false, Check(<<"user_id">>, <<"f">>)),
+        % invalid (prefix is not a binary string)
+        ?assertThrow(
+            {mango_error, mango_selector, {invalid_operator, <<"$beginsWith">>}},
+            Check(<<"user_id">>, 1)
+        )
+    ].
+
 -endif.
diff --git a/src/mango/src/mango_selector_text.erl b/src/mango/src/mango_selector_text.erl
index 1f8609ac2..fc9280d85 100644
--- a/src/mango/src/mango_selector_text.erl
+++ b/src/mango/src/mango_selector_text.erl
@@ -142,6 +142,9 @@ convert(Path, {[{<<"$exists">>, ShouldExist}]}) ->
         true -> FieldExists;
         false -> {op_not, {FieldExists, false}}
     end;
+convert(Path, {[{<<"$beginsWith">>, Arg}]}) ->
+    PrefixSearch = [value_str(Arg), <<"*">>],
+    {op_field, {make_field(Path, Arg), PrefixSearch}};
 % We're not checking the actual type here, just looking for
 % anything that has a possibility of matching by checking
 % for the field name. We use the same logic for $exists on
diff --git a/src/mango/test/03-operator-test.py b/src/mango/test/03-operator-test.py
index 70e3fbc5f..6de11e006 100644
--- a/src/mango/test/03-operator-test.py
+++ b/src/mango/test/03-operator-test.py
@@ -141,6 +141,22 @@ class BaseOperatorTests:
             for d in docs:
                 self.assertNotIn("twitter", d)
 
+        def test_beginswith(self):
+            docs = self.db.find({"location.state": {"$beginsWith": "New"}})
+            self.assertEqual(len(docs), 2)
+            self.assertUserIds([2, 10], docs)
+
+        # non-string prefixes should return an error
+        def test_beginswith_invalid_prefix(self):
+            docs = self.db.find({"location.state": {"$beginsWith": 123}})
+            self.assertEqual(len(docs), 2)
+
+        # non-string values in documents should not match the prefix, 
+        # but should not error
+        def test_beginswith_invalid_prefix(self):
+            docs = self.db.find({"user_id": {"$beginsWith": "Foo"}})
+            self.assertEqual(len(docs), 0)
+
 
 class OperatorJSONTests(mango.UserDocsTests, BaseOperatorTests.Common):
     # START: text indexes do not support range queries across type boundaries so only
diff --git a/src/mango/test/25-beginswith-test.py b/src/mango/test/25-beginswith-test.py
new file mode 100644
index 000000000..76772c243
--- /dev/null
+++ b/src/mango/test/25-beginswith-test.py
@@ -0,0 +1,112 @@
+# Licensed under the Apache License, Version 2.0 (the "License"); you may not
+# use this file except in compliance with the License. You may obtain a copy of
+# the License at
+#
+#   http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+# License for the specific language governing permissions and limitations under
+# the License.
+
+import copy
+import mango
+
+DOCS = [
+    {"_id": "aaa", "name": "Jimi", "location": "AUS", "age": 27},
+    {"_id": "abc", "name": "Eddie", "location": "AND", "age": 65},
+    {"_id": "bbb", "name": "Harry", "location": "CAN", "age": 21},
+    {"_id": "ccc", "name": "Eddie", "location": "DEN", "age": 37},
+    {"_id": "ddd", "name": "Jones", "location": "ETH", "age": 49},
+]
+
+
+def to_utf8_bytes(list):
+    return [x.encode() for x in list]
+
+
+class BeginsWithOperator(mango.DbPerClass):
+    def setUp(self):
+        self.db.recreate()
+        self.db.save_docs(copy.deepcopy(DOCS))
+        self.db.create_index(["location"])
+        self.db.create_index(["name", "location"])
+
+    def assertDocIds(self, user_ids, docs):
+        user_ids_returned = list(d["_id"] for d in docs)
+        user_ids.sort()
+        user_ids_returned.sort()
+        self.assertEqual(user_ids, user_ids_returned)
+
+    def test_basic(self):
+        docs = self.db.find({"location": {"$beginsWith": "A"}})
+
+        self.assertEqual(len(docs), 2)
+        self.assertDocIds(["aaa", "abc"], docs)
+
+    def test_json_range(self):
+        explain = self.db.find({"location": {"$beginsWith": "A"}}, explain=True)
+        self.assertEqual(explain["mrargs"]["start_key"], ["A"])
+        end_key_bytes = to_utf8_bytes(explain["mrargs"]["end_key"])
+        self.assertEqual(end_key_bytes, [b"A\xef\xbf\xbd", b"<MAX>"])
+
+    def test_compound_key(self):
+        selector = {"name": "Eddie", "location": {"$beginsWith": "A"}}
+        explain = self.db.find(selector, explain=True)
+
+        self.assertEqual(explain["mrargs"]["start_key"], ["Eddie", "A"])
+        end_key_bytes = to_utf8_bytes(explain["mrargs"]["end_key"])
+        self.assertEqual(end_key_bytes, [b"Eddie", b"A\xef\xbf\xbd", b"<MAX>"])
+
+        docs = self.db.find(selector)
+        self.assertEqual(len(docs), 1)
+        self.assertDocIds(["abc"], docs)
+
+    def test_sort_asc(self):
+        selector = {"location": {"$beginsWith": "A"}}
+        explain = self.db.find(selector, sort=["location"], explain=True)
+
+        self.assertEqual(explain["mrargs"]["start_key"], ["A"])
+        end_key_bytes = to_utf8_bytes(explain["mrargs"]["end_key"])
+        self.assertEqual(end_key_bytes, [b"A\xef\xbf\xbd", b"<MAX>"])
+        self.assertEqual(explain["mrargs"]["direction"], "fwd")
+
+    def test_sort_desc(self):
+        selector = {"location": {"$beginsWith": "A"}}
+        explain = self.db.find(selector, sort=[{"location": "desc"}], explain=True)
+
+        start_key_bytes = to_utf8_bytes(explain["mrargs"]["end_key"])
+        self.assertEqual(start_key_bytes, [b"A"])
+        self.assertEqual(explain["mrargs"]["end_key"], ["A"])
+        self.assertEqual(explain["mrargs"]["direction"], "rev")
+
+    def test_all_docs_range(self):
+        explain = self.db.find({"_id": {"$beginsWith": "a"}}, explain=True)
+        self.assertEqual(explain["mrargs"]["start_key"], "a")
+        end_key_bytes = to_utf8_bytes(explain["mrargs"]["end_key"])
+        self.assertEqual(end_key_bytes, [b"a", b"\xef\xbf\xbd"])
+
+    def test_no_index(self):
+        selector = {"foo": {"$beginsWith": "a"}}
+        resp_explain = self.db.find(selector, explain=True)
+
+        self.assertEqual(resp_explain["index"]["type"], "special")
+        self.assertEqual(resp_explain["mrargs"]["start_key"], None)
+        self.assertEqual(resp_explain["mrargs"]["end_key"], "<MAX>")
+
+    def test_invalid_operand(self):
+        try:
+            self.db.find({"_id": {"$beginsWith": True}})
+        except Exception as e:
+            self.assertEqual(e.response.status_code, 400)
+            resp = e.response.json()
+            self.assertEqual(resp["error"], "invalid_operator")
+        else:
+            raise AssertionError("expected find error")
+
+    def test_does_not_match_non_string_value(self):
+        selector = {"age": {"$beginsWith": "a"}}
+        docs = self.db.find(selector)
+
+        self.assertEqual(len(docs), 0)