#
#
# patch "database.cc"
#  from [244233392b6b1ee174b300df6c855606b58b010f]
#    to [1953bfcbbff1cef39434d8c5896ab4b7ef454458]
# 
# patch "schema.sql"
#  from [29a110d28b652d3d923e5c355092c6dc853fc999]
#    to [f9c13c1cc7ea3fa4ba4196b9291582b74a161c14]
# 
# patch "schema_migration.cc"
#  from [72a441aa9b77bdd8661c66e47d238ac4a7aa2b57]
#    to [16307957747ed7458f56319fefb71049a5c637c9]
# 
# patch "tests/schema_migration/__driver__.lua"
#  from [d708709c691b1536d54702969a8ffbffd5fa3c5f]
#    to [e875c22494147e62d954e6ea67fafebe5cde48c5]
#
============================================================
--- database.cc	244233392b6b1ee174b300df6c855606b58b010f
+++ database.cc	1953bfcbbff1cef39434d8c5896ab4b7ef454458
@@ -2016,30 +2016,33 @@ database::put_height_for_revision(revisi
 {
   I(!null_id(new_id));
   
-  rev_height height;
+  rev_height highest_parent;
+  // we always branch off the highest parent ...
   for (edge_map::const_iterator e = rev.edges.begin();
        e != rev.edges.end(); ++e)
     {
-      bool found(false);
-      u32 childnr(0);
-      rev_height candidate; MM(candidate);
       rev_height parent; MM(parent);
       get_rev_height(edge_old_revision(e), parent);
-      
-      while(!found)
+      if (parent > highest_parent)
+      {
+        highest_parent = parent;
+      }
+    }
+    
+  // ... then find the first unused child
+  u32 childnr(0);
+  rev_height candidate; MM(candidate);
+  while(true)
+    {
+      candidate = highest_parent.child_height(childnr);
+      if (!has_rev_height(candidate))
         {
-          candidate = parent.child_height(childnr);
-          if (!has_rev_height(candidate))
-            {
-              found = true;
-              if (candidate > height)
-                height = candidate;
-            }
-          I(childnr < std::numeric_limits<u32>::max());
-          ++childnr;
+          break;
         }
+      I(childnr < std::numeric_limits<u32>::max());
+      ++childnr;
     }
-  put_rev_height(new_id, height);
+  put_rev_height(new_id, candidate);
 }
 
 void
============================================================
--- schema.sql	29a110d28b652d3d923e5c355092c6dc853fc999
+++ schema.sql	f9c13c1cc7ea3fa4ba4196b9291582b74a161c14
@@ -54,6 +54,8 @@ CREATE TABLE heights
 	height not null,	-- complex height, array of big endian u32 integers
 	unique(revision, height)
 	);
+	
+CREATE INDEX heights__height ON heights (height);
 
 CREATE TABLE rosters
 	(
============================================================
--- schema_migration.cc	72a441aa9b77bdd8661c66e47d238ac4a7aa2b57
+++ schema_migration.cc	16307957747ed7458f56319fefb71049a5c637c9
@@ -610,6 +610,10 @@ char const migrate_add_heights[] =
   "  );"
   ;
 
+char const migrate_add_heights_index[] =
+  "CREATE INDEX heights__height ON heights (height);"
+  ;
+
 // this is a function because it has to refer to the numeric constant
 // defined in schema_migration.hh.
 static void
@@ -695,10 +699,13 @@ const migration_event migration_events[]
 
   { "48fd5d84f1e5a949ca093e87e5ac558da6e5956d",
     0, migrate_add_ccode, upgrade_none },
+    
+  { "fe48b0804e0048b87b4cea51b3ab338ba187bdc2",
+    migrate_add_heights_index, 0, upgrade_none },
 
   // The last entry in this table should always be the current
   // schema ID, with 0 for the migrators.
-  { "fe48b0804e0048b87b4cea51b3ab338ba187bdc2", 0, 0, upgrade_none }
+  { "7ca81b45279403419581d7fde31ed888a80bd34e", 0, 0, upgrade_none }
 };
 const size_t n_migration_events = (sizeof migration_events
                                    / sizeof migration_events[0]);
============================================================
--- tests/schema_migration/__driver__.lua	d708709c691b1536d54702969a8ffbffd5fa3c5f
+++ tests/schema_migration/__driver__.lua	e875c22494147e62d954e6ea67fafebe5cde48c5
@@ -117,3 +117,4 @@ check_migrate_from("fe48b0804e0048b87b4c
 check_migrate_from("ae196843d368d042f475e3dadfed11e9d7f9f01e", true)
 check_migrate_from("48fd5d84f1e5a949ca093e87e5ac558da6e5956d", false)
 check_migrate_from("fe48b0804e0048b87b4cea51b3ab338ba187bdc2", false)
+check_migrate_from("7ca81b45279403419581d7fde31ed888a80bd34e", false)