Re: [Tarantool-patches] [PATCH] box: add binary search for _session settings space

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

Hi!

>> 2. We don't really need this function anywhere except session_settings.c.
>> Besides, even in that file it is needed only in session_settings_next_in_module().
>> So you can just patch the latter function.
> 
> I don’t think it’s a good idea, consider the following:
> 
> tarantool> box.space._session_settings:select('a', {iterator = 'GE’})
> 
> With the current version, we will find the first element which is GE with linear lookup,
> and the rest loops will consist of one iteration (overall it will always be the number of elements
> in the array). If we change session_settings_next_in_module() to use binary search, 
> however, it will highly increase the number of comparisons, because, even though we know
> that the next element is greater or equal, we are still looking for it in the array.
> 
> My initial patch takes advantage of the array being sorted for update and get methods,
> leaving the case from above untouched. Perhaps I could try to make the first lookup 
> with binary search, and the rest with linear. What do you think?

Hm, you are right. session_settings_next_in_module() perhaps is not the
best place.

Yes, I think all linear places should be fixed and become binary
search. For the iterators case you can patch
session_settings_index_create_iterator() so as it initializes
module_id and setting_id with a first matching module and setting
(or last, depending on the iterator type). Although not sure if it
is correct, because usually creation of an iterator does not
position the iterator. At least it does not happen in all our other
iterators.

Alternative solution - for forward iterator initialize module_id
with -1. In session_settings_iterator_next() check, that if module_id
is -1, then find a first setting with a binary search.
For backward iterator the same - init module_id with session_setting_type_MAX,
and use a binary search first time in session_settings_iterator_prev(),
when you see module_id == MAX.

Motivation is that even though 'update' and 'get' are the most
important places, and you fixed them, some users may still use :select()
even when they want to select just one tuple, with EQ iterator and a
full key. And it will be linear, because select() is always an iterator.