Re: Yet another fast GiST build

> 7 сент. 2020 г., в 19:10, Heikki Linnakangas <hlinnaka@iki.fi> написал(а):
> 
> On 07/09/2020 13:59, Pavel Borisov wrote:
>>>>> I suppose there is a big jump in integer value (whether signed or
>>>>> unsigned) as you cross from positive to negative floats, and then the
>>>>> sort order is reversed.  I have no idea if either of those things is a
>>>>> problem worth fixing.  That made me wonder if there might also be an
>>> 
>>> I took a stab at fixing this, see attached patch (applies on top of your
>>> patch v14).
>>> 
>>> To evaluate this, I used the other attached patch to expose the zorder
>>> function to SQL, and plotted points around zero with gnuplot. See the
>>> attached two images, one with patch v14, and the other one with this patch.
>> 
>> I'd made testing of sorted SpGist build in cases of points distributed only
>> in 2d quadrant and points in all 4 quadrants and it appears that this
>> abnormality doesn't affect as much as Andrey supposed. But Heikki's patch
>> is really nice way to avoid what can be avoided and I'd like it is included
>> together with Andrey's patch.
> 
> Thanks! Did you measure the quality of the built index somehow? The 
> ordering shouldn't make any difference to the build speed, but it 
> affects the shape of the resulting index and the speed of queries 
> against it.
I've tried to benchmark the difference between build time v14 and v15. v15 seems to be slightly slower, but with negligible difference.

> I played with some simple queries like this:
> 
> explain (analyze, buffers) select count(*) from points_good where p <@ 
> box(point(50, 50), point(75, 75));
To observe IndexScan difference query should touch 4 quadrants. i.e. search within ((-25,-25),point(25,25))

> and looking at the "Buffers" line for how many pages were accessed. 
> There doesn't seem to be any consistent difference between v14 and my 
> fix. So I concur it doesn't seem to matter much.
> 
> 
> I played some more with plotting the curve. I wrote a little python 
> program to make an animation of it, and also simulated how the points 
> would be divided into pages, assuming that each GiST page can hold 200 
> tuples (I think the real number is around 150 with default page size). 
> In the animation, the leaf pages appear as rectangles as it walks 
> through the Z-order curve. This is just a simulation by splitting all 
> the points into batches of 200 and drawing a bounding box around each 
> batch. I haven't checked the actual pages as the GiST creates, but I 
> think this gives a good idea of how it works.
> The animation shows that there's quite a lot of overlap between the 
> pages. It's not necessarily this patch's business to try to improve 
> that, and the non-sorting index build isn't perfect either. But it 
> occurs to me that there's maybe one pretty simple trick we could do: 
> instead of blindly filling the leaf pages in Z-order, collect tuples 
> into a larger buffer, in Z-order. I'm thinking 32 pages worth of tuples, 
> or something in that ballpark, or maybe go all the way up to work_mem. 
> When the buffer fills up, call the picksplit code to divide the buffer 
> into the actual pages, and flush them to disk. If you look at the 
> animation and imagine that you would take a handful of pages in the 
> order they're created, and re-divide the points with the split 
> algorithm, there would be much less overlap.

Animation looks cool! It really pins the inefficiency of resulting MBRs.
But in R*-tree one of Beckman's points was that overlap optimisation worth doing on higher levels, not lower.
But we can do this for splits on each level, I think. We do not know tree depth in advance to divide maintenance workmem among level.. But, probably we don't need to, let's allocate half to first level, quarter to second, 1/8 to third etc until it's one page. Should we take allocations inside picksplit() into account?
The more I think about it the cooler idea seem to me.

BTW I've found one more bug in the patch: it writes WAL even for unlogged tables. I'm not sending a patch because changes are trivial and currently we already have lengthy patchset in different messages.
Also, to avoid critical section we can use log_new_page() instead of log_buffer().


Thanks!

Best regards, Andrey Borodin.