[erlang-questions] ranged lookup on ordered_set ETS

[Robert Virding]

Yes, using ets:select would be the most beautiful way, but as Ulf says giving the key as a "variable" will scan the whole table.

Another way of doing it is to use ets:next. If your key range LowerLimit < Key < UpperLimit you can step through the keys using ets:next. Something like:

K1 = ets:next(Table, LowerLimit),
[V1] = ets:lookup(Table, K1),
K2 = ets:next(Table, K1),
[V2] = ets:lookup(Table, K2),
...

until you hit the UpperLimit. In a nice loop of course. This works *even if LowerLimit is not a key in the table*. It means that all lookups will be fast as you use the key and you never scan the table, but you have to do the looping yourself which will slow it down. If the table is big it should be better.

Robert

----- Original Message -----
> 
> 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
> 
> 
> 
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>