PostGIS  3.1.6dev-r@@SVN_REVISION@@

◆ gserialized_gist_picksplit_2d()

Datum gserialized_gist_picksplit_2d ( PG_FUNCTION_ARGS  )

Definition at line 1660 of file gserialized_gist_2d.c.

1661 {
1662  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1663  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1664  OffsetNumber i,
1665  maxoff;
1666  ConsiderSplitContext context;
1667  BOX2DF *box,
1668  *leftBox,
1669  *rightBox;
1670  int dim,
1671  commonEntriesCount;
1672  SplitInterval *intervalsLower,
1673  *intervalsUpper;
1674  CommonEntry *commonEntries;
1675  int nentries;
1676 
1677  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
1678 
1679  memset(&context, 0, sizeof(ConsiderSplitContext));
1680 
1681  maxoff = entryvec->n - 1;
1682  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1683 
1684  /* Allocate arrays for intervals along axes */
1685  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1686  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1687 
1688  /*
1689  * Calculate the overall minimum bounding box over all the entries.
1690  */
1691  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1692  {
1693  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1694  if (i == FirstOffsetNumber)
1695  context.boundingBox = *box;
1696  else
1697  adjustBox(&context.boundingBox, box);
1698  }
1699 
1700  POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
1701  &context.boundingBox));
1702 
1703  /*
1704  * Iterate over axes for optimal split searching.
1705  */
1706  context.first = true; /* nothing selected yet */
1707  for (dim = 0; dim < 2; dim++)
1708  {
1709  float leftUpper,
1710  rightLower;
1711  int i1,
1712  i2;
1713 
1714  /* Project each entry as an interval on the selected axis. */
1715  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1716  {
1717  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1718  if (dim == 0)
1719  {
1720  intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
1721  intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
1722  }
1723  else
1724  {
1725  intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
1726  intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
1727  }
1728  }
1729 
1730  /*
1731  * Make two arrays of intervals: one sorted by lower bound and another
1732  * sorted by upper bound.
1733  */
1734  memcpy(intervalsUpper, intervalsLower,
1735  sizeof(SplitInterval) * nentries);
1736  qsort(intervalsLower, nentries, sizeof(SplitInterval),
1738  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1740 
1741  /*----
1742  * The goal is to form a left and right interval, so that every entry
1743  * interval is contained by either left or right interval (or both).
1744  *
1745  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1746  *
1747  * 0 1 2 3 4
1748  * +-+
1749  * +---+
1750  * +-+
1751  * +---+
1752  *
1753  * The left and right intervals are of the form (0,a) and (b,4).
1754  * We first consider splits where b is the lower bound of an entry.
1755  * We iterate through all entries, and for each b, calculate the
1756  * smallest possible a. Then we consider splits where a is the
1757  * upper bound of an entry, and for each a, calculate the greatest
1758  * possible b.
1759  *
1760  * In the above example, the first loop would consider splits:
1761  * b=0: (0,1)-(0,4)
1762  * b=1: (0,1)-(1,4)
1763  * b=2: (0,3)-(2,4)
1764  *
1765  * And the second loop:
1766  * a=1: (0,1)-(1,4)
1767  * a=3: (0,3)-(2,4)
1768  * a=4: (0,4)-(2,4)
1769  */
1770 
1771  /*
1772  * Iterate over lower bound of right group, finding smallest possible
1773  * upper bound of left group.
1774  */
1775  i1 = 0;
1776  i2 = 0;
1777  rightLower = intervalsLower[i1].lower;
1778  leftUpper = intervalsUpper[i2].lower;
1779  while (true)
1780  {
1781  /*
1782  * Find next lower bound of right group.
1783  */
1784  while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
1785  isnan(intervalsLower[i1].lower)))
1786  {
1787  leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1788  i1++;
1789  }
1790  if (i1 >= nentries)
1791  break;
1792  rightLower = intervalsLower[i1].lower;
1793 
1794  /*
1795  * Find count of intervals which anyway should be placed to the
1796  * left group.
1797  */
1798  while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
1799  i2++;
1800 
1801  /*
1802  * Consider found split.
1803  */
1804  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
1805  }
1806 
1807  /*
1808  * Iterate over upper bound of left group finding greatest possible
1809  * lower bound of right group.
1810  */
1811  i1 = nentries - 1;
1812  i2 = nentries - 1;
1813  rightLower = intervalsLower[i1].upper;
1814  leftUpper = intervalsUpper[i2].upper;
1815  while (true)
1816  {
1817  /*
1818  * Find next upper bound of left group.
1819  */
1820  while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
1821  isnan(intervalsUpper[i2].upper)))
1822  {
1823  rightLower = Min(rightLower, intervalsUpper[i2].lower);
1824  i2--;
1825  }
1826  if (i2 < 0)
1827  break;
1828  leftUpper = intervalsUpper[i2].upper;
1829 
1830  /*
1831  * Find count of intervals which anyway should be placed to the
1832  * right group.
1833  */
1834  while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
1835  i1--;
1836 
1837  /*
1838  * Consider found split.
1839  */
1840  g_box_consider_split(&context, dim,
1841  rightLower, i1 + 1, leftUpper, i2 + 1);
1842  }
1843  }
1844 
1845  /*
1846  * If we failed to find any acceptable splits, use trivial split.
1847  */
1848  if (context.first)
1849  {
1850  POSTGIS_DEBUG(4, "no acceptable splits, trivial split");
1851  fallbackSplit(entryvec, v);
1852  PG_RETURN_POINTER(v);
1853  }
1854 
1855  /*
1856  * Ok, we have now selected the split across one axis.
1857  *
1858  * While considering the splits, we already determined that there will be
1859  * enough entries in both groups to reach the desired ratio, but we did
1860  * not memorize which entries go to which group. So determine that now.
1861  */
1862 
1863  POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
1864 
1865  /* Allocate vectors for results */
1866  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1867  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
1868  v->spl_nleft = 0;
1869  v->spl_nright = 0;
1870 
1871  /* Allocate bounding boxes of left and right groups */
1872  leftBox = palloc0(sizeof(BOX2DF));
1873  rightBox = palloc0(sizeof(BOX2DF));
1874 
1875  /*
1876  * Allocate an array for "common entries" - entries which can be placed to
1877  * either group without affecting overlap along selected axis.
1878  */
1879  commonEntriesCount = 0;
1880  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
1881 
1882  /* Helper macros to place an entry in the left or right group */
1883 #define PLACE_LEFT(box, off) \
1884  do { \
1885  if (v->spl_nleft > 0) \
1886  adjustBox(leftBox, box); \
1887  else \
1888  *leftBox = *(box); \
1889  v->spl_left[v->spl_nleft++] = off; \
1890  } while(0)
1891 
1892 #define PLACE_RIGHT(box, off) \
1893  do { \
1894  if (v->spl_nright > 0) \
1895  adjustBox(rightBox, box); \
1896  else \
1897  *rightBox = *(box); \
1898  v->spl_right[v->spl_nright++] = off; \
1899  } while(0)
1900 
1901  /*
1902  * Distribute entries which can be distributed unambiguously, and collect
1903  * common entries.
1904  */
1905  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1906  {
1907  float lower,
1908  upper;
1909 
1910  /*
1911  * Get upper and lower bounds along selected axis.
1912  */
1913  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1914  if (context.dim == 0)
1915  {
1916  lower = box->xmin;
1917  upper = box->xmax;
1918  }
1919  else
1920  {
1921  lower = box->ymin;
1922  upper = box->ymax;
1923  }
1924 
1925  if (upper <= context.leftUpper || isnan(upper))
1926  {
1927  /* Fits to the left group */
1928  if (lower >= context.rightLower || isnan(lower))
1929  {
1930  /* Fits also to the right group, so "common entry" */
1931  commonEntries[commonEntriesCount++].index = i;
1932  }
1933  else
1934  {
1935  /* Doesn't fit to the right group, so join to the left group */
1936  PLACE_LEFT(box, i);
1937  }
1938  }
1939  else
1940  {
1941  /*
1942  * Each entry should fit on either left or right group. Since this
1943  * entry didn't fit on the left group, it better fit in the right
1944  * group.
1945  */
1946  Assert(lower >= context.rightLower);
1947 
1948  /* Doesn't fit to the left group, so join to the right group */
1949  PLACE_RIGHT(box, i);
1950  }
1951  }
1952 
1953  POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
1954  POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
1955 
1956  /*
1957  * Distribute "common entries", if any.
1958  */
1959  if (commonEntriesCount > 0)
1960  {
1961  /*
1962  * Calculate minimum number of entries that must be placed in both
1963  * groups, to reach LIMIT_RATIO.
1964  */
1965  int m = ceil(LIMIT_RATIO * (double) nentries);
1966 
1967  /*
1968  * Calculate delta between penalties of join "common entries" to
1969  * different groups.
1970  */
1971  for (i = 0; i < commonEntriesCount; i++)
1972  {
1973  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
1974  commonEntries[i].index].key);
1975  commonEntries[i].delta = Abs(box2df_penalty(leftBox, box) - box2df_penalty(rightBox, box));
1976  }
1977 
1978  /*
1979  * Sort "common entries" by calculated deltas in order to distribute
1980  * the most ambiguous entries first.
1981  */
1982  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
1983 
1984  /*
1985  * Distribute "common entries" between groups.
1986  */
1987  for (i = 0; i < commonEntriesCount; i++)
1988  {
1989  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
1990  commonEntries[i].index].key);
1991 
1992  /*
1993  * Check if we have to place this entry in either group to achieve
1994  * LIMIT_RATIO.
1995  */
1996  if (v->spl_nleft + (commonEntriesCount - i) <= m)
1997  PLACE_LEFT(box, commonEntries[i].index);
1998  else if (v->spl_nright + (commonEntriesCount - i) <= m)
1999  PLACE_RIGHT(box, commonEntries[i].index);
2000  else
2001  {
2002  /* Otherwise select the group by minimal penalty */
2003  if (box2df_penalty(leftBox, box) < box2df_penalty(rightBox, box))
2004  PLACE_LEFT(box, commonEntries[i].index);
2005  else
2006  PLACE_RIGHT(box, commonEntries[i].index);
2007  }
2008  }
2009  }
2010  v->spl_ldatum = PointerGetDatum(leftBox);
2011  v->spl_rdatum = PointerGetDatum(rightBox);
2012 
2013  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2014 
2015  PG_RETURN_POINTER(v);
2016 }
static char * box2df_to_string(const BOX2DF *a)
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
static int interval_cmp_upper(const void *i1, const void *i2)
#define LIMIT_RATIO
#define PLACE_RIGHT(box, off)
static void g_box_consider_split(ConsiderSplitContext *context, int dimNum, float rightLower, int minLeftCount, float leftUpper, int maxLeftCount)
static int interval_cmp_lower(const void *i1, const void *i2)
static int common_entry_cmp(const void *i1, const void *i2)
#define PLACE_LEFT(box, off)
static float box2df_penalty(const BOX2DF *b1, const BOX2DF *b2)
static void adjustBox(BOX2DF *b, BOX2DF *addon)

References adjustBox(), ConsiderSplitContext::boundingBox, box2df_penalty(), box2df_to_string(), common_entry_cmp(), CommonEntry::delta, ConsiderSplitContext::dim, ConsiderSplitContext::entriesCount, fallbackSplit(), ConsiderSplitContext::first, g_box_consider_split(), CommonEntry::index, interval_cmp_lower(), interval_cmp_upper(), ConsiderSplitContext::leftUpper, LIMIT_RATIO, SplitInterval::lower, PLACE_LEFT, PLACE_RIGHT, ConsiderSplitContext::rightLower, and SplitInterval::upper.

Here is the call graph for this function: