WL#9439: InnoDB: Support geographic R-trees

In order to support geographic R-trees, InnoDB must compute bounding boxes and operations on these in the correct spatial reference system.

Currently, InnoDB parses geometry objects and does all bounding box computations separate from the server code. These computations are all Cartesian. This WL moves geometry parsing and bounding box computations for R-trees from InnoDB into the server. With the bounding box computations in the server, InnoDB R-trees will automatically start supporting geographic data when geographic operations are supported by the server.

As a bonus, the geometry parsing is also moved into the server, which makes it possible to have one geometry parser that is used everywhere. However, unifying the geometry parsers is not part of this WL.

So in a nutshell, this worklog would just move the geometry code, related to geometry parsing, computing bounding boxes and operations on them, present in InnoDB to the server so that geographic R-trees can be supported easily in the future without having to change anything in InnoDB. There would be no change in behavior observed as such from this worklog.

Non-Functional Requirements

NF1: InnoDB MUST NOT contain code for parsing geometries, but rely on the server to do that.

NF2: InnoDB MUST NOT contain code for computing bounding boxes of geometries, but rely on the server to do that.

NF3: InnoDB MUST NOT contain code for computing relational operations (within, overlaps, intersects, etc.) of bounding boxes/geometries, but rely on the server to do that.

NF4: The R-tree bounding box interface between InnoDB and the server MUST pass the SRID of the geometries.

NF5: The R-tree bounding box interface between InnoDB and the server MUST be clearly defined in one header file that contains the entire interface and nothing else.

NF6: When computing the bounding box of a geometry, InnoDB MUST pass the geometry string as a whole (SRID+WKB) to the server without parsing it.

NF7: There should not be any performance gain or regression due to this WL.

The InnoDB code present in storage/innobase/gis/gis0geo.cc and storage/innobase/gis/gis0geo.h, containing code for computing bounding box and computing relational operations (within, overlaps, intersects, etc.) of bounding boxes/geometries, is simply moved to the server (sql/gis/srs/rtree_support.h and sql/gis/srs/rtree_support.cc). rtree_support.h will contain only the handler interface between InnoDB and the server and nothing else, and the implementation would be present in rtree_support.cc.

The handler interfaces between the server and InnoDB will be:

1) struct rtr_mbr - memory representation of a minimum bounding rectangle.

2) Interface for computing relational operations - contain, equal, intersect,

  disjoint, and within.

  mbr_contain_cmp()   - Interface to check whether one MBR contains another.
  mbr_equal_cmp()     - Interface to check whether one MBR equals to another.
  mbr_intersect_cmp() - Interface to check whether one MBR intersects another.
  mbr_within_cmp()    - Interface to check whether one MBR is within another.
  mbr_disjoint_cmp()  - Interface to check whether two MBR's are disjoint.

3) mbr_join()

  Interface to join 2 MBR's.

4) mbr_join_area()

  Interface to compute the area of MBR which is the join of a and b. Both a 
  and b are of dimensions n_dim.

5) compute_area()

  Interface to compute the area of MBR of dimension n_dim.

6) get_mbr_from_store()

  Interface to calculate Minimal Bounding Rectangle (MBR) of the spatial
  object stored in geometry storage format (WKB+SRID).
  InnoDB passes SRID+WKB to this interface and this interface parses it and 
  passes SRID and WKB to the server.

7) rtree_area_increase()

  Interface to calculate the increase in area between two MBR's. InnoDB passes 
  the two MBR's.

8) rtree_area_overlapping()

  Interface to calculate overlapping area between two MBR's. InnoDB passes the 
  two MBR's.

Since InnoDB doesn't store SRID values anywhere, 0 is passed by default as SRID to the above interfaces. Storing and passing a valid SRID is a worklog in itself and would be addressed in a separate worklog.

Most of the interface defined in storage/innosbase/gis/gis0geo.cc along with relevant parts of storage/innobase/include/gis0geo.h are moved into sql/gis/rtree_support.cc. sql/gis/rtree_support.h will contain only the interface between the R-tree and the server. These files will be under MySQL Optimizer Team ownership and provided as a service to R-tree implementations in storage engines.

The interfaces between the R-tree and the server, present in sql/gis/rtree_support.h, are as specified in HLS section. Since InnoDB doesn't store SRID values anywhere, 0 is passed by default as SRID to the interfaces. Storing and passing a valid SRID is a worklog in itself and would be addressed in a separate worklog.