From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 4BE1227A87 for ; Wed, 13 Feb 2019 14:52:58 -0500 (EST) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VTHgza5iqvvi for ; Wed, 13 Feb 2019 14:52:58 -0500 (EST) Received: from smtpng1.m.smailru.net (smtpng1.m.smailru.net [94.100.181.251]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id F21D427A83 for ; Wed, 13 Feb 2019 14:52:57 -0500 (EST) From: Nikita Pettik Subject: [tarantool-patches] [PATCH] sql: re-enable ORDER BY field filter optimization Date: Wed, 13 Feb 2019 22:52:52 +0300 Message-Id: <20190213195252.38092-1-korablev@tarantool.org> Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-help: List-unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-subscribe: List-owner: List-post: List-archive: To: tarantool-patches@freelists.org Cc: 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