<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 06/19/2013 06:51 PM, Aleksander Nycz wrote:
<blockquote cite="mid:51C1E19C.2070000@comarch.pl" type="cite">Hello,
<br>
<br>
Mnesia gives possibility to create table indexes, when
<br>
the user wants to frequently use some other field
<br>
than the key field to look up records.
<br>
<br>
Current index solution in mnesia uses ets table (type bag or
duplicated_bag) to maintain mapping:
<br>
Indexed field value -> Primary key value.
<br>
<br>
Unfortunatelly current solution has very significant disadvantage:
<br>
operation performance (loading table, insert new records,
<br>
delete records, etc.) is very low when index is set on
'Low-cardinality column'
<br>
<br>
<a class="moz-txt-link-freetext" href="http://en.wikipedia.org/wiki/Cardinality_%28SQL_statements%29">http://en.wikipedia.org/wiki/Cardinality_%28SQL_statements%29</a>
<br>
<br>
In such case operation complexity is O(n) when n is number
<br>
of Primary Key Values. For small n performance can be acceptable
for some application,
<br>
but when n is the hundreds, thousands or even more such index
<br>
are useless. New index type provides O(1) complexity.
<br>
<br>
This patch introduces new index type in mnesia database.
<br>
Main concept is to maintain all Primary Key Values not direcly in
<br>
bag/duplicated_bag ets but in set of ets.
<br>
For each Indexed field value new ets is created
<br>
and Primary Key Values are strored in this ets.
<br>
For 'Low-cardinality column' there is only a few Indexed key value
(eg. isActive (true/false), state (new/pending/suspended/active),
...)
<br>
so memory overhead for ets is not significant.
<br>
<br>
Standard index:
<br>
Indexed field value -> [Primary key value]
<br>
<br>
New index based on ets:
<br>
Indexed field value -> ets, that contains Primary key value
<br>
<br>
Restrictions:
<br>
<br>
1. New index can be created on disc_copies or ram_copies tables
only. Tables disc_only_copies are not supported.
<br>
2. Index type can't be changed. The only way to change existing
index idx_list to idx_ets and vice versa
<br>
is to delete existing index and create new one by
mnesia:add_table_index/3 (new function, see below)
<br>
<br>
<br>
New API:
<br>
<br>
1. Define index type when table is created:
<br>
<br>
create_table(Name, TabDef) -> {atomic, ok} | {aborted, Reason}
<br>
<br>
New TabDef value:
<br>
{index_type, [{atom() | int(), 'idx_std' | 'idx_ets'}]} -
'idx_std' is default when index is created
<br>
<br>
Example:
<br>
<br>
-type(poolId() :: integer()).
<br>
-type(bucketId() :: integer()).
<br>
-type(resourceState() :: free | reserved | gracePeriod).
<br>
<br>
-record(rmResource, {id ::
{poolId(), any()}
<br>
,state ::
{poolId(), bucketId(), resourceState()}
<br>
,availableFrom ::
integer()
<br>
,availableTo ::
integer()
<br>
,requestorId :: any()
<br>
,reservedFrom ::
integer()
<br>
,reservedTo ::
integer()
<br>
,isDeleted = false ::
boolean()
<br>
,mTime ::
integer()}).
<br>
<br>
{atomic,ok} = mnesia:create_table(tRMResources
<br>
,[
<br>
{disc_copies, []}
<br>
,{ram_copies, [node()]}
<br>
,{type,set}
<br>
,{attributes,record_info(fields, rmResource)}
<br>
,{record_name, rmResource}
<br>
,{index, [state,
requestorId, mTime]}
<br>
,{index_type, [{state,
idx_ets}, {requestorId, idx_std}]}
<br>
]),
<br>
<br>
2. Add new index to existing table:
<br>
<br>
mnesia:add_table_index(Tab, AttrName, IndexOpts) -> {aborted,
R} | {atomic, ok}
<br>
<br>
This function creates a index on Mnesia table called Tab on
AttrName
<br>
field according to the argument IndexOpts.
<br>
This list must be a list of {Item, Value} tuples, currently only
one
<br>
option is allowed:
<br>
{index_type, 'idx_std' | 'idx_ets'}
<br>
<br>
Example:
<br>
<br>
mnesia:add_table_index(tRMResources, isDeleted, [{index_type,
'idx_ets'}])
<br>
<br>
3. New match_object/4, dirty_match_object/3 functions:
<br>
<br>
match_object(Tab, Pat, Limit, LockKind) -> [Record] |
transaction abort.
<br>
dirty_match_object(Tab, Pat, Limit) -> [Record] |
exit({aborted, Reason}).
<br>
<br>
Similar to match_object/3 and dirty_match_object/2, but returns no
more than Limit records.
<br>
<br>
<br>
4. New index_match_object/5, dirty_index_match_object/4 functions:
<br>
<br>
index_match_object(Tab, Pat, Attr, Limit, LockKind) -> [Record]
| transaction abort.
<br>
dirty_index_match_object(Tab, Pat, Attr, Limit) -> [Record] |
exit({aborted, Reason}).
<br>
<br>
Similar to index_match_object/4, dirty_index_match_object/3 but
returns no more than Limit records.
<br>
<br>
<br>
5. New index_read/4, dirty_index_read/4 functions:
<br>
<br>
index_read(Tab, Key, Attr, Limit) -> [Record] | transaction
abort.
<br>
dirty_index_read(Tab, Key, Attr, Limit) -> [Record] |
exit({aborted, Reason}).
<br>
<br>
Similar to index_read/3, dirty_index_read/3 but returns no more
than Limit records.
<br>
<br>
<br>
6. New select_limit/3, select_limit/4, dirty_select/3 functions;
<br>
<br>
select_limit(Tab, MatchSpec, NObjects [, Lock]) -> [Object] |
transaction abort.
<br>
<br>
Similar to select(Tab, MatchSpec [, Lock]) but returns maximum
NObjects
<br>
records, of course empty list can also be returned.
<br>
Continuation (see select/4) is not possible. This function can
also use
<br>
indexes to find matching records
<br>
as contrasted with select/4.
<br>
<br>
dirty_select(Tab, Spec, Limit) -> [Object] | exit({aborted,
Reason}.
<br>
<br>
Similar to dirty_select/2 but returns no more than Limit records.
<br>
<br>
And git links:
<br>
<br>
git fetch git://github.com/nyczol/otp.git mnesia_new_index
<br>
<br>
<a class="moz-txt-link-freetext" href="https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index">https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index</a>
<br>
<a class="moz-txt-link-freetext" href="https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index.patch">https://github.com/nyczol/otp/compare/erlang:master...mnesia_new_index.patch</a>
<br>
<br>
Regards,
<br>
Aleksander Nycz
<br>
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
erlang-patches mailing list
<a class="moz-txt-link-abbreviated" href="mailto:erlang-patches@erlang.org">erlang-patches@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/erlang-patches">http://erlang.org/mailman/listinfo/erlang-patches</a>
</pre>
</blockquote>
Hello,<br>
Please rebase this patch upon current maint. No mergeing ;)<br>
Thanks,<br>
<br>
<pre class="moz-signature" cols="72">--
BR Fredrik Gustafsson
Erlang OTP Team</pre>
</body>
</html>