[Tarantool-patches] [PATCH v1 1/1] sql: enable autoindex optimization
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Thu Sep 10 00:58:09 MSK 2020
Hi! Thanks for the patch!
See 14 comments below.
On 04.09.2020 13:53, imeevma at tarantool.org wrote:
> This patch enables the "auto-index" optimization in SQL. The auto-index
> is actually an ephemeral space that contain some columns of the original
> space.
1. In the patch the code calls the index 'covering' meaning that it
contains all the columns. What is true?
> In some cases, this can speed up execution, since creating a new
> index and searching using it can be more cost efficient than scanning.
2. Could you provide an example?
> Co-authored-by: Mergen Imeev <imeevma at gmail.com>
> Co-authored-by: Timur Safin <tsafin at 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).
>
> src/box/CMakeLists.txt | 2 +-
> src/box/sql.c | 2 +-
> src/box/sql/delete.c | 16 ++--
> src/box/sql/sqlInt.h | 8 +-
> src/box/sql/where.c | 170 +++++++++++++++++++++++------------
> src/box/sql/wherecode.c | 13 +--
> test/sql-tap/whereF.test.lua | 16 +++-
> 7 files changed, 151 insertions(+), 76 deletions(-)
>
> diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
> index b8b2689d2..7e3ad0e22 100644
> --- a/src/box/CMakeLists.txt
> +++ b/src/box/CMakeLists.txt
> @@ -217,7 +217,7 @@ add_library(box STATIC
> if(CMAKE_BUILD_TYPE STREQUAL "Debug")
> add_definitions(-DSQL_DEBUG=1)
> endif()
> -add_definitions(-DSQL_OMIT_AUTOMATIC_INDEX=1 -DSQL_TEST=1)
> +add_definitions(-DSQL_TEST=1)
3. I still see SQL_OMIT_AUTOMATIC_INDEX in src/box/sql/where.c.
> set(EXT_SRC_DIR ${CMAKE_SOURCE_DIR}/extra)
> set(EXT_BIN_DIR ${CMAKE_BINARY_DIR}/extra)
> diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
> index 68abd1f58..57478c129 100644
> --- a/src/box/sql/delete.c
> +++ b/src/box/sql/delete.c
> @@ -546,24 +546,25 @@ sql_generate_row_delete(struct Parse *parse, struct space *space,
> }
>
> int
> -sql_generate_index_key(struct Parse *parse, struct index *index, int cursor,
> - int reg_out, struct index *prev, int reg_prev)
> +sql_generate_index_key(struct Parse *parse, struct index_def *idx_def,
> + int cursor, int reg_out, struct index *prev,
> + int reg_prev, int reg_eph)
4. The function has nothing to do with ephemeral spaces. It just does not
care whether its space is ephemeral. Its task is to just assemble a key,
not caring about space type. Why did you make it always work with an
ephemeral space? Won't this will affect normal spaces - they don't need
OP_NextIdEphemeral or whatever else is related to ephemerals.
In the end of the review I realized the function is never used for anything
except automatic index. Moreover, prev and reg_prev are NULL and 0 always.
I suggest to move this function into the file, which needs it; make it
'static'; remove 'prev' and 'reg_prev' args; rename it to something closer to
what it actually does.
> diff --git a/src/box/sql/where.c b/src/box/sql/where.c
> index e9e936856..c5f79f908 100644
> --- a/src/box/sql/where.c
> +++ b/src/box/sql/where.c
> @@ -727,21 +727,18 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */
5. You need to update the comment of this function. It looks
outdated. At least 'Index' type name, which no longer exists.
6. The function talks about 'covering' index, but covering makes no
sense in Tarantool. It is not possible to fetch a part of tuple. All
indexes in Tarantool, from box API point of view, are covering. So
why is this concept still here? Can we remove it and simplify things?
> @@ -791,26 +789,24 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */
> * if they go out of sync.
> */
> extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS - 1));
> - mxBitCol = MIN(BMS - 1, pTable->def->field_count);
> - testcase(pTable->def->field_count == BMS - 1);
> - testcase(pTable->def->field_count == BMS - 2);
> + mxBitCol = MIN(BMS - 1, space->def->field_count);
> for (i = 0; i < mxBitCol; i++) {
> if (extraCols & MASKBIT(i))
> nKeyCol++;
> }
> if (pSrc->colUsed & MASKBIT(BMS - 1)) {
> - nKeyCol += pTable->def->field_count - BMS + 1;
> + nKeyCol += space->def->field_count - BMS + 1;
> }
>
> - /* Construct the Index object to describe this index */
> - pIdx = sqlDbMallocZero(pParse->db, sizeof(*pIdx));
> - if (pIdx == 0)
> - goto end_auto_index_create;
> - pLoop->pIndex = pIdx;
> - pIdx->zName = "auto-index";
> - pIdx->pTable = pTable;
> n = 0;
> idxCols = 0;
> + uint32_t size = sizeof(struct key_part_def) * nKeyCol;
> + struct key_part_def *part_def = malloc(size);
7. Better use region not to waste time on one another malloc() + free().
> + if (part_def == NULL) {
> + diag_set(OutOfMemory, size, "malloc", "part_def");
> + pParse->is_aborted = true;
> + return;
> + }
> for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
> if (termCanDriveIndex(pTerm, pSrc, notReady)) {
> int iCol = pTerm->u.leftColumn;
> @@ -819,9 +815,18 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */
> testcase(iCol == BMS - 1);
> testcase(iCol == BMS);
> if ((idxCols & cMask) == 0) {
> - Expr *pX = pTerm->pExpr;
> idxCols |= cMask;
> - pIdx->aiColumn[n] = pTerm->u.leftColumn;
> + int i = pTerm->u.leftColumn;
8. You don't need "i". You already have iCol here. It is the same.
> + struct field_def *field =
> + &space->def->fields[i];
> + struct key_part_def *part = &part_def[n];
> + part->fieldno = iCol;
> + part->type = field->type;
> + part->nullable_action = field->nullable_action;
> + part->is_nullable = field->is_nullable;
> + part->sort_order = SORT_ORDER_ASC;
> + part->coll_id = field->coll_id;
> + part->path = NULL;
> n++;
> }
> }
> @@ -833,25 +838,65 @@ constructAutomaticIndex(Parse * pParse, /* The parsing context */
> */
> for (i = 0; i < mxBitCol; i++) {
> if (extraCols & MASKBIT(i)) {
> - pIdx->aiColumn[n] = i;
> + struct field_def *field = &space->def->fields[i];
> + struct key_part_def *part = &part_def[n];
> + part->fieldno = i;
> + part->type = field->type;
> + part->nullable_action = field->nullable_action;
> + part->is_nullable = field->is_nullable;
> + part->sort_order = SORT_ORDER_ASC;
> + part->coll_id = field->coll_id;
> + part->path = NULL;
> n++;
> }
> }
> if (pSrc->colUsed & MASKBIT(BMS - 1)) {
> - for (i = BMS - 1; i < (int)pTable->def->field_count; i++) {
> - pIdx->aiColumn[n] = i;
> + for (i = BMS - 1; i < (int)space->def->field_count; i++) {
> + struct field_def *field = &space->def->fields[i];
> + struct key_part_def *part = &part_def[n];
> + part->fieldno = i;
> + part->type = field->type;
> + part->nullable_action = field->nullable_action;
> + part->is_nullable = field->is_nullable;
> + part->sort_order = SORT_ORDER_ASC;
> + part->coll_id = field->coll_id;
> + part->path = NULL;
> n++;
> }
> }
> assert(n == nKeyCol);
> - pIdx->aiColumn[n] = XN_ROWID;
> +
> + struct key_def *key_def = key_def_new(part_def, nKeyCol, false);
> + free(part_def);
> + if (key_def == NULL) {
> + pParse->is_aborted = true;
> + return;
> + }
> +
> + /* Construct the index definition to describe this index. */
> + struct index_opts opts;
> + index_opts_create(&opts);
> + struct index_def *idx_def = index_def_new(space->def->id, 0,
> + "auto-index",
> + sizeof("auto-index") -1,
> + TREE, &opts, key_def, NULL);
> + key_def_delete(key_def);
> + if (idx_def == NULL) {
> + pParse->is_aborted = true;
> + return;
> + }
> + pLoop->index_def = idx_def;
>
> /* Create the automatic index */
> assert(pLevel->iIdxCur >= 0);
> pLevel->iIdxCur = pParse->nTab++;
> - sqlVdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol + 1);
> - sql_vdbe_set_p4_key_def(pParse, pIdx->key_def);
> - VdbeComment((v, "for %s", pTable->def->name));
> + int reg_eph = ++pParse->nMem;
> + struct sql_key_info *pk_info =
> + sql_key_info_new_from_key_def(pParse->db, idx_def->key_def);
9. Who sets pParse->is_aborted, if sql_key_info_new_from_key_def() fails?
> + sqlVdbeAddOp4(v, OP_OpenTEphemeral, reg_eph, nKeyCol + 1, 0,
> + (char *)pk_info, P4_KEYINFO);
> + sqlVdbeAddOp3(v, OP_IteratorOpen, pLevel->iIdxCur, 0, reg_eph);
> + VdbeComment((v, "for %s", space->def->name));
>
> /* Fill the automatic index with content */
> sqlExprCachePush(pParse);
> @@ -2841,12 +2885,12 @@ tnt_error:
> * those objects, since there is no opportunity to add schema
> * indexes on subqueries and views.
> */
> - pNew->rSetup = rLogSize + rSize + 4;
> - if (!pTab->def->opts.is_view &&
> - pTab->def->id == 0)
> - pNew->rSetup += 24;
> - if (pNew->rSetup < 0)
> - pNew->rSetup = 0;
> + pNew->rSetup = rLogSize + rSize;
> + if (!space->def->opts.is_view &&
> + space->def->id == 0)
> + pNew->rSetup += 28;
> + else
> + pNew->rSetup -= 10;
10. What is this? What are the numbers?
> /* TUNING: Each index lookup yields 20 rows in the table. This
> * is more than the usual guess of 10 rows, since we have no way
> * of knowing how selective the index will ultimately be. It would
> @@ -4794,18 +4838,34 @@ sqlWhereEnd(WhereInfo * pWInfo)
> for (; k < last; k++, pOp++) {
> if (pOp->p1 != pLevel->iTabCur)
> continue;
> - if (pOp->opcode == OP_Column) {
> - int x = pOp->p2;
> - assert(def == NULL ||
> - def->space_id ==
> - pTabItem->space->def->id);
> - if (x >= 0) {
> - pOp->p2 = x;
> - pOp->p1 = pLevel->iIdxCur;
> - }
> - assert((pLoop->
> - wsFlags & WHERE_IDX_ONLY) == 0
> - || x >= 0);
> + if (pOp->opcode != OP_Column)
> + continue;
> + assert(def == NULL || def->space_id ==
> + pTabItem->space->def->id);
> + int x = pOp->p2;
> + assert((pLoop->wsFlags & WHERE_IDX_ONLY) == 0 ||
> + x >= 0);
> + if (x < 0)
> + continue;
> + pOp->p1 = pLevel->iIdxCur;
> + if ((pLoop->wsFlags & WHERE_AUTO_INDEX) == 0) {
> + pOp->p2 = x;
11. Previously 'pOp->p2 = x' was executed unconditionally. Why did you add
this 'if'?
> + continue;
> + }
> + /*
> + * In case we are using auto-indexing, we have
> + * to change the column number, because in
> + * ephemeral space columns are in the same order
> + * as they described in key_def. So, instead of
> + * the field number, we have to insert index of
> + * the part with this fieldno.
12. Why are the columns reordered?
> + */
> + struct key_def *key_def =
> + pLevel->pWLoop->index_def->key_def;
> + uint32_t part_count = key_def->part_count;
> + for (uint32_t i = 0; i < part_count; ++i) {
> + if ((int)key_def->parts[i].fieldno == x)
> + pOp->p2 = i;
> }
> }
> }
> diff --git a/src/box/sql/wherecode.c b/src/box/sql/wherecode.c
> index 6d8768865..534819d48 100644
> --- a/src/box/sql/wherecode.c
> +++ b/src/box/sql/wherecode.c> @@ -1047,8 +1048,6 @@ sqlWhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about the W
> startEq = 0;
> start_constraints = 1;
> }
> - struct index_def *idx_pk = space->index[0]->def;
> - uint32_t pk_part_count = idx_pk->key_def->part_count;
> /*
> * Tarantool's iterator over integer fields doesn't
> * tolerate floating point values. Hence, if term
> @@ -1234,6 +1233,8 @@ sqlWhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about the W
> if (omitTable) {
> /* pIdx is a covering index. No need to access the main table. */
> } else if (iCur != iIdxCur) {
> + struct index_def *idx_pk = space->index[0]->def;
> + uint32_t pk_part_count = idx_pk->key_def->part_count;
13. Does this relocation affect anything?
> int iKeyReg = sqlGetTempRange(pParse, pk_part_count);
> for (j = 0; j < (int) pk_part_count; j++) {
> k = idx_pk->key_def->parts[j].fieldno;
> diff --git a/test/sql-tap/whereF.test.lua b/test/sql-tap/whereF.test.lua
> index 5a894b748..3235df437 100755
> --- a/test/sql-tap/whereF.test.lua
> +++ b/test/sql-tap/whereF.test.lua
> @@ -90,10 +90,20 @@ test:do_execsql_test(
>
> -- for _ in X(0, "X!foreach", [=[["tn sql","\n 1 \"SELECT * FROM t1, t2 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e\"\n 2 \"SELECT * FROM t2, t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e\"\n 3 \"SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e\"\n"]]=]) do
> for tn, sql in ipairs({"SELECT * FROM t1, t2 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e",
> - "SELECT * FROM t2, t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e",
> - "SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"}) do
> + "SELECT * FROM t2, t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"}) do
> test:do_test(
> - "2."..tn,
> + "2.1."..tn,
> + function()
> + return test:execsql("EXPLAIN QUERY PLAN "..sql)
> + end, {
> + '/SEARCH TABLE T1/',
> + '/SEARCH TABLE T2/'
> + })
> +end
> +
> +for tn, sql in ipairs({"SELECT * FROM t2 CROSS JOIN t1 WHERE t1.a>? AND t2.d>t1.c AND t1.b=t2.e"}) do
> + test:do_test(
> + "2.2."..tn,
> function()
> return test:execsql("EXPLAIN QUERY PLAN "..sql)
> end, {
14. Shouldn't there be a test showing 'AUTOMATIC' keyword in the execution plan?
More information about the Tarantool-patches
mailing list