Mailing-List: contact commits-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@couchdb.apache.org
Date: Tue, 09 May 2017 14:31:41 +0000
To: "commits@couchdb.apache.org" <commits@couchdb.apache.org>
Subject: [couchdb] branch master updated: Choose index based on fields match
 (#469)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Message-ID: <149434030124.12794.5800523983291350544@gitbox.apache.org>
From: garren@apache.org
Reply-To: "commits@couchdb.apache.org" <commits@couchdb.apache.org>
Auto-Submitted: auto-generated
archived-at: Tue, 09 May 2017 14:31:45 -0000

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

garren pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/couchdb.git

The following commit(s) were added to refs/heads/master by this push:
       new  9568bb7   Choose index based on fields match (#469)
9568bb7 is described below

commit 9568bb7bed6b138663281d4d9065f5dad2794556
Author: garren smith <garren.smith@gmail.com>
AuthorDate: Tue May 9 16:31:38 2017 +0200

    Choose index based on fields match (#469)
    
    * Choose index based on Prefix and FieldRange
    
    First choose the index with the lowest difference between its
    Prefix and the FieldRanges. If that is equal, then
    choose the index with the least number of
    fields in the index. If we still cannot break the tie,
    then choose alphabetically based on ddocId.
    Return the first element's Index and IndexRanges.
---
 src/mango/src/mango_cursor_view.erl    |  41 +++++++++-----
 src/mango/test/12-use-correct-index.py | 100 +++++++++++++++++++++++++++++++++
 2 files changed, 128 insertions(+), 13 deletions(-)

diff --git a/src/mango/src/mango_cursor_view.erl b/src/mango/src/mango_cursor_view.erl
index 2918a2d..ffa5ec1 100644
--- a/src/mango/src/mango_cursor_view.erl
+++ b/src/mango/src/mango_cursor_view.erl
@@ -110,7 +110,11 @@ composite_indexes(Indexes, FieldRanges) ->
     lists:foldl(fun(Idx, Acc) ->
         Cols = mango_idx:columns(Idx),
         Prefix = composite_prefix(Cols, FieldRanges),
-        [{Idx, Prefix} | Acc]
+        % Calcuate the difference between the FieldRanges/Selector
+        % and the Prefix. We want to select the index with a prefix
+        % that is as close to the FieldRanges as possible
+        PrefixDifference = length(FieldRanges) - length(Prefix),
+        [{Idx, Prefix, PrefixDifference} | Acc]
     end, [], Indexes).
 
 
@@ -125,29 +129,40 @@ composite_prefix([Col | Rest], Ranges) ->
     end.
 
 
-% Low and behold our query planner. Or something.
-% So stupid, but we can fix this up later. First
-% pass: Sort the IndexRanges by (num_columns, idx_name)
-% and return the first element. Yes. Its going to
-% be that dumb for now.
+% The query planner
+% First choose the index with the lowest difference between its 
+% Prefix and the FieldRanges. If that is equal, then
+% choose the index with the least number of 
+% fields in the index. If we still cannot break the tie, 
+% then choose alphabetically based on ddocId.
+% Return the first element's Index and IndexRanges.
 %
 % In the future we can look into doing a cached parallel
 % reduce view read on each index with the ranges to find
 % the one that has the fewest number of rows or something.
 choose_best_index(_DbName, IndexRanges) ->
-    Cmp = fun({A1, A2}, {B1, B2}) ->
-        case length(A2) - length(B2) of
+    Cmp = fun({IdxA, _PrefixA, PrefixDifferenceA}, {IdxB, _PrefixB, PrefixDifferenceB}) ->
+        case PrefixDifferenceA - PrefixDifferenceB of
             N when N < 0 -> true;
             N when N == 0 ->
-                % This is a really bad sort and will end
-                % up preferring indices based on the
-                % (dbname, ddocid, view_name) triple
-                A1 =< B1;
+                ColsLenA = length(mango_idx:columns(IdxA)),
+                ColsLenB = length(mango_idx:columns(IdxB)),
+                case ColsLenA - ColsLenB of
+                    M when M < 0 -> 
+                        true;
+                    M when M == 0 ->
+                        % We have no other way to choose, so at this point 
+                        % select the index based on (dbname, ddocid, view_name) triple
+                        IdxA =< IdxB;
+                    _ -> 
+                        false
+                end;
             _ ->
                 false
         end
     end,
-    hd(lists:sort(Cmp, IndexRanges)).
+    {SelectedIndex, SelectedIndexRanges, _} = hd(lists:sort(Cmp, IndexRanges)),
+    {SelectedIndex, SelectedIndexRanges}.
 
 
 handle_message({meta, _}, Cursor) ->
diff --git a/src/mango/test/12-use-correct-index.py b/src/mango/test/12-use-correct-index.py
new file mode 100644
index 0000000..f1eaf5f
--- /dev/null
+++ b/src/mango/test/12-use-correct-index.py
@@ -0,0 +1,100 @@
+# 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 mango
+import copy
+
+DOCS = [
+    {
+        "_id": "_design/my-design-doc",
+    },
+    {
+        "_id": "54af50626de419f5109c962f",
+        "user_id": 0,
+        "age": 10,
+        "name": "Jimi",
+        "location": "UK",
+        "number": 4
+    },
+    {
+        "_id": "54af50622071121b25402dc3",
+        "user_id": 1,
+        "age": 12,
+        "name": "Eddie",
+        "location": "ZAR",
+        "number": 2
+    },
+    {
+        "_id": "54af50622071121b25402dc6",
+        "user_id": 1,
+        "age": 6,
+        "name": "Harry",
+        "location": "US",
+        "number":8
+    },
+    {
+        "_id": "54af50622071121b25402dc9",
+        "name": "Eddie",
+        "occupation": "engineer",
+        "number":7
+    },
+]
+
+class ChooseCorrectIndexForDocs(mango.DbPerClass):
+    def setUp(self):
+        self.db.recreate()
+        self.db.save_docs(copy.deepcopy(DOCS))
+
+    def test_choose_index_with_one_field_in_index(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie"}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/zzz'
+
+    def test_choose_index_with_two(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age":{"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/bbb'
+
+    def test_choose_index_alphabetically(self):
+        self.db.create_index(["name", "age", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "location"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age": {"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/aaa'
+
+    def test_choose_index_most_accurate(self):
+        self.db.create_index(["name", "location", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "user_id"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "age": {"$gte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/bbb'
+    
+    def test_choose_index_most_accurate_in_memory_selector(self):
+        self.db.create_index(["name", "location", "user_id"], ddoc="aaa")
+        self.db.create_index(["name", "age", "user_id"], ddoc="bbb")
+        self.db.create_index(["name"], ddoc="zzz")
+        explain = self.db.find({"name": "Eddie", "number": {"$lte": 12}}, explain=True)
+        assert explain["index"]["ddoc"] == '_design/zzz'
+
+    def test_chooses_idxA(self):
+        DOCS2 = [
+            {"a":1, "b":1, "c":1},
+            {"a":1000, "d" : 1000, "e": 1000}
+        ]
+        self.db.save_docs(copy.deepcopy(DOCS2))
+        self.db.create_index(["a", "b", "c"])
+        self.db.create_index(["a", "d", "e"])
+        explain = self.db.find({"a": {"$gt": 0}, "b": {"$gt": 0}, "c": {"$gt": 0}}, explain=True)
+        assert explain["index"]["def"]["fields"] == [{'a': 'asc'}, {'b': 'asc'}, {'c': 'asc'}]

-- 
To stop receiving notification emails like this one, please contact
['"commits@couchdb.apache.org" <commits@couchdb.apache.org>'].