From c690204c701f35bda2d19f14b0e8423c80cff1bb Mon Sep 17 00:00:00 2001
From: unknown <hf@deer.(none)>
Date: Tue, 25 May 2004 15:06:32 +0500
Subject: WL#1562 (Improving spatial code) A set of changes improving our RTree
 indexes and fixed few bugs found during the tests

myisam/rt_index.c:
  Algorythm for picking the branch to insert was fixed.
  pick_by_perimeter version of the algorythm added (mostly for testing
  purposes)
myisam/rt_index.h:
  minimal size of the page set to 1/3
  It noticeable increases searching performance
myisam/rt_key.c:
  counting of the size of the filled part of the page fixed
  rtree_choose_key moved to rt_index.c
myisam/rt_key.h:
  no need to make rtree_choose_key global
myisam/rt_mbr.c:
  operations for counting the perimeter of MBR added
myisam/rt_mbr.h:
  interface for rtree_perimeter_increase
myisam/rt_split.c:
  my_multi_malloc changed with my_alloca
sql/spatial.cc:
  LINESTRING object can consist of single point
---
 myisam/rt_index.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 90 insertions(+), 2 deletions(-)

(limited to 'myisam/rt_index.c')

diff --git a/myisam/rt_index.c b/myisam/rt_index.c
index 30146b9fd67..824cb7a396f 100644
--- a/myisam/rt_index.c
+++ b/myisam/rt_index.c
@@ -22,6 +22,8 @@
 #include "rt_mbr.h"
 
 #define REINSERT_BUFFER_INC 10
+#define PICK_BY_AREA
+/*#define PICK_BY_PERIMETER*/
 
 typedef struct st_page_level
 {
@@ -436,6 +438,92 @@ int rtree_get_next(MI_INFO *info, uint keynr, uint key_length)
 }
 
 
+/*
+  Choose non-leaf better key for insertion
+*/
+
+#ifdef PICK_BY_PERIMETER
+static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+			     uint key_length, uchar *page_buf, uint nod_flag)
+{
+  double increase;
+  double best_incr = DBL_MAX;
+  double perimeter;
+  double best_perimeter;
+  uchar *best_key;
+  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  uchar *last = rt_PAGE_END(page_buf);
+
+  LINT_INIT(best_perimeter);
+  LINT_INIT(best_key);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = rtree_perimeter_increase(keyinfo->seg, k, key, key_length,
+					     &perimeter)) == -1)
+      return NULL;
+    if (increase < best_incr)
+    {
+      best_key = k;
+      best_perimeter= perimeter;
+      best_incr = increase;
+    }
+    else
+    {
+      if ((increase == best_incr) && (perimeter < best_perimeter))
+      {
+        best_key = k;
+        best_perimeter= perimeter;
+        best_incr = increase;
+      }
+    }
+  }
+  return best_key;
+}
+
+#endif /*PICK_BY_PERIMETER*/
+
+#ifdef PICK_BY_AREA
+static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+			     uint key_length, uchar *page_buf, uint nod_flag)
+{
+  double increase;
+  double best_incr = DBL_MAX;
+  double area;
+  double best_area;
+  uchar *best_key;
+  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  uchar *last = rt_PAGE_END(page_buf);
+
+  LINT_INIT(best_area);
+  LINT_INIT(best_key);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = rtree_area_increase(keyinfo->seg, k, key, key_length, 
+                                        &area)) == -1)
+      return NULL;
+    if (increase < best_incr)
+    {
+      best_key = k;
+      best_area = area;
+      best_incr = increase;
+    }
+    else
+    {
+      if ((increase == best_incr) && (area < best_area))
+      {
+        best_key = k;
+        best_area = area;
+        best_incr = increase;
+      }
+    }
+  }
+  return best_key;
+}
+
+#endif /*PICK_BY_AREA*/
+
 /*
   Go down and insert key into tree
 
@@ -467,7 +555,7 @@ static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
       (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
   { 
-    if ((k = rtree_choose_key(info, keyinfo, key, key_length, page_buf, 
+    if ((k = rtree_pick_key(info, keyinfo, key, key_length, page_buf, 
                              nod_flag)) == NULL)
       goto err1;
     switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
@@ -577,7 +665,7 @@ static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key,
 
       mi_putint(new_root_buf, 2, nod_flag);
       if ((new_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
-                                                             HA_OFFSET_ERROR)
+	  HA_OFFSET_ERROR)
         goto err1;
 
       new_key = new_root_buf + keyinfo->block_length + nod_flag;
-- 
cgit v1.2.1