PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ g_box_consider_split()

static void g_box_consider_split ( ConsiderSplitContext context,
int  dimNum,
float  rightLower,
int  minLeftCount,
float  leftUpper,
int  maxLeftCount 
)
inlinestatic

Definition at line 1692 of file gserialized_gist_2d.c.

1695 {
1696  int leftCount,
1697  rightCount;
1698  float4 ratio,
1699  overlap;
1700  float range;
1701 
1702  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1703  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1704  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1705 
1706  /*
1707  * Calculate entries distribution ratio assuming most uniform distribution
1708  * of common entries.
1709  */
1710  if (minLeftCount >= (context->entriesCount + 1) / 2)
1711  {
1712  leftCount = minLeftCount;
1713  }
1714  else
1715  {
1716  if (maxLeftCount <= context->entriesCount / 2)
1717  leftCount = maxLeftCount;
1718  else
1719  leftCount = context->entriesCount / 2;
1720  }
1721  rightCount = context->entriesCount - leftCount;
1722 
1723  /*
1724  * Ratio of split - quotient between size of lesser group and total
1725  * entries count.
1726  */
1727  ratio = ((float4) Min(leftCount, rightCount)) /
1728  ((float4) context->entriesCount);
1729 
1730  if (ratio > LIMIT_RATIO)
1731  {
1732  bool selectthis = false;
1733 
1734  /*
1735  * The ratio is acceptable, so compare current split with previously
1736  * selected one. Between splits of one dimension we search for minimal
1737  * overlap (allowing negative values) and minimal ration (between same
1738  * overlaps. We switch dimension if find less overlap (non-negative)
1739  * or less range with same overlap.
1740  */
1741  if (dimNum == 0)
1742  range = context->boundingBox.xmax - context->boundingBox.xmin;
1743  else
1744  range = context->boundingBox.ymax - context->boundingBox.ymin;
1745 
1746  overlap = (leftUpper - rightLower) / range;
1747 
1748  /* If there is no previous selection, select this */
1749  if (context->first)
1750  selectthis = true;
1751  else if (context->dim == dimNum)
1752  {
1753  /*
1754  * Within the same dimension, choose the new split if it has a
1755  * smaller overlap, or same overlap but better ratio.
1756  */
1757  if (overlap < context->overlap ||
1758  (overlap == context->overlap && ratio > context->ratio))
1759  selectthis = true;
1760  }
1761  else
1762  {
1763  /*
1764  * Across dimensions, choose the new split if it has a smaller
1765  * *non-negative* overlap, or same *non-negative* overlap but
1766  * bigger range. This condition differs from the one described in
1767  * the article. On the datasets where leaf MBRs don't overlap
1768  * themselves, non-overlapping splits (i.e. splits which have zero
1769  * *non-negative* overlap) are frequently possible. In this case
1770  * splits tends to be along one dimension, because most distant
1771  * non-overlapping splits (i.e. having lowest negative overlap)
1772  * appears to be in the same dimension as in the previous split.
1773  * Therefore MBRs appear to be very prolonged along another
1774  * dimension, which leads to bad search performance. Using range
1775  * as the second split criteria makes MBRs more quadratic. Using
1776  * *non-negative* overlap instead of overlap as the first split
1777  * criteria gives to range criteria a chance to matter, because
1778  * non-overlapping splits are equivalent in this criteria.
1779  */
1780  if (non_negative(overlap) < non_negative(context->overlap) ||
1781  (range > context->range &&
1782  non_negative(overlap) <= non_negative(context->overlap)))
1783  selectthis = true;
1784  }
1785 
1786  if (selectthis)
1787  {
1788  /* save information about selected split */
1789  context->first = false;
1790  context->ratio = ratio;
1791  context->range = range;
1792  context->overlap = overlap;
1793  context->rightLower = rightLower;
1794  context->leftUpper = leftUpper;
1795  context->dim = dimNum;
1796  POSTGIS_DEBUG(5, "split selected");
1797  }
1798  }
1799 }
#define LIMIT_RATIO
static float non_negative(float val)

References ConsiderSplitContext::boundingBox, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, ConsiderSplitContext::first, ConsiderSplitContext::leftUpper, LIMIT_RATIO, non_negative(), ConsiderSplitContext::overlap, ConsiderSplitContext::range, ConsiderSplitContext::ratio, and ConsiderSplitContext::rightLower.

Referenced by gserialized_gist_picksplit_2d().

Here is the call graph for this function:
Here is the caller graph for this function: