On Thu, Aug 11, 2011 at 10:21 AM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:
Split of an internal node works like this:
1. Gather all the existing tuples on the page, plus the new tuple being inserted.
2. Call picksplit on the tuples, to divide them into pages
3. Go through all tuples on the buffer associated with the page, and divide them into buffers on the new pages. This is done by calling penalty function on each buffered tuple.
I wonder if it would be better for index quality to pass the buffered tuples to picksplit in the 2nd step, so that they too can affect the split decision. Maybe it doesn't make much difference in practice..
I had this idea. But:
1) Buffer contain much more tuples than page plus new tuple.
2) Picksplit method can easily be quadratic for example.
Let's see the complexity of picksplit algorithms:
1) geometric datatypes (point, box etc) - O(n) (BTW, I have serious doubts about it, i.e. O(n*log(n)) algorithm can be in times better in many cases)
2) pg_trgm and fts - O(n^2)
3) seg - O(n*log(n))
4) cube - O(n^2)
Thus, I believe such feature should be an optional. We can try it as add-on patch.
------
With best regards,
Alexander Korotkov.