PostGIS  2.5.2dev-r@@SVN_REVISION@@

◆ gserialized_gist_picksplit_2d()

Datum gserialized_gist_picksplit_2d ( PG_FUNCTION_ARGS  )

Definition at line 1862 of file gserialized_gist_2d.c.

References adjustBox(), ConsiderSplitContext::boundingBox, box2df_in(), box2df_size(), box2df_to_string(), box_penalty(), common_entry_cmp(), rtgdalraster::cur, 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, PG_FUNCTION_INFO_V1(), PLACE_LEFT, PLACE_RIGHT, ConsiderSplitContext::rightLower, and SplitInterval::upper.

Referenced by common_entry_cmp().

1863 {
1864  GistEntryVector *entryvec = (GistEntryVector *) PG_GETARG_POINTER(0);
1865  GIST_SPLITVEC *v = (GIST_SPLITVEC *) PG_GETARG_POINTER(1);
1866  OffsetNumber i,
1867  maxoff;
1868  ConsiderSplitContext context;
1869  BOX2DF *box,
1870  *leftBox,
1871  *rightBox;
1872  int dim,
1873  commonEntriesCount;
1874  SplitInterval *intervalsLower,
1875  *intervalsUpper;
1876  CommonEntry *commonEntries;
1877  int nentries;
1878 
1879  POSTGIS_DEBUG(3, "[GIST] 'picksplit' entered");
1880 
1881  memset(&context, 0, sizeof(ConsiderSplitContext));
1882 
1883  maxoff = entryvec->n - 1;
1884  nentries = context.entriesCount = maxoff - FirstOffsetNumber + 1;
1885 
1886  /* Allocate arrays for intervals along axes */
1887  intervalsLower = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1888  intervalsUpper = (SplitInterval *) palloc(nentries * sizeof(SplitInterval));
1889 
1890  /*
1891  * Calculate the overall minimum bounding box over all the entries.
1892  */
1893  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1894  {
1895  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1896  if (i == FirstOffsetNumber)
1897  context.boundingBox = *box;
1898  else
1899  adjustBox(&context.boundingBox, box);
1900  }
1901 
1902  POSTGIS_DEBUGF(4, "boundingBox is %s", box2df_to_string(
1903  &context.boundingBox));
1904 
1905  /*
1906  * Iterate over axes for optimal split searching.
1907  */
1908  context.first = true; /* nothing selected yet */
1909  for (dim = 0; dim < 2; dim++)
1910  {
1911  float leftUpper,
1912  rightLower;
1913  int i1,
1914  i2;
1915 
1916  /* Project each entry as an interval on the selected axis. */
1917  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
1918  {
1919  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
1920  if (dim == 0)
1921  {
1922  intervalsLower[i - FirstOffsetNumber].lower = box->xmin;
1923  intervalsLower[i - FirstOffsetNumber].upper = box->xmax;
1924  }
1925  else
1926  {
1927  intervalsLower[i - FirstOffsetNumber].lower = box->ymin;
1928  intervalsLower[i - FirstOffsetNumber].upper = box->ymax;
1929  }
1930  }
1931 
1932  /*
1933  * Make two arrays of intervals: one sorted by lower bound and another
1934  * sorted by upper bound.
1935  */
1936  memcpy(intervalsUpper, intervalsLower,
1937  sizeof(SplitInterval) * nentries);
1938  qsort(intervalsLower, nentries, sizeof(SplitInterval),
1940  qsort(intervalsUpper, nentries, sizeof(SplitInterval),
1942 
1943  /*----
1944  * The goal is to form a left and right interval, so that every entry
1945  * interval is contained by either left or right interval (or both).
1946  *
1947  * For example, with the intervals (0,1), (1,3), (2,3), (2,4):
1948  *
1949  * 0 1 2 3 4
1950  * +-+
1951  * +---+
1952  * +-+
1953  * +---+
1954  *
1955  * The left and right intervals are of the form (0,a) and (b,4).
1956  * We first consider splits where b is the lower bound of an entry.
1957  * We iterate through all entries, and for each b, calculate the
1958  * smallest possible a. Then we consider splits where a is the
1959  * upper bound of an entry, and for each a, calculate the greatest
1960  * possible b.
1961  *
1962  * In the above example, the first loop would consider splits:
1963  * b=0: (0,1)-(0,4)
1964  * b=1: (0,1)-(1,4)
1965  * b=2: (0,3)-(2,4)
1966  *
1967  * And the second loop:
1968  * a=1: (0,1)-(1,4)
1969  * a=3: (0,3)-(2,4)
1970  * a=4: (0,4)-(2,4)
1971  */
1972 
1973  /*
1974  * Iterate over lower bound of right group, finding smallest possible
1975  * upper bound of left group.
1976  */
1977  i1 = 0;
1978  i2 = 0;
1979  rightLower = intervalsLower[i1].lower;
1980  leftUpper = intervalsUpper[i2].lower;
1981  while (true)
1982  {
1983  /*
1984  * Find next lower bound of right group.
1985  */
1986  while (i1 < nentries && (rightLower == intervalsLower[i1].lower ||
1987  isnan(intervalsLower[i1].lower)))
1988  {
1989  leftUpper = Max(leftUpper, intervalsLower[i1].upper);
1990  i1++;
1991  }
1992  if (i1 >= nentries)
1993  break;
1994  rightLower = intervalsLower[i1].lower;
1995 
1996  /*
1997  * Find count of intervals which anyway should be placed to the
1998  * left group.
1999  */
2000  while (i2 < nentries && intervalsUpper[i2].upper <= leftUpper)
2001  i2++;
2002 
2003  /*
2004  * Consider found split.
2005  */
2006  g_box_consider_split(&context, dim, rightLower, i1, leftUpper, i2);
2007  }
2008 
2009  /*
2010  * Iterate over upper bound of left group finding greatest possible
2011  * lower bound of right group.
2012  */
2013  i1 = nentries - 1;
2014  i2 = nentries - 1;
2015  rightLower = intervalsLower[i1].upper;
2016  leftUpper = intervalsUpper[i2].upper;
2017  while (true)
2018  {
2019  /*
2020  * Find next upper bound of left group.
2021  */
2022  while (i2 >= 0 && (leftUpper == intervalsUpper[i2].upper ||
2023  isnan(intervalsUpper[i2].upper)))
2024  {
2025  rightLower = Min(rightLower, intervalsUpper[i2].lower);
2026  i2--;
2027  }
2028  if (i2 < 0)
2029  break;
2030  leftUpper = intervalsUpper[i2].upper;
2031 
2032  /*
2033  * Find count of intervals which anyway should be placed to the
2034  * right group.
2035  */
2036  while (i1 >= 0 && intervalsLower[i1].lower >= rightLower)
2037  i1--;
2038 
2039  /*
2040  * Consider found split.
2041  */
2042  g_box_consider_split(&context, dim,
2043  rightLower, i1 + 1, leftUpper, i2 + 1);
2044  }
2045  }
2046 
2047  /*
2048  * If we failed to find any acceptable splits, use trivial split.
2049  */
2050  if (context.first)
2051  {
2052  POSTGIS_DEBUG(4, "no acceptable splits, trivial split");
2053  fallbackSplit(entryvec, v);
2054  PG_RETURN_POINTER(v);
2055  }
2056 
2057  /*
2058  * Ok, we have now selected the split across one axis.
2059  *
2060  * While considering the splits, we already determined that there will be
2061  * enough entries in both groups to reach the desired ratio, but we did
2062  * not memorize which entries go to which group. So determine that now.
2063  */
2064 
2065  POSTGIS_DEBUGF(4, "split direction: %d", context.dim);
2066 
2067  /* Allocate vectors for results */
2068  v->spl_left = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2069  v->spl_right = (OffsetNumber *) palloc(nentries * sizeof(OffsetNumber));
2070  v->spl_nleft = 0;
2071  v->spl_nright = 0;
2072 
2073  /* Allocate bounding boxes of left and right groups */
2074  leftBox = palloc0(sizeof(BOX2DF));
2075  rightBox = palloc0(sizeof(BOX2DF));
2076 
2077  /*
2078  * Allocate an array for "common entries" - entries which can be placed to
2079  * either group without affecting overlap along selected axis.
2080  */
2081  commonEntriesCount = 0;
2082  commonEntries = (CommonEntry *) palloc(nentries * sizeof(CommonEntry));
2083 
2084  /* Helper macros to place an entry in the left or right group */
2085 #define PLACE_LEFT(box, off) \
2086  do { \
2087  if (v->spl_nleft > 0) \
2088  adjustBox(leftBox, box); \
2089  else \
2090  *leftBox = *(box); \
2091  v->spl_left[v->spl_nleft++] = off; \
2092  } while(0)
2093 
2094 #define PLACE_RIGHT(box, off) \
2095  do { \
2096  if (v->spl_nright > 0) \
2097  adjustBox(rightBox, box); \
2098  else \
2099  *rightBox = *(box); \
2100  v->spl_right[v->spl_nright++] = off; \
2101  } while(0)
2102 
2103  /*
2104  * Distribute entries which can be distributed unambiguously, and collect
2105  * common entries.
2106  */
2107  for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
2108  {
2109  float lower,
2110  upper;
2111 
2112  /*
2113  * Get upper and lower bounds along selected axis.
2114  */
2115  box = (BOX2DF *) DatumGetPointer(entryvec->vector[i].key);
2116  if (context.dim == 0)
2117  {
2118  lower = box->xmin;
2119  upper = box->xmax;
2120  }
2121  else
2122  {
2123  lower = box->ymin;
2124  upper = box->ymax;
2125  }
2126 
2127  if (upper <= context.leftUpper || isnan(upper))
2128  {
2129  /* Fits to the left group */
2130  if (lower >= context.rightLower || isnan(lower))
2131  {
2132  /* Fits also to the right group, so "common entry" */
2133  commonEntries[commonEntriesCount++].index = i;
2134  }
2135  else
2136  {
2137  /* Doesn't fit to the right group, so join to the left group */
2138  PLACE_LEFT(box, i);
2139  }
2140  }
2141  else
2142  {
2143  /*
2144  * Each entry should fit on either left or right group. Since this
2145  * entry didn't fit on the left group, it better fit in the right
2146  * group.
2147  */
2148  Assert(lower >= context.rightLower);
2149 
2150  /* Doesn't fit to the left group, so join to the right group */
2151  PLACE_RIGHT(box, i);
2152  }
2153  }
2154 
2155  POSTGIS_DEBUGF(4, "leftBox is %s", box2df_to_string(leftBox));
2156  POSTGIS_DEBUGF(4, "rightBox is %s", box2df_to_string(rightBox));
2157 
2158  /*
2159  * Distribute "common entries", if any.
2160  */
2161  if (commonEntriesCount > 0)
2162  {
2163  /*
2164  * Calculate minimum number of entries that must be placed in both
2165  * groups, to reach LIMIT_RATIO.
2166  */
2167  int m = ceil(LIMIT_RATIO * (double) nentries);
2168 
2169  /*
2170  * Calculate delta between penalties of join "common entries" to
2171  * different groups.
2172  */
2173  for (i = 0; i < commonEntriesCount; i++)
2174  {
2175  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2176  commonEntries[i].index].key);
2177  commonEntries[i].delta = Abs(box_penalty(leftBox, box) -
2178  box_penalty(rightBox, box));
2179  }
2180 
2181  /*
2182  * Sort "common entries" by calculated deltas in order to distribute
2183  * the most ambiguous entries first.
2184  */
2185  qsort(commonEntries, commonEntriesCount, sizeof(CommonEntry), common_entry_cmp);
2186 
2187  /*
2188  * Distribute "common entries" between groups.
2189  */
2190  for (i = 0; i < commonEntriesCount; i++)
2191  {
2192  box = (BOX2DF *) DatumGetPointer(entryvec->vector[
2193  commonEntries[i].index].key);
2194 
2195  /*
2196  * Check if we have to place this entry in either group to achieve
2197  * LIMIT_RATIO.
2198  */
2199  if (v->spl_nleft + (commonEntriesCount - i) <= m)
2200  PLACE_LEFT(box, commonEntries[i].index);
2201  else if (v->spl_nright + (commonEntriesCount - i) <= m)
2202  PLACE_RIGHT(box, commonEntries[i].index);
2203  else
2204  {
2205  /* Otherwise select the group by minimal penalty */
2206  if (box_penalty(leftBox, box) < box_penalty(rightBox, box))
2207  PLACE_LEFT(box, commonEntries[i].index);
2208  else
2209  PLACE_RIGHT(box, commonEntries[i].index);
2210  }
2211  }
2212  }
2213  v->spl_ldatum = PointerGetDatum(leftBox);
2214  v->spl_rdatum = PointerGetDatum(rightBox);
2215 
2216  POSTGIS_DEBUG(4, "[GIST] 'picksplit' completed");
2217 
2218  PG_RETURN_POINTER(v);
2219 }
#define LIMIT_RATIO
static void fallbackSplit(GistEntryVector *entryvec, GIST_SPLITVEC *v)
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 void adjustBox(BOX2DF *b, BOX2DF *addon)
static char * box2df_to_string(const BOX2DF *a)
static int interval_cmp_upper(const void *i1, const void *i2)
static int common_entry_cmp(const void *i1, const void *i2)
#define PLACE_RIGHT(box, off)
#define PLACE_LEFT(box, off)
static float box_penalty(BOX2DF *original, BOX2DF *new)
Here is the call graph for this function:
Here is the caller graph for this function: