ets select match specification analysis

[Paul Mineiro]

Timing tests in R12B5 indicate the range-constrained prefix condition
results in a full table scan for ets ordered_set.

http://dukesoferl.blogspot.com/2009/07/ets-ordered-set-select-efficiency.html

-- p

On Sat, 25 Jul 2009, Paul Mineiro wrote:

> hi.  i'm working on improving the query planning in tcerl and i realized i
> might be duplicating effort, so i was hoping to get some insight on how
> ets does it's thing.
>
> suppose i have an ordered_set ets table with key position 1.  a match
> specification like
>
> [ { { '_', '_' }, [], [ '$_' ] } ]
>
> will do a full-table scan but
>
> [ { { { Value, '_' }, '_' }, [], [ '$_' ] } ]
>
> will not, instead it will only scan the range of keys which are tuples
> whose first element is Value.[1]
>
> currently tcerl will also recognize a partially bound prefix key and
> restrict the range of keys considered.  however for an application i'm
> working on i need efficient queries corresponding to match specifications
> that look like
>
> [ { { { '$1', '_' }, '_' },
>     [ { '>', '$1', Lower }, { '<', '$1', Upper } ],
>     [ '$_' ]
>   }
> ]
>
> which ideally would only consider the range of keys defined by tuples
> whose first element is between Lower and Upper.
>
> i'm modified tcerl to detect this condition[2] but now i'm worried i'm
> slowly rewriting some ets function that is already available, has
> less defects, and/or is faster because it's a BIF.
>
> so:
>
>   1) is the match specification analysis in ets this sophisticated?
>   2) if yes, is it exposed reusably?
>
> thanks,
>
> -- p
>
> [1] http://erlang.org/documentation/doc-5.5.1/doc/efficiency_guide/tablesDatabases.html
> [2] http://code.google.com/p/tcerl/source/browse/trunk/tcerl/src/tcbdbmsutil.erl
>