← Back to team overview

maria-developers team mailing list archive

Re: 6ac19d09c66: MDEV-16978 Application-time periods: WITHOUT OVERLAPS

 

On Wed, 4 Dec 2019 at 01:00, Nikita Malyavin <nikitamalyavin@xxxxxxxxx>
wrote:

>
>
> On Tue, 3 Dec 2019 at 23:59, Sergei Golubchik <serg@xxxxxxxxxxx> wrote:
>
>> > > > > But it can be done better. You search for the key with the same
>> > > > > value and a period start <= than the period start of new row.
>> > > > > And then you have to check two rows for overlaps. If you'll
>> > > > > search for a key with the period start <= than the _period end_
>> > > > > of the new row, then you'll only need to check one row (may be
>> > > > > one more, if updating).
>> > > > >
>> > > >  It can't work just that way: to handle case when period start =
>> > > >  _period end_ of the new row, you should write even more checks,
>> > > >  and then move cursor left.
>> > >
>> > > No, I don't see that. Can you show an example where you'd need even
>> > > more checks?
>> >
>> > Ok,
>> > suppose you have to rows in table with periods:
>> > (b, c),
>> > (c, d).
>> >
>> > Now you insert (a, c). ha_index_read_map will look for period_start <=
>> > c, so it will return (c, d). These rows do not overlap, but we yet do
>> > not know if (b, c) is there. So we need to go to the previous row.
>> >
>> > Now the algorithm looks same complex: read key, make some checks, got
>> > to the prev record.
>>
>> I see. Because intervals are inclusive we probably have to search
>> with < not <=. HA_READ_BEFORE_KEY
>>
>> Yes, suddenly I didn't think about <  (i.e., HA_READ_BEFORE_KEY), but
> that can work
>

Another case:
suppose you have to rows in table with periods (a<b<c<d):
(a, c),
(c, d).
Let us update (c,d) --> (b,d). I call it "move left".

ha_index_read_map with period_start < d will return (c,d). Again check
is_update, and call ha_index_prev()

Follow ups

References