[erlang-questions] Mnesia:write, index and complexity

[Pablo Polvorin]

Hi,
there has been a discussion of this some months ago,
search for "Index Overhead In Mnesia"


2008/10/2 Greg Burri <greg.burri@REDACTED>:
> Hi,
> I use mnesia for a little project and I observed a strange (but maybe right)
> behavior from the function mnesia:write/1 when an extra index has alway the
> same value.
> In this case the complexity of the insertion appears to be in O(n) where n
> is the number of tuple in the table.
>
> My record :
> -record(minichat,
>    {
>       id,
>       auteur_id, %indexed
>       date,
>       pseudo,
>       contenu,
>       troll_id = undefined, %indexed
>       racine_id = undefined
>    }).
>
> So, I made a little benchmark to see what happen in three cases :
> 1) '#minichat.troll_id' is undefined for all tuple
> 2) same as 1) but without the index on 'troll_id'
> 3) 'troll_id' is indexed but some random values are put in it
>
> You can see the results here :
> 1) O(n) : http://www.gburri.org/mnesia_write/results_100_000.png
> 2) O(1) :
> http://www.gburri.org/mnesia_write/results_100_000_without_index_on_troll_id.png
> 3) O(1) :
> http://www.gburri.org/mnesia_write/results_100_000_with_random_data_into_troll_id.png
>
> Is this behavior normal ? Is this the result of the collisions of keys ?
>
>
> Here is some additional informations about my tests :
>
> The creation of the table (called at the beginning of all test) :
> [..]
>    mnesia:create_table(minichat, [
>       {attributes, record_info(fields, minichat)},
>       {disc_copies, [node()]}
>    ]),
>    mnesia:add_table_index(minichat, auteur_id),
>    mnesia:add_table_index(minichat, troll_id). % commented for the second
> case test
>
> The benchmark code :
> [..]
> bench_write_minichat(Filename) ->
>    Times = bench_write_minichat(1, []),
>    {ok, File} = file:open(Filename, [write]),
>    lists:foreach(
>       fun({Id, Time}) ->
>          io:format(File, "~w ~w~n", [Id, Time])
>       end,
>       Times
>    ),
>    file:close(File).
> bench_write_minichat(100000, Temps) -> Temps;
> bench_write_minichat(Id, Temps) ->
>    {T, _} = timer:tc(mnesia, transaction, [fun() ->
>       mnesia:write(#minichat{
>          id = Id,
>          auteur_id = random:uniform(1000),
>          date = now(),
>          pseudo = "Test",
>          contenu = "Blabla blabla bla.",
>          racine_id = random:uniform(1000)
>          % ,troll_id = random:uniform(1000) % uncommented for the third case
> test
>       })
>    end]),
>    bench_write_minichat(Id + 1, if Id rem 500 =:= 0 -> [{Id, T} | Temps];
> true -> Temps end).
>
>
> /Greg Burri
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>