Re: [Tarantool-patches] [PATCH v2 1/1] sql: enable autoindex optimization

[Mergen Imeev <imeevma@tarantool.org>]

Hi! I added a few tests. I added not all tests since some of them heavily
relies on stat tables. I tried to reproduce them, but it is quite complicated
and it becomes more complicated when cost of autoindex will be changed.

Also, after this letter I will send you another letter where cost of autoindex
will be changed. Some tests also will be changed. The most important change is
that in the test with subquery autoindex is not used in this patch, but it will
be used in that patch. I didn't include this case here since this patch mostly
for comparison to sqlite tests.

On Tue, Oct 06, 2020 at 10:44:40AM +0000, Nikita Pettik wrote:
> On 06 Oct 10:08, imeevma@tarantool.org wrote:
> > This patch enables "autoindex" optimization. This optimization uses an
> > ephemeral space that contains all the fields used in the query. This
> > ephemeral space is called "autoindex". Autoindex may have fewer fields
> > than the original space, and the order of these fields in autoindex may
> > be different from their order in the original space. In addition to the
> > mentioned fields, autoindex contains a rowid.
> > 
> > The primary key of autoindex is a covering index, i.e. it contains all
> > of its fields.
> > 
> > Currently this optimization mainly used in cases when values SELECTED
> > from more than one space and WHERE specified.
> > 
> > At the moment, this optimization does not take into account the number
> > of tuples in spaces. This should be fixed.
> > 
> > Closes #4933
> > 
> > Co-authored-by: Mergen Imeev <imeevma@gmail.com>
> > Co-authored-by: Timur Safin <tsafin@tarantool.org>
> > ---
> > https://github.com/tarantool/tarantool/issues/4933
> > https://github.com/tarantool/tarantool/tree/imeevma/gh-4933-autoindex
> > 
> > @ChangeLog
> >  - "Auto-index" optimization is now enabled (gh-4933).
> > diff --git a/test/sql/misc.result b/test/sql/misc.result
> > index 6af11bfba..d86d55081 100644
> > --- a/test/sql/misc.result
> > +++ b/test/sql/misc.result
> > @@ -204,3 +204,32 @@ box.execute('SELECT field66, field68, field70 FROM test')
> >  box.space.TEST:drop()
> >  ---
> >  ...
> > +-- gh-4933: Make sure that autoindex optimization is used.
> > +box.execute('CREATE TABLE t1(i int primary key, a int);')
> > +---
> > +- row_count: 1
> > +...
> > +box.execute('CREATE TABLE t2(i int primary key, b int);')
> > +---
> > +- row_count: 1
> > +...
> > +--
> > +-- There is no need to insert values in the tables since planner assumes a
> > +-- default number of tuples for each space, regardless of how many tuples there
> > +-- actually are in those spaces. The default value is 1048576 (== 2^20).
> > +--
> > +box.execute('EXPLAIN QUERY PLAN SELECT a, b FROM t1, t2 WHERE a = b;')
> > +---
> > +- metadata:
> > +  - name: selectid
> > +    type: integer
> > +  - name: order
> > +    type: integer
> > +  - name: from
> > +    type: integer
> > +  - name: detail
> > +    type: text
> > +  rows:
> > +  - [0, 0, 0, 'SCAN TABLE T1 (~1048576 rows)']
> > +  - [0, 1, 1, 'SEARCH TABLE T2 USING AUTOMATIC COVERING INDEX (B=?) (~20 rows)']
> > +...
> 
> I haven't reviewed the whole patch yet, but do you really think autoindex
> qp optimization deserves this single insignificant test..?
> 

diff --git a/test/sql-tap/autoindex1.test.lua b/test/sql-tap/autoindex1.test.lua
new file mode 100755
index 000000000..bc6cb6dde
--- /dev/null
+++ b/test/sql-tap/autoindex1.test.lua
@@ -0,0 +1,122 @@
+#!/usr/bin/env tarantool
+test = require("sqltester")
+test:plan(8)
+
+--  2010 April 07
+
+--  The author disclaims copyright to this source code.  In place of
+--  a legal notice, here is a blessing:
+
+--     May you do good and not evil.
+--     May you find forgiveness for yourself and forgive others.
+--     May you share freely, never taking more than you give.
+
+---------------------------------------------------------------------------
+--  This file implements regression tests for sql library.  The focus of this
+-- script is testing automatic index creation logic.
+
+test:execsql([[
+    CREATE TABLE t1(a INT, b INT PRIMARY KEY);
+    INSERT INTO t1 VALUES(1, 11);
+    INSERT INTO t1 VALUES(2, 22);
+    INSERT INTO t1 SELECT a + 2, b + 22 FROM t1;
+    INSERT INTO t1 SELECT a + 4, b + 44 FROM t1;
+    CREATE TABLE t2(c INT, d INT PRIMARY KEY);
+    INSERT INTO t2 SELECT a, 900 + b FROM t1;
+]])
+
+test:do_execsql_test(
+    "autoindex-1.1", [[
+        SELECT b, d FROM t1 JOIN t2 ON a = c ORDER BY b;
+    ]], {
+        11, 911, 22, 922, 33, 933, 44, 944, 55, 955, 66, 966, 77, 977, 88, 988
+    })
+
+test:do_execsql_test(
+    "autoindex-1.2", [[
+        EXPLAIN QUERY PLAN SELECT b, d FROM t1 JOIN t2 ON a = c ORDER BY b;
+    ]], {
+        0,0,0,"SCAN TABLE T1 (~1048576 rows)",
+        0,1,1,"SEARCH TABLE T2 USING AUTOMATIC COVERING INDEX (C=?) (~20 rows)"
+    })
+
+test:do_execsql_test(
+    "autoindex-1.3", [[
+        SELECT b, (SELECT d FROM t2 WHERE c = a) FROM t1;
+    ]], {
+        11, 911, 22, 922, 33, 933, 44, 944, 55, 955, 66, 966, 77, 977, 88, 988
+    })
+
+test:do_execsql_test(
+    "autoindex-1.4", [[
+        EXPLAIN QUERY PLAN SELECT b, (SELECT d FROM t2 WHERE c = a) FROM t1;
+    ]], {
+        0,0,0,"SCAN TABLE T1 (~1048576 rows)",
+        0,0,0,"EXECUTE CORRELATED SCALAR SUBQUERY 1",
+        1,0,0,"SCAN TABLE T2 (~262144 rows)"
+    })
+
+test:do_execsql_test(
+    "autoindex-1.5", [[
+        SELECT b, d FROM t1 CROSS JOIN t2 ON (c = a);
+    ]], {
+        11, 911, 22, 922, 33, 933, 44, 944, 55, 955, 66, 966, 77, 977, 88, 988
+    })
+
+test:do_execsql_test(
+    "autoindex-1.6", [[
+        EXPLAIN QUERY PLAN SELECT b, d FROM t1 CROSS JOIN t2 ON (c = a);
+    ]], {
+        0,0,0,"SCAN TABLE T1 (~1048576 rows)",0,1,1,"SEARCH TABLE T2 USING AUTOMATIC COVERING INDEX (C=?) (~20 rows)"
+    })
+
+test:execsql([[
+    CREATE TABLE t3(i INT PRIMARY KEY, a INT, b INT);
+]])
+
+for i = 1, 4096 do test:execsql("INSERT INTO t3 VALUES ("..i..", "..i..", "..(i + 1)..");") end
+
+test:do_execsql_test(
+    "autoindex-1.7", [[
+        SELECT count(*)
+          FROM t3 AS x1
+          JOIN t3 AS x2 ON x2.a=x1.b
+          JOIN t3 AS x3 ON x3.a=x2.b
+          JOIN t3 AS x4 ON x4.a=x3.b
+          JOIN t3 AS x5 ON x5.a=x4.b
+          JOIN t3 AS x6 ON x6.a=x5.b
+          JOIN t3 AS x7 ON x7.a=x6.b
+          JOIN t3 AS x8 ON x8.a=x7.b
+          JOIN t3 AS x9 ON x9.a=x8.b
+          JOIN t3 AS x10 ON x10.a=x9.b;
+    ]], {
+        4087
+    })
+
+test:do_execsql_test(
+    "autoindex-1.8", [[
+        EXPLAIN QUERY PLAN SELECT count(*)
+          FROM t3 AS x1
+          JOIN t3 AS x2 ON x2.a=x1.b
+          JOIN t3 AS x3 ON x3.a=x2.b
+          JOIN t3 AS x4 ON x4.a=x3.b
+          JOIN t3 AS x5 ON x5.a=x4.b
+          JOIN t3 AS x6 ON x6.a=x5.b
+          JOIN t3 AS x7 ON x7.a=x6.b
+          JOIN t3 AS x8 ON x8.a=x7.b
+          JOIN t3 AS x9 ON x9.a=x8.b
+          JOIN t3 AS x10 ON x10.a=x9.b;
+    ]], {
+        0,0,0,"SCAN TABLE T3 AS X1 (~1048576 rows)",
+        0,1,1,"SEARCH TABLE T3 AS X2 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,2,2,"SEARCH TABLE T3 AS X3 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,3,3,"SEARCH TABLE T3 AS X4 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,4,4,"SEARCH TABLE T3 AS X5 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,5,5,"SEARCH TABLE T3 AS X6 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,6,6,"SEARCH TABLE T3 AS X7 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,7,7,"SEARCH TABLE T3 AS X8 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,8,8,"SEARCH TABLE T3 AS X9 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)",
+        0,9,9,"SEARCH TABLE T3 AS X10 USING AUTOMATIC COVERING INDEX (A=?) (~20 rows)"
+    })
+
+test:finish_test()
diff --git a/test/sql-tap/autoindex4.test.lua b/test/sql-tap/autoindex4.test.lua
index 46488f13a..e22f49c67 100755
--- a/test/sql-tap/autoindex4.test.lua
+++ b/test/sql-tap/autoindex4.test.lua
@@ -1,6 +1,6 @@
 #!/usr/bin/env tarantool
 test = require("sqltester")
-test:plan(7)
+test:plan(8)
 
 --!./tcltestrunner.lua
 -- 2014-10-24
@@ -75,6 +75,18 @@ test:do_execsql_test(
         -- </autoindex4-1.4>
     })
 
+test:do_execsql_test(
+    "autoindex4-2.0",
+    [[
+        CREATE TABLE t3(i INT PRIMARY KEY, e INT, f INT);
+        INSERT INTO t3 VALUES(1, 123,654), (2, 555,444), (3, 234,987);
+        SELECT (SELECT count(*) FROM t1, t2 WHERE a=e AND x=f), e, f, '|' FROM t3 ORDER BY i;
+    ]], {
+        -- <autoindex4-2.0>
+        1, 123, 654, "|", 0, 555, 444, "|", 4, 234, 987, "|"
+        -- </autoindex4-2.0>
+    })
+
 -- do_execsql_test autoindex4-2.0 {
 --   CREATE TABLE t3(e INT,f INT);
 --   INSERT INTO t3 VALUES(123,654),(555,444),(234,987);