[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Wed Aug 14 23:18:02 MSK 2019
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;
More information about the Tarantool-patches
mailing list