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 0EC2328F70 for ; Thu, 30 Aug 2018 11:18:08 -0400 (EDT) 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 Edi1cofm6ps3 for ; Thu, 30 Aug 2018 11:18:07 -0400 (EDT) Received: from smtpng3.m.smailru.net (smtpng3.m.smailru.net [94.100.177.149]) (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 77EC228F6C for ; Thu, 30 Aug 2018 11:18:06 -0400 (EDT) From: Kirill Shcherbatov Subject: [tarantool-patches] [PATCH v1 1/1] sql: replace sql column mask with core mask Date: Thu, 30 Aug 2018 18:18:01 +0300 Message-Id: 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: korablev@tarantool.org, Kirill Shcherbatov Refactored SQL Bitmask with tarantool core uint64_t column mask and API functions. Closes #3571. --- Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-3571-replace-sql-column-mask Issue: https://github.com/tarantool/tarantool/issues/3571 src/box/column_mask.h | 23 +- src/box/sql/delete.c | 4 +- src/box/sql/expr.c | 76 ++-- src/box/sql/resolve.c | 25 +- src/box/sql/sqliteInt.h | 69 ++-- src/box/sql/update.c | 10 +- src/box/sql/vdbeaux.c | 2 +- src/box/sql/where.c | 1051 ++++++++++++++++++++++++----------------------- src/box/sql/whereInt.h | 149 +++++-- src/box/sql/wherecode.c | 509 ++++++++++++----------- src/box/sql/whereexpr.c | 160 ++++---- 11 files changed, 1069 insertions(+), 1009 deletions(-) diff --git a/src/box/column_mask.h b/src/box/column_mask.h index d71911d..cf52913 100644 --- a/src/box/column_mask.h +++ b/src/box/column_mask.h @@ -50,7 +50,9 @@ * in such case we set not one bit, but a range of bits. */ -#define COLUMN_MASK_FULL UINT64_MAX +#define COLUMN_MASK_FULL UINT64_MAX +#define COLUMN_MASK_BIT(n) (((uint64_t)1)<<(n)) +#define COLUMN_MASK_SIZE ((int)(sizeof(uint64_t)*8)) /** * Set a bit in the bitmask corresponding to a @@ -61,12 +63,12 @@ static inline void column_mask_set_fieldno(uint64_t *column_mask, uint32_t fieldno) { - if (fieldno >= 63) + if (fieldno >= COLUMN_MASK_SIZE - 1) /* * @sa column_mask key_def declaration for * details. */ - *column_mask |= ((uint64_t) 1) << 63; + *column_mask |= ((uint64_t) 1) << (COLUMN_MASK_SIZE - 1); else *column_mask |= ((uint64_t) 1) << fieldno; } @@ -80,7 +82,7 @@ column_mask_set_fieldno(uint64_t *column_mask, uint32_t fieldno) static inline void column_mask_set_range(uint64_t *column_mask, uint32_t first_fieldno_in_range) { - if (first_fieldno_in_range < 63) { + if (first_fieldno_in_range < COLUMN_MASK_SIZE - 1) { /* * Set all bits by default via COLUMN_MASK_FULL * and then unset bits preceding the operation @@ -90,11 +92,22 @@ column_mask_set_range(uint64_t *column_mask, uint32_t first_fieldno_in_range) *column_mask |= COLUMN_MASK_FULL << first_fieldno_in_range; } else { /* A range outside "short" range. */ - *column_mask |= ((uint64_t) 1) << 63; + *column_mask |= ((uint64_t) 1) << (COLUMN_MASK_SIZE - 1); } } /** + * Test if overflow flag is set in mask. + * @param column_mask Mask to test. + * @retval true If mask overflowed, false otherwise. + */ +static inline bool +column_mask_is_overflowed(uint64_t column_mask) +{ + return column_mask & (((uint64_t) 1) << (COLUMN_MASK_SIZE - 1)); +} + +/** * True if the update operation does not change the key. * @param key_mask Key mask. * @param update_mask Column mask of the update operation. diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c index 93ada3a..d146201 100644 --- a/src/box/sql/delete.c +++ b/src/box/sql/delete.c @@ -501,10 +501,8 @@ sql_generate_row_delete(struct Parse *parse, struct Table *table, */ sqlite3VdbeAddOp2(v, OP_Copy, reg_pk, first_old_reg); for (int i = 0; i < (int)table->def->field_count; i++) { - testcase(mask != 0xffffffff && iCol == 31); - testcase(mask != 0xffffffff && iCol == 32); if (mask == 0xffffffff - || (i <= 31 && (mask & MASKBIT32(i)) != 0)) { + || (i <= 31 && (mask & COLUMN_MASK_BIT(i)) != 0)) { sqlite3ExprCodeGetColumnOfTable(v, table->def, cursor, i, first_old_reg + diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c index 50505b1..fd0b2b2 100644 --- a/src/box/sql/expr.c +++ b/src/box/sql/expr.c @@ -1539,7 +1539,7 @@ sqlite3SrcListDup(sqlite3 * db, SrcList * p, int flags) sqlite3SelectDup(db, pOldItem->pSelect, flags); pNewItem->pOn = sqlite3ExprDup(db, pOldItem->pOn, flags); pNewItem->pUsing = sqlite3IdListDup(db, pOldItem->pUsing); - pNewItem->colUsed = pOldItem->colUsed; + pNewItem->column_used_mask = pOldItem->column_used_mask; } return pNew; } @@ -2402,20 +2402,18 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ /* Search for an existing index that will work for this IN operator */ for (pIdx = pTab->pIndex; pIdx && eType == 0; pIdx = pIdx->pNext) { - Bitmask colUsed; /* Columns of the index used */ - Bitmask mCol; /* Mask for the current column */ uint32_t part_count = pIdx->def->key_def->part_count; struct key_part *parts = pIdx->def->key_def->parts; if ((int)part_count < nExpr) continue; - /* Maximum nColumn is BMS-2, not BMS-1, so that we can compute - * BITMASK(nExpr) without overflowing + /* + * Maximum nColumn is COLUMN_MASK_SIZE-2, not + * COLUMN_MASK_SIZE-1, so that we can compute + * bitmasks without overflowing. */ - testcase(part_count == BMS - 2); - testcase(part_count == BMS - 1); - if (part_count >= BMS - 1) + if (part_count >= COLUMN_MASK_SIZE - 1) continue; if (mustBeUnique && ((int)part_count > nExpr || @@ -2427,8 +2425,8 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ */ continue; } - - colUsed = 0; /* Columns of index used so far */ + /* Columns of the index used mask. */ + uint64_t col_used_mask = 0; for (i = 0; i < nExpr; i++) { Expr *pLhs = sqlite3VectorFieldSubexpr(pX->pLeft, i); Expr *pRhs = pEList->a[i].pExpr; @@ -2451,20 +2449,25 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ } if (j == nExpr) break; - mCol = MASKBIT(j); - if (mCol & colUsed) - break; /* Each column used only once */ - colUsed |= mCol; + /* Each column used only once. */ + if (COLUMN_MASK_BIT(j) & col_used_mask) + break; + column_mask_set_fieldno(&col_used_mask, + j); if (aiMap) aiMap[i] = pRhs->iColumn; else if (pSingleIdxCol && nExpr == 1) *pSingleIdxCol = pRhs->iColumn; } - assert(i == nExpr - || colUsed != (MASKBIT(nExpr) - 1)); - if (colUsed == (MASKBIT(nExpr) - 1)) { - /* If we reach this point, that means the index pIdx is usable */ + assert((COLUMN_MASK_BIT(nExpr) - 1) != + col_used_mask || i == nExpr); + if (col_used_mask == + (COLUMN_MASK_BIT(nExpr) - 1)) { + /* + * If we reach this point, that means + * the index pIdx is usable. + */ int iAddr = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); sqlite3VdbeAddOp4(v, OP_Explain, @@ -2486,18 +2489,12 @@ sqlite3FindInIndex(Parse * pParse, /* Parsing context */ if (prRhsHasNull) { #ifdef SQLITE_ENABLE_COLUMN_USED_MASK - i64 mask = - (1 << nExpr) - 1; - sqlite3VdbeAddOp4Dup8(v, - OP_ColumnsUsed, - iTab, - 0, - 0, - (u8 - *) - & - mask, - P4_INT64); + uint64_t mask = (1 << nExpr) - 1; + sqlite3VdbeAddOp4Dup8(v, + OP_ColumnsUsed, + iTab, 0, 0, + (u8*)&mask, + P4_INT64); #endif *prRhsHasNull = ++pParse->nMem; if (nExpr == 1) { @@ -3943,7 +3940,6 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target) int nFarg; /* Number of function arguments */ FuncDef *pDef; /* The function definition object */ const char *zId; /* The function name */ - u32 constMask = 0; /* Mask of function arguments that are constant */ int i; /* Loop counter */ sqlite3 *db = pParse->db; /* The database connection */ struct coll *coll = NULL; @@ -4005,12 +4001,13 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target) target); } + /* Mask of function arguments that are constant. */ + uint64_t farg_const_mask = 0; for (i = 0; i < nFarg; i++) { - if (i < 32 - && sqlite3ExprIsConstant(pFarg->a[i]. - pExpr)) { - testcase(i == 31); - constMask |= MASKBIT32(i); + if (i < 32 && + sqlite3ExprIsConstant(pFarg->a[i].pExpr)) { + column_mask_set_fieldno(&farg_const_mask, + i); } if ((pDef->funcFlags & SQLITE_FUNC_NEEDCOLL) != 0 && coll == NULL) { @@ -4022,7 +4019,7 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target) } } if (pFarg) { - if (constMask) { + if (farg_const_mask != 0) { r1 = pParse->nMem + 1; pParse->nMem += nFarg; } else { @@ -4070,12 +4067,11 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target) sqlite3VdbeAddOp4(v, OP_CollSeq, 0, 0, 0, (char *)coll, P4_COLLSEQ); } - sqlite3VdbeAddOp4(v, OP_Function0, constMask, r1, + sqlite3VdbeAddOp4(v, OP_Function0, farg_const_mask, r1, target, (char *)pDef, P4_FUNCDEF); sqlite3VdbeChangeP5(v, (u8) nFarg); - if (nFarg && constMask == 0) { + if (nFarg != 0 && farg_const_mask == 0) sqlite3ReleaseTempRange(pParse, r1, nFarg); - } return target; } case TK_EXISTS: diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c index 9a2d6ff..134292a 100644 --- a/src/box/sql/resolve.c +++ b/src/box/sql/resolve.c @@ -437,20 +437,18 @@ lookupName(Parse * pParse, /* The parsing context */ pTopNC->nErr++; } - /* If a column from a table in pSrcList is referenced, then record - * this fact in the pSrcList.a[].colUsed bitmask. Column 0 causes - * bit 0 to be set. Column 1 sets bit 1. And so forth. If the - * column number is greater than the number of bits in the bitmask - * then set the high-order bit of the bitmask. + /* + * If a column from a table in pSrcList is referenced, + * then record this fact in pSrcList.a.column_used_mask + * bitmask. Column 0 causes bit 0 to be set. Column 1 + * sets bit 1. And so forth. If the column number is + * greater than the number of bits in the bitmask then + * set the high-order bit of the bitmask. */ if (pExpr->iColumn >= 0 && pMatch != 0) { - int n = pExpr->iColumn; - testcase(n == BMS - 1); - if (n >= BMS) { - n = BMS - 1; - } assert(pMatch->iCursor == pExpr->iTable); - pMatch->colUsed |= ((Bitmask) 1) << n; + column_mask_set_fieldno(&pMatch->column_used_mask, + pExpr->iColumn); } /* Clean up and return @@ -492,10 +490,7 @@ sqlite3CreateColumnExpr(sqlite3 * db, SrcList * pSrc, int iSrc, int iCol) p->space_def = pItem->pTab->def; p->iTable = pItem->iCursor; p->iColumn = (ynVar) iCol; - testcase(iCol == BMS); - testcase(iCol == BMS - 1); - pItem->colUsed |= - ((Bitmask) 1) << (iCol >= BMS ? BMS - 1 : iCol); + column_mask_set_fieldno(&pItem->column_used_mask, iCol); ExprSetProperty(p, EP_Resolved); } return p; diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h index 1d32c9a..6945121 100644 --- a/src/box/sql/sqliteInt.h +++ b/src/box/sql/sqliteInt.h @@ -67,6 +67,7 @@ #include +#include "box/column_mask.h" #include "box/field_def.h" #include "box/sql.h" #include "box/txn.h" @@ -2296,49 +2297,28 @@ struct IdList { int nId; /* Number of identifiers on the list */ }; -/* - * The bitmask datatype defined below is used for various optimizations. - * - * Changing this from a 64-bit to a 32-bit type limits the number of - * tables in a join to 32 instead of 64. But it also reduces the size - * of the library by 738 bytes on ix86. - */ -#ifdef SQLITE_BITMASK_TYPE -typedef SQLITE_BITMASK_TYPE Bitmask; -#else -typedef u64 Bitmask; -#endif - -/* - * The number of bits in a Bitmask. "BMS" means "BitMask Size". - */ -#define BMS ((int)(sizeof(Bitmask)*8)) - -/* - * A bit in a Bitmask - */ -#define MASKBIT(n) (((Bitmask)1)<<(n)) -#define MASKBIT32(n) (((unsigned int)1)<<(n)) -#define ALLBITS ((Bitmask)-1) - -/* - * The following structure describes the FROM clause of a SELECT statement. - * Each table or subquery in the FROM clause is a separate element of - * the SrcList.a[] array. - * - * With the addition of multiple database support, the following structure - * can also be used to describe a particular table such as the table that - * is modified by an INSERT, DELETE, or UPDATE statement. In standard SQL, - * such a table must be a simple name: ID. But in SQLite, the table can - * now be identified by a database name, a dot, then the table name: ID.ID. - * - * The jointype starts out showing the join type between the current table - * and the next table on the list. The parser builds the list this way. - * But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each - * jointype expresses the join between the table and the previous table. - * - * In the colUsed field, the high-order bit (bit 63) is set if the table - * contains more than 63 columns and the 64-th or later column is used. +/** + * The following structure describes the FROM clause of a SELECT + * statement. Each table or subquery in the FROM clause is a + * separate element of the SrcList.a[] array. + * + * With the addition of multiple database support, the following + * structure can also be used to describe a particular table such + * as the table that is modified by an INSERT, DELETE, or UPDATE + * statement. In standard SQL, + * such a table must be a simple name: ID. But in SQLite, the + * table can now be identified by a database name, a dot, then + * the table name: ID.ID. + * + * The jointype starts out showing the join type between the + * current table and the next table on the list. The parser + * builds the list this way. But sqlite3SrcListShiftJoinType() + * later shifts the jointypes so that each jointype expresses the + * join between the table and the previous table. + * + * In the column_used_mask field, the high-order bit (bit 63) is + * set if thetable contains more than 63 columns and the 64-th or + * later column is used. */ struct SrcList { int nSrc; /* Number of tables or subqueries in the FROM clause */ @@ -2365,7 +2345,8 @@ struct SrcList { int iCursor; /* The VDBE cursor number used to access this table */ Expr *pOn; /* The ON clause of a join */ IdList *pUsing; /* The USING clause of a join */ - Bitmask colUsed; /* Bit N (1<" clause */ ExprList *pFuncArg; /* Arguments to table-valued-function */ diff --git a/src/box/sql/update.c b/src/box/sql/update.c index 3e39688..4d9abdc 100644 --- a/src/box/sql/update.c +++ b/src/box/sql/update.c @@ -195,9 +195,9 @@ sqlite3Update(Parse * pParse, /* The parser context */ } /* * The SET expressions are not actually used inside the - * WHERE loop. So reset the colUsed mask. + * WHERE loop. So reset the column_used_mask mask. */ - pTabList->a[0].colUsed = 0; + pTabList->a[0].column_used_mask = 0; hasFK = fkey_is_required(pTab->def->id, aXRef); @@ -325,13 +325,13 @@ sqlite3Update(Parse * pParse, /* The parser context */ if (is_pk_modified || hasFK != 0 || trigger != NULL) { struct space *space = space_by_id(pTab->def->id); assert(space != NULL); - u32 oldmask = hasFK ? space->fkey_mask : 0; + uint64_t oldmask = hasFK != 0 ? space->fkey_mask : 0; oldmask |= sql_trigger_colmask(pParse, trigger, pChanges, 0, TRIGGER_BEFORE | TRIGGER_AFTER, pTab, on_error); for (i = 0; i < (int)def->field_count; i++) { if (oldmask == 0xffffffff - || (i < 32 && (oldmask & MASKBIT32(i)) != 0) + || (i < 32 && (oldmask & COLUMN_MASK_BIT(i)) != 0) || table_column_is_in_pk(pTab, i)) { testcase(oldmask != 0xffffffff && i == 31); sqlite3ExprCodeGetColumnOfTable(v, def, @@ -365,7 +365,7 @@ sqlite3Update(Parse * pParse, /* The parser context */ sqlite3ExprCode(pParse, pChanges->a[j].pExpr, regNew + i); } else if (0 == (tmask & TRIGGER_BEFORE) || i > 31 - || (newmask & MASKBIT32(i))) { + || (newmask & COLUMN_MASK_BIT(i))) { /* This branch loads the value of a column that will not be changed * into a register. This is done if there are no BEFORE triggers, or * if there are one or more BEFORE triggers that use this value via diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c index 3b0c90c..7569970 100644 --- a/src/box/sql/vdbeaux.c +++ b/src/box/sql/vdbeaux.c @@ -2713,7 +2713,7 @@ sqlite3VdbeDeleteAuxData(sqlite3 * db, AuxData ** pp, int iOp, int mask) AuxData *pAux = *pp; if ((iOp < 0) || (pAux->iOp == iOp - && (pAux->iArg > 31 || !(mask & MASKBIT32(pAux->iArg)))) + && (pAux->iArg > 31 || !(mask & COLUMN_MASK_BIT(pAux->iArg)))) ) { testcase(pAux->iArg == 31); if (pAux->xDelete) { diff --git a/src/box/sql/where.c b/src/box/sql/where.c index a4a1c45..850e2a7 100644 --- a/src/box/sql/where.c +++ b/src/box/sql/where.c @@ -166,62 +166,61 @@ whereOrMove(WhereOrSet * pDest, WhereOrSet * pSrc) memcpy(pDest->a, pSrc->a, pDest->n * sizeof(pDest->a[0])); } -/* - * Try to insert a new prerequisite/cost entry into the WhereOrSet pSet. - * +/** + * Try to insert a new prerequisite/cost entry into the WhereOrSet @set. * The new entry might overwrite an existing entry, or it might be * appended, or it might be discarded. Do whatever is the right thing * so that pSet keeps the N_OR_COST best entries seen so far. + * + * @param set The WhereOrSet to be updated. + * @param prereq_mask Prerequisites of the new entry. + * @param run_cost Run-cost of the new entry. + * @param outputs_cnt Number of outputs for the new entry. + * @retval 1 on new record has been inserted, 0 otherwise. */ static int -whereOrInsert(WhereOrSet * pSet, /* The WhereOrSet to be updated */ - Bitmask prereq, /* Prerequisites of the new entry */ - LogEst rRun, /* Run-cost of the new entry */ - LogEst nOut) /* Number of outputs for the new entry */ +sql_where_or_set_append(struct WhereOrSet *set, uint64_t prereq_mask, + LogEst run_cost, LogEst outputs_cnt) { u16 i; WhereOrCost *p; - for (i = pSet->n, p = pSet->a; i > 0; i--, p++) { - if (rRun <= p->rRun && (prereq & p->prereq) == prereq) { + for (i = set->n, p = set->a; i > 0; i--, p++) { + if (run_cost <= p->rRun && + (prereq_mask & p->prereq_mask) == prereq_mask) goto whereOrInsert_done; - } - if (p->rRun <= rRun && (p->prereq & prereq) == p->prereq) { + if (p->rRun <= run_cost && + (p->prereq_mask & prereq_mask) == p->prereq_mask) return 0; - } } - if (pSet->n < N_OR_COST) { - p = &pSet->a[pSet->n++]; - p->nOut = nOut; + if (set->n < N_OR_COST) { + p = &set->a[set->n++]; + p->nOut = outputs_cnt; } else { - p = pSet->a; - for (i = 1; i < pSet->n; i++) { - if (p->rRun > pSet->a[i].rRun) - p = pSet->a + i; + p = set->a; + for (i = 1; i < set->n; i++) { + if (p->rRun > set->a[i].rRun) + p = set->a + i; } - if (p->rRun <= rRun) + if (p->rRun <= run_cost) return 0; } whereOrInsert_done: - p->prereq = prereq; - p->rRun = rRun; - if (p->nOut > nOut) - p->nOut = nOut; + p->prereq_mask = prereq_mask; + p->rRun = run_cost; + if (p->nOut > outputs_cnt) + p->nOut = outputs_cnt; return 1; } -/* - * Return the bitmask for the given cursor number. Return 0 if - * iCursor is not in the set. - */ -Bitmask -sqlite3WhereGetMask(WhereMaskSet * pMaskSet, int iCursor) + +uint64_t +sql_where_get_mask(struct WhereMaskSet *mask_set, int cursor) { int i; - assert(pMaskSet->n <= (int)sizeof(Bitmask) * 8); - for (i = 0; i < pMaskSet->n; i++) { - if (pMaskSet->ix[i] == iCursor) { - return MASKBIT(i); - } + assert(mask_set->n <= COLUMN_MASK_SIZE); + for (i = 0; i < mask_set->n; i++) { + if (mask_set->ix[i] == cursor) + return COLUMN_MASK_BIT(i); } return 0; } @@ -441,55 +440,24 @@ where_scan_init(struct WhereScan *scan, struct WhereClause *clause, return whereScanNext(scan); } -/* - * Search for a term in the WHERE clause that is of the form "X " - * where X is a reference to the iColumn of table iCur or of index pIdx - * if pIdx!=0 and is one of the WO_xx operator codes specified by - * the op parameter. Return a pointer to the term. Return 0 if not found. - * - * If pIdx!=0 then it must be one of the indexes of table iCur. - * Search for terms matching the iColumn-th column of pIdx - * rather than the iColumn-th column of table iCur. - * - * The term returned might by Y= if there is another constraint in - * the WHERE clause that specifies that X=Y. Any such constraints will be - * identified by the WO_EQUIV bit in the pTerm->eOperator field. The - * aiCur[]/iaColumn[] arrays hold X and all its equivalents. There are 11 - * slots in aiCur[]/aiColumn[] so that means we can look for X plus up to 10 - * other equivalent values. Hence a search for X will return if X=A1 - * and A1=A2 and A2=A3 and ... and A9=A10 and A10=. - * - * If there are multiple terms in the WHERE clause of the form "X " - * then try for the one with no dependencies on - in other words where - * is a constant expression of some kind. Only return entries of - * the form "X Y" where Y is a column in another table if no terms of - * the form "X " exist. If no terms with a constant RHS - * exist, try to return a term that does not use WO_EQUIV. - */ -WhereTerm * -sqlite3WhereFindTerm(WhereClause * pWC, /* The WHERE clause to be searched */ - int iCur, /* Cursor number of LHS */ - int iColumn, /* Column number of LHS */ - Bitmask notReady, /* RHS must not overlap with this mask */ - u32 op, /* Mask of WO_xx values describing operator */ - Index * pIdx) /* Must be compatible with this index, if not NULL */ +struct WhereTerm * +sql_where_find_term(struct WhereClause *where, int cursor, int column, + uint64_t is_not_ready, u32 op, struct Index *index) { - WhereTerm *pResult = 0; - WhereTerm *p; - WhereScan scan; - - p = whereScanInit(&scan, pWC, iCur, iColumn, op, pIdx); + struct WhereScan scan; + struct WhereTerm *p = + whereScanInit(&scan, where, cursor, column, op, index); + struct WhereTerm *result = NULL; op &= WO_EQ; - while (p) { - if ((p->prereqRight & notReady) == 0) { - if (p->prereqRight == 0 && (p->eOperator & op) != 0) - return p; - if (pResult == 0) - pResult = p; - } - p = whereScanNext(&scan); + for (; p != NULL; p = whereScanNext(&scan)) { + if ((p->prereq_right_mask & is_not_ready) != 0) + continue; + if (p->prereq_right_mask == 0 && (p->eOperator & op) != 0) + return p; + if (result == NULL) + result = p; } - return pResult; + return result; } /** @@ -511,7 +479,7 @@ sqlite3WhereFindTerm(WhereClause * pWC, /* The WHERE clause to be searched */ */ static inline struct WhereTerm * where_clause_find_term(struct WhereClause *where_clause, int cursor, int column, - Bitmask is_ready, u32 op, struct space_def *space_def, + uint64_t is_ready, u32 op, struct space_def *space_def, struct key_def *key_def) { struct WhereTerm *result = NULL; @@ -520,8 +488,9 @@ where_clause_find_term(struct WhereClause *where_clause, int cursor, int column, column, op, space_def, key_def); op &= WO_EQ; while (p != NULL) { - if ((p->prereqRight & is_ready) == 0) { - if (p->prereqRight == 0 && (p->eOperator & op) != 0) + if ((p->prereq_right_mask & is_ready) == 0) { + if (p->prereq_right_mask == 0 && + (p->eOperator & op) != 0) return p; if (result == NULL) result = p; @@ -618,13 +587,14 @@ isDistinctRedundant(Parse * pParse, /* Parsing context */ continue; int col_count = pIdx->def->key_def->part_count; for (i = 0; i < col_count; i++) { - if (0 == - sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask) 0, - WO_EQ, pIdx)) { - if (findIndexCol - (pParse, pDistinct, iBase, pIdx, i) < 0) + if (sql_where_find_term(pWC, iBase, i, + COLUMN_MASK_FULL, WO_EQ, + pIdx) == NULL) { + if (findIndexCol(pParse, pDistinct, iBase, + pIdx, i) < 0) break; - uint32_t j = pIdx->def->key_def->parts[i].fieldno; + uint32_t j = + pIdx->def->key_def->parts[i].fieldno; if (pIdx->pTable->def->fields[j].is_nullable) break; } @@ -691,7 +661,7 @@ termCanDriveIndex(WhereTerm * pTerm, /* WHERE clause term to check */ return 0; if ((pTerm->eOperator & WO_EQ) == 0) return 0; - if ((pTerm->prereqRight & notReady) != 0) + if ((pTerm->prereq_right_mask & notReady) != 0) return 0; if (pTerm->u.leftColumn < 0) return 0; @@ -1643,8 +1613,8 @@ whereTermPrint(WhereTerm * pTerm, int iTerm) } else if ((pTerm->eOperator & WO_OR) != 0 && pTerm->u.pOrInfo != 0) { sqlite3_snprintf(sizeof(zLeft), zLeft, - "indexable=0x%lld", - pTerm->u.pOrInfo->indexable); + "indexable_mask=0x%lld", + pTerm->u.pOrInfo->indexable_mask); } else { sqlite3_snprintf(sizeof(zLeft), zLeft, "left=%d", pTerm->leftCursor); @@ -1688,10 +1658,11 @@ whereLoopPrint(WhereLoop * p, WhereClause * pWC) int nb = 1 + (pWInfo->pTabList->nSrc + 3) / 4; struct SrcList_item *pItem = pWInfo->pTabList->a + p->iTab; Table *pTab = pItem->pTab; - Bitmask mAll = (((Bitmask) 1) << (nb * 4)) - 1; + uint64_t all_mask = COLUMN_MASK_BIT(nb * 4) - 1;; #ifdef SQLITE_DEBUG sqlite3DebugPrintf("%c%2d.%0*llx.%0*llx", p->cId, - p->iTab, nb, p->maskSelf, nb, p->prereq & mAll); + p->iTab, nb, p->self_mask, nb, + p->prereq_mask & all_mask); sqlite3DebugPrintf(" %12s", pItem->zAlias ? pItem->zAlias : pTab->def->name); #endif @@ -1883,10 +1854,10 @@ whereLoopCheaperProperSubset(const WhereLoop * pX, /* First WhereLoop to compare if (j < 0) return 0; /* X not a subset of Y since term X[i] not used by Y */ } - if ((pX->wsFlags & WHERE_IDX_ONLY) != 0 - && (pY->wsFlags & WHERE_IDX_ONLY) == 0) { - return 0; /* Constraint (5) */ - } + /* Constraint (5). */ + if ((pX->wsFlags & WHERE_IDX_ONLY) != 0 && + (pY->wsFlags & WHERE_IDX_ONLY) == 0) + return 0; return 1; /* All conditions meet */ } @@ -1972,9 +1943,11 @@ whereLoopFindLesser(WhereLoop ** ppPrev, const WhereLoop * pTemplate) assert(p->rSetup == 0 || pTemplate->rSetup == 0 || p->rSetup == pTemplate->rSetup); - /* whereLoopAddBtree() always generates and inserts the automatic index - * case first. Hence compatible candidate WhereLoops never have a larger - * rSetup. Call this SETUP-INVARIANT + /* + * sql_where_loop_add_btree() always generates + * and inserts the automatic index case first. + * Hence compatible candidate WhereLoops never + * have a larger rSetup. Call this SETUP-INVARIANT. */ assert(p->rSetup >= pTemplate->rSetup); @@ -1986,32 +1959,28 @@ whereLoopFindLesser(WhereLoop ** ppPrev, const WhereLoop * pTemplate) && (pTemplate->nSkip) == 0 && (pTemplate->wsFlags & WHERE_INDEXED) != 0 && (pTemplate->wsFlags & WHERE_COLUMN_EQ) != 0 - && (p->prereq & pTemplate->prereq) == pTemplate->prereq) { + && (p->prereq_mask & pTemplate->prereq_mask) == + pTemplate->prereq_mask) break; - } /* If existing WhereLoop p is better than pTemplate, pTemplate can be * discarded. WhereLoop p is better if: * (1) p has no more dependencies than pTemplate, and * (2) p has an equal or lower cost than pTemplate */ - if ((p->prereq & pTemplate->prereq) == p->prereq /* (1) */ - && p->rSetup <= pTemplate->rSetup /* (2a) */ - && p->rRun <= pTemplate->rRun /* (2b) */ - && p->nOut <= pTemplate->nOut /* (2c) */ - ) { - return 0; /* Discard pTemplate */ - } + if ((p->prereq_mask & pTemplate->prereq_mask) == + p->prereq_mask && p->rSetup <= pTemplate->rSetup && + p->rRun <= pTemplate->rRun && p->nOut <= pTemplate->nOut) + return 0; /* If pTemplate is always better than p, then cause p to be overwritten * with pTemplate. pTemplate is better than p if: * (1) pTemplate has no more dependences than p, and * (2) pTemplate has an equal or lower cost than p. */ - if ((p->prereq & pTemplate->prereq) == pTemplate->prereq /* (1) */ - && p->rRun >= pTemplate->rRun /* (2a) */ - && p->nOut >= pTemplate->nOut /* (2b) */ - ) { + if ((p->prereq_mask & pTemplate->prereq_mask) == + pTemplate->prereq_mask && p->rRun >= pTemplate->rRun && + p->nOut >= pTemplate->nOut) { assert(p->rSetup >= pTemplate->rSetup); /* SETUP-INVARIANT above */ break; /* Cause p to be overwritten by pTemplate */ } @@ -2060,9 +2029,10 @@ whereLoopInsert(WhereLoopBuilder * pBuilder, WhereLoop * pTemplate) u16 n = pBuilder->pOrSet->n; int x = #endif - whereOrInsert(pBuilder->pOrSet, pTemplate->prereq, - pTemplate->rRun, - pTemplate->nOut); + sql_where_or_set_append(pBuilder->pOrSet, + pTemplate->prereq_mask, + pTemplate->rRun, + pTemplate->nOut); #ifdef WHERETRACE_ENABLED /* 0x8 */ if (sqlite3WhereTrace & 0x8) { sqlite3DebugPrintf(x ? " or-%d: " : @@ -2181,7 +2151,7 @@ whereLoopOutputAdjust(WhereClause * pWC, /* The WHERE clause */ LogEst nRow) /* Number of rows in the entire table */ { WhereTerm *pTerm, *pX; - Bitmask notAllowed = ~(pLoop->prereq | pLoop->maskSelf); + uint64_t not_allowed_mask = ~(pLoop->prereq_mask | pLoop->self_mask); int i, j, k; LogEst iReduce = 0; /* pLoop->nOut should not exceed nRow-iReduce */ @@ -2189,9 +2159,9 @@ whereLoopOutputAdjust(WhereClause * pWC, /* The WHERE clause */ for (i = pWC->nTerm, pTerm = pWC->a; i > 0; i--, pTerm++) { if ((pTerm->wtFlags & TERM_VIRTUAL) != 0) break; - if ((pTerm->prereqAll & pLoop->maskSelf) == 0) + if ((pTerm->prereq_all_mask & pLoop->self_mask) == 0) continue; - if ((pTerm->prereqAll & notAllowed) != 0) + if ((pTerm->prereq_all_mask & not_allowed_mask) != 0) continue; for (j = pLoop->nLTerm - 1; j >= 0; j--) { pX = pLoop->aLTerm[j]; @@ -2326,7 +2296,6 @@ whereLoopAddBtreeIndex(WhereLoopBuilder * pBuilder, /* The WhereLoop factory */ WhereTerm *pTerm; /* A WhereTerm under consideration */ int opMask; /* Valid operators for constraints */ WhereScan scan; /* Iterator for WHERE terms */ - Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ u16 saved_nEq; /* Original value of pNew->nEq */ u16 saved_nBtm; /* Original value of pNew->nBtm */ @@ -2380,7 +2349,8 @@ whereLoopAddBtreeIndex(WhereLoopBuilder * pBuilder, /* The WhereLoop factory */ saved_nSkip = pNew->nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; - saved_prereq = pNew->prereq; + /* Original value of pNew->prereq_mask. */ + uint64_t saved_prereq = pNew->prereq_mask; saved_nOut = pNew->nOut; pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq, opMask, pProbe); @@ -2402,7 +2372,7 @@ whereLoopAddBtreeIndex(WhereLoopBuilder * pBuilder, /* The WhereLoop factory */ */ continue; } - if (pTerm->prereqRight & pNew->maskSelf) + if (pTerm->prereq_right_mask & pNew->self_mask) continue; /* Do not allow the upper bound of a LIKE optimization range constraint @@ -2430,8 +2400,8 @@ whereLoopAddBtreeIndex(WhereLoopBuilder * pBuilder, /* The WhereLoop factory */ if (whereLoopResize(db, pNew, pNew->nLTerm + 1)) break; /* OOM */ pNew->aLTerm[pNew->nLTerm++] = pTerm; - pNew->prereq = - (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; + pNew->prereq_mask = + (saved_prereq | pTerm->prereq_right_mask) & ~pNew->self_mask; assert(nInMul == 0 || (pNew->wsFlags & WHERE_COLUMN_NULL) != 0 @@ -2648,7 +2618,7 @@ whereLoopAddBtreeIndex(WhereLoopBuilder * pBuilder, /* The WhereLoop factory */ pNew->nOut = saved_nOut; pBuilder->nRecValid = nRecValid; } - pNew->prereq = saved_prereq; + pNew->prereq_mask = saved_prereq; pNew->nEq = saved_nEq; pNew->nBtm = saved_nBtm; pNew->nTop = saved_nTop; @@ -2756,74 +2726,86 @@ indexMightHelpWithOrderBy(WhereLoopBuilder * pBuilder, return 0; } -/* - * Add all WhereLoop objects for a single table of the join where the table - * is identified by pBuilder->pNew->iTab. +/** + * Add all WhereLoop objects for a single table of the join where + * the table is identified by loop_builder->pNew->iTab. * - * The costs (WhereLoop.rRun) of the b-tree loops added by this function - * are calculated as follows: + * The costs (WhereLoop.rRun) of the b-tree loops added by this + * function are calculated as follows: * rRun = log2(cost) * 10 * - * For a full scan, assuming the table (or index) contains nRow rows: + * For a full scan, assuming the table (or index) contains nRow + * rows: * - * cost = nRow * 3.0 // full-table scan - * cost = nRow * K -> 4.0 for Tarantool // scan of covering index - * cost = nRow * (K+3.0) -> 4.0 for Tarantool // scan of non-covering index + * full-table scan: + * cost = nRow * 3.0 + * scan of covering index: + * cost = nRow * K -> 4.0 for Tarantool + * scan of non-covering index: + * cost = nRow * (K+3.0) -> 4.0 for Tarantool * - * This formula forces usage of pk for full-table scan for Tarantool + * This formula forces usage of pk for full-table scan for + * Tarantool. * - * where K is a value between 1.1 and 3.0 set based on the relative - * estimated average size of the index and table records. + * where K is a value between 1.1 and 3.0 set based on the + * relative estimated average size of the index and table records. * - * For an index scan, where nVisit is the number of index rows visited - * by the scan, and nSeek is the number of seek operations required on - * the index b-tree: + * For an index scan, where nVisit is the number of index rows + * visited by the scan, and nSeek is the number of seek operations + * required on the index b-tree: * - * cost = nSeek * (log(nRow) + K * nVisit) // covering index - * cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index + * covering index: + * cost = nSeek * (log(nRow) + K * nVisit) + * non-covering index: + * cost = nSeek * (log(nRow) + (K+3.0) * nVisit) * - * Normally, nSeek is 1. nSeek values greater than 1 come about if the - * WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when - * implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans. + * Normally, nSeek is 1. nSeek values greater than 1 come about + * if the WHERE clause includes "x IN (....)" terms used in place + * of "x=?". Or when implicit "x IN (SELECT x FROM tbl)" terms are + * added for skip-scans. * - * The estimated values (nRow, nVisit, nSeek) often contain a large amount - * of uncertainty. For this reason, scoring is designed to pick plans that - * "do the least harm" if the estimates are inaccurate. For example, a - * log(nRow) factor is omitted from a non-covering index scan in order to - * bias the scoring in favor of using an index, since the worst-case - * performance of using an index is far better than the worst-case performance - * of a full table scan. + * The estimated values (nRow, nVisit, nSeek) often contain a + * large amount of uncertainty. For this reason, scoring is + * designed to pick plans that "do the least harm" if the + * estimates are inaccurate. For example, a log(nRow) factor is + * omitted from a non-covering index scan in order to bias the + * scoring in favor of using an index, since the worst-case + * performance of using an index is far better than the worst-case + * performance of a full table scan. + * + * @param loop_builder WHERE clause information. + * @param prereq_mask Extra prerequesites for using this table. + * @retval 0 On success, not 0 elsewhere. */ static int -whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ - Bitmask mPrereq) /* Extra prerequesites for using this table */ +sql_where_loop_add_btree(struct WhereLoopBuilder *loop_builder, + uint64_t prereq_mask) { - WhereInfo *pWInfo; /* WHERE analysis context */ - Index *pProbe; /* An index we are evaluating */ Index fake_index; /* A fake index object for the primary key */ - SrcList *pTabList; /* The FROM clause */ - struct SrcList_item *pSrc; /* The FROM clause btree term to add */ - WhereLoop *pNew; /* Template WhereLoop object */ int rc = SQLITE_OK; /* Return code */ int iSortIdx = 1; /* Index number */ - int b; /* A boolean value */ LogEst rSize; /* number of rows in the table */ - WhereClause *pWC; /* The parsed WHERE clause */ - Table *pTab; /* Table being queried */ - pNew = pBuilder->pNew; - pWInfo = pBuilder->pWInfo; - pTabList = pWInfo->pTabList; - pSrc = pTabList->a + pNew->iTab; - pTab = pSrc->pTab; - pWC = pBuilder->pWC; - - if (pSrc->pIBIndex) { - /* An INDEXED BY clause specifies a particular index to use */ - pProbe = pSrc->pIBIndex; + /* Template WhereLoop object. */ + struct WhereLoop *new_where_loop = loop_builder->pNew; + /* WHERE analysis context. */ + struct WhereInfo *where_info = loop_builder->pWInfo; + /* The FROM clause. */ + struct SrcList *tab_list = where_info->pTabList; + /* The FROM clause btree term to add. */ + struct SrcList_item *src_list_table = tab_list->a + new_where_loop->iTab; + /* Table being queried. */ + struct Table *table = src_list_table->pTab; + /* The parsed WHERE clause. */ + struct WhereClause *where_clause = loop_builder->pWC; + /* An index we are evaluating. */ + struct Index *index; + if (src_list_table->pIBIndex) { + /* An INDEXED BY clause specifies a particular index to use. */ + index = src_list_table->pIBIndex; fake_index.def = NULL; - } else if (pTab->pIndex) { - pProbe = pTab->pIndex; + } else if (table->pIndex) { + index = table->pIndex; fake_index.def = NULL; } else { /* There is no INDEXED BY clause. Create a fake Index object in local @@ -2833,16 +2815,16 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ */ Index *pFirst; /* First of real indices on the table */ memset(&fake_index, 0, sizeof(Index)); - fake_index.pTable = pTab; + fake_index.pTable = table; struct key_def *key_def = key_def_new(1); if (key_def == NULL) { - pWInfo->pParse->nErr++; - pWInfo->pParse->rc = SQL_TARANTOOL_ERROR; + where_info->pParse->nErr++; + where_info->pParse->rc = SQL_TARANTOOL_ERROR; return SQL_TARANTOOL_ERROR; } - key_def_set_part(key_def, 0, 0, pTab->def->fields[0].type, + key_def_set_part(key_def, 0, 0, table->def->fields[0].type, ON_CONFLICT_ACTION_ABORT, NULL, COLL_NONE, SORT_ORDER_ASC); @@ -2850,7 +2832,7 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ index_opts_create(&opts); opts.sql = "fake_autoindex"; fake_index.def = - index_def_new(pTab->def->id, 0,"fake_autoindex", + index_def_new(table->def->id, 0,"fake_autoindex", sizeof("fake_autoindex") - 1, TREE, &opts, key_def, NULL); key_def_delete(key_def); @@ -2858,8 +2840,8 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ fake_index.def->iid = UINT32_MAX; if (fake_index.def == NULL) { - pWInfo->pParse->nErr++; - pWInfo->pParse->rc = SQL_TARANTOOL_ERROR; + where_info->pParse->nErr++; + where_info->pParse->rc = SQL_TARANTOOL_ERROR; return SQL_TARANTOOL_ERROR; } @@ -2867,18 +2849,18 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ (struct index_stat *) malloc(sizeof(struct index_stat)); stat->tuple_log_est = (log_est_t *) malloc(sizeof(log_est_t) * 2); - stat->tuple_log_est[0] = sql_space_tuple_log_count(pTab); + stat->tuple_log_est[0] = sql_space_tuple_log_count(table); stat->tuple_log_est[1] = 0; fake_index.def->opts.stat = stat; - pFirst = pSrc->pTab->pIndex; - if (pSrc->fg.notIndexed == 0) { + pFirst = src_list_table->pTab->pIndex; + if (src_list_table->fg.notIndexed == 0) { /* The real indices of the table are only considered if the * NOT INDEXED qualifier is omitted from the FROM clause */ fake_index.pNext = pFirst; } - pProbe = &fake_index; + index = &fake_index; } #ifndef SQLITE_OMIT_AUTOMATIC_INDEX @@ -2939,39 +2921,42 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ /* Loop over all indices */ - for (; rc == SQLITE_OK && pProbe; pProbe = pProbe->pNext, iSortIdx++) { - rSize = index_field_tuple_est(pProbe, 0); - pNew->nEq = 0; - pNew->nBtm = 0; - pNew->nTop = 0; - pNew->nSkip = 0; - pNew->nLTerm = 0; - pNew->iSortIdx = 0; - pNew->rSetup = 0; - pNew->prereq = mPrereq; - pNew->nOut = rSize; - pNew->pIndex = pProbe; - b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); + for (; rc == SQLITE_OK && index != NULL; + index = index->pNext, iSortIdx++) { + rSize = index_field_tuple_est(index, 0); + new_where_loop->nEq = 0; + new_where_loop->nBtm = 0; + new_where_loop->nTop = 0; + new_where_loop->nSkip = 0; + new_where_loop->nLTerm = 0; + new_where_loop->iSortIdx = 0; + new_where_loop->rSetup = 0; + new_where_loop->prereq_mask = prereq_mask; + new_where_loop->nOut = rSize; + new_where_loop->pIndex = index; + int b = indexMightHelpWithOrderBy(loop_builder, index, + src_list_table->iCursor); /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */ - assert((pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED) == 0 - || b == 0); - if (pProbe->def->iid == UINT32_MAX) { + assert((where_info->wctrlFlags & WHERE_ONEPASS_DESIRED) == 0 || + b == 0); + if (index->def->iid == UINT32_MAX) { /* Integer primary key index */ - pNew->wsFlags = WHERE_IPK; + new_where_loop->wsFlags = WHERE_IPK; /* Full table scan */ - pNew->iSortIdx = b ? iSortIdx : 0; + new_where_loop->iSortIdx = b != 0 ? iSortIdx : 0; /* TUNING: Cost of full table scan is (N*3.0). */ - pNew->rRun = rSize + 16; - whereLoopOutputAdjust(pWC, pNew, rSize); - rc = whereLoopInsert(pBuilder, pNew); - pNew->nOut = rSize; + new_where_loop->rRun = rSize + 16; + whereLoopOutputAdjust(where_clause, new_where_loop, + rSize); + rc = whereLoopInsert(loop_builder, new_where_loop); + new_where_loop->nOut = rSize; if (rc) break; } else { - pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; + new_where_loop->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED; /* Full scan via index */ - pNew->iSortIdx = b ? iSortIdx : 0; + new_where_loop->iSortIdx = b != 0 ? iSortIdx : 0; /* The cost of visiting the index rows is N*K, where K is * between 1.1 and 3.0 (3.0 and 4.0 for tarantool), @@ -2982,24 +2967,27 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ * of secondary indexes, because secondary indexes * are not really store any data (only pointers to tuples). */ - int notPkPenalty = sql_index_is_primary(pProbe) ? 0 : 4; - pNew->rRun = rSize + 16 + notPkPenalty; - whereLoopOutputAdjust(pWC, pNew, rSize); - rc = whereLoopInsert(pBuilder, pNew); - pNew->nOut = rSize; + int not_pk_penalty = + sql_index_is_primary(index) ? 0 : 4; + new_where_loop->rRun = rSize + 16 + not_pk_penalty; + whereLoopOutputAdjust(where_clause, new_where_loop, + rSize); + rc = whereLoopInsert(loop_builder, new_where_loop); + new_where_loop->nOut = rSize; if (rc) break; } - rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0); - sqlite3Stat4ProbeFree(pBuilder->pRec); - pBuilder->nRecValid = 0; - pBuilder->pRec = 0; + rc = whereLoopAddBtreeIndex(loop_builder, src_list_table, + index, 0); + sqlite3Stat4ProbeFree(loop_builder->pRec); + loop_builder->nRecValid = 0; + loop_builder->pRec = 0; /* If there was an INDEXED BY clause, then only that one index is * considered. */ - if (pSrc->pIBIndex) + if (src_list_table->pIBIndex != NULL) break; } if (fake_index.def != NULL) @@ -3010,132 +2998,150 @@ whereLoopAddBtree(WhereLoopBuilder * pBuilder, /* WHERE clause information */ return rc; } -/* +/** * Add WhereLoop entries to handle OR terms. + * @param loop_builder WHERE clause information. + * @param prereq_mask Extra prerequesites for using this table. + * @retval 0 On success, not 0 elsewhere. */ static int -whereLoopAddOr(WhereLoopBuilder * pBuilder, Bitmask mPrereq, Bitmask mUnusable) +sql_where_loop_add_or(struct WhereLoopBuilder *loop_builder, + uint64_t prereq_mask) { - WhereInfo *pWInfo = pBuilder->pWInfo; - WhereClause *pWC; - WhereLoop *pNew; - WhereTerm *pTerm, *pWCEnd; int rc = SQLITE_OK; - int iCur; - WhereClause tempWC; - WhereLoopBuilder sSubBuild; - WhereOrSet sSum, sCur; - struct SrcList_item *pItem; - - pWC = pBuilder->pWC; - pWCEnd = pWC->a + pWC->nTerm; - pNew = pBuilder->pNew; - memset(&sSum, 0, sizeof(sSum)); - pItem = pWInfo->pTabList->a + pNew->iTab; - iCur = pItem->iCursor; - - for (pTerm = pWC->a; pTerm < pWCEnd && rc == SQLITE_OK; pTerm++) { - if ((pTerm->eOperator & WO_OR) != 0 - && (pTerm->u.pOrInfo->indexable & pNew->maskSelf) != 0) { - WhereClause *const pOrWC = &pTerm->u.pOrInfo->wc; - WhereTerm *const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; - WhereTerm *pOrTerm; - int once = 1; - int i, j; - - sSubBuild = *pBuilder; - sSubBuild.pOrderBy = 0; - sSubBuild.pOrSet = &sCur; + struct WhereClause *where_clause = loop_builder->pWC; + struct WhereLoop *where_loop = loop_builder->pNew; + struct WhereOrSet where_costs_set; + memset(&where_costs_set, 0, sizeof(where_costs_set)); + struct WhereInfo *where_info = loop_builder->pWInfo; + struct SrcList_item *src_list_table = + where_info->pTabList->a + where_loop->iTab; + int cursor = src_list_table->iCursor; + struct WhereTerm *where_term = where_clause->a; + struct WhereTerm *where_term_end = + where_clause->a + where_clause->nTerm; + for (; where_term < where_term_end && rc == SQLITE_OK; where_term++) { + if ((where_term->eOperator & WO_OR) == 0 + || (where_term->u.pOrInfo->indexable_mask & + where_loop->self_mask) == 0) + continue; - WHERETRACE(0x200, - ("Begin processing OR-clause %p\n", pTerm)); - for (pOrTerm = pOrWC->a; pOrTerm < pOrWCEnd; pOrTerm++) { - if ((pOrTerm->eOperator & WO_AND) != 0) { - sSubBuild.pWC = - &pOrTerm->u.pAndInfo->wc; - } else if (pOrTerm->leftCursor == iCur) { - tempWC.pWInfo = pWC->pWInfo; - tempWC.pOuter = pWC; - tempWC.op = TK_AND; - tempWC.nTerm = 1; - tempWC.a = pOrTerm; - sSubBuild.pWC = &tempWC; - } else { - continue; - } - sCur.n = 0; + WHERETRACE(0x200, + ("Begin processing OR-clause %p\n", where_term)); + int once = 1; + struct WhereLoopBuilder sub_loop_builder; + sub_loop_builder = *loop_builder; + sub_loop_builder.pOrderBy = 0; + struct WhereOrSet where_or_set; + sub_loop_builder.pOrSet = &where_or_set; + struct WhereClause temp_wc; + + struct WhereClause *const or_wc = &where_term->u.pOrInfo->wc; + struct WhereTerm *or_term = or_wc->a; + struct WhereTerm *const or_term_end = &or_wc->a[or_wc->nTerm]; + for (; or_term < or_term_end; or_term++) { + if ((or_term->eOperator & WO_AND) != 0) { + sub_loop_builder.pWC = + &or_term->u.pAndInfo->wc; + } else if (or_term->leftCursor == cursor) { + temp_wc.pWInfo = where_clause->pWInfo; + temp_wc.pOuter = where_clause; + temp_wc.op = TK_AND; + temp_wc.nTerm = 1; + temp_wc.a = or_term; + sub_loop_builder.pWC = &temp_wc; + } else { + continue; + } + where_or_set.n = 0; #ifdef WHERETRACE_ENABLED - WHERETRACE(0x200, - ("OR-term %d of %p has %d subterms:\n", - (int)(pOrTerm - pOrWC->a), pTerm, - sSubBuild.pWC->nTerm)); - if (sqlite3WhereTrace & 0x400) { - sqlite3WhereClausePrint(sSubBuild.pWC); - } + WHERETRACE(0x200, + ("OR-term %d of %p has %d subterms:\n", + (int)(or_term - or_wc->a), where_term, + sub_loop_builder.pWC->nTerm)); + if (sqlite3WhereTrace & 0x400) { + sqlite3WhereClausePrint(sub_loop_builder. + pWC); + } #endif - { - rc = whereLoopAddBtree(&sSubBuild, - mPrereq); - } - if (rc == SQLITE_OK) { - rc = whereLoopAddOr(&sSubBuild, mPrereq, - mUnusable); - } - assert(rc == SQLITE_OK || sCur.n == 0); - if (sCur.n == 0) { - sSum.n = 0; - break; - } else if (once) { - whereOrMove(&sSum, &sCur); - once = 0; - } else { - WhereOrSet sPrev; - whereOrMove(&sPrev, &sSum); - sSum.n = 0; - for (i = 0; i < sPrev.n; i++) { - for (j = 0; j < sCur.n; j++) { - whereOrInsert(&sSum, - sPrev.a[i].prereq - | sCur.a[j].prereq, - sqlite3LogEstAdd(sPrev.a[i].rRun, - sCur.a[j].rRun), - sqlite3LogEstAdd(sPrev.a[i].nOut, - sCur.a[j].nOut)); - } + rc = sql_where_loop_add_btree(&sub_loop_builder, + prereq_mask); + if (rc == SQLITE_OK) { + rc = sql_where_loop_add_or(&sub_loop_builder, + prereq_mask); + } + assert(rc == SQLITE_OK || where_or_set.n == 0); + if (where_or_set.n == 0) { + where_costs_set.n = 0; + break; + } else if (once) { + whereOrMove(&where_costs_set, + &where_or_set); + once = 0; + } else { + struct WhereOrSet prev_costs_set; + whereOrMove(&prev_costs_set, &where_costs_set); + where_costs_set.n = 0; + for (int i = 0; i < prev_costs_set.n; i++) { + for (int j = 0; j < where_or_set.n; + j++) { + uint64_t prereq = + prev_costs_set.a[i]. + prereq_mask | + where_or_set.a[j]. + prereq_mask; + LogEst run_cost = + sqlite3LogEstAdd(prev_costs_set.a[i].rRun, + where_or_set.a[j].rRun); + LogEst outputs_cnt = + sqlite3LogEstAdd(prev_costs_set.a[i].nOut, + where_or_set.a[j].nOut); + sql_where_or_set_append(&where_costs_set, + prereq, + run_cost, + outputs_cnt); } } } - pNew->nLTerm = 1; - pNew->aLTerm[0] = pTerm; - pNew->wsFlags = WHERE_MULTI_OR; - pNew->rSetup = 0; - pNew->iSortIdx = 0; - pNew->nEq = 0; - pNew->nBtm = 0; - pNew->nTop = 0; - pNew->pIndex = NULL; - for (i = 0; rc == SQLITE_OK && i < sSum.n; i++) { - /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs - * of all sub-scans required by the OR-scan. However, due to rounding - * errors, it may be that the cost of the OR-scan is equal to its - * most expensive sub-scan. Add the smallest possible penalty - * (equivalent to multiplying the cost by 1.07) to ensure that - * this does not happen. Otherwise, for WHERE clauses such as the - * following where there is an index on "y": - * - * WHERE likelihood(x=?, 0.99) OR y=? - * - * the planner may elect to "OR" together a full-table scan and an - * index lookup. And other similarly odd results. - */ - pNew->rRun = sSum.a[i].rRun + 1; - pNew->nOut = sSum.a[i].nOut; - pNew->prereq = sSum.a[i].prereq; - rc = whereLoopInsert(pBuilder, pNew); - } - WHERETRACE(0x200, - ("End processing OR-clause %p\n", pTerm)); } + where_loop->nLTerm = 1; + where_loop->aLTerm[0] = where_term; + where_loop->wsFlags = WHERE_MULTI_OR; + where_loop->rSetup = 0; + where_loop->iSortIdx = 0; + where_loop->nEq = 0; + where_loop->nBtm = 0; + where_loop->nTop = 0; + where_loop->pIndex = NULL; + for (int i = 0; rc == SQLITE_OK && i < where_costs_set.n; i++) { + /* + * TUNING: + * Currently where_costs_set.a[i].rRun + * is where_or_set to the sum of the costs + * of all sub-scans required by the + * OR-scan. However, due to rounding + * errors, it may be that the cost of the + * OR-scan is equal to its most expensive + * sub-scan. Add the smallest possible + * penalty (equivalent to multiplying the + * cost by 1.07) to ensure that this does + * not happen. Otherwise, for WHERE + * clauses such as the following where + * there is an index on "y": + * + * WHERE likelihood(x=?, 0.99) OR y=? + * + * the planner may elect to "OR" together + * a full-table scan and an index lookup. + * And other similarly odd results. + */ + where_loop->rRun = where_costs_set.a[i].rRun + 1; + where_loop->nOut = where_costs_set.a[i].nOut; + where_loop->prereq_mask = where_costs_set.a[i].prereq_mask; + rc = whereLoopInsert(loop_builder, where_loop); + } + WHERETRACE(0x200, + ("End processing OR-clause %p\n", where_term)); } return rc; } @@ -3147,8 +3153,8 @@ static int whereLoopAddAll(WhereLoopBuilder * pBuilder) { WhereInfo *pWInfo = pBuilder->pWInfo; - Bitmask mPrereq = 0; - Bitmask mPrior = 0; + uint64_t prereq_mask = 0; + uint64_t prior_mask = 0; int iTab; SrcList *pTabList = pWInfo->pTabList; struct SrcList_item *pItem; @@ -3162,25 +3168,23 @@ whereLoopAddAll(WhereLoopBuilder * pBuilder) pNew = pBuilder->pNew; whereLoopInit(pNew); for (iTab = 0, pItem = pTabList->a; pItem < pEnd; iTab++, pItem++) { - Bitmask mUnusable = 0; pNew->iTab = iTab; - pNew->maskSelf = - sqlite3WhereGetMask(&pWInfo->sMaskSet, pItem->iCursor); + pNew->self_mask = + sql_where_get_mask(&pWInfo->sMaskSet, pItem->iCursor); if (((pItem->fg. jointype | priorJointype) & (JT_LEFT | JT_CROSS)) != 0) { /* This condition is true when pItem is the FROM clause term on the * right-hand-side of a LEFT or CROSS JOIN. */ - mPrereq = mPrior; + prereq_mask = prior_mask; } priorJointype = pItem->fg.jointype; { - rc = whereLoopAddBtree(pBuilder, mPrereq); - } - if (rc == SQLITE_OK) { - rc = whereLoopAddOr(pBuilder, mPrereq, mUnusable); + rc = sql_where_loop_add_btree(pBuilder, prereq_mask); } - mPrior |= pNew->maskSelf; + if (rc == SQLITE_OK) + rc = sql_where_loop_add_or(pBuilder, prereq_mask); + prior_mask |= pNew->self_mask; if (rc || db->mallocFailed) break; } @@ -3189,31 +3193,43 @@ whereLoopAddAll(WhereLoopBuilder * pBuilder) return rc; } -/* - * Examine a WherePath (with the addition of the extra WhereLoop of the 5th - * parameters) to see if it outputs rows in the requested ORDER BY - * (or GROUP BY) without requiring a separate sort operation. Return N: +/** + * Examine a WherePath (with the addition of the extra WhereLoop + * of the 5th parameters) to see if it outputs rows in the + * requested ORDER BY (or GROUP BY) without requiring a separate + * sort operation. * - * N>0: N terms of the ORDER BY clause are satisfied - * N==0: No terms of the ORDER BY clause are satisfied - * N<0: Unknown yet how many terms of ORDER BY might be satisfied. + * Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY + * is not as strict. With GROUP BY and DISTINCT the only + * requirement is that equivalent rows appear immediately adjacent + * to one another. GROUP BY + * and DISTINCT do not require rows to appear in any particular + * order as long as equivalent rows are grouped together. Thus + * for GROUP BY and DISTINCT the pOrderBy terms can be matched + * in any order. With ORDER BY, the pOrderBy terms must be + * matched in strict left-to-right order. + * @param where_info The WHERE clause. + * @param order_expr_list ORDER BY or GROUP BY or DISTINCT clause + * to check. + * @param where_path The WherePath to check. + * @param wctrl_flags WHERE_GROUPBY or _DISTINCTBY or + * _ORDERBY_LIMIT. + * @param loop_cnt Number of entries in pPath->aLoop[]. + * @param new_where_loop Add this WhereLoop to the end of + * pPath->aLoop[]. + * @param rev_mask Mask of WhereLoops to run in reverse order. * - * Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as - * strict. With GROUP BY and DISTINCT the only requirement is that - * equivalent rows appear immediately adjacent to one another. GROUP BY - * and DISTINCT do not require rows to appear in any particular order as long - * as equivalent rows are grouped together. Thus for GROUP BY and DISTINCT - * the pOrderBy terms can be matched in any order. With ORDER BY, the - * pOrderBy terms must be matched in strict left-to-right order. + * @retval N>0: On N terms of the ORDER BY clause are satisfied + * N==0: No terms of the ORDER BY clause are satisfied + * N<0: Unknown yet how many terms of ORDER BY might be + * satisfied. */ static i8 -wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ - ExprList * pOrderBy, /* ORDER BY or GROUP BY or DISTINCT clause to check */ - WherePath * pPath, /* The WherePath to check */ - u16 wctrlFlags, /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */ - u16 nLoop, /* Number of entries in pPath->aLoop[] */ - WhereLoop * pLast, /* Add this WhereLoop to the end of pPath->aLoop[] */ - Bitmask * pRevMask) /* OUT: Mask of WhereLoops to run in reverse order */ +sql_path_match_order_by(struct WhereInfo *where_info, + struct ExprList *order_expr_list, + struct WherePath *where_path, u16 wctrl_flags, + u16 loop_cnt, struct WhereLoop *new_where_loop, + uint64_t *rev_mask) { u8 revSet; /* True if rev is known */ u8 rev; /* Composite sort order */ @@ -3224,7 +3240,6 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ u16 eqOpMask; /* Allowed equality operators */ u16 nColumn; /* Total number of ordered columns in the index */ u16 nOrderBy; /* Number terms in the ORDER BY clause */ - int iLoop; /* Index of WhereLoop in pPath being processed */ int i, j; /* Loop counters */ int iCur; /* Cursor number for current WhereLoop */ int iColumn; /* A column number within table iCur */ @@ -3232,11 +3247,16 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ WhereTerm *pTerm; /* A single term of the WHERE clause */ Expr *pOBExpr; /* An expression from the ORDER BY clause */ Index *pIndex; /* The index associated with pLoop */ - sqlite3 *db = pWInfo->pParse->db; /* Database connection */ - Bitmask obSat = 0; /* Mask of ORDER BY terms satisfied so far */ - Bitmask obDone; /* Mask of all ORDER BY terms */ - Bitmask orderDistinctMask; /* Mask of all well-ordered loops */ - Bitmask ready; /* Mask of inner loops */ + /* Database connection. */ + struct sqlite3 *db = where_info->pParse->db; + /* Mask of ORDER BY terms satisfied so far. */ + uint64_t ob_sat_mask = 0; + /* Mask of all ORDER BY terms. */ + uint64_t ob_all_mask = 0; + /* Mask of all well-ordered loops. */ + uint64_t ob_dist_mask; + /* Mask of inner loops */ + uint64_t ready_mask; /* * We say the WhereLoop is "one-row" if it generates no more than one @@ -3256,33 +3276,32 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ * To be order-distinct, the columns must be UNIQUE and NOT NULL. */ - assert(pOrderBy != 0); - if (nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin)) + assert(order_expr_list != 0); + if (loop_cnt && OptimizationDisabled(db, SQLITE_OrderByIdxJoin)) return 0; - nOrderBy = pOrderBy->nExpr; - testcase(nOrderBy == BMS - 1); - if (nOrderBy > BMS - 1) + nOrderBy = order_expr_list->nExpr; + if (nOrderBy > COLUMN_MASK_SIZE - 1) return 0; /* Cannot optimize overly large ORDER BYs */ isOrderDistinct = 1; - obDone = MASKBIT(nOrderBy) - 1; - orderDistinctMask = 0; - ready = 0; + ob_all_mask = COLUMN_MASK_BIT(nOrderBy) - 1; + ob_dist_mask = 0; + ready_mask = 0; eqOpMask = WO_EQ | WO_ISNULL; - if (wctrlFlags & WHERE_ORDERBY_LIMIT) + if (wctrl_flags & WHERE_ORDERBY_LIMIT) eqOpMask |= WO_IN; - for (iLoop = 0; isOrderDistinct && obSat < obDone && iLoop <= nLoop; - iLoop++) { - if (iLoop > 0) - ready |= pLoop->maskSelf; - if (iLoop < nLoop) { - pLoop = pPath->aLoop[iLoop]; - if (wctrlFlags & WHERE_ORDERBY_LIMIT) + for (int loops_done = 0; isOrderDistinct && ob_sat_mask < ob_all_mask && loops_done <= loop_cnt; + loops_done++) { + if (loops_done > 0) + ready_mask |= pLoop->self_mask; + if (loops_done < loop_cnt) { + pLoop = where_path->aLoop[loops_done]; + if (wctrl_flags & WHERE_ORDERBY_LIMIT) continue; } else { - pLoop = pLast; + pLoop = new_where_loop; } - iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; + iCur = where_info->pTabList->a[pLoop->iTab].iCursor; /* Mark off any ORDER BY term X that is a column in the table of * the current loop for which there is term in the WHERE @@ -3290,25 +3309,24 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ * loops. */ for (i = 0; i < nOrderBy; i++) { - if (MASKBIT(i) & obSat) + if (COLUMN_MASK_BIT(i) & ob_sat_mask) continue; - pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr); + pOBExpr = sqlite3ExprSkipCollate(order_expr_list->a[i].pExpr); if (pOBExpr->op != TK_COLUMN) continue; if (pOBExpr->iTable != iCur) continue; - pTerm = - sqlite3WhereFindTerm(&pWInfo->sWC, iCur, - pOBExpr->iColumn, ~ready, - eqOpMask, 0); - if (pTerm == 0) + pTerm = sql_where_find_term(&where_info->sWC, iCur, + pOBExpr->iColumn, ~ready_mask, + eqOpMask, 0); + if (pTerm == NULL) continue; if (pTerm->eOperator == WO_IN) { /* IN terms are only valid for sorting in the ORDER BY LIMIT * optimization, and then only if they are actually used * by the query plan */ - assert(wctrlFlags & WHERE_ORDERBY_LIMIT); + assert(wctrl_flags & WHERE_ORDERBY_LIMIT); for (j = 0; j < pLoop->nLTerm && pTerm != pLoop->aLTerm[j]; j++) { @@ -3321,16 +3339,16 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ struct coll *coll1, *coll2; bool unused; uint32_t id; - coll1 = sql_expr_coll(pWInfo->pParse, - pOrderBy->a[i].pExpr, + coll1 = sql_expr_coll(where_info->pParse, + order_expr_list->a[i].pExpr, &unused, &id); - coll2 = sql_expr_coll(pWInfo->pParse, + coll2 = sql_expr_coll(where_info->pParse, pTerm->pExpr, &unused, &id); if (coll1 != coll2) continue; } - obSat |= MASKBIT(i); + column_mask_set_fieldno(&ob_sat_mask, i); } if ((pLoop->wsFlags & WHERE_ONEROW) == 0) { @@ -3428,13 +3446,11 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ */ isMatch = 0; for (i = 0; bOnce && i < nOrderBy; i++) { - if (MASKBIT(i) & obSat) + if (COLUMN_MASK_BIT(i) & ob_sat_mask) continue; pOBExpr = - sqlite3ExprSkipCollate(pOrderBy-> a[i].pExpr); - testcase(wctrlFlags & WHERE_GROUPBY); - testcase(wctrlFlags & WHERE_DISTINCTBY); - if ((wctrlFlags & (WHERE_GROUPBY | WHERE_DISTINCTBY)) == 0) + sqlite3ExprSkipCollate(order_expr_list-> a[i].pExpr); + if ((wctrl_flags & (WHERE_GROUPBY | WHERE_DISTINCTBY)) == 0) bOnce = 0; if (iColumn >= (-1)) { if (pOBExpr->op != TK_COLUMN) @@ -3450,8 +3466,8 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ bool is_found; uint32_t id; struct coll *coll = - sql_expr_coll(pWInfo->pParse, - pOrderBy->a[i].pExpr, + sql_expr_coll(where_info->pParse, + order_expr_list->a[i].pExpr, &is_found, &id); struct coll *idx_coll = pIndex->def->key_def->parts[j].coll; @@ -3463,26 +3479,25 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ break; } if (isMatch - && (wctrlFlags & WHERE_GROUPBY) == 0) { + && (wctrl_flags & WHERE_GROUPBY) == 0) { /* Make sure the sort order is compatible in an ORDER BY clause. * Sort order is irrelevant for a GROUP BY clause. */ if (revSet) { if ((rev ^ revIdx) != - pOrderBy->a[i].sort_order) + order_expr_list->a[i].sort_order) isMatch = 0; } else { rev = - revIdx ^ pOrderBy->a[i]. + revIdx ^ order_expr_list->a[i]. sort_order; if (rev) - *pRevMask |= - MASKBIT(iLoop); + column_mask_set_fieldno(rev_mask, loops_done); revSet = 1; } } if (isMatch) { - obSat |= MASKBIT(i); + column_mask_set_fieldno(&ob_sat_mask, i); } else { /* No match found */ if (j == 0 || j < nColumn) { @@ -3501,29 +3516,28 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo, /* The WHERE clause */ /* end-if not one-row */ /* Mark off any other ORDER BY terms that reference pLoop */ if (isOrderDistinct) { - orderDistinctMask |= pLoop->maskSelf; + ob_dist_mask |= pLoop->self_mask; for (i = 0; i < nOrderBy; i++) { Expr *p; - Bitmask mTerm; - if (MASKBIT(i) & obSat) + uint64_t mTerm; + if (COLUMN_MASK_BIT(i) & ob_sat_mask) continue; - p = pOrderBy->a[i].pExpr; + p = order_expr_list->a[i].pExpr; mTerm = - sqlite3WhereExprUsage(&pWInfo->sMaskSet, p); + sqlite3WhereExprUsage(&where_info->sMaskSet, p); if (mTerm == 0 && !sqlite3ExprIsConstant(p)) continue; - if ((mTerm & ~orderDistinctMask) == 0) { - obSat |= MASKBIT(i); - } + if ((mTerm & ~ob_dist_mask) == 0) + column_mask_set_fieldno(&ob_sat_mask, i); } } } /* End the loop over all WhereLoops from outer-most down to inner-most */ - if (obSat == obDone) + if (ob_sat_mask == ob_all_mask) return (i8) nOrderBy; if (!isOrderDistinct) { for (i = nOrderBy - 1; i > 0; i--) { - Bitmask m = MASKBIT(i) - 1; - if ((obSat & m) == m) + uint64_t m = COLUMN_MASK_BIT(i) - 1; + if ((ob_sat_mask & m) == m) return i; } return 0; @@ -3739,12 +3753,14 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) LogEst rCost; /* Cost of path (pFrom+pWLoop) */ LogEst rUnsorted; /* Unsorted cost of (pFrom+pWLoop) */ i8 isOrdered = pFrom->isOrdered; /* isOrdered for (pFrom+pWLoop) */ - Bitmask maskNew; /* Mask of src visited by (..) */ - Bitmask revMask = 0; /* Mask of rev-order loops for (..) */ + /* Mask of src visited by (..) */ + uint64_t new_mask; + /* Mask of rev-order loops for (..) */ + uint64_t rev_mask = 0; - if ((pWLoop->prereq & ~pFrom->maskLoop) != 0) + if ((pWLoop->prereq_mask & ~pFrom->loop_mask) != 0) continue; - if ((pWLoop->maskSelf & pFrom->maskLoop) != 0) + if ((pWLoop->self_mask & pFrom->loop_mask) != 0) continue; if ((pWLoop->wsFlags & WHERE_AUTO_INDEX) != 0 && pFrom->nRow < 10) { @@ -3764,18 +3780,20 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted); nOut = pFrom->nRow + pWLoop->nOut; - maskNew = pFrom->maskLoop | pWLoop->maskSelf; + new_mask = pFrom->loop_mask | pWLoop->self_mask; if (isOrdered < 0) { isOrdered = - wherePathSatisfiesOrderBy(pWInfo, - pWInfo->pOrderBy, - pFrom, - pWInfo->wctrlFlags, - iLoop, - pWLoop, - &revMask); + sql_path_match_order_by(pWInfo, + pWInfo-> + pOrderBy, + pFrom, + pWInfo-> + wctrlFlags, + iLoop, + pWLoop, + &rev_mask); } else { - revMask = pFrom->revLoop; + rev_mask = pFrom->rev_loop_mask; } if (isOrdered >= 0 && isOrdered < nOrderBy) { if (aSortCost[isOrdered] == 0) { @@ -3812,7 +3830,7 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) * of legal values for isOrdered, -1..64. */ for (jj = 0, pTo = aTo; jj < nTo; jj++, pTo++) { - if (pTo->maskLoop == maskNew + if (pTo->loop_mask == new_mask && ((pTo->isOrdered ^ isOrdered) & 0x80) == 0) { testcase(jj == nTo - 1); @@ -3917,8 +3935,8 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) #endif } /* pWLoop is a winner. Add it to the set of best so far */ - pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; - pTo->revLoop = revMask; + pTo->loop_mask = pFrom->loop_mask | pWLoop->self_mask; + pTo->rev_loop_mask = rev_mask; pTo->nRow = nOut; pTo->rCost = rCost; pTo->rUnsorted = rUnsorted; @@ -3958,7 +3976,7 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) 0 ? (pTo->isOrdered + '0') : '?'); if (pTo->isOrdered > 0) { sqlite3DebugPrintf(" rev=0x%llx\n", - pTo->revLoop); + pTo->rev_loop_mask); } else { sqlite3DebugPrintf("\n"); } @@ -3996,67 +4014,58 @@ wherePathSolver(WhereInfo * pWInfo, LogEst nRowEst) if ((pWInfo->wctrlFlags & WHERE_WANT_DISTINCT) != 0 && (pWInfo->wctrlFlags & WHERE_DISTINCTBY) == 0 && pWInfo->eDistinct == WHERE_DISTINCT_NOOP && nRowEst) { - Bitmask notUsed; - int rc = - wherePathSatisfiesOrderBy(pWInfo, pWInfo->pDistinctSet, - pFrom, - WHERE_DISTINCTBY, nLoop - 1, - pFrom->aLoop[nLoop - 1], - ¬Used); + uint64_t notUsed; + int rc = sql_path_match_order_by(pWInfo, + pWInfo->pDistinctSet, pFrom, + WHERE_DISTINCTBY, nLoop - 1, + pFrom->aLoop[nLoop - 1], + ¬Used); if (rc == pWInfo->pDistinctSet->nExpr) { pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } } if (pWInfo->pOrderBy) { if (pWInfo->wctrlFlags & WHERE_DISTINCTBY) { - if (pFrom->isOrdered == pWInfo->pOrderBy->nExpr) { + if (pFrom->isOrdered == pWInfo->pOrderBy->nExpr) pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; - } } else { pWInfo->nOBSat = pFrom->isOrdered; - pWInfo->revMask = pFrom->revLoop; - if (pWInfo->nOBSat <= 0) { - pWInfo->nOBSat = 0; - if (nLoop > 0) { - u32 wsFlags = - pFrom->aLoop[nLoop - 1]->wsFlags; - if ((wsFlags & WHERE_ONEROW) == 0 - && (wsFlags & (WHERE_IPK | WHERE_COLUMN_IN)) != (WHERE_IPK | WHERE_COLUMN_IN)) { - Bitmask m = 0; - int rc = - wherePathSatisfiesOrderBy - (pWInfo, pWInfo->pOrderBy, - pFrom, - WHERE_ORDERBY_LIMIT, - nLoop - 1, - pFrom->aLoop[nLoop - 1], - &m); - testcase(wsFlags & WHERE_IPK); - testcase(wsFlags & - WHERE_COLUMN_IN); - if (rc == - pWInfo->pOrderBy->nExpr) { - pWInfo-> - bOrderedInnerLoop = - 1; - pWInfo->revMask = m; - } - } + pWInfo->rev_mask = pFrom->rev_loop_mask; + if (pWInfo->nOBSat <= 0) + pWInfo->nOBSat = 0;; + u32 wsFlags = pFrom->aLoop[nLoop - 1]->wsFlags; + if ((pWInfo->nOBSat <= 0 && nLoop > 0) && + ((wsFlags & WHERE_ONEROW) == 0 && + (wsFlags & (WHERE_IPK | WHERE_COLUMN_IN)) != + (WHERE_IPK | WHERE_COLUMN_IN))) { + uint64_t m = 0; + int rc; + rc = sql_path_match_order_by(pWInfo, + pWInfo->pOrderBy, + pFrom, + WHERE_ORDERBY_LIMIT, + nLoop - 1, + pFrom-> + aLoop[nLoop - 1], + &m); + if (rc == pWInfo->pOrderBy->nExpr) { + pWInfo-> bOrderedInnerLoop = 1; + pWInfo->rev_mask = m; } } } if ((pWInfo->wctrlFlags & WHERE_SORTBYGROUP) && pWInfo->nOBSat == pWInfo->pOrderBy->nExpr && nLoop > 0) { - Bitmask revMask = 0; + uint64_t rev_mask = 0; int nOrder = - wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, - pFrom, 0, nLoop - 1, - pFrom->aLoop[nLoop - 1], - &revMask); + sql_path_match_order_by(pWInfo, pWInfo->pOrderBy, + pFrom, 0, nLoop - 1, + pFrom->aLoop[nLoop - 1], + &rev_mask); assert(pWInfo->sorted == 0); if (nOrder == pWInfo->pOrderBy->nExpr) { pWInfo->sorted = 1; - pWInfo->revMask = revMask; + pWInfo->rev_mask = rev_mask; } } } @@ -4142,8 +4151,8 @@ where_loop_builder_shortcut(struct WhereLoopBuilder *builder) loop->wsFlags = 0; loop->nSkip = 0; loop->pIndex = NULL; - struct WhereTerm *term = sqlite3WhereFindTerm(clause, cursor, -1, 0, - WO_EQ, 0); + struct WhereTerm *term = sql_where_find_term(clause, cursor, -1, 0, + WO_EQ, 0); if (term != NULL) { loop->wsFlags = WHERE_COLUMN_EQ | WHERE_IPK | WHERE_ONEROW; loop->aLTerm[0] = term; @@ -4176,8 +4185,8 @@ where_loop_builder_shortcut(struct WhereLoopBuilder *builder) if (loop->wsFlags) { loop->nOut = (LogEst) 1; where_info->a[0].pWLoop = loop; - loop->maskSelf = sqlite3WhereGetMask(&where_info->sMaskSet, - cursor); + loop->self_mask = sql_where_get_mask(&where_info->sMaskSet, + cursor); where_info->a[0].iTabCur = cursor; where_info->nRowOut = 1; if (where_info->pOrderBy) @@ -4296,7 +4305,6 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ - Bitmask notReady; /* Cursors that are not yet positioned */ WhereLoopBuilder sWLB; /* The WhereLoop builder */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ @@ -4329,8 +4337,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ memset(&sWLB, 0, sizeof(sWLB)); /* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */ - testcase(pOrderBy && pOrderBy->nExpr == BMS - 1); - if (pOrderBy && pOrderBy->nExpr >= BMS) + if (pOrderBy != 0 && pOrderBy->nExpr >= COLUMN_MASK_SIZE) pOrderBy = 0; sWLB.pOrderBy = pOrderBy; @@ -4342,11 +4349,11 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ } /* The number of tables in the FROM clause is limited by the number of - * bits in a Bitmask + * bits in a uint64_t */ - testcase(pTabList->nSrc == BMS); - if (pTabList->nSrc > BMS) { - sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); + if (pTabList->nSrc > COLUMN_MASK_SIZE) { + sqlite3ErrorMsg(pParse, "at most %d tables in a join", + COLUMN_MASK_SIZE); return 0; } @@ -4361,7 +4368,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ * return value. A single allocation is used to store the WhereInfo * struct, the contents of WhereInfo.a[], the WhereClause structure * and the WhereMaskSet structure. Since WhereClause contains an 8-byte - * field (type Bitmask) it must be aligned on an 8-byte boundary on + * field (type uint64_t) it must be aligned on an 8-byte boundary on * some architectures. Hence the ROUND8() below. */ nByteWInfo = @@ -4446,9 +4453,9 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ } #ifdef SQLITE_DEBUG for (ii = 0; ii < pTabList->nSrc; ii++) { - Bitmask m = - sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor); - assert(m == MASKBIT(ii)); + uint64_t m = + sql_where_get_mask(pMaskSet, pTabList->a[ii].iCursor); + assert(m == COLUMN_MASK_BIT(ii)); } #endif @@ -4514,18 +4521,16 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ } } if (pWInfo->pOrderBy == 0 && - (user_session->sql_flags & SQLITE_ReverseOrder) != 0) { - pWInfo->revMask = ALLBITS; - } - if (pParse->nErr || NEVER(db->mallocFailed)) { + (user_session->sql_flags & SQLITE_ReverseOrder) != 0) + pWInfo->rev_mask = COLUMN_MASK_FULL; + if (pParse->nErr != 0 || NEVER(db->mallocFailed != 0)) goto whereBeginError; - } #ifdef WHERETRACE_ENABLED if (sqlite3WhereTrace) { sqlite3DebugPrintf("---- Solution nRow=%d", pWInfo->nRowOut); if (pWInfo->nOBSat > 0) { sqlite3DebugPrintf(" ORDERBY=%d,0x%llx", pWInfo->nOBSat, - pWInfo->revMask); + pWInfo->rev_mask); } switch (pWInfo->eDistinct) { case WHERE_DISTINCT_UNIQUE:{ @@ -4551,10 +4556,10 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ if (pWInfo->nLevel >= 2 && pDistinctSet != 0 && OptimizationEnabled(db, SQLITE_OmitNoopJoin) ) { - Bitmask tabUsed = + uint64_t tab_used_mask = sqlite3WhereExprListUsage(pMaskSet, pDistinctSet); if (sWLB.pOrderBy) { - tabUsed |= + tab_used_mask |= sqlite3WhereExprListUsage(pMaskSet, sWLB.pOrderBy); } while (pWInfo->nLevel >= 2) { @@ -4567,11 +4572,11 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ && (pLoop->wsFlags & WHERE_ONEROW) == 0) { break; } - if ((tabUsed & pLoop->maskSelf) != 0) + if ((tab_used_mask & pLoop->self_mask) != 0) break; pEnd = sWLB.pWC->a + sWLB.pWC->nTerm; for (pTerm = sWLB.pWC->a; pTerm < pEnd; pTerm++) { - if ((pTerm->prereqAll & pLoop->maskSelf) != 0 + if ((pTerm->prereq_all_mask & pLoop->self_mask) != 0 && !ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) { @@ -4621,15 +4626,12 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ }; sqlite3OpenTable(pParse, pTabItem->iCursor, pTab, op); assert(pTabItem->iCursor == pLevel->iTabCur); - testcase(pWInfo->eOnePass == ONEPASS_OFF - && pTab->nCol == BMS - 1); - testcase(pWInfo->eOnePass == ONEPASS_OFF - && pTab->nCol == BMS); sqlite3VdbeChangeP5(v, bFordelete); #ifdef SQLITE_ENABLE_COLUMN_USED_MASK sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, pTabItem->iCursor, 0, 0, - (const u8 *)&pTabItem->colUsed, + (const u8 *) + &pTabItem->column_used_mask, P4_INT64); #endif } @@ -4727,7 +4729,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ VdbeComment((v, "%s", idx_def->name)); #ifdef SQLITE_ENABLE_COLUMN_USED_MASK { - u64 colUsed = 0; + u64 column_used_mask = 0; int ii, jj; for (ii = 0; ii < pIx->nColumn; ii++) { jj = pIx->aiColumn[ii]; @@ -4736,16 +4738,16 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ if (jj > 63) jj = 63; if ((pTabItem-> - colUsed & MASKBIT(jj)) == + column_used_mask & COLUMN_MASK_BIT(jj)) == 0) continue; - colUsed |= + column_used_mask |= ((u64) 1) << (ii < 63 ? ii : 63); } sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, iIndexCur, 0, 0, - (u8 *) & colUsed, + (u8 *) & column_used_mask, P4_INT64); } #endif /* SQLITE_ENABLE_COLUMN_USED_MASK */ @@ -4760,7 +4762,8 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ * loop below generates code for a single nested loop of the VM * program. */ - notReady = ~(Bitmask) 0; + /* Cursors that are not yet positioned. */ + uint64_t not_ready_mask = COLUMN_MASK_FULL; for (ii = 0; ii < nTabList; ii++) { int addrExplain; int wsFlags; @@ -4770,7 +4773,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ if ((pLevel->pWLoop->wsFlags & WHERE_AUTO_INDEX) != 0) { constructAutomaticIndex(pParse, &pWInfo->sWC, &pTabList->a[pLevel->iFrom], - notReady, pLevel); + not_ready_mask, pLevel); if (db->mallocFailed) goto whereBeginError; } @@ -4779,7 +4782,7 @@ sqlite3WhereBegin(Parse * pParse, /* The parser context */ sqlite3WhereExplainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags); pLevel->addrBody = sqlite3VdbeCurrentAddr(v); - notReady = sqlite3WhereCodeOneLoopStart(pWInfo, ii, notReady); + not_ready_mask = sql_where_code_one_loop(pWInfo, ii, not_ready_mask); pWInfo->iContinue = pLevel->addrCont; if ((wsFlags & WHERE_MULTI_OR) == 0 && (wctrlFlags & WHERE_OR_SUBCLAUSE) == 0) { diff --git a/src/box/sql/whereInt.h b/src/box/sql/whereInt.h index 889a667..eed1482 100644 --- a/src/box/sql/whereInt.h +++ b/src/box/sql/whereInt.h @@ -105,7 +105,8 @@ struct WhereLevel { Index *pCovidx; /* Possible covering index for WHERE_MULTI_OR */ } u; struct WhereLoop *pWLoop; /* The selected WhereLoop object */ - Bitmask notReady; /* FROM entries not usable at this level */ + /** FROM entries not usable at this level. */ + uint64_t not_ready_mask; #ifdef SQLITE_ENABLE_STMT_SCANSTATUS int addrVisit; /* Address at which row is visited */ #endif @@ -126,8 +127,10 @@ struct WhereLevel { * and that minimize the overall cost. */ struct WhereLoop { - Bitmask prereq; /* Bitmask of other loops that must run first */ - Bitmask maskSelf; /* Bitmask identifying table iTab */ + /** Bitmask of other loops that must run first. */ + uint64_t prereq_mask; + /** Bitmask identifying table iTab. */ + uint64_t self_mask; #ifdef SQLITE_DEBUG char cId; /* Symbolic ID of this loop for debugging use */ #endif @@ -159,7 +162,8 @@ struct WhereLoop { * See WhereOrSet for additional information */ struct WhereOrCost { - Bitmask prereq; /* Prerequisites */ + /** Prerequisites mask. */ + uint64_t prereq_mask; LogEst rRun; /* Cost of running this subquery */ LogEst nOut; /* Number of outputs for this subquery */ }; @@ -193,8 +197,10 @@ struct WhereOrSet { * at the end is the chosen query plan. */ struct WherePath { - Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ - Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ + /** Bitmask of all WhereLoop objects in this path. */ + uint64_t loop_mask; + /** aLoop[]s that should be reversed for ORDER BY. */ + uint64_t rev_loop_mask; LogEst nRow; /* Estimated number of rows generated by this path */ LogEst rCost; /* Total cost of this path */ LogEst rUnsorted; /* Total cost of this path ignoring sorting costs */ @@ -203,12 +209,14 @@ struct WherePath { }; /* - * The query generator uses an array of instances of this structure to - * help it analyze the subexpressions of the WHERE clause. Each WHERE - * clause subexpression is separated from the others by AND operators, - * usually, or sometimes subexpressions separated by OR. + * The query generator uses an array of instances of this + * structure to help it analyze the subexpressions of the WHERE + * clause. Each WHERE clause subexpression is separated from the + * others by AND operators, usually, or sometimes subexpressions + * separated by OR. * - * All WhereTerms are collected into a single WhereClause structure. + * All WhereTerms are collected into a single WhereClause + * structure. * The following identity holds: * * WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm @@ -218,11 +226,12 @@ struct WherePath { * X * * where X is a column name and is one of certain operators, - * then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the - * cursor number and column number for X. WhereTerm.eOperator records - * the using a bitmask encoding defined by WO_xxx below. The - * use of a bitmask encoding for the operator allows us to search - * quickly for terms that match any of several different operators. + * then WhereTerm.leftCursor and WhereTerm.u.leftColumn record + * the cursor number and column number for X. WhereTerm.eOperator + * records the using a bitmask encoding defined by + * WO_xxx below. The use of a bitmask encoding for the operator + * allows us to search quickly for terms that match any of several + * different operators. * * A WhereTerm might also be two or more subterms connected by OR: * @@ -237,20 +246,20 @@ struct WherePath { * to the original subexpression content and wtFlags is set up appropriately * but no other fields in the WhereTerm object are meaningful. * - * When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers, + * When eOperator!=0, prereq_right_mask and prereq_all_mask record sets of cursor numbers, * but they do so indirectly. A single WhereMaskSet structure translates - * cursor number into bits and the translated bit is stored in the prereq + * cursor number into bits and the translated bit is stored in the prereq_mask * fields. The translation is used in order to maximize the number of - * bits that will fit in a Bitmask. The VDBE cursor numbers might be + * bits that will fit in a uint64_t. The VDBE cursor numbers might be * spread out over the non-negative integers. For example, the cursor * numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet * translates these sparse cursor numbers into consecutive integers * beginning with 0 in order to make the best possible use of the available - * bits in the Bitmask. So, in the example above, the cursor numbers + * bits in the uint64_t. So, in the example above, the cursor numbers * would be mapped into integers 0 through 7. * * The number of terms in a join is limited by the number of bits - * in prereqRight and prereqAll. The default is 64 bits, hence SQLite + * in prereq_right_mask and prereq_all_mask. The default is 64 bits, hence SQLite * is only able to process joins with 64 or fewer tables. */ struct WhereTerm { @@ -268,8 +277,10 @@ struct WhereTerm { WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; - Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ - Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ + /** Bitmask of tables used by pExpr->pRight. */ + uint64_t prereq_right_mask; + /** Bitmask of tables referenced by pExpr. */ + uint64_t prereq_all_mask; }; /* @@ -340,7 +351,8 @@ struct WhereClause { */ struct WhereOrInfo { WhereClause wc; /* Decomposition into subterms */ - Bitmask indexable; /* Bitmask of all indexable tables in the clause */ + /** Bitmask of all indexable_mask tables in the clause. */ + uint64_t indexable_mask; }; /* @@ -379,7 +391,8 @@ struct WhereAndInfo { */ struct WhereMaskSet { int n; /* Number of assigned cursor values */ - int ix[BMS]; /* Cursor assigned to each bit */ + /** Cursor assigned to each bit. */ + int ix[COLUMN_MASK_SIZE]; }; /* @@ -431,29 +444,67 @@ struct WhereInfo { u8 bOrderedInnerLoop; /* True if only the inner-most loop is ordered */ int iTop; /* The very beginning of the WHERE loop */ WhereLoop *pLoops; /* List of all WhereLoop objects */ - Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ + /** Mask of ORDER BY terms that need reversing. */ + uint64_t rev_mask; LogEst nRowOut; /* Estimated number of output rows */ WhereClause sWC; /* Decomposition of the WHERE clause */ WhereMaskSet sMaskSet; /* Map cursor numbers to bitmasks */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; -/* - * Private interfaces - callable only by other where.c routines. - * - * where.c: +/** + * Return the bitmask for the given cursor number. + * @param mask_set Where masks assigned for cursors. + * @param cursor Cursor to get mask if any. + * @retval Return 0 if iCursor is not in the set. */ -Bitmask sqlite3WhereGetMask(WhereMaskSet *, int); +uint64_t +sql_where_get_mask(struct WhereMaskSet *mask_set, int cursor); + #ifdef WHERETRACE_ENABLED void sqlite3WhereClausePrint(WhereClause * pWC); #endif -WhereTerm *sqlite3WhereFindTerm(WhereClause * pWC, /* The WHERE clause to be searched */ - int iCur, /* Cursor number of LHS */ - int iColumn, /* Column number of LHS */ - Bitmask notReady, /* RHS must not overlap with this mask */ - u32 op, /* Mask of WO_xx values describing operator */ - Index * pIdx /* Must be compatible with this index, if not NULL */ - ); + +/** + * Search for a term in the WHERE clause that is of the form + * "X " where X is a reference to the @column of table + * @cursor or of @index if @index != NULL and is one of the + * WO_xx operator codes specified by the op parameter. Return a + * pointer to the term. Return 0 if not found. + * + * If @index != NULL then it must be one of the indexes of table + * @cursor. Search for terms matching the @column-th column of + * @index rather than the @column-th column of table @cursor. + * + * The term returned might by Y= if there is another + * constraint in the WHERE clause that specifies that X=Y. Any + * such constraints will be identified by the WO_EQUIV bit in the + * pTerm->eOperator field. The aiCur[]/iaColumn[] arrays hold X + * and all its equivalents. There are 11 slots in + * aiCur[]/aiColumn[] so that means we can look for X plus up to + * 10 other equivalent values. Hence a search for X will return + * if X=A1 and A1=A2 and A2=A3 and ... and A9=A10 and + * A10=. + * + * If there are multiple terms in the WHERE clause of the form + * "X " then try for the one with no dependencies on + * - in other words where is a constant expression + * of some kind. Only return entries of the form "X Y" + * where Y is a column in another table if no terms of the form + * "X " exist. If no terms with a constant RHS + * exist, try to return a term that does not use WO_EQUIV. + * + * @param where The WHERE clause to be searched. + * @param cursor Cursor number of LHS. + * @param column Column number of LHS. + * @param is_not_ready RHS must not overlap with this mask. + * @param op Mask of WO_xx values describing operator. + * @param index Must be compatible with this index, if not NULL. + * @retval not NULL WhereTerm pointer on found, NULL otherwise. + */ +struct WhereTerm * +sql_where_find_term(struct WhereClause *where, int cursor, int column, + uint64_t is_not_ready, u32 op, struct Index *index); /* wherecode.c: */ int sqlite3WhereExplainOneScan(Parse * pParse, /* Parse context */ @@ -472,22 +523,30 @@ void sqlite3WhereAddScanStatus(Vdbe * v, /* Vdbe to add scanstatus entry to */ #else #define sqlite3WhereAddScanStatus(a, b, c, d) ((void)d) #endif -Bitmask sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about the WHERE clause */ - int iLevel, /* Which level of pWInfo->a[] should be coded */ - Bitmask notReady /* Which tables are currently available */ - ); + +/** + * Generate code for the start of the iLevel-th loop in the WHERE clause + * implementation described by pWInfo. + * + * @param where_info Complete information about the WHERE clause. + * @param level Which level of pWInfo->a[] should be coded. + * @param not_ready_mask Which tables are currently available. + */ +uint64_t +sql_where_code_one_loop(struct WhereInfo *where_info, int level, + uint64_t not_ready_mask); /* whereexpr.c: */ void sqlite3WhereClauseInit(WhereClause *, WhereInfo *); void sqlite3WhereClauseClear(WhereClause *); void sqlite3WhereSplit(WhereClause *, Expr *, u8); -Bitmask sqlite3WhereExprUsage(WhereMaskSet *, Expr *); -Bitmask sqlite3WhereExprListUsage(WhereMaskSet *, ExprList *); +uint64_t sqlite3WhereExprUsage(WhereMaskSet *, Expr *); +uint64_t sqlite3WhereExprListUsage(WhereMaskSet *, ExprList *); void sqlite3WhereExprAnalyze(SrcList *, WhereClause *); void sqlite3WhereTabFuncArgs(Parse *, struct SrcList_item *, WhereClause *); /* - * Bitmasks for the operators on WhereTerm objects. These are all + * uint64_ts for the operators on WhereTerm objects. These are all * operators that are of interest to the query planner. An * OR-ed combination of these values can be used when searching for * particular WhereTerms within a WhereClause. diff --git a/src/box/sql/wherecode.c b/src/box/sql/wherecode.c index 13a045c..0e0ef89 100644 --- a/src/box/sql/wherecode.c +++ b/src/box/sql/wherecode.c @@ -360,7 +360,7 @@ disableTerm(WhereLevel * pLevel, WhereTerm * pTerm) && (pTerm->wtFlags & TERM_CODED) == 0 && (pLevel->iLeftJoin == 0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) - && (pLevel->notReady & pTerm->prereqAll) == 0) { + && (pLevel->not_ready_mask & pTerm->prereq_all_mask) == 0) { if (nLoop && (pTerm->wtFlags & TERM_LIKE) != 0) { pTerm->wtFlags |= TERM_LIKECOND; } else { @@ -883,46 +883,43 @@ codeExprOrVector(Parse * pParse, Expr * p, int iReg, int nReg) } } -/* - * Generate code for the start of the iLevel-th loop in the WHERE clause - * implementation described by pWInfo. - */ -Bitmask -sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about the WHERE clause */ - int iLevel, /* Which level of pWInfo->a[] should be coded */ - Bitmask notReady) /* Which tables are currently available */ + +uint64_t +sql_where_code_one_loop(struct WhereInfo *where_info, int level, + uint64_t not_ready_mask) { int j, k; /* Loop counters */ - int iCur; /* The VDBE cursor for the table */ int addrNxt; /* Where to jump to continue with the next IN case */ int omitTable; /* True if we use the index only */ - int bRev; /* True if we need to scan in reverse order */ - WhereLevel *pLevel; /* The where level to be coded */ - WhereLoop *pLoop; /* The WhereLoop object being coded */ - WhereClause *pWC; /* Decomposition of the entire WHERE clause */ WhereTerm *pTerm; /* A WHERE clause term */ - Parse *pParse; /* Parsing context */ - sqlite3 *db; /* Database connection */ - Vdbe *v; /* The prepared stmt under constructions */ - struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ int addrCont; /* Jump here to continue with next cycle */ - pParse = pWInfo->pParse; - v = pParse->pVdbe; - pWC = &pWInfo->sWC; - db = pParse->db; - pLevel = &pWInfo->a[iLevel]; - pLoop = pLevel->pWLoop; - pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; - iCur = pTabItem->iCursor; - pLevel->notReady = - notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); - bRev = (pWInfo->revMask >> iLevel) & 1; - omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY) != 0 - && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) == 0; - VdbeModuleComment((v, "Begin WHERE-loop%d: %s", iLevel, - pTabItem->pTab->zName)); + /* Parsing context. */ + struct Parse *parser = where_info->pParse; + /* The prepared stmt under constructions. */ + struct Vdbe *v = parser->pVdbe; + /* Decomposition of the entire WHERE clause. */ + struct WhereClause *where_clause = &where_info->sWC; + /* Database connection. */ + struct sqlite3 *db = parser->db; + /* The where level to be coded. */ + struct WhereLevel *where_level = &where_info->a[level]; + /* The WhereLoop object being coded. */ + struct WhereLoop *where_loop = where_level->pWLoop; + /* FROM clause term being coded. */ + struct SrcList_item *src_list_table = + &where_info->pTabList->a[where_level->iFrom]; + /* The VDBE cursor for the table. */ + int cursor = src_list_table->iCursor; + where_level->not_ready_mask = + not_ready_mask & ~sql_where_get_mask(&where_info->sMaskSet, cursor); + /* True if we need to scan in reverse order. */ + int is_reversed = (where_info->rev_mask >> level) & 1; + omitTable = (where_loop->wsFlags & WHERE_IDX_ONLY) != 0 && + (where_info->wctrlFlags & WHERE_OR_SUBCLAUSE) == 0; + VdbeModuleComment((v, "Begin WHERE-loop%d: %s", level, + src_list_table->pTab->zName)); /* Create labels for the "break" and "continue" instructions * for the current loop. Jump to addrBrk to break out of a loop. @@ -934,29 +931,33 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * there are no IN operators in the constraints, the "addrNxt" label * is the same as "addrBrk". */ - addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v); - addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v); + addrBrk = where_level->addrBrk = where_level->addrNxt = + sqlite3VdbeMakeLabel(v); + addrCont = where_level->addrCont = sqlite3VdbeMakeLabel(v); /* If this is the right table of a LEFT OUTER JOIN, allocate and * initialize a memory cell that records if this table matches any * row of the left table of the join. */ - if (pLevel->iFrom > 0 && (pTabItem[0].fg.jointype & JT_LEFT) != 0) { - pLevel->iLeftJoin = ++pParse->nMem; - sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin); + if (where_level->iFrom > 0 && + (src_list_table[0].fg.jointype & JT_LEFT) != 0) { + where_level->iLeftJoin = ++parser->nMem; + sqlite3VdbeAddOp2(v, OP_Integer, 0, where_level->iLeftJoin); VdbeComment((v, "init LEFT JOIN no-match flag")); } /* Special case of a FROM clause subquery implemented as a co-routine */ - if (pTabItem->fg.viaCoroutine) { - int regYield = pTabItem->regReturn; + if (src_list_table->fg.viaCoroutine) { + int regYield = src_list_table->regReturn; sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, - pTabItem->addrFillSub); - pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); + src_list_table->addrFillSub); + where_level->p2 = + sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); VdbeCoverage(v); - VdbeComment((v, "next row of \"%s\"", pTabItem->pTab->def->name)); - pLevel->op = OP_Goto; - } else if (pLoop->wsFlags & WHERE_INDEXED) { + VdbeComment((v, "next row of \"%s\"", + src_list_table->pTab->def->name)); + where_level->op = OP_Goto; + } else if (where_loop->wsFlags & WHERE_INDEXED) { /* Case 4: A scan using an index. * * The WHERE clause may contain zero or more equality @@ -991,22 +992,25 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t static const u8 aStartOp[] = { 0, 0, - OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */ - OP_Last, /* 3: (!start_constraints && startEq && bRev) */ - OP_SeekGT, /* 4: (start_constraints && !startEq && !bRev) */ - OP_SeekLT, /* 5: (start_constraints && !startEq && bRev) */ - OP_SeekGE, /* 6: (start_constraints && startEq && !bRev) */ - OP_SeekLE /* 7: (start_constraints && startEq && bRev) */ + OP_Rewind, /* 2: (!start_constraints && startEq && !is_reversed) */ + OP_Last, /* 3: (!start_constraints && startEq && is_reversed) */ + OP_SeekGT, /* 4: (start_constraints && !startEq && !is_reversed) */ + OP_SeekLT, /* 5: (start_constraints && !startEq && is_reversed) */ + OP_SeekGE, /* 6: (start_constraints && startEq && !is_reversed) */ + OP_SeekLE /* 7: (start_constraints && startEq && is_reversed) */ }; static const u8 aEndOp[] = { - OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */ - OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */ - OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */ - OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */ + OP_IdxGE, /* 0: (end_constraints && !is_reversed && !endEq) */ + OP_IdxGT, /* 1: (end_constraints && !is_reversed && endEq) */ + OP_IdxLE, /* 2: (end_constraints && is_reversed && !endEq) */ + OP_IdxLT, /* 3: (end_constraints && is_reversed && endEq) */ }; - u16 nEq = pLoop->nEq; /* Number of == or IN terms */ - u16 nBtm = pLoop->nBtm; /* Length of BTM vector */ - u16 nTop = pLoop->nTop; /* Length of TOP vector */ + /* Number of == or IN terms. */ + u16 eq_cnt = where_loop->nEq; + /* Length of BTM vector */ + u16 btm_cnt = where_loop->nBtm; + /* Length of TOP vector */ + u16 top_cnt = where_loop->nTop; int regBase; /* Base register holding constraint values */ WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ @@ -1026,31 +1030,31 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * to integer type, used for IPK. */ - struct Index *pIdx = pLoop->pIndex; - struct index_def *idx_def = pLoop->index_def; - assert(pIdx != NULL || idx_def != NULL); - iIdxCur = pLevel->iIdxCur; - assert(nEq >= pLoop->nSkip); + struct Index *index = where_loop->pIndex; + struct index_def *idx_def = where_loop->index_def; + assert(index != NULL || idx_def != NULL); + iIdxCur = where_level->iIdxCur; + assert(eq_cnt >= where_loop->nSkip); /* If this loop satisfies a sort order (pOrderBy) request that * was passed to this function to implement a "SELECT min(x) ..." * query, then the caller will only allow the loop to run for * a single iteration. This means that the first row returned * should not have a NULL value stored in 'x'. If column 'x' is - * the first one after the nEq equality constraints in the index, + * the first one after the eq_cnt equality constraints in the index, * this requires some special handling. */ - assert(pWInfo->pOrderBy == 0 - || pWInfo->pOrderBy->nExpr == 1 - || (pWInfo->wctrlFlags & WHERE_ORDERBY_MIN) == 0); + assert(where_info->pOrderBy == 0 || + where_info->pOrderBy->nExpr == 1 || + (where_info->wctrlFlags & WHERE_ORDERBY_MIN) == 0); uint32_t part_count; - if (pIdx != NULL) - part_count = pIdx->def->key_def->part_count; + if (index != NULL) + part_count = index->def->key_def->part_count; else part_count = idx_def->key_def->part_count; - if ((pWInfo->wctrlFlags & WHERE_ORDERBY_MIN) != 0 && - pWInfo->nOBSat > 0 && part_count > nEq) { - j = pIdx->def->key_def->parts[nEq].fieldno; + if ((where_info->wctrlFlags & WHERE_ORDERBY_MIN) != 0 && + where_info->nOBSat > 0 && part_count > eq_cnt) { + j = index->def->key_def->parts[eq_cnt].fieldno; /* Allow seek for column with `NOT NULL` == false attribute. * If a column may contain NULL-s, the comparator installed * by Tarantool is prepared to seek using a NULL value. @@ -1061,8 +1065,8 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * FYI: entries in an index are ordered as follows: * NULL, ... NULL, min_value, ... */ - if (pIdx->pTable->def->fields[j].is_nullable) { - assert(pLoop->nSkip == 0); + if (index->pTable->def->fields[j].is_nullable) { + assert(where_loop->nSkip == 0); bSeekPastNull = 1; nExtraReg = 1; } @@ -1071,43 +1075,43 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t /* Find any inequality constraint terms for the start and end * of the range. */ - j = nEq; - if (pLoop->wsFlags & WHERE_BTM_LIMIT) { - pRangeStart = pLoop->aLTerm[j++]; - nExtraReg = MAX(nExtraReg, pLoop->nBtm); + j = eq_cnt; + if (where_loop->wsFlags & WHERE_BTM_LIMIT) { + pRangeStart = where_loop->aLTerm[j++]; + nExtraReg = MAX(nExtraReg, where_loop->nBtm); /* Like optimization range constraints always occur in pairs */ assert((pRangeStart->wtFlags & TERM_LIKEOPT) == 0 || - (pLoop->wsFlags & WHERE_TOP_LIMIT) != 0); + (where_loop->wsFlags & WHERE_TOP_LIMIT) != 0); } - if (pLoop->wsFlags & WHERE_TOP_LIMIT) { - pRangeEnd = pLoop->aLTerm[j++]; - nExtraReg = MAX(nExtraReg, pLoop->nTop); + if (where_loop->wsFlags & WHERE_TOP_LIMIT) { + pRangeEnd = where_loop->aLTerm[j++]; + nExtraReg = MAX(nExtraReg, where_loop->nTop); #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS if ((pRangeEnd->wtFlags & TERM_LIKEOPT) != 0) { assert(pRangeStart != 0); /* LIKE opt constraints */ assert(pRangeStart->wtFlags & TERM_LIKEOPT); /* occur in pairs */ - pLevel->iLikeRepCntr = (u32)++ pParse->nMem; + where_level->iLikeRepCntr = (u32)++ parser->nMem; sqlite3VdbeAddOp2(v, OP_Integer, 1, - (int)pLevel->iLikeRepCntr); + (int)where_level->iLikeRepCntr); VdbeComment((v, "LIKE loop counter")); - pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); + where_level->addrLikeRep = sqlite3VdbeCurrentAddr(v); /* iLikeRepCntr actually stores 2x the counter register number. The * bottom bit indicates whether the search order is ASC or DESC. */ - testcase(bRev); - testcase(pIdx->aSortOrder[nEq] == + testcase(index->aSortOrder[eq_cnt] == SORT_ORDER_DESC); - assert((bRev & ~1) == 0); - struct key_def *def = pIdx->def->key_def; - pLevel->iLikeRepCntr <<= 1; - pLevel->iLikeRepCntr |= - bRev ^ (def->parts[nEq].sort_order == - SORT_ORDER_DESC); + assert((is_reversed & ~1) == 0); + struct key_def *def = index->def->key_def; + where_level->iLikeRepCntr <<= 1; + where_level->iLikeRepCntr |= + is_reversed ^ + (def->parts[eq_cnt].sort_order == + SORT_ORDER_DESC); } #endif if (pRangeStart == 0) { - j = pIdx->def->key_def->parts[nEq].fieldno; - if (pIdx->pTable->def->fields[j].is_nullable) + j = index->def->key_def->parts[eq_cnt].fieldno; + if (index->pTable->def->fields[j].is_nullable) bSeekPastNull = 1; } } @@ -1118,12 +1122,12 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * a forward order scan on a descending index, interchange the * start and end terms (pRangeStart and pRangeEnd). */ - if ((nEq < part_count && - bRev == (pIdx->def->key_def->parts[nEq].sort_order == - SORT_ORDER_ASC)) || (bRev && part_count == nEq)) { + if ((eq_cnt < part_count && is_reversed == + (index->def->key_def->parts[eq_cnt].sort_order == + SORT_ORDER_ASC)) || (is_reversed && part_count == eq_cnt)) { SWAP(pRangeEnd, pRangeStart); SWAP(bSeekPastNull, bStopAtNull); - SWAP(nBtm, nTop); + SWAP(btm_cnt, top_cnt); } /* Generate code to evaluate all constraint terms using == or IN @@ -1131,13 +1135,12 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * starting at regBase. */ regBase = - codeAllEqualityTerms(pParse, pLevel, bRev, nExtraReg, - &zStartAff); - assert(zStartAff == 0 || sqlite3Strlen30(zStartAff) >= nEq); - if (zStartAff && nTop) { - zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]); - } - addrNxt = pLevel->addrNxt; + codeAllEqualityTerms(parser, where_level, is_reversed, + nExtraReg, &zStartAff); + assert(zStartAff == 0 || sqlite3Strlen30(zStartAff) >= eq_cnt); + if (zStartAff && top_cnt) + zEndAff = sqlite3DbStrDup(db, &zStartAff[eq_cnt]); + addrNxt = where_level->addrNxt; testcase(pRangeStart && (pRangeStart->eOperator & WO_LE) != 0); testcase(pRangeStart && (pRangeStart->eOperator & WO_GE) != 0); @@ -1146,37 +1149,37 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE | WO_GE); endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE | WO_GE); - start_constraints = pRangeStart || nEq > 0; + start_constraints = pRangeStart || eq_cnt > 0; /* Seek the index cursor to the start of the range. */ - nConstraint = nEq; + nConstraint = eq_cnt; if (pRangeStart) { Expr *pRight = pRangeStart->pExpr->pRight; - codeExprOrVector(pParse, pRight, regBase + nEq, nBtm); + codeExprOrVector(parser, pRight, regBase + eq_cnt, btm_cnt); - whereLikeOptimizationStringFixup(v, pLevel, + whereLikeOptimizationStringFixup(v, where_level, pRangeStart); if ((pRangeStart->wtFlags & TERM_VNULL) == 0 && sqlite3ExprCanBeNull(pRight)) { - sqlite3VdbeAddOp2(v, OP_IsNull, regBase + nEq, + sqlite3VdbeAddOp2(v, OP_IsNull, regBase + eq_cnt, addrNxt); VdbeCoverage(v); } if (zStartAff) { - updateRangeAffinityStr(pRight, nBtm, - &zStartAff[nEq]); + updateRangeAffinityStr(pRight, btm_cnt, + &zStartAff[eq_cnt]); } - nConstraint += nBtm; + nConstraint += btm_cnt; testcase(pRangeStart->wtFlags & TERM_VIRTUAL); if (sqlite3ExprIsVector(pRight) == 0) { - disableTerm(pLevel, pRangeStart); + disableTerm(where_level, pRangeStart); } else { startEq = 1; } bSeekPastNull = 0; } else if (bSeekPastNull) { - sqlite3VdbeAddOp2(v, OP_Null, 0, regBase + nEq); + sqlite3VdbeAddOp2(v, OP_Null, 0, regBase + eq_cnt); nConstraint++; startEq = 0; start_constraints = 1; @@ -1184,7 +1187,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t struct Index *pk = NULL; struct index_def *idx_pk = NULL; char affinity; - if (pIdx == NULL) { + if (index == NULL) { struct space *space = space_cache_find(idx_def->space_id); assert(space != NULL); idx_pk = space->index[0]->def; @@ -1199,9 +1202,9 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t affinity = AFFINITY_BLOB; } } else { - pk = sqlite3PrimaryKeyIndex(pIdx->pTable); + pk = sqlite3PrimaryKeyIndex(index->pTable); uint32_t fieldno = pk->def->key_def->parts[0].fieldno; - affinity = pIdx->pTable->def->fields[fieldno].affinity; + affinity = index->pTable->def->fields[fieldno].affinity; } uint32_t pk_part_count; @@ -1215,10 +1218,10 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * here: try to loosely convert FLOAT to INT. If RHS type * is not INT or FLOAT - skip this ites, i.e. goto addrNxt. */ - int limit = pRangeStart == NULL ? nEq : nEq + 1; + int limit = pRangeStart == NULL ? eq_cnt : eq_cnt + 1; for (int i = 0; i < limit; i++) { - if ((pIdx != NULL && - pIdx->def->key_def->parts[i].fieldno == + if ((index != NULL && + index->def->key_def->parts[i].fieldno == pk->def->key_def->parts[0].fieldno) || (idx_pk != NULL && idx_def->key_def->parts[i].fieldno == @@ -1226,7 +1229,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t /* Here: we know for sure that table has INTEGER PRIMARY KEY, single column, and Index we're trying to use for scan contains this column. */ - if (i < nEq) + if (i < eq_cnt) sqlite3VdbeAddOp2(v, OP_MustBeInt, regBase + i, addrNxt); else force_integer_reg = regBase + i; @@ -1234,16 +1237,16 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t } } } - codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, + codeApplyAffinity(parser, regBase, nConstraint - bSeekPastNull, zStartAff); - if (pLoop->nSkip > 0 && nConstraint == pLoop->nSkip) { + if (where_loop->nSkip > 0 && nConstraint == where_loop->nSkip) { /* The skip-scan logic inside the call to codeAllEqualityConstraints() * above has already left the cursor sitting on the correct row, * so no further seeking is needed */ } else { op = aStartOp[(start_constraints << 2) + - (startEq << 1) + bRev]; + (startEq << 1) + is_reversed]; assert(op != 0); sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); @@ -1273,35 +1276,36 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t /* Load the value for the inequality constraint at the end of the * range (if any). */ - nConstraint = nEq; + nConstraint = eq_cnt; if (pRangeEnd) { Expr *pRight = pRangeEnd->pExpr->pRight; - sqlite3ExprCacheRemove(pParse, regBase + nEq, 1); - codeExprOrVector(pParse, pRight, regBase + nEq, nTop); - whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd); + sqlite3ExprCacheRemove(parser, regBase + eq_cnt, 1); + codeExprOrVector(parser, pRight, regBase + eq_cnt, top_cnt); + whereLikeOptimizationStringFixup(v, where_level, + pRangeEnd); if ((pRangeEnd->wtFlags & TERM_VNULL) == 0 && sqlite3ExprCanBeNull(pRight)) { - sqlite3VdbeAddOp2(v, OP_IsNull, regBase + nEq, + sqlite3VdbeAddOp2(v, OP_IsNull, regBase + eq_cnt, addrNxt); VdbeCoverage(v); } if (zEndAff) { - updateRangeAffinityStr(pRight, nTop, zEndAff); - codeApplyAffinity(pParse, regBase + nEq, nTop, + updateRangeAffinityStr(pRight, top_cnt, zEndAff); + codeApplyAffinity(parser, regBase + eq_cnt, top_cnt, zEndAff); } else { - assert(pParse->db->mallocFailed); + assert(parser->db->mallocFailed); } - nConstraint += nTop; + nConstraint += top_cnt; testcase(pRangeEnd->wtFlags & TERM_VIRTUAL); if (sqlite3ExprIsVector(pRight) == 0) { - disableTerm(pLevel, pRangeEnd); + disableTerm(where_level, pRangeEnd); } else { endEq = 1; } } else if (bStopAtNull) { - sqlite3VdbeAddOp2(v, OP_Null, 0, regBase + nEq); + sqlite3VdbeAddOp2(v, OP_Null, 0, regBase + eq_cnt); endEq = 0; nConstraint++; } @@ -1309,11 +1313,11 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t sqlite3DbFree(db, zEndAff); /* Top of the loop body */ - pLevel->p2 = sqlite3VdbeCurrentAddr(v); + where_level->p2 = sqlite3VdbeCurrentAddr(v); /* Check if the index cursor is past the end of the range. */ if (nConstraint) { - op = aEndOp[bRev * 2 + endEq]; + op = aEndOp[is_reversed * 2 + endEq]; sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); testcase(op == OP_IdxGT); @@ -1328,40 +1332,44 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t /* Seek the table cursor, if required */ if (omitTable) { - /* pIdx is a covering index. No need to access the main table. */ - } else if (iCur != iIdxCur) { - Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable); + /* + * Index is a covering index. + * No need to access the main table. + */ + } else if (cursor != iIdxCur) { + Index *pPk = sqlite3PrimaryKeyIndex(index->pTable); int pk_part_count = pPk->def->key_def->part_count; - int iKeyReg = sqlite3GetTempRange(pParse, pk_part_count); + int iKeyReg = sqlite3GetTempRange(parser, pk_part_count); for (j = 0; j < pk_part_count; j++) { k = pPk->def->key_def->parts[j].fieldno; sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iKeyReg + j); } - sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont, + sqlite3VdbeAddOp4Int(v, OP_NotFound, cursor, addrCont, iKeyReg, pk_part_count); VdbeCoverage(v); - sqlite3ReleaseTempRange(pParse, iKeyReg, pk_part_count); + sqlite3ReleaseTempRange(parser, iKeyReg, pk_part_count); } /* Record the instruction used to terminate the loop. */ - if (pLoop->wsFlags & WHERE_ONEROW) { - pLevel->op = OP_Noop; - } else if (bRev) { - pLevel->op = OP_Prev; + if (where_loop->wsFlags & WHERE_ONEROW) { + where_level->op = OP_Noop; + } else if (is_reversed) { + where_level->op = OP_Prev; } else { - pLevel->op = OP_Next; + where_level->op = OP_Next; } - pLevel->p1 = iIdxCur; - pLevel->p3 = (pLoop->wsFlags & WHERE_UNQ_WANTED) != 0 ? 1 : 0; - if ((pLoop->wsFlags & WHERE_CONSTRAINT) == 0) { - pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; + where_level->p1 = iIdxCur; + where_level->p3 = + (where_loop->wsFlags & WHERE_UNQ_WANTED) != 0 ? 1 : 0; + if ((where_loop->wsFlags & WHERE_CONSTRAINT) == 0) { + where_level->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } else { - assert(pLevel->p5 == 0); + assert(where_level->p5 == 0); } } else #ifndef SQLITE_OMIT_OR_OPTIMIZATION - if (pLoop->wsFlags & WHERE_MULTI_OR) { + if (where_loop->wsFlags & WHERE_MULTI_OR) { /* Case 5: Two or more separately indexed terms connected by OR * * Example: @@ -1380,56 +1388,59 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t WhereClause *pOrWc; /* The OR-clause broken out into subterms */ SrcList *pOrTab; /* Shortened table list or OR-clause generation */ Index *pCov = 0; /* Potential covering index (or NULL) */ - int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ + /* Cursor used for index scans (if any). */ + int iCovCur = parser->nTab++; - int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ + /* Register used with OP_Gosub. */ + int return_reg = ++parser->nMem; int regRowset = 0; /* Register for RowSet object */ int regPk = 0; /* Register holding PK */ int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ - int iRetInit; /* Address of regReturn init */ + int iRetInit; /* Address of return_reg init */ int untestedTerms = 0; /* Some terms not completely tested */ int ii; /* Loop counter */ u16 wctrlFlags; /* Flags for sub-WHERE clause */ Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ - Table *pTab = pTabItem->pTab; + Table *pTab = src_list_table->pTab; - pTerm = pLoop->aLTerm[0]; + pTerm = where_loop->aLTerm[0]; assert(pTerm != 0); assert(pTerm->eOperator & WO_OR); assert((pTerm->wtFlags & TERM_ORINFO) != 0); pOrWc = &pTerm->u.pOrInfo->wc; - pLevel->op = OP_Return; - pLevel->p1 = regReturn; + where_level->op = OP_Return; + where_level->p1 = return_reg; /* Set up a new SrcList in pOrTab containing the table being scanned - * by this loop in the a[0] slot and all notReady tables in a[1..] slots. + * by this loop in the a[0] slot and all not_ready_mask tables in a[1..] slots. * This becomes the SrcList in the recursive call to sqlite3WhereBegin(). */ - if (pWInfo->nLevel > 1) { - int nNotReady; /* The number of notReady tables */ + if (where_info->nLevel > 1) { + int nNotReady; /* The number of not_ready_mask tables */ struct SrcList_item *origSrc; /* Original list of tables */ - nNotReady = pWInfo->nLevel - iLevel - 1; + nNotReady = where_info->nLevel - level - 1; pOrTab = sqlite3StackAllocRaw(db, sizeof(*pOrTab) + nNotReady * sizeof(pOrTab->a[0])); if (pOrTab == 0) - return notReady; + return not_ready_mask; pOrTab->nAlloc = (u8) (nNotReady + 1); pOrTab->nSrc = pOrTab->nAlloc; - memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem)); - origSrc = pWInfo->pTabList->a; + memcpy(pOrTab->a, src_list_table, sizeof(*src_list_table)); + origSrc = where_info->pTabList->a; for (k = 1; k <= nNotReady; k++) { - memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], + memcpy(&pOrTab->a[k], + &origSrc[where_level[k].iFrom], sizeof(pOrTab->a[k])); } } else { - pOrTab = pWInfo->pTabList; + pOrTab = where_info->pTabList; } /* Create an ephemeral index capable of holding primary keys. * - * Also initialize regReturn to contain the address of the instruction + * Also initialize return_reg to contain the address of the instruction * immediately following the OP_Return at the bottom of the loop. This * is required in a few obscure LEFT JOIN cases where control jumps * over the top of the loop into the body of it. In this case the @@ -1437,16 +1448,16 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * fall through to the next instruction, just as an OP_Next does if * called on an uninitialized cursor. */ - if ((pWInfo->wctrlFlags & WHERE_DUPLICATES_OK) == 0) { + if ((where_info->wctrlFlags & WHERE_DUPLICATES_OK) == 0) { Index *pPk = sqlite3PrimaryKeyIndex(pTab); int pk_part_count = pPk->def->key_def->part_count; - regRowset = pParse->nTab++; + regRowset = parser->nTab++; sqlite3VdbeAddOp2(v, OP_OpenTEphemeral, regRowset, pk_part_count); - sql_vdbe_set_p4_key_def(pParse, pPk); - regPk = ++pParse->nMem; + sql_vdbe_set_p4_key_def(parser, pPk); + regPk = ++parser->nMem; } - iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); + iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, return_reg); /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y * Then for every term xN, evaluate as the subexpression: xN AND z @@ -1462,29 +1473,29 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * is not contained in the ON clause of a LEFT JOIN. * See ticket http://www.sqlite.org/src/info/f2369304e4 */ - if (pWC->nTerm > 1) { + if (where_clause->nTerm > 1) { int iTerm; - for (iTerm = 0; iTerm < pWC->nTerm; iTerm++) { - Expr *pExpr = pWC->a[iTerm].pExpr; - if (&pWC->a[iTerm] == pTerm) + for (iTerm = 0; iTerm < where_clause->nTerm; iTerm++) { + Expr *pExpr = where_clause->a[iTerm].pExpr; + if (&where_clause->a[iTerm] == pTerm) continue; if (ExprHasProperty(pExpr, EP_FromJoin)) continue; - testcase(pWC->a[iTerm].wtFlags & TERM_VIRTUAL); - testcase(pWC->a[iTerm].wtFlags & TERM_CODED); - if ((pWC->a[iTerm]. + testcase(where_clause->a[iTerm].wtFlags & TERM_VIRTUAL); + testcase(where_clause->a[iTerm].wtFlags & TERM_CODED); + if ((where_clause->a[iTerm]. wtFlags & (TERM_VIRTUAL | TERM_CODED)) != 0) continue; - if ((pWC->a[iTerm].eOperator & WO_ALL) == 0) + if ((where_clause->a[iTerm].eOperator & WO_ALL) == 0) continue; - testcase(pWC->a[iTerm].wtFlags & TERM_ORINFO); + testcase(where_clause->a[iTerm].wtFlags & TERM_ORINFO); pExpr = sqlite3ExprDup(db, pExpr, 0); pAndExpr = sqlite3ExprAnd(db, pAndExpr, pExpr); } if (pAndExpr) { pAndExpr = - sqlite3PExpr(pParse, + sqlite3PExpr(parser, TK_AND | TKFLG_DONTFOLD, 0, pAndExpr); } @@ -1495,11 +1506,11 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * sub-WHERE clause is to to invoke the main loop body as a subroutine. */ wctrlFlags = - WHERE_OR_SUBCLAUSE | (pWInfo-> + WHERE_OR_SUBCLAUSE | (where_info-> wctrlFlags & WHERE_SEEK_TABLE); for (ii = 0; ii < pOrWc->nTerm; ii++) { WhereTerm *pOrTerm = &pOrWc->a[ii]; - if (pOrTerm->leftCursor == iCur + if (pOrTerm->leftCursor == cursor || (pOrTerm->eOperator & WO_AND) != 0) { WhereInfo *pSubWInfo; /* Info for single OR-term scan */ Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */ @@ -1513,19 +1524,21 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t WHERETRACE(0xffff, ("Subplan for OR-clause:\n")); pSubWInfo = - sqlite3WhereBegin(pParse, pOrTab, pOrExpr, + sqlite3WhereBegin(parser, pOrTab, pOrExpr, 0, 0, wctrlFlags, iCovCur); - assert(pSubWInfo || pParse->nErr + assert(pSubWInfo || parser->nErr || db->mallocFailed); if (pSubWInfo) { WhereLoop *pSubLoop; int addrExplain = - sqlite3WhereExplainOneScan(pParse, + sqlite3WhereExplainOneScan(parser, pOrTab, - &pSubWInfo->a[0], - iLevel, - pLevel->iFrom, + &pSubWInfo-> + a[0], + level, + where_level-> + iFrom, 0); sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], @@ -1536,7 +1549,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * PRIMARY KEY for the current row so that the same * row will be skipped in subsequent sub-WHERE clauses. */ - if ((pWInfo-> + if ((where_info-> wctrlFlags & WHERE_DUPLICATES_OK) == 0) { int r; @@ -1547,7 +1560,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t pPk->def->key_def; /* Read the PK into an array of temp registers. */ - r = sqlite3GetTempRange(pParse, + r = sqlite3GetTempRange(parser, def->part_count); for (uint32_t iPk = 0; iPk < def->part_count; @@ -1556,10 +1569,10 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t def->parts[iPk]. fieldno; sqlite3ExprCodeGetColumnToReg - (pParse, + (parser, pTab->def, fieldno, - iCur, + cursor, r + iPk); } @@ -1593,12 +1606,12 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t } /* Release the array of temp registers */ - sqlite3ReleaseTempRange(pParse, r, def->part_count); + sqlite3ReleaseTempRange(parser, r, def->part_count); } /* Invoke the main loop body as a subroutine */ sqlite3VdbeAddOp2(v, OP_Gosub, - regReturn, iLoopBody); + return_reg, iLoopBody); /* Jump here (skipping the main loop body subroutine) if the * current sub-WHERE row is a duplicate from prior sub-WHEREs. @@ -1607,8 +1620,8 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t sqlite3VdbeJumpHere(v, jmp1); /* The pSubWInfo->untestedTerms flag means that this OR term - * contained one or more AND term from a notReady table. The - * terms from the notReady table could not be tested and will + * contained one or more AND term from a not_ready_mask table. The + * terms from the not_ready_mask table could not be tested and will * need to be tested later. */ if (pSubWInfo->untestedTerms) @@ -1643,21 +1656,21 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t } } } - pLevel->u.pCovidx = pCov; + where_level->u.pCovidx = pCov; if (pCov) - pLevel->iIdxCur = iCovCur; + where_level->iIdxCur = iCovCur; if (pAndExpr) { pAndExpr->pLeft = 0; sql_expr_delete(db, pAndExpr, false); } sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); - sqlite3VdbeGoto(v, pLevel->addrBrk); + sqlite3VdbeGoto(v, where_level->addrBrk); sqlite3VdbeResolveLabel(v, iLoopBody); - if (pWInfo->nLevel > 1) + if (where_info->nLevel > 1) sqlite3StackFree(db, pOrTab); if (!untestedTerms) - disableTerm(pLevel, pTerm); + disableTerm(where_level, pTerm); } else #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ @@ -1667,21 +1680,21 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t */ static const u8 aStep[] = { OP_Next, OP_Prev }; static const u8 aStart[] = { OP_Rewind, OP_Last }; - assert(bRev == 0 || bRev == 1); - if (pTabItem->fg.isRecursive) { + assert(is_reversed == 0 || is_reversed == 1); + if (src_list_table->fg.isRecursive) { /* Tables marked isRecursive have only a single row that is stored in * a pseudo-cursor. No need to Rewind or Next such cursors. */ - pLevel->op = OP_Noop; + where_level->op = OP_Noop; } else { - pLevel->op = aStep[bRev]; - pLevel->p1 = iCur; - pLevel->p2 = - 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, - addrBrk); - VdbeCoverageIf(v, bRev == 0); - VdbeCoverageIf(v, bRev != 0); - pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; + where_level->op = aStep[is_reversed]; + where_level->p1 = cursor; + where_level->p2 = + 1 + sqlite3VdbeAddOp2(v, aStart[is_reversed], + cursor, addrBrk); + VdbeCoverageIf(v, is_reversed == 0); + VdbeCoverageIf(v, is_reversed != 0); + where_level->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } } @@ -1692,25 +1705,24 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t /* Insert code to test every subexpression that can be completely * computed using the current set of tables. */ - for (pTerm = pWC->a, j = pWC->nTerm; j > 0; j--, pTerm++) { + for (pTerm = where_clause->a, j = where_clause->nTerm; j > 0; + j--, pTerm++) { Expr *pE; int skipLikeAddr = 0; testcase(pTerm->wtFlags & TERM_VIRTUAL); testcase(pTerm->wtFlags & TERM_CODED); if (pTerm->wtFlags & (TERM_VIRTUAL | TERM_CODED)) continue; - if ((pTerm->prereqAll & pLevel->notReady) != 0) { - testcase(pWInfo->untestedTerms == 0 - && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE) != - 0); - pWInfo->untestedTerms = 1; + if ((pTerm->prereq_all_mask & + where_level->not_ready_mask) != 0) { + where_info->untestedTerms = 1; continue; } pE = pTerm->pExpr; assert(pE != 0); - if (pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin)) { + if (where_level->iLeftJoin && + !ExprHasProperty(pE, EP_FromJoin)) continue; - } if (pTerm->wtFlags & TERM_LIKECOND) { /* If the TERM_LIKECOND flag is set, that means that the range search * is sufficient to guarantee that the LIKE operator is true, so we @@ -1721,7 +1733,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS continue; #else - u32 x = pLevel->iLikeRepCntr; + u32 x = where_level->iLikeRepCntr; assert(x > 0); skipLikeAddr = sqlite3VdbeAddOp1(v, (x & 1) ? OP_IfNot : OP_If, @@ -1729,7 +1741,7 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t VdbeCoverage(v); #endif } - sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); + sqlite3ExprIfFalse(parser, pE, addrCont, SQLITE_JUMPIFNULL); if (skipLikeAddr) sqlite3VdbeJumpHere(v, skipLikeAddr); pTerm->wtFlags |= TERM_CODED; @@ -1743,7 +1755,8 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t * then we cannot use the "t1.a=t2.b" constraint, but we can code * the implied "t1.a=123" constraint. */ - for (pTerm = pWC->a, j = pWC->nTerm; j > 0; j--, pTerm++) { + for (pTerm = where_clause->a, j = where_clause->nTerm; j > 0; + j--, pTerm++) { Expr *pE, sEAlt; WhereTerm *pAlt; if (pTerm->wtFlags & (TERM_VIRTUAL | TERM_CODED)) @@ -1752,16 +1765,17 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t continue; if ((pTerm->eOperator & WO_EQUIV) == 0) continue; - if (pTerm->leftCursor != iCur) + if (pTerm->leftCursor != cursor) continue; - if (pLevel->iLeftJoin) + if (where_level->iLeftJoin) continue; pE = pTerm->pExpr; assert(!ExprHasProperty(pE, EP_FromJoin)); - assert((pTerm->prereqRight & pLevel->notReady) != 0); - pAlt = - sqlite3WhereFindTerm(pWC, iCur, pTerm->u.leftColumn, - notReady, WO_EQ | WO_IN, 0); + assert((pTerm->prereq_right_mask & + where_level->not_ready_mask) != 0); + pAlt = sql_where_find_term(where_clause, cursor, + pTerm->u.leftColumn, not_ready_mask, + WO_EQ | WO_IN, 0); if (pAlt == 0) continue; if (pAlt->wtFlags & (TERM_CODED)) @@ -1771,32 +1785,33 @@ sqlite3WhereCodeOneLoopStart(WhereInfo * pWInfo, /* Complete information about t VdbeModuleComment((v, "begin transitive constraint")); sEAlt = *pAlt->pExpr; sEAlt.pLeft = pE->pLeft; - sqlite3ExprIfFalse(pParse, &sEAlt, addrCont, SQLITE_JUMPIFNULL); + sqlite3ExprIfFalse(parser, &sEAlt, addrCont, SQLITE_JUMPIFNULL); } /* For a LEFT OUTER JOIN, generate code that will record the fact that * at least one row of the right table has matched the left table. */ - if (pLevel->iLeftJoin) { - pLevel->addrFirst = sqlite3VdbeCurrentAddr(v); - sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin); + if (where_level->iLeftJoin != 0) { + where_level->addrFirst = sqlite3VdbeCurrentAddr(v); + sqlite3VdbeAddOp2(v, OP_Integer, 1, where_level->iLeftJoin); VdbeComment((v, "record LEFT JOIN hit")); - sqlite3ExprCacheClear(pParse); - for (pTerm = pWC->a, j = 0; j < pWC->nTerm; j++, pTerm++) { + sqlite3ExprCacheClear(parser); + for (pTerm = where_clause->a, j = 0; j < where_clause->nTerm; j++, pTerm++) { testcase(pTerm->wtFlags & TERM_VIRTUAL); testcase(pTerm->wtFlags & TERM_CODED); if (pTerm->wtFlags & (TERM_VIRTUAL | TERM_CODED)) continue; - if ((pTerm->prereqAll & pLevel->notReady) != 0) { - assert(pWInfo->untestedTerms); + if ((pTerm->prereq_all_mask & + where_level->not_ready_mask) != 0) { + assert(where_info->untestedTerms); continue; } assert(pTerm->pExpr); - sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, + sqlite3ExprIfFalse(parser, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL); pTerm->wtFlags |= TERM_CODED; } } - return pLevel->notReady; + return where_level->not_ready_mask; } diff --git a/src/box/sql/whereexpr.c b/src/box/sql/whereexpr.c index 6128686..2b208b1 100644 --- a/src/box/sql/whereexpr.c +++ b/src/box/sql/whereexpr.c @@ -126,7 +126,7 @@ whereClauseInsert(WhereClause * pWC, Expr * p, u16 wtFlags) /* * Return TRUE if the given operator is one of the operators that is - * allowed for an indexable WHERE clause term. The allowed operators are + * allowed for an indexable_mask WHERE clause term. The allowed operators are * "=", "<", ">", "<=", ">=", "IN", "IS", and "IS NULL" */ static int @@ -481,20 +481,20 @@ whereCombineDisjuncts(SrcList * pSrc, /* the FROM clause */ * * CASE 3: * - * If all subterms are indexable by a single table T, then set + * If all subterms are indexable_mask by a single table T, then set * * WhereTerm.eOperator = WO_OR - * WhereTerm.u.pOrInfo->indexable |= the cursor number for table T + * WhereTerm.u.pOrInfo->indexable_mask |= the cursor number for table T * - * A subterm is "indexable" if it is of the form + * A subterm is "indexable_mask" if it is of the form * "T.C " where C is any column of table T and * is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN". - * A subterm is also indexable if it is an AND of two or more - * subsubterms at least one of which is indexable. Indexable AND + * A subterm is also indexable_mask if it is an AND of two or more + * subsubterms at least one of which is indexable_mask. Indexable AND * subterms have their eOperator set to WO_AND and they have * u.pAndInfo set to a dynamically allocated WhereAndTerm object. * - * From another point of view, "indexable" means that the subterm could + * From another point of view, "indexable_mask" means that the subterm could * potentially be used with an index if an appropriate index exists. * This analysis does not consider whether or not the index exists; that * is decided elsewhere. This analysis only looks at whether subterms @@ -505,8 +505,8 @@ whereCombineDisjuncts(SrcList * pSrc, /* the FROM clause */ * always prefer case 1, so in that case we pretend that case 3 is not * satisfied. * - * It might be the case that multiple tables are indexable. For example, - * (E) above is indexable on tables P, Q, and R. + * It might be the case that multiple tables are indexable_mask. For example, + * (E) above is indexable_mask on tables P, Q, and R. * * OTHERWISE: * @@ -528,8 +528,6 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ WhereClause *pOrWc; /* Breakup of pTerm into subterms */ WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */ WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */ - Bitmask chngToIN; /* Tables that might satisfy case 1 */ - Bitmask indexable; /* Tables that are indexable, satisfying case 2 */ /* * Break the OR clause into its separate subterms. The subterms are @@ -555,21 +553,23 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ /* * Compute the set of tables that might satisfy cases 1 or 3. */ - indexable = ~(Bitmask) 0; - chngToIN = ~(Bitmask) 0; - for (i = pOrWc->nTerm - 1, pOrTerm = pOrWc->a; i >= 0 && indexable; + /* Tables that might satisfy case 1. */ + uint64_t chng_to_in_mask = COLUMN_MASK_FULL; + /* Tables that are indexable_mask, satisfying case 2. */ + uint64_t indexable_mask = COLUMN_MASK_FULL; + for (i = pOrWc->nTerm - 1, pOrTerm = pOrWc->a; i >= 0 && indexable_mask; i--, pOrTerm++) { if ((pOrTerm->eOperator & WO_SINGLE) == 0) { WhereAndInfo *pAndInfo; assert((pOrTerm-> wtFlags & (TERM_ANDINFO | TERM_ORINFO)) == 0); - chngToIN = 0; + chng_to_in_mask = 0; pAndInfo = sqlite3DbMallocRawNN(db, sizeof(*pAndInfo)); if (pAndInfo) { WhereClause *pAndWC; WhereTerm *pAndTerm; int j; - Bitmask b = 0; + uint64_t b = 0; pOrTerm->u.pAndInfo = pAndInfo; pOrTerm->wtFlags |= TERM_ANDINFO; pOrTerm->eOperator = WO_AND; @@ -581,42 +581,39 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ TK_AND); sqlite3WhereExprAnalyze(pSrc, pAndWC); pAndWC->pOuter = pWC; - if (!db->mallocFailed) { - for (j = 0, pAndTerm = pAndWC->a; - j < pAndWC->nTerm; - j++, pAndTerm++) { - assert(pAndTerm->pExpr); - if (allowedOp - (pAndTerm->pExpr->op) - || pAndTerm->eOperator == - WO_MATCH) { - b |= sqlite3WhereGetMask - (&pWInfo->sMaskSet, - pAndTerm-> - leftCursor); - } - } + if (db->mallocFailed) + break; + for (j = 0, pAndTerm = pAndWC->a; + j < pAndWC->nTerm; j++, pAndTerm++) { + assert(pAndTerm->pExpr != NULL); + if (!allowedOp(pAndTerm->pExpr->op) && + pAndTerm->eOperator != WO_MATCH) + continue; + b |= sql_where_get_mask(&pWInfo-> + sMaskSet, + pAndTerm-> + leftCursor); } - indexable &= b; + indexable_mask &= b; } } else if (pOrTerm->wtFlags & TERM_COPIED) { /* Skip this term for now. We revisit it when we process the * corresponding TERM_VIRTUAL term */ } else { - Bitmask b; - b = sqlite3WhereGetMask(&pWInfo->sMaskSet, - pOrTerm->leftCursor); + uint64_t b; + b = sql_where_get_mask(&pWInfo->sMaskSet, + pOrTerm->leftCursor); if (pOrTerm->wtFlags & TERM_VIRTUAL) { WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent]; - b |= sqlite3WhereGetMask(&pWInfo->sMaskSet, - pOther->leftCursor); + b |= sql_where_get_mask(&pWInfo->sMaskSet, + pOther->leftCursor); } - indexable &= b; + indexable_mask &= b; if ((pOrTerm->eOperator & WO_EQ) == 0) { - chngToIN = 0; + chng_to_in_mask = 0; } else { - chngToIN &= b; + chng_to_in_mask &= b; } } } @@ -625,12 +622,12 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ * Record the set of tables that satisfy case 3. The set might be * empty. */ - pOrInfo->indexable = indexable; - pTerm->eOperator = indexable == 0 ? 0 : WO_OR; + pOrInfo->indexable_mask = indexable_mask; + pTerm->eOperator = indexable_mask == 0 ? 0 : WO_OR; /* For a two-way OR, attempt to implementation case 2. */ - if (indexable && pOrWc->nTerm == 2) { + if (indexable_mask && pOrWc->nTerm == 2) { int iOne = 0; WhereTerm *pOne; while ((pOne = whereNthSubterm(&pOrWc->a[0], iOne++)) != 0) { @@ -644,11 +641,11 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ } /* - * chngToIN holds a set of tables that *might* satisfy case 1. But + * chng_to_in_mask holds a set of tables that *might* satisfy case 1. But * we have to do some additional checking to see if case 1 really * is satisfied. * - * chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means + * chng_to_in_mask will hold either 0, 1, or 2 bits. The 0-bit case means * that there is no possibility of transforming the OR clause into an * IN operator because one or more terms in the OR clause contain * something other than == on a column in the single table. The 1-bit @@ -664,7 +661,7 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ * Note that terms of the form "table.column1=table.column2" (the * same table on both sizes of the ==) cannot be optimized. */ - if (chngToIN) { + if (chng_to_in_mask != 0) { int okToChngToIN = 0; /* True if the conversion to IN is valid */ int iColumn = -1; /* Column index on lhs of IN operator */ int iCursor = -1; /* Table cursor common to all terms */ @@ -688,14 +685,17 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ assert(j == 1); continue; } - if ((chngToIN & - sqlite3WhereGetMask(&pWInfo->sMaskSet, - pOrTerm-> - leftCursor)) == 0) { - /* This term must be of the form t1.a==t2.b where t2 is in the - * chngToIN set but t1 is not. This term will be either preceded - * or follwed by an inverted copy (t2.b==t1.a). Skip this term - * and use its inversion. + if ((sql_where_get_mask(&pWInfo->sMaskSet, + pOrTerm->leftCursor) & + chng_to_in_mask) ==0) { + /* + * This term must be of the form + * t1.a==t2.b where t2 is in the + * chng_to_in_mask set but t1 is not. + * This term will be either preceded + * or follwed by an inverted copy + * (t2.b==t1.a). Skip this term and + * use its inversion. */ testcase(pOrTerm-> wtFlags & TERM_COPIED); @@ -715,9 +715,9 @@ exprAnalyzeOrTerm(SrcList * pSrc, /* the FROM clause */ * on the second iteration */ assert(j == 1); - assert(IsPowerOfTwo(chngToIN)); - assert(chngToIN == - sqlite3WhereGetMask(&pWInfo->sMaskSet, + assert(IsPowerOfTwo(chng_to_in_mask)); + assert(chng_to_in_mask == + sql_where_get_mask(&pWInfo->sMaskSet, iCursor)); break; } @@ -854,10 +854,10 @@ termIsEquivalence(Parse * pParse, Expr * pExpr) * a bitmask indicating which tables are used in that expression * tree. */ -static Bitmask +static uint64_t exprSelectUsage(WhereMaskSet * pMaskSet, Select * pS) { - Bitmask mask = 0; + uint64_t mask = 0; while (pS) { SrcList *pSrc = pS->pSrc; mask |= sqlite3WhereExprListUsage(pMaskSet, pS->pEList); @@ -947,9 +947,9 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ WhereTerm *pTerm; /* The term to be analyzed */ WhereMaskSet *pMaskSet; /* Set of table index masks */ Expr *pExpr; /* The expression to be analyzed */ - Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */ - Bitmask prereqAll; /* Prerequesites of pExpr */ - Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */ + uint64_t prereqLeft; /* Prerequesites of the pExpr->pLeft */ + uint64_t prereqAll; /* Prerequesites of pExpr */ + uint64_t extraRight = 0; /* Extra dependencies on LEFT JOIN */ Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */ int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */ int noCase = 0; /* uppercase equivalent to lowercase */ @@ -971,28 +971,28 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ if (sqlite3ExprCheckIN(pParse, pExpr)) return; if (ExprHasProperty(pExpr, EP_xIsSelect)) { - pTerm->prereqRight = + pTerm->prereq_right_mask = exprSelectUsage(pMaskSet, pExpr->x.pSelect); } else { - pTerm->prereqRight = + pTerm->prereq_right_mask = sqlite3WhereExprListUsage(pMaskSet, pExpr->x.pList); } } else if (op == TK_ISNULL) { - pTerm->prereqRight = 0; + pTerm->prereq_right_mask = 0; } else { - pTerm->prereqRight = + pTerm->prereq_right_mask = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight); } prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr); if (ExprHasProperty(pExpr, EP_FromJoin)) { - Bitmask x = - sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable); + uint64_t x = + sql_where_get_mask(pMaskSet, pExpr->iRightJoinTable); prereqAll |= x; extraRight = x - 1; /* ON clause terms may not be used with an index * on left table of a LEFT JOIN. Ticket #3015 */ } - pTerm->prereqAll = prereqAll; + pTerm->prereq_all_mask = prereqAll; pTerm->leftCursor = -1; pTerm->iParent = -1; pTerm->eOperator = 0; @@ -1001,7 +1001,7 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ Expr *pLeft = sqlite3ExprSkipCollate(pExpr->pLeft); Expr *pRight = sqlite3ExprSkipCollate(pExpr->pRight); u16 opMask = - (pTerm->prereqRight & prereqLeft) == 0 ? WO_ALL : WO_EQUIV; + (pTerm->prereq_right_mask & prereqLeft) == 0 ? WO_ALL : WO_EQUIV; if (pTerm->iField > 0) { assert(op == TK_IN); @@ -1050,8 +1050,8 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ pNew->leftCursor = iCur; pNew->u.leftColumn = iColumn; testcase((prereqLeft | extraRight) != prereqLeft); - pNew->prereqRight = prereqLeft | extraRight; - pNew->prereqAll = prereqAll; + pNew->prereq_right_mask = prereqLeft | extraRight; + pNew->prereq_all_mask = prereqAll; pNew->eOperator = (operatorMask(pDup->op) + eExtraOp) & opMask; } @@ -1277,14 +1277,14 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ TERM_VNULL); if (idxNew) { pNewTerm = &pWC->a[idxNew]; - pNewTerm->prereqRight = 0; + pNewTerm->prereq_right_mask = 0; pNewTerm->leftCursor = pLeft->iTable; pNewTerm->u.leftColumn = pLeft->iColumn; pNewTerm->eOperator = WO_GT; markTermAsChild(pWC, idxNew, idxTerm); pTerm = &pWC->a[idxTerm]; pTerm->wtFlags |= TERM_COPIED; - pNewTerm->prereqAll = pTerm->prereqAll; + pNewTerm->prereq_all_mask = pTerm->prereq_all_mask; } } @@ -1293,7 +1293,7 @@ exprAnalyze(SrcList * pSrc, /* the FROM clause */ */ testcase(pTerm != &pWC->a[idxTerm]); pTerm = &pWC->a[idxTerm]; - pTerm->prereqRight |= extraRight; + pTerm->prereq_right_mask |= extraRight; } /*************************************************************************** @@ -1379,14 +1379,14 @@ sqlite3WhereClauseClear(WhereClause * pWC) * a bitmask indicating which tables are used in that expression * tree. */ -Bitmask +uint64_t sqlite3WhereExprUsage(WhereMaskSet * pMaskSet, Expr * p) { - Bitmask mask; + uint64_t mask; if (p == 0) return 0; if (p->op == TK_COLUMN) { - mask = sqlite3WhereGetMask(pMaskSet, p->iTable); + mask = sql_where_get_mask(pMaskSet, p->iTable); return mask; } assert(!ExprHasProperty(p, EP_TokenOnly)); @@ -1401,11 +1401,11 @@ sqlite3WhereExprUsage(WhereMaskSet * pMaskSet, Expr * p) return mask; } -Bitmask +uint64_t sqlite3WhereExprListUsage(WhereMaskSet * pMaskSet, ExprList * pList) { int i; - Bitmask mask = 0; + uint64_t mask = 0; if (pList) { for (i = 0; i < pList->nExpr; i++) { mask |= -- 2.7.4