[erlang-questions] Re: ets select match specification analysis

[Paul Mineiro]

Well you can grab the etsselect module in the blog post and try in it the
shell.  I'll do this one for demonstration purposes.

----------
% erl
Erlang (BEAM) emulator version 5.6.5 [source] [smp:2] [async-threads:0]
[kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
1> etsselect:select_time ([ { { '$1', bar }, [ { '>=', '$1', { const, {
foo, 1, 0 } } }, { '=<', '$1', { const, { foo, 1, 10 } } } ], [ '$_' ] }
]).
[{5,5.44},
 {25,9.56},
 {125,29.01},
 {625,144.73},
 {3125,515.0666666666667},
 {15625,2731.8333333333335},
 {78125,15812.533333333333},
 {390625,79042.6},
 {1953125,409633.5}]
--------

Verdict: full table scan.

-- p

On Sun, 26 Jul 2009, Tom McNulty wrote:

> Hi Paul
>
> I'm curious to see how a purely range based query will stack up
> against those results. That is, ranging over the entire key, as
> opposed to a partially bound key.  I would be quite surprised if this
> also resulted in a full table scan.
>
> -Tom
>
> On 26-Jul-09, at 2:01 PM, Paul Mineiro wrote:
>
> > 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
> >>
> >
> >
> > ________________________________________________________________
> > erlang-questions mailing list. See http://www.erlang.org/faq.html
> > erlang-questions (at) erlang.org
> >
>
>