[tarantool-patches] [PATCH v1 0/4] sql: replace 32 bit column mask

[tarantool-patches] [PATCH v1 0/4] sql: replace 32 bit column mask

[Kirill Shcherbatov]

Column mask in Tarantool is not just 32 bits greater, but also it
is smarter. When a column with number > 63 is added to the mask,
the only last bit (64th) is set indicating the overflow.
SQLite mask in such a case just resets the whole mask in -1.

Reworked sqlite code to use Tarantool mask helpers everywhere.

Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-3571-sql-column-mask-64
Issue: https://github.com/tarantool/tarantool/issues/3571

Kirill Shcherbatov (4):
  box: introduce new helpers in column_mask.h
  sql: use 64b bitmasks instead of 32b where possible
  sql: got rid of redundant MASKBIT32 definition
  sql: got rid of redundant bitmask helpers

 src/box/alter.cc        |  10 +---
 src/box/column_mask.h   |  39 +++++++++++---
 src/box/sql/delete.c    |   8 ++-
 src/box/sql/expr.c      |  53 ++++++++++---------
 src/box/sql/resolve.c   |  31 +++--------
 src/box/sql/sqliteInt.h |  71 +++++++++++---------------
 src/box/sql/trigger.c   |  14 ++---
 src/box/sql/update.c    |  21 ++++----
 src/box/sql/vdbeaux.c   |   7 ++-
 src/box/sql/where.c     | 110 ++++++++++++++++++----------------------
 src/box/sql/whereInt.h  |   3 +-
 11 files changed, 175 insertions(+), 192 deletions(-)

-- 
2.20.1

[tarantool-patches] [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Kirill Shcherbatov]

Refactored column_mask.h definitions: introduced a new routine
column_mask_is_overflowed, column_mask_is_set and macro
COLUMN_MASK_BIT, COLUMN_MASK_SIZE.
We need this helpers in further refactoring.

Needed for #3571
---
 src/box/column_mask.h | 39 +++++++++++++++++++++++++++++++++------
 1 file changed, 33 insertions(+), 6 deletions(-)

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index d71911d46..6e9c0f81a 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,14 +63,14 @@
 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 |= COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
 	else
-		*column_mask |= ((uint64_t) 1) << fieldno;
+		*column_mask |= COLUMN_MASK_BIT(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,10 +92,35 @@ 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 |= COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
 	}
 }
 
+/**
+ * Test if overflow flag 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 & COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
+}
+
+/**
+ * Test a bit in the bitmask corresponding to a column fieldno.
+ * @param column_mask Mask to test.
+ * @param fieldno Fieldno number to test (index base must be 0).
+ * @retval true If bit corresponding to a column fieldno.
+ * @retval false if bit is not set or fieldno > COLUMN_MASK_SIZE.
+ */
+static inline bool
+column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
+{
+	return fieldno < COLUMN_MASK_SIZE &&
+	       (column_mask & COLUMN_MASK_BIT(fieldno)) != 0;
+}
+
 /**
  * True if the update operation does not change the key.
  * @param key_mask Key mask.
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Vladislav Shpilevoy]

Hi! Thanks for the patch! See 2 comments below.

On 08/02/2019 13:52, Kirill Shcherbatov wrote:
> Refactored column_mask.h definitions: introduced a new routine
> column_mask_is_overflowed, column_mask_is_set and macro
> COLUMN_MASK_BIT, COLUMN_MASK_SIZE.
> We need this helpers in further refactoring.
> 
> Needed for #3571
> ---
>   src/box/column_mask.h | 39 +++++++++++++++++++++++++++++++++------
>   1 file changed, 33 insertions(+), 6 deletions(-)
> 
> diff --git a/src/box/column_mask.h b/src/box/column_mask.h
> index d71911d46..6e9c0f81a 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))

1. COLUMN_MASK_BIT will return 0, when >= 64. Please, fix it
to return the last bit in such a case. Otherwise it is not
COLUMN_MASK_BIT, but just <<.

> +#define COLUMN_MASK_SIZE	((int)(sizeof(uint64_t)*8))

2. Not sure if it is worth macrosing, because anyway column
mask every where is uint64_t. If we want to hide a size,
we should introduce column_mask_t type.

>   
>   /**
>    * Set a bit in the bitmask corresponding to a
> @@ -90,10 +92,35 @@ 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 |= COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
>   	}
>   }
>   
> +/**
> + * Test if overflow flag 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 & COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
> +}
> +
> +/**
> + * Test a bit in the bitmask corresponding to a column fieldno.
> + * @param column_mask Mask to test.
> + * @param fieldno Fieldno number to test (index base must be 0).
> + * @retval true If bit corresponding to a column fieldno.
> + * @retval false if bit is not set or fieldno > COLUMN_MASK_SIZE.
> + */
> +static inline bool
> +column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
> +{
> +	return fieldno < COLUMN_MASK_SIZE &&
> +	       (column_mask & COLUMN_MASK_BIT(fieldno)) != 0;
> +}

3. If a field no >= 63, you should return true, if the last bit of
the mask is set - this is how the last bit works here. The bit 63
means fields [63, +inf].

Also, please, write tests for the new functions. We have unit tests
for column mask in test/unit/column_mask.c.

> +
>   /**
>    * True if the update operation does not change the key.
>    * @param key_mask Key mask.
> -- 
> 2.20.1
> 
> 

[tarantool-patches] Re: [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Kirill Shcherbatov]

> 1. COLUMN_MASK_BIT will return 0, when >= 64. Please, fix it
> to return the last bit in such a case. Otherwise it is not
> COLUMN_MASK_BIT, but just <<.

fixed:
+ uint64_t mask = (uint64_t) 1 << (fieldno < 63 ? fieldno : 63);
+ return (column_mask & mask) != 0;

> 2. Not sure if it is worth macrosing, because anyway column
> mask every where is uint64_t. If we want to hide a size,
> we should introduce column_mask_t type.
I also think so now. Let's introduce such macro in sqlInt with Bitmask.

So we have new helpers column_mask_is_overflowed, column_mask_fieldno_is_set,
column_mask32_set_fieldno, column_mask32_fieldno_is_set,
column_mask32_is_overflowed.

==================================

Refactored column_mask.h definitions: introduced a new routine
column_mask_is_overflowed, column_mask_is_set. Also a couple of
routines for 32-bit bitmask.
We need this helpers in further refactoring.

Needed for #3571
---
 src/box/column_mask.h        | 66 ++++++++++++++++++++++++++++++++++++
 test/unit/column_mask.c      | 33 +++++++++++++++++-
 test/unit/column_mask.result | 10 +++++-
 3 files changed, 107 insertions(+), 2 deletions(-)

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index d71911d46..f447d8386 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -94,6 +94,31 @@ column_mask_set_range(uint64_t *column_mask, uint32_t first_fieldno_in_range)
 	}
 }
 
+/**
+ * Test if overflow flag set in bitmask.
+ * @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 << 63);
+}
+
+/**
+ * Test a bit in the bitmask corresponding to a column fieldno.
+ * @param column_mask Mask to test.
+ * @param fieldno Fieldno number to test (index base must be 0).
+ * @retval true If bit corresponding to a column fieldno.
+ * @retval false if bit is not set or fieldno > 64.
+ */
+static inline bool
+column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
+{
+	uint64_t mask = (uint64_t) 1 << (fieldno < 63 ? fieldno : 63);
+	return (column_mask & mask) != 0;
+}
+
 /**
  * True if the update operation does not change the key.
  * @param key_mask Key mask.
@@ -109,4 +134,45 @@ key_update_can_be_skipped(uint64_t key_mask, uint64_t update_mask)
 	return (key_mask & update_mask) == 0;
 }
 
+/**
+ * Set a bit in the 32-bit bitmask corresponding to a single
+ * changed column.
+ * @param column_mask Mask to update.
+ * @param fieldno     Updated fieldno (index base must be 0).
+ */
+static inline void
+column_mask32_set_fieldno(uint32_t *column_mask, uint32_t fieldno)
+{
+	if (fieldno >= 31)
+		*column_mask |= ((uint32_t) 1) << 31;
+	else
+		*column_mask |= ((uint32_t) 1) << fieldno;
+}
+
+/**
+ * Test a bit in the 32-bit bitmask corresponding to a column
+ * fieldno.
+ * @param column_mask Mask to test.
+ * @param fieldno Fieldno number to test (index base must be 0).
+ * @retval true If bit corresponding to a column fieldno.
+ * @retval false if bit is not set or fieldno > 64.
+ */
+static inline bool
+column_mask32_fieldno_is_set(uint32_t column_mask, uint32_t fieldno)
+{
+	uint32_t mask = (uint32_t) 1 << (fieldno < 31 ? fieldno : 31);
+	return (column_mask & mask) != 0;
+}
+
+/**
+ * Test if overflow flag set in 32-bit bitmask.
+ * @param column_mask Mask to test.
+ * @retval true If mask overflowed, false otherwise.
+ */
+static inline bool
+column_mask32_is_overflowed(uint32_t column_mask)
+{
+	return column_mask & ((uint32_t) 1 << 31);
+}
+
 #endif
diff --git a/test/unit/column_mask.c b/test/unit/column_mask.c
index 7859626f8..0d5c04fd4 100644
--- a/test/unit/column_mask.c
+++ b/test/unit/column_mask.c
@@ -236,13 +236,44 @@ basic_test()
 				    column_masks[i]);
 }
 
+static inline void
+helpers_test()
+{
+	uint64_t bitmask = 0;
+	column_mask_set_fieldno(&bitmask, 33);
+	is(column_mask_fieldno_is_set(bitmask, 33), true,
+	   "64 bitmask internal bit");
+	is(column_mask_is_overflowed(bitmask), false,
+	   "64 bitmask is not overflowed");
+
+	column_mask_set_fieldno(&bitmask, 74);
+	is(column_mask_fieldno_is_set(bitmask, 74), true,
+	   "64 bitmask external bit");
+	is(column_mask_is_overflowed(bitmask), true,
+	   "64 bitmask is overflowed");
+
+	uint32_t bitmask32 = 0;
+	column_mask32_set_fieldno(&bitmask32, 23);
+	is(column_mask32_fieldno_is_set(bitmask32, 23), true,
+	   "32 bitmask internal bit");
+	is(column_mask32_is_overflowed(bitmask32), false,
+	   "32 bitmask is not overflowed");
+
+	column_mask32_set_fieldno(&bitmask32, 54);
+	is(column_mask32_fieldno_is_set(bitmask32, 54), true,
+	   "32 bitmask external bit");
+	is(column_mask32_is_overflowed(bitmask32), true,
+	   "32 bitmask is overflowed");
+}
+
 int
 main()
 {
 	header();
-	plan(27);
+	plan(35);
 
 	basic_test();
+	helpers_test();
 
 	footer();
 	check_plan();
diff --git a/test/unit/column_mask.result b/test/unit/column_mask.result
index 9309e6cdc..91d1f1feb 100644
--- a/test/unit/column_mask.result
+++ b/test/unit/column_mask.result
@@ -1,5 +1,5 @@
 	*** main ***
-1..27
+1..35
 ok 1 - check result length
 ok 2 - tuple update is correct
 ok 3 - column_mask is correct
@@ -27,4 +27,12 @@ ok 24 - column_mask is correct
 ok 25 - check result length
 ok 26 - tuple update is correct
 ok 27 - column_mask is correct
+ok 28 - 64 bitmask internal bit
+ok 29 - 64 bitmask is not overflowed
+ok 30 - 64 bitmask external bit
+ok 31 - 64 bitmask is overflowed
+ok 32 - 32 bitmask internal bit
+ok 33 - 32 bitmask is not overflowed
+ok 34 - 32 bitmask external bit
+ok 35 - 32 bitmask is overflowed
 	*** main: done ***
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Vladislav Shpilevoy]

Hi! Thanks for the fixes!

Once you introduced the new helpers, please, use them.

I found raw column mask usage in sql_space_column_is_in_pk().
Also, the first two hunks from the next commit does not
belong to the bug, so please, move them here (I speak about
alter.cc changes).

[tarantool-patches] Re: [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Konstantin Osipov]

* Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/08 16:22]:
> Refactored column_mask.h definitions: introduced a new routine
> column_mask_is_overflowed, column_mask_is_set and macro
> COLUMN_MASK_BIT, COLUMN_MASK_SIZE.
> We need this helpers in further refactoring.
> 
> Needed for #3571
> ---
>  src/box/column_mask.h | 39 +++++++++++++++++++++++++++++++++------
>  1 file changed, 33 insertions(+), 6 deletions(-)
> 
> diff --git a/src/box/column_mask.h b/src/box/column_mask.h
> index d71911d46..6e9c0f81a 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))

Please use CHAR_BIT constant instead of 8.

The patch otherwise looks good to me.

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

[tarantool-patches] Re: [PATCH v1 1/4] box: introduce new helpers in column_mask.h

[Konstantin Osipov]

* Konstantin Osipov <kostja@tarantool.org> [19/02/22 21:02]:
> The patch otherwise looks good to me.

Checked Vlad's review, I agree with Vlad one should not introduce
helpers without starting to use them.

-- 
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov

[tarantool-patches] [PATCH v1 2/4] sql: use 64b bitmasks instead of 32b where possible

[Kirill Shcherbatov]

In some cases(like foreign keys) the SQL code is still used
32-bit bit mask, while 64-bit bit masks will perform better
column optimizations. There was refactored code to work with 64b
bitmasks where required.
The 32b bitmasks are still used to specify constant OP_Function
arguments because this change would require changing the P1 type
of the VDBE p1 argument, which is not desirable. Moreover, the
64 function's arguments is an explicit overkill.

Part of #3571
---
 src/box/alter.cc        | 10 ++-------
 src/box/sql/delete.c    |  8 +++----
 src/box/sql/resolve.c   | 19 ++++++-----------
 src/box/sql/sqliteInt.h | 46 +++++++++++++++++++++++------------------
 src/box/sql/trigger.c   | 14 ++++++-------
 src/box/sql/update.c    | 21 ++++++++-----------
 6 files changed, 53 insertions(+), 65 deletions(-)

diff --git a/src/box/alter.cc b/src/box/alter.cc
index 9656a4189..cdc7aa0d7 100644
--- a/src/box/alter.cc
+++ b/src/box/alter.cc
@@ -29,6 +29,7 @@
  * SUCH DAMAGE.
  */
 #include "alter.h"
+#include "column_mask.h"
 #include "schema.h"
 #include "user.h"
 #include "space.h"
@@ -3732,13 +3733,6 @@ fkey_grab_by_name(struct rlist *list, const char *fkey_name)
 	return NULL;
 }
 
-/**
- * FIXME: as SQLite legacy temporary we use such mask throught
- * SQL code. It should be replaced later with regular
- * mask from column_mask.h
- */
-#define FKEY_MASK(x) (((x)>31) ? 0xffffffff : ((uint64_t)1<<(x)))
-
 /**
  * Set bits of @mask which correspond to fields involved in
  * given foreign key constraint.
@@ -3752,7 +3746,7 @@ static inline void
 fkey_set_mask(const struct fkey *fk, uint64_t *mask, int type)
 {
 	for (uint32_t i = 0; i < fk->def->field_count; ++i)
-		*mask |= FKEY_MASK(fk->def->links[i].fields[type]);
+		column_mask_set_fieldno(mask, fk->def->links[i].fields[type]);
 }
 
 /**
diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
index f9c42fdec..5e134ab0c 100644
--- a/src/box/sql/delete.c
+++ b/src/box/sql/delete.c
@@ -468,7 +468,7 @@ sql_generate_row_delete(struct Parse *parse, struct Table *table,
 	    (fkey_is_required(table->def->id, NULL) || trigger_list != NULL)) {
 		/* Mask of OLD.* columns in use */
 		/* TODO: Could use temporary registers here. */
-		uint32_t mask =
+		uint64_t mask =
 			sql_trigger_colmask(parse, trigger_list, 0, 0,
 					    TRIGGER_BEFORE | TRIGGER_AFTER,
 					    table, onconf);
@@ -484,10 +484,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)) {
+			if (i >= COLUMN_MASK_SIZE ||
+			    column_mask_fieldno_is_set(mask, i)) {
 				sqlite3ExprCodeGetColumnOfTable(v, table->def,
 								cursor, i,
 								first_old_reg +
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index 6462467bc..1f6ba0418 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -341,20 +341,13 @@ lookupName(Parse * pParse,	/* The parsing context */
 					if (iCol < 0) {
 						pExpr->affinity =
 							AFFINITY_INTEGER;
-					} else if (pExpr->iTable == 0) {
-						testcase(iCol == 31);
-						testcase(iCol == 32);
-						pParse->oldmask |=
-						    (iCol >=
-						     32 ? 0xffffffff
-						     : (((u32) 1) << iCol));
 					} else {
-						testcase(iCol == 31);
-						testcase(iCol == 32);
-						pParse->newmask |=
-						    (iCol >=
-						     32 ? 0xffffffff
-						     : (((u32) 1) << iCol));
+						uint64_t *mask =
+							pExpr->iTable == 0 ?
+							&pParse->oldmask :
+							&pParse->newmask;
+						column_mask_set_fieldno(mask,
+									iCol);
 					}
 					pExpr->iColumn = (i16) iCol;
 					pExpr->space_def = pTab->def;
diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h
index ee24e0337..4280c1938 100644
--- a/src/box/sql/sqliteInt.h
+++ b/src/box/sql/sqliteInt.h
@@ -67,6 +67,7 @@
 
 #include <stdbool.h>
 
+#include "box/column_mask.h"
 #include "box/field_def.h"
 #include "box/sql.h"
 #include "box/txn.h"
@@ -2630,22 +2631,24 @@ struct SelectDest {
 #endif
 
 /*
- * At least one instance of the following structure is created for each
- * trigger that may be fired while parsing an INSERT, UPDATE or DELETE
- * statement. All such objects are stored in the linked list headed at
- * Parse.pTriggerPrg and deleted once statement compilation has been
- * completed.
- *
- * A Vdbe sub-program that implements the body and WHEN clause of trigger
- * TriggerPrg.pTrigger, assuming a default ON CONFLICT clause of
- * TriggerPrg.orconf, is stored in the TriggerPrg.pProgram variable.
- * The Parse.pTriggerPrg list never contains two entries with the same
- * values for both pTrigger and orconf.
- *
- * The TriggerPrg.aColmask[0] variable is set to a mask of old.* columns
- * accessed (or set to 0 for triggers fired as a result of INSERT
- * statements). Similarly, the TriggerPrg.aColmask[1] variable is set to
- * a mask of new.* columns used by the program.
+ * At least one instance of the following structure is created for
+ * each trigger that may be fired while parsing an INSERT, UPDATE
+ * or DELETE statement. All such objects are stored in the linked
+ * list headed at Parse.pTriggerPrg and deleted once statement
+ * compilation has been completed.
+ *
+ * A Vdbe sub-program that implements the body and WHEN clause of
+ * trigger TriggerPrg.pTrigger, assuming a default ON CONFLICT
+ * clause of TriggerPrg.orconf, is stored in the
+ * TriggerPrg.pProgram variable. The Parse.pTriggerPrg list never
+ * contains two entries with the same values for both pTrigger
+ * and orconf.
+ *
+ * The TriggerPrg.column_mask[0] variable is set to a mask of
+ * old.* columns accessed (or set to 0 for triggers fired as a
+ * result of INSERT statements). Similarly, the
+ * TriggerPrg.column_mask[1] variable is set to a mask of new.*
+ * columns used by the program.
  */
 struct TriggerPrg {
 	/** Trigger this program was coded from. */
@@ -2653,7 +2656,8 @@ struct TriggerPrg {
 	TriggerPrg *pNext;	/* Next entry in Parse.pTriggerPrg list */
 	SubProgram *pProgram;	/* Program implementing pTrigger/orconf */
 	int orconf;		/* Default ON CONFLICT policy */
-	u32 aColmask[2];	/* Masks of old.*, new.* columns accessed */
+	/* Masks of old.*, new.* columns accessed. */
+	uint64_t column_mask[2];
 };
 
 enum ast_type {
@@ -2735,8 +2739,10 @@ struct Parse {
 	Parse *pToplevel;	/* Parse structure for main program (or NULL) */
 	Table *pTriggerTab;	/* Table triggers are being coded for */
 	u32 nQueryLoop;		/* Est number of iterations of a query (10*log2(N)) */
-	u32 oldmask;		/* Mask of old.* columns referenced */
-	u32 newmask;		/* Mask of new.* columns referenced */
+	/* Mask of old.* columns referenced. */
+	uint64_t oldmask;
+	/* Mask of new.* columns referenced. */
+	uint64_t newmask;
 	u8 eTriggerOp;		/* TK_UPDATE, TK_INSERT or TK_DELETE */
 	u8 eOrconf;		/* Default ON CONFLICT policy for trigger steps */
 	/** Region to make SQL temp allocations. */
@@ -4124,7 +4130,7 @@ TriggerStep *sqlite3TriggerDeleteStep(sqlite3 *, Token *, Expr *);
  *
  * @retval mask value.
  */
-u32
+uint64_t
 sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 		    ExprList *changes_list, int new, int tr_tm,
 		    Table *table, int orconf);
diff --git a/src/box/sql/trigger.c b/src/box/sql/trigger.c
index 7d5dc9e23..039350550 100644
--- a/src/box/sql/trigger.c
+++ b/src/box/sql/trigger.c
@@ -786,8 +786,8 @@ sql_row_trigger_program(struct Parse *parser, struct sql_trigger *trigger,
 	sqlite3VdbeLinkSubProgram(pTop->pVdbe, pProgram);
 	pPrg->trigger = trigger;
 	pPrg->orconf = orconf;
-	pPrg->aColmask[0] = 0xffffffff;
-	pPrg->aColmask[1] = 0xffffffff;
+	pPrg->column_mask[0] = COLUMN_MASK_FULL;
+	pPrg->column_mask[1] = COLUMN_MASK_FULL;
 
 	/*
 	 * Allocate and populate a new Parse context to use for
@@ -859,8 +859,8 @@ sql_row_trigger_program(struct Parse *parser, struct sql_trigger *trigger,
 		pProgram->nMem = pSubParse->nMem;
 		pProgram->nCsr = pSubParse->nTab;
 		pProgram->token = (void *)trigger;
-		pPrg->aColmask[0] = pSubParse->oldmask;
-		pPrg->aColmask[1] = pSubParse->newmask;
+		pPrg->column_mask[0] = pSubParse->oldmask;
+		pPrg->column_mask[1] = pSubParse->newmask;
 		sqlite3VdbeDelete(v);
 	}
 
@@ -978,13 +978,13 @@ vdbe_code_row_trigger(struct Parse *parser, struct sql_trigger *trigger,
 	}
 }
 
-u32
+uint64_t
 sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 		    ExprList *changes_list, int new, int tr_tm,
 		    Table *table, int orconf)
 {
 	const int op = changes_list != NULL ? TK_UPDATE : TK_DELETE;
-	u32 mask = 0;
+	uint64_t mask = 0;
 
 	assert(new == 1 || new == 0);
 	for (struct sql_trigger *p = trigger; p != NULL; p = p->next) {
@@ -993,7 +993,7 @@ sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 			TriggerPrg *prg =
 				sql_row_trigger(parser, p, table, orconf);
 			if (prg != NULL)
-				mask |= prg->aColmask[new];
+				mask |= prg->column_mask[new];
 		}
 	}
 
diff --git a/src/box/sql/update.c b/src/box/sql/update.c
index dbef22fd8..50b81c188 100644
--- a/src/box/sql/update.c
+++ b/src/box/sql/update.c
@@ -101,7 +101,6 @@ sqlite3Update(Parse * pParse,		/* The parser context */
 	/* List of triggers on pTab, if required. */
 	struct sql_trigger *trigger;
 	int tmask;		/* Mask of TRIGGER_BEFORE|TRIGGER_AFTER */
-	int newmask;		/* Mask of NEW.* columns accessed by BEFORE triggers */
 	int iEph = 0;		/* Ephemeral table holding all primary key values */
 	int nKey = 0;		/* Number of elements in regKey */
 	int aiCurOnePass[2];	/* The write cursors opened by WHERE_ONEPASS */
@@ -335,15 +334,14 @@ 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 ? 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) ||
-				sql_space_column_is_in_pk(pTab->space, i)) {
-				testcase(oldmask != 0xffffffff && i == 31);
+			if (i >= COLUMN_MASK_SIZE ||
+			    column_mask_fieldno_is_set(oldmask, i) ||
+			    sql_space_column_is_in_pk(pTab->space, i)) {
 				sqlite3ExprCodeGetColumnOfTable(v, def,
 								pk_cursor, i,
 								regOld + i);
@@ -367,22 +365,21 @@ sqlite3Update(Parse * pParse,		/* The parser context */
 	 * may have modified them). So not loading those that are not going to
 	 * be used eliminates some redundant opcodes.
 	 */
-	newmask = sql_trigger_colmask(pParse, trigger, pChanges, 1,
-				      TRIGGER_BEFORE, pTab, on_error);
+	uint64_t newmask = sql_trigger_colmask(pParse, trigger, pChanges, 1,
+					       TRIGGER_BEFORE, pTab, on_error);
 	for (i = 0; i < (int)def->field_count; i++) {
 		j = aXRef[i];
 		if (j >= 0) {
 			sqlite3ExprCode(pParse, pChanges->a[j].pExpr,
 					regNew + i);
-		} else if (0 == (tmask & TRIGGER_BEFORE) || i > 31
-			   || (newmask & MASKBIT32(i))) {
+		} else if ((tmask & TRIGGER_BEFORE) == 0 ||
+			   i >= COLUMN_MASK_SIZE ||
+			   column_mask_fieldno_is_set(newmask, i) != 0) {
 			/* 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
 			 * a new.* reference in a trigger program.
 			 */
-			testcase(i == 31);
-			testcase(i == 32);
 			sqlite3ExprCodeGetColumnToReg(pParse, def, i,
 						      pk_cursor, regNew + i);
 		} else {
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 2/4] sql: use 64b bitmasks instead of 32b where possible

[Vladislav Shpilevoy]

Thanks for the patch! See 1 comment below.

On 08/02/2019 13:52, Kirill Shcherbatov wrote:
> In some cases(like foreign keys) the SQL code is still used
> 32-bit bit mask, while 64-bit bit masks will perform better
> column optimizations. There was refactored code to work with 64b
> bitmasks where required.
> The 32b bitmasks are still used to specify constant OP_Function
> arguments because this change would require changing the P1 type
> of the VDBE p1 argument, which is not desirable. Moreover, the
> 64 function's arguments is an explicit overkill.
> 
> Part of #3571
> ---
>   src/box/alter.cc        | 10 ++-------
>   src/box/sql/delete.c    |  8 +++----
>   src/box/sql/resolve.c   | 19 ++++++-----------
>   src/box/sql/sqliteInt.h | 46 +++++++++++++++++++++++------------------
>   src/box/sql/trigger.c   | 14 ++++++-------
>   src/box/sql/update.c    | 21 ++++++++-----------
>   6 files changed, 53 insertions(+), 65 deletions(-)
> 
> diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
> index f9c42fdec..5e134ab0c 100644
> --- a/src/box/sql/delete.c
> +++ b/src/box/sql/delete.c
> @@ -484,10 +484,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)) {
> +			if (i >= COLUMN_MASK_SIZE ||
> +			    column_mask_fieldno_is_set(mask, i)) {

Now I see, why did you define COLUMN_MASK_SIZE. And still the problem
is in the way how you understand the last bit.
column_mask_fieldno_is_set() should check, if i >= COLUMN_MASK_SIZE, and in such
a case 'and' it with the last bit. In your code the mask is not 'smart' -
you consider fields >= 63 as set even if the last bit of the mask is 0. It is
worthy of note that literally every place of column_mask_fieldno_is_set() usage
also checks for i >= COLUMN_MASK_SIZE.

>   				sqlite3ExprCodeGetColumnOfTable(v, table->def,
>   								cursor, i,
>   								first_old_reg +

[tarantool-patches] Re: [PATCH v1 2/4] sql: use 64b bitmasks instead of 32b where possible

[Kirill Shcherbatov]

> Now I see, why did you define COLUMN_MASK_SIZE. And still the problem
> is in the way how you understand the last bit.
> column_mask_fieldno_is_set() should check, if i >= COLUMN_MASK_SIZE, and in such
> a case 'and' it with the last bit. In your code the mask is not 'smart' -
> you consider fields >= 63 as set even if the last bit of the mask is 0. It is
> worthy of note that literally every place of column_mask_fieldno_is_set() usage
> also checks for i >= COLUMN_MASK_SIZE.
You are right, we may omit such check for smart mask

So, this is the central patch of this patchset extending SQLite functionality.
All other are just boring refactoring. Maybe it worth stop just here.

====================================================

In some cases(like foreign keys) the SQL code is still used
32-bit bit mask, while 64-bit bit masks will perform better
column optimizations. There was refactored code to work with 64b
bitmasks where required.
The 32b bitmasks are still used to specify constant OP_Function
arguments because this change would require changing the P1 type
of the VDBE p1 argument, which is not desirable. Moreover, the
64 function's arguments is an explicit overkill.

Part of #3571
---
 src/box/alter.cc      | 10 ++--------
 src/box/sql/delete.c  |  7 ++-----
 src/box/sql/resolve.c | 19 ++++++------------
 src/box/sql/sqlInt.h  | 46 ++++++++++++++++++++++++-------------------
 src/box/sql/trigger.c | 14 ++++++-------
 src/box/sql/update.c  | 24 +++++++++-------------
 6 files changed, 52 insertions(+), 68 deletions(-)

diff --git a/src/box/alter.cc b/src/box/alter.cc
index bea15c8a2..f5f4c2112 100644
--- a/src/box/alter.cc
+++ b/src/box/alter.cc
@@ -29,6 +29,7 @@
  * SUCH DAMAGE.
  */
 #include "alter.h"
+#include "column_mask.h"
 #include "schema.h"
 #include "user.h"
 #include "space.h"
@@ -3729,13 +3730,6 @@ fkey_grab_by_name(struct rlist *list, const char *fkey_name)
 	return NULL;
 }
 
-/**
- * FIXME: as sql legacy temporary we use such mask throught
- * SQL code. It should be replaced later with regular
- * mask from column_mask.h
- */
-#define FKEY_MASK(x) (((x)>31) ? 0xffffffff : ((uint64_t)1<<(x)))
-
 /**
  * Set bits of @mask which correspond to fields involved in
  * given foreign key constraint.
@@ -3749,7 +3743,7 @@ static inline void
 fkey_set_mask(const struct fkey *fk, uint64_t *mask, int type)
 {
 	for (uint32_t i = 0; i < fk->def->field_count; ++i)
-		*mask |= FKEY_MASK(fk->def->links[i].fields[type]);
+		column_mask_set_fieldno(mask, fk->def->links[i].fields[type]);
 }
 
 /**
diff --git a/src/box/sql/delete.c b/src/box/sql/delete.c
index 95512ea9e..bd6228c0d 100644
--- a/src/box/sql/delete.c
+++ b/src/box/sql/delete.c
@@ -459,7 +459,7 @@ sql_generate_row_delete(struct Parse *parse, struct space *space,
 	   (fkey_is_required(space, NULL) || trigger_list != NULL)) {
 		/* Mask of OLD.* columns in use */
 		/* TODO: Could use temporary registers here. */
-		uint32_t mask =
+		uint64_t mask =
 			sql_trigger_colmask(parse, trigger_list, 0, 0,
 					    TRIGGER_BEFORE | TRIGGER_AFTER,
 					    space, onconf);
@@ -474,10 +474,7 @@ sql_generate_row_delete(struct Parse *parse, struct space *space,
 		 */
 		sqlVdbeAddOp2(v, OP_Copy, reg_pk, first_old_reg);
 		for (int i = 0; i < (int)space->def->field_count; i++) {
-			testcase(mask != 0xffffffff && iCol == 31);
-			testcase(mask != 0xffffffff && iCol == 32);
-			if (mask == 0xffffffff
-			    || (i <= 31 && (mask & MASKBIT32(i)) != 0)) {
+			if (column_mask_fieldno_is_set(mask, i)) {
 				sqlExprCodeGetColumnOfTable(v, space->def,
 								cursor, i,
 								first_old_reg +
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index bc208cc9d..a9a167477 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -340,20 +340,13 @@ lookupName(Parse * pParse,	/* The parsing context */
 					if (iCol < 0) {
 						pExpr->type =
 							FIELD_TYPE_INTEGER;
-					} else if (pExpr->iTable == 0) {
-						testcase(iCol == 31);
-						testcase(iCol == 32);
-						pParse->oldmask |=
-						    (iCol >=
-						     32 ? 0xffffffff
-						     : (((u32) 1) << iCol));
 					} else {
-						testcase(iCol == 31);
-						testcase(iCol == 32);
-						pParse->newmask |=
-						    (iCol >=
-						     32 ? 0xffffffff
-						     : (((u32) 1) << iCol));
+						uint64_t *mask =
+							pExpr->iTable == 0 ?
+							&pParse->oldmask :
+							&pParse->newmask;
+						column_mask_set_fieldno(mask,
+									iCol);
 					}
 					pExpr->iColumn = (i16) iCol;
 					pExpr->space_def = space_def;
diff --git a/src/box/sql/sqlInt.h b/src/box/sql/sqlInt.h
index 2830ab639..5be695e51 100644
--- a/src/box/sql/sqlInt.h
+++ b/src/box/sql/sqlInt.h
@@ -67,6 +67,7 @@
 
 #include <stdbool.h>
 
+#include "box/column_mask.h"
 #include "box/field_def.h"
 #include "box/sql.h"
 #include "box/txn.h"
@@ -2580,22 +2581,24 @@ struct SelectDest {
 #endif
 
 /*
- * At least one instance of the following structure is created for each
- * trigger that may be fired while parsing an INSERT, UPDATE or DELETE
- * statement. All such objects are stored in the linked list headed at
- * Parse.pTriggerPrg and deleted once statement compilation has been
- * completed.
- *
- * A Vdbe sub-program that implements the body and WHEN clause of trigger
- * TriggerPrg.pTrigger, assuming a default ON CONFLICT clause of
- * TriggerPrg.orconf, is stored in the TriggerPrg.pProgram variable.
- * The Parse.pTriggerPrg list never contains two entries with the same
- * values for both pTrigger and orconf.
- *
- * The TriggerPrg.aColmask[0] variable is set to a mask of old.* columns
- * accessed (or set to 0 for triggers fired as a result of INSERT
- * statements). Similarly, the TriggerPrg.aColmask[1] variable is set to
- * a mask of new.* columns used by the program.
+ * At least one instance of the following structure is created for
+ * each trigger that may be fired while parsing an INSERT, UPDATE
+ * or DELETE statement. All such objects are stored in the linked
+ * list headed at Parse.pTriggerPrg and deleted once statement
+ * compilation has been completed.
+ *
+ * A Vdbe sub-program that implements the body and WHEN clause of
+ * trigger TriggerPrg.pTrigger, assuming a default ON CONFLICT
+ * clause of TriggerPrg.orconf, is stored in the
+ * TriggerPrg.pProgram variable. The Parse.pTriggerPrg list never
+ * contains two entries with the same values for both pTrigger
+ * and orconf.
+ *
+ * The TriggerPrg.column_mask[0] variable is set to a mask of
+ * old.* columns accessed (or set to 0 for triggers fired as a
+ * result of INSERT statements). Similarly, the
+ * TriggerPrg.column_mask[1] variable is set to a mask of new.*
+ * columns used by the program.
  */
 struct TriggerPrg {
 	/** Trigger this program was coded from. */
@@ -2603,7 +2606,8 @@ struct TriggerPrg {
 	TriggerPrg *pNext;	/* Next entry in Parse.pTriggerPrg list */
 	SubProgram *pProgram;	/* Program implementing pTrigger/orconf */
 	int orconf;		/* Default ON CONFLICT policy */
-	u32 aColmask[2];	/* Masks of old.*, new.* columns accessed */
+	/* Masks of old.*, new.* columns accessed. */
+	uint64_t column_mask[2];
 };
 
 enum ast_type {
@@ -2684,8 +2688,10 @@ struct Parse {
 	int nSelectIndent;	/* How far to indent SELECTTRACE() output */
 	Parse *pToplevel;	/* Parse structure for main program (or NULL) */
 	u32 nQueryLoop;		/* Est number of iterations of a query (10*log2(N)) */
-	u32 oldmask;		/* Mask of old.* columns referenced */
-	u32 newmask;		/* Mask of new.* columns referenced */
+	/* Mask of old.* columns referenced. */
+	uint64_t oldmask;
+	/* Mask of new.* columns referenced. */
+	uint64_t newmask;
 	u8 eTriggerOp;		/* TK_UPDATE, TK_INSERT or TK_DELETE */
 	u8 eOrconf;		/* Default ON CONFLICT policy for trigger steps */
 	/** Region to make SQL temp allocations. */
@@ -4083,7 +4089,7 @@ TriggerStep *sqlTriggerDeleteStep(sql *, Token *, Expr *);
  *
  * @retval mask value.
  */
-u32
+uint64_t
 sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 		    ExprList *changes_list, int new, int tr_tm,
 		    struct space *space, int orconf);
diff --git a/src/box/sql/trigger.c b/src/box/sql/trigger.c
index 9901a5606..039a33198 100644
--- a/src/box/sql/trigger.c
+++ b/src/box/sql/trigger.c
@@ -786,8 +786,8 @@ sql_row_trigger_program(struct Parse *parser, struct sql_trigger *trigger,
 	sqlVdbeLinkSubProgram(pTop->pVdbe, pProgram);
 	pPrg->trigger = trigger;
 	pPrg->orconf = orconf;
-	pPrg->aColmask[0] = 0xffffffff;
-	pPrg->aColmask[1] = 0xffffffff;
+	pPrg->column_mask[0] = COLUMN_MASK_FULL;
+	pPrg->column_mask[1] = COLUMN_MASK_FULL;
 
 	/*
 	 * Allocate and populate a new Parse context to use for
@@ -859,8 +859,8 @@ sql_row_trigger_program(struct Parse *parser, struct sql_trigger *trigger,
 		pProgram->nMem = pSubParse->nMem;
 		pProgram->nCsr = pSubParse->nTab;
 		pProgram->token = (void *)trigger;
-		pPrg->aColmask[0] = pSubParse->oldmask;
-		pPrg->aColmask[1] = pSubParse->newmask;
+		pPrg->column_mask[0] = pSubParse->oldmask;
+		pPrg->column_mask[1] = pSubParse->newmask;
 		sqlVdbeDelete(v);
 	}
 
@@ -977,13 +977,13 @@ vdbe_code_row_trigger(struct Parse *parser, struct sql_trigger *trigger,
 	}
 }
 
-u32
+uint64_t
 sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 		    ExprList *changes_list, int new, int tr_tm,
 		    struct space *space, int orconf)
 {
 	const int op = changes_list != NULL ? TK_UPDATE : TK_DELETE;
-	u32 mask = 0;
+	uint64_t mask = 0;
 
 	assert(new == 1 || new == 0);
 	for (struct sql_trigger *p = trigger; p != NULL; p = p->next) {
@@ -992,7 +992,7 @@ sql_trigger_colmask(Parse *parser, struct sql_trigger *trigger,
 			TriggerPrg *prg =
 				sql_row_trigger(parser, p, space, orconf);
 			if (prg != NULL)
-				mask |= prg->aColmask[new];
+				mask |= prg->column_mask[new];
 		}
 	}
 
diff --git a/src/box/sql/update.c b/src/box/sql/update.c
index cb303c107..f4351aee6 100644
--- a/src/box/sql/update.c
+++ b/src/box/sql/update.c
@@ -100,7 +100,6 @@ sqlUpdate(Parse * pParse,		/* The parser context */
 	/* List of triggers on pTab, if required. */
 	struct sql_trigger *trigger;
 	int tmask;		/* Mask of TRIGGER_BEFORE|TRIGGER_AFTER */
-	int newmask;		/* Mask of NEW.* columns accessed by BEFORE triggers */
 	int iEph = 0;		/* Ephemeral table holding all primary key values */
 	int nKey = 0;		/* Number of elements in regKey */
 	int aiCurOnePass[2];	/* The write cursors opened by WHERE_ONEPASS */
@@ -332,18 +331,15 @@ sqlUpdate(Parse * pParse,		/* The parser context */
 	 */
 	if (is_pk_modified || hasFK != 0 || trigger != NULL) {
 		assert(space != NULL);
-		u32 oldmask = hasFK ? space->fkey_mask : 0;
+		uint64_t oldmask = hasFK ? space->fkey_mask : 0;
 		oldmask |= sql_trigger_colmask(pParse, trigger, pChanges, 0,
 					       TRIGGER_BEFORE | TRIGGER_AFTER,
 					       space, on_error);
 		for (i = 0; i < (int)def->field_count; i++) {
-			if (oldmask == 0xffffffff
-			    || (i < 32 && (oldmask & MASKBIT32(i)) != 0) ||
-				sql_space_column_is_in_pk(space, i)) {
-				testcase(oldmask != 0xffffffff && i == 31);
-				sqlExprCodeGetColumnOfTable(v, def,
-								pk_cursor, i,
-								regOld + i);
+			if (column_mask_fieldno_is_set(oldmask, i) ||
+			    sql_space_column_is_in_pk(space, i)) {
+				sqlExprCodeGetColumnOfTable(v, def, pk_cursor,
+							    i, regOld + i);
 			} else {
 				sqlVdbeAddOp2(v, OP_Null, 0, regOld + i);
 			}
@@ -364,22 +360,20 @@ sqlUpdate(Parse * pParse,		/* The parser context */
 	 * may have modified them). So not loading those that are not going to
 	 * be used eliminates some redundant opcodes.
 	 */
-	newmask = sql_trigger_colmask(pParse, trigger, pChanges, 1,
-				      TRIGGER_BEFORE, space, on_error);
+	uint64_t newmask = sql_trigger_colmask(pParse, trigger, pChanges, 1,
+					       TRIGGER_BEFORE, space, on_error);
 	for (i = 0; i < (int)def->field_count; i++) {
 		j = aXRef[i];
 		if (j >= 0) {
 			sqlExprCode(pParse, pChanges->a[j].pExpr,
 					regNew + i);
-		} else if (0 == (tmask & TRIGGER_BEFORE) || i > 31
-			   || (newmask & MASKBIT32(i))) {
+		} else if ((tmask & TRIGGER_BEFORE) == 0 ||
+			   column_mask_fieldno_is_set(newmask, i) != 0) {
 			/* 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
 			 * a new.* reference in a trigger program.
 			 */
-			testcase(i == 31);
-			testcase(i == 32);
 			sqlExprCodeGetColumnToReg(pParse, def, i,
 						      pk_cursor, regNew + i);
 		} else {
-- 
2.20.1

[tarantool-patches] [PATCH v1 3/4] sql: got rid of redundant MASKBIT32 definition

[Kirill Shcherbatov]

MASK BIT 32 macro is now redundant, so we got rid of it.
Also refactored related code to use core bitmasks helpers

Part of #3571
---
 src/box/sql/expr.c      | 22 ++++++++++++----------
 src/box/sql/sqliteInt.h |  1 -
 src/box/sql/vdbeaux.c   |  7 +++----
 3 files changed, 15 insertions(+), 15 deletions(-)

diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index d83be5101..cf82bd366 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -3963,7 +3963,11 @@ 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 */
+			/*
+			 * Mask of function arguments that are
+			 * constant.
+			 */
+			uint32_t const_mask = 0;
 			int i;	/* Loop counter */
 			sqlite3 *db = pParse->db;	/* The database connection */
 			struct coll *coll = NULL;
@@ -4038,11 +4042,10 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
 			}
 
 			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((uint64_t *)
+								&const_mask, i);
 				}
 				if ((pDef->funcFlags & SQLITE_FUNC_NEEDCOLL) !=
 				    0 && coll == NULL) {
@@ -4054,7 +4057,7 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
 				}
 			}
 			if (pFarg) {
-				if (constMask) {
+				if (const_mask != 0) {
 					r1 = pParse->nMem + 1;
 					pParse->nMem += nFarg;
 				} else {
@@ -4102,12 +4105,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, const_mask, r1,
 					  target, (char *)pDef, P4_FUNCDEF);
 			sqlite3VdbeChangeP5(v, (u8) nFarg);
-			if (nFarg && constMask == 0) {
+			if (nFarg && const_mask == 0)
 				sqlite3ReleaseTempRange(pParse, r1, nFarg);
-			}
 			return target;
 		}
 	case TK_EXISTS:
diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h
index 4280c1938..913d3f9ac 100644
--- a/src/box/sql/sqliteInt.h
+++ b/src/box/sql/sqliteInt.h
@@ -2307,7 +2307,6 @@ typedef u64 Bitmask;
  * A bit in a Bitmask
  */
 #define MASKBIT(n)   (((Bitmask)1)<<(n))
-#define MASKBIT32(n) (((unsigned int)1)<<(n))
 #define ALLBITS      ((Bitmask)-1)
 
 /*
diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c
index 975f114df..af57c244b 100644
--- a/src/box/sql/vdbeaux.c
+++ b/src/box/sql/vdbeaux.c
@@ -2698,10 +2698,9 @@ sqlite3VdbeDeleteAuxData(sqlite3 * db, AuxData ** pp, int iOp, int mask)
 {
 	while (*pp) {
 		AuxData *pAux = *pp;
-		if ((iOp < 0)
-		    || (pAux->iOp == iOp
-			&& (pAux->iArg > 31 || !(mask & MASKBIT32(pAux->iArg))))
-		    ) {
+		if (iOp < 0 || (pAux->iOp == iOp &&
+		    (pAux->iArg >= 32 ||
+		    (mask & COLUMN_MASK_BIT(pAux->iArg)) == 0))) {
 			testcase(pAux->iArg == 31);
 			if (pAux->xDelete) {
 				pAux->xDelete(pAux->pAux);
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 3/4] sql: got rid of redundant MASKBIT32 definition

[Vladislav Shpilevoy]

Thanks for the patch! See 4 comments below.

1. We do not use the past in commit titles. Please, use 'get',
not 'got'. In the next commit too.

On 08/02/2019 13:52, Kirill Shcherbatov wrote:
> MASK BIT 32 macro is now redundant, so we got rid of it.
> Also refactored related code to use core bitmasks helpers
> 
> Part of #3571
> ---
>   src/box/sql/expr.c      | 22 ++++++++++++----------
>   src/box/sql/sqliteInt.h |  1 -
>   src/box/sql/vdbeaux.c   |  7 +++----
>   3 files changed, 15 insertions(+), 15 deletions(-)
> 
> diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
> index d83be5101..cf82bd366 100644
> --- a/src/box/sql/expr.c
> +++ b/src/box/sql/expr.c
> @@ -3963,7 +3963,11 @@ 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 */
> +			/*
> +			 * Mask of function arguments that are
> +			 * constant.
> +			 */
> +			uint32_t const_mask = 0;


2. In the previous commit you said, that 32bit mask is already
replaced with 64bit one where possible. But why was not it
possible to replace this one?

>   			int i;	/* Loop counter */
>   			sqlite3 *db = pParse->db;	/* The database connection */
>   			struct coll *coll = NULL;
> @@ -4038,11 +4042,10 @@ sqlite3ExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
>   			}
>   
>   			for (i = 0; i < nFarg; i++) {
> -				if (i < 32
> -				    && sqlite3ExprIsConstant(pFarg->a[i].
> -							     pExpr)) {
> -					testcase(i == 31);
> -					constMask |= MASKBIT32(i);
> +				if (i < 32 &&

3. Why 32? The column mask is smart, it has no size restrictions.

> +				    sqlite3ExprIsConstant(pFarg->a[i].pExpr)) {
> +					column_mask_set_fieldno((uint64_t *)
> +								&const_mask, i);

4. column_mask_set_fieldo does *mask = ... . It means, that it rewrites 8 bytes
from the specified address. But you passed a value of only 4 bytes, so the next
4 bytes of foreign memory are polluted.

>   				}
>   				if ((pDef->funcFlags & SQLITE_FUNC_NEEDCOLL) !=
>   				    0 && coll == NULL) {

[tarantool-patches] Re: [PATCH v1 3/4] sql: got rid of redundant MASKBIT32 definition

[Kirill Shcherbatov]

> Thanks for the patch! See 4 comments below.
> 
> 1. We do not use the past in commit titles. Please, use 'get',
> not 'got'. In the next commit too.
Ok, done.

> 2. In the previous commit you said, that 32bit mask is already
> replaced with 64bit one where possible. But why was not it
> possible to replace this one?
The answer is in previous commit description:
"
The 32b bitmasks are still used to specify constant OP_Function
arguments because this change would require changing the P1 type
of the VDBE p1 argument, which is not desirable. Moreover, the
64 function's arguments is an explicit overkill.
"

>>   			for (i = 0; i < nFarg; i++) {
>> -				if (i < 32
>> -				    && sqlite3ExprIsConstant(pFarg->a[i].
>> -							     pExpr)) {
>> -					testcase(i == 31);
>> -					constMask |= MASKBIT32(i);
>> +				if (i < 32 &&
> 
> 3. Why 32? The column mask is smart, it has no size restrictions.
All function arguments that are not able to fit in mask to be marked as constant,
assumed to by dynamic. There is nice commit before sqlVdbeDeleteAuxData
routine definition. i < 32 must be kept to avoid calculation sqlite3ExprIsConstant
where unnecessary.
In fact such 32bit column mask is not smart, but it is not matter. Smart mask
also works fine in this scenario.

> 
>> +				    sqlite3ExprIsConstant(pFarg->a[i].pExpr)) {
>> +					column_mask_set_fieldno((uint64_t *)
>> +								&const_mask, i);
> 
> 4. column_mask_set_fieldo does *mask = ... . It means, that it rewrites 8 bytes
> from the specified address. But you passed a value of only 4 bytes, so the next
> 4 bytes of foreign memory are polluted.
You are right. It is not problem anymore.

=============================================

MASK BIT 32 macro is now redundant, so we got rid of it.
Also refactored related code to use core bitmasks helpers

Part of #3571
---
 src/box/sql/expr.c    | 24 +++++++++++++-----------
 src/box/sql/sqlInt.h  |  1 -
 src/box/sql/vdbeaux.c |  8 +++-----
 3 files changed, 16 insertions(+), 17 deletions(-)

diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index 35145cef6..a72f986c6 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -3914,7 +3914,11 @@ sqlExprCodeTarget(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 */
+			/*
+			 * Mask of function arguments that are
+			 * constant.
+			 */
+			uint32_t const_mask = 0;
 			int i;	/* Loop counter */
 			sql *db = pParse->db;	/* The database connection */
 			struct coll *coll = NULL;
@@ -3988,11 +3992,10 @@ sqlExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
 			}
 
 			for (i = 0; i < nFarg; i++) {
-				if (i < 32
-				    && sqlExprIsConstant(pFarg->a[i].
-							     pExpr)) {
-					testcase(i == 31);
-					constMask |= MASKBIT32(i);
+				if (i < 32 &&
+				    sqlExprIsConstant(pFarg->a[i].pExpr)) {
+					column_mask32_set_fieldno(&const_mask,
+								  i);
 				}
 				if ((pDef->funcFlags & SQL_FUNC_NEEDCOLL) !=
 				    0 && coll == NULL) {
@@ -4004,7 +4007,7 @@ sqlExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
 				}
 			}
 			if (pFarg) {
-				if (constMask) {
+				if (const_mask != 0) {
 					r1 = pParse->nMem + 1;
 					pParse->nMem += nFarg;
 				} else {
@@ -4052,12 +4055,11 @@ sqlExprCodeTarget(Parse * pParse, Expr * pExpr, int target)
 				sqlVdbeAddOp4(v, OP_CollSeq, 0, 0, 0,
 						  (char *)coll, P4_COLLSEQ);
 			}
-			sqlVdbeAddOp4(v, OP_Function0, constMask, r1,
-					  target, (char *)pDef, P4_FUNCDEF);
+			sqlVdbeAddOp4(v, OP_Function0, const_mask, r1, target,
+				      (char *)pDef, P4_FUNCDEF);
 			sqlVdbeChangeP5(v, (u8) nFarg);
-			if (nFarg && constMask == 0) {
+			if (nFarg && const_mask == 0)
 				sqlReleaseTempRange(pParse, r1, nFarg);
-			}
 			return target;
 		}
 	case TK_EXISTS:
diff --git a/src/box/sql/sqlInt.h b/src/box/sql/sqlInt.h
index 5be695e51..a9b7dfa4e 100644
--- a/src/box/sql/sqlInt.h
+++ b/src/box/sql/sqlInt.h
@@ -2255,7 +2255,6 @@ typedef u64 Bitmask;
  * A bit in a Bitmask
  */
 #define MASKBIT(n)   (((Bitmask)1)<<(n))
-#define MASKBIT32(n) (((unsigned int)1)<<(n))
 #define ALLBITS      ((Bitmask)-1)
 
 /*
diff --git a/src/box/sql/vdbeaux.c b/src/box/sql/vdbeaux.c
index b831b52ad..fedbc0a15 100644
--- a/src/box/sql/vdbeaux.c
+++ b/src/box/sql/vdbeaux.c
@@ -2698,11 +2698,9 @@ 	(sql * db, AuxData ** pp, int iOp, int mask)
 {
 	while (*pp) {
 		AuxData *pAux = *pp;
-		if ((iOp < 0)
-		    || (pAux->iOp == iOp
-			&& (pAux->iArg > 31 || !(mask & MASKBIT32(pAux->iArg))))
-		    ) {
-			testcase(pAux->iArg == 31);
+		if (iOp < 0 || (pAux->iOp == iOp &&
+		    (pAux->iArg >= 32 ||
+		     !column_mask32_fieldno_is_set(mask, pAux->iArg)))) {
 			if (pAux->xDelete) {
 				pAux->xDelete(pAux->pAux);
 			}
-- 
2.20.1

[tarantool-patches] [PATCH v1 4/4] sql: got rid of redundant bitmask helpers

[Kirill Shcherbatov]

The original SQLite code allowed the program to be compiled using
32-bit masks to save disk space. Since we are not going to
compile Tarantool in such way, we will get rid of these macros by
replacing them(where possible) with helpers from column_mask.h

Closes #3571
---
 src/box/sql/expr.c      |  31 ++++++-----
 src/box/sql/resolve.c   |  12 +----
 src/box/sql/sqliteInt.h |  24 ++-------
 src/box/sql/where.c     | 110 ++++++++++++++++++----------------------
 src/box/sql/whereInt.h  |   3 +-
 5 files changed, 74 insertions(+), 106 deletions(-)

diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index cf82bd366..613c29bbb 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -2456,19 +2456,20 @@ sqlite3FindInIndex(Parse * pParse,	/* Parsing context */
 			     eType == 0; ++k) {
 				struct index *idx = space->index[k];
 				Bitmask colUsed; /* Columns of the index used */
-				Bitmask mCol;	/* Mask for the current column */
 				uint32_t part_count =
 					idx->def->key_def->part_count;
 				struct key_part *parts =
 					idx->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 bitmask 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 ||
@@ -2504,19 +2505,23 @@ 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_fieldno_is_set(colUsed,
+								       j))
+						break;
+					column_mask_set_fieldno(&colUsed, 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)) {
+				assert(i == nExpr ||
+				       colUsed != (COLUMN_MASK_BIT(nExpr) - 1));
+				if (colUsed == (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);
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index 1f6ba0418..809771be4 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -437,13 +437,8 @@ lookupName(Parse * pParse,	/* The parsing context */
 	 * 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->colUsed, pExpr->iColumn);
 	}
 
 	/* Clean up and return
@@ -485,10 +480,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->colUsed, iCol);
 		ExprSetProperty(p, EP_Resolved);
 	}
 	return p;
diff --git a/src/box/sql/sqliteInt.h b/src/box/sql/sqliteInt.h
index 913d3f9ac..19c9cb3c0 100644
--- a/src/box/sql/sqliteInt.h
+++ b/src/box/sql/sqliteInt.h
@@ -2286,28 +2286,10 @@ struct IdList {
 };
 
 /*
- * 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
+ * The bitmask datatype defined below is used for various
+ * optimizations.
  */
-#define MASKBIT(n)   (((Bitmask)1)<<(n))
-#define ALLBITS      ((Bitmask)-1)
+typedef uint64_t Bitmask;
 
 /*
  * The following structure describes the FROM clause of a SELECT statement.
diff --git a/src/box/sql/where.c b/src/box/sql/where.c
index 814bd3926..84470199d 100644
--- a/src/box/sql/where.c
+++ b/src/box/sql/where.c
@@ -220,7 +220,7 @@ sqlite3WhereGetMask(WhereMaskSet * pMaskSet, int iCursor)
 	assert(pMaskSet->n <= (int)sizeof(Bitmask) * 8);
 	for (i = 0; i < pMaskSet->n; i++) {
 		if (pMaskSet->ix[i] == iCursor) {
-			return MASKBIT(i);
+			return COLUMN_MASK_BIT(i);
 		}
 	}
 	return 0;
@@ -732,12 +732,10 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	int regRecord;		/* Register holding an index record */
 	int n;			/* Column counter */
 	int i;			/* Loop counter */
-	int mxBitCol;		/* Maximum column in pSrc->colUsed */
 	struct coll *pColl;		/* Collating sequence to on a column */
 	WhereLoop *pLoop;	/* The Loop object */
 	char *zNotUsed;		/* Extra space on the end of pIdx */
 	Bitmask idxCols;	/* Bitmap of columns used for indexing */
-	Bitmask extraCols;	/* Bitmap of additional columns */
 	u8 sentWarning = 0;	/* True if a warnning has been issued */
 	int iContinue = 0;	/* Jump here to skip excluded rows */
 	struct SrcList_item *pTabItem;	/* FROM clause term being indexed */
@@ -763,10 +761,8 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS);
-			testcase(iCol == BMS - 1);
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
 			if (!sentWarning) {
 				sqlite3_log(SQLITE_WARNING_AUTOINDEX,
 					    "automatic index on %s(%s)",
@@ -774,13 +770,13 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 					    pTable->aCol[iCol].zName);
 				sentWarning = 1;
 			}
-			if ((idxCols & cMask) == 0) {
+			if ((idxCols & column_mask) == 0) {
 				if (whereLoopResize
 				    (pParse->db, pLoop, nKeyCol + 1)) {
 					goto end_auto_index_create;
 				}
 				pLoop->aLTerm[nKeyCol++] = pTerm;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 			}
 		}
 	}
@@ -797,17 +793,17 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	 * original table changes and the index and table cannot both be used
 	 * if they go out of sync.
 	 */
-	extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS - 1));
-	mxBitCol = MIN(BMS - 1, pTable->def->field_count);
-	testcase(pTable->def->field_count == BMS - 1);
-	testcase(pTable->def->field_count == BMS - 2);
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i))
+	/* Bitmap of additional columns. */
+	uint64_t extra_cols = pSrc->colUsed &
+			     (~idxCols | COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1));
+	/* Maximum column in pSrc->colUsed. */
+	int max_col_idx = MIN(COLUMN_MASK_SIZE - 1, pTable->def->field_count);
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i))
 			nKeyCol++;
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		nKeyCol += pTable->def->field_count - BMS + 1;
-	}
+	if (column_mask_is_overflowed(pSrc->colUsed))
+		nKeyCol += pTable->def->field_count - COLUMN_MASK_SIZE + 1;
 
 	/* Construct the Index object to describe this index */
 	pIdx = sqlite3DbMallocZero(pParse->db, sizeof(*pIdx));
@@ -821,13 +817,11 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS - 1);
-			testcase(iCol == BMS);
-			if ((idxCols & cMask) == 0) {
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
+			if ((idxCols & column_mask) == 0) {
 				Expr *pX = pTerm->pExpr;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 				pIdx->aiColumn[n] = pTerm->u.leftColumn;
 				n++;
 			}
@@ -838,14 +832,15 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	/* Add additional columns needed to make the automatic index into
 	 * a covering index
 	 */
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i)) {
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i)) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		for (i = BMS - 1; i < (int)pTable->def->field_count; i++) {
+	if (column_mask_is_overflowed(pSrc->colUsed)) {
+		for (i = COLUMN_MASK_SIZE - 1;
+		     i < (int)pTable->def->field_count; i++) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
@@ -3213,11 +3208,11 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return 0;
 
 	nOrderBy = pOrderBy->nExpr;
-	testcase(nOrderBy == BMS - 1);
-	if (nOrderBy > BMS - 1)
-		return 0;	/* Cannot optimize overly large ORDER BYs */
+	/* Cannot optimize overly large ORDER BYs. */
+	if (nOrderBy > COLUMN_MASK_SIZE - 1)
+		return 0;
 	isOrderDistinct = 1;
-	obDone = MASKBIT(nOrderBy) - 1;
+	obDone = COLUMN_MASK_BIT(nOrderBy) - 1;
 	orderDistinctMask = 0;
 	ready = 0;
 	eqOpMask = WO_EQ | WO_ISNULL;
@@ -3242,7 +3237,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		 * loops.
 		 */
 		for (i = 0; i < nOrderBy; i++) {
-			if (MASKBIT(i) & obSat)
+			if (column_mask_fieldno_is_set(obSat, i))
 				continue;
 			pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
 			if (pOBExpr->op != TK_COLUMN)
@@ -3282,7 +3277,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				if (coll1 != coll2)
 					continue;
 			}
-			obSat |= MASKBIT(i);
+			column_mask_set_fieldno(&obSat, i);
 		}
 
 		if ((pLoop->wsFlags & WHERE_ONEROW) == 0) {
@@ -3381,7 +3376,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				 */
 				isMatch = 0;
 				for (i = 0; bOnce && i < nOrderBy; i++) {
-					if (MASKBIT(i) & obSat)
+					if (column_mask_fieldno_is_set(obSat, i))
 						continue;
 					pOBExpr =
 					    sqlite3ExprSkipCollate(pOrderBy-> a[i].pExpr);
@@ -3427,14 +3422,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 						rev =
 						    revIdx ^ pOrderBy->a[i].
 						    sort_order;
-						if (rev)
-							*pRevMask |=
-							    MASKBIT(iLoop);
+						if (rev) {
+							column_mask_set_fieldno(
+								pRevMask, iLoop);
+						}
 						revSet = 1;
 					}
 				}
 				if (isMatch) {
-					obSat |= MASKBIT(i);
+					column_mask_set_fieldno(&obSat, i);
 				} else {
 					/* No match found */
 					if (j == 0 || j < nColumn) {
@@ -3457,16 +3453,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 			for (i = 0; i < nOrderBy; i++) {
 				Expr *p;
 				Bitmask mTerm;
-				if (MASKBIT(i) & obSat)
+				if (column_mask_fieldno_is_set(obSat, i))
 					continue;
 				p = pOrderBy->a[i].pExpr;
 				mTerm =
 				    sqlite3WhereExprUsage(&pWInfo->sMaskSet, p);
 				if (mTerm == 0 && !sqlite3ExprIsConstant(p))
 					continue;
-				if ((mTerm & ~orderDistinctMask) == 0) {
-					obSat |= MASKBIT(i);
-				}
+				if ((mTerm & ~orderDistinctMask) == 0)
+					column_mask_set_fieldno(&obSat, i);
 			}
 		}
 	}			/* End the loop over all WhereLoops from outer-most down to inner-most */
@@ -3474,7 +3469,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return (i8) nOrderBy;
 	if (!isOrderDistinct) {
 		for (i = nOrderBy - 1; i > 0; i--) {
-			Bitmask m = MASKBIT(i) - 1;
+			uint64_t m = COLUMN_MASK_BIT(i) - 1;
 			if ((obSat & m) == m)
 				return i;
 		}
@@ -4281,8 +4276,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 && pOrderBy->nExpr >= COLUMN_MASK_SIZE)
 		pOrderBy = 0;
 	sWLB.pOrderBy = pOrderBy;
 
@@ -4296,9 +4290,9 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 	/* The number of tables in the FROM clause is limited by the number of
 	 * bits in a Bitmask
 	 */
-	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;
 	}
 
@@ -4400,7 +4394,7 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 	for (ii = 0; ii < pTabList->nSrc; ii++) {
 		Bitmask m =
 		    sqlite3WhereGetMask(pMaskSet, pTabList->a[ii].iCursor);
-		assert(m == MASKBIT(ii));
+		assert(m == COLUMN_MASK_BIT(ii));
 	}
 #endif
 
@@ -4467,7 +4461,7 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 	}
 	if (pWInfo->pOrderBy == 0 &&
 	    (user_session->sql_flags & SQLITE_ReverseOrder) != 0) {
-		pWInfo->revMask = ALLBITS;
+		pWInfo->revMask = COLUMN_MASK_FULL;
 	}
 	if (pParse->nErr || NEVER(db->mallocFailed)) {
 		goto whereBeginError;
@@ -4574,10 +4568,6 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 					      space);
 			VdbeComment((v, "%s", space->def->name));
 			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,
@@ -4668,13 +4658,11 @@ sqlite3WhereBegin(Parse * pParse,	/* The parser context */
 							continue;
 						if (jj > 63)
 							jj = 63;
-						if ((pTabItem->
-						     colUsed & MASKBIT(jj)) ==
-						    0)
+						if (!column_mask_fieldno_is_set(
+							&pTabItem->colUsed, i))
 							continue;
-						colUsed |=
-						    ((u64) 1) << (ii <
-								  63 ? ii : 63);
+						column_mask_set_fieldno(&colUsed,
+									ii);
 					}
 					sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed,
 							      iIndexCur, 0, 0,
diff --git a/src/box/sql/whereInt.h b/src/box/sql/whereInt.h
index 4657055ea..db403ab55 100644
--- a/src/box/sql/whereInt.h
+++ b/src/box/sql/whereInt.h
@@ -378,7 +378,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];
 };
 
 /*
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 4/4] sql: got rid of redundant bitmask helpers

[Vladislav Shpilevoy]

Thanks for the patch! See 2 comments below.

On 08/02/2019 13:52, Kirill Shcherbatov wrote:
> The original SQLite code allowed the program to be compiled using
> 32-bit masks to save disk space. Since we are not going to
> compile Tarantool in such way, we will get rid of these macros by
> replacing them(where possible) with helpers from column_mask.h
> 
> Closes #3571
> ---
>   src/box/sql/expr.c      |  31 ++++++-----
>   src/box/sql/resolve.c   |  12 +----
>   src/box/sql/sqliteInt.h |  24 ++-------
>   src/box/sql/where.c     | 110 ++++++++++++++++++----------------------
>   src/box/sql/whereInt.h  |   3 +-
>   5 files changed, 74 insertions(+), 106 deletions(-)
> 
> diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
> index cf82bd366..613c29bbb 100644
> --- a/src/box/sql/expr.c
> +++ b/src/box/sql/expr.c
> @@ -2456,19 +2456,20 @@ sqlite3FindInIndex(Parse * pParse,	/* Parsing context */
>   			     eType == 0; ++k) {
>   				struct index *idx = space->index[k];
>   				Bitmask colUsed; /* Columns of the index used */
> -				Bitmask mCol;	/* Mask for the current column */
>   				uint32_t part_count =
>   					idx->def->key_def->part_count;
>   				struct key_part *parts =
>   					idx->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

1. There is no nColumn variable.

> +				 * COLUMN_MASK_SIZE-2, not
> +				 * COLUMN_MASK_SIZE-1, so that we
> +				 * can compute bitmask 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 ||
> @@ -2504,19 +2505,23 @@ 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_fieldno_is_set(colUsed,
> +								       j))
> +						break;

2. You broke down the behaviour. Before your patch,
mCol in case of j >= BMS was == 0 and the condition
(mCol & colUsed) == false. Now it is possible that
with j >= COLUMN_MASK_SIZE the condition is true.

Even if j was not visited earlier in fact. For example,
if you visited any of columns [63, +inf], then you will
consider visited *all* the columns [63, +inf].

Taking into account the previous patch and the problem
with 32bit VdbeOp.p1 I see a more common problem - column
mask is not scalable nor configurable. For example, here
we do not need a smart mask. We need just a simple one.
On the other hand, in the previous commit we need a 32bit
mask.

Honestly, I do not know what to advice you in order how
to fix it because my solution is likely to be rejected by
Kostja. I can just formalize and list possible options
and let you choose one. Or you can come up with a better
one. And consult Kostja.

My variants:

1. Do not introduce any additional types or macros.
    Just make several hardcoded sets of functions.

     One set for smart 64 bit mask:

         smart_column_mask_fieldno_is_set
         smart_column_mask_is_overflowed
         smart_column_mask_set_range
         smart_column_mask_set_fieldno

     One set for simple 64 bit mask:

         column_mask64_fieldno_is_set
         column_mask64_set_fieldno

     One set for simple 32 bit mask:

         column_mask32_fieldno_is_set
         column_mask32_set_fieldno

2. Turn column_mask.h into a template header, like mhash, rbtree etc.

     Before calling include "column_mask.h" you define something like
     CMASK_IS_SMART (1 / 0), CMASK_SIZE (32 / 64).

     Then column_mask.h uses these macro values in functions names and
     bodies.

     Example:

	#ifndef CMASK_IS_SMART
	#error "Expected CMASK_IS_SMART macro"
	#endif

	#ifndef CMASK_SIZE
	#error "Expected CMASK_SIZE macro"
	#endif

	#if CMASK_IS_SMART == 1
	#define PREFIX smart_
	#else
	#define PREFIX
	#endif

	#define mask_t uint##CMASK_SIZE##_t

	#define cmask(funcname) PREFIX##column_mask##CMASK_SIZE##funcname

	static inline void
	cmask(set_fieldno)(mask_t *column_mask, uint32_t fieldno)
	{
		if (CMASK_IS_SMART && fieldno >= COLUMN_MASK_SIZE - 1)
			/*
			 * @sa column_mask key_def declaration for
			 * details.
			 */
			*column_mask |= COLUMN_MASK_BIT(COLUMN_MASK_SIZE - 1);
		else
			*column_mask |= COLUMN_MASK_BIT(fieldno);
	}

	/** Other functions ... */

	#undef CMASK_IS_SMART
	#undef CMASK_SIZE
	#undef PREFIX
	#undef mask_t
	#undef cmask

Personally, I prefer the second one. Looks beautiful in my opinion. I will
review the rest after you fixed the present comments.

> +					column_mask_set_fieldno(&colUsed, 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)) {
> +				assert(i == nExpr ||
> +				       colUsed != (COLUMN_MASK_BIT(nExpr) - 1));
> +				if (colUsed == (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);

[tarantool-patches] Re: [PATCH v1 4/4] sql: got rid of redundant bitmask helpers

[Kirill Shcherbatov]

> 1. There is no nColumn variable.
Fixed.

> 2. You broke down the behaviour. Before your patch,
> mCol in case of j >= BMS was == 0 and the condition
> (mCol & colUsed) == false. Now it is possible that
> with j >= COLUMN_MASK_SIZE the condition is true.
It is not so.
The are few if ... continue branches before, 
if ((int)part_count < nExpr)
	continue;
if (part_count >= BITMASK_SIZE - 1)
	continue;

So,
nExpr <= part_count
part_count < BITMASK_SIZE - 1
=> nExpr < BITMASK_SIZE - 1
=> j <= nExpr < BITMASK_SIZE - 1
So our bitmasks work fine, but like not smart.

=============================================

The original SQLite code allowed the program to be compiled using
32-bit masks to save disk space. Since we are not going to
compile Tarantool in such way, we will get rid of these macros by
replacing them(where possible) with helpers from column_mask.h

Closes #3571
---
 src/box/sql/expr.c     |  31 +++++++-----
 src/box/sql/resolve.c  |  12 +----
 src/box/sql/sqlInt.h   |  26 ++--------
 src/box/sql/where.c    | 109 +++++++++++++++++++----------------------
 src/box/sql/whereInt.h |   3 +-
 5 files changed, 77 insertions(+), 104 deletions(-)

diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index a72f986c6..a6c077fc4 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -2396,19 +2396,20 @@ sqlFindInIndex(Parse * pParse,	/* Parsing context */
 			     eType == 0; ++k) {
 				struct index *idx = space->index[k];
 				Bitmask colUsed; /* Columns of the index used */
-				Bitmask mCol;	/* Mask for the current column */
 				uint32_t part_count =
 					idx->def->key_def->part_count;
 				struct key_part *parts =
 					idx->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 fieldno is
+				 * BITMASK_SIZE-2, not
+				 * BITMASK_SIZE-1, so that we
+				 * can compute bitmask without
+				 * overflowing.
 				 */
-				testcase(part_count == BMS - 2);
-				testcase(part_count == BMS - 1);
-				if (part_count >= BMS - 1)
+				if (part_count >= BITMASK_SIZE - 1)
 					continue;
 				if (mustBeUnique &&
 				    ((int)part_count > nExpr ||
@@ -2444,19 +2445,23 @@ sqlFindInIndex(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_fieldno_is_set(colUsed,
+								       j))
+						break;
+					column_mask_set_fieldno(&colUsed, 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)) {
+				assert(i == nExpr ||
+				       colUsed != (BITMASK_BIT(nExpr) - 1));
+				if (colUsed == (BITMASK_BIT(nExpr) - 1)) {
 					/* If we reach this point, that means the index pIdx is usable */
 					int iAddr = sqlVdbeAddOp0(v, OP_Once);
 					VdbeCoverage(v);
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index a9a167477..8940efd9d 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -440,13 +440,8 @@ lookupName(Parse * pParse,	/* The parsing context */
 	 * 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->colUsed, pExpr->iColumn);
 	}
 
 	/* Clean up and return
@@ -488,10 +483,7 @@ sqlCreateColumnExpr(sql * db, SrcList * pSrc, int iSrc, int iCol)
 		p->space_def = pItem->space->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->colUsed, iCol);
 		ExprSetProperty(p, EP_Resolved);
 	}
 	return p;
diff --git a/src/box/sql/sqlInt.h b/src/box/sql/sqlInt.h
index a9b7dfa4e..7d17e8753 100644
--- a/src/box/sql/sqlInt.h
+++ b/src/box/sql/sqlInt.h
@@ -2234,28 +2234,12 @@ struct IdList {
 };
 
 /*
- * 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 SQL_BITMASK_TYPE
-typedef SQL_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
+ * The bitmask datatype defined below is used for various
+ * optimizations.
  */
-#define MASKBIT(n)   (((Bitmask)1)<<(n))
-#define ALLBITS      ((Bitmask)-1)
+typedef uint64_t Bitmask;
+#define BITMASK_SIZE ((int)sizeof(Bitmask)*CHAR_BIT)
+#define BITMASK_BIT(n)   (((Bitmask)1)<<(n))
 
 /*
  * The following structure describes the FROM clause of a SELECT statement.
diff --git a/src/box/sql/where.c b/src/box/sql/where.c
index fc05c9f85..b8a9d6f31 100644
--- a/src/box/sql/where.c
+++ b/src/box/sql/where.c
@@ -219,9 +219,8 @@ sqlWhereGetMask(WhereMaskSet * pMaskSet, int iCursor)
 	int i;
 	assert(pMaskSet->n <= (int)sizeof(Bitmask) * 8);
 	for (i = 0; i < pMaskSet->n; i++) {
-		if (pMaskSet->ix[i] == iCursor) {
-			return MASKBIT(i);
-		}
+		if (pMaskSet->ix[i] == iCursor)
+			return BITMASK_BIT(i);
 	}
 	return 0;
 }
@@ -731,12 +730,10 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	int regRecord;		/* Register holding an index record */
 	int n;			/* Column counter */
 	int i;			/* Loop counter */
-	int mxBitCol;		/* Maximum column in pSrc->colUsed */
 	struct coll *pColl;		/* Collating sequence to on a column */
 	WhereLoop *pLoop;	/* The Loop object */
 	char *zNotUsed;		/* Extra space on the end of pIdx */
 	Bitmask idxCols;	/* Bitmap of columns used for indexing */
-	Bitmask extraCols;	/* Bitmap of additional columns */
 	u8 sentWarning = 0;	/* True if a warnning has been issued */
 	int iContinue = 0;	/* Jump here to skip excluded rows */
 	struct SrcList_item *pTabItem;	/* FROM clause term being indexed */
@@ -762,10 +759,8 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS);
-			testcase(iCol == BMS - 1);
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
 			if (!sentWarning) {
 				sql_log(SQL_WARNING_AUTOINDEX,
 					    "automatic index on %s(%s)",
@@ -773,13 +768,13 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 					    pTable->aCol[iCol].zName);
 				sentWarning = 1;
 			}
-			if ((idxCols & cMask) == 0) {
+			if ((idxCols & column_mask) == 0) {
 				if (whereLoopResize
 				    (pParse->db, pLoop, nKeyCol + 1)) {
 					goto end_auto_index_create;
 				}
 				pLoop->aLTerm[nKeyCol++] = pTerm;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 			}
 		}
 	}
@@ -796,17 +791,17 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	 * original table changes and the index and table cannot both be used
 	 * if they go out of sync.
 	 */
-	extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS - 1));
-	mxBitCol = MIN(BMS - 1, pTable->def->field_count);
-	testcase(pTable->def->field_count == BMS - 1);
-	testcase(pTable->def->field_count == BMS - 2);
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i))
+	/* Bitmap of additional columns. */
+	uint64_t extra_cols = pSrc->colUsed &
+			     (~idxCols | BITMASK_BIT(BITMASK_SIZE - 1));
+	/* Maximum column in pSrc->colUsed. */
+	int max_col_idx = MIN(BITMASK_SIZE - 1, pTable->def->field_count);
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i))
 			nKeyCol++;
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		nKeyCol += pTable->def->field_count - BMS + 1;
-	}
+	if (column_mask_is_overflowed(pSrc->colUsed))
+		nKeyCol += pTable->def->field_count - BITMASK_SIZE + 1;
 
 	/* Construct the Index object to describe this index */
 	pIdx = sqlDbMallocZero(pParse->db, sizeof(*pIdx));
@@ -820,13 +815,11 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS - 1);
-			testcase(iCol == BMS);
-			if ((idxCols & cMask) == 0) {
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
+			if ((idxCols & column_mask) == 0) {
 				Expr *pX = pTerm->pExpr;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 				pIdx->aiColumn[n] = pTerm->u.leftColumn;
 				n++;
 			}
@@ -837,14 +830,15 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	/* Add additional columns needed to make the automatic index into
 	 * a covering index
 	 */
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i)) {
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i)) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		for (i = BMS - 1; i < (int)pTable->def->field_count; i++) {
+	if (column_mask_is_overflowed(pSrc->colUsed)) {
+		for (i = BITMASK_SIZE - 1;
+		     i < (int)pTable->def->field_count; i++) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
@@ -3201,11 +3195,11 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return 0;
 
 	nOrderBy = pOrderBy->nExpr;
-	testcase(nOrderBy == BMS - 1);
-	if (nOrderBy > BMS - 1)
-		return 0;	/* Cannot optimize overly large ORDER BYs */
+	/* Cannot optimize overly large ORDER BYs. */
+	if (nOrderBy > BITMASK_SIZE - 1)
+		return 0;
 	isOrderDistinct = 1;
-	obDone = MASKBIT(nOrderBy) - 1;
+	obDone = BITMASK_BIT(nOrderBy) - 1;
 	orderDistinctMask = 0;
 	ready = 0;
 	eqOpMask = WO_EQ | WO_ISNULL;
@@ -3230,7 +3224,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		 * loops.
 		 */
 		for (i = 0; i < nOrderBy; i++) {
-			if (MASKBIT(i) & obSat)
+			if (column_mask_fieldno_is_set(obSat, i))
 				continue;
 			pOBExpr = sqlExprSkipCollate(pOrderBy->a[i].pExpr);
 			if (pOBExpr->op != TK_COLUMN)
@@ -3270,7 +3264,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				if (coll1 != coll2)
 					continue;
 			}
-			obSat |= MASKBIT(i);
+			column_mask_set_fieldno(&obSat, i);
 		}
 
 		if ((pLoop->wsFlags & WHERE_ONEROW) == 0) {
@@ -3369,7 +3363,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				 */
 				isMatch = 0;
 				for (i = 0; bOnce && i < nOrderBy; i++) {
-					if (MASKBIT(i) & obSat)
+					if (column_mask_fieldno_is_set(obSat, i))
 						continue;
 					pOBExpr =
 					    sqlExprSkipCollate(pOrderBy-> a[i].pExpr);
@@ -3415,14 +3409,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 						rev =
 						    revIdx ^ pOrderBy->a[i].
 						    sort_order;
-						if (rev)
-							*pRevMask |=
-							    MASKBIT(iLoop);
+						if (rev) {
+							column_mask_set_fieldno(
+								pRevMask, iLoop);
+						}
 						revSet = 1;
 					}
 				}
 				if (isMatch) {
-					obSat |= MASKBIT(i);
+					column_mask_set_fieldno(&obSat, i);
 				} else {
 					/* No match found */
 					if (j == 0 || j < nColumn) {
@@ -3445,16 +3440,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 			for (i = 0; i < nOrderBy; i++) {
 				Expr *p;
 				Bitmask mTerm;
-				if (MASKBIT(i) & obSat)
+				if (column_mask_fieldno_is_set(obSat, i))
 					continue;
 				p = pOrderBy->a[i].pExpr;
 				mTerm =
 				    sqlWhereExprUsage(&pWInfo->sMaskSet, p);
 				if (mTerm == 0 && !sqlExprIsConstant(p))
 					continue;
-				if ((mTerm & ~orderDistinctMask) == 0) {
-					obSat |= MASKBIT(i);
-				}
+				if ((mTerm & ~orderDistinctMask) == 0)
+					column_mask_set_fieldno(&obSat, i);
 			}
 		}
 	}			/* End the loop over all WhereLoops from outer-most down to inner-most */
@@ -3462,7 +3456,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return (i8) nOrderBy;
 	if (!isOrderDistinct) {
 		for (i = nOrderBy - 1; i > 0; i--) {
-			Bitmask m = MASKBIT(i) - 1;
+			uint32_t m = BITMASK_BIT(i) - 1;
 			if ((obSat & m) == m)
 				return i;
 		}
@@ -4269,8 +4263,7 @@ sqlWhereBegin(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 && pOrderBy->nExpr >= BITMASK_SIZE)
 		pOrderBy = 0;
 	sWLB.pOrderBy = pOrderBy;
 
@@ -4284,9 +4277,9 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	/* The number of tables in the FROM clause is limited by the number of
 	 * bits in a Bitmask
 	 */
-	testcase(pTabList->nSrc == BMS);
-	if (pTabList->nSrc > BMS) {
-		sqlErrorMsg(pParse, "at most %d tables in a join", BMS);
+	if (pTabList->nSrc > BITMASK_SIZE) {
+		sqlErrorMsg(pParse, "at most %d tables in a join",
+			    BITMASK_SIZE);
 		return 0;
 	}
 
@@ -4388,7 +4381,7 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	for (ii = 0; ii < pTabList->nSrc; ii++) {
 		Bitmask m =
 		    sqlWhereGetMask(pMaskSet, pTabList->a[ii].iCursor);
-		assert(m == MASKBIT(ii));
+		assert(m == BITMASK_BIT(ii));
 	}
 #endif
 
@@ -4455,7 +4448,7 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	}
 	if (pWInfo->pOrderBy == 0 &&
 	    (user_session->sql_flags & SQL_ReverseOrder) != 0) {
-		pWInfo->revMask = ALLBITS;
+		pWInfo->revMask = COLUMN_MASK_FULL;
 	}
 	if (pParse->nErr || NEVER(db->mallocFailed)) {
 		goto whereBeginError;
@@ -4653,13 +4646,11 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 							continue;
 						if (jj > 63)
 							jj = 63;
-						if ((pTabItem->
-						     colUsed & MASKBIT(jj)) ==
-						    0)
+						if (!column_mask_fieldno_is_set(
+							&pTabItem->colUsed, i))
 							continue;
-						colUsed |=
-						    ((u64) 1) << (ii <
-								  63 ? ii : 63);
+						column_mask_set_fieldno(&colUsed,
+									ii);
 					}
 					sqlVdbeAddOp4Dup8(v, OP_ColumnsUsed,
 							      iIndexCur, 0, 0,
diff --git a/src/box/sql/whereInt.h b/src/box/sql/whereInt.h
index 7a0312dfd..12a1dded6 100644
--- a/src/box/sql/whereInt.h
+++ b/src/box/sql/whereInt.h
@@ -379,7 +379,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[BITMASK_SIZE];
 };
 
 /*
-- 
2.20.1

[tarantool-patches] Re: [PATCH v1 4/4] sql: got rid of redundant bitmask helpers

[Vladislav Shpilevoy]

During verbal discussion we decided, that there are no
places, where non-smart 64 bit mask is needed. But this
patch proves the contrary. Bitmask in most places of
its usage is not smart, and can not be smart, because
is used for only limited number of optimizations relying
on some limited resources like cursors.

So now for me it is obvious, that in such places it makes
no sense to use 64 bit mask - anyway smartness is not
available.

I think, you should keep Bitmask 32 bit. What is more,
32bit mask, introduced in the first commit, is never used
as a smart one. It means, that you all in all should finally
make any 32 bit mask as not smart, replace Bitmask with
uint32_t, and refactor its usages with new methods from the
first commit.

Personally, I still think, that we should introduce bitmask_t
and smartmask_t to explicitly distinguish between them and
never mix. And to be able to change their size with ease.
Because your assumption that we never need non-smart masks
appeared to be wrong.

Of course, you can consult the server team chat, Kostja, or
Kirill, if you do not want to do it.