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 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).
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"; }