[tarantool-patches] [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher
Kirill Shcherbatov
kshcherbatov at tarantool.org
Mon Jul 22 10:43:32 MSK 2019
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
More information about the Tarantool-patches
mailing list