From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id 96CD322681 for ; Wed, 14 Aug 2019 16:15:20 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xgnRUY_qjzQ8 for ; Wed, 14 Aug 2019 16:15:20 -0400 (EDT) Received: from smtp52.i.mail.ru (smtp52.i.mail.ru [94.100.177.112]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id D8FBF21BAA for ; Wed, 14 Aug 2019 16:15:19 -0400 (EDT) Subject: [tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher References: <978c68684414e4df06fa7b37697c3f348d96cf5b.1563781318.git.kshcherbatov@tarantool.org> <967599c4-0e10-8cdc-2860-dc02105cd341@tarantool.org> <9a02e44d-cdf8-c2e6-16b9-326aef714021@tarantool.org> From: Vladislav Shpilevoy Message-ID: <4151ee6c-fb07-0801-e6ad-d62cffcdb197@tarantool.org> Date: Wed, 14 Aug 2019 22:18:02 +0200 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 7bit Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: Kirill Shcherbatov , Tarantool MailList 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;