180
186
combine mem with the first and second indexes, creating a new one of
181
187
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(transport.get_transport('.'),
198
# GC will clean up the file
199
new_backing._file = new_backing_file
200
if self._combine_backing_indices:
201
if len(self._backing_indices) == backing_pos:
202
self._backing_indices.append(None)
203
self._backing_indices[backing_pos] = new_backing
204
for backing_pos in range(backing_pos):
205
self._backing_indices[backing_pos] = None
207
self._backing_indices.append(new_backing)
209
self._nodes_by_key = None
211
def _spill_mem_keys_without_combining(self):
212
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
214
def _spill_mem_keys_and_combine(self):
183
215
iterators_to_combine = [self._iter_mem_nodes()]
185
217
for pos, backing in enumerate(self._backing_indices):
189
221
iterators_to_combine.append(backing.iter_all_entries())
190
222
backing_pos = pos + 1
191
223
new_backing_file, size = \
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
224
self._write_nodes(self._iter_smallest(iterators_to_combine),
225
allow_optimize=False)
226
return new_backing_file, size, backing_pos
209
228
def add_nodes(self, nodes):
210
229
"""Add nodes to the index.
564
605
class _LeafNode(object):
565
606
"""A leaf node for a serialised B+Tree index."""
608
__slots__ = ('keys', 'min_key', 'max_key')
567
610
def __init__(self, bytes, key_length, ref_list_length):
568
611
"""Parse bytes to create a leaf node object."""
569
612
# 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))
613
key_list = _btree_serializer._parse_leaf_lines(bytes,
614
key_length, ref_list_length)
616
self.min_key = key_list[0][0]
617
self.max_key = key_list[-1][0]
619
self.min_key = self.max_key = None
620
self.keys = dict(key_list)
574
623
class _InternalNode(object):
575
624
"""An internal node for a serialised B+Tree index."""
626
__slots__ = ('keys', 'offset')
577
628
def __init__(self, bytes):
578
629
"""Parse bytes to create an internal node object."""
579
630
# splitlines mangles the \r delimiters.. don't use it.
801
867
new_tips = next_tips
802
868
return final_offsets
870
def clear_cache(self):
871
"""Clear out any cached/memoized values.
873
This can be called at any time, but generally it is used when we have
874
extracted some information, but don't expect to be requesting any more
877
# Note that we don't touch self._root_node or self._internal_node_cache
878
# We don't expect either of those to be big, and it can save
879
# round-trips in the future. We may re-evaluate this if InternalNode
880
# memory starts to be an issue.
881
self._leaf_node_cache.clear()
883
def external_references(self, ref_list_num):
884
if self._root_node is None:
885
self._get_root_node()
886
if ref_list_num + 1 > self.node_ref_lists:
887
raise ValueError('No ref list %d, index has %d ref lists'
888
% (ref_list_num, self.node_ref_lists))
891
for node in self.iter_all_entries():
893
refs.update(node[3][ref_list_num])
804
896
def _find_layer_first_and_end(self, offset):
805
897
"""Find the start/stop nodes for the layer corresponding to offset.
996
1088
output.append(cur_out)
1091
def _walk_through_internal_nodes(self, keys):
1092
"""Take the given set of keys, and find the corresponding LeafNodes.
1094
:param keys: An unsorted iterable of keys to search for
1095
:return: (nodes, index_and_keys)
1096
nodes is a dict mapping {index: LeafNode}
1097
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1099
# 6 seconds spent in miss_torture using the sorted() line.
1100
# Even with out of order disk IO it seems faster not to sort it when
1101
# large queries are being made.
1102
keys_at_index = [(0, sorted(keys))]
1104
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1105
node_indexes = [idx for idx, s_keys in keys_at_index]
1106
nodes = self._get_internal_nodes(node_indexes)
1108
next_nodes_and_keys = []
1109
for node_index, sub_keys in keys_at_index:
1110
node = nodes[node_index]
1111
positions = self._multi_bisect_right(sub_keys, node.keys)
1112
node_offset = next_row_start + node.offset
1113
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1114
for pos, s_keys in positions])
1115
keys_at_index = next_nodes_and_keys
1116
# We should now be at the _LeafNodes
1117
node_indexes = [idx for idx, s_keys in keys_at_index]
1119
# TODO: We may *not* want to always read all the nodes in one
1120
# big go. Consider setting a max size on this.
1121
nodes = self._get_leaf_nodes(node_indexes)
1122
return nodes, keys_at_index
999
1124
def iter_entries(self, keys):
1000
1125
"""Iterate over keys within the index.
1039
1164
needed_keys = keys
1040
1165
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)
1167
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1068
1168
for node_index, sub_keys in nodes_and_keys:
1069
1169
if not sub_keys:
1078
1178
yield (self, next_sub_key, value)
1180
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1181
"""Find the parent_map information for the set of keys.
1183
This populates the parent_map dict and missing_keys set based on the
1184
queried keys. It also can fill out an arbitrary number of parents that
1185
it finds while searching for the supplied keys.
1187
It is unlikely that you want to call this directly. See
1188
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1190
:param keys: A keys whose ancestry we want to return
1191
Every key will either end up in 'parent_map' or 'missing_keys'.
1192
:param ref_list_num: This index in the ref_lists is the parents we
1194
:param parent_map: {key: parent_keys} for keys that are present in this
1195
index. This may contain more entries than were in 'keys', that are
1196
reachable ancestors of the keys requested.
1197
:param missing_keys: keys which are known to be missing in this index.
1198
This may include parents that were not directly requested, but we
1199
were able to determine that they are not present in this index.
1200
:return: search_keys parents that were found but not queried to know
1201
if they are missing or present. Callers can re-query this index for
1202
those keys, and they will be placed into parent_map or missing_keys
1204
if not self.key_count():
1205
# We use key_count() to trigger reading the root node and
1206
# determining info about this BTreeGraphIndex
1207
# If we don't have any keys, then everything is missing
1208
missing_keys.update(keys)
1210
if ref_list_num >= self.node_ref_lists:
1211
raise ValueError('No ref list %d, index has %d ref lists'
1212
% (ref_list_num, self.node_ref_lists))
1214
# The main trick we are trying to accomplish is that when we find a
1215
# key listing its parents, we expect that the parent key is also likely
1216
# to sit on the same page. Allowing us to expand parents quickly
1217
# without suffering the full stack of bisecting, etc.
1218
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1220
# These are parent keys which could not be immediately resolved on the
1221
# page where the child was present. Note that we may already be
1222
# searching for that key, and it may actually be present [or known
1223
# missing] on one of the other pages we are reading.
1225
# We could try searching for them in the immediate previous or next
1226
# page. If they occur "later" we could put them in a pending lookup
1227
# set, and then for each node we read thereafter we could check to
1228
# see if they are present.
1229
# However, we don't know the impact of keeping this list of things
1230
# that I'm going to search for every node I come across from here on
1232
# It doesn't handle the case when the parent key is missing on a
1233
# page that we *don't* read. So we already have to handle being
1234
# re-entrant for that.
1235
# Since most keys contain a date string, they are more likely to be
1236
# found earlier in the file than later, but we would know that right
1237
# away (key < min_key), and wouldn't keep searching it on every other
1238
# page that we read.
1239
# Mostly, it is an idea, one which should be benchmarked.
1240
parents_not_on_page = set()
1242
for node_index, sub_keys in nodes_and_keys:
1245
# sub_keys is all of the keys we are looking for that should exist
1246
# on this page, if they aren't here, then they won't be found
1247
node = nodes[node_index]
1248
node_keys = node.keys
1249
parents_to_check = set()
1250
for next_sub_key in sub_keys:
1251
if next_sub_key not in node_keys:
1252
# This one is just not present in the index at all
1253
missing_keys.add(next_sub_key)
1255
value, refs = node_keys[next_sub_key]
1256
parent_keys = refs[ref_list_num]
1257
parent_map[next_sub_key] = parent_keys
1258
parents_to_check.update(parent_keys)
1259
# Don't look for things we've already found
1260
parents_to_check = parents_to_check.difference(parent_map)
1261
# this can be used to test the benefit of having the check loop
1263
# parents_not_on_page.update(parents_to_check)
1265
while parents_to_check:
1266
next_parents_to_check = set()
1267
for key in parents_to_check:
1268
if key in node_keys:
1269
value, refs = node_keys[key]
1270
parent_keys = refs[ref_list_num]
1271
parent_map[key] = parent_keys
1272
next_parents_to_check.update(parent_keys)
1274
# This parent either is genuinely missing, or should be
1275
# found on another page. Perf test whether it is better
1276
# to check if this node should fit on this page or not.
1277
# in the 'everything-in-one-pack' scenario, this *not*
1278
# doing the check is 237ms vs 243ms.
1279
# So slightly better, but I assume the standard 'lots
1280
# of packs' is going to show a reasonable improvement
1281
# from the check, because it avoids 'going around
1282
# again' for everything that is in another index
1283
# parents_not_on_page.add(key)
1284
# Missing for some reason
1285
if key < node.min_key:
1286
# in the case of bzr.dev, 3.4k/5.3k misses are
1287
# 'earlier' misses (65%)
1288
parents_not_on_page.add(key)
1289
elif key > node.max_key:
1290
# This parent key would be present on a different
1292
parents_not_on_page.add(key)
1294
# assert key != node.min_key and key != node.max_key
1295
# If it was going to be present, it would be on
1296
# *this* page, so mark it missing.
1297
missing_keys.add(key)
1298
parents_to_check = next_parents_to_check.difference(parent_map)
1299
# Might want to do another .difference() from missing_keys
1300
# parents_not_on_page could have been found on a different page, or be
1301
# known to be missing. So cull out everything that has already been
1303
search_keys = parents_not_on_page.difference(
1304
parent_map).difference(missing_keys)
1080
1307
def iter_entries_prefix(self, keys):
1081
1308
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
