180
190
combine mem with the first and second indexes, creating a new one of
181
191
size 4x. On the fifth create a single new one, etc.
193
if self._combine_backing_indices:
194
(new_backing_file, size,
195
backing_pos) = self._spill_mem_keys_and_combine()
197
new_backing_file, size = self._spill_mem_keys_without_combining()
198
# Note: The transport here isn't strictly needed, because we will use
199
# direct access to the new_backing._file object
200
new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
202
# GC will clean up the file
203
new_backing._file = new_backing_file
204
if self._combine_backing_indices:
205
if len(self._backing_indices) == backing_pos:
206
self._backing_indices.append(None)
207
self._backing_indices[backing_pos] = new_backing
208
for backing_pos in range(backing_pos):
209
self._backing_indices[backing_pos] = None
211
self._backing_indices.append(new_backing)
213
self._nodes_by_key = None
215
def _spill_mem_keys_without_combining(self):
216
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
218
def _spill_mem_keys_and_combine(self):
183
219
iterators_to_combine = [self._iter_mem_nodes()]
185
221
for pos, backing in enumerate(self._backing_indices):
555
600
For InMemoryGraphIndex the estimate is exact.
557
return len(self._keys) + sum(backing.key_count() for backing in
602
return len(self._nodes) + sum(backing.key_count() for backing in
558
603
self._backing_indices if backing is not None)
560
605
def validate(self):
561
606
"""In memory index's have no known corruption at the moment."""
564
class _LeafNode(object):
609
class _LeafNode(dict):
565
610
"""A leaf node for a serialised B+Tree index."""
612
__slots__ = ('min_key', 'max_key', '_keys')
567
614
def __init__(self, bytes, key_length, ref_list_length):
568
615
"""Parse bytes to create a leaf node object."""
569
616
# splitlines mangles the \r delimiters.. don't use it.
570
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
571
key_length, ref_list_length))
617
key_list = _btree_serializer._parse_leaf_lines(bytes,
618
key_length, ref_list_length)
620
self.min_key = key_list[0][0]
621
self.max_key = key_list[-1][0]
623
self.min_key = self.max_key = None
624
super(_LeafNode, self).__init__(key_list)
625
self._keys = dict(self)
628
"""Return a sorted list of (key, (value, refs)) items"""
634
"""Return a sorted list of all keys."""
574
640
class _InternalNode(object):
575
641
"""An internal node for a serialised B+Tree index."""
643
__slots__ = ('keys', 'offset')
577
645
def __init__(self, bytes):
578
646
"""Parse bytes to create an internal node object."""
579
647
# splitlines mangles the \r delimiters.. don't use it.
996
1106
output.append(cur_out)
1109
def _walk_through_internal_nodes(self, keys):
1110
"""Take the given set of keys, and find the corresponding LeafNodes.
1112
:param keys: An unsorted iterable of keys to search for
1113
:return: (nodes, index_and_keys)
1114
nodes is a dict mapping {index: LeafNode}
1115
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1117
# 6 seconds spent in miss_torture using the sorted() line.
1118
# Even with out of order disk IO it seems faster not to sort it when
1119
# large queries are being made.
1120
keys_at_index = [(0, sorted(keys))]
1122
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1123
node_indexes = [idx for idx, s_keys in keys_at_index]
1124
nodes = self._get_internal_nodes(node_indexes)
1126
next_nodes_and_keys = []
1127
for node_index, sub_keys in keys_at_index:
1128
node = nodes[node_index]
1129
positions = self._multi_bisect_right(sub_keys, node.keys)
1130
node_offset = next_row_start + node.offset
1131
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1132
for pos, s_keys in positions])
1133
keys_at_index = next_nodes_and_keys
1134
# We should now be at the _LeafNodes
1135
node_indexes = [idx for idx, s_keys in keys_at_index]
1137
# TODO: We may *not* want to always read all the nodes in one
1138
# big go. Consider setting a max size on this.
1139
nodes = self._get_leaf_nodes(node_indexes)
1140
return nodes, keys_at_index
999
1142
def iter_entries(self, keys):
1000
1143
"""Iterate over keys within the index.
1039
1182
needed_keys = keys
1040
1183
if not needed_keys:
1042
# 6 seconds spent in miss_torture using the sorted() line.
1043
# Even with out of order disk IO it seems faster not to sort it when
1044
# large queries are being made.
1045
needed_keys = sorted(needed_keys)
1047
nodes_and_keys = [(0, needed_keys)]
1049
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1050
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1051
nodes = self._get_internal_nodes(node_indexes)
1053
next_nodes_and_keys = []
1054
for node_index, sub_keys in nodes_and_keys:
1055
node = nodes[node_index]
1056
positions = self._multi_bisect_right(sub_keys, node.keys)
1057
node_offset = next_row_start + node.offset
1058
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1059
for pos, s_keys in positions])
1060
nodes_and_keys = next_nodes_and_keys
1061
# We should now be at the _LeafNodes
1062
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1064
# TODO: We may *not* want to always read all the nodes in one
1065
# big go. Consider setting a max size on this.
1067
nodes = self._get_leaf_nodes(node_indexes)
1185
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1068
1186
for node_index, sub_keys in nodes_and_keys:
1069
1187
if not sub_keys:
1071
1189
node = nodes[node_index]
1072
1190
for next_sub_key in sub_keys:
1073
if next_sub_key in node.keys:
1074
value, refs = node.keys[next_sub_key]
1191
if next_sub_key in node:
1192
value, refs = node[next_sub_key]
1075
1193
if self.node_ref_lists:
1076
1194
yield (self, next_sub_key, value, refs)
1078
1196
yield (self, next_sub_key, value)
1198
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1199
"""Find the parent_map information for the set of keys.
1201
This populates the parent_map dict and missing_keys set based on the
1202
queried keys. It also can fill out an arbitrary number of parents that
1203
it finds while searching for the supplied keys.
1205
It is unlikely that you want to call this directly. See
1206
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1208
:param keys: A keys whose ancestry we want to return
1209
Every key will either end up in 'parent_map' or 'missing_keys'.
1210
:param ref_list_num: This index in the ref_lists is the parents we
1212
:param parent_map: {key: parent_keys} for keys that are present in this
1213
index. This may contain more entries than were in 'keys', that are
1214
reachable ancestors of the keys requested.
1215
:param missing_keys: keys which are known to be missing in this index.
1216
This may include parents that were not directly requested, but we
1217
were able to determine that they are not present in this index.
1218
:return: search_keys parents that were found but not queried to know
1219
if they are missing or present. Callers can re-query this index for
1220
those keys, and they will be placed into parent_map or missing_keys
1222
if not self.key_count():
1223
# We use key_count() to trigger reading the root node and
1224
# determining info about this BTreeGraphIndex
1225
# If we don't have any keys, then everything is missing
1226
missing_keys.update(keys)
1228
if ref_list_num >= self.node_ref_lists:
1229
raise ValueError('No ref list %d, index has %d ref lists'
1230
% (ref_list_num, self.node_ref_lists))
1232
# The main trick we are trying to accomplish is that when we find a
1233
# key listing its parents, we expect that the parent key is also likely
1234
# to sit on the same page. Allowing us to expand parents quickly
1235
# without suffering the full stack of bisecting, etc.
1236
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1238
# These are parent keys which could not be immediately resolved on the
1239
# page where the child was present. Note that we may already be
1240
# searching for that key, and it may actually be present [or known
1241
# missing] on one of the other pages we are reading.
1243
# We could try searching for them in the immediate previous or next
1244
# page. If they occur "later" we could put them in a pending lookup
1245
# set, and then for each node we read thereafter we could check to
1246
# see if they are present.
1247
# However, we don't know the impact of keeping this list of things
1248
# that I'm going to search for every node I come across from here on
1250
# It doesn't handle the case when the parent key is missing on a
1251
# page that we *don't* read. So we already have to handle being
1252
# re-entrant for that.
1253
# Since most keys contain a date string, they are more likely to be
1254
# found earlier in the file than later, but we would know that right
1255
# away (key < min_key), and wouldn't keep searching it on every other
1256
# page that we read.
1257
# Mostly, it is an idea, one which should be benchmarked.
1258
parents_not_on_page = set()
1260
for node_index, sub_keys in nodes_and_keys:
1263
# sub_keys is all of the keys we are looking for that should exist
1264
# on this page, if they aren't here, then they won't be found
1265
node = nodes[node_index]
1266
parents_to_check = set()
1267
for next_sub_key in sub_keys:
1268
if next_sub_key not in node:
1269
# This one is just not present in the index at all
1270
missing_keys.add(next_sub_key)
1272
value, refs = node[next_sub_key]
1273
parent_keys = refs[ref_list_num]
1274
parent_map[next_sub_key] = parent_keys
1275
parents_to_check.update(parent_keys)
1276
# Don't look for things we've already found
1277
parents_to_check = parents_to_check.difference(parent_map)
1278
# this can be used to test the benefit of having the check loop
1280
# parents_not_on_page.update(parents_to_check)
1282
while parents_to_check:
1283
next_parents_to_check = set()
1284
for key in parents_to_check:
1286
value, refs = node[key]
1287
parent_keys = refs[ref_list_num]
1288
parent_map[key] = parent_keys
1289
next_parents_to_check.update(parent_keys)
1291
# This parent either is genuinely missing, or should be
1292
# found on another page. Perf test whether it is better
1293
# to check if this node should fit on this page or not.
1294
# in the 'everything-in-one-pack' scenario, this *not*
1295
# doing the check is 237ms vs 243ms.
1296
# So slightly better, but I assume the standard 'lots
1297
# of packs' is going to show a reasonable improvement
1298
# from the check, because it avoids 'going around
1299
# again' for everything that is in another index
1300
# parents_not_on_page.add(key)
1301
# Missing for some reason
1302
if key < node.min_key:
1303
# in the case of bzr.dev, 3.4k/5.3k misses are
1304
# 'earlier' misses (65%)
1305
parents_not_on_page.add(key)
1306
elif key > node.max_key:
1307
# This parent key would be present on a different
1309
parents_not_on_page.add(key)
1311
# assert key != node.min_key and key != node.max_key
1312
# If it was going to be present, it would be on
1313
# *this* page, so mark it missing.
1314
missing_keys.add(key)
1315
parents_to_check = next_parents_to_check.difference(parent_map)
1316
# Might want to do another .difference() from missing_keys
1317
# parents_not_on_page could have been found on a different page, or be
1318
# known to be missing. So cull out everything that has already been
1320
search_keys = parents_not_on_page.difference(
1321
parent_map).difference(missing_keys)
1080
1324
def iter_entries_prefix(self, keys):
1081
1325
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
