Testing of various opclasses for ranges - Mailing list pgsql-hackers

Hackers,

I've tested various opclasses for ranges (including currently in-core one and my patches). I've looked into scholar papers for which datasets they are using for testing. The lists below show kinds of datasets used in papers.

1) "Advanced Indexing Technique for Temporal Data", "Indexing Valid Time Intervals" uses two kinds of datasets:

  a) uniformly distributed start of range and uniformly distributed size of range

  b) uniformly distributed start of range and exponentially distributed size of range

2) "The Time index+: An incremental access structure for temporal databases" uses dataset produced by simulating of objects "life". Each object consists of number of versions which lifetime ranges are adjuncted. Start of object life is uniformly distributed. Object lifetime is normally distributed. Version time is exponentially distributed.

3) "Top-k Queries on Temporal Data"

  a) Datasets of clusters. Each cluster center is normally distributed. Offset of range inside cluster is also normally distributed. Range size is distributed exponentially.

  b) Real-life datasets http://www.cs.ucr.edu/~eamonn/time_series_data/. Unfortunately I can't get password for them ((((

  

4) "Indexing Valid Time Intervals" uses two kinds of datasets

  a) uniformly distributed start of range and exponentially distributed size of range

  b) uniformly distributed start of range and normally distributed size of range

5) "Managing intervals efficiently in object-relational databases", "Segment indexes: dynamic indexing techniques for multi-dimensional interval data"

  a) uniformly distributed start of range and exponentially distributed size of range

  b) uniformly distributed start of range and uniformly distributed size of range

  a) exponentially distributed start of range and exponentially distributed size of range

  b) exponentially distributed start of range and uniformly distributed size of range

Therefore 3 basic distributions are used in synthetic datasets:

1) uniform

2) exponential

3) normal

Datasets can be classified into 3 kinds:

1) simple: ranges are distributed independently

2) clusters: ranges are grouped into clusters

3) lifetime: ranges are produced by life simulation

Each kind of dataset require some distributions for generation:

1) simple: range start and range size

2) clusters: cluster center, range offset, range size

3) lifetime: object lifetime start, object lifetime length, version length

In my testsuite each of 3 distribution is used in each slot. Additionally mean size of range was varied. See attached range_test.php and range_test_schema.sql.

I've merged all 3 patches into 1 (see 2d_map_range_indexing.patch). In this patch following opclasses are available for ranges:

1) range_ops - currently in-core GiST opclass

2) range_ops2 - GiST opclass based on 2d-mapping

3) range_ops_quad - SP-GiST quad tree based opclass

4) range_ops_kd - SP-GiST k-d tree based opclass

There is average results of index build time depending on used operator class.

2d-mapping GiST is longer for build than 1d GiST. It seems to be inevitable because 2d-mapping GiST has to try split in both dimensions and it has more complicated calculations in penalty too. K-d tree is faster for build than quad tree, I don't have convincing explanation why.

There is average number of page hits and average execution in milliseconds for test queries depending on operator and opclass. We can see that 2d-mapping GiST use about 2 times less pages for "<@" operators. However, it use a little more pages in "@>" and "&&" while I expected superiority also for "@>". But average time of query execution is lower for all operators. Probably, it's because consistent function appears to be more efficiently implemented.

SP-GiST uses more pages than GiST. Especially k-d tree. However, some pages could be counted more than once, but I think it's OK to compare SP-GiST opclasses by this parameter between themselves. Also, k-d tree appears to be slower than quad tree.

In order to find why test results don't always meet my expectations I filter tests to show only low-selectivity queries. Now, we can see 2d-mapping GiST is much more dramatically faster than 1d GiST on "<@" and use slightly less amount of pages than 1d GiST. k-d tree appears to be much slower than quad tree and use dramatically more pages. Probably, it is caused by some bug. I will examine it.

You can download full results of testing at http://test.i-gene.ru/uploads/range_test.sql.gz.

------

With best regards,

Alexander Korotkov.