mnesia:match_object() on an ordered_set

[Hakan Mattsson]

On Fri, 25 Apr 2003, Ulf Wiger wrote:

Uffe> On Fri, 25 Apr 2003, Ulf Wiger wrote:
Uffe> 
Uffe> >On Thu, 24 Apr 2003, Hakan Mattsson wrote:
Uffe> >
Uffe> >>On Thu, 24 Apr 2003, Ulf Wiger wrote:
Uffe> >>
Uffe> >>Uffe> Given the current implementation of mnesia:match_object(), I
Uffe> >>Uffe> don't think preserving the order would have to impact
Uffe> >>Uffe> performance, esp. not on large sets (and on small sets, I
Uffe> >>Uffe> don't think it matters.)
Uffe> >>
Uffe> >>For fragmented tables it would have a tremendous impact, as
Uffe> >>the order only is preserved within each fragment. In order
Uffe> >>to return an ordered result, it would require a quite
Uffe> >>substantial sort operation.
Uffe> >
Uffe> >True, unless one writes a custom mnesia_frag_hash callback
Uffe> >which manages fragments with some global order. This is
Uffe> >what I had in mind to do with XML Query for Mnesia.
Uffe> 
Uffe> Actually, given the current implementation of
Uffe> mnesia:match_object/2, the order is _not_ preserved, even
Uffe> within the fragment. ;-)

With "as the order only is preserved within each fragment", I was
referring to the persistent order, not the transient order during the
transaction. Sorry for the confusion.

Uffe> As to preserving a global order, mnesia_frag in its default
Uffe> implementation makes this hard. On the other hand, what's
Uffe> the point of having multiple ordered set fragments if
Uffe> objects are distributed among the fragments using a hashing
Uffe> algorithm?  (:  Each ordered_set fragment will contain only
Uffe> a pseudo-random subset of the global set, so it's doubtful
Uffe> whether there is any point to the local ordering anyway.

In most cases it would not be any point. But if you have an access
pattern with frequent matching of a partitially bound key, it could
make a big difference. You would in the standard case (using the
default hash function) still need to perform the match in all
fragments, but ets would not need to perform an exhaustive search of
the entire table.

Uffe> Using a custom fragmentation scheme, one may distribute
Uffe> objects such that e.g. all objects belonging to one
Uffe> particular document fall into the same fragment; then there
Uffe> is some point to having an ordered_set fragment. It's
Uffe> still quite feasible to have a hashing algorithm at the top,
Uffe> so that the order among documents is undefined, but the
Uffe> order _within_ documents is well defined.
Uffe> 
Uffe> Fixing mnesia:match_object/2 for ordered sets should make
Uffe> this scheme work well.

If the documented behavior of mnesia:match_object/2 on an ordered_set,
is changed to also guarantee an ordered result, then this implies that
this is consequently implemented. The semantics should be the same for
both ordinary tables and fragmented tables and not rely on any
customized fragmentation scheme.

/Håkan

---
Håkan Mattsson
Ericsson
High Availability Software, DBMS Internals
http://www.ericsson.com/cslab/~hakan/