[tarantool-patches] [PATCH] sql: re-enable ORDER BY field filter optimization

[Nikita Pettik]

When we replaced SQLite's ephemeral spaces with our ones, one
optimization concerning ORDER BY clause was disabled. It allows to
reduce number of fields in format of ephemeral space or sorter table.
To illustrate how it works, consider example:

CREATE TABLE t (id INT PRIMARY KEY, b INT);
SELECT * FROM t ORDER BY b;

To sort entries from t, ephemeral space with format [b, id, b] is
created. One can see, that such format contains duplicate of b column.
To avoid such situation, SQLite provides optimization which removes
duplicates. Meanwhile, it doesn't change already set format of ephemeral
(or sorter) space (and SQLite tolerates that format difference). That's
why it was turned off. However, such optimization turns out to be not
optional but required: some column values shouldn't be computed twice.
For instance:

SELECT random() AS x FROM t ORDER BY x;

Without filtering fields from ephemeral space format, it would be like:
[random(), random()]. In other words, results would be sorted by first
call to random() function, but resulting set would consist of values
given by second call of random(). So, to enable it, we should reduce
field count in format of ephemeral space by number of matches between
SELECT and ORDER BY column lists.

Also, type of return value for random() function has been fixed.

Closes #3783
---
Branch: https://github.com/tarantool/tarantool/tree/np/gh-3783-enable-field-filter-order-by
Issue: https://github.com/tarantool/tarantool/issues/3783

 src/box/sql/func.c             |  2 +-
 src/box/sql/select.c           | 38 ++++++++++++++++++++++++--------------
 test/sql-tap/orderby9.test.lua |  4 ++--
 3 files changed, 27 insertions(+), 17 deletions(-)

diff --git a/src/box/sql/func.c b/src/box/sql/func.c
index 9db3915a5..237070429 100644
--- a/src/box/sql/func.c
+++ b/src/box/sql/func.c
@@ -1759,7 +1759,7 @@ sqlite3RegisterBuiltinFunctions(void)
 		FUNCTION(hex, 1, 0, 0, hexFunc, FIELD_TYPE_STRING),
 		FUNCTION2(ifnull, 2, 0, 0, noopFunc, SQLITE_FUNC_COALESCE,
 			  FIELD_TYPE_INTEGER),
-		VFUNCTION(random, 0, 0, 0, randomFunc, FIELD_TYPE_NUMBER),
+		VFUNCTION(random, 0, 0, 0, randomFunc, FIELD_TYPE_INTEGER),
 		VFUNCTION(randomblob, 1, 0, 0, randomBlob, FIELD_TYPE_SCALAR),
 		FUNCTION(nullif, 2, 0, 1, nullifFunc, FIELD_TYPE_SCALAR),
 		FUNCTION(version, 0, 0, 0, sql_func_version, FIELD_TYPE_STRING),
diff --git a/src/box/sql/select.c b/src/box/sql/select.c
index 4d2894616..58b4a608b 100644
--- a/src/box/sql/select.c
+++ b/src/box/sql/select.c
@@ -975,23 +975,33 @@ selectInnerLoop(Parse * pParse,		/* The parser context */
 			 * saving space and CPU cycles.
 			 */
 			ecelFlags |= (SQLITE_ECEL_OMITREF | SQLITE_ECEL_REF);
-			/* This optimization is temporary disabled. It seems
-			 * that it was possible to create table with n columns and
-			 * insert tuple with m columns, where m < n. Contrary, Tarantool
-			 * doesn't allow to alter the number of fields in tuple
-			 * to be inserted. This may be uncommented by delaying the
-			 * creation of table until insertion of first tuple,
-			 * so that the number of fields in tuple can be precisely calculated.
+			/*
+			 * Format for ephemeral space has been
+			 * already set with field count calculated
+			 * as orderBy->nExpr + pEList->nExpr + 1,
+			 * where pEList is a select list.
+			 * Since we want to reduce number of fields
+			 * in format of ephemeral space, we should
+			 * fix corresponding opcode's argument.
+			 * Otherwise, tuple format won't match
+			 * space format.
 			 */
-			/*for (i = pSort->nOBSat; i < pSort->pOrderBy->nExpr; i++) {
-				int j;
-				if ((j =
-				     pSort->pOrderBy->a[i].u.x.iOrderByCol) >
-				    0) {
+			uint32_t excess_field_count = 0;
+			for (i = pSort->nOBSat; i < pSort->pOrderBy->nExpr;
+			     i++) {
+				int j = pSort->pOrderBy->a[i].u.x.iOrderByCol;
+				if (j > 0) {
+					excess_field_count++;
 					pEList->a[j - 1].u.x.iOrderByCol =
-					    (u16) (i + 1 - pSort->nOBSat);
+						(u16) (i + 1 - pSort->nOBSat);
 				}
-			}*/
+			}
+			struct VdbeOp *open_eph_op =
+				sqlite3VdbeGetOp(v, pSort->addrSortIndex);
+			assert(open_eph_op->p2 - excess_field_count > 0);
+			sqlite3VdbeChangeP2(v, pSort->addrSortIndex,
+					    open_eph_op->p2 -
+					    excess_field_count);
 			regOrig = 0;
 			assert(eDest == SRT_Set || eDest == SRT_Mem
 			       || eDest == SRT_Coroutine
diff --git a/test/sql-tap/orderby9.test.lua b/test/sql-tap/orderby9.test.lua
index 33c9a31a4..a062cf3b7 100755
--- a/test/sql-tap/orderby9.test.lua
+++ b/test/sql-tap/orderby9.test.lua
@@ -44,7 +44,7 @@ test:do_test(
         local l2 = table.deepcopy(l1)
         table.sort(l1)
         return test.is_deeply_regex(l1, l2)
-    end, false)
+    end, true)
 
 test:do_test(
     1.1,
@@ -53,7 +53,7 @@ test:do_test(
         local l2 = table.deepcopy(l1)
         table.sort(l1)
         return test.is_deeply_regex(l1, l2)
-    end, false)
+    end, true)
 
 test:do_test(
     1.2,
-- 
2.15.1