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

[Greg Burri]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20081002/52c185e9/attachment.htm>