mnesia:match_object() on an ordered_set

[Ulf Wiger]

On Fri, 25 Apr 2003, Ulf Wiger wrote:

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

Actually, given the current implementation of
mnesia:match_object/2, the order is _not_ preserved, even
within the fragment. ;-)

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

Using a custom fragmentation scheme, one may distribute
objects such that e.g. all objects belonging to one
particular document fall into the same fragment; then there
is some point to having an ordered_set fragment. It's
still quite feasible to have a hashing algorithm at the top,
so that the order among documents is undefined, but the
order _within_ documents is well defined.

Fixing mnesia:match_object/2 for ordered sets should make
this scheme work well.

(A random thought: if an ets:match_object/3 could allow one
to specify a target ets table, a corresponding
mnesia:match_object/3 run over a fragmented table could drop
all found objects in an ordered_set table, and the problem
would be solved. This ets:match_object/3 function would also
have very pleasant memory characteristics, since it would
not build large heap structures.)

/Uffe
-- 
Ulf Wiger, Senior Specialist,
   / / /   Architecture & Design of Carrier-Class Software
  / / /    Strategic Product & System Management
 / / /     Ericsson AB, Connectivity and Control Nodes