R-tree to be available in mdds

[michael.meeks@xxxxxxxxxxxxx (Michael Meeks)]

Hi Kohei,

On 31/07/18 01:06, Kohei Yoshida wrote:
> I can think of many areas where R-tree could be used inside the
> libreoffice code base, but one area I am particularly interested in
> is formula dependency tracking, especially those that involve cell
> ranges.  I suspect that, if implemented correctly, the use of R-tree
> could improve the query speed and also potentially minimize the
> complexity of the range-based listener-broadcaster handling on the
> libreoffice side (by moving the complexity of managing the data
> structure into mdds).  Also, by using R-tree to manage formula
> dependency data, we could in theory merge all of cell-to-cell,
> cell-to-range, range-to-cell and range-to-range dependency tracking
> into a single data structure, which to me is a very attractive
> proposition.

	Sounds good to me. Particularly since we can now handle huge spans of
single-cell FormulaGroup dependencies with a single range entry in the
range / dependency machine instead of a very large number of single
dependencies on each cell (which in the past were a performance
nightmare to create, manage and cleanup). I assume that we also do the
same for large numbers of overlapping sliding ranges (?). My hope is
that if this goes well - we could consider removing the SvtListener
base-class to shrink the FormulaCell and make it even simpler.

	I'm also fairly convinced that our dependency tracking structures don't
need to be precise (cf. the big formula-group sharing wins) but that
dependency notifications should be filtered against the formula tokens
themselves as a 2nd step (as we do now =) before dirtying cells. I'd
also love to do that dirtying on a column/span basis =)

> Now, this all sounds good, but I'm fully aware that I'm being overly
> optimistic not to mention biased, and it's entirely possible that I'm
> wrong, and using R-tree in range-based dependency tracking would end
> up in more pain and less gain.

	I hope it should be reasonably easy to test replacing the bcaslot
mechanism as a first step - and benchmarking some smaller unit-test for
memory & time against that.

>  So, my current plan is to experiment
> this idea of mine in the ixion library [3] first, then if it works
> well there, we can re-visit it here perhaps with more confidence.  I
> just wanted to throw this idea on this list early, and see what you
> guys think.

	Love it =)

		Michael.

-- 
michael.meeks at collabora.com <><, GM Collabora Productivity
Hangout: mejmeeks at gmail.com, Skype: mmeeks
(M) +44 7795 666 147 - timezone usually UK / Europe