Re: Faster inserts with mostly-monotonically increasing values

On Sun, Mar 11, 2018 at 2:27 AM, Pavan Deolasee
<pavan(dot)deolasee(at)gmail(dot)com> wrote:
>
>
> On Sat, Mar 10, 2018 at 12:11 AM, Claudio Freire <klaussfreire(at)gmail(dot)com>
> wrote:
>>
>> On Fri, Mar 9, 2018 at 2:54 PM, Pavan Deolasee <pavan(dot)deolasee(at)gmail(dot)com>
>> wrote:
>> >
>> >
>>
>> >
>> > So yes, the benefits of the patch go down with higher number of clients,
>> > but
>> > it does not entirely vanish.
>>
>> What if you implement my suggestion?
>>
>> That should improve the multi-client case considerably.
>
>
>
> Yes, I will try that next - it seems like a good idea. So the idea would be:
> check if the block is still the rightmost block and the insertion-key is
> greater than the first key in the page. If those conditions are satisfied,
> then we do a regular binary search within the page to find the correct
> location. This might add an overhead of binary search when keys are strictly
> ordered and a single client is inserting the data. If that becomes a
> concern, we might be able to look for that special case too and optimise for
> it too.

Yeah, pretty much that's the idea. Beware, if the new item doesn't
fall in the rightmost place, you still need to check for serialization
conflicts.