[tarantool-patches] Re: [PATCH 2/5] schema: add new system space for FK constraints
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Thu Jul 26 23:12:03 MSK 2018
Thanks for the patch! See my answers, 4 comments and a
patch on the branch.
>
> +++ b/src/box/alter.cc
> @@ -1920,7 +1920,7 @@ on_replace_dd_index(struct trigger * /* trigger */, void *event)
> * Can't drop index if foreign key constraints references
> * this index.
> */
> - if (new_tuple == NULL) {
> + if (old_index != NULL && new_tuple == NULL) {
>
> Also, I didn’t get what you mean by mentioning index_def_change_requires_rebuild.
> Can index id change on its renaming?
Index_id can not change. But a one can remove an index part, or add a new
one. Or change nullability that breaks uniqueness. I do not see how do you
deal with that. To detect such dramatic changes
index_def_change_requires_rebuild() is used in on_replace_dd_index().
>>
>> 4. What about a second key? mp_typeof(**map) right after decoding its
>> header returns type of the first key. But second can be of another type.
>
> Fixed:
>
> - if (mp_typeof(**map) != MP_STR) {
> - tnt_raise(ClientError, errcode,
> - tt_cstr(constraint_name, constraint_len),
> - tt_sprintf("link %d is not map "\
> - "with string keys", i));
> - }
> for (uint8_t j = 0; j < map_sz; ++j) {
> + if (mp_typeof(**map) != MP_STR) {
> + tnt_raise(ClientError, errcode,
> + tt_cstr(constraint_name,
> + constraint_len),
> + tt_sprintf("link %d is not map "\
> + "with string keys", i));
> + }
>
>>
>> And why do we need this {child = , parent = }, ... sequence? Lets just
>> use {<uint>, <uint>}, {<uint>, <uint>}, {<uint>, <uint>} ... It is more
>> compact and simpler to parse. Or even just two arrays: first child and
>> second parent field numbers. It is the most canonical way similar to
>> SQL, it is not? When you specify two column ranges.
>
> I use this format since it is easier to avoid confusing parent and child ids
> (i.e. what comes first and what comes second). Even if we add separate
> convenient Lua API for that purpose.
> If you insist on doing that, I will change format.
Lua API is not about _fk_constraint space. Lua API will be like
space:create_fk() with fancy arguments etc.
I think, _fk_constraint should be compact and easy to store and parse,
not to manually read or write. My opinion is that 3 the best options
exist:
{{..., ..., ...}, {..., ..., ...}} - array of 2 arrays. First is child,
second is parent. Or:
, {..., ..., ...}, {..., ..., ...}, - create separate fields in
_fk_constraint for child and parent arrays. Or:
{child = {..., ..., ...}, parent = {..., ..., ...}} - map with two
keys and two array values.
I do not insist on my format but think we should consult
Kostja and Kirill on the final one.
>>
>> 10. Above you have said that order may be different, but here I see
>> that once you have found a unique index, you merely check that it
>> has sequentially the same field numbers as the fk.
>
> For some reason I forgot to fix this when was preparing patch.
> Fixed by now. Also, according to ANSI (11.8 4.a):
> • Each referenced column shall identify a column of the referenced table and the same column shall not be identi ed more than once.
>
> @@ -3710,6 +3710,41 @@ on_drop_or_replace_fkey_commit(struct trigger *trigger, void *event)
> fkey_delete(fk);
> }
>
> +static int
> +cmp_uint32(const void *_a, const void *_b)
> +{
> + const uint32_t *a = (const uint32_t *) _a, *b = (const uint32_t *) _b;
> + if (*a == *b)
> + return 0;
> + return (*a > *b) ? 1 : -1;
> +}
Looks like in Tarantool source we have plenty of various cmp functions
for qsort. I greped uint32_compare, cmp_uint32 (your), cmp_i64, size_compator,
nums_comparator, int64_cmp. How about to merge them into trivia/util.h as
cmp_uint32, cmp_int64, cmp_size?
> +
> +/**
> + * ANSI SQL doesn't allow list of referenced fields to contain
> + * duplicates.
> + */
> +static int
> +fkey_links_check_duplicates(struct fkey_def *fk_def)
> +{
> + uint32_t *parent_fields =
> + (uint32_t *) region_alloc(&fiber()->gc, fk_def->field_count);
> + if (parent_fields == NULL) {
> + tnt_raise(OutOfMemory, fk_def->field_count, "region",
> + "parent_fields");
> + }
> + for (uint32_t i = 0; i < fk_def->field_count; ++i)
> + parent_fields[i] = fk_def->links[i].parent_field;
> + qsort(parent_fields, fk_def->field_count, sizeof(*parent_fields),
> + cmp_uint32);
> + uint32_t prev_val = parent_fields[0];
> + for (uint32_t i = 1; i < fk_def->field_count; ++i) {
> + if (prev_val == parent_fields[i])
> + return -1;
> + prev_val = parent_fields[i];
Why not
for (uint32_t i = 1; i < fk_def->field_count; ++i) {
if (parent_fields[i - 1] == parent_fields[i])
return -1;
}
So you do not need prev_val actually. Also lets do tnt_raise here
instead of return -1.
> + }
> + return 0;
> +}
> +
>
> on_replace_dd_fk_constraint(struct trigger * /* trigger*/, void *event)
> @@ -3777,6 +3812,11 @@ on_replace_dd_fk_constraint(struct trigger * /* trigger*/, void *event)
> "field collation mismatch");
> }
> }
> + if (fkey_links_check_duplicates(fk_def)) {
> + tnt_raise(ClientError, ER_CREATE_FK_CONSTRAINT,
> + fk_def->name, "referenced fields can not "
> + "contain duplicates");
> + }
>
>
> Probably this is not best implementation. As an improvement I can add kind of optimisation:
>
> *pseudo code below*
>
> uint_64 mask;
> for parent_field in fk_def:
> if (pk_mask & (((uint64_t) 1) << parent_field ==1)
> return -1;
> column_mask_set_field(&mask, parent_field);
> end
> if (pk_mask & (((uint64_t) 1) << 63)) != 0
> fkey_links_check_duplicates(…) // Full version of checking.
> else
> return 1;
>
> Is it worth the effort? I mean here we waste O(field_count) in case the largest
> filedno in parent table > 63. On the other hand, I don’t think that many users
> have tables with field count > 63, so it is likely to be reasonable.
I like this optimization. What is more, I think, we can remove the sorting
things above then. For users who have field numbers > 63 the smallest problem
is slow alter. So for them we can just use O(field_count ^ 2) with no region
and sorting.
>
> Moreover, it would be cool if column_mask_set_fieldno() worked the same
> as bit_set() from lib/bit, i.e. returned previous bit value.
You are free to extend the API.
>>
>>> + fk_index = idx;
>>> + break;
>>> + }
>>> + if (fk_index == NULL) {
>>> + tnt_raise(ClientError, ER_CREATE_FK_CONSTRAINT,
>>> + fk_def->name, "referenced fields don't "
>>> + "compose unique index");
>>> + }
>>> + struct fkey *fkey = (struct fkey *) malloc(sizeof(*fkey));
>>
>> 11. I know how you like memory mapping. How about merge fkey_def into
>> fkey memory? I see, that it is relatively simple and linear thing.
>
> What is the point of doing this? Do you suggest to allocate enough memory for fkey
> right in fkey_def_new_from_tuple() ? Like this:
>
> @@ -3536,7 +3536,8 @@ fkey_def_new_from_tuple(const struct tuple *tuple, uint32_t errcode)
> struct field_link *links = fkey_links_decode(links_raw, &link_count,
> name, name_len, errcode);
> size_t fkey_sz = fkey_def_sizeof(link_count, name_len);
> - struct fkey_def *fk_def = (struct fkey_def *) malloc(fkey_sz);
> + struct fkey_def *fk_def = (struct fkey_def *) malloc(fkey_sz +
> + sizeof(struct fkey);
>
> If so, it would be quite confusing I think (since function returns only
> fkey_def, but memory would be allocated for fkey_def + fkey).
> If you mean smth else or insist on this change, I will fix it.
I just like when structure is self-sufficient. When it can be freed with
one free, and can fit in one cache line for better performance on access fields,
maybe partially. If you do not want to merge them, I do not insist though.
>
>>> diff --git a/src/box/fkey.c b/src/box/fkey.c
>>> new file mode 100644
>>> index 000000000..e45889a0d
>>> --- /dev/null
>>> +++ b/src/box/fkey.c
>>> +void
>>> +fkey_trigger_delete(struct sqlite3 *db, struct sql_trigger *p)
>>> +{
>>
>> 12. Why do you need this function when sql_trigger_delete exists?
>
> Memory layout of FK trigger differs from ordinary one (from sql/fkey.c):
>
> size_t trigger_size = sizeof(struct sql_trigger) +
> sizeof(TriggerStep) + nFrom + 1;
> trigger =
> (struct sql_trigger *)sqlite3DbMallocZero(db,
> trigger_size);
>
> One can see, memory for TriggerStep, sql_trigger and name of
> target table is allocated in one chunk. Thus, fkey_trigger_delete()
> doesn’t release memory for TriggerStep. Overall, if compare
> these functions fkey_trigger_delete() looks much simpler.
I very do not like that the same structure is allocated on different
layouts, it confuses. It is ok only during alter when we temporary
allocate some things on region. Lets allocate this trigger like
ordinary ones and remove fkey_trigger_delete. I like when a
structure is compact, as I say in the previous comment, but not when
it is sometimes compact and other times not.
>>> diff --git a/test/engine/iterator.result b/test/engine/iterator.result
>>> index a36761df8..ba9b0545a 100644
>>> --- a/test/engine/iterator.result
>>> +++ b/test/engine/iterator.result
>>> @@ -4211,7 +4211,7 @@ s:replace{35}
>>> ...
>>> state, value = gen(param,state)
>>> ---
>>> -- error: 'builtin/box/schema.lua:1049: usage: next(param, state)'
>>> +- error: 'builtin/box/schema.lua:1055: usage: next(param, state)'
>>
>> 18. This test fails on each schema change. Lets remove this file:line
>> from the error message alongside the patch.
>
> Ok:
I meant remove 'file:line' from the error message. Not the test itself.
For example, you can catch the error and match the message using
string.match("usage: next(param, state)").
> diff --git a/src/box/alter.cc b/src/box/alter.cc
> index 7b6bd1a5a..c5d1f75df 100644
> --- a/src/box/alter.cc
> +++ b/src/box/alter.cc
> +/**
> + * Decode MsgPack array of links. It consists from maps:
> + * {parent_id (UINT) : child_id (UINT)}.
> + *
> + * @param data MsgPack array of links.
> + * @param[out] out_count Count of links.
> + * @param constraint_name Constraint name to use in error
> + * messages.
> + * @param constraint_len Length of constraint name.
> + * @param errcode Errcode for client errors.
> + * @retval Array of links.
> + */
> +static struct field_link *
> +fkey_links_decode(const char *data, uint32_t *out_count,
> + const char *constraint_name, uint32_t constraint_len,
> + uint32_t errcode)
> +{
> + assert(mp_typeof(*data) == MP_ARRAY);
> + uint32_t count = mp_decode_array(&data);
> + if (count == 0) {
> + tnt_raise(ClientError, errcode,
> + tt_cstr(constraint_name, constraint_len),
> + "at least one link must be specified");
> + }
> + *out_count = count;
> + size_t size = count * sizeof(struct field_link);
> + struct field_link *region_links =
> + (struct field_link *) region_alloc_xc(&fiber()->gc, size);
> + memset(region_links, 0, size);
> + const char **map = &data;
> + for (uint32_t i = 0; i < count; ++i) {
> + uint32_t map_sz = mp_decode_map(map);
> + if (map_sz != 2) {
> + tnt_raise(ClientError, errcode,
> + tt_cstr(constraint_name, constraint_len),
> + tt_sprintf("link must be map with 2 fields"));
> + }
> + for (uint8_t j = 0; j < map_sz; ++j) {
> + if (mp_typeof(**map) != MP_STR) {
> + tnt_raise(ClientError, errcode,
> + tt_cstr(constraint_name,
> + constraint_len),
> + tt_sprintf("link %d is not map "\
> + "with string keys", i));
> + }
> + uint32_t key_len;
> + const char *key = mp_decode_str(map, &key_len);
1. Until we have this https://github.com/tarantool/tarantool/issues/1253
we should check tuple field internals. Here we need to check for MP_UINT
or the crash is possible:
box.cfg{}
t = {'fk_1', 1, 1, false, 'simple', 'restrict', 'restrict', {{child = 'crash', parent = 'crash'}}}
box.space._fk_constraint:insert(t)
Assertion failed: (0), function mp_decode_uint, file /Users/v.shpilevoy/Work/Repositories/tarantool/src/lib/msgpuck/msgpuck.h, line 1434.
Process 76355 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = signal SIGABRT
frame #0: 0x00007fff56cf5b66 libsystem_kernel.dylib`__pthread_kill + 10
libsystem_kernel.dylib`__pthread_kill:
-> 0x7fff56cf5b66 <+10>: jae 0x7fff56cf5b70 ; <+20>
0x7fff56cf5b68 <+12>: movq %rax, %rdi
0x7fff56cf5b6b <+15>: jmp 0x7fff56cecae9 ; cerror_nocancel
0x7fff56cf5b70 <+20>: retq
Target 0: (tarantool) stopped.
> + if (key_len == 6 &&
> + memcmp(key, "parent", key_len) == 0) {
> + region_links[i].parent_field =
> + mp_decode_uint(map);
> + } else if (key_len == 5 &&
> + memcmp(key, "child", key_len) == 0) {
> + region_links[i].child_field =
> + mp_decode_uint(map);
> + } else {
> + char *errmsg = tt_static_buf();
> + snprintf(errmsg, TT_STATIC_BUF_LEN,
> + "unexpected key of link %d '%.*s'", i,
> + key_len, key);
> + tnt_raise(ClientError, errcode,
> + tt_cstr(constraint_name,
> + constraint_len), errmsg);
> + }
> + }
> + }
> + return region_links;
> +}
> +
> +/**
> + * Remove FK constraint from child's list.
> + * Entries in child list are supposed to be unique
> + * by their name.
> + *
> + * @param list List of child FK constraints.
> + * @param fkey_name Name of constraint to be removed.
> + * @retval FK being removed.
> + */
> +static struct fkey *
> +fkey_remove_child(struct rlist *list, const char *fkey_name)
> +{
> + struct fkey *fk;
> + rlist_foreach_entry(fk, list, child_link) {
> + if (strcmp(fkey_name, fk->def->name) == 0) {
> + rlist_del_entry(fk, child_link);
> + return fk;
> + }
> + }
2. In all 3 places of usage you remove the fd from parent list too.
Lets move the deletion there and rename this function to something
like fkey_snatch_by_name or something.
> diff --git a/src/box/fkey.h b/src/box/fkey.h
> new file mode 100644
> index 000000000..0d537b1a7
> --- /dev/null
> +++ b/src/box/fkey.h
> +/** Definition of foreign key constraint. */
> +struct fkey_def {
> + /** Id of space containing the REFERENCES clause (child). */
> + uint32_t child_id;
> + /** Id of space that the key points to (parent). */
> + uint32_t parent_id;
> + /** Number of fields in this key. */
> + uint32_t field_count;
> + /** True if constraint checking is deferred till COMMIT. */
> + bool is_deferred;
3. What is the difference between this and pragma defer_foreign_keys?
Can we remove this flag or the pragma?
> + /** Match condition for foreign key. SIMPLE by default. */
> + enum fkey_match match;
> + /** ON DELETE action. NO ACTION by default. */
> + enum fkey_action on_delete;
> + /** ON UPDATE action. NO ACTION by default. */
> + enum fkey_action on_update;
> + /** Mapping of fields in child to fields in parent. */
> + struct field_link *links;
> + /** Name of the constraint. */
> + char name[0];
> +};
> diff --git a/src/box/space.h b/src/box/space.h
> index 01a4af726..97650cffe 100644
> --- a/src/box/space.h
> +++ b/src/box/space.h
> @@ -183,6 +183,15 @@ struct space {
> * of index id.
> */
> struct index **index;
> + /**
> + * Lists of foreign key constraints. In SQL terms parent
> + * space is the "from" table i.e. the table that contains
> + * the REFERENCES clause. Child space is "to" table, in
> + * other words the table that is named in the REFERENCES
> + * clause.
4. Are you sure?
https://en.wikipedia.org/wiki/Foreign_key
"The table containing the foreign key is called the child table,
and the table containing the candidate key is called the
referenced or parent table."
> + */
> + struct rlist parent_fkey;
> + struct rlist child_fkey;
> };
>
> /** Initialize a base space instance. */
More information about the Tarantool-patches
mailing list