186
180
combine mem with the first and second indexes, creating a new one of
187
181
size 4x. On the fifth create a single new one, etc.
189
if self._combine_backing_indices:
190
(new_backing_file, size,
191
backing_pos) = self._spill_mem_keys_and_combine()
193
new_backing_file, size = self._spill_mem_keys_without_combining()
194
# Note: The transport here isn't strictly needed, because we will use
195
# direct access to the new_backing._file object
196
new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
197
# GC will clean up the file
198
new_backing._file = new_backing_file
199
if self._combine_backing_indices:
200
if len(self._backing_indices) == backing_pos:
201
self._backing_indices.append(None)
202
self._backing_indices[backing_pos] = new_backing
203
for backing_pos in range(backing_pos):
204
self._backing_indices[backing_pos] = None
206
self._backing_indices.append(new_backing)
208
self._nodes_by_key = None
210
def _spill_mem_keys_without_combining(self):
211
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
213
def _spill_mem_keys_and_combine(self):
214
183
iterators_to_combine = [self._iter_mem_nodes()]
216
185
for pos, backing in enumerate(self._backing_indices):
220
189
iterators_to_combine.append(backing.iter_all_entries())
221
190
backing_pos = pos + 1
222
191
new_backing_file, size = \
223
self._write_nodes(self._iter_smallest(iterators_to_combine),
224
allow_optimize=False)
225
return new_backing_file, size, backing_pos
192
self._write_nodes(self._iter_smallest(iterators_to_combine))
193
dir_path, base_name = osutils.split(new_backing_file.name)
194
# Note: The transport here isn't strictly needed, because we will use
195
# direct access to the new_backing._file object
196
new_backing = BTreeGraphIndex(get_transport(dir_path),
198
# GC will clean up the file
199
new_backing._file = new_backing_file
200
if len(self._backing_indices) == backing_pos:
201
self._backing_indices.append(None)
202
self._backing_indices[backing_pos] = new_backing
203
for pos in range(backing_pos):
204
self._backing_indices[pos] = None
207
self._nodes_by_key = None
227
209
def add_nodes(self, nodes):
228
210
"""Add nodes to the index.
463
431
efficient order for the index (keys iteration order in this case).
466
# Note: We don't use keys.intersection() here. If you read the C api,
467
# set.intersection(other) special cases when other is a set and
468
# will iterate the smaller of the two and lookup in the other.
469
# It does *not* do this for any other type (even dict, unlike
470
# some other set functions.) Since we expect keys is generally <<
471
# self._nodes, it is faster to iterate over it in a list
474
local_keys = [key for key in keys if key in nodes]
475
434
if self.reference_lists:
476
for key in local_keys:
435
for key in keys.intersection(self._keys):
436
node = self._nodes[key]
478
437
yield self, key, node[1], node[0]
480
for key in local_keys:
439
for key in keys.intersection(self._keys):
440
node = self._nodes[key]
482
441
yield self, key, node[1]
483
# Find things that are in backing indices that have not been handled
485
if not self._backing_indices:
486
return # We won't find anything there either
487
# Remove all of the keys that we found locally
488
keys.difference_update(local_keys)
442
keys.difference_update(self._keys)
489
443
for backing in self._backing_indices:
490
444
if backing is None:
604
558
class _LeafNode(object):
605
559
"""A leaf node for a serialised B+Tree index."""
607
__slots__ = ('keys', 'min_key', 'max_key')
609
561
def __init__(self, bytes, key_length, ref_list_length):
610
562
"""Parse bytes to create a leaf node object."""
611
563
# splitlines mangles the \r delimiters.. don't use it.
612
key_list = _btree_serializer._parse_leaf_lines(bytes,
613
key_length, ref_list_length)
615
self.min_key = key_list[0][0]
616
self.max_key = key_list[-1][0]
618
self.min_key = self.max_key = None
619
self.keys = dict(key_list)
564
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
565
key_length, ref_list_length))
622
568
class _InternalNode(object):
623
569
"""An internal node for a serialised B+Tree index."""
625
__slots__ = ('keys', 'offset')
627
571
def __init__(self, bytes):
628
572
"""Parse bytes to create an internal node object."""
629
573
# splitlines mangles the \r delimiters.. don't use it.
866
795
new_tips = next_tips
867
796
return final_offsets
869
def clear_cache(self):
870
"""Clear out any cached/memoized values.
872
This can be called at any time, but generally it is used when we have
873
extracted some information, but don't expect to be requesting any more
876
# Note that we don't touch self._root_node or self._internal_node_cache
877
# We don't expect either of those to be big, and it can save
878
# round-trips in the future. We may re-evaluate this if InternalNode
879
# memory starts to be an issue.
880
self._leaf_node_cache.clear()
882
def external_references(self, ref_list_num):
883
if self._root_node is None:
884
self._get_root_node()
885
if ref_list_num + 1 > self.node_ref_lists:
886
raise ValueError('No ref list %d, index has %d ref lists'
887
% (ref_list_num, self.node_ref_lists))
890
for node in self.iter_all_entries():
892
refs.update(node[3][ref_list_num])
895
798
def _find_layer_first_and_end(self, offset):
896
799
"""Find the start/stop nodes for the layer corresponding to offset.
946
849
return self._get_nodes(self._internal_node_cache, node_indexes)
948
def _cache_leaf_values(self, nodes):
949
"""Cache directly from key => value, skipping the btree."""
851
def _get_leaf_nodes(self, node_indexes):
852
"""Get a bunch of nodes, from cache or disk."""
853
found = self._get_nodes(self._leaf_node_cache, node_indexes)
950
854
if self._leaf_value_cache is not None:
951
for node in nodes.itervalues():
855
for node in found.itervalues():
952
856
for key, value in node.keys.iteritems():
953
857
if key in self._leaf_value_cache:
954
858
# Don't add the rest of the keys, we've seen this node
957
861
self._leaf_value_cache[key] = value
959
def _get_leaf_nodes(self, node_indexes):
960
"""Get a bunch of nodes, from cache or disk."""
961
found = self._get_nodes(self._leaf_node_cache, node_indexes)
962
self._cache_leaf_values(found)
965
864
def iter_all_entries(self):
976
875
"iter_all_entries scales with size of history.")
977
876
if not self.key_count():
979
if self._row_offsets[-1] == 1:
980
# There is only the root node, and we read that via key_count()
981
if self.node_ref_lists:
982
for key, (value, refs) in sorted(self._root_node.keys.items()):
983
yield (self, key, value, refs)
985
for key, (value, refs) in sorted(self._root_node.keys.items()):
986
yield (self, key, value)
988
878
start_of_leaves = self._row_offsets[-2]
989
879
end_of_leaves = self._row_offsets[-1]
990
needed_offsets = range(start_of_leaves, end_of_leaves)
991
if needed_offsets == [0]:
992
# Special case when we only have a root node, as we have already
994
nodes = [(0, self._root_node)]
996
nodes = self._read_nodes(needed_offsets)
880
needed_nodes = range(start_of_leaves, end_of_leaves)
997
881
# We iterate strictly in-order so that we can use this function
998
882
# for spilling index builds to disk.
999
883
if self.node_ref_lists:
1000
for _, node in nodes:
884
for _, node in self._read_nodes(needed_nodes):
1001
885
for key, (value, refs) in sorted(node.keys.items()):
1002
886
yield (self, key, value, refs)
1004
for _, node in nodes:
888
for _, node in self._read_nodes(needed_nodes):
1005
889
for key, (value, refs) in sorted(node.keys.items()):
1006
890
yield (self, key, value)
1087
971
output.append(cur_out)
1090
def _walk_through_internal_nodes(self, keys):
1091
"""Take the given set of keys, and find the corresponding LeafNodes.
1093
:param keys: An unsorted iterable of keys to search for
1094
:return: (nodes, index_and_keys)
1095
nodes is a dict mapping {index: LeafNode}
1096
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1098
# 6 seconds spent in miss_torture using the sorted() line.
1099
# Even with out of order disk IO it seems faster not to sort it when
1100
# large queries are being made.
1101
keys_at_index = [(0, sorted(keys))]
1103
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1104
node_indexes = [idx for idx, s_keys in keys_at_index]
1105
nodes = self._get_internal_nodes(node_indexes)
1107
next_nodes_and_keys = []
1108
for node_index, sub_keys in keys_at_index:
1109
node = nodes[node_index]
1110
positions = self._multi_bisect_right(sub_keys, node.keys)
1111
node_offset = next_row_start + node.offset
1112
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1113
for pos, s_keys in positions])
1114
keys_at_index = next_nodes_and_keys
1115
# We should now be at the _LeafNodes
1116
node_indexes = [idx for idx, s_keys in keys_at_index]
1118
# TODO: We may *not* want to always read all the nodes in one
1119
# big go. Consider setting a max size on this.
1120
nodes = self._get_leaf_nodes(node_indexes)
1121
return nodes, keys_at_index
1123
974
def iter_entries(self, keys):
1124
975
"""Iterate over keys within the index.
1163
1014
needed_keys = keys
1164
1015
if not needed_keys:
1166
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1017
# 6 seconds spent in miss_torture using the sorted() line.
1018
# Even with out of order disk IO it seems faster not to sort it when
1019
# large queries are being made.
1020
needed_keys = sorted(needed_keys)
1022
nodes_and_keys = [(0, needed_keys)]
1024
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1025
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1026
nodes = self._get_internal_nodes(node_indexes)
1028
next_nodes_and_keys = []
1029
for node_index, sub_keys in nodes_and_keys:
1030
node = nodes[node_index]
1031
positions = self._multi_bisect_right(sub_keys, node.keys)
1032
node_offset = next_row_start + node.offset
1033
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1034
for pos, s_keys in positions])
1035
nodes_and_keys = next_nodes_and_keys
1036
# We should now be at the _LeafNodes
1037
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1039
# TODO: We may *not* want to always read all the nodes in one
1040
# big go. Consider setting a max size on this.
1042
nodes = self._get_leaf_nodes(node_indexes)
1167
1043
for node_index, sub_keys in nodes_and_keys:
1168
1044
if not sub_keys:
1177
1053
yield (self, next_sub_key, value)
1179
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1180
"""Find the parent_map information for the set of keys.
1182
This populates the parent_map dict and missing_keys set based on the
1183
queried keys. It also can fill out an arbitrary number of parents that
1184
it finds while searching for the supplied keys.
1186
It is unlikely that you want to call this directly. See
1187
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1189
:param keys: A keys whose ancestry we want to return
1190
Every key will either end up in 'parent_map' or 'missing_keys'.
1191
:param ref_list_num: This index in the ref_lists is the parents we
1193
:param parent_map: {key: parent_keys} for keys that are present in this
1194
index. This may contain more entries than were in 'keys', that are
1195
reachable ancestors of the keys requested.
1196
:param missing_keys: keys which are known to be missing in this index.
1197
This may include parents that were not directly requested, but we
1198
were able to determine that they are not present in this index.
1199
:return: search_keys parents that were found but not queried to know
1200
if they are missing or present. Callers can re-query this index for
1201
those keys, and they will be placed into parent_map or missing_keys
1203
if not self.key_count():
1204
# We use key_count() to trigger reading the root node and
1205
# determining info about this BTreeGraphIndex
1206
# If we don't have any keys, then everything is missing
1207
missing_keys.update(keys)
1209
if ref_list_num >= self.node_ref_lists:
1210
raise ValueError('No ref list %d, index has %d ref lists'
1211
% (ref_list_num, self.node_ref_lists))
1213
# The main trick we are trying to accomplish is that when we find a
1214
# key listing its parents, we expect that the parent key is also likely
1215
# to sit on the same page. Allowing us to expand parents quickly
1216
# without suffering the full stack of bisecting, etc.
1217
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1219
# These are parent keys which could not be immediately resolved on the
1220
# page where the child was present. Note that we may already be
1221
# searching for that key, and it may actually be present [or known
1222
# missing] on one of the other pages we are reading.
1224
# We could try searching for them in the immediate previous or next
1225
# page. If they occur "later" we could put them in a pending lookup
1226
# set, and then for each node we read thereafter we could check to
1227
# see if they are present.
1228
# However, we don't know the impact of keeping this list of things
1229
# that I'm going to search for every node I come across from here on
1231
# It doesn't handle the case when the parent key is missing on a
1232
# page that we *don't* read. So we already have to handle being
1233
# re-entrant for that.
1234
# Since most keys contain a date string, they are more likely to be
1235
# found earlier in the file than later, but we would know that right
1236
# away (key < min_key), and wouldn't keep searching it on every other
1237
# page that we read.
1238
# Mostly, it is an idea, one which should be benchmarked.
1239
parents_not_on_page = set()
1241
for node_index, sub_keys in nodes_and_keys:
1244
# sub_keys is all of the keys we are looking for that should exist
1245
# on this page, if they aren't here, then they won't be found
1246
node = nodes[node_index]
1247
node_keys = node.keys
1248
parents_to_check = set()
1249
for next_sub_key in sub_keys:
1250
if next_sub_key not in node_keys:
1251
# This one is just not present in the index at all
1252
missing_keys.add(next_sub_key)
1254
value, refs = node_keys[next_sub_key]
1255
parent_keys = refs[ref_list_num]
1256
parent_map[next_sub_key] = parent_keys
1257
parents_to_check.update(parent_keys)
1258
# Don't look for things we've already found
1259
parents_to_check = parents_to_check.difference(parent_map)
1260
# this can be used to test the benefit of having the check loop
1262
# parents_not_on_page.update(parents_to_check)
1264
while parents_to_check:
1265
next_parents_to_check = set()
1266
for key in parents_to_check:
1267
if key in node_keys:
1268
value, refs = node_keys[key]
1269
parent_keys = refs[ref_list_num]
1270
parent_map[key] = parent_keys
1271
next_parents_to_check.update(parent_keys)
1273
# This parent either is genuinely missing, or should be
1274
# found on another page. Perf test whether it is better
1275
# to check if this node should fit on this page or not.
1276
# in the 'everything-in-one-pack' scenario, this *not*
1277
# doing the check is 237ms vs 243ms.
1278
# So slightly better, but I assume the standard 'lots
1279
# of packs' is going to show a reasonable improvement
1280
# from the check, because it avoids 'going around
1281
# again' for everything that is in another index
1282
# parents_not_on_page.add(key)
1283
# Missing for some reason
1284
if key < node.min_key:
1285
# in the case of bzr.dev, 3.4k/5.3k misses are
1286
# 'earlier' misses (65%)
1287
parents_not_on_page.add(key)
1288
elif key > node.max_key:
1289
# This parent key would be present on a different
1291
parents_not_on_page.add(key)
1293
# assert key != node.min_key and key != node.max_key
1294
# If it was going to be present, it would be on
1295
# *this* page, so mark it missing.
1296
missing_keys.add(key)
1297
parents_to_check = next_parents_to_check.difference(parent_map)
1298
# Might want to do another .difference() from missing_keys
1299
# parents_not_on_page could have been found on a different page, or be
1300
# known to be missing. So cull out everything that has already been
1302
search_keys = parents_not_on_page.difference(
1303
parent_map).difference(missing_keys)
1306
1055
def iter_entries_prefix(self, keys):
1307
1056
"""Iterate over keys within the index using prefix matching.
1486
1235
"""Read some nodes from disk into the LRU cache.
1488
1237
This performs a readv to get the node data into memory, and parses each
1489
node, then yields it to the caller. The nodes are requested in the
1238
node, the yields it to the caller. The nodes are requested in the
1490
1239
supplied order. If possible doing sort() on the list before requesting
1491
1240
a read may improve performance.
1493
1242
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1496
# may be the byte string of the whole file
1498
# list of (offset, length) regions of the file that should, evenually
1499
# be read in to data_ranges, either from 'bytes' or from the transport
1501
base_offset = self._base_offset
1502
1246
for index in nodes:
1503
offset = (index * _PAGE_SIZE)
1247
offset = index * _PAGE_SIZE
1504
1248
size = _PAGE_SIZE
1506
1250
# Root node - special case
1508
1252
size = min(_PAGE_SIZE, self._size)
1510
# The only case where we don't know the size, is for very
1511
# small indexes. So we read the whole thing
1512
bytes = self._transport.get_bytes(self._name)
1513
num_bytes = len(bytes)
1514
self._size = num_bytes - base_offset
1515
# the whole thing should be parsed out of 'bytes'
1516
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1517
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1254
stream = self._transport.get(self._name)
1255
start = stream.read(_PAGE_SIZE)
1256
# Avoid doing this again
1257
self._size = len(start)
1258
size = min(_PAGE_SIZE, self._size)
1520
1260
if offset > self._size:
1521
1261
raise AssertionError('tried to read past the end'
1522
1262
' of the file %s > %s'
1523
1263
% (offset, self._size))
1524
1264
size = min(size, self._size - offset)
1525
ranges.append((base_offset + offset, size))
1265
ranges.append((offset, size))
1528
elif bytes is not None:
1529
# already have the whole file
1530
data_ranges = [(start, bytes[start:start+size])
1531
for start, size in ranges]
1532
elif self._file is None:
1268
if self._file is None:
1533
1269
data_ranges = self._transport.readv(self._name, ranges)
1535
1271
data_ranges = []
added
removed
bzrlib/btree_index.py
