PostGIS  3.1.6dev-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 1507 of file gserialized_gist_2d.c.

1510 {
1511  int leftCount,
1512  rightCount;
1513  float4 ratio,
1514  overlap;
1515  float range;
1516 
1517  POSTGIS_DEBUGF(5, "consider split: dimNum = %d, rightLower = %f, "
1518  "minLeftCount = %d, leftUpper = %f, maxLeftCount = %d ",
1519  dimNum, rightLower, minLeftCount, leftUpper, maxLeftCount);
1520 
1521  /*
1522  * Calculate entries distribution ratio assuming most uniform distribution
1523  * of common entries.
1524  */
1525  if (minLeftCount >= (context->entriesCount + 1) / 2)
1526  {
1527  leftCount = minLeftCount;
1528  }
1529  else
1530  {
1531  if (maxLeftCount <= context->entriesCount / 2)
1532  leftCount = maxLeftCount;
1533  else
1534  leftCount = context->entriesCount / 2;
1535  }
1536  rightCount = context->entriesCount - leftCount;
1537 
1538  /*
1539  * Ratio of split - quotient between size of lesser group and total
1540  * entries count.
1541  */
1542  ratio = ((float4) Min(leftCount, rightCount)) /
1543  ((float4) context->entriesCount);
1544 
1545  if (ratio > LIMIT_RATIO)
1546  {
1547  bool selectthis = false;
1548 
1549  /*
1550  * The ratio is acceptable, so compare current split with previously
1551  * selected one. Between splits of one dimension we search for minimal
1552  * overlap (allowing negative values) and minimal ration (between same
1553  * overlaps. We switch dimension if find less overlap (non-negative)
1554  * or less range with same overlap.
1555  */
1556  if (dimNum == 0)
1557  range = context->boundingBox.xmax - context->boundingBox.xmin;
1558  else
1559  range = context->boundingBox.ymax - context->boundingBox.ymin;
1560 
1561  overlap = (leftUpper - rightLower) / range;
1562 
1563  /* If there is no previous selection, select this */
1564  if (context->first)
1565  selectthis = true;
1566  else if (context->dim == dimNum)
1567  {
1568  /*
1569  * Within the same dimension, choose the new split if it has a
1570  * smaller overlap, or same overlap but better ratio.
1571  */
1572  if (overlap < context->overlap ||
1573  (overlap == context->overlap && ratio > context->ratio))
1574  selectthis = true;
1575  }
1576  else
1577  {
1578  /*
1579  * Across dimensions, choose the new split if it has a smaller
1580  * *non-negative* overlap, or same *non-negative* overlap but
1581  * bigger range. This condition differs from the one described in
1582  * the article. On the datasets where leaf MBRs don't overlap
1583  * themselves, non-overlapping splits (i.e. splits which have zero
1584  * *non-negative* overlap) are frequently possible. In this case
1585  * splits tends to be along one dimension, because most distant
1586  * non-overlapping splits (i.e. having lowest negative overlap)
1587  * appears to be in the same dimension as in the previous split.
1588  * Therefore MBRs appear to be very prolonged along another
1589  * dimension, which leads to bad search performance. Using range
1590  * as the second split criteria makes MBRs more quadratic. Using
1591  * *non-negative* overlap instead of overlap as the first split
1592  * criteria gives to range criteria a chance to matter, because
1593  * non-overlapping splits are equivalent in this criteria.
1594  */
1595  if (non_negative(overlap) < non_negative(context->overlap) ||
1596  (range > context->range &&
1597  non_negative(overlap) <= non_negative(context->overlap)))
1598  selectthis = true;
1599  }
1600 
1601  if (selectthis)
1602  {
1603  /* save information about selected split */
1604  context->first = false;
1605  context->ratio = ratio;
1606  context->range = range;
1607  context->overlap = overlap;
1608  context->rightLower = rightLower;
1609  context->leftUpper = leftUpper;
1610  context->dim = dimNum;
1611  POSTGIS_DEBUG(5, "split selected");
1612  }
1613  }
1614 }
#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: