Re: Fast insertion indexes: why no developments

On 30 October 2013 11:23, Leonardo Francalanci <m_lists(at)yahoo(dot)it> wrote:
>> What is the reason for needing such fast access to individual groups
>> of records? Sure sounds like the NSA or similar ;-)
>
>
> Users need to search all calls originated from/to a user or from/to a specific mobile phone to answer/analyze customers' probl... ok, I give up: I work for the NSA ;)
>
>> In terms of generality, do you think its worth a man year of developer
>> effort to replicate what you have already achieved? Who would pay?
>
>
> 1) I haven't achieved what I need: realtime indexing. I can't query the "current 15 minutes" table efficiently. Plus, K*log(N) is not that great when you have a lot of K.
> 2) I'm not suggesting that this is top priority. I'm asking if there's something else, other than "we don't have time for this", that I don't know. In fact, I don't even know if those indexes types would really help in my (specific) case. That's why my original question was "why aren't there developments in this area": I didn't mean to imply someone should do it. I just wanted to know if those indexes were already discussed (and maybe dismissed for some reason) in the past...

OK, I understand now.

LSM-trees seem patent free, since open source implementations exist.
The main concept is to partition the index into multiple trees, so
that the current insertion sub-tree fits more easily in memory. That
sounds good and was exactly the solution I'd come up with as well,
which is a good cross check. It leads to a slow increase in index
response times, but we could offset that by having minimum values on
each subtree and using partitioning logic as with a minmax index.

LSM-tree also covers the goal of maintaining just 2 sub-trees and a
concurrent process of merging sub-trees. That sounds like it would
take a lot of additional time to get right and would need some
off-line process to perform the merge.

Please somebody advise patent status of Y-trees otherwise I wouldn't bother.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services