Re: [boost] [MultiIndex] proposal - delayed index initialisationandmaintenance

From: Neil Hunt (boost_at_[hidden])
Date: 2005-12-20 22:20:30

Joaquín Mª López Muñoz wrote:
> Hello Neil, excuse my late answering.

Thanks Joaquín. No worries. Appreciate your time. And your repsonse was 
excellent.

> 
> Lazy indices, right? Leaving implementation complexities aside (this
> doesn't look trivial to write efficiently) 

I thought as much, hence the "wild idea". :)

> I wonder whether the motivation
> is consistent: if you only need one index at a time, why using a
> multi-index container? 

You picked up the reason later on. As well as the user's column 
selection, a "fixed" index is held which represents the database table's 
key, used by other code.

> You can always have a vector and sort it
> as needed depending on the column clicked by the user.

Since one of my goals was to present the "fastest" sort (visually) to 
the user possible, I was trying to avoid recalculation of the indices 
when columns are re-clicked. (I know I am over-engineering my program.)

> An in-between case is when you have several fixed indices (say, those
> given the most usage) plus many more that are seldom selected. Even
> in this case, lazy indices are just half-way to an optimal solution: even
> if you save computing time, there's still a lot of wasted space: nodes
> must allocate space for all index headers, regardless of whether the
> indices use them right away or lazily.
I realised this after I posted.

> Thinking out loud, the "some fixed, some dynamic indices" situation
> can be handled in a number of ways:
> 1. Allowing ordered indices to change their (key extractor, comparer)
> pair and re-sorting appropriately. This can make an index kind of
> multi-column.
If I can compare this (1) to my current solution(V) written before I 
knew of MultiIndex:
vector(columns) of vectors(index) of iterators into the list of rows,
where accessing of a given index for the first time builds the index.

(1) Pros - efficient storage(none) of unaccessed indices, auto update of 
fixed and dynamic indices upon row change.
(1) Cons - recalculation of index on each column change.

(V) Pros - efficient storage(empty vector) of unintialised indices. 
Index is cached between column clicks.
(V) Cons - (in my time-abbreviated solution)updating a row clears all 
indices, until next accessed.

I guess I was hoping for the auto-updating capability of MultiIndex. But 
it seems that would come with the cost of storage for each index, 
whether they are lazy or not, or the loss of caching of indices.

> 2. Using a random access index for supporting the dynamic columns.
> The index can be sorted according to the current column. You can
> already try this approach, there's a preview of random access
> indices in the vault.
I don't understand how the random access part of the index helps with 
laziness. But I can appreciate the operator[] facility for what I am doing.

> 3. Dynamic multi-index containers. Sometime in 2006 I plan to
> begin studying how to design such a beast, still uncertain about
> its feasibility and value.
I too am unsure about it's value. But it is an interesting task.

BTW, Thanks for a great library and I am very much looking forward to 
notifying indices.

Neil