Quelle  gis0geo.cc   Sprache: C

/*****************************************************************************

Copyright (c) 2013, 2015, Oracle and/or its affiliates. All Rights Reserved.
Copyright (c) 2019, MariaDB Corporation.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA

*****************************************************************************/

/**************************************************//**
@file gis/gis0geo.cc
InnoDB R-tree related functions.

Created 2013/03/27 Allen Lai and Jimmy Yang
*******************************************************/

#include "page0types.h"
#include "gis0geo.h"
#include "page0cur.h"
#include "ut0rnd.h"
#include "mach0data.h"

#include <spatial.h>
#include <cmath>

/* These definitions are for comparing 2 mbrs. */

/* Check if a intersects b.
Return false if a intersects b, otherwise true. */
#define INTERSECT_CMP(amin, amax, bmin, bmax) \
(((amin) > (bmax)) || ((bmin) > (amax)))

/* Check if b contains a.
Return false if b contains a, otherwise true. */
#define CONTAIN_CMP(amin, amax, bmin, bmax) \
(((bmin) > (amin)) || ((bmax) < (amax)))

/* Check if b is within a.
Return false if b is within a, otherwise true. */
#define WITHIN_CMP(amin, amax, bmin, bmax) \
(((amin) > (bmin)) || ((amax) < (bmax)))

/* Check if a disjoints b.
Return false if a disjoints b, otherwise true. */
#define DISJOINT_CMP(amin, amax, bmin, bmax) \
(((amin) <= (bmax)) && ((bmin) <= (amax)))

/* Check if a equals b.
Return false if equal, otherwise true. */
#define EQUAL_CMP(amin, amax, bmin, bmax) \
(((amin) != (bmin)) || ((amax) != (bmax)))

/****************************************************************
Functions for generating mbr
****************************************************************/
/*************************************************************//**
Add one point stored in wkb to a given mbr.
@return 0 if the point in wkb is valid, otherwise -1. */
static
int
rtree_add_point_to_mbr(
/*===================*/
 const uchar** wkb,  /*!< in: pointer to wkb,
where point is stored */
 const uchar* end,  /*!< in: end of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr)  /*!< in/out: mbr, which
must be of length n_dims * 2. */
{
 double ord;
 double* mbr_end = mbr + n_dims * 2;

 while (mbr < mbr_end) {
  if ((*wkb) + sizeof(double) > end) {
   return(-1);
  }

  ord = mach_double_read(*wkb);
  (*wkb) += sizeof(double);

  if (ord < *mbr) {
   *mbr = ord;
  }
  mbr++;

  if (ord > *mbr) {
   *mbr = ord;
  }
  mbr++;
 }

 return(0);
}

/*************************************************************//**
Get mbr of point stored in wkb.
@return 0 if ok, otherwise -1. */
static
int
rtree_get_point_mbr(
/*================*/
 const uchar** wkb,  /*!< in: pointer to wkb,
where point is stored. */
 const uchar* end,  /*!< in: end of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr)  /*!< in/out: mbr,
must be of length n_dims * 2. */
{
 return rtree_add_point_to_mbr(wkb, end, n_dims, mbr);
}


/*************************************************************//**
Get mbr of linestring stored in wkb.
@return 0 if the linestring is valid, otherwise -1. */
static
int
rtree_get_linestring_mbr(
/*=====================*/
 const uchar** wkb,  /*!< in: pointer to wkb,
where point is stored. */
 const uchar* end,  /*!< in: end of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr)  /*!< in/out: mbr,
must be of length n_dims * 2. */
{
 uint n_points;

 n_points = uint4korr(*wkb);
 (*wkb) += 4;

 for (; n_points > 0; --n_points) {
  /* Add next point to mbr */
  if (rtree_add_point_to_mbr(wkb, end, n_dims, mbr)) {
   return(-1);
  }
 }

 return(0);
}

/*************************************************************//**
Get mbr of polygon stored in wkb.
@return 0 if the polygon is valid, otherwise -1. */
static
int
rtree_get_polygon_mbr(
/*==================*/
 const uchar** wkb,  /*!< in: pointer to wkb,
where point is stored. */
 const uchar* end,  /*!< in: end of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr)  /*!< in/out: mbr,
must be of length n_dims * 2. */
{
 uint n_linear_rings;
 uint n_points;

 n_linear_rings = uint4korr((*wkb));
 (*wkb) += 4;

 for (; n_linear_rings > 0; --n_linear_rings) {
  n_points = uint4korr((*wkb));
  (*wkb) += 4;

  for (; n_points > 0; --n_points) {
   /* Add next point to mbr */
   if (rtree_add_point_to_mbr(wkb, end, n_dims, mbr)) {
    return(-1);
   }
  }
 }

 return(0);
}

/*************************************************************//**
Get mbr of geometry stored in wkb.
@return 0 if the geometry is valid, otherwise -1. */
static
int
rtree_get_geometry_mbr(
/*===================*/
 const uchar** wkb,  /*!< in: pointer to wkb,
where point is stored. */
 const uchar* end,  /*!< in: end of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr,  /*!< in/out: mbr. */
 int top)  /*!< in: if it is the top,
    which means it's not called
by itself. */
{
 int res;
 uint wkb_type = 0;
 uint n_items;

 /* byte_order = *(*wkb); */
 ++(*wkb);

 wkb_type = uint4korr((*wkb));
 (*wkb) += 4;

 switch ((enum wkbType) wkb_type) {
 case wkbPoint:
  res = rtree_get_point_mbr(wkb, end, n_dims, mbr);
  break;
 case wkbLineString:
  res = rtree_get_linestring_mbr(wkb, end, n_dims, mbr);
  break;
 case wkbPolygon:
  res = rtree_get_polygon_mbr(wkb, end, n_dims, mbr);
  break;
 case wkbMultiPoint:
  n_items = uint4korr((*wkb));
  (*wkb) += 4;
  for (; n_items > 0; --n_items) {
   /* byte_order = *(*wkb); */
   ++(*wkb);
   (*wkb) += 4;
   if (rtree_get_point_mbr(wkb, end, n_dims, mbr)) {
    return(-1);
   }
  }
  res = 0;
  break;
 case wkbMultiLineString:
  n_items = uint4korr((*wkb));
  (*wkb) += 4;
  for (; n_items > 0; --n_items) {
   /* byte_order = *(*wkb); */
   ++(*wkb);
   (*wkb) += 4;
   if (rtree_get_linestring_mbr(wkb, end, n_dims, mbr)) {
    return(-1);
   }
  }
  res = 0;
  break;
 case wkbMultiPolygon:
  n_items = uint4korr((*wkb));
  (*wkb) += 4;
  for (; n_items > 0; --n_items) {
   /* byte_order = *(*wkb); */
   ++(*wkb);
   (*wkb) += 4;
   if (rtree_get_polygon_mbr(wkb, end, n_dims, mbr)) {
    return(-1);
   }
  }
  res = 0;
  break;
 case wkbGeometryCollection:
  if (!top) {
   return(-1);
  }

  n_items = uint4korr((*wkb));
  (*wkb) += 4;
  for (; n_items > 0; --n_items) {
   if (rtree_get_geometry_mbr(wkb, end, n_dims,
         mbr, 0)) {
    return(-1);
   }
  }
  res = 0;
  break;
 default:
  res = -1;
 }

 return(res);
}

/*************************************************************//**
Calculate Minimal Bounding Rectangle (MBR) of the spatial object
stored in "well-known binary representation" (wkb) format.
@return 0 if ok. */
int
rtree_mbr_from_wkb(
/*===============*/
 const uchar* wkb,  /*!< in: wkb */
 uint size,  /*!< in: size of wkb. */
 uint n_dims,  /*!< in: dimensions. */
 double* mbr)  /*!< in/out: mbr, which must
be of length n_dim2 * 2. */
{
 for (uint i = 0; i < n_dims; ++i) {
  mbr[i * 2] = DBL_MAX;
  mbr[i * 2 + 1] = -DBL_MAX;
 }

 return rtree_get_geometry_mbr(&wkb, wkb + size, n_dims, mbr, 1);
}


/****************************************************************
Functions for Rtree split
****************************************************************/
/*************************************************************//**
Join 2 mbrs of dimensions n_dim. */
static
void
mbr_join(
/*=====*/
 double*  a, /*!< in/out: the first mbr,
where the joined result will be. */
 const double* b, /*!< in: the second mbr. */
 int  n_dim) /*!< in: dimensions. */
{
 double*  end = a + n_dim * 2;

 do {
  if (a[0] > b[0]) {
   a[0] = b[0];
  }

  if (a[1] < b[1]) {
   a[1] = b[1];
  }

  a += 2;
  b += 2;

 } while (a != end);
}

/*************************************************************//**
Counts the square of mbr which is the join of a and b. Both a and b
are of dimensions n_dim. */
static
double
mbr_join_square(
/*============*/
 const double* a, /*!< in: the first mbr. */
 const double* b, /*!< in: the second mbr. */
 int  n_dim) /*!< in: dimensions. */
{
 const double* end = a + n_dim * 2;
 double  square = 1.0;

 do {
  square *= std::max(a[1], b[1]) - std::min(a[0], b[0]);

  a += 2;
  b += 2;
 } while (a != end);

 /* Check if finite (not infinity or NaN),
so we don't get NaN in calculations */
 if (!std::isfinite(square)) {
  return DBL_MAX;
 }

 return square;
}

/*************************************************************//**
Counts the square of mbr of dimension n_dim. */
static
double
count_square(
/*=========*/
 const double* a, /*!< in: the mbr. */
 int  n_dim) /*!< in: dimensions. */
{
 const double* end = a + n_dim * 2;
 double  square = 1.0;

 do {
  square *= a[1] - a[0];
  a += 2;
 } while (a != end);

 return square;
}

/*************************************************************//**
Copy mbr of dimension n_dim from src to dst. */
inline
static
void
copy_coords(
/*========*/
 double*  dst, /*!< in/out: destination. */
 const double* src, /*!< in: source. */
 int)
{
 memcpy(dst, src, DATA_MBR_LEN);
}

/*************************************************************//**
Select two nodes to collect group upon */
static
void
pick_seeds(
/*=======*/
 rtr_split_node_t* node,  /*!< in: split nodes. */
 int   n_entries, /*!< in: entries number. */
 rtr_split_node_t** seed_a,  /*!< out: seed 1. */
 rtr_split_node_t** seed_b,  /*!< out: seed 2. */
 int   n_dim)  /*!< in: dimensions. */
{
 rtr_split_node_t* cur1;
 rtr_split_node_t* lim1 = node + (n_entries - 1);
 rtr_split_node_t* cur2;
 rtr_split_node_t* lim2 = node + n_entries;

 double   max_d = -DBL_MAX;
 double   d;

 *seed_a = node;
 *seed_b = node + 1;

 for (cur1 = node; cur1 < lim1; ++cur1) {
  for (cur2 = cur1 + 1; cur2 < lim2; ++cur2) {
   d = mbr_join_square(cur1->coords, cur2->coords, n_dim) -
    cur1->square - cur2->square;
   if (d > max_d) {
    max_d = d;
    *seed_a = cur1;
    *seed_b = cur2;
   }
  }
 }
}

/*************************************************************//**
Select next node and group where to add. */
static
void
pick_next(
/*======*/
 rtr_split_node_t* node,  /*!< in: split nodes. */
 int   n_entries, /*!< in: entries number. */
 double*   g1,  /*!< in: mbr of group 1. */
 double*   g2,  /*!< in: mbr of group 2. */
 rtr_split_node_t** choice,  /*!< out: the next node.*/
 uint16_t*  n_group, /*!< out: 1 or 2 */
 int   n_dim)  /*!< in: dimensions. */
{
 rtr_split_node_t* cur = node;
 rtr_split_node_t* end = node + n_entries;
 double   max_diff = -DBL_MAX;

 for (; cur < end; ++cur) {
  double diff;
  double abs_diff;

  if (cur->n_node != 0) {
   continue;
  }

  diff = mbr_join_square(g1, cur->coords, n_dim) -
         mbr_join_square(g2, cur->coords, n_dim);

  abs_diff = fabs(diff);
  if (abs_diff > max_diff) {
   max_diff = abs_diff;

   /* Introduce some randomness if the record
is identical */
   if (diff == 0) {
    diff = static_cast<double>(ut_rnd_gen() & 1);
   }

   *n_group = 1 + (diff > 0);
   *choice = cur;
  }
 }
}

/*************************************************************//**
Mark not-in-group entries as n_group. */
static
void
mark_all_entries(
/*=============*/
 rtr_split_node_t* node,  /*!< in/out: split nodes. */
 int   n_entries, /*!< in: entries number. */
 uint16_t  n_group) /*!< in: 1 or 2 */
{
 rtr_split_node_t* cur = node;
 rtr_split_node_t* end = node + n_entries;
 for (; cur < end; ++cur) {
  if (cur->n_node != 0) {
   continue;
  }
  cur->n_node = n_group;
 }
}

/*************************************************************//**
Split rtree node.
Return which group the first rec is in. */
int
split_rtree_node(
/*=============*/
 rtr_split_node_t* node,  /*!< in: split nodes. */
 int   n_entries, /*!< in: entries number. */
 int   all_size, /*!< in: total key's size. */
 int   key_size, /*!< in: key's size. */
 int   min_size, /*!< in: minimal group size. */
 int   size1,  /*!< in: size of group. */
 int   size2,  /*!< in: initial group sizes */
 double**  d_buffer, /*!< in/out: buffer. */
 int   n_dim,  /*!< in: dimensions. */
 uchar*   first_rec) /*!< in: the first rec. */
{
 rtr_split_node_t* cur;
 rtr_split_node_t* a = NULL;
 rtr_split_node_t* b = NULL;
 double*   g1 = reserve_coords(d_buffer, n_dim);
 double*   g2 = reserve_coords(d_buffer, n_dim);
 rtr_split_node_t* next = NULL;
 uint16_t  next_node = 0;
 int   i;
 int   first_rec_group = 1;
 rtr_split_node_t* end = node + n_entries;

 if (all_size < min_size * 2) {
  return 1;
 }

 cur = node;
 for (; cur < end; ++cur) {
  cur->square = count_square(cur->coords, n_dim);
  cur->n_node = 0;
 }

 pick_seeds(node, n_entries, &a, &b, n_dim);
 a->n_node = 1;
 b->n_node = 2;

 copy_coords(g1, a->coords, n_dim);
 size1 += a->key_len;
 copy_coords(g2, b->coords, n_dim);
 size2 += b->key_len;

 for (i = n_entries - 2; i > 0; --i) {
  /* Can't write into group 2 */
  if (all_size - (size2 + key_size) < min_size) {
   mark_all_entries(node, n_entries, 1);
   break;
  }

  /* Can't write into group 1 */
  if (all_size - (size1 + key_size) < min_size) {
   mark_all_entries(node, n_entries, 2);
   break;
  }

  pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
  if (next_node == 1) {
   size1 += next->key_len;
   mbr_join(g1, next->coords, n_dim);
  } else {
   size2 += next->key_len;
   mbr_join(g2, next->coords, n_dim);
  }

  next->n_node = next_node;

  /* Find out where the first rec (of the page) will be at,
and inform the caller */
  if (first_rec && first_rec == next->key) {
   first_rec_group = next_node;
  }
 }

 return(first_rec_group);
}

/** Compare two minimum bounding rectangles.
@param mode   comparison operator
   MBR_INTERSECT(a,b)  a overlaps b
   MBR_CONTAIN(a,b)    a contains b
   MBR_DISJOINT(a,b)   a disjoint b
   MBR_WITHIN(a,b)     a within   b
   MBR_EQUAL(a,b)      All coordinates of MBRs are equal
   MBR_DATA(a,b)       Data reference is the same
@param b first MBR
@param a second MBR
@retval 0 if the predicate holds
@retval 1 if the precidate does not hold */
int rtree_key_cmp(page_cur_mode_t mode, const void *b, const void *a)
{
  const byte *b_= static_cast<const byte*>(b);
  const byte *a_= static_cast<const byte*>(a);

  static_assert(DATA_MBR_LEN == SPDIMS * 2 * sizeof(double), "compatibility");

  for (auto i = SPDIMS; i--; )
  {
    double amin= mach_double_read(a_);
    double bmin= mach_double_read(b_);
    a_+= sizeof(double);
    b_+= sizeof(double);
    double amax= mach_double_read(a_);
    double bmax= mach_double_read(b_);
    a_+= sizeof(double);
    b_+= sizeof(double);

    switch (mode) {
    case PAGE_CUR_INTERSECT:
      if (INTERSECT_CMP(amin, amax, bmin, bmax))
        return 1;
      continue;
    case PAGE_CUR_CONTAIN:
      if (CONTAIN_CMP(amin, amax, bmin, bmax))
        return 1;
      continue;
    case PAGE_CUR_WITHIN:
      if (WITHIN_CMP(amin, amax, bmin, bmax))
        return 1;
      continue;
    case PAGE_CUR_MBR_EQUAL:
      if (EQUAL_CMP(amin, amax, bmin, bmax))
        return 1;
      continue;
    case PAGE_CUR_DISJOINT:
      if (!DISJOINT_CMP(amin, amax, bmin, bmax))
        return 0;
      if (!i)
        return 1;
      continue;
    case PAGE_CUR_UNSUPP:
    case PAGE_CUR_G:
    case PAGE_CUR_GE:
    case PAGE_CUR_L:
    case PAGE_CUR_LE:
    case PAGE_CUR_RTREE_LOCATE:
    case PAGE_CUR_RTREE_GET_FATHER:
    case PAGE_CUR_RTREE_INSERT:
      break;
    }
    ut_ad("unknown comparison operator" == 0);
  }

  return 0;
}