Re: New index type in mnesia (new feature)
| Newsgroups | gmane.comp.lang.erlang.patches |
|---|---|
| Message-ID | <[email protected]> |
Hello,
Unfortunatelly patch in R16B01 does't fix all performance problem for low
cardinality columns.
I've prepared simple benchmark for otp_R16B, otp_R16B01 and otp_R16B01
with mnesia new index patch. File test.erl shouls be run on otp_R16B,
otp_R16B01
and test2.erl on otp_R16B01 with mnesia new index patch.
In atachement benchmark results from my laptop (ubuntu 13.04, 4 core, 4GB
RAM).
Please note that patch, that was applied in R1601 fix only problem with
insert operation (was bag in R16B, is duplicated_bag in R16B01):
{{TableType, Storage, IndexesAndType, Unused}, TransactionContext,
Operation, Records, OperationTime [us], Rec/sec}
otp_R16:
{{set,ram_copies,[state],[]},async_dirty,'Insert',10000,754401,13255.55},
otp_R16B01:
{{set,ram_copies,[state],[]},async_dirty,'Insert',10000,111412,89756.94},
but write and delete operations are still very slow:
{{set,ram_copies,[state],[]},async_dirty,'UpdateStateField',10000,3107059,3218.48},
{{set,ram_copies,[state],[]},async_dirty,'UpdatemTimeField',10000,2920105,3424.53},
{{set,ram_copies,[state],[]},async_dirty,'Delete',10000,1445054,6920.16},
In my solution, there is no necessity to iterate long lists (in case of
low cardinality column), but Primary key value are deleted/inserted
from/info ets.
Below benchmark result for my solution with new index type:
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'Insert',10000,122417,81688.00},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'UpdateStateField',10000,149560,66862.80},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'UpdatemTimeField',10000,146501,68258.92},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'Delete',10000,103037,97052.52}
Please run this benchmarks on your machine and check results.
Regards
Aleksander Nycz
> There is a patch included in the today's release that address this issue
> in
> a simpler way,
> for set (and ordered set if I remember correctly).
>
> Can you check if the performance is good enough for you in R16B01.
>
> /Dan
>
>
> On Wed, Jun 19, 2013 at 6:51 PM, Aleksander Nycz
> <[email protected]
>> wrote:
>
>> Hello,
>>
>> Mnesia gives possibility to create table indexes, when
>> the user wants to frequently use some other field
>> than the key field to look up records.
>>
>> Current index solution in mnesia uses ets table (type bag or
>> duplicated_bag) to maintain mapping:
>> Indexed field value -> Primary key value.
>>
>> Unfortunatelly current solution has very significant disadvantage:
>> operation performance (loading table, insert new records,
>> delete records, etc.) is very low when index is set on 'Low-cardinality
>> column'
>>
>> http://en.wikipedia.org/wiki/**Cardinality_%28SQL_statements%**29<http://en.wikipedia.org/wiki/Cardinality_%28SQL_statements%29>
>>
>> In such case operation complexity is O(n) when n is number
>> of Primary Key Values. For small n performance can be acceptable for
>> some
>> application,
>> but when n is the hundreds, thousands or even more such index
>> are useless. New index type provides O(1) complexity.
>>
>> This patch introduces new index type in mnesia database.
>> Main concept is to maintain all Primary Key Values not direcly in
>> bag/duplicated_bag ets but in set of ets.
>> For each Indexed field value new ets is created
>> and Primary Key Values are strored in this ets.
>> For 'Low-cardinality column' there is only a few Indexed key value (eg.
>> isActive (true/false), state (new/pending/suspended/active)**, ...)
>> so memory overhead for ets is not significant.
>>
>> Standard index:
>> Indexed field value -> [Primary key value]
>>
>> New index based on ets:
>> Indexed field value -> ets, that contains Primary key value
>>
>> Restrictions:
>>
>> 1. New index can be created on disc_copies or ram_copies tables only.
>> Tables disc_only_copies are not supported.
>> 2. Index type can't be changed. The only way to change existing index
>> idx_list to idx_ets and vice versa
>> is to delete existing index and create new one by
>> mnesia:add_table_index/3 (new function, see below)
>>
>>
>> New API:
>>
>> 1. Define index type when table is created:
>>
>> create_table(Name, TabDef) -> {atomic, ok} | {aborted, Reason}
>>
>> New TabDef value:
>> {index_type, [{atom() | int(), 'idx_std' | 'idx_ets'}]} - 'idx_std' is
>> default when index is created
>>
>> Example:
>>
>> -type(poolId() :: integer()).
>> -type(bucketId() :: integer()).
>> -type(resourceState() :: free | reserved | gracePeriod).
>>
>> -record(rmResource, {id :: {poolId(),
>> any()}
>> ,state :: {poolId(),
>> bucketId(), resourceState()}
>> ,availableFrom :: integer()
>> ,availableTo :: integer()
>> ,requestorId :: any()
>> ,reservedFrom :: integer()
>> ,reservedTo :: integer()
>> ,isDeleted = false :: boolean()
>> ,mTime :: integer()}).
>>
>> {atomic,ok} = mnesia:create_table(**tRMResources
>> ,[
>> {disc_copies, []}
>> ,{ram_copies, [node()]}
>> ,{type,set}
>> ,{attributes,record_info(**fields, rmResource)}
>> ,{record_name, rmResource}
>> ,{index, [state, requestorId,
>> mTime]}
>> ,{index_type, [{state, idx_ets},
>> {requestorId, idx_std}]}
>> ]),
>>
>> 2. Add new index to existing table:
>>
>> mnesia:add_table_index(Tab, AttrName, IndexOpts) -> {aborted, R} |
>> {atomic, ok}
>>
>> This function creates a index on Mnesia table called Tab on AttrName
>> field according to the argument IndexOpts.
>> This list must be a list of {Item, Value} tuples, currently only one
>> option is allowed:
>> {index_type, 'idx_std' | 'idx_ets'}
>>
>> Example:
>>
>> mnesia:add_table_index(**tRMResources, isDeleted, [{index_type,
>> 'idx_ets'}])
>>
>> 3. New match_object/4, dirty_match_object/3 functions:
>>
>> match_object(Tab, Pat, Limit, LockKind) -> [Record] | transaction abort.
>> dirty_match_object(Tab, Pat, Limit) -> [Record] | exit({aborted,
>> Reason}).
>>
>> Similar to match_object/3 and dirty_match_object/2, but returns no more
>> than Limit records.
>>
>>
>> 4. New index_match_object/5, dirty_index_match_object/4 functions:
>>
>> index_match_object(Tab, Pat, Attr, Limit, LockKind) -> [Record] |
>> transaction abort.
>> dirty_index_match_object(Tab, Pat, Attr, Limit) -> [Record] |
>> exit({aborted, Reason}).
>>
>> Similar to index_match_object/4, dirty_index_match_object/3 but returns
>> no
>> more than Limit records.
>>
>>
>> 5. New index_read/4, dirty_index_read/4 functions:
>>
>> index_read(Tab, Key, Attr, Limit) -> [Record] | transaction abort.
>> dirty_index_read(Tab, Key, Attr, Limit) -> [Record] | exit({aborted,
>> Reason}).
>>
>> Similar to index_read/3, dirty_index_read/3 but returns no more than
>> Limit
>> records.
>>
>>
>> 6. New select_limit/3, select_limit/4, dirty_select/3 functions;
>>
>> select_limit(Tab, MatchSpec, NObjects [, Lock]) -> [Object] |
>> transaction
>> abort.
>>
>> Similar to select(Tab, MatchSpec [, Lock]) but returns maximum NObjects
>> records, of course empty list can also be returned.
>> Continuation (see select/4) is not possible. This function can also use
>> indexes to find matching records
>> as contrasted with select/4.
>>
>> dirty_select(Tab, Spec, Limit) -> [Object] | exit({aborted, Reason}.
>>
>> Similar to dirty_select/2 but returns no more than Limit records.
>>
>> And git links:
>>
>> git fetch
>> git://github.com/nyczol/otp.**git<http://github.com/nyczol/otp.git>mnesia_new_index
>>
>> https://github.com/nyczol/otp/**compare/erlang:master...**mnesia_new_index<https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index>
>> https://github.com/nyczol/otp/**compare/erlang:master...**
>> mnesia_new_index.patch<https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index.patch>
>>
>> Regards,
>> Aleksander Nycz
>>
>> --
>> Aleksander Nycz
>> Senior Software Engineer
>> Telco_021 BSS R&D
>> Comarch SA
>> Phone: +48 12 646 1216
>> Mobile: +48 691 464 275
>> website: www.comarch.pl
>>
>>
>>
>> _______________________________________________
>> erlang-patches mailing list
>> [email protected]
>> http://erlang.org/mailman/listinfo/erlang-patches
>>
>>
>
_______________________________________________
erlang-patches mailing list
[email protected]
http://erlang.org/mailman/listinfo/erlang-patches
test2.erl
(text/x-erlang, 3.7 KB)
-module(test2).
-export([t/1]).
-type(resourceState() :: free | reserved).
-record(rmResource, {id :: integer()
,state :: resourceState()
,mTime :: integer()}).
createTable({Type, Storage, {Index, IndexType}, _Unused}) ->
{atomic,ok} = mnesia:create_table(tRMResources
,[{disc_copies, case Storage of disc_copies -> [node()]; _ -> [] end}
,{ram_copies, case Storage of ram_copies -> [node()]; _ -> [] end}
,{type,Type}
,{attributes,record_info(fields, rmResource)}
,{record_name, rmResource}
,{index, [Index]}
,{index_type, [{Index, IndexType}] } ]),
ok.
doAction(Max, Max, F, TransCtx) ->
mnesia:activity(TransCtx, F, [Max]),
ok;
doAction(Cnt, Max, F, TransCtx) ->
mnesia:activity(TransCtx, F, [Cnt]),
doAction(Cnt+1, Max, F, TransCtx).
performTests([], Results) ->
lists:reverse(Results);
performTests([{TabParams, Actions}|Tail], Results) ->
Res = performOneTest(TabParams, Actions),
performTests(Tail, [Res|Results]).
performOneTest(TabParams, Actions) ->
io:format("Perform test for table ~p~n", [TabParams]),
catch mnesia:delete_table(tRMResources),
ok = createTable(TabParams),
timer:sleep(1000),
lists:reverse(performActions(Actions, TabParams, [])).
performActions([], _TabParams, Result) ->
Result;
performActions([{Ctx, {Desc, F}, MaxRec}|Tail], TabParams, Result) ->
io:format("Perform action ~p~n", [Desc]),
Start = erlang:now(),
ok = doAction(1, MaxRec, F, Ctx),
Stop = erlang:now(),
Time = timer:now_diff(Stop, Start),
performActions(Tail, TabParams, [{TabParams, Ctx, Desc, MaxRec, Time, MaxRec*1000000.0/Time}|Result]).
t(MaxRec) ->
%Storages = [disc_copies, ram_copies],
Storages = [ram_copies],
%Types = [set, ordered_set],
Types = [set],
Indexes = [{state, idx_ets}, {mTime, idx_std}],
catch mnesia:stop(),
catch mnesia:delete_schema([node()]),
ok = mnesia:create_schema([node()]),
ok = mnesia:start(),
TransCtx = [async_dirty, transaction],
InsertAction =
fun(Cnt) ->
ok = mnesia:write(tRMResources
,#rmResource{id = Cnt
,state = case Cnt rem 2 of 0 -> free; _ -> reserved end
,mTime = Cnt * 10}
,write)
end,
DeleteAction =
fun(Cnt) ->
ok = mnesia:delete(tRMResources, Cnt, write)
end,
UpdateStateField =
fun(Cnt) ->
[Rec] = mnesia:read(tRMResources, Cnt, write),
ok = mnesia:write(tRMResources
,Rec#rmResource{state = case Rec#rmResource.state of free -> reserved; _ -> free end}
,write)
end,
UpdatemTimeField =
fun(Cnt) ->
[Rec] = mnesia:read(tRMResources, Cnt, write),
ok = mnesia:write(tRMResources
,Rec#rmResource{mTime = Cnt * 2}
,write)
end,
TabParams = [{T, S, I, []} || T <- Types, S <- Storages, I <- Indexes],
Actions = [{C, A, MaxRec} || C <- TransCtx, A <- [{'Insert', InsertAction}
,{'UpdateStateField', UpdateStateField}
,{'UpdatemTimeField', UpdatemTimeField}
,{'Delete', DeleteAction}]],
TestCases = [{T, Actions} || T <- TabParams],
Results = performTests(TestCases, []),
Results.
% TestCases.
test.erl
(text/x-erlang, 3.8 KB)
-module(test).
-export([t/1]).
-type(resourceState() :: free | reserved).
-record(rmResource, {id :: integer()
,state :: resourceState()
,mTime :: integer()}).
createTable({Type, Storage, Index, IndexType}) ->
{atomic,ok} = mnesia:create_table(tRMResources
,[{disc_copies, case Storage of disc_copies -> [node()]; _ -> [] end}
,{ram_copies, case Storage of ram_copies -> [node()]; _ -> [] end}
,{type,Type}
,{attributes,record_info(fields, rmResource)}
,{record_name, rmResource}
,{index, Index}]
++ case IndexType of [] -> []; _ -> [{index_type, IndexType}] end),
ok.
doAction(Max, Max, F, TransCtx) ->
mnesia:activity(TransCtx, F, [Max]),
ok;
doAction(Cnt, Max, F, TransCtx) ->
mnesia:activity(TransCtx, F, [Cnt]),
doAction(Cnt+1, Max, F, TransCtx).
performTests([], Results) ->
lists:reverse(Results);
performTests([{TabParams, Actions}|Tail], Results) ->
Res = performOneTest(TabParams, Actions),
performTests(Tail, [Res|Results]).
performOneTest(TabParams, Actions) ->
io:format("Perform test for table ~p~n", [TabParams]),
catch mnesia:delete_table(tRMResources),
ok = createTable(TabParams),
timer:sleep(1000),
lists:reverse(performActions(Actions, TabParams, [])).
performActions([], _TabParams, Result) ->
Result;
performActions([{Ctx, {Desc, F}, MaxRec}|Tail], TabParams, Result) ->
io:format("Perform action ~p~n", [Desc]),
Start = erlang:now(),
ok = doAction(1, MaxRec, F, Ctx),
Stop = erlang:now(),
Time = timer:now_diff(Stop, Start),
performActions(Tail, TabParams, [{TabParams, Ctx, Desc, MaxRec, Time, MaxRec*1000000.0/Time}|Result]).
t(MaxRec) ->
%Storages = [disc_copies, ram_copies],
Storages = [ram_copies],
%Types = [set, ordered_set],
Types = [set],
Indexes = [state, mTime],
catch mnesia:stop(),
catch mnesia:delete_schema([node()]),
ok = mnesia:create_schema([node()]),
ok = mnesia:start(),
TransCtx = [async_dirty, transaction],
InsertAction =
fun(Cnt) ->
ok = mnesia:write(tRMResources
,#rmResource{id = Cnt
,state = case Cnt rem 2 of 0 -> free; _ -> reserved end
,mTime = Cnt * 10}
,write)
end,
DeleteAction =
fun(Cnt) ->
ok = mnesia:delete(tRMResources, Cnt, write)
end,
UpdateStateField =
fun(Cnt) ->
[Rec] = mnesia:read(tRMResources, Cnt, write),
ok = mnesia:write(tRMResources
,Rec#rmResource{state = case Rec#rmResource.state of free -> reserved; _ -> free end}
,write)
end,
UpdatemTimeField =
fun(Cnt) ->
[Rec] = mnesia:read(tRMResources, Cnt, write),
ok = mnesia:write(tRMResources
,Rec#rmResource{mTime = Cnt * 2}
,write)
end,
TabParams = [{T, S, [I], []} || T <- Types, S <- Storages, I <- Indexes],
Actions = [{C, A, MaxRec} || C <- TransCtx, A <- [{'Insert', InsertAction}
,{'UpdateStateField', UpdateStateField}
,{'UpdatemTimeField', UpdatemTimeField}
,{'Delete', DeleteAction}]],
TestCases = [{T, Actions} || T <- TabParams],
Results = performTests(TestCases, []),
Results.
% TestCases.
benchmark_result.txt
(text/plain, 4.7 KB)
Field state has only two values: reserved/free (low cardinalities)
Field mTime has unique value for each records (high cardinality)
{TableType, Storage, IndexesAndType, Unused}, TransactionContext, Operation, Records, OperationTime [us], Rec/sec}
otp_R16:
[ {{set,ram_copies,[state],[]},async_dirty,'Insert',10000,754401,13255.549767298824},
{{set,ram_copies,[state],[]},async_dirty,'UpdateStateField',10000,4659211,2146.2861415806237},
{{set,ram_copies,[state],[]},async_dirty,'UpdatemTimeField',10000,4236247,2360.580013393931},
{{set,ram_copies,[state],[]},async_dirty,'Delete',10000,1674870,5970.612644563459},
{{set,ram_copies,[mTime],[]},async_dirty,'Insert',10000,122212,81825.02536575786},
{{set,ram_copies,[mTime],[]},async_dirty,'UpdateStateField',10000,161716,61836.800316604415},
{{set,ram_copies,[mTime],[]},async_dirty,'UpdatemTimeField',10000,172136,58093.60040897895},
{{set,ram_copies,[mTime],[]},async_dirty,'Delete',10000,125839,79466.62004624958},
{{set,ram_copies,[state],[]},transaction,'Insert',10000,2262236,4420.405298120974},
{{set,ram_copies,[state],[]},transaction,'UpdateStateField',10000,11338668,881.9378078624403},
{{set,ram_copies,[state],[]},transaction,'UpdatemTimeField',10000,10003560,999.644126690898},
{{set,ram_copies,[state],[]},transaction,'Delete',10000,3385216,2954.0212500472644},
{{set,ram_copies,[mTime],[]},transaction,'Insert',10000,763301,13100.991614055269},
{{set,ram_copies,[mTime],[]},transaction,'UpdateStateField',10000,1070849,9338.384776938672},
{{set,ram_copies,[mTime],[]},transaction,'UpdatemTimeField',10000,980298,10200.979702090588},
{{set,ram_copies,[mTime],[]},transaction,'Delete',10000,956111,10459.036659969397}]
otp_R16B01:
[ {{set,ram_copies,[state],[]},async_dirty,'Insert',10000,111412,89756.93821132374},
{{set,ram_copies,[state],[]},async_dirty,'UpdateStateField',10000,3107059,3218.4776665007007},
{{set,ram_copies,[state],[]},async_dirty,'UpdatemTimeField',10000,2920105,3424.5343917427626},
{{set,ram_copies,[state],[]},async_dirty,'Delete',10000,1445054,6920.1566169845555},
{{set,ram_copies,[mTime],[]},async_dirty,'Insert',10000,111397,89769.02430047488},
{{set,ram_copies,[mTime],[]},async_dirty,'UpdateStateField',10000,155569,64280.15864343153},
{{set,ram_copies,[mTime],[]},async_dirty,'UpdatemTimeField',10000,161992,61731.44352807546},
{{set,ram_copies,[mTime],[]},async_dirty,'Delete',10000,114569,87283.64566331207},
{{set,ram_copies,[state],[]},transaction,'Insert',10000,614271,16279.459717290903},
{{set,ram_copies,[state],[]},transaction,'UpdateStateField',10000,6406570,1560.897641015395},
{{set,ram_copies,[state],[]},transaction,'UpdatemTimeField',10000,5847392,1710.1641210303671},
{{set,ram_copies,[state],[]},transaction,'Delete',10000,2868029,3486.715092490348},
{{set,ram_copies,[mTime],[]},transaction,'Insert',10000,627578,15934.274305345312},
{{set,ram_copies,[mTime],[]},transaction,'UpdateStateField',10000,792824,12613.13986458533},
{{set,ram_copies,[mTime],[]},transaction,'UpdatemTimeField',10000,797585,12537.848630553483},
{{set,ram_copies,[mTime],[]},transaction,'Delete',10000,703820,14208.178227387685}]
otp_R16B01_mnesia_new_index_patch:
[ {{set,ram_copies,{state,idx_ets},[]},async_dirty,'Insert',10000,122417,81688.0008495552},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'UpdateStateField',10000,149560,66862.79753944905},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'UpdatemTimeField',10000,146501,68258.91973433629},
{{set,ram_copies,{state,idx_ets},[]},async_dirty,'Delete',10000,103037,97052.51511592923},
{{set,ram_copies,{mTime,idx_std},[]},async_dirty,'Insert',10000,111806,89440.63824839453},
{{set,ram_copies,{mTime,idx_std},[]},async_dirty,'UpdateStateField',10000,156550,63877.35547748323},
{{set,ram_copies,{mTime,idx_std},[]},async_dirty,'UpdatemTimeField',10000,160791,62192.53565187106},
{{set,ram_copies,{mTime,idx_std},[]},async_dirty,'Delete',10000,113802,87871.91789247992},
{{set,ram_copies,{state,idx_ets},[]},transaction,'Insert',10000,618469,16168.959155592278},
{{set,ram_copies,{state,idx_ets},[]},transaction,'UpdateStateField',10000,771512,12961.561194122709},
{{set,ram_copies,{state,idx_ets},[]},transaction,'UpdatemTimeField',10000,785130,12736.744233439049},
{{set,ram_copies,{state,idx_ets},[]},transaction,'Delete',10000,684825,14602.270653086554},
{{set,ram_copies,{mTime,idx_std},[]},transaction,'Insert',10000,623569,16036.717668774427},
{{set,ram_copies,{mTime,idx_std},[]},transaction,'UpdateStateField',10000,808488,12368.767378118166},
{{set,ram_copies,{mTime,idx_std},[]},transaction,'UpdatemTimeField',10000,801881,12470.678317605729},
{{set,ram_copies,{mTime,idx_std},[]},transaction,'Delete',10000,698536,14315.65445445904}]