RecTree

[Paul Ramsey]

Sandro,
I don’t know if you’re still poking around distance, but I have been too, and here’s a few notes.

- Firstly, with respect to distance vs distance_sqr approaches in the core measures.c, before attacking that I did some micro benchmarking with a simple C program, testing the difference in time to do 10M distance calculations and 10M square distance calculations, and I didn’t see any big difference. I would have thought I’d see something measurable, so either it’s just there or my test was so simple it somehow got washed away.

(For the record, here’s the test program)

  // Generate a random double between 0.0 and 1.0
  double sum = 0;
  double a = 100.0 * (double)random() / RAND_MAX;
  double b = 100.0 * (double)random() / RAND_MAX;
  for (int i = 0; i < 1000000000; i++)
  {
    a += 1;
    b += 1;
    double sq = a*a + b*b;
    double d = sqrt(sq);
    sum += d;
  }
  printf("%g\n", sum);

- Secondly, I have dusted off the old RecTree code, it still compiles and passes tests. In fact, it’s available for testing, it’s just not included in the SQL definition file. You can find the function definitions there though, 

-- Availability: Future
-- CREATE OR REPLACE FUNCTION _ST_DistanceRectTree(g1 geometry, g2 geometry)
--	RETURNS float8
--	AS 'MODULE_PATHNAME', 'ST_DistanceRectTree'
--	LANGUAGE 'c' IMMUTABLE STRICT PARALLEL SAFE
--  _COST_MEDIUM;

-- Availability: Future
-- CREATE OR REPLACE FUNCTION _ST_DistanceRectTreeCached(g1 geometry, g2 geometry)
--	RETURNS float8
--	AS 'MODULE_PATHNAME', 'ST_DistanceRectTreeCached'
--	LANGUAGE 'c' IMMUTABLE STRICT PARALLEL SAFE
--  _COST_MEDIUM;

So you can manually turn on the functionality, see if/how much better it is than the existing functions for your workloads.

I am going to look at trying to make the build a little more memory friendly which should also increase the locality of the tree nodes, which might speed up the scan phase a little (this kind of rework make the point-in-poly code about 15% faster, but no guarantees.)

ATB,

P