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 EE9E8266DE for ; Tue, 13 Aug 2019 17:20:58 -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 KAahIe2XK0iM for ; Tue, 13 Aug 2019 17:20:58 -0400 (EDT) Received: from smtp45.i.mail.ru (smtp45.i.mail.ru [94.100.177.105]) (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 37BB82664D for ; Tue, 13 Aug 2019 17:20:58 -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> From: Vladislav Shpilevoy Message-ID: <9a02e44d-cdf8-c2e6-16b9-326aef714021@tarantool.org> Date: Tue, 13 Aug 2019 23:23:38 +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! 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).