PostGIS  2.1.10dev-r@@SVN_REVISION@@
Datum gserialized_gist_picksplit ( PG_FUNCTION_ARGS  )

Definition at line 1066 of file gserialized_gist_nd.c.

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

1067 {
1068 
1069  GistEntryVector *entryvec = (GistEntryVector*) PG_GETARG_POINTER(0);
1070 
1071  GIST_SPLITVEC *v = (GIST_SPLITVEC*) PG_GETARG_POINTER(1);
1072  OffsetNumber i;
1073  /* One union box for each half of the space. */
1074  GIDX **box_union;
1075  /* One offset number list for each half of the space. */
1076  OffsetNumber **list;
1077  /* One position index for each half of the space. */
1078  int *pos;
1079  GIDX *box_pageunion;
1080  GIDX *box_current;
1081  int direction = -1;
1082  bool all_entries_equal = true;
1083  OffsetNumber max_offset;
1084  int nbytes, ndims_pageunion, d;
1085  int posmin = entryvec->n;
1086 
1087  POSTGIS_DEBUG(4, "[GIST] 'picksplit' function called");
1088 
1089  /*
1090  ** First calculate the bounding box and maximum number of dimensions in this page.
1091  */
1092 
1093  max_offset = entryvec->n - 1;
1094  box_current = (GIDX*) DatumGetPointer(entryvec->vector[FirstOffsetNumber].key);
1095  box_pageunion = gidx_copy(box_current);
1096 
1097  /* Calculate the containing box (box_pageunion) for the whole page we are going to split. */
1098  for ( i = OffsetNumberNext(FirstOffsetNumber); i <= max_offset; i = OffsetNumberNext(i) )
1099  {
1100  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1101 
1102  if ( all_entries_equal == true && ! gidx_equals (box_pageunion, box_current) )
1103  all_entries_equal = false;
1104 
1105  gidx_merge( &box_pageunion, box_current );
1106  }
1107 
1108  POSTGIS_DEBUGF(3, "[GIST] box_pageunion: %s", gidx_to_string(box_pageunion));
1109 
1110  /* Every box in the page is the same! So, we split and just put half the boxes in each child. */
1111  if ( all_entries_equal )
1112  {
1113  POSTGIS_DEBUG(4, "[GIST] picksplit finds all entries equal!");
1115  PG_RETURN_POINTER(v);
1116  }
1117 
1118  /* Initialize memory structures. */
1119  nbytes = (max_offset + 2) * sizeof(OffsetNumber);
1120  ndims_pageunion = GIDX_NDIMS(box_pageunion);
1121  POSTGIS_DEBUGF(4, "[GIST] ndims_pageunion == %d", ndims_pageunion);
1122  pos = palloc(2*ndims_pageunion * sizeof(int));
1123  list = palloc(2*ndims_pageunion * sizeof(OffsetNumber*));
1124  box_union = palloc(2*ndims_pageunion * sizeof(GIDX*));
1125  for ( d = 0; d < ndims_pageunion; d++ )
1126  {
1127  list[BELOW(d)] = (OffsetNumber*) palloc(nbytes);
1128  list[ABOVE(d)] = (OffsetNumber*) palloc(nbytes);
1129  box_union[BELOW(d)] = gidx_new(ndims_pageunion);
1130  box_union[ABOVE(d)] = gidx_new(ndims_pageunion);
1131  pos[BELOW(d)] = 0;
1132  pos[ABOVE(d)] = 0;
1133  }
1134 
1135  /*
1136  ** Assign each entry in the node to the volume partitions it belongs to,
1137  ** such as "above the x/y plane, left of the y/z plane, below the x/z plane".
1138  ** Each entry thereby ends up in three of the six partitions.
1139  */
1140  POSTGIS_DEBUG(4, "[GIST] 'picksplit' calculating best split axis");
1141  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1142  {
1143  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1144 
1145  for ( d = 0; d < ndims_pageunion; d++ )
1146  {
1147  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) )
1148  {
1149  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1150  }
1151  else
1152  {
1153  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1154  }
1155 
1156  }
1157 
1158  }
1159 
1160  /*
1161  ** "Bad disposition", too many entries fell into one octant of the space, so no matter which
1162  ** plane we choose to split on, we're going to end up with a mostly full node. Where the
1163  ** data is pretty homogeneous (lots of duplicates) entries that are equidistant from the
1164  ** sides of the page union box can occasionally all end up in one place, leading
1165  ** to this condition.
1166  */
1167  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1168  {
1169  /*
1170  ** Instead we split on center points and see if we do better.
1171  ** First calculate the average center point for each axis.
1172  */
1173  double *avgCenter = palloc(ndims_pageunion * sizeof(double));
1174 
1175  for ( d = 0; d < ndims_pageunion; d++ )
1176  {
1177  avgCenter[d] = 0.0;
1178  }
1179 
1180  POSTGIS_DEBUG(4, "[GIST] picksplit can't find good split axis, trying center point method");
1181 
1182  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1183  {
1184  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1185  for ( d = 0; d < ndims_pageunion; d++ )
1186  {
1187  avgCenter[d] += (GIDX_GET_MAX(box_current,d) + GIDX_GET_MIN(box_current,d)) / 2.0;
1188  }
1189  }
1190  for ( d = 0; d < ndims_pageunion; d++ )
1191  {
1192  avgCenter[d] /= max_offset;
1193  pos[BELOW(d)] = pos[ABOVE(d)] = 0; /* Re-initialize our counters. */
1194  POSTGIS_DEBUGF(4, "[GIST] picksplit average center point[%d] = %.12g", d, avgCenter[d]);
1195  }
1196 
1197  /* For each of our entries... */
1198  for ( i = FirstOffsetNumber; i <= max_offset; i = OffsetNumberNext(i) )
1199  {
1200  double center;
1201  box_current = (GIDX*) DatumGetPointer(entryvec->vector[i].key);
1202 
1203  for ( d = 0; d < ndims_pageunion; d++ )
1204  {
1205  center = (GIDX_GET_MIN(box_current,d)+GIDX_GET_MAX(box_current,d))/2.0;
1206  if ( center < avgCenter[d] )
1207  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1208  else if ( FPeq(center, avgCenter[d]) )
1209  if ( pos[BELOW(d)] > pos[ABOVE(d)] )
1210  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1211  else
1212  gserialized_gist_picksplit_addlist(list[BELOW(d)], &(box_union[BELOW(d)]), box_current, &(pos[BELOW(d)]), i);
1213  else
1214  gserialized_gist_picksplit_addlist(list[ABOVE(d)], &(box_union[ABOVE(d)]), box_current, &(pos[ABOVE(d)]), i);
1215  }
1216 
1217  }
1218 
1219  /* Do we have a good disposition now? If not, screw it, just cut the node in half. */
1220  if ( gserialized_gist_picksplit_badratios(pos,ndims_pageunion) == TRUE )
1221  {
1222  POSTGIS_DEBUG(4, "[GIST] picksplit still cannot find a good split! just cutting the node in half");
1224  PG_RETURN_POINTER(v);
1225  }
1226 
1227  }
1228 
1229  /*
1230  ** Now, what splitting plane gives us the most even ratio of
1231  ** entries in our child pages? Since each split region has been apportioned entries
1232  ** against the same number of total entries, the axis that has the smallest maximum
1233  ** number of entries in its regions is the most evenly distributed.
1234  ** TODO: what if the distributions are equal in two or more axes?
1235  */
1236  for ( d = 0; d < ndims_pageunion; d++ )
1237  {
1238  int posd = Max(pos[ABOVE(d)],pos[BELOW(d)]);
1239  if ( posd < posmin )
1240  {
1241  direction = d;
1242  posmin = posd;
1243  }
1244  }
1245  if ( direction == -1 || posmin == entryvec->n )
1246  {
1247  /* ERROR OUT HERE */
1248  elog(ERROR, "Error in building split, unable to determine split direction.");
1249  }
1250 
1251  POSTGIS_DEBUGF(3, "[GIST] 'picksplit' splitting on axis %d", direction);
1252 
1254  pos[BELOW(direction)],
1255  &(box_union[BELOW(direction)]),
1256  list[ABOVE(direction)],
1257  pos[ABOVE(direction)],
1258  &(box_union[ABOVE(direction)]) );
1259 
1260  POSTGIS_DEBUGF(4, "[GIST] spl_ldatum: %s", gidx_to_string((GIDX*)v->spl_ldatum));
1261  POSTGIS_DEBUGF(4, "[GIST] spl_rdatum: %s", gidx_to_string((GIDX*)v->spl_rdatum));
1262 
1263  POSTGIS_DEBUGF(4, "[GIST] axis %d: parent range (%.12g, %.12g) left range (%.12g, %.12g), right range (%.12g, %.12g)",
1264  direction,
1265  GIDX_GET_MIN(box_pageunion, direction), GIDX_GET_MAX(box_pageunion, direction),
1266  GIDX_GET_MIN((GIDX*)v->spl_ldatum, direction), GIDX_GET_MAX((GIDX*)v->spl_ldatum, direction),
1267  GIDX_GET_MIN((GIDX*)v->spl_rdatum, direction), GIDX_GET_MAX((GIDX*)v->spl_rdatum, direction) );
1268 
1269  PG_RETURN_POINTER(v);
1270 
1271 }
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:11
#define ABOVE(d)
#define TRUE
Definition: dbfopen.c:170

Here is the call graph for this function: