[erlang-questions] Mnesia sorting/limiting

[Barry Mitchelson]

On Thu, Jun 11, 2009 at 12:18 AM, Richard O'Keefe<ok@REDACTED> wrote:
>
> On 10 Jun 2009, at 8:30 pm, Ola Andersson A wrote:
>
>> I was surprised to discover that there is no priority queue
>> implementation in OTP.
>
> You will find an implementation of skew heaps in
> http://erlang.org/pipermail/erlang-questions/2007-August/028769.html
>
> It was on the first page of results from a Google search for
> (priority queues Erlang).
>
> According to that thread as stored at Nabble, the use of gb_trees
> for priority queues was proposed by Ulf Wiger.
>
> There is a paper "Optimal Purely Functional Priority Queues" by
> Brodal and Okasaki at
> http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf
> which it might be interesting to translate into Erlang; that
> paper uses ML, which is strict like Erlang, not lazy like Haskell.
> However, I'd draw your attention to a sentence in that paper:
> "Our data structure is reasonably ecient in practice;
> however, there are several competing data structures that, although
> not asymptotically optimal, are somewhat faster than ours in practice."
>
> We had a visitor here for a month or two a couple of years ago who
> was interested in priority queue algorithms.  He was evalluating a
> recent theoretically improved algorithm, and was quite pleased that
> his implementation of it was _by actual measurement_ faster than
> several other moderately recent contenders.  I said "why aren't
> you including the old heap-in-an-array data structure in your
> benchmarks?  I think you really OUGHT to include the old heap-in-
> an-array data structure in your benchmarks!"  So he did.  And it
> was about 10 times faster than the _theoretically_ better ones.
>
> If all you need is new(), empty(), insert(), find_min(), and
> remove_min(), something like skew heaps or perfectly balanced
> heaps will probably be hard to beat.  If you need fancier things
> like O(1) meld(), then you will need something like the
> Brodal/Okasaki data structure.
>

Thanks for the interesting answers, aside from this specific problem,
the more general question I'm trying to find an answer is how to
select data from an mnesia table ordered by a certain element and
limited without having to go through the entire table when I perform
the sort. I'm not sure if I'm trying to shoehorn my SQL thinking into
this, or if I'm not aware of the solution.

Thanks,

Barry