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

Subject: Re: [Boost-users] [Multi-Index] Skip-Scan "virtual" ordered-non-unique index on top of composite ordered-unique index
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2013-11-28 14:37:48

Dominique Devienne <ddevienne <at> gmail.com> writes:

> 
> We have BMIs of entries with complex composite "natural-keys".
>  [...]
> After recently reading
> http://www.sqlite.org/draft/optoverview.html#skipscan%c2%a0and 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).

This is an interesting idea! Without making any internal change to
Boost.MultiIndex indices, a decent approximation to skip-scanning can
be achieved. The code pasted at the bottom provides a function skip_scan
that you can use like this

  // scan elements with keys *,1,2,3
  skip_scan<1>(
    c,[](const element& v){std::cout<<v<<" ";},
    1,2,3);

  // scan elements with keys *,*,2,3
  skip_scan<2>(
    c,[](const element& v){std::cout<<v<<" ";},
    2,3);

Whether this is good enough would require some profiling, but at least
it saves you some additional indices. If you decide to test the thing
please tell me back.

Code requires C++11 support :-/

Joaquín M López Muñoz
Telefónica Digital

#include <boost/tuple/tuple.hpp>
#include <boost/ref.hpp>
#include <utility>

// index_sequence code stolen from
// http://stackoverflow.com/questions/19783205/
//    why-sizeof-t-so-slow-implement-c14-make-index-sequence-without-sizeof

template<int...> struct index_sequence{using type=index_sequence;};
template<typename T> using invoke=typename T::type;
template<typename T,typename U> struct concate;
template<int ...i,int ... j>
struct concate<index_sequence<i...>,index_sequence<j...>>:
  index_sequence<i...,(j+sizeof...(i))...>{};
template<int n>
struct make_index_sequence_help :
  concate< 
    invoke<make_index_sequence_help<n/2>>,
    invoke< make_index_sequence_help<n-n/2>>
  >
{};
template<> struct make_index_sequence_help<0>:index_sequence<>{};
template<> struct make_index_sequence_help<1>:index_sequence<0>{};

template<int n> using make_index_sequence=invoke<make_index_sequence_help<n>>;

template<int N,typename CompositeKey,typename Value>
auto key(const CompositeKey& ck,const Value& v)->decltype(
  boost::tuples::get<N>(ck.key_extractors())(v))
{
  return boost::tuples::get<N>(ck.key_extractors())(v);
}
 
template<int N,typename Container,typename F,typename... Args,int... I>
void skip_scan_helper(
  const Container& c,F f,index_sequence<I...>,Args&&... args)
{
  for(auto it=c.begin(),it_end=c.end();it!=it_end;){
    for(auto rng=c.equal_range(
          boost::make_tuple(
            boost::cref(key<I>(c.key_extractor(),*it))...,
            std::forward<Args>(args)...));
        rng.first!=rng.second;++rng.first){
      f(*rng.first);
    }
    it=c.upper_bound(
      boost::make_tuple(boost::cref(key<I>(c.key_extractor(),*it))...));
  }
}

template<
  int N,typename Container,typename F,
  typename... Args,typename Indices=make_index_sequence<N>
>
void skip_scan(const Container& c,F f,Args&&... args)
{
  skip_scan_helper<N>(c,f,Indices(),std::forward<Args>(args)...);
}

// testing

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <iostream>

using namespace boost::multi_index;

struct element
{
  int x0,x1,x2,x3,x4;
};

std::ostream& operator<<(std::ostream& os,const element& v)
{
  os<<"("<<v.x0<<","<<v.x1<<","<<v.x2<<","<<v.x3<<","<<v.x4<<")";
  return os;
}

typedef multi_index_container<
  element,
  indexed_by<
    ordered_non_unique<
      composite_key<
        element,
        member<element,int,&element::x0>,
        member<element,int,&element::x1>,
        member<element,int,&element::x2>,
        member<element,int,&element::x3>,
        member<element,int,&element::x4>
      >
    >
  >
> multi_t;

int main()
{
  multi_t c={
    {0,1,2,3,4},
    {0,1,2,3,5},
    {0,1,3,4,0},
    {1,0,0,0,0},
    {1,1,2,3,0},
    {1,1,2,3,0},
    {2,1,2,1,0},
    {2,2,2,3,0},
  };
  
  skip_scan<1>(
    c,[](const element& v){std::cout<<v<<" ";},
    1,2,3);
  std::cout<<"\n";

  skip_scan<3>(
    c,[](const element& v){std::cout<<v<<" ";},
    3);
  std::cout<<"\n";

  skip_scan<2>(
    c,[](const element& v){std::cout<<v<<" ";},
    2,3);
  std::cout<<"\n";
}