[couchdb] branch mango-beginswith created (now 85e8a9d64)

[wi...@apache.org]

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

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


      at 85e8a9d64 mango: add $beginsWith operator

This branch includes the following new commits:

     new 85e8a9d64 mango: add $beginsWith operator

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.

[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)