[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).