Rev 68: Reduce the number of string comparisons during prefix lookups in BTree indices. in http://people.ubuntu.com/~robertc/baz2.0/plugins/search/trunk

[Robert Collins]

At http://people.ubuntu.com/~robertc/baz2.0/plugins/search/trunk

------------------------------------------------------------
revno: 68
revision-id: robertc at robertcollins.net-20090121064842-avtykqfcn1kfvkj3
parent: robertc at robertcollins.net-20090121044253-cm1ogklzp31qpkvj
committer: Robert Collins <robertc at robertcollins.net>
branch nick: trunk
timestamp: Wed 2009-01-21 17:48:42 +1100
message:
  Reduce the number of string comparisons during prefix lookups in BTree indices.
=== modified file 'index.py'
--- a/index.py	2009-01-21 04:42:53 +0000
+++ b/index.py	2009-01-21 06:48:42 +0000
@@ -17,6 +17,7 @@
 
 """The core logic for search."""
 
+from bisect import bisect_left
 from itertools import chain
 import math
 import re
@@ -1414,11 +1415,22 @@
             for node in nodes.values():
                 # TODO bisect the edge nodes? / find boundaries and so skip
                 # some work.
-                for node_key, (value, refs) in sorted(node.keys.iteritems()):
+                items = sorted(node.keys.items())
+                low_value = (key, ())
+                start_pos = bisect_left(low_value, items)
+                for pos in xrange(start_pos, len(items)):
+                    node_key, (value, refs) = items[pos]
                     if node_key[:-1] != key_prefix:
+                        # Shouldn't happen, but may.
                         continue
                     if not node_key[-1].startswith(key_suffix):
-                        continue
+                        # A node that doesn't match
+                        if node_key[-1] > key_suffix:
+                            # and is after: stop
+                            break
+                        else:
+                            # was before the search start point.
+                            continue
                     if self.node_ref_lists:
                         yield (self, node_key, value, refs)
                     else: