[erlang-questions] ranged lookup on ordered_set ETS

[Ulf Wiger]

Yeah, unfortunately, it is not smart enough to know from guard expressions that it could ignore an entire subtree, so a pattern like [{{{'$1', '_'}, '_'}, [{'and', {'>', '$1', 9999}, {'<', '$1', 10001}}], ['$_']}] will always scan the entire table.

It seems as if this would be possible to fix, but that means digging into the PAM (Patrik's Abstract Machine), and I gather even Patrik is reluctant to do that. ;-)

BR,
Ulf W

On 4 Aug 2011, at 10:18, caox wrote:

> Thanks. 
> 
> You mean in the case  100 <Key  <105, the key could be arranged in format of 
> {100, Extra}, {106, Extra}, {110, Extra} or sth like that. And then match_spec like [{100, '$1'}, [], []} can be applied to do the match job.
> 
> So the ordered_set table is only for the case that the order of search result is significant, but not for ranged searching.
> 
> 在 2011-8-4，下午3:48， Ulf Wiger 写道：
> 
>> 
>> On 4 Aug 2011, at 08:56, caox wrote:
>> 
>>> Hi
>>> 	According to ETS reference,  records in ordered_set ETS are stored in the Erlang Term order of  their key. So, is there a efficient way to do a ranged lookup of key on this kind of ETS without scanning the whole table. For example,    100 < Key  <105.
>>> 	 I guess ets:select/2 doesn't fit for the job.
>> 
>> If you arrange the key so that you can call ets:select/2 with the first part of the key bound, then it will only scan the subset that matches the bound part.
>> 
>> E.g. if you have a table where the key is {Document, Chapter}, and call
>> 
>> ets:select(Docs, [{{{Document,'$1'}, '$2'}, [], [{{'$1','$2'}}]}]).
>> 
>> Your search time will be proportional to the number of chapters in the book, modulo the normal O factor of ordered_set tables.
>> 
>> BR,
>> Ulf W
>> 
>> Ulf Wiger, CTO, Erlang Solutions, Ltd.
>> http://erlang-solutions.com
>> 
>> 
>> 
> 

Ulf Wiger, CTO, Erlang Solutions, Ltd.
http://erlang-solutions.com