Performance of mnesia:select/2

[Sverker Eriksson]

ETS traversals with match specs like this:

MatchExpression = [ {{'_', K, '_'}, [], ['$_']} || K <- ManyKeys ]

With a long list of fully bound keys, are note optimized very well.

For ordered_set it will remember that smallest and largest key in that list 
and then traverse the tree starting at smallest and stop when reaching the 
largest key, visiting *all* keys in between.

For set, bag and duplicate_bag it will hash all keys and remember their table 
bucket index in an array. However, to not visit same bucket twice (or more) it 
checks for duplicate by a linear search. This makes it O(N*N) where N is 
length(ManyKeys).

We should probably do something about that O(N*N) precalculation of unique 
bucket indexes as it most likely makes things worse than just hash and visit 
one key at a time when there are a lot of them.

/Sverker




-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5509 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20210301/aa9f32df/attachment.bin>