[Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index

Subject: [Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2013-11-28 08:49:34

We have BMIs of entries with complex composite "natural-keys". For example:

    typedef boost::multi_index_container<
        FooIdPtr, // FYI: boost::shared_ptr<FooId>
        bmi::indexed_by<
            EntityIndex<ByUid>::unique, // FYI: Surrogate/Primary Key
            EntityIndex<ByNKey>::of<FooId>::unique, // FYI: Natural Key

            // additional indexes by type, name and parent
            EntityIndex<ByType>::non_unique,
            EntityIndex<ByName>::non_unique,
            EntityIndex<ByParent>::non_unique
        >
    > Impl;

The EntityIndex template utility simply factors the index definitions used
in several BMIs. For example

template <> struct EntityIndex<ByNKey> {
    template <typename T_IDENT> struct of {
        typedef hashed_unique< // natural key (logical primary key)
            tag<ByNKey>, identity< shared_ptr<T_IDENT> >,
            EntityIdHash<T_IDENT>, EntityIdPred<T_IDENT>
        > unique;
    };
};

template <> struct EntityIndex<ByParent> {
    typedef hashed_non_unique<
        tag<ByParent>,
        BOOST_MULTI_INDEX_CONST_MEM_FUN(
            EntityId, const Uid&, parent_uid // FYI: EntityId is the base
class of FooId and co.
        )
    > non_unique;
};

After recently reading
http://www.sqlite.org/draft/optoverview.html#skipscan and
its Skip-Scan optimization, I wondered about changing my ByNKey unique
index from hashed to ordered, and thought that in theory, I could perhaps
avoid the maintenance and memory cost of the additional type+name+parent
indexes, since all three are subsets of the ByNKey unique index, and using
a similar skip-scan strategy, which might/would still provide reasonable
performance, at least better than no index at all (i.e. a full scan).

I know BMI does not provide this of course, but do you think Joaquin that
it would be possible to one-day add such "virtual" ordered non-unique
indexes on top of an existing ordered (possibly unique) composite index? Of
course in this case, the composite'ness is hidden inside FooId, and not
exposed to BMI (it used to be a true BMI composite index, but modeling the
identity as an object made more sense and simplified things), so whether an
index is a subset of another would need to be "configurable" in some way,
to yield a "compatible key" with the right "prefix" keys to skip to the
next "sub-range" to scan (hopefully that makes sense...).

I think I would be able to write custom code on top of a ByNKey
ordered-non-unique index to implement a subset of the functionality a true
BMI ordered non-unique index provides, for my own needs (with some
difficulty, but feasible nonetheless), but the kind of template
meta-programming BMI uses to implements its indexes is beyond my current
skill level, which is why I'm posting to see what the experts (i.e.
Joaquin) thinks about this Skip-Scan virtual indexes idea.

Thanks, --DD