← Back to team overview

maria-developers team mailing list archive

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

 

Hello, Sergei!
I have updated the code, please see

   - bb-10.5-MDEV-16978-without-overlaps
   <https://github.com/MariaDB/server/compare/bb-10.5-MDEV-16978-without-overlaps>

  branch.

Among the changes I, having noticed that innodb combination is missing,
have added it, and some merging down from my INSERT/REPLACE patch was
required to make it run successfully.

Below are the rest comments:

On Tue, 19 Nov 2019 at 15:45, Sergei Golubchik <serg@xxxxxxxxxxx> wrote:

>
> > diff --git a/sql/handler.cc b/sql/handler.cc
> > index 94cffd69b75..560f6316602 100644
> > --- a/sql/handler.cc
> > +++ b/sql/handler.cc
> > @@ -6913,6 +6928,130 @@ void handler::set_lock_type(enum thr_lock_type
> lock)
> >    table->reginfo.lock_type= lock;
> >  }
> >
> > +int handler::ha_check_overlaps(const uchar *old_data, const uchar*
> new_data)
> > +{
> > +  DBUG_ASSERT(new_data);
> > +  if (!table_share->period.unique_keys)
> > +    return 0;
> > +  if (table->versioned() && !table->vers_end_field()->is_max())
> > +    return 0;
> > +
> > +  bool is_update= old_data != NULL;
> > +  if (!check_overlaps_buffer)
> > +    check_overlaps_buffer= (uchar*)alloc_root(&table_share->mem_root,
> > +
> table_share->max_unique_length
> > +                                              + table_share->reclength);
> > +  auto *record_buffer= check_overlaps_buffer +
> table_share->max_unique_length;
> > +  auto *handler= this;
> > +  if (handler->inited != NONE)
> > +  {
> > +    if (!check_overlaps_handler)
> > +    {
> > +      check_overlaps_handler= clone(table_share->normalized_path.str,
> > +                                    &table_share->mem_root);
>
> wouldn't it be simpler and cheaper to use HA_EXTRA_REMEMBER_POS and
> HA_EXTRA_RESTORE_POS, as we've discussed?
>
Can it stack (like, what'd be if HA_EXTRA_REMEMBER_POS is called several
times)?
I guess it can't, and somebody on upper layers could have already used it.
This is for example done in TABLE::delete_row(). I see that you've removed
it in latest 10.4+, but anyway, I think it's better to avoid remembering on
lower layers


> > +      int error= -1;
> > +      if (check_overlaps_handler != NULL)
> > +        error= check_overlaps_handler->ha_external_lock(table->in_use,
> F_RDLCK);
> > +      if (error)
> > +        return error;
> > +    }
> > +    handler= check_overlaps_handler;
> > +  }
>
> why "if (handler->inited != NONE)" ?
> What happens if it is NONE?
>
then `this` is used

>
> > +
> > +  for (uint key_nr= 0; key_nr < table_share->keys; key_nr++)
> > +  {
> > +    const KEY *key_info= table->key_info + key_nr;
> > +    const uint key_parts= key_info->user_defined_key_parts;
> > +    if (!key_info->without_overlaps)
> > +      continue;
> > +
> > +    key_copy(check_overlaps_buffer, new_data, key_info, 0);
> > +    if (is_update)
> > +    {
> > +      bool key_used= false;
> > +      for (uint k= 0; k < key_parts && !key_used; k++)
> > +        key_used= bitmap_is_set(table->write_set,
> > +                                key_info->key_part[k].fieldnr - 1);
> > +      if (!key_used)
> > +        continue;
> > +    }
>
> Good.
>
That's midenok's idea:)


> > +
> > +    int error= handler->ha_index_init(key_nr, 0);
> > +    if (error)
> > +      return error;
> > +
> > +    for (int run= 0; run < 2; run++)
> > +    {
> > +      if (run == 0)
> > +      {
> > +        error = handler->ha_index_read_map(record_buffer,
> > +                                           check_overlaps_buffer,
> > +                                           key_part_map((1 <<
> key_parts) - 1),
> > +                                           HA_READ_KEY_OR_PREV);
> > +        if (error == HA_ERR_KEY_NOT_FOUND)
> > +          continue;
> > +      }
> > +      else
> > +      {
> > +        error = handler->ha_index_next(record_buffer);
> > +        if (error == HA_ERR_END_OF_FILE)
> > +          continue;
> > +      }
> > +
> > +      if (error)
> > +      {
> > +        handler->ha_index_end();
> > +        return error;
> > +      }
>
> I found this "for (int run= 0; run < 2; run++)" rather confusing.
> Particularly as you have an if() to have different code for the first
> and the second runs.
>
> it would be clearer to unroll the loop and move the common code (period
> comparison) into a function. Like
>
>   handler->ha_index_read_map(...);
>   compare_periods();
>   handler->ha_index_next();
>   compare_periods();
>

Have rewritten it that way, looks really better👍


> 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. So even more amount of effort is required, but the advantage
on the other hand is that moving the cursor will happen much less frequent.

Also, why do you store both period ends in the index? It seems like it'd
> be enough to store only one end - only the start or only the end. Both
> ends help if you use keyreads, but you don't. On the second thought,
> perhaps, you should use keyreads, there's no need to fetch the whole row
> for this overlap check. On the yet another thought it might not work
> with HA_EXTRA_REMEMBER_POS.
>

I think keyreads can work with HA_EXTRA_REMEMBER_POS. Moreover, I agree
that using keyreads can be much more efficient. However, all of my latest
code, namely FKs and REPLACE/IODKU, are not based on keyreads, and
rewriting it now will require significant effort. Let's make it a separate
task, maybe?

> +
> > +      /* In case of update it could appear that the nearest neighbour is
> > +       * a record we are updating. It means, that there are no overlaps
> > +       * from this side. */
> > +      if (is_update && memcmp(old_data + table->s->null_bytes,
> > +                              record_buffer + table->s->null_bytes,
> > +                              table->s->reclength -
> table->s->null_bytes) == 0)
> > +      {
> > +        continue;
> > +      }
>
> I'd rather compare row positions here.
>
What do you mean by that?


> > +
> > +      uint period_key_part_nr= key_parts - 2;
> > +      int cmp_res= 0;
> > +      for (uint part_nr= 0; !cmp_res && part_nr < period_key_part_nr;
> part_nr++)
> > +      {
> > +        Field *f= key_info->key_part[part_nr].field;
> > +        cmp_res= f->cmp(f->ptr_in_record(new_data),
> > +                        f->ptr_in_record(record_buffer));
> > +      }
> > +      if (cmp_res)
> > +        continue; /* key is different => no overlaps */
> > +
> > +      int period_cmp[2][2]= {/* l1 > l2, l1 > r2, r1 > l2, r1 > r2 */};
> > +      for (int i= 0; i < 2; i++)
> > +      {
> > +        for (int j= 0; j < 2; j++)
> > +        {
> > +          Field *lhs= key_info->key_part[period_key_part_nr + i].field;
> > +          Field *rhs= key_info->key_part[period_key_part_nr + j].field;
> > +
> > +          period_cmp[i][j]= lhs->cmp(lhs->ptr_in_record(new_data),
> > +                                     rhs->ptr_in_record(record_buffer));
> > +        }
> > +      }
>
> this can be simplified too if you'll change the code as I suggested
> above to do only one index read - you'll only need one comparison,
> instead of four.
>
I have already moved it in a separate function in FK and REPLACE code. Have
merged it down to WITHOUT OVERLAPS branch now.


> > +
> > +      if ((period_cmp[0][0] <= 0 && period_cmp[1][0] > 0)
> > +          || (period_cmp[0][0] >= 0 && period_cmp[0][1] < 0))
> > +      {
> > +        handler->ha_index_end();
> > +        return HA_ERR_FOUND_DUPP_KEY;
> > +      }
> > +    }
> > +    error= handler->ha_index_end();
> > +    if (error)
> > +      return error;
> > +  }
> > +  return 0;
> > +}
> > +
> >  #ifdef WITH_WSREP
> >  /**
> >    @details
> > diff --git a/sql/handler.h b/sql/handler.h
> > index 63d0bf2215c..71debf9bab7 100644
> > --- a/sql/handler.h
> > +++ b/sql/handler.h
> > @@ -3237,6 +3243,8 @@ class handler :public Sql_alloc
> >      DBUG_ASSERT(cached_table_flags < (HA_LAST_TABLE_FLAG << 1));
> >      return cached_table_flags;
> >    }
> > +  /** PRIMARY KEY WITHOUT OVERLAPS check is done globally */
>
> what do you mean "globally"?
>
Yeah, looks weird. Updated

> +  int ha_check_overlaps(const uchar *old_data, const uchar* new_data);
> >    /**
> >      These functions represent the public interface to *users* of the
> >      handler class, hence they are *not* virtual. For the inheritance
> > diff --git a/sql/sql_table.cc b/sql/sql_table.cc
> > index 9bb1d98152b..5aba86003c6 100644
> > --- a/sql/sql_table.cc
> > +++ b/sql/sql_table.cc
> > @@ -4549,25 +4552,57 @@ static bool vers_prepare_keys(THD *thd,
> HA_CREATE_INFO *create_info,
> >      if (key->type != Key::PRIMARY && key->type != Key::UNIQUE)
> >        continue;
> >
> > -    Key_part_spec *key_part= NULL;
> > -    List_iterator<Key_part_spec> part_it(key->columns);
> > -    while ((key_part=part_it++))
> > +    if (create_info->versioned())
> >      {
> > -      if (!my_strcasecmp(system_charset_info,
> > -                         row_start_field,
> > -                         key_part->field_name.str) ||
> > -
> > -          !my_strcasecmp(system_charset_info,
> > -                         row_end_field,
> > -                         key_part->field_name.str))
> > -        break;
> > +      Key_part_spec *key_part=NULL;
> > +      List_iterator<Key_part_spec> part_it(key->columns);
> > +      while ((key_part=part_it++))
> > +      {
> > +        if (row_start_field.streq(key_part->field_name) ||
> > +            row_end_field.streq(key_part->field_name))
> > +          break;
> > +      }
> > +      if (!key_part)
> > +        key->columns.push_back(new Key_part_spec(&row_end_field, 0));
> >      }
> > -    if (key_part)
> > -      continue; // Key already contains Sys_start or Sys_end
> > +  }
> >
> > -    Key_part_spec *key_part_sys_end_col=
> > -        new (thd->mem_root)
> Key_part_spec(&create_info->vers_info.as_row.end, 0);
> > -    key->columns.push_back(key_part_sys_end_col);
> > +  key_it.rewind();
> > +  while ((key=key_it++))
> > +  {
> > +    if (key->without_overlaps)
> > +    {
> > +      if (key->type != Key::PRIMARY && key->type != Key::UNIQUE)
> > +      {
> > +        my_error(ER_PERIOD_WITHOUT_OVERLAPS_NON_UNIQUE, MYF(0),
> key->period.str);
> > +        return true;
> > +      }
> > +      if (!create_info->period_info.is_set()
> > +          || !key->period.streq(create_info->period_info.name))
> > +      {
> > +        my_error(ER_PERIOD_NOT_FOUND, MYF(0), key->period.str);
> > +        return true;
> > +      }
> > +      if (thd->work_part_info)
> > +      {
> > +        my_error(ER_PERIOD_WITHOUT_OVERLAPS_PARTITIONED, MYF(0));
>
> why?
>
Unfortunately partitions do not support searching upper/lower bounds (i.e.
KEY_OR_PREV, KEY_OR_NEXT). But I think it is doable. For now it just
doesn't work.


>
> > +        return true;
> > +      }
> > +      const auto &period_start= create_info->period_info.period.start;
> > +      const auto &period_end= create_info->period_info.period.end;
> > +      List_iterator<Key_part_spec> part_it(key->columns);
> > +      while (Key_part_spec *key_part= part_it++)
> > +      {
> > +        if (period_start.streq(key_part->field_name)
> > +            || period_end.streq(key_part->field_name))
> > +        {
> > +          my_error(ER_KEY_CONTAINS_PERIOD_FIELDS, MYF(0),
> key->name.str);
> > +          return true;
> > +        }
> > +      }
> > +      key->columns.push_back(new Key_part_spec(&period_start, 0));
> > +      key->columns.push_back(new Key_part_spec(&period_end, 0));
> > +    }
> >    }
> >
> >    return false;
> > diff --git a/sql/table.h b/sql/table.h
> > index 2b866159fe0..6511960488e 100644
> > --- a/sql/table.h
> > +++ b/sql/table.h
> > @@ -1730,10 +1731,18 @@ class IS_table_read_plan;
> >
> >  /** number of bytes used by field positional indexes in frm */
> >  constexpr uint frm_fieldno_size= 2;
> > +/** number of bytes used by key position number in frm */
> > +constexpr uint frm_keyno_size= 2;
> >  static inline uint16 read_frm_fieldno(const uchar *data)
> >  { return uint2korr(data); }
> > -static inline void store_frm_fieldno(const uchar *data, uint16 fieldno)
> > +static inline void store_frm_fieldno(uchar *data, uint16 fieldno)
> >  { int2store(data, fieldno); }
> > +static inline uint16 read_frm_keyno(const uchar *data)
> > +{ return uint2korr(data); }
> > +static inline void store_frm_keyno(uchar *data, uint16 fieldno)
> > +{ int2store(data, fieldno); }
> > +static inline size_t frm_ident_stored_size(size_t len)
> > +{ return len + (len > 255 ? 3 : 1); }
>
> this is exactly extra2_str_size() function. Don't duplicate it, reuse.
> (and rename, if you'd like a more generic name)
>
> thanks, replaced with  extra2_str_size()

> >
> >  class select_unit;
> >  class TMP_TABLE_PARAM;
> > diff --git a/sql/unireg.cc b/sql/unireg.cc
> > index 7130b3e5d8a..1e95242786e 100644
> > --- a/sql/unireg.cc
> > +++ b/sql/unireg.cc
> > @@ -485,6 +486,16 @@ LEX_CUSTRING build_frm_image(THD *thd, const
> LEX_CSTRING &table,
> >      store_frm_fieldno(pos, get_fieldno_by_name(create_info,
> create_fields,
> >
>  create_info->period_info.period.end));
> >      pos+= frm_fieldno_size;
> > +    store_frm_keyno(pos, create_info->period_info.unique_keys);
> > +    pos+= frm_keyno_size;
> > +    for (uint key= 0; key < keys; key++)
> > +    {
> > +      if (key_info[key].without_overlaps)
> > +      {
> > +        store_frm_keyno(pos, key);
> > +        pos+= frm_keyno_size;
> > +      }
> > +    }
>
> This will make 10.5 frms look corrupted in 10.4. Better use a new EXTRA2
> flag for that. With a number > EXTRA2_ENGINE_IMPORTANT.
>
> Another way is to update 10.4 code to handle additional entry, but ok,
this way is same good for me

Regards,
> Sergei
> VP of MariaDB Server Engineering
> and security@xxxxxxxxxxx
>


-- 
Yours truly,
Nikita Malyavin

Follow ups

References