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

[Greg Burri]

Thanks a lot, I solved my problem...

/Greg

On Fri, Oct 3, 2008 at 1:36 AM, Pablo Polvorin <pablo.polvorin@REDACTED>wrote:

> 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
> >
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20081003/954cccb9/attachment.htm>