[postgis-devel] Re: geometry stats

[David Blasby]

I looked at the way the new (7.4) gist_rtree works.  Its changed since 
7.2.  In fact, its almost morphed itself back to what it looked like in 7.1.

Basically, they use different strategies based on where they are in the 
search - either at internal nodes in the tree or in leafs.  GiST trees 
are a little different than normal binary search trees (for lots of 
reasons, but I want to emphasis one).  Here's the last portion of a tree.


           ....
          /
         /
       'J'
       / \
      /   \
     /     \
  Ant     Spider

The two leafs ("Ant" and "Spider") would represent actual database rows. 
  Unlike most binary trees, the internal nodes are *not* actual database 
rows.  Here "J" is 1/2 way between 'Ant' and 'Spider'.

In the Rtree GiST, the internal node is a BOX that contain all the boxes 
below them in the tree.

The 7.4 codes uses this for *internal* BOXes (unioned boxes):

  switch (strategy)
     {
         case RTLeftStrategyNumber:
         case RTOverLeftStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overleft, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTOverlapStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overlap, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTOverRightStrategyNumber:
         case RTRightStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_right, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTSameStrategyNumber:
         case RTContainsStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_contain, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTContainedByStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overlap, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         default:
             retval = FALSE;
     }



and this (more exact) for leafs (ie. real geometries):



    switch (strategy)
     {
         case RTLeftStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_left, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTOverLeftStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overleft, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTOverlapStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overlap, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTOverRightStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_overright, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTRightStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_right, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTSameStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_same, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTContainsStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_contain, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         case RTContainedByStrategyNumber:
             retval = DatumGetBool(DirectFunctionCall2(box_contained, 
PointerGetDatum(key), PointerGetDatum(query)));
             break;
         default:
             retval = FALSE;
     }


I'm not sure why they also have a RECHECK, unless the polygon type's 
actual contains() function checks for true containment.



So;

1. There shouldnt be anything wrong with the && operator.  If anyone's 
ever seen an example of the index and seq scan returning different 
results, SEND ME THE TEST.  I'm going to write a simple program to test 
the current one (as I outlined earlier today).

2. We can fix the '@~'-like operators by either (a) adding RECHECK to 
the definition or (b) adding the leaf consistent function (as in the 
rtree_gist 7.4 implementation shown above) or (c) both.


dave