PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ gserialized_gist_picksplit()

Datum gserialized_gist_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 1796 of file gserialized_gist_nd.c.

1797 {
1798 
1799  GistEntryVector *entryvec = (GistEntryVector*) PG_GETARG_POINTER(0);
1800 
1801  GIST_SPLITVEC *v = (GIST_SPLITVEC*) PG_GETARG_POINTER(1);
1802  OffsetNumber i;
1803  /* One union box for each half of the space. */
1804  GIDX **box_union;
1805  /* One offset number list for each half of the space. */
1806  OffsetNumber **list;
1807  /* One position index for each half of the space. */
1808  int *pos;
1809  GIDX *box_pageunion;
1810  GIDX *box_current;
1811  int direction = -1;
1812  bool all_entries_equal = true;
1813  OffsetNumber max_offset;
1814  int nbytes, ndims_pageunion, d;
1815  int posmin = entryvec->n;
1816 
1817  POSTGIS_DEBUG(4, "[GIST] 'picksplit' function called");
1818 
1819  /*
1820  ** First calculate the bounding box and maximum number of dimensions in this page.
1821  */
1822 
1823  max_offset = entryvec->n - 1;
1824  box_current = (GIDX*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
1825  box_pageunion = gidx_copy(box_current);
1826 
1827  /* Calculate the containing box (box_pageunion) for the whole page we are going to split. */
1828  for ( i = OffsetNumberNext(FirstOffsetNumber); i <= max_offset; i = OffsetNumberNext(i) )
1829  {
1830  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1831 
1832  if ( all_entries_equal == true && ! gidx_equals (box_pageunion, box_current) )
1833  all_entries_equal = false;
1834 
1835  gidx_merge( &box_pageunion, box_current );
1836  }
1837 
1838  POSTGIS_DEBUGF(3, "[GIST] box_pageunion: %s", gidx_to_string(box_pageunion));
1839 
1840  /* Every box in the page is the same! So, we split and just put half the boxes in each child. */
1841  if ( all_entries_equal )
1842  {
1843  POSTGIS_DEBUG(4, "[GIST] picksplit finds all entries equal!");
1845  PG_RETURN_POINTER(v);
1846  }
1847 
1848  /* Initialize memory structures. */
1849  nbytes = (max_offset + 2) * sizeof(OffsetNumber);
1850  ndims_pageunion = GIDX_NDIMS(box_pageunion);
1851  POSTGIS_DEBUGF(4, "[GIST] ndims_pageunion == %d", ndims_pageunion);
1852  pos = palloc(2*ndims_pageunion * sizeof(int));
1853  list = palloc(2*ndims_pageunion * sizeof(OffsetNumber*));
1854  box_union = palloc(2*ndims_pageunion * sizeof(GIDX*));
1855  for ( d = 0; d < ndims_pageunion; d++ )
1856  {
1857  list[BELOW(d)] = (OffsetNumber*) palloc(nbytes);
1858  list[ABOVE(d)] = (OffsetNumber*) palloc(nbytes);
1859  box_union[BELOW(d)] = gidx_new(ndims_pageunion);
1860  box_union[ABOVE(d)] = gidx_new(ndims_pageunion);
1861  pos[BELOW(d)] = 0;
1862  pos[ABOVE(d)] = 0;
1863  }
1864 
1865  /*
1866  ** Assign each entry in the node to the volume partitions it belongs to,
1867  ** such as "above the x/y plane, left of the y/z plane, below the x/z plane".
1868  ** Each entry thereby ends up in three of the six partitions.
1869  */
1870  POSTGIS_DEBUG(4, "[GIST] 'picksplit' calculating best split axis");
1871  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1872  {
1873  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1874 
1875  for ( d = 0; d < ndims_pageunion; d++ )
1876  {
1877  if ( GIDX_GET_MIN(box_current,d)-GIDX_GET_MIN(box_pageunion,d) < GIDX_GET_MAX(box_pageunion,d)-GIDX_GET_MAX(box_current,d) )
1878  {
1879  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1880  }
1881  else
1882  {
1883  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1884  }
1885 
1886  }
1887 
1888  }
1889 
1890  /*
1891  ** "Bad disposition", too many entries fell into one octant of the space, so no matter which
1892  ** plane we choose to split on, we're going to end up with a mostly full node. Where the
1893  ** data is pretty homogeneous (lots of duplicates) entries that are equidistant from the
1894  ** sides of the page union box can occasionally all end up in one place, leading
1895  ** to this condition.
1896  */
1897  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == true )
1898  {
1899  /*
1900  ** Instead we split on center points and see if we do better.
1901  ** First calculate the average center point for each axis.
1902  */
1903  double *avgCenter = palloc(ndims_pageunion * sizeof(double));
1904 
1905  for ( d = 0; d < ndims_pageunion; d++ )
1906  {
1907  avgCenter[d] = 0.0;
1908  }
1909 
1910  POSTGIS_DEBUG(4, "[GIST] picksplit can't find good split axis, trying center point method");
1911 
1912  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1913  {
1914  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1915  for ( d = 0; d < ndims_pageunion; d++ )
1916  {
1917  avgCenter[d] += (GIDX_GET_MAX(box_current,d) + GIDX_GET_MIN(box_current,d)) / 2.0;
1918  }
1919  }
1920  for ( d = 0; d < ndims_pageunion; d++ )
1921  {
1922  avgCenter[d] /= max_offset;
1923  pos[BELOW(d)] = pos[ABOVE(d)] = 0; /* Re-initialize our counters. */
1924  POSTGIS_DEBUGF(4, "[GIST] picksplit average center point[%d] = %.12g", d, avgCenter[d]);
1925  }
1926 
1927  /* For each of our entries... */
1928  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1929  {
1930  double center;
1931  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1932 
1933  for ( d = 0; d < ndims_pageunion; d++ )
1934  {
1935  center = (GIDX_GET_MIN(box_current,d)+GIDX_GET_MAX(box_current,d))/2.0;
1936  if ( center < avgCenter[d] )
1937  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1938  else if ( FPeq(center, avgCenter[d]) )
1939  if ( pos[BELOW(d)] > pos[ABOVE(d)] )
1940  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1941  else
1942  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1943  else
1944  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1945  }
1946 
1947  }
1948 
1949  /* Do we have a good disposition now? If not, screw it, just cut the node in half. */
1950  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == true )
1951  {
1952  POSTGIS_DEBUG(4, "[GIST] picksplit still cannot find a good split! just cutting the node in half");
1954  PG_RETURN_POINTER(v);
1955  }
1956 
1957  }
1958 
1959  /*
1960  ** Now, what splitting plane gives us the most even ratio of
1961  ** entries in our child pages? Since each split region has been apportioned entries
1962  ** against the same number of total entries, the axis that has the smallest maximum
1963  ** number of entries in its regions is the most evenly distributed.
1964  ** TODO: what if the distributions are equal in two or more axes?
1965  */
1966  for ( d = 0; d < ndims_pageunion; d++ )
1967  {
1968  int posd = Max(pos[ABOVE(d)],pos[BELOW(d)]);
1969  if ( posd < posmin )
1970  {
1971  direction = d;
1972  posmin = posd;
1973  }
1974  }
1975  if ( direction == -1 || posmin == entryvec->n )
1976  {
1977  /* ERROR OUT HERE */
1978  elog(ERROR, "Error in building split, unable to determine split direction.");
1979  }
1980 
1981  POSTGIS_DEBUGF(3, "[GIST] 'picksplit' splitting on axis %d", direction);
1982 
1984  pos[BELOW(direction)],
1985  &(box_union[BELOW(direction)]),
1986  list[ABOVE(direction)],
1987  pos[ABOVE(direction)],
1988  &(box_union[ABOVE(direction)]) );
1989 
1990  POSTGIS_DEBUGF(4, "[GIST] spl_ldatum: %s", gidx_to_string((GIDX*)v->spl_ldatum));
1991  POSTGIS_DEBUGF(4, "[GIST] spl_rdatum: %s", gidx_to_string((GIDX*)v->spl_rdatum));
1992 
1993  POSTGIS_DEBUGF(4, "[GIST] axis %d: parent range (%.12g, %.12g) left range (%.12g, %.12g), right range (%.12g, %.12g)",
1994  direction,
1995  GIDX_GET_MIN(box_pageunion, direction), GIDX_GET_MAX(box_pageunion, direction),
1996  GIDX_GET_MIN((GIDX*)v->spl_ldatum, direction), GIDX_GET_MAX((GIDX*)v->spl_ldatum, direction),
1997  GIDX_GET_MIN((GIDX*)v->spl_rdatum, direction), GIDX_GET_MAX((GIDX*)v->spl_rdatum, direction) );
1998 
1999  PG_RETURN_POINTER(v);
2000 
2001 }
static void gserialized_gist_picksplit_constructsplit(GIST_SPLITVEC *v, OffsetNumber *list1, int nlist1, GIDX **union1, OffsetNumber *list2, int nlist2, GIDX **union2)
static bool gserialized_gist_picksplit_badratios(int *pos, int dims)
static void gserialized_gist_picksplit_addlist(OffsetNumber *list, GIDX **box_union, GIDX *box_current, int *pos, int num)
GIDX * gidx_copy(GIDX *b)
#define ABOVE(d)
#define BELOW(d)
static bool gidx_equals(GIDX *a, GIDX *b)
static void gserialized_gist_picksplit_fallback(GistEntryVector *entryvec, GIST_SPLITVEC *v)
void gidx_merge(GIDX **b_union, GIDX *b_new)

References ABOVE, BELOW, gidx_copy(), gidx_equals(), gidx_merge(), gserialized_gist_picksplit_addlist(), gserialized_gist_picksplit_badratios(), gserialized_gist_picksplit_constructsplit(), and gserialized_gist_picksplit_fallback().

Here is the call graph for this function: