PostGIS  2.3.8dev-r@@SVN_REVISION@@

◆ gserialized_gist_picksplit()

Datum gserialized_gist_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 1682 of file gserialized_gist_nd.c.

References ABOVE, BELOW, FPeq, gidx_copy(), gidx_equals(), gidx_in(), gidx_merge(), gserialized_gist_picksplit_addlist(), gserialized_gist_picksplit_badratios(), gserialized_gist_picksplit_constructsplit(), gserialized_gist_picksplit_fallback(), PG_FUNCTION_INFO_V1(), and TRUE.

1683 {
1684 
1685  GistEntryVector *entryvec = (GistEntryVector*) PG_GETARG_POINTER(0);
1686 
1687  GIST_SPLITVEC *v = (GIST_SPLITVEC*) PG_GETARG_POINTER(1);
1688  OffsetNumber i;
1689  /* One union box for each half of the space. */
1690  GIDX **box_union;
1691  /* One offset number list for each half of the space. */
1692  OffsetNumber **list;
1693  /* One position index for each half of the space. */
1694  int *pos;
1695  GIDX *box_pageunion;
1696  GIDX *box_current;
1697  int direction = -1;
1698  bool all_entries_equal = true;
1699  OffsetNumber max_offset;
1700  int nbytes, ndims_pageunion, d;
1701  int posmin = entryvec->n;
1702 
1703  POSTGIS_DEBUG(4, "[GIST] 'picksplit' function called");
1704 
1705  /*
1706  ** First calculate the bounding box and maximum number of dimensions in this page.
1707  */
1708 
1709  max_offset = entryvec->n - 1;
1710  box_current = (GIDX*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
1711  box_pageunion = gidx_copy(box_current);
1712 
1713  /* Calculate the containing box (box_pageunion) for the whole page we are going to split. */
1714  for ( i = OffsetNumberNext(FirstOffsetNumber); i <= max_offset; i = OffsetNumberNext(i) )
1715  {
1716  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1717 
1718  if ( all_entries_equal == true && ! gidx_equals (box_pageunion, box_current) )
1719  all_entries_equal = false;
1720 
1721  gidx_merge( &box_pageunion, box_current );
1722  }
1723 
1724  POSTGIS_DEBUGF(3, "[GIST] box_pageunion: %s", gidx_to_string(box_pageunion));
1725 
1726  /* Every box in the page is the same! So, we split and just put half the boxes in each child. */
1727  if ( all_entries_equal )
1728  {
1729  POSTGIS_DEBUG(4, "[GIST] picksplit finds all entries equal!");
1731  PG_RETURN_POINTER(v);
1732  }
1733 
1734  /* Initialize memory structures. */
1735  nbytes = (max_offset + 2) * sizeof(OffsetNumber);
1736  ndims_pageunion = GIDX_NDIMS(box_pageunion);
1737  POSTGIS_DEBUGF(4, "[GIST] ndims_pageunion == %d", ndims_pageunion);
1738  pos = palloc(2*ndims_pageunion * sizeof(int));
1739  list = palloc(2*ndims_pageunion * sizeof(OffsetNumber*));
1740  box_union = palloc(2*ndims_pageunion * sizeof(GIDX*));
1741  for ( d = 0; d < ndims_pageunion; d++ )
1742  {
1743  list[BELOW(d)] = (OffsetNumber*) palloc(nbytes);
1744  list[ABOVE(d)] = (OffsetNumber*) palloc(nbytes);
1745  box_union[BELOW(d)] = gidx_new(ndims_pageunion);
1746  box_union[ABOVE(d)] = gidx_new(ndims_pageunion);
1747  pos[BELOW(d)] = 0;
1748  pos[ABOVE(d)] = 0;
1749  }
1750 
1751  /*
1752  ** Assign each entry in the node to the volume partitions it belongs to,
1753  ** such as "above the x/y plane, left of the y/z plane, below the x/z plane".
1754  ** Each entry thereby ends up in three of the six partitions.
1755  */
1756  POSTGIS_DEBUG(4, "[GIST] 'picksplit' calculating best split axis");
1757  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1758  {
1759  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1760 
1761  for ( d = 0; d < ndims_pageunion; d++ )
1762  {
1763  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) )
1764  {
1765  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1766  }
1767  else
1768  {
1769  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1770  }
1771 
1772  }
1773 
1774  }
1775 
1776  /*
1777  ** "Bad disposition", too many entries fell into one octant of the space, so no matter which
1778  ** plane we choose to split on, we're going to end up with a mostly full node. Where the
1779  ** data is pretty homogeneous (lots of duplicates) entries that are equidistant from the
1780  ** sides of the page union box can occasionally all end up in one place, leading
1781  ** to this condition.
1782  */
1783  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1784  {
1785  /*
1786  ** Instead we split on center points and see if we do better.
1787  ** First calculate the average center point for each axis.
1788  */
1789  double *avgCenter = palloc(ndims_pageunion * sizeof(double));
1790 
1791  for ( d = 0; d < ndims_pageunion; d++ )
1792  {
1793  avgCenter[d] = 0.0;
1794  }
1795 
1796  POSTGIS_DEBUG(4, "[GIST] picksplit can't find good split axis, trying center point method");
1797 
1798  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1799  {
1800  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1801  for ( d = 0; d < ndims_pageunion; d++ )
1802  {
1803  avgCenter[d] += (GIDX_GET_MAX(box_current,d) + GIDX_GET_MIN(box_current,d)) / 2.0;
1804  }
1805  }
1806  for ( d = 0; d < ndims_pageunion; d++ )
1807  {
1808  avgCenter[d] /= max_offset;
1809  pos[BELOW(d)] = pos[ABOVE(d)] = 0; /* Re-initialize our counters. */
1810  POSTGIS_DEBUGF(4, "[GIST] picksplit average center point[%d] = %.12g", d, avgCenter[d]);
1811  }
1812 
1813  /* For each of our entries... */
1814  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1815  {
1816  double center;
1817  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1818 
1819  for ( d = 0; d < ndims_pageunion; d++ )
1820  {
1821  center = (GIDX_GET_MIN(box_current,d)+GIDX_GET_MAX(box_current,d))/2.0;
1822  if ( center < avgCenter[d] )
1823  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1824  else if ( FPeq(center, avgCenter[d]) )
1825  if ( pos[BELOW(d)] > pos[ABOVE(d)] )
1826  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1827  else
1828  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1829  else
1830  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1831  }
1832 
1833  }
1834 
1835  /* Do we have a good disposition now? If not, screw it, just cut the node in half. */
1836  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1837  {
1838  POSTGIS_DEBUG(4, "[GIST] picksplit still cannot find a good split! just cutting the node in half");
1840  PG_RETURN_POINTER(v);
1841  }
1842 
1843  }
1844 
1845  /*
1846  ** Now, what splitting plane gives us the most even ratio of
1847  ** entries in our child pages? Since each split region has been apportioned entries
1848  ** against the same number of total entries, the axis that has the smallest maximum
1849  ** number of entries in its regions is the most evenly distributed.
1850  ** TODO: what if the distributions are equal in two or more axes?
1851  */
1852  for ( d = 0; d < ndims_pageunion; d++ )
1853  {
1854  int posd = Max(pos[ABOVE(d)],pos[BELOW(d)]);
1855  if ( posd < posmin )
1856  {
1857  direction = d;
1858  posmin = posd;
1859  }
1860  }
1861  if ( direction == -1 || posmin == entryvec->n )
1862  {
1863  /* ERROR OUT HERE */
1864  elog(ERROR, "Error in building split, unable to determine split direction.");
1865  }
1866 
1867  POSTGIS_DEBUGF(3, "[GIST] 'picksplit' splitting on axis %d", direction);
1868 
1870  pos[BELOW(direction)],
1871  &(box_union[BELOW(direction)]),
1872  list[ABOVE(direction)],
1873  pos[ABOVE(direction)],
1874  &(box_union[ABOVE(direction)]) );
1875 
1876  POSTGIS_DEBUGF(4, "[GIST] spl_ldatum: %s", gidx_to_string((GIDX*)v->spl_ldatum));
1877  POSTGIS_DEBUGF(4, "[GIST] spl_rdatum: %s", gidx_to_string((GIDX*)v->spl_rdatum));
1878 
1879  POSTGIS_DEBUGF(4, "[GIST] axis %d: parent range (%.12g, %.12g) left range (%.12g, %.12g), right range (%.12g, %.12g)",
1880  direction,
1881  GIDX_GET_MIN(box_pageunion, direction), GIDX_GET_MAX(box_pageunion, direction),
1882  GIDX_GET_MIN((GIDX*)v->spl_ldatum, direction), GIDX_GET_MAX((GIDX*)v->spl_ldatum, direction),
1883  GIDX_GET_MIN((GIDX*)v->spl_rdatum, direction), GIDX_GET_MAX((GIDX*)v->spl_rdatum, direction) );
1884 
1885  PG_RETURN_POINTER(v);
1886 
1887 }
static void gidx_merge(GIDX **b_union, GIDX *b_new)
static GIDX * gidx_copy(GIDX *b)
static void gserialized_gist_picksplit_constructsplit(GIST_SPLITVEC *v, OffsetNumber *list1, int nlist1, GIDX **union1, OffsetNumber *list2, int nlist2, GIDX **union2)
static bool gidx_equals(GIDX *a, GIDX *b)
#define BELOW(d)
static bool gserialized_gist_picksplit_badratios(int *pos, int dims)
static void gserialized_gist_picksplit_fallback(GistEntryVector *entryvec, GIST_SPLITVEC *v)
static void gserialized_gist_picksplit_addlist(OffsetNumber *list, GIDX **box_union, GIDX *box_current, int *pos, int num)
#define FPeq(A, B)
Definition: box2d.c:37
#define ABOVE(d)
#define TRUE
Definition: dbfopen.c:169
Here is the call graph for this function: