Re: Double sorting split patch

Path without allocating extra bytes is attached.
I run some more detailed tests on geonames and two smaller datasets from
rtreeportal.org.
Test tables are following:
1) test1 - geonames
2) test2 - California Roads, containing the MBRs of 2,249,727 streets
3) test3 - Tiger Streams, containing the MBRs of 194,971 streams
Scripts for test queries generation and execution are attached
(scripts.tar.gz).

Build times are given in the following table:
New linear Double sorting
test1 277.889630 273.766355
test2 73.262561 75.114079
test3 4.251563 4.425139
As we can see, build times differ insignificantly.

Index sizes are given in the following table:
New linear Double sorting
test1 572383232 578977792
test2 179929088 178569216
test3 15409152 15532032
As we can see, index sizes differ insignificantly.

Data about index quality testing are in the table test_results of the
following structure:
tablename - name of the queried table
count - actual count of rows matching query
nominal_count - count of rows matching query which test generator tried to
provide (test generator not always can create test query which return
exactly same amount of rows as it was expected)
strategy - split strategy: 1 - new liner split(current), 2 - double
sorting(this patch)
hits - number of pages hits for query execution.

Raw data are in the attachment (test_result.sql.gz). Report is below.
test=# select tablename, nominal_count, round(avg(count),2) as avg_count,
strategy, round(avg(hits),2) as avg_hits from test_results group by
tablename, nominal_count, strategy order by tablename, nominal_count,
strategy;
tablename | nominal_count | avg_count | strategy | avg_hits
-----------+---------------+-----------+----------+----------
test1 | 1 | 4.87 | 1 | 19.94
test1 | 1 | 4.87 | 2 | 6.46
test1 | 10 | 11.07 | 1 | 23.95
test1 | 10 | 11.07 | 2 | 7.36
test1 | 100 | 101.36 | 1 | 43.30
test1 | 100 | 101.36 | 2 | 10.19
test1 | 1000 | 998.70 | 1 | 86.48
test1 | 1000 | 998.70 | 2 | 24.21
test2 | 1 | 1.32 | 1 | 8.67
test2 | 1 | 1.32 | 2 | 5.99
test2 | 10 | 11.32 | 1 | 9.40
test2 | 10 | 11.32 | 2 | 6.71
test2 | 100 | 102.93 | 1 | 13.10
test2 | 100 | 102.93 | 2 | 9.02
test2 | 1000 | 999.67 | 1 | 32.16
test2 | 1000 | 999.67 | 2 | 23.51
test3 | 1 | 0.99 | 1 | 6.03
test3 | 1 | 0.99 | 2 | 4.32
test3 | 10 | 9.95 | 1 | 7.52
test3 | 10 | 9.95 | 2 | 5.09
test3 | 100 | 99.92 | 1 | 10.73
test3 | 100 | 99.92 | 2 | 7.73
test3 | 1000 | 999.75 | 1 | 27.47
test3 | 1000 | 999.75 | 2 | 22.44
(24 rows)

As we can see, double sorting split outperfoms new linear split in all the
presented cases. Difference in test2 and test3 is not so big as it is in
test1. It can be explained by fact that test2 and test3 are smaller than
test1.

------
With best regards,
Alexander Korotkov.