[erlang-questions] Efficient way to select a range of data between 2 values?

[Paul Mineiro]

On Mon, 31 Aug 2009, Alexander Uvarov wrote:

> I have ~100K ip2country records like {ip_address_map, {range_from,
> range_to, country_code}} and I am searching for fastest way to lookup
> country_code. There should be matching guard like range_from =< IP >=
> range_to. Any ideas, guys? I am not satisfied with ets (lookup time
> from 0.06s up to 1.6s).
>
> This is my current code (original http://code.google.com/p/ip2country-erlang/source/browse/trunk/ip2country.erl)
> :
>
> -record(ip_address_map, {range_from, range_to, country_code}).
>
> start() ->
>      ets:new(ip, [named_table, public, {keypos, 2}]).
>
> lookup(IP) ->
>    	MatchHead = #ip_address_map{range_from='$1', range_to='$2',
> country_code='$3'},
>    	Guard = [{'=<', '$1', IP}, {'>=', '$2', IP}],
>    	Result = '$3',
> 	ets:select(ip, [{MatchHead, Guard, [Result]}], 1).

Step 1 would be to make the ets table ordered_set type.

Ideally, that would be sufficient, but as I discovered, ets does not
optimize the inequality constraint in a match guard:
http://dukesoferl.blogspot.com/2009/07/ets-ordered-set-select-efficiency.html

However all is not lost, since you can iterate through the ets table using
ets:next/2.  This is less efficient than select when select is optimized,
but can be a win in this case, especially if the number of elements to be
examined is much less than the total number in the table.

Since you say {'=<','$1',IP} you need to do an initial lookup of the lower
bound to get the equality, but if the problem is {'<', '$1', IP} you don't
even need to do that since the Key argument to ets:next/2 in an
ordered_set table need not be a member of the table.

-- p

>
>
> ________________________________________________________________
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
>
>