596
577
For InMemoryGraphIndex the estimate is exact.
598
return len(self._nodes) + sum(backing.key_count() for backing in
579
return len(self._keys) + sum(backing.key_count() for backing in
599
580
self._backing_indices if backing is not None)
601
582
def validate(self):
602
583
"""In memory index's have no known corruption at the moment."""
605
class _LeafNode(dict):
586
class _LeafNode(object):
606
587
"""A leaf node for a serialised B+Tree index."""
608
__slots__ = ('min_key', 'max_key', '_keys')
589
__slots__ = ('keys',)
610
591
def __init__(self, bytes, key_length, ref_list_length):
611
592
"""Parse bytes to create a leaf node object."""
612
593
# splitlines mangles the \r delimiters.. don't use it.
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
super(_LeafNode, self).__init__(key_list)
621
self._keys = dict(self)
624
"""Return a sorted list of (key, (value, refs)) items"""
630
"""Return a sorted list of all keys."""
594
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
595
key_length, ref_list_length))
636
598
class _InternalNode(object):
1102
1039
output.append(cur_out)
1105
def _walk_through_internal_nodes(self, keys):
1106
"""Take the given set of keys, and find the corresponding LeafNodes.
1108
:param keys: An unsorted iterable of keys to search for
1109
:return: (nodes, index_and_keys)
1110
nodes is a dict mapping {index: LeafNode}
1111
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1113
# 6 seconds spent in miss_torture using the sorted() line.
1114
# Even with out of order disk IO it seems faster not to sort it when
1115
# large queries are being made.
1116
keys_at_index = [(0, sorted(keys))]
1118
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1119
node_indexes = [idx for idx, s_keys in keys_at_index]
1120
nodes = self._get_internal_nodes(node_indexes)
1122
next_nodes_and_keys = []
1123
for node_index, sub_keys in keys_at_index:
1124
node = nodes[node_index]
1125
positions = self._multi_bisect_right(sub_keys, node.keys)
1126
node_offset = next_row_start + node.offset
1127
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1128
for pos, s_keys in positions])
1129
keys_at_index = next_nodes_and_keys
1130
# We should now be at the _LeafNodes
1131
node_indexes = [idx for idx, s_keys in keys_at_index]
1133
# TODO: We may *not* want to always read all the nodes in one
1134
# big go. Consider setting a max size on this.
1135
nodes = self._get_leaf_nodes(node_indexes)
1136
return nodes, keys_at_index
1138
1042
def iter_entries(self, keys):
1139
1043
"""Iterate over keys within the index.
1178
1082
needed_keys = keys
1179
1083
if not needed_keys:
1181
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1085
# 6 seconds spent in miss_torture using the sorted() line.
1086
# Even with out of order disk IO it seems faster not to sort it when
1087
# large queries are being made.
1088
needed_keys = sorted(needed_keys)
1090
nodes_and_keys = [(0, needed_keys)]
1092
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1093
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1094
nodes = self._get_internal_nodes(node_indexes)
1096
next_nodes_and_keys = []
1097
for node_index, sub_keys in nodes_and_keys:
1098
node = nodes[node_index]
1099
positions = self._multi_bisect_right(sub_keys, node.keys)
1100
node_offset = next_row_start + node.offset
1101
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1102
for pos, s_keys in positions])
1103
nodes_and_keys = next_nodes_and_keys
1104
# We should now be at the _LeafNodes
1105
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1107
# TODO: We may *not* want to always read all the nodes in one
1108
# big go. Consider setting a max size on this.
1110
nodes = self._get_leaf_nodes(node_indexes)
1182
1111
for node_index, sub_keys in nodes_and_keys:
1183
1112
if not sub_keys:
1185
1114
node = nodes[node_index]
1186
1115
for next_sub_key in sub_keys:
1187
if next_sub_key in node:
1188
value, refs = node[next_sub_key]
1116
if next_sub_key in node.keys:
1117
value, refs = node.keys[next_sub_key]
1189
1118
if self.node_ref_lists:
1190
1119
yield (self, next_sub_key, value, refs)
1192
1121
yield (self, next_sub_key, value)
1194
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1195
"""Find the parent_map information for the set of keys.
1197
This populates the parent_map dict and missing_keys set based on the
1198
queried keys. It also can fill out an arbitrary number of parents that
1199
it finds while searching for the supplied keys.
1201
It is unlikely that you want to call this directly. See
1202
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1204
:param keys: A keys whose ancestry we want to return
1205
Every key will either end up in 'parent_map' or 'missing_keys'.
1206
:param ref_list_num: This index in the ref_lists is the parents we
1208
:param parent_map: {key: parent_keys} for keys that are present in this
1209
index. This may contain more entries than were in 'keys', that are
1210
reachable ancestors of the keys requested.
1211
:param missing_keys: keys which are known to be missing in this index.
1212
This may include parents that were not directly requested, but we
1213
were able to determine that they are not present in this index.
1214
:return: search_keys parents that were found but not queried to know
1215
if they are missing or present. Callers can re-query this index for
1216
those keys, and they will be placed into parent_map or missing_keys
1218
if not self.key_count():
1219
# We use key_count() to trigger reading the root node and
1220
# determining info about this BTreeGraphIndex
1221
# If we don't have any keys, then everything is missing
1222
missing_keys.update(keys)
1224
if ref_list_num >= self.node_ref_lists:
1225
raise ValueError('No ref list %d, index has %d ref lists'
1226
% (ref_list_num, self.node_ref_lists))
1228
# The main trick we are trying to accomplish is that when we find a
1229
# key listing its parents, we expect that the parent key is also likely
1230
# to sit on the same page. Allowing us to expand parents quickly
1231
# without suffering the full stack of bisecting, etc.
1232
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1234
# These are parent keys which could not be immediately resolved on the
1235
# page where the child was present. Note that we may already be
1236
# searching for that key, and it may actually be present [or known
1237
# missing] on one of the other pages we are reading.
1239
# We could try searching for them in the immediate previous or next
1240
# page. If they occur "later" we could put them in a pending lookup
1241
# set, and then for each node we read thereafter we could check to
1242
# see if they are present.
1243
# However, we don't know the impact of keeping this list of things
1244
# that I'm going to search for every node I come across from here on
1246
# It doesn't handle the case when the parent key is missing on a
1247
# page that we *don't* read. So we already have to handle being
1248
# re-entrant for that.
1249
# Since most keys contain a date string, they are more likely to be
1250
# found earlier in the file than later, but we would know that right
1251
# away (key < min_key), and wouldn't keep searching it on every other
1252
# page that we read.
1253
# Mostly, it is an idea, one which should be benchmarked.
1254
parents_not_on_page = set()
1256
for node_index, sub_keys in nodes_and_keys:
1259
# sub_keys is all of the keys we are looking for that should exist
1260
# on this page, if they aren't here, then they won't be found
1261
node = nodes[node_index]
1262
parents_to_check = set()
1263
for next_sub_key in sub_keys:
1264
if next_sub_key not in node:
1265
# This one is just not present in the index at all
1266
missing_keys.add(next_sub_key)
1268
value, refs = node[next_sub_key]
1269
parent_keys = refs[ref_list_num]
1270
parent_map[next_sub_key] = parent_keys
1271
parents_to_check.update(parent_keys)
1272
# Don't look for things we've already found
1273
parents_to_check = parents_to_check.difference(parent_map)
1274
# this can be used to test the benefit of having the check loop
1276
# parents_not_on_page.update(parents_to_check)
1278
while parents_to_check:
1279
next_parents_to_check = set()
1280
for key in parents_to_check:
1282
value, refs = node[key]
1283
parent_keys = refs[ref_list_num]
1284
parent_map[key] = parent_keys
1285
next_parents_to_check.update(parent_keys)
1287
# This parent either is genuinely missing, or should be
1288
# found on another page. Perf test whether it is better
1289
# to check if this node should fit on this page or not.
1290
# in the 'everything-in-one-pack' scenario, this *not*
1291
# doing the check is 237ms vs 243ms.
1292
# So slightly better, but I assume the standard 'lots
1293
# of packs' is going to show a reasonable improvement
1294
# from the check, because it avoids 'going around
1295
# again' for everything that is in another index
1296
# parents_not_on_page.add(key)
1297
# Missing for some reason
1298
if key < node.min_key:
1299
# in the case of bzr.dev, 3.4k/5.3k misses are
1300
# 'earlier' misses (65%)
1301
parents_not_on_page.add(key)
1302
elif key > node.max_key:
1303
# This parent key would be present on a different
1305
parents_not_on_page.add(key)
1307
# assert key != node.min_key and key != node.max_key
1308
# If it was going to be present, it would be on
1309
# *this* page, so mark it missing.
1310
missing_keys.add(key)
1311
parents_to_check = next_parents_to_check.difference(parent_map)
1312
# Might want to do another .difference() from missing_keys
1313
# parents_not_on_page could have been found on a different page, or be
1314
# known to be missing. So cull out everything that has already been
1316
search_keys = parents_not_on_page.difference(
1317
parent_map).difference(missing_keys)
1320
1123
def iter_entries_prefix(self, keys):
1321
1124
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
