[tarantool-patches] [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[tarantool-patches] [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

An updated vdbe_field_ref fetcher class use a bitmap of
initialized slots to use pre-calculated offsets when possible.
This should speed-up SQL a bit.

Closes #4267
---
Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
Issue: https://github.com/tarantool/tarantool/issues/4267

 src/box/ck_constraint.c |   6 +-
 src/box/sql.c           |  16 ++++-
 src/box/sql.h           |  16 +++--
 src/box/sql/vdbe.c      | 128 +++++++++++++++++++++++++---------------
 4 files changed, 112 insertions(+), 54 deletions(-)

diff --git a/src/box/ck_constraint.c b/src/box/ck_constraint.c
index 1cde27022..48890e5df 100644
--- a/src/box/ck_constraint.c
+++ b/src/box/ck_constraint.c
@@ -188,8 +188,10 @@ ck_constraint_on_replace_trigger(struct trigger *trigger, void *event)
 
 	struct space *space = stmt->space;
 	assert(space != NULL);
-	uint32_t field_ref_sz = sizeof(struct vdbe_field_ref) +
-				sizeof(uint32_t) * space->def->field_count;
+	uint32_t field_ref_extra_sz =
+		vbde_field_ref_extra_sizeof(space->def->field_count);
+	uint32_t field_ref_sz =
+		sizeof(struct vdbe_field_ref) + field_ref_extra_sz;
 	struct vdbe_field_ref *field_ref =
 		region_alloc(&fiber()->gc, field_ref_sz);
 	if (field_ref == NULL) {
diff --git a/src/box/sql.c b/src/box/sql.c
index 4c9a4c15b..6c05518b3 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1226,6 +1226,14 @@ sql_ephemeral_space_new(Parse *parser, const char *name)
 	return space;
 }
 
+uint32_t
+vbde_field_ref_extra_sizeof(uint32_t max_field_count)
+{
+	assert(max_field_count > 0);
+	return (max_field_count) * sizeof(uint32_t) +
+	        bitmap_size(max_field_count + 1);
+}
+
 /**
  * Initialize a new vdbe_field_ref instance with given tuple
  * data.
@@ -1244,8 +1252,14 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
+
+	uint32_t slots_size = sizeof(uint32_t) * (field_ref->field_count + 1);
+	field_ref->slot_bitmap = (char *)field_ref->slots + slots_size;
+	memset(field_ref->slot_bitmap, 0,
+	       bitmap_size(field_ref->field_count + 1));
+
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	bit_set(field_ref->slot_bitmap, 0);
 }
 
 void
diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..3ad31cb21 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -360,6 +360,8 @@ sqlSrcListDelete(struct sql *db, struct SrcList *list);
  * |  struct vdbe_field_ref  |
  * +-------------------------+
  * |      RESERVED MEMORY    |
+ * |         (slots)         |
+ * |      (slot_bitmap)      |
  * +-------------------------+
  */
 struct vdbe_field_ref {
@@ -371,11 +373,8 @@ struct vdbe_field_ref {
 	uint32_t data_sz;
 	/** Count of fields in tuple. */
 	uint32_t field_count;
-	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
-	 */
-	uint32_t rightmost_slot;
+	/** Bitmap of initialized slots. */
+	void *slot_bitmap;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
@@ -383,6 +382,13 @@ struct vdbe_field_ref {
 	uint32_t slots[1];
 };
 
+/**
+ * Calculate the size of vdbe_field_ref structure
+ * that manages up to max_field_count fields.
+ */
+uint32_t
+vbde_field_ref_extra_sizeof(uint32_t max_field_count);
+
 /**
  * Initialize a new vdbe_field_ref instance with given tuple
  * data.
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index 6a4a303b9..0148b0297 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -234,8 +234,9 @@ allocateCursor(
 
 	int nByte;
 	VdbeCursor *pCx = 0;
-	nByte =
-		ROUND8(sizeof(VdbeCursor)) + sizeof(u32)*nField +
+	uint32_t field_ref_extra_sz =
+		ROUND8(vbde_field_ref_extra_sizeof(nField));
+	nByte = ROUND8(sizeof(VdbeCursor)) + field_ref_extra_sz +
 		(eCurType==CURTYPE_TARANTOOL ? ROUND8(sizeof(BtCursor)) : 0);
 
 	assert(iCur>=0 && iCur<p->nCursor);
@@ -250,7 +251,8 @@ allocateCursor(
 		pCx->nField = nField;
 		if (eCurType==CURTYPE_TARANTOOL) {
 			pCx->uc.pCursor = (BtCursor*)
-				&pMem->z[ROUND8(sizeof(VdbeCursor))+sizeof(u32)*nField];
+				&pMem->z[ROUND8(sizeof(VdbeCursor))+
+					 field_ref_extra_sz];
 			sqlCursorZero(pCx->uc.pCursor);
 		}
 	}
@@ -597,6 +599,23 @@ mem_type_to_str(const struct Mem *p)
 	}
 }
 
+static uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint32_t sz = bitmap_size(field_ref->field_count);
+	struct bit_iterator it;
+	bit_iterator_init(&it, field_ref->slot_bitmap, sz, true);
+	size_t prev, curr;
+	for (prev = curr = bit_iterator_next(&it);
+		curr < fieldno && curr < SIZE_MAX;
+		curr = bit_iterator_next(&it)) {
+		prev = curr;
+	}
+	assert(prev < SIZE_MAX);
+	return prev;
+}
+
 /**
  * Try to get a current tuple field using its field map.
  * @param field_ref The vdbe_field_ref instance to use.
@@ -610,18 +629,63 @@ static const void *
 vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 			  uint32_t *field_size)
 {
-	if (field_ref->tuple == NULL)
-		return NULL;
-	struct tuple_format *format = tuple_format(field_ref->tuple);
-	if (fieldno >= tuple_format_field_count(format) ||
-	    tuple_format_field(format, fieldno)->offset_slot ==
-	    TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	struct tuple_format *format = field_ref->tuple != NULL ?
+				      tuple_format(field_ref->tuple) : NULL;
+	uint32_t format_field_count =
+		 format != NULL ? tuple_format_field_count(format) : 0;
+
+	const char *field_begin = NULL, *field_end = NULL;
+	if (bit_test(field_ref->slot_bitmap, fieldno)) {
+		/*
+		 * Current field has been already
+		 * touched before.
+		 */
+		field_begin = field_ref->data + field_ref->slots[fieldno];
+	} else {
+		struct tuple_field *field =
+			fieldno < format_field_count ?
+			tuple_format_field(format, fieldno) : NULL;
+		if (field != NULL &&
+		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+			field_begin = tuple_field(field_ref->tuple, fieldno);
+		} else {
+			/*
+			 * Lookup for the closest previously
+			 * touched field.
+			 */
+			uint32_t prev =
+				vdbe_field_ref_closest_slotno(field_ref,
+							      fieldno);
+			field_begin = field_ref->data + field_ref->slots[prev];
+			for (; prev < fieldno; prev++)
+				mp_next(&field_begin);
+		}
+		field_ref->slots[fieldno] =
+			(uint32_t)(field_begin - field_ref->data);
+		bit_set(field_ref->slot_bitmap, fieldno);
+	}
+
+	if (bit_test(field_ref->slot_bitmap, fieldno + 1)) {
+		/* Next field has been already touched before. */
+		field_end = field_ref->data + field_ref->slots[fieldno + 1];
+	} else {
+		struct tuple_field *field =
+			fieldno + 1 < format_field_count ?
+			tuple_format_field(format, fieldno + 1) : NULL;
+		if (field != NULL &&
+		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+			field_end = tuple_field(field_ref->tuple, fieldno + 1);
+		} else {
+			field_end = field_begin;
+			mp_next(&field_end);
+		}
+		field_ref->slots[fieldno + 1] =
+			(uint32_t)(field_end - field_ref->data);
+		bit_set(field_ref->slot_bitmap, fieldno + 1);
+	}
+
+	*field_size = field_end - field_begin;
+	return field_begin;
 }
 
 /**
@@ -643,37 +707,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
+	uint32_t field_sz;
+	const char *data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
+						     &field_sz);
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
 	uint32_t dummy;
 	data = field_ref->data + slots[fieldno];
-- 
2.22.0

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

Sorry, please take into account this diff:

diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index 0148b0297..dca483785 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -657,8 +657,12 @@ vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 				vdbe_field_ref_closest_slotno(field_ref,
 							      fieldno);
 			field_begin = field_ref->data + field_ref->slots[prev];
-			for (; prev < fieldno; prev++)
+			for (; prev < fieldno; prev++) {
+				field_ref->slots[prev] =
+					(uint32_t)(field_begin - field_ref->data);
+				bit_set(field_ref->slot_bitmap, prev);
 				mp_next(&field_begin);
+			}
 		}
 		field_ref->slots[fieldno] =
 			(uint32_t)(field_begin - field_ref->data);

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

An updated vdbe_field_ref fetcher class use a bitmap of
initialized slots to use pre-calculated offsets when possible.
This should speed-up SQL a bit.

Closes #4267
---
 src/box/ck_constraint.c |   6 +-
 src/box/sql.c           |  16 ++++-
 src/box/sql.h           |  16 +++--
 src/box/sql/vdbe.c      | 132 ++++++++++++++++++++++++++--------------
 4 files changed, 116 insertions(+), 54 deletions(-)

diff --git a/src/box/ck_constraint.c b/src/box/ck_constraint.c
index 1cde27022..48890e5df 100644
--- a/src/box/ck_constraint.c
+++ b/src/box/ck_constraint.c
@@ -188,8 +188,10 @@ ck_constraint_on_replace_trigger(struct trigger *trigger, void *event)
 
 	struct space *space = stmt->space;
 	assert(space != NULL);
-	uint32_t field_ref_sz = sizeof(struct vdbe_field_ref) +
-				sizeof(uint32_t) * space->def->field_count;
+	uint32_t field_ref_extra_sz =
+		vbde_field_ref_extra_sizeof(space->def->field_count);
+	uint32_t field_ref_sz =
+		sizeof(struct vdbe_field_ref) + field_ref_extra_sz;
 	struct vdbe_field_ref *field_ref =
 		region_alloc(&fiber()->gc, field_ref_sz);
 	if (field_ref == NULL) {
diff --git a/src/box/sql.c b/src/box/sql.c
index 4c9a4c15b..6c05518b3 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1226,6 +1226,14 @@ sql_ephemeral_space_new(Parse *parser, const char *name)
 	return space;
 }
 
+uint32_t
+vbde_field_ref_extra_sizeof(uint32_t max_field_count)
+{
+	assert(max_field_count > 0);
+	return (max_field_count) * sizeof(uint32_t) +
+	        bitmap_size(max_field_count + 1);
+}
+
 /**
  * Initialize a new vdbe_field_ref instance with given tuple
  * data.
@@ -1244,8 +1252,14 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
+
+	uint32_t slots_size = sizeof(uint32_t) * (field_ref->field_count + 1);
+	field_ref->slot_bitmap = (char *)field_ref->slots + slots_size;
+	memset(field_ref->slot_bitmap, 0,
+	       bitmap_size(field_ref->field_count + 1));
+
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	bit_set(field_ref->slot_bitmap, 0);
 }
 
 void
diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..3ad31cb21 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -360,6 +360,8 @@ sqlSrcListDelete(struct sql *db, struct SrcList *list);
  * |  struct vdbe_field_ref  |
  * +-------------------------+
  * |      RESERVED MEMORY    |
+ * |         (slots)         |
+ * |      (slot_bitmap)      |
  * +-------------------------+
  */
 struct vdbe_field_ref {
@@ -371,11 +373,8 @@ struct vdbe_field_ref {
 	uint32_t data_sz;
 	/** Count of fields in tuple. */
 	uint32_t field_count;
-	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
-	 */
-	uint32_t rightmost_slot;
+	/** Bitmap of initialized slots. */
+	void *slot_bitmap;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
@@ -383,6 +382,13 @@ struct vdbe_field_ref {
 	uint32_t slots[1];
 };
 
+/**
+ * Calculate the size of vdbe_field_ref structure
+ * that manages up to max_field_count fields.
+ */
+uint32_t
+vbde_field_ref_extra_sizeof(uint32_t max_field_count);
+
 /**
  * Initialize a new vdbe_field_ref instance with given tuple
  * data.
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index 6a4a303b9..dca483785 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -234,8 +234,9 @@ allocateCursor(
 
 	int nByte;
 	VdbeCursor *pCx = 0;
-	nByte =
-		ROUND8(sizeof(VdbeCursor)) + sizeof(u32)*nField +
+	uint32_t field_ref_extra_sz =
+		ROUND8(vbde_field_ref_extra_sizeof(nField));
+	nByte = ROUND8(sizeof(VdbeCursor)) + field_ref_extra_sz +
 		(eCurType==CURTYPE_TARANTOOL ? ROUND8(sizeof(BtCursor)) : 0);
 
 	assert(iCur>=0 && iCur<p->nCursor);
@@ -250,7 +251,8 @@ allocateCursor(
 		pCx->nField = nField;
 		if (eCurType==CURTYPE_TARANTOOL) {
 			pCx->uc.pCursor = (BtCursor*)
-				&pMem->z[ROUND8(sizeof(VdbeCursor))+sizeof(u32)*nField];
+				&pMem->z[ROUND8(sizeof(VdbeCursor))+
+					 field_ref_extra_sz];
 			sqlCursorZero(pCx->uc.pCursor);
 		}
 	}
@@ -597,6 +599,23 @@ mem_type_to_str(const struct Mem *p)
 	}
 }
 
+static uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint32_t sz = bitmap_size(field_ref->field_count);
+	struct bit_iterator it;
+	bit_iterator_init(&it, field_ref->slot_bitmap, sz, true);
+	size_t prev, curr;
+	for (prev = curr = bit_iterator_next(&it);
+		curr < fieldno && curr < SIZE_MAX;
+		curr = bit_iterator_next(&it)) {
+		prev = curr;
+	}
+	assert(prev < SIZE_MAX);
+	return prev;
+}
+
 /**
  * Try to get a current tuple field using its field map.
  * @param field_ref The vdbe_field_ref instance to use.
@@ -610,18 +629,67 @@ static const void *
 vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 			  uint32_t *field_size)
 {
-	if (field_ref->tuple == NULL)
-		return NULL;
-	struct tuple_format *format = tuple_format(field_ref->tuple);
-	if (fieldno >= tuple_format_field_count(format) ||
-	    tuple_format_field(format, fieldno)->offset_slot ==
-	    TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	struct tuple_format *format = field_ref->tuple != NULL ?
+				      tuple_format(field_ref->tuple) : NULL;
+	uint32_t format_field_count =
+		 format != NULL ? tuple_format_field_count(format) : 0;
+
+	const char *field_begin = NULL, *field_end = NULL;
+	if (bit_test(field_ref->slot_bitmap, fieldno)) {
+		/*
+		 * Current field has been already
+		 * touched before.
+		 */
+		field_begin = field_ref->data + field_ref->slots[fieldno];
+	} else {
+		struct tuple_field *field =
+			fieldno < format_field_count ?
+			tuple_format_field(format, fieldno) : NULL;
+		if (field != NULL &&
+		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+			field_begin = tuple_field(field_ref->tuple, fieldno);
+		} else {
+			/*
+			 * Lookup for the closest previously
+			 * touched field.
+			 */
+			uint32_t prev =
+				vdbe_field_ref_closest_slotno(field_ref,
+							      fieldno);
+			field_begin = field_ref->data + field_ref->slots[prev];
+			for (; prev < fieldno; prev++) {
+				field_ref->slots[prev] =
+					(uint32_t)(field_begin - field_ref->data);
+				bit_set(field_ref->slot_bitmap, prev);
+				mp_next(&field_begin);
+			}
+		}
+		field_ref->slots[fieldno] =
+			(uint32_t)(field_begin - field_ref->data);
+		bit_set(field_ref->slot_bitmap, fieldno);
+	}
+
+	if (bit_test(field_ref->slot_bitmap, fieldno + 1)) {
+		/* Next field has been already touched before. */
+		field_end = field_ref->data + field_ref->slots[fieldno + 1];
+	} else {
+		struct tuple_field *field =
+			fieldno + 1 < format_field_count ?
+			tuple_format_field(format, fieldno + 1) : NULL;
+		if (field != NULL &&
+		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+			field_end = tuple_field(field_ref->tuple, fieldno + 1);
+		} else {
+			field_end = field_begin;
+			mp_next(&field_end);
+		}
+		field_ref->slots[fieldno + 1] =
+			(uint32_t)(field_end - field_ref->data);
+		bit_set(field_ref->slot_bitmap, fieldno + 1);
+	}
+
+	*field_size = field_end - field_begin;
+	return field_begin;
 }
 
 /**
@@ -643,37 +711,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
+	uint32_t field_sz;
+	const char *data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
+						     &field_sz);
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
 	uint32_t dummy;
 	data = field_ref->data + slots[fieldno];
-- 
2.22.0

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

Hi! Thanks for the patch!

See 7 comments below.

On 22/07/2019 09:43, Kirill Shcherbatov wrote:
> An updated vdbe_field_ref fetcher class use a bitmap of
> initialized slots to use pre-calculated offsets when possible.
> This should speed-up SQL a bit.

1. Please, describe here the problem in more details. Otherwise
it is far from obvious what is wrong with the current version.

> 
> Closes #4267
> ---
> Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
> Issue: https://github.com/tarantool/tarantool/issues/4267
> 
>  src/box/ck_constraint.c |   6 +-
>  src/box/sql.c           |  16 ++++-
>  src/box/sql.h           |  16 +++--
>  src/box/sql/vdbe.c      | 128 +++++++++++++++++++++++++---------------
>  4 files changed, 112 insertions(+), 54 deletions(-)
> 
> diff --git a/src/box/sql.c b/src/box/sql.c
> index 4c9a4c15b..6c05518b3 100644
> --- a/src/box/sql.c
> +++ b/src/box/sql.c
> @@ -1226,6 +1226,14 @@ sql_ephemeral_space_new(Parse *parser, const char *name)
>  	return space;
>  }
>  
> +uint32_t
> +vbde_field_ref_extra_sizeof(uint32_t max_field_count)
> +{
> +	assert(max_field_count > 0);
> +	return (max_field_count) * sizeof(uint32_t) +

2. Why do you need parentheses for max_field_count?

> +	        bitmap_size(max_field_count + 1);
> +}
> +
>  /**
>   * Initialize a new vdbe_field_ref instance with given tuple
>   * data.
> @@ -1244,8 +1252,14 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
>  
>  	const char *field0 = data;
>  	field_ref->field_count = mp_decode_array((const char **) &field0);
> +
> +	uint32_t slots_size = sizeof(uint32_t) * (field_ref->field_count + 1);
> +	field_ref->slot_bitmap = (char *)field_ref->slots + slots_size;
> +	memset(field_ref->slot_bitmap, 0,
> +	       bitmap_size(field_ref->field_count + 1));

3. Why +1?

> +
>  	field_ref->slots[0] = (uint32_t)(field0 - data);
> -	field_ref->rightmost_slot = 0;
> +	bit_set(field_ref->slot_bitmap, 0);
>  }
>  
>  void
> diff --git a/src/box/sql.h b/src/box/sql.h
> index 9ccecf28c..3ad31cb21 100644
> --- a/src/box/sql.h
> +++ b/src/box/sql.h
> @@ -383,6 +382,13 @@ struct vdbe_field_ref {
>  	uint32_t slots[1];
>  };
>  
> +/**
> + * Calculate the size of vdbe_field_ref structure
> + * that manages up to max_field_count fields.

4. But it is not size of the whole structure. Only size
of a tail memory block.

> + */
> +uint32_t
> +vbde_field_ref_extra_sizeof(uint32_t max_field_count);
> +
>  /**
>   * Initialize a new vdbe_field_ref instance with given tuple
>   * data.
> diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
> index 6a4a303b9..0148b0297 100644
> --- a/src/box/sql/vdbe.c
> +++ b/src/box/sql/vdbe.c
> @@ -597,6 +599,23 @@ mem_type_to_str(const struct Mem *p)
>  	}
>  }
>  
> +static uint32_t
> +vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
> +			      uint32_t fieldno)
> +{
> +	uint32_t sz = bitmap_size(field_ref->field_count);
> +	struct bit_iterator it;
> +	bit_iterator_init(&it, field_ref->slot_bitmap, sz, true);
> +	size_t prev, curr;
> +	for (prev = curr = bit_iterator_next(&it);
> +		curr < fieldno && curr < SIZE_MAX;
> +		curr = bit_iterator_next(&it)) {

5. The alignment is broken.

In addition, have you seen bit_iterator_init and bit_iterator_next?
They are huge. They do so many actions, that perhaps it would be
faster to decode MessagePack. Could you bench if it works really faster
now? The most notable improvement should be for the case, when
tuple fields are big complex objects (array, maps), and mp_next(&field)
becomes a really expensive operation.

I understand, that it is hard to microbench this in Lua or C, so I
propose to write a Lua bench, and to add time measurements right into
the C code
- before and after sql_prepare_and_execute;
- before and after vdbe_field_ref_fetch.

In Lua we will see ~ overall improvement (I hope),
around sql_prepare_and_execute we will see results not affected by
Lua, and around vdbe_field_ref_fetch we will see the true impact. 

> +		prev = curr;
> +	}
> +	assert(prev < SIZE_MAX);
> +	return prev;
> +}
> +
>  /**
>   * Try to get a current tuple field using its field map.
>   * @param field_ref The vdbe_field_ref instance to use.
> @@ -610,18 +629,63 @@ static const void *
>  vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
>  			  uint32_t *field_size)

6. I guess it is not a fast path anymore, because you moved all the paths
here, including the case when fieldno is not in the format. The function
should be renamed to something appropriate, please.

>  {
> -	if (field_ref->tuple == NULL)
> -		return NULL;
> -	struct tuple_format *format = tuple_format(field_ref->tuple);
> -	if (fieldno >= tuple_format_field_count(format) ||
> -	    tuple_format_field(format, fieldno)->offset_slot ==
> -	    TUPLE_OFFSET_SLOT_NIL)
> -		return NULL;
> -	const char *field = tuple_field(field_ref->tuple, fieldno);
> -	const char *end = field;
> -	mp_next(&end);
> -	*field_size = end - field;
> -	return field;
> +	struct tuple_format *format = field_ref->tuple != NULL ?
> +				      tuple_format(field_ref->tuple) : NULL;
> +	uint32_t format_field_count =
> +		 format != NULL ? tuple_format_field_count(format) : 0;
> +
> +	const char *field_begin = NULL, *field_end = NULL;
> +	if (bit_test(field_ref->slot_bitmap, fieldno)) {
> +		/*
> +		 * Current field has been already
> +		 * touched before.
> +		 */
> +		field_begin = field_ref->data + field_ref->slots[fieldno];
> +	} else {
> +		struct tuple_field *field =
> +			fieldno < format_field_count ?
> +			tuple_format_field(format, fieldno) : NULL;
> +		if (field != NULL &&
> +		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
> +			field_begin = tuple_field(field_ref->tuple, fieldno);
> +		} else {
> +			/*
> +			 * Lookup for the closest previously
> +			 * touched field.
> +			 */
> +			uint32_t prev =
> +				vdbe_field_ref_closest_slotno(field_ref,
> +							      fieldno);
> +			field_begin = field_ref->data + field_ref->slots[prev];
> +			for (; prev < fieldno; prev++)
> +				mp_next(&field_begin);
> +		}
> +		field_ref->slots[fieldno] =
> +			(uint32_t)(field_begin - field_ref->data);
> +		bit_set(field_ref->slot_bitmap, fieldno);
> +	}

7. The blocks above and below are basically the same. Please, move one of them to
a function, and use it here.

> +
> +	if (bit_test(field_ref->slot_bitmap, fieldno + 1)) {
> +		/* Next field has been already touched before. */
> +		field_end = field_ref->data + field_ref->slots[fieldno + 1];
> +	} else {
> +		struct tuple_field *field =
> +			fieldno + 1 < format_field_count ?
> +			tuple_format_field(format, fieldno + 1) : NULL;
> +		if (field != NULL &&
> +		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
> +			field_end = tuple_field(field_ref->tuple, fieldno + 1);
> +		} else {
> +			field_end = field_begin;
> +			mp_next(&field_end);
> +		}
> +		field_ref->slots[fieldno + 1] =
> +			(uint32_t)(field_end - field_ref->data);
> +		bit_set(field_ref->slot_bitmap, fieldno + 1);
> +	}
> +
> +	*field_size = field_end - field_begin;
> +	return field_begin;
>  }
>  
>  /**

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

> Hi! Thanks for the patch!
Hello, Vlad! Thank you for your review.

> 1. Please, describe here the problem in more details. Otherwise
> it is far from obvious what is wrong with the current version.
Done =)

>> +uint32_t
>> +vbde_field_ref_extra_sizeof(uint32_t max_field_count)
>> +{
>> +	assert(max_field_count > 0);
>> +	return (max_field_count) * sizeof(uint32_t) +
> 
> 2. Why do you need parentheses for max_field_count?

>> +	memset(field_ref->slot_bitmap, 0,
>> +	       bitmap_size(field_ref->field_count + 1));
> 
> 3. Why +1?
Outdated.

>> +/**
>> + * Calculate the size of vdbe_field_ref structure
>> + * that manages up to max_field_count fields.
> 
> 4. But it is not size of the whole structure. Only size
> of a tail memory block.
Outdated. I don't introduce this function now. (redundant diff)

>> +		curr = bit_iterator_next(&it)) {
> 
> 5. The alignment is broken.
Outdated

> 
> In addition, have you seen bit_iterator_init and bit_iterator_next?
> They are huge. They do so many actions, that perhaps it would be
> faster to decode MessagePack. Could you bench if it works really faster
> now? The most notable improvement should be for the case, when
> tuple fields are big complex objects (array, maps), and mp_next(&field)
> becomes a really expensive operation.
> 
> I understand, that it is hard to microbench this in Lua or C, so I
> propose to write a Lua bench, and to add time measurements right into
> the C code
> - before and after sql_prepare_and_execute;
> - before and after vdbe_field_ref_fetch.
> 
> In Lua we will see ~ overall improvement (I hope),
> around sql_prepare_and_execute we will see results not affected by
> Lua, and around vdbe_field_ref_fetch we will see the true impact. 

I've carried three interesting experiments:
1) a very special corner case:
s = box.schema.create_space('test')
s:format({{'id', 'integer'}, {'crap1', 'array'}, {'crap2', 'array'}, {'crap3', 'array'},
          {'crap4', 'array'}, {'crap5', 'array'}, {'crap6', 'array'}, {'crap7', 'array'},
          {'crap8', 'array'}, {'crap9', 'array'}, {'crap10', 'array'}, {'crap11', 'array'},
          {'crap12', 'array'}, {'crap13', 'array'}, {'crap14', 'array'}, {'crap15', 'array'},
          {'crap16', 'array'}, {'crap17', 'array'}, {'crap18', 'array'}, {'crap19', 'array'},
          {'crap20', 'array'}, {'crap21', 'array'}, {'crap22', 'array'}, {'crap23', 'array'},
          {'crap24', 'array'}, {'crap25', 'array'}, {'crap26', 'array'}, {'crap27', 'array'},
          {'crap28', 'array'}, {'crap29', 'array'}, {'crap30', 'array'},
          {'num', 'integer'}, {'crap31', 'array'},  {'word', 'string'}})
_ = s:create_index('pk')
_ = s:create_index('sk', {parts = {32, 'integer'}})
t = {1, {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        666,
        {{1, 2, 3, 4, 5}, {hello={1, 2, 3}, world={2, 3, 4}, yet={3, 4, 5}, another={4, 5, 6}, word={5, 6, 7}}},
        "hey"}
s:insert(t)
box.execute("SELECT \"num\", \"word\" from \"test\";")

I've added 
    clock_t start, end;
    start = clock();
    /*  ...retrieve field code */
    end = clock();
    printf(">> %ld\n", (end - start));

code to measure performance of two sequential  calls: for 666 field and for "hey" field

Original: field 666 - 3 clock_t_diff; "hey" - 6 clock_t_diff
Patched: field 666 - 3 clock_t_diff; "hey" - 2 clock_t_diff

So as you see, this approach works.

2) I've instrumented the same peace of code, but I've also defined a few
static global variables, to aggregate statistics and portionally flush  it in
a file (you need to run a single test-runner thread):
    clock_t start, end;
    double cpu_time_used;
    start = clock();
    /* ...retrieve field code */
    end = clock();
    sum += (end - start);
    count++;
    if (count == 100000) {
	FILE *f = fopen("results.txt", "a+");
	assert(f != NULL);
	fprintf(f, "%Lf\n", ((long double)sum)/count);
	fflush(f);
	sum = 0;
	count = 0;
	fclose(f);
    }

I then averaged the results from this file.

I should say that modified code a bit faster, about 1.25%

> 6. I guess it is not a fast path anymore, because you moved all the paths
> here, including the case when fieldno is not in the format. The function
> should be renamed to something appropriate, please.
Shure.

> 7. The blocks above and below are basically the same. Please, move one of them to
> a function, and use it here.
Outdated.

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

Vdbe field ref is a dynamic index over tuple fields storing
offsets to each field and filling the offset array on demand.
It is highly used in SQL, because it strongly relies on fast and
repetitive access to any field, not only indexed.

There is an optimisation for the case when a requested field
fieldno is indexed, and the tuple itself stores offset to the
field in its own small field map, used by indexes. vdbe_field_ref
then uses that map to retrieve offset value without decoding
anything. But when SQL requests any field > fieldno, then
vdbe_field_ref decodes the tuple from the beginning in the worst
case. Even having previously accessed fieldno. But it could
start decoding from the latter.

An updated vdbe_field_ref fetcher class use a bitmask of an
initialized slots to use pre-calculated offsets when possible.
This speed-ups SQL in some corner case and doesn't damage
performance in general scenarios.

Closes #4267
---
Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
Issue: https://github.com/tarantool/tarantool/issues/4267

 src/box/sql.h      |  10 ++--
 src/box/sql.c      |   3 +-
 src/box/sql/vdbe.c | 111 +++++++++++++++++++++++++--------------------
 3 files changed, 70 insertions(+), 54 deletions(-)

diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..ec90d9099 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -372,10 +372,14 @@ struct vdbe_field_ref {
 	/** Count of fields in tuple. */
 	uint32_t field_count;
 	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
+	 * Bitmask of initialized slots. The fieldno == 0 slot
+	 * must be initially initialized in vdbe_field_ref
+	 * constructor.
+	 * This bitmap allows to lookup for a nearest initialized
+	 * slot for a given fieldno to perform as less extra
+	 * tuple decoding, as possible.
 	 */
-	uint32_t rightmost_slot;
+	uint64_t slot_bitmask;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
diff --git a/src/box/sql.c b/src/box/sql.c
index 0ab3a506f..94f468c28 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1245,7 +1245,8 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	field_ref->slot_bitmask = 0;
+	column_mask_set_fieldno(&field_ref->slot_bitmask, 0);
 }
 
 void
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index e096e1f65..d0ff420c1 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -606,27 +606,69 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 }
 
 /**
- * Try to get a current tuple field using its field map.
+ * Find the closest field for given fieldno in field_ref's
+ * slot_bitmask. The fieldno is expected to be greater than 1.
+ * @param field_ref The vdbe_field_ref instance to use.
+ * @pram fieldno Number of a field to find nearest neighbor.
+ * @retval >0 an index of the closest lesser fieldno
+ *            initialized in slot_bitmask.
+ */
+static uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint64_t slot_bitmask = field_ref->slot_bitmask;
+	assert(slot_bitmask != 0 && fieldno > 0);
+	uint64_t le_mask = fieldno < 64 ?
+			   slot_bitmask & ((1LLU << fieldno) - 1) : slot_bitmask;
+	assert(bit_clz_u64(le_mask) < 64);
+	return 64 - bit_clz_u64(le_mask) - 1;
+}
+
+/**
+ * Get a tuple's field using field_ref's slot_bitmask, and tuple's
+ * field_map when possible. Required field must present in tuple.
  * @param field_ref The vdbe_field_ref instance to use.
  * @param fieldno Number of a field to get.
- * @param[out] field_size Result field size.
  * @retval not NULL MessagePack field.
- * @retval NULL Can not use field_map - it does not contain
- *              offset to @a fieldno.
  */
-static const void *
-vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
-			  uint32_t *field_size)
+static const char *
+vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 {
-	const struct tuple_field *tf =
-		vdbe_field_ref_fetch_field(field_ref, fieldno);
-	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	/*
+	 * The column_mask_fieldno API works with a "smart" masks,
+	 * but actually we don't need smart masks here so we
+	 * should manually test that fieldno is lesser than
+	 * bitmask's size.
+	 */
+	if (fieldno < 64 &&
+	    column_mask_fieldno_is_set(field_ref->slot_bitmask, fieldno))
+		return field_ref->data + field_ref->slots[fieldno];
+
+	const char *field_begin;
+	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
+								     fieldno);
+	if (field != NULL &&
+		field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+		field_begin = tuple_field(field_ref->tuple, fieldno);
+	} else {
+		uint32_t prev =
+			vdbe_field_ref_closest_slotno(field_ref,
+							fieldno);
+		field_begin = field_ref->data + field_ref->slots[prev];
+		for (prev++; prev < fieldno; prev++) {
+			mp_next(&field_begin);
+			field_ref->slots[prev] =
+				(uint32_t)(field_begin - field_ref->data);
+			column_mask_set_fieldno(&field_ref->slot_bitmask,
+						prev);
+		}
+		mp_next(&field_begin);
+	}
+	field_ref->slots[fieldno] =
+		(uint32_t)(field_begin - field_ref->data);
+	column_mask_set_fieldno(&field_ref->slot_bitmask, fieldno);
+	return field_begin;
 }
 
 static inline enum field_type
@@ -652,45 +694,13 @@ static int
 vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		     struct Mem *dest_mem)
 {
-	uint32_t *slots = field_ref->slots;
 	if (fieldno >= field_ref->field_count) {
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
+	const char *data = vdbe_field_ref_fetch_data(field_ref, fieldno);
 	uint32_t dummy;
-	data = field_ref->data + slots[fieldno];
 	if (vdbe_decode_msgpack_into_mem(data, dest_mem, &dummy) != 0)
 		return -1;
 
@@ -699,8 +709,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 	 * Wrap it in a blob verbatim.
 	 */
 	if (dest_mem->flags == 0) {
-		dest_mem->n = slots[fieldno + 1] - slots[fieldno];
 		dest_mem->z = (char *) data;
+		dest_mem->n = vdbe_field_ref_fetch_data(field_ref,
+							fieldno + 1) - data;
 		dest_mem->flags = MEM_Blob | MEM_Ephem | MEM_Subtype;
 		dest_mem->subtype = SQL_SUBTYPE_MSGPACK;
 	}
-- 
2.22.0

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

Hi! Thanks for the fixes!

The patch is really cool, it gives notable impact on
performance. But see some technical and grammatical
comments, 21 items.


> Vdbe field ref is a dynamic index over tuple fields storing
> offsets to each field and filling the offset array on demand.
> It is highly used in SQL, because it strongly relies on fast and
> repetitive access to any field, not only indexed.
> 
> There is an optimisation for the case when a requested field
> fieldno is indexed, and the tuple itself stores offset to the
> field in its own small field map, used by indexes. vdbe_field_ref
> then uses that map to retrieve offset value without decoding
> anything. But when SQL requests any field > fieldno, then
> vdbe_field_ref decodes the tuple from the beginning in the worst
> case. Even having previously accessed fieldno. But it could
> start decoding from the latter.
> 
> An updated vdbe_field_ref fetcher class use a bitmask of an

1. 'uses'
2. 'an' is not used with plural.

> initialized slots to use pre-calculated offsets when possible.
> This speed-ups SQL in some corner case and doesn't damage
> performance in general scenarios.
> 
> Closes #4267
> ---
> Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
> Issue: https://github.com/tarantool/tarantool/issues/4267
> 
>  src/box/sql.h      |  10 ++--
>  src/box/sql.c      |   3 +-
>  src/box/sql/vdbe.c | 111 +++++++++++++++++++++++++--------------------
>  3 files changed, 70 insertions(+), 54 deletions(-)
> 
> diff --git a/src/box/sql.h b/src/box/sql.h
> index 9ccecf28c..ec90d9099 100644
> --- a/src/box/sql.h
> +++ b/src/box/sql.h
> @@ -372,10 +372,14 @@ struct vdbe_field_ref {
>  	/** Count of fields in tuple. */
>  	uint32_t field_count;
>  	/**
> -	 * Index of the rightmost initialized slot in slots
> -	 * array.
> +	 * Bitmask of initialized slots. The fieldno == 0 slot
> +	 * must be initially initialized in vdbe_field_ref

3. 'initially initialized'? Please, chose one word.

> +	 * constructor.
> +	 * This bitmap allows to lookup for a nearest initialized

4. Superlative adjectives should have 'the' almost always, not 'a'.

> +	 * slot for a given fieldno to perform as less extra

5. 'As few as'.

> +	 * tuple decoding, as possible.
>  	 */
> -	uint32_t rightmost_slot;
> +	uint64_t slot_bitmask;
>  	/**
>  	 * Array of offsets of tuple fields.
>  	 * Only values <= rightmost_slot are valid.
> diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
> index e096e1f65..d0ff420c1 100644
> --- a/src/box/sql/vdbe.c
> +++ b/src/box/sql/vdbe.c
> @@ -606,27 +606,69 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
>  }
>  
>  /**
> - * Try to get a current tuple field using its field map.
> + * Find the closest field for given fieldno in field_ref's
> + * slot_bitmask. The fieldno is expected to be greater than 1.

6. Comment says '> 1', but the assertion says '> 0'. What is
correct?

> + * @param field_ref The vdbe_field_ref instance to use.
> + * @pram fieldno Number of a field to find nearest neighbor.

7. 'param'.

8. 'the nearest left neighbor of'.

9. In fact it finds not the nearest neighbor, but the
nearest left.

> + * @retval >0 an index of the closest lesser fieldno

10. lesser != of a smaller value, it is a different word.
'lesser' is "less than small".

11. Usually we start sentences from a capital letter.

> + *            initialized in slot_bitmask.
> + */
> +static uint32_t

12. Why not 'inline'? There is only one usage place, it won't
affect the code section size.

> +vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
> +			      uint32_t fieldno)
> +{
> +	uint64_t slot_bitmask = field_ref->slot_bitmask;
> +	assert(slot_bitmask != 0 && fieldno > 0);
> +	uint64_t le_mask = fieldno < 64 ?
> +			   slot_bitmask & ((1LLU << fieldno) - 1) : slot_bitmask;

13. Why do you consider fieldno >= 64 separately? If it is >= 64,
then ((1LLU << fieldno) - 1) is all ones, a full mask. It won't affect
slot_bitmask, and you will have the same result without this
branching.

> +	assert(bit_clz_u64(le_mask) < 64);
> +	return 64 - bit_clz_u64(le_mask) - 1;
> +}
> +
> +/**
> + * Get a tuple's field using field_ref's slot_bitmask, and tuple's
> + * field_map when possible. Required field must present in tuple.

14. 'be present'.

>   * @param field_ref The vdbe_field_ref instance to use.
>   * @param fieldno Number of a field to get.
> - * @param[out] field_size Result field size.
>   * @retval not NULL MessagePack field.
> - * @retval NULL Can not use field_map - it does not contain
> - *              offset to @a fieldno.
>   */
> -static const void *
> -vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
> -			  uint32_t *field_size)
> +static const char *
> +vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
>  {
> -	const struct tuple_field *tf =
> -		vdbe_field_ref_fetch_field(field_ref, fieldno);
> -	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
> -		return NULL;
> -	const char *field = tuple_field(field_ref->tuple, fieldno);
> -	const char *end = field;
> -	mp_next(&end);
> -	*field_size = end - field;
> -	return field;
> +	/*
> +	 * The column_mask_fieldno API works with a "smart" masks,

15. 'a' is not used with plural.

> +	 * but actually we don't need smart masks here so we
> +	 * should manually test that fieldno is lesser than

16. 'less'.

> +	 * bitmask's size.
> +	 */
> +	if (fieldno < 64 &&
> +	    column_mask_fieldno_is_set(field_ref->slot_bitmask, fieldno))
> +		return field_ref->data + field_ref->slots[fieldno];
> +
> +	const char *field_begin;
> +	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
> +								     fieldno);
> +	if (field != NULL &&
> +		field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {

17. Indentation is broken. In some places below too.

> +		field_begin = tuple_field(field_ref->tuple, fieldno);
> +	} else {
> +		uint32_t prev =
> +			vdbe_field_ref_closest_slotno(field_ref,
> +							fieldno);

18. Fits in 2 lines.

> +		field_begin = field_ref->data + field_ref->slots[prev];
> +		for (prev++; prev < fieldno; prev++) {
> +			mp_next(&field_begin);
> +			field_ref->slots[prev] =
> +				(uint32_t)(field_begin - field_ref->data);
> +			column_mask_set_fieldno(&field_ref->slot_bitmask,
> +						prev);

19. Fits one line.

> +		}
> +		mp_next(&field_begin);
> +	}
> +	field_ref->slots[fieldno] =
> +		(uint32_t)(field_begin - field_ref->data);

20. Fits one line.

> +	column_mask_set_fieldno(&field_ref->slot_bitmask, fieldno);

21. I remember we have already had this discussion, but here we go again.
When you use a smart mask as a dumb mask, you will face problems, for
sure. This leads to an assertion:

    box.cfg{}
    format = {}
    t = {}
    for i = 1, 70 do
        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
        t[i] = i
    end
    s = box.schema.create_space('TEST', {format = format})
    pk = s:create_index('pk', {parts = {70}})
    s:insert(t)
    box.execute('SELECT field70, field64 FROM test')

My opinion has not changed, we need separate functions for smart
and not-smart masks. This code not only asserts, but its fix on
top of smart masks would look bulky (you will manually set the bits
and check for < 64), repetitive (you have 2 places where bits
are set and one where checked), work slower (set_fieldno still would
make a check if fieldno >= 63 to set a smart bit).

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

> 1. 'uses'
> 2. 'an' is not used with plural.
> 3. 'initially initialized'? Please, chose one word.
> 4. Superlative adjectives should have 'the' almost always, not 'a'.
> 5. 'As few as'.
Tnx, fixed.

> 6. Comment says '> 1', but the assertion says '> 0'. What is
> correct?
The second. Fixed.

> 7. 'param'.
> 8. 'the nearest left neighbor of'.
> 9. In fact it finds not the nearest neighbor, but the
> nearest left.
> 11. Usually we start sentences from a capital letter.
> 12. Why not 'inline'? There is only one usage place, it won't
> affect the code section size.
Fixed.

> 13. Why do you consider fieldno >= 64 separately? If it is >= 64,
> then ((1LLU << fieldno) - 1) is all ones, a full mask. It won't affect
> slot_bitmask, and you will have the same result without this
> branching.
Because type overflow with << operator has undefined behavior.
This doesn't work in release mode (with optimization flags).

> 14. 'be present'.
> 15. 'a' is not used with plural.
> 16. 'less'.
> 17. Indentation is broken. In some places below too.
> 18. Fits in 2 lines.
> 19. Fits one line.
> 20. Fits one line.
Fixed.

> 21. I remember we have already had this discussion, but here we go again.
> When you use a smart mask as a dumb mask, you will face problems, for
> sure. This leads to an assertion:
> 
>     box.cfg{}
>     format = {}
>     t = {}
>     for i = 1, 70 do
>         format[i] = {name = 'FIELD'..i, type = 'unsigned'}
>         t[i] = i
>     end
>     s = box.schema.create_space('TEST', {format = format})
>     pk = s:create_index('pk', {parts = {70}})
>     s:insert(t)
>     box.execute('SELECT field70, field64 FROM test')
> 
> My opinion has not changed, we need separate functions for smart
> and not-smart masks. This code not only asserts, but its fix on
> top of smart masks would look bulky (you will manually set the bits
> and check for < 64), repetitive (you have 2 places where bits
> are set and one where checked), work slower (set_fieldno still would
> make a check if fieldno >= 63 to set a smart bit).
I've kept your test in test suite and fixed it:
I've introduced a new bitmask64_set_bit and bitmask64_bit_is_set helpers.

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

Vdbe field ref is a dynamic index over tuple fields storing
offsets to each field and filling the offset array on demand.
It is highly used in SQL, because it strongly relies on fast and
repetitive access to any field, not only indexed.

There is an optimisation for the case when a requested field
fieldno is indexed, and the tuple itself stores offset to the
field in its own small field map, used by indexes. vdbe_field_ref
then uses that map to retrieve offset value without decoding
anything. But when SQL requests any field > fieldno, then
vdbe_field_ref decodes the tuple from the beginning in the worst
case. Even having previously accessed fieldno. But it could
start decoding from the latter.

An updated vdbe_field_ref fetcher class uses a bitmask of
initialized slots to use pre-calculated offsets when possible.
This speed-ups SQL in some corner case and doesn't damage
performance in general scenarios.

Closes #4267
---
 src/box/column_mask.h  |  30 ++++++++++++
 src/box/sql.h          |   9 ++--
 src/box/sql.c          |   3 +-
 src/box/sql/vdbe.c     | 102 +++++++++++++++++++++--------------------
 test/sql/misc.result   |  46 +++++++++++++++++++
 test/sql/misc.test.lua |  17 +++++++
 6 files changed, 153 insertions(+), 54 deletions(-)

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index 14da841f1..0518fa6c3 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -123,4 +123,34 @@ column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
 	return (column_mask & mask) != 0;
 }
 
+/**
+ * Set a bit with given index @a bitno in a given @a bitmask.
+ * Do nothing when @a bitno is greater than size if bitmask.
+ * @param bitmask Bitmask to test.
+ * @param bitno bit number to test (must be 0-based).
+ */
+static inline void
+bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return;
+	*bitmask |= ((uint64_t)1 << bitno);
+}
+
+/**
+ * Test a bit in the bitmask corresponding to a bitno..
+ * @param bitmask Bitmask to test.
+ * @param bitno bit number to test (must be 0-based).
+ * @return Whether given bit is set in a given bitmask.
+ *         When bitno is greater than size of bitmask returns
+ *         false.
+ */
+static inline bool
+bitmask64_bit_is_set(uint64_t bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return false;
+	return (bitmask & ((uint64_t)1 << bitno)) != 0;
+}
+
 #endif
diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..08fe5c7af 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -372,10 +372,13 @@ struct vdbe_field_ref {
 	/** Count of fields in tuple. */
 	uint32_t field_count;
 	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
+	 * Bitmask of initialized slots. The fieldno == 0 slot
+	 * must be initialized in vdbe_field_ref constructor.
+	 * This bitmap allows to lookup for the nearest
+	 * initialized slot for a given fieldno to perform a few
+	 * extra tuple decoding, as possible.
 	 */
-	uint32_t rightmost_slot;
+	uint64_t slot_bitmask;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
diff --git a/src/box/sql.c b/src/box/sql.c
index 0ab3a506f..1a9a94eff 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1245,7 +1245,8 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	field_ref->slot_bitmask = 0;
+	bitmask64_set_bit(&field_ref->slot_bitmask, 0);
 }
 
 void
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index e096e1f65..cfb487115 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -606,27 +606,60 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 }
 
 /**
- * Try to get a current tuple field using its field map.
+ * Find the closest field for given fieldno in field_ref's
+ * slot_bitmask. The fieldno is expected to be greater than 0.
+ * @param field_ref The vdbe_field_ref instance to use.
+ * @param fieldno Number of a field to find the nearest left
+ *        neighbor of.
+ * @retval >0 An index of the closest smaller fieldno
+ *            initialized in slot_bitmask.
+ */
+static inline uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint64_t slot_bitmask = field_ref->slot_bitmask;
+	assert(slot_bitmask != 0 && fieldno > 0);
+	uint64_t le_mask = fieldno < 64 ?
+			   slot_bitmask & ((1LLU << fieldno) - 1) : slot_bitmask;
+	assert(bit_clz_u64(le_mask) < 64);
+	return 64 - bit_clz_u64(le_mask) - 1;
+}
+
+/**
+ * Get a tuple's field using field_ref's slot_bitmask, and tuple's
+ * field_map when possible. Required field must be present in
+ * tuple.
  * @param field_ref The vdbe_field_ref instance to use.
  * @param fieldno Number of a field to get.
- * @param[out] field_size Result field size.
  * @retval not NULL MessagePack field.
- * @retval NULL Can not use field_map - it does not contain
- *              offset to @a fieldno.
  */
-static const void *
-vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
-			  uint32_t *field_size)
+static const char *
+vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 {
-	const struct tuple_field *tf =
-		vdbe_field_ref_fetch_field(field_ref, fieldno);
-	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	if (bitmask64_bit_is_set(field_ref->slot_bitmask, fieldno))
+		return field_ref->data + field_ref->slots[fieldno];
+
+	const char *field_begin;
+	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
+								     fieldno);
+	if (field != NULL && field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+		field_begin = tuple_field(field_ref->tuple, fieldno);
+	} else {
+		uint32_t prev = vdbe_field_ref_closest_slotno(field_ref,
+							      fieldno);
+		field_begin = field_ref->data + field_ref->slots[prev];
+		for (prev++; prev < fieldno; prev++) {
+			mp_next(&field_begin);
+			field_ref->slots[prev] =
+				(uint32_t)(field_begin - field_ref->data);
+			bitmask64_set_bit(&field_ref->slot_bitmask, prev);
+		}
+		mp_next(&field_begin);
+	}
+	field_ref->slots[fieldno] = (uint32_t)(field_begin - field_ref->data);
+	bitmask64_set_bit(&field_ref->slot_bitmask, fieldno);
+	return field_begin;
 }
 
 static inline enum field_type
@@ -652,45 +685,13 @@ static int
 vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		     struct Mem *dest_mem)
 {
-	uint32_t *slots = field_ref->slots;
 	if (fieldno >= field_ref->field_count) {
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
+	const char *data = vdbe_field_ref_fetch_data(field_ref, fieldno);
 	uint32_t dummy;
-	data = field_ref->data + slots[fieldno];
 	if (vdbe_decode_msgpack_into_mem(data, dest_mem, &dummy) != 0)
 		return -1;
 
@@ -699,8 +700,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 	 * Wrap it in a blob verbatim.
 	 */
 	if (dest_mem->flags == 0) {
-		dest_mem->n = slots[fieldno + 1] - slots[fieldno];
 		dest_mem->z = (char *) data;
+		dest_mem->n = vdbe_field_ref_fetch_data(field_ref,
+							fieldno + 1) - data;
 		dest_mem->flags = MEM_Blob | MEM_Ephem | MEM_Subtype;
 		dest_mem->subtype = SQL_SUBTYPE_MSGPACK;
 	}
diff --git a/test/sql/misc.result b/test/sql/misc.result
index 2591d9d75..f2357c122 100644
--- a/test/sql/misc.result
+++ b/test/sql/misc.result
@@ -133,3 +133,49 @@ box.execute('select * from "s"')
 s:drop()
 ---
 ...
+--
+-- gh-4267: Full power of vdbe_field_ref
+--
+format = {}
+---
+...
+t = {}
+---
+...
+test_run:cmd("setopt delimiter ';'")
+---
+- true
+...
+for i = 1, 70 do
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
+        t[i] = i
+end
+test_run:cmd("setopt delimiter ''");
+---
+...
+s = box.schema.create_space('TEST', {format = format})
+---
+...
+pk = s:create_index('pk', {parts = {70}})
+---
+...
+s:insert(t)
+---
+- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
+  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
+  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
+  63, 64, 65, 66, 67, 68, 69, 70]
+...
+box.execute('SELECT field70, field64 FROM test')
+---
+- metadata:
+  - name: FIELD70
+    type: unsigned
+  - name: FIELD64
+    type: unsigned
+  rows:
+  - [70, 64]
+...
+box.space.TEST:drop()
+---
+...
diff --git a/test/sql/misc.test.lua b/test/sql/misc.test.lua
index fdc19f3ac..fb0fd5394 100644
--- a/test/sql/misc.test.lua
+++ b/test/sql/misc.test.lua
@@ -35,3 +35,20 @@ s = box.schema.space.create('s',{format=format, temporary=true})
 i = s:create_index('i')
 box.execute('select * from "s"')
 s:drop()
+
+--
+-- gh-4267: Full power of vdbe_field_ref
+--
+format = {}
+t = {}
+test_run:cmd("setopt delimiter ';'")
+for i = 1, 70 do
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
+        t[i] = i
+end
+test_run:cmd("setopt delimiter ''");
+s = box.schema.create_space('TEST', {format = format})
+pk = s:create_index('pk', {parts = {70}})
+s:insert(t)
+box.execute('SELECT field70, field64 FROM test')
+box.space.TEST:drop()
-- 
2.22.0

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

Hi! Thanks for the fixes!

But you missed some places. Consider my fixes on top of the
branch and at the bottom of the email. Also see 2 comments.

>> 13. Why do you consider fieldno >= 64 separately? If it is >= 64,
>> then ((1LLU << fieldno) - 1) is all ones, a full mask. It won't affect
>> slot_bitmask, and you will have the same result without this
>> branching.
> Because type overflow with << operator has undefined behavior.
> This doesn't work in release mode (with optimization flags).

Ok, I missed that, thanks for the check.

> ===============================================
> 
> Vdbe field ref is a dynamic index over tuple fields storing
> offsets to each field and filling the offset array on demand.
> It is highly used in SQL, because it strongly relies on fast and
> repetitive access to any field, not only indexed.
> 
> There is an optimisation for the case when a requested field
> fieldno is indexed, and the tuple itself stores offset to the
> field in its own small field map, used by indexes. vdbe_field_ref
> then uses that map to retrieve offset value without decoding
> anything. But when SQL requests any field > fieldno, then
> vdbe_field_ref decodes the tuple from the beginning in the worst
> case. Even having previously accessed fieldno. But it could
> start decoding from the latter.
> 
> An updated vdbe_field_ref fetcher class uses a bitmask of
> initialized slots to use pre-calculated offsets when possible.
> This speed-ups SQL in some corner case and doesn't damage
> performance in general scenarios.
> 
> Closes #4267
> ---
>  src/box/column_mask.h  |  30 ++++++++++++
>  src/box/sql.h          |   9 ++--
>  src/box/sql.c          |   3 +-
>  src/box/sql/vdbe.c     | 102 +++++++++++++++++++++--------------------
>  test/sql/misc.result   |  46 +++++++++++++++++++
>  test/sql/misc.test.lua |  17 +++++++
>  6 files changed, 153 insertions(+), 54 deletions(-)
> 
> diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
> index e096e1f65..cfb487115 100644
> --- a/src/box/sql/vdbe.c
> +++ b/src/box/sql/vdbe.c
> @@ -606,27 +606,60 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
>  }
>  
>  /**
> - * Try to get a current tuple field using its field map.
> + * Find the closest field for given fieldno in field_ref's
> + * slot_bitmask. The fieldno is expected to be greater than 0.
> + * @param field_ref The vdbe_field_ref instance to use.
> + * @param fieldno Number of a field to find the nearest left
> + *        neighbor of.
> + * @retval >0 An index of the closest smaller fieldno
> + *            initialized in slot_bitmask.
> + */
> +static inline uint32_t
> +vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
> +			      uint32_t fieldno)
> +{
> +	uint64_t slot_bitmask = field_ref->slot_bitmask;
> +	assert(slot_bitmask != 0 && fieldno > 0);
> +	uint64_t le_mask = fieldno < 64 ?
> +			   slot_bitmask & ((1LLU << fieldno) - 1) : slot_bitmask;
> +	assert(bit_clz_u64(le_mask) < 64);
> +	return 64 - bit_clz_u64(le_mask) - 1;
> +}
> +
> +/**
> + * Get a tuple's field using field_ref's slot_bitmask, and tuple's
> + * field_map when possible. Required field must be present in
> + * tuple.
>   * @param field_ref The vdbe_field_ref instance to use.
>   * @param fieldno Number of a field to get.
> - * @param[out] field_size Result field size.
>   * @retval not NULL MessagePack field.
> - * @retval NULL Can not use field_map - it does not contain
> - *              offset to @a fieldno.
>   */
> -static const void *
> -vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
> -			  uint32_t *field_size)
> +static const char *
> +vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
>  {
> -	const struct tuple_field *tf =
> -		vdbe_field_ref_fetch_field(field_ref, fieldno);
> -	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
> -		return NULL;
> -	const char *field = tuple_field(field_ref->tuple, fieldno);
> -	const char *end = field;
> -	mp_next(&end);
> -	*field_size = end - field;
> -	return field;
> +	if (bitmask64_bit_is_set(field_ref->slot_bitmask, fieldno))
> +		return field_ref->data + field_ref->slots[fieldno];
> +
> +	const char *field_begin;
> +	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
> +								     fieldno);
> +	if (field != NULL && field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
> +		field_begin = tuple_field(field_ref->tuple, fieldno);
> +	} else {
> +		uint32_t prev = vdbe_field_ref_closest_slotno(field_ref,
> +							      fieldno);
> +		field_begin = field_ref->data + field_ref->slots[prev];
> +		for (prev++; prev < fieldno; prev++) {
> +			mp_next(&field_begin);

1. Now there is a new problem. If a field is > 64, but there are filled
slots >= 64 and < the requested field, we still decode all the fields
from 64. Even if the field was accessed earlier and has a slot.

In the 'if' above:

    if (bitmask64_bit_is_set(field_ref->slot_bitmask, fieldno))
        return field_ref->data + field_ref->slots[fieldno];

We miss fields, which actually has slot, but >= 64.

We could solve that by
1) Filling slot array with an invalid value. For example, 0.
2) In the 'if' above we check, that if a slot (not bit, but the slot)
is not 0, then it was filled earlier and can be used. It will work
for all fields, even >= 64.
3) Otherwise for < 64 we check slot bitmask of the left neighbour.
For >= 64 we get index of the biggest bit in the mask and scan all
left neighbour slots of the requested field until find non-empty, or
stumble into the max index of the mask.

What do you think?

> +			field_ref->slots[prev] =
> +				(uint32_t)(field_begin - field_ref->data);
> +			bitmask64_set_bit(&field_ref->slot_bitmask, prev);
> +		}
> +		mp_next(&field_begin);
> +	}
> +	field_ref->slots[fieldno] = (uint32_t)(field_begin - field_ref->data);
> +	bitmask64_set_bit(&field_ref->slot_bitmask, fieldno);
> +	return field_begin;
>  }
>  
>  static inline enum field_type
> @@ -652,45 +685,13 @@ static int
> diff --git a/test/sql/misc.result b/test/sql/misc.result
> index 2591d9d75..f2357c122 100644
> --- a/test/sql/misc.result
> +++ b/test/sql/misc.result
> @@ -133,3 +133,49 @@ box.execute('select * from "s"')
>  s:drop()
>  ---
>  ...
> +--
> +-- gh-4267: Full power of vdbe_field_ref

2. It would be great to have here a short description of what
are we testing here.

> +--
> +format = {}
> +---
> +...
> +t = {}
> +---
> +...
> +test_run:cmd("setopt delimiter ';'")
> +---
> +- true
> +...
> +for i = 1, 70 do
> +        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
> +        t[i] = i
> +end
> +test_run:cmd("setopt delimiter ''");
> +---
> +...
> +s = box.schema.create_space('TEST', {format = format})
> +---
> +...
> +pk = s:create_index('pk', {parts = {70}})
> +---
> +...
> +s:insert(t)
> +---
> +- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
> +  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
> +  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
> +  63, 64, 65, 66, 67, 68, 69, 70]
> +...
> +box.execute('SELECT field70, field64 FROM test')
> +---
> +- metadata:
> +  - name: FIELD70
> +    type: unsigned
> +  - name: FIELD64
> +    type: unsigned
> +  rows:
> +  - [70, 64]
> +...
> +box.space.TEST:drop()
> +---
> +...
================================================================================

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index 0518fa6c3..5fb0e1fe0 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -138,15 +138,15 @@ bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
 }
 
 /**
- * Test a bit in the bitmask corresponding to a bitno..
+ * Test a bit in the bitmask corresponding to @a bitno.
  * @param bitmask Bitmask to test.
- * @param bitno bit number to test (must be 0-based).
+ * @param bitno Bit number to test (must be 0-based).
  * @return Whether given bit is set in a given bitmask.
  *         When bitno is greater than size of bitmask returns
  *         false.
  */
 static inline bool
-bitmask64_bit_is_set(uint64_t bitmask, uint32_t bitno)
+bitmask64_is_bit_set(uint64_t bitmask, uint32_t bitno)
 {
 	if (bitno >= 64)
 		return false;
diff --git a/src/box/sql.h b/src/box/sql.h
index 08fe5c7af..7644051b4 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -375,8 +375,8 @@ struct vdbe_field_ref {
 	 * Bitmask of initialized slots. The fieldno == 0 slot
 	 * must be initialized in vdbe_field_ref constructor.
 	 * This bitmap allows to lookup for the nearest
-	 * initialized slot for a given fieldno to perform a few
-	 * extra tuple decoding, as possible.
+	 * initialized slot for a given fieldno to perform as few
+	 * extra tuple decoding as possible.
 	 */
 	uint64_t slot_bitmask;
 	/**
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index cfb487115..327dc699a 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -606,7 +606,7 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 }
 
 /**
- * Find the closest field for given fieldno in field_ref's
+ * Find the left closest field for a given fieldno in field_ref's
  * slot_bitmask. The fieldno is expected to be greater than 0.
  * @param field_ref The vdbe_field_ref instance to use.
  * @param fieldno Number of a field to find the nearest left
@@ -620,8 +620,8 @@ vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
 {
 	uint64_t slot_bitmask = field_ref->slot_bitmask;
 	assert(slot_bitmask != 0 && fieldno > 0);
-	uint64_t le_mask = fieldno < 64 ?
-			   slot_bitmask & ((1LLU << fieldno) - 1) : slot_bitmask;
+	uint64_t le_mask = fieldno < 64 ? slot_bitmask & ((1LLU << fieldno) - 1)
+			   : slot_bitmask;
 	assert(bit_clz_u64(le_mask) < 64);
 	return 64 - bit_clz_u64(le_mask) - 1;
 }
@@ -637,7 +637,7 @@ vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
 static const char *
 vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 {
-	if (bitmask64_bit_is_set(field_ref->slot_bitmask, fieldno))
+	if (bitmask64_is_bit_set(field_ref->slot_bitmask, fieldno))
 		return field_ref->data + field_ref->slots[fieldno];
 
 	const char *field_begin;

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

> Hi! Thanks for the fixes!
Hi! Thank you for your contribution. Squashed your changes.

> 1. Now there is a new problem. If a field is > 64, but there are filled
> slots >= 64 and < the requested field, we still decode all the fields
> from 64. Even if the field was accessed earlier and has a slot.
> 
> In the 'if' above:
> 
>     if (bitmask64_bit_is_set(field_ref->slot_bitmask, fieldno))
>         return field_ref->data + field_ref->slots[fieldno];
> 
> We miss fields, which actually has slot, but >= 64.
> 
> We could solve that by
> 1) Filling slot array with an invalid value. For example, 0.
> 2) In the 'if' above we check, that if a slot (not bit, but the slot)
> is not 0, then it was filled earlier and can be used. It will work
> for all fields, even >= 64.
> 3) Otherwise for < 64 we check slot bitmask of the left neighbour.
> For >= 64 we get index of the biggest bit in the mask and scan all
> left neighbour slots of the requested field until find non-empty, or
> stumble into the max index of the mask.
> 
> What do you think?

Sounds good. I've implemented this feature.

>> +--
>> +-- gh-4267: Full power of vdbe_field_ref
> 
> 2. It would be great to have here a short description of what
> are we testing here.
Done.

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

From 87e383a01abc6bf63e88dee22a18d1a08aac414e Mon Sep 17 00:00:00 2001
Message-Id: <87e383a01abc6bf63e88dee22a18d1a08aac414e.1565857939.git.kshcherbatov@tarantool.org>
From: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Date: Mon, 12 Aug 2019 16:14:55 +0300
Subject: [PATCH v2 1/1] sql: improve vdbe_field_ref fetcher

Vdbe field ref is a dynamic index over tuple fields storing
offsets to each field and filling the offset array on demand.
It is highly used in SQL, because it strongly relies on fast and
repetitive access to any field, not only indexed.

There is an optimisation for the case when a requested field
fieldno is indexed, and the tuple itself stores offset to the
field in its own small field map, used by indexes. vdbe_field_ref
then uses that map to retrieve offset value without decoding
anything. But when SQL requests any field > fieldno, then
vdbe_field_ref decodes the tuple from the beginning in the worst
case. Even having previously accessed fieldno. But it could
start decoding from the latter.

An updated vdbe_field_ref fetcher class uses a bitmask of
initialized slots to use pre-calculated offsets when possible.
This speed-ups SQL in some corner case and doesn't damage
performance in general scenarios.

Closes #4267
---
 src/box/column_mask.h  |  30 +++++++++++
 src/box/sql.h          |   9 ++--
 src/box/sql.c          |   5 +-
 src/box/sql/vdbe.c     | 116 +++++++++++++++++++++++------------------
 test/sql/misc.result   |  53 +++++++++++++++++++
 test/sql/misc.test.lua |  22 ++++++++
 6 files changed, 181 insertions(+), 54 deletions(-)

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index 14da841f1..5fb0e1fe0 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -123,4 +123,34 @@ column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
 	return (column_mask & mask) != 0;
 }
 
+/**
+ * Set a bit with given index @a bitno in a given @a bitmask.
+ * Do nothing when @a bitno is greater than size if bitmask.
+ * @param bitmask Bitmask to test.
+ * @param bitno bit number to test (must be 0-based).
+ */
+static inline void
+bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return;
+	*bitmask |= ((uint64_t)1 << bitno);
+}
+
+/**
+ * Test a bit in the bitmask corresponding to @a bitno.
+ * @param bitmask Bitmask to test.
+ * @param bitno Bit number to test (must be 0-based).
+ * @return Whether given bit is set in a given bitmask.
+ *         When bitno is greater than size of bitmask returns
+ *         false.
+ */
+static inline bool
+bitmask64_is_bit_set(uint64_t bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return false;
+	return (bitmask & ((uint64_t)1 << bitno)) != 0;
+}
+
 #endif
diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..7644051b4 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -372,10 +372,13 @@ struct vdbe_field_ref {
 	/** Count of fields in tuple. */
 	uint32_t field_count;
 	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
+	 * Bitmask of initialized slots. The fieldno == 0 slot
+	 * must be initialized in vdbe_field_ref constructor.
+	 * This bitmap allows to lookup for the nearest
+	 * initialized slot for a given fieldno to perform as few
+	 * extra tuple decoding as possible.
 	 */
-	uint32_t rightmost_slot;
+	uint64_t slot_bitmask;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
diff --git a/src/box/sql.c b/src/box/sql.c
index 0ab3a506f..f1df55571 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1245,7 +1245,10 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	memset(&field_ref->slots[1], 0,
+	       field_ref->field_count * sizeof(field_ref->slots[0]));
+	field_ref->slot_bitmask = 0;
+	bitmask64_set_bit(&field_ref->slot_bitmask, 0);
 }
 
 void
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index e096e1f65..21b585364 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -606,27 +606,74 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 }
 
 /**
- * Try to get a current tuple field using its field map.
+ * Find the left closest field for a given fieldno in field_ref's
+ * slot_bitmask. The fieldno is expected to be greater than 0.
+ * @param field_ref The vdbe_field_ref instance to use.
+ * @param fieldno Number of a field to find the nearest left
+ *        neighbor of.
+ * @retval >0 An index of the closest smaller fieldno
+ *            initialized in slot_bitmask.
+ */
+static inline uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint64_t slot_bitmask = field_ref->slot_bitmask;
+	assert(slot_bitmask != 0 && fieldno > 0);
+	uint64_t le_mask = fieldno < 64 ? slot_bitmask & ((1LLU << fieldno) - 1)
+			   : slot_bitmask;
+	assert(bit_clz_u64(le_mask) < 64);
+	return 64 - bit_clz_u64(le_mask) - 1;
+}
+
+/**
+ * Get a tuple's field using field_ref's slot_bitmask, and tuple's
+ * field_map when possible. Required field must be present in
+ * tuple.
  * @param field_ref The vdbe_field_ref instance to use.
  * @param fieldno Number of a field to get.
- * @param[out] field_size Result field size.
  * @retval not NULL MessagePack field.
- * @retval NULL Can not use field_map - it does not contain
- *              offset to @a fieldno.
  */
-static const void *
-vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
-			  uint32_t *field_size)
+static const char *
+vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 {
-	const struct tuple_field *tf =
-		vdbe_field_ref_fetch_field(field_ref, fieldno);
-	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	if (field_ref->slots[fieldno] != 0)
+		return field_ref->data + field_ref->slots[fieldno];
+
+	const char *field_begin;
+	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
+								     fieldno);
+	if (field != NULL && field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+		field_begin = tuple_field(field_ref->tuple, fieldno);
+	} else {
+		uint32_t prev = vdbe_field_ref_closest_slotno(field_ref,
+							      fieldno);;
+		if (fieldno >= 64) {
+			/*
+			 * There could be initialized slots
+			 * that didn't fit in the bitmask.
+			 * Try to find the biggest initialized
+			 * slot.
+			 */
+			for (uint32_t it = fieldno - 1; it > prev; it--) {
+				if (field_ref->slots[it] == 0)
+					continue;
+				prev = it;
+				break;
+			}
+		}
+		field_begin = field_ref->data + field_ref->slots[prev];
+		for (prev++; prev < fieldno; prev++) {
+			mp_next(&field_begin);
+			field_ref->slots[prev] =
+				(uint32_t)(field_begin - field_ref->data);
+			bitmask64_set_bit(&field_ref->slot_bitmask, prev);
+		}
+		mp_next(&field_begin);
+	}
+	field_ref->slots[fieldno] = (uint32_t)(field_begin - field_ref->data);
+	bitmask64_set_bit(&field_ref->slot_bitmask, fieldno);
+	return field_begin;
 }
 
 static inline enum field_type
@@ -652,45 +699,13 @@ static int
 vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		     struct Mem *dest_mem)
 {
-	uint32_t *slots = field_ref->slots;
 	if (fieldno >= field_ref->field_count) {
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
+	const char *data = vdbe_field_ref_fetch_data(field_ref, fieldno);
 	uint32_t dummy;
-	data = field_ref->data + slots[fieldno];
 	if (vdbe_decode_msgpack_into_mem(data, dest_mem, &dummy) != 0)
 		return -1;
 
@@ -699,8 +714,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 	 * Wrap it in a blob verbatim.
 	 */
 	if (dest_mem->flags == 0) {
-		dest_mem->n = slots[fieldno + 1] - slots[fieldno];
 		dest_mem->z = (char *) data;
+		dest_mem->n = vdbe_field_ref_fetch_data(field_ref,
+							fieldno + 1) - data;
 		dest_mem->flags = MEM_Blob | MEM_Ephem | MEM_Subtype;
 		dest_mem->subtype = SQL_SUBTYPE_MSGPACK;
 	}
diff --git a/test/sql/misc.result b/test/sql/misc.result
index 2591d9d75..7d183d3a0 100644
--- a/test/sql/misc.result
+++ b/test/sql/misc.result
@@ -133,3 +133,56 @@ box.execute('select * from "s"')
 s:drop()
 ---
 ...
+--
+-- gh-4267: Full power of vdbe_field_ref
+-- The test consists of sequential reads of multiple fields:
+-- the first is indexed while the other are not indexed.
+-- In skope of this issue an optimization that makes second and
+-- third lookups faster were introduced. Test that they works
+-- correctly.
+--
+format = {}
+---
+...
+t = {}
+---
+...
+test_run:cmd("setopt delimiter ';'")
+---
+- true
+...
+for i = 1, 70 do
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
+        t[i] = i
+end
+test_run:cmd("setopt delimiter ''");
+---
+...
+s = box.schema.create_space('TEST', {format = format})
+---
+...
+pk = s:create_index('pk', {parts = {66}})
+---
+...
+s:insert(t)
+---
+- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
+  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
+  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
+  63, 64, 65, 66, 67, 68, 69, 70]
+...
+box.execute('SELECT field66, field68, field70 FROM test')
+---
+- metadata:
+  - name: FIELD66
+    type: unsigned
+  - name: FIELD68
+    type: unsigned
+  - name: FIELD70
+    type: unsigned
+  rows:
+  - [66, 68, 70]
+...
+box.space.TEST:drop()
+---
+...
diff --git a/test/sql/misc.test.lua b/test/sql/misc.test.lua
index fdc19f3ac..afbb2d7f8 100644
--- a/test/sql/misc.test.lua
+++ b/test/sql/misc.test.lua
@@ -35,3 +35,25 @@ s = box.schema.space.create('s',{format=format, temporary=true})
 i = s:create_index('i')
 box.execute('select * from "s"')
 s:drop()
+
+--
+-- gh-4267: Full power of vdbe_field_ref
+-- The test consists of sequential reads of multiple fields:
+-- the first is indexed while the other are not indexed.
+-- In skope of this issue an optimization that makes second and
+-- third lookups faster were introduced. Test that they works
+-- correctly.
+--
+format = {}
+t = {}
+test_run:cmd("setopt delimiter ';'")
+for i = 1, 70 do
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
+        t[i] = i
+end
+test_run:cmd("setopt delimiter ''");
+s = box.schema.create_space('TEST', {format = format})
+pk = s:create_index('pk', {parts = {66}})
+s:insert(t)
+box.execute('SELECT field66, field68, field70 FROM test')
+box.space.TEST:drop()
-- 
2.22.1

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

Hi! Thanks for the fixes.

See 2 comments below.

> diff --git a/test/sql/misc.test.lua b/test/sql/misc.test.lua
> index fdc19f3ac..afbb2d7f8 100644
> --- a/test/sql/misc.test.lua
> +++ b/test/sql/misc.test.lua
> @@ -35,3 +35,25 @@ s = box.schema.space.create('s',{format=format, temporary=true})
>  i = s:create_index('i')
>  box.execute('select * from "s"')
>  s:drop()
> +
> +--
> +-- gh-4267: Full power of vdbe_field_ref
> +-- The test consists of sequential reads of multiple fields:
> +-- the first is indexed while the other are not indexed.
> +-- In skope of this issue an optimization that makes second and

1. 'scope'.

> +-- third lookups faster were introduced. Test that they works
> +-- correctly.

2. This is not an explanation, but rather a bit of water. With
the same explanation you could test fields 1 and 2. Please, explain
why exactly these numbers.

Also you somewhy dropped the previous test on the border case about
a field < 64 and >= 64 in one request. Why? The test below does not
cover it.

> +--
> +format = {}
> +t = {}
> +test_run:cmd("setopt delimiter ';'")
> +for i = 1, 70 do
> +        format[i] = {name = 'FIELD'..i, type = 'unsigned'}
> +        t[i] = i
> +end
> +test_run:cmd("setopt delimiter ''");

For such a small piece of code you could use '\' instead of
setopt delimiter. IMO \ looks much better. Up to you.

> +s = box.schema.create_space('TEST', {format = format})
> +pk = s:create_index('pk', {parts = {66}})
> +s:insert(t)
> +box.execute('SELECT field66, field68, field70 FROM test')
> +box.space.TEST:drop()
> 

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

> 1. 'scope'.
> 2. This is not an explanation, but rather a bit of water. With
> the same explanation you could test fields 1 and 2. Please, explain
> why exactly these numbers.
Got it.
================================================

Vdbe field ref is a dynamic index over tuple fields storing
offsets to each field and filling the offset array on demand.
It is highly used in SQL, because it strongly relies on fast and
repetitive access to any field, not only indexed.

There is an optimisation for the case when a requested field
fieldno is indexed, and the tuple itself stores offset to the
field in its own small field map, used by indexes. vdbe_field_ref
then uses that map to retrieve offset value without decoding
anything. But when SQL requests any field > fieldno, then
vdbe_field_ref decodes the tuple from the beginning in the worst
case. Even having previously accessed fieldno. But it could
start decoding from the latter.

An updated vdbe_field_ref fetcher class uses a bitmask of
initialized slots to use pre-calculated offsets when possible.
This speed-ups SQL in some corner case and doesn't damage
performance in general scenarios.

Closes #4267
---
 src/box/column_mask.h  |  30 +++++++++++
 src/box/sql.h          |   9 ++--
 src/box/sql.c          |   5 +-
 src/box/sql/vdbe.c     | 116 +++++++++++++++++++++++------------------
 test/sql/misc.result   |  92 ++++++++++++++++++++++++++++++++
 test/sql/misc.test.lua |  38 ++++++++++++++
 6 files changed, 236 insertions(+), 54 deletions(-)

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index 14da841f1..5fb0e1fe0 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -123,4 +123,34 @@ column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
 	return (column_mask & mask) != 0;
 }
 
+/**
+ * Set a bit with given index @a bitno in a given @a bitmask.
+ * Do nothing when @a bitno is greater than size if bitmask.
+ * @param bitmask Bitmask to test.
+ * @param bitno bit number to test (must be 0-based).
+ */
+static inline void
+bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return;
+	*bitmask |= ((uint64_t)1 << bitno);
+}
+
+/**
+ * Test a bit in the bitmask corresponding to @a bitno.
+ * @param bitmask Bitmask to test.
+ * @param bitno Bit number to test (must be 0-based).
+ * @return Whether given bit is set in a given bitmask.
+ *         When bitno is greater than size of bitmask returns
+ *         false.
+ */
+static inline bool
+bitmask64_is_bit_set(uint64_t bitmask, uint32_t bitno)
+{
+	if (bitno >= 64)
+		return false;
+	return (bitmask & ((uint64_t)1 << bitno)) != 0;
+}
+
 #endif
diff --git a/src/box/sql.h b/src/box/sql.h
index 9ccecf28c..7644051b4 100644
--- a/src/box/sql.h
+++ b/src/box/sql.h
@@ -372,10 +372,13 @@ struct vdbe_field_ref {
 	/** Count of fields in tuple. */
 	uint32_t field_count;
 	/**
-	 * Index of the rightmost initialized slot in slots
-	 * array.
+	 * Bitmask of initialized slots. The fieldno == 0 slot
+	 * must be initialized in vdbe_field_ref constructor.
+	 * This bitmap allows to lookup for the nearest
+	 * initialized slot for a given fieldno to perform as few
+	 * extra tuple decoding as possible.
 	 */
-	uint32_t rightmost_slot;
+	uint64_t slot_bitmask;
 	/**
 	 * Array of offsets of tuple fields.
 	 * Only values <= rightmost_slot are valid.
diff --git a/src/box/sql.c b/src/box/sql.c
index 0ab3a506f..f1df55571 100644
--- a/src/box/sql.c
+++ b/src/box/sql.c
@@ -1245,7 +1245,10 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
 	const char *field0 = data;
 	field_ref->field_count = mp_decode_array((const char **) &field0);
 	field_ref->slots[0] = (uint32_t)(field0 - data);
-	field_ref->rightmost_slot = 0;
+	memset(&field_ref->slots[1], 0,
+	       field_ref->field_count * sizeof(field_ref->slots[0]));
+	field_ref->slot_bitmask = 0;
+	bitmask64_set_bit(&field_ref->slot_bitmask, 0);
 }
 
 void
diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
index e096e1f65..21b585364 100644
--- a/src/box/sql/vdbe.c
+++ b/src/box/sql/vdbe.c
@@ -606,27 +606,74 @@ vdbe_field_ref_fetch_field(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 }
 
 /**
- * Try to get a current tuple field using its field map.
+ * Find the left closest field for a given fieldno in field_ref's
+ * slot_bitmask. The fieldno is expected to be greater than 0.
+ * @param field_ref The vdbe_field_ref instance to use.
+ * @param fieldno Number of a field to find the nearest left
+ *        neighbor of.
+ * @retval >0 An index of the closest smaller fieldno
+ *            initialized in slot_bitmask.
+ */
+static inline uint32_t
+vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
+			      uint32_t fieldno)
+{
+	uint64_t slot_bitmask = field_ref->slot_bitmask;
+	assert(slot_bitmask != 0 && fieldno > 0);
+	uint64_t le_mask = fieldno < 64 ? slot_bitmask & ((1LLU << fieldno) - 1)
+			   : slot_bitmask;
+	assert(bit_clz_u64(le_mask) < 64);
+	return 64 - bit_clz_u64(le_mask) - 1;
+}
+
+/**
+ * Get a tuple's field using field_ref's slot_bitmask, and tuple's
+ * field_map when possible. Required field must be present in
+ * tuple.
  * @param field_ref The vdbe_field_ref instance to use.
  * @param fieldno Number of a field to get.
- * @param[out] field_size Result field size.
  * @retval not NULL MessagePack field.
- * @retval NULL Can not use field_map - it does not contain
- *              offset to @a fieldno.
  */
-static const void *
-vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
-			  uint32_t *field_size)
+static const char *
+vdbe_field_ref_fetch_data(struct vdbe_field_ref *field_ref, uint32_t fieldno)
 {
-	const struct tuple_field *tf =
-		vdbe_field_ref_fetch_field(field_ref, fieldno);
-	if (tf == NULL || tf->offset_slot == TUPLE_OFFSET_SLOT_NIL)
-		return NULL;
-	const char *field = tuple_field(field_ref->tuple, fieldno);
-	const char *end = field;
-	mp_next(&end);
-	*field_size = end - field;
-	return field;
+	if (field_ref->slots[fieldno] != 0)
+		return field_ref->data + field_ref->slots[fieldno];
+
+	const char *field_begin;
+	const struct tuple_field *field = vdbe_field_ref_fetch_field(field_ref,
+								     fieldno);
+	if (field != NULL && field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
+		field_begin = tuple_field(field_ref->tuple, fieldno);
+	} else {
+		uint32_t prev = vdbe_field_ref_closest_slotno(field_ref,
+							      fieldno);;
+		if (fieldno >= 64) {
+			/*
+			 * There could be initialized slots
+			 * that didn't fit in the bitmask.
+			 * Try to find the biggest initialized
+			 * slot.
+			 */
+			for (uint32_t it = fieldno - 1; it > prev; it--) {
+				if (field_ref->slots[it] == 0)
+					continue;
+				prev = it;
+				break;
+			}
+		}
+		field_begin = field_ref->data + field_ref->slots[prev];
+		for (prev++; prev < fieldno; prev++) {
+			mp_next(&field_begin);
+			field_ref->slots[prev] =
+				(uint32_t)(field_begin - field_ref->data);
+			bitmask64_set_bit(&field_ref->slot_bitmask, prev);
+		}
+		mp_next(&field_begin);
+	}
+	field_ref->slots[fieldno] = (uint32_t)(field_begin - field_ref->data);
+	bitmask64_set_bit(&field_ref->slot_bitmask, fieldno);
+	return field_begin;
 }
 
 static inline enum field_type
@@ -652,45 +699,13 @@ static int
 vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 		     struct Mem *dest_mem)
 {
-	uint32_t *slots = field_ref->slots;
 	if (fieldno >= field_ref->field_count) {
 		UPDATE_MAX_BLOBSIZE(dest_mem);
 		return 0;
 	}
-
-	const char *data;
-	if (field_ref->rightmost_slot <= fieldno) {
-		uint32_t field_sz;
-		data = vdbe_field_ref_fast_fetch(field_ref, fieldno,
-						 &field_sz);
-		if (data != NULL) {
-			/*
-			 * Special case for tarantool spaces: for
-			 * indexed fields a tuple field map can be
-			 * used. Else there is no sense in
-			 * tuple_field usage, because it makes
-			 * foreach field { mp_next(); } to find
-			 * a field. In such a case sql is
-			 * better - it saves offsets to all fields
-			 * visited in mp_next() cycle.
-			 */
-			uint32_t offset = (uint32_t)(data - field_ref->data);
-			slots[fieldno] = offset;
-			slots[fieldno + 1] = offset + field_sz;
-		} else {
-			uint32_t i = field_ref->rightmost_slot;
-			data = field_ref->data + slots[i];
-			do {
-				mp_next(&data);
-				slots[++i] = (uint32_t)(data - field_ref->data);
-			} while (i <= fieldno);
-			field_ref->rightmost_slot = i;
-		}
-	}
-
 	assert(sqlVdbeCheckMemInvariants(dest_mem) != 0);
+	const char *data = vdbe_field_ref_fetch_data(field_ref, fieldno);
 	uint32_t dummy;
-	data = field_ref->data + slots[fieldno];
 	if (vdbe_decode_msgpack_into_mem(data, dest_mem, &dummy) != 0)
 		return -1;
 
@@ -699,8 +714,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
 	 * Wrap it in a blob verbatim.
 	 */
 	if (dest_mem->flags == 0) {
-		dest_mem->n = slots[fieldno + 1] - slots[fieldno];
 		dest_mem->z = (char *) data;
+		dest_mem->n = vdbe_field_ref_fetch_data(field_ref,
+							fieldno + 1) - data;
 		dest_mem->flags = MEM_Blob | MEM_Ephem | MEM_Subtype;
 		dest_mem->subtype = SQL_SUBTYPE_MSGPACK;
 	}
diff --git a/test/sql/misc.result b/test/sql/misc.result
index 2591d9d75..545be15f6 100644
--- a/test/sql/misc.result
+++ b/test/sql/misc.result
@@ -133,3 +133,95 @@ box.execute('select * from "s"')
 s:drop()
 ---
 ...
+--
+-- gh-4267: Full power of vdbe_field_ref
+-- Tarantool's SQL internally stores data offset for all acceded
+-- fields. It also keeps a bitmask of size 64 with all initialized
+-- slots in actual state to find the nearest left field really
+-- fast and parse tuple from that position. For fieldno >= 64
+-- bitmask is not applicable, so it scans data offsets area in
+-- a cycle.
+--
+-- The test below covers a case when this optimisation doesn't
+-- work and the second lookup require parsing tuple from
+-- beginning.
+---
+format = {}
+---
+...
+t = {}
+---
+...
+for i = 1, 70 do                                                \
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
+        t[i] = i                                                \
+end
+---
+...
+s = box.schema.create_space('TEST', {format = format})
+---
+...
+pk = s:create_index('pk', {parts = {70}})
+---
+...
+s:insert(t)
+---
+- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
+  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
+  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
+  63, 64, 65, 66, 67, 68, 69, 70]
+...
+box.execute('SELECT field70, field64 FROM test')
+---
+- metadata:
+  - name: FIELD70
+    type: unsigned
+  - name: FIELD64
+    type: unsigned
+  rows:
+  - [70, 64]
+...
+box.space.TEST:drop()
+---
+...
+-- In the case below described optimization works fine.
+format = {}
+---
+...
+t = {}
+---
+...
+for i = 1, 70 do                                                \
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
+        t[i] = i                                                \
+end
+---
+...
+s = box.schema.create_space('TEST', {format = format})
+---
+...
+pk = s:create_index('pk', {parts = {66}})
+---
+...
+s:insert(t)
+---
+- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
+  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
+  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
+  63, 64, 65, 66, 67, 68, 69, 70]
+...
+box.execute('SELECT field66, field68, field70 FROM test')
+---
+- metadata:
+  - name: FIELD66
+    type: unsigned
+  - name: FIELD68
+    type: unsigned
+  - name: FIELD70
+    type: unsigned
+  rows:
+  - [66, 68, 70]
+...
+box.space.TEST:drop()
+---
+...
diff --git a/test/sql/misc.test.lua b/test/sql/misc.test.lua
index fdc19f3ac..8067be213 100644
--- a/test/sql/misc.test.lua
+++ b/test/sql/misc.test.lua
@@ -35,3 +35,41 @@ s = box.schema.space.create('s',{format=format, temporary=true})
 i = s:create_index('i')
 box.execute('select * from "s"')
 s:drop()
+
+--
+-- gh-4267: Full power of vdbe_field_ref
+-- Tarantool's SQL internally stores data offset for all acceded
+-- fields. It also keeps a bitmask of size 64 with all initialized
+-- slots in actual state to find the nearest left field really
+-- fast and parse tuple from that position. For fieldno >= 64
+-- bitmask is not applicable, so it scans data offsets area in
+-- a cycle.
+--
+-- The test below covers a case when this optimisation doesn't
+-- work and the second lookup require parsing tuple from
+-- beginning.
+---
+format = {}
+t = {}
+for i = 1, 70 do                                                \
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
+        t[i] = i                                                \
+end
+s = box.schema.create_space('TEST', {format = format})
+pk = s:create_index('pk', {parts = {70}})
+s:insert(t)
+box.execute('SELECT field70, field64 FROM test')
+box.space.TEST:drop()
+
+-- In the case below described optimization works fine.
+format = {}
+t = {}
+for i = 1, 70 do                                                \
+        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
+        t[i] = i                                                \
+end
+s = box.schema.create_space('TEST', {format = format})
+pk = s:create_index('pk', {parts = {66}})
+s:insert(t)
+box.execute('SELECT field66, field68, field70 FROM test')
+box.space.TEST:drop()
-- 
2.22.1

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

Hi! Thanks for the fixes. Mine are on the branch in
a separate commit and below. Squash them please, if they
are ok.

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

diff --git a/src/box/column_mask.h b/src/box/column_mask.h
index 5fb0e1fe0..9470fe19c 100644
--- a/src/box/column_mask.h
+++ b/src/box/column_mask.h
@@ -125,16 +125,15 @@ column_mask_fieldno_is_set(uint64_t column_mask, uint32_t fieldno)
 
 /**
  * Set a bit with given index @a bitno in a given @a bitmask.
- * Do nothing when @a bitno is greater than size if bitmask.
+ * Do nothing when @a bitno is greater than size of bitmask.
  * @param bitmask Bitmask to test.
- * @param bitno bit number to test (must be 0-based).
+ * @param bitno Bit number to test (must be 0-based).
  */
 static inline void
 bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
 {
-	if (bitno >= 64)
-		return;
-	*bitmask |= ((uint64_t)1 << bitno);
+	if (bitno < 64)
+		*bitmask |= ((uint64_t)1 << bitno);
 }
 
 /**
@@ -148,9 +147,7 @@ bitmask64_set_bit(uint64_t *bitmask, uint32_t bitno)
 static inline bool
 bitmask64_is_bit_set(uint64_t bitmask, uint32_t bitno)
 {
-	if (bitno >= 64)
-		return false;
-	return (bitmask & ((uint64_t)1 << bitno)) != 0;
+	return bitno < 64 && (bitmask & ((uint64_t)1 << bitno)) != 0;
 }
 
 #endif
diff --git a/test/sql/misc.result b/test/sql/misc.result
index 545be15f6..a157ddbc1 100644
--- a/test/sql/misc.result
+++ b/test/sql/misc.result
@@ -181,35 +181,10 @@ box.execute('SELECT field70, field64 FROM test')
   rows:
   - [70, 64]
 ...
-box.space.TEST:drop()
----
-...
 -- In the case below described optimization works fine.
-format = {}
----
-...
-t = {}
----
-...
-for i = 1, 70 do                                                \
-        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
-        t[i] = i                                                \
-end
+pk:alter({parts = {66}})
 ---
 ...
-s = box.schema.create_space('TEST', {format = format})
----
-...
-pk = s:create_index('pk', {parts = {66}})
----
-...
-s:insert(t)
----
-- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
-  23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
-  43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62,
-  63, 64, 65, 66, 67, 68, 69, 70]
-...
 box.execute('SELECT field66, field68, field70 FROM test')
 ---
 - metadata:
diff --git a/test/sql/misc.test.lua b/test/sql/misc.test.lua
index 8067be213..541660c61 100644
--- a/test/sql/misc.test.lua
+++ b/test/sql/misc.test.lua
@@ -59,17 +59,8 @@ s = box.schema.create_space('TEST', {format = format})
 pk = s:create_index('pk', {parts = {70}})
 s:insert(t)
 box.execute('SELECT field70, field64 FROM test')
-box.space.TEST:drop()
 
 -- In the case below described optimization works fine.
-format = {}
-t = {}
-for i = 1, 70 do                                                \
-        format[i] = {name = 'FIELD'..i, type = 'unsigned'}      \
-        t[i] = i                                                \
-end
-s = box.schema.create_space('TEST', {format = format})
-pk = s:create_index('pk', {parts = {66}})
-s:insert(t)
+pk:alter({parts = {66}})
 box.execute('SELECT field66, field68, field70 FROM test')
 box.space.TEST:drop()

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Shcherbatov]

They are ok, tnx! Ready to push.

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

LGTM.

On 19/08/2019 22:27, Kirill Shcherbatov wrote:
> They are ok, tnx! Ready to push.
> 

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[n.pettik]

> On 19 Aug 2019, at 23:27, Kirill Shcherbatov <kshcherbatov@tarantool.org> wrote:
> 
> They are ok, tnx! Ready to push.

Did you measure performance gain? Is there any improvement at all?

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy]

On 20/08/2019 11:07, n.pettik wrote:
> 
> 
>> On 19 Aug 2019, at 23:27, Kirill Shcherbatov <kshcherbatov@tarantool.org> wrote:
>>
>> They are ok, tnx! Ready to push.
> 
> Did you measure performance gain? Is there any improvement at all?
> 

Yes, please, look at the previous responses.

[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Kirill Yukhin]

Hello,

On 22 Jul 10:43, Kirill Shcherbatov wrote:
> An updated vdbe_field_ref fetcher class use a bitmap of
> initialized slots to use pre-calculated offsets when possible.
> This should speed-up SQL a bit.
> 
> Closes #4267
> ---
> Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
> Issue: https://github.com/tarantool/tarantool/issues/4267

Patch was checked into master.

--
Regards, Kirill Yukhin