1083
1043
output.append(cur_out)
1086
def _walk_through_internal_nodes(self, keys):
1087
"""Take the given set of keys, and find the corresponding LeafNodes.
1089
:param keys: An unsorted iterable of keys to search for
1090
:return: (nodes, index_and_keys)
1091
nodes is a dict mapping {index: LeafNode}
1092
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1094
# 6 seconds spent in miss_torture using the sorted() line.
1095
# Even with out of order disk IO it seems faster not to sort it when
1096
# large queries are being made.
1097
keys_at_index = [(0, sorted(keys))]
1099
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1100
node_indexes = [idx for idx, s_keys in keys_at_index]
1101
nodes = self._get_internal_nodes(node_indexes)
1103
next_nodes_and_keys = []
1104
for node_index, sub_keys in keys_at_index:
1105
node = nodes[node_index]
1106
positions = self._multi_bisect_right(sub_keys, node.keys)
1107
node_offset = next_row_start + node.offset
1108
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1109
for pos, s_keys in positions])
1110
keys_at_index = next_nodes_and_keys
1111
# We should now be at the _LeafNodes
1112
node_indexes = [idx for idx, s_keys in keys_at_index]
1114
# TODO: We may *not* want to always read all the nodes in one
1115
# big go. Consider setting a max size on this.
1116
nodes = self._get_leaf_nodes(node_indexes)
1117
return nodes, keys_at_index
1119
1046
def iter_entries(self, keys):
1120
1047
"""Iterate over keys within the index.
1159
1086
needed_keys = keys
1160
1087
if not needed_keys:
1162
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1089
# 6 seconds spent in miss_torture using the sorted() line.
1090
# Even with out of order disk IO it seems faster not to sort it when
1091
# large queries are being made.
1092
needed_keys = sorted(needed_keys)
1094
nodes_and_keys = [(0, needed_keys)]
1096
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1097
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1098
nodes = self._get_internal_nodes(node_indexes)
1100
next_nodes_and_keys = []
1101
for node_index, sub_keys in nodes_and_keys:
1102
node = nodes[node_index]
1103
positions = self._multi_bisect_right(sub_keys, node.keys)
1104
node_offset = next_row_start + node.offset
1105
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1106
for pos, s_keys in positions])
1107
nodes_and_keys = next_nodes_and_keys
1108
# We should now be at the _LeafNodes
1109
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1111
# TODO: We may *not* want to always read all the nodes in one
1112
# big go. Consider setting a max size on this.
1114
nodes = self._get_leaf_nodes(node_indexes)
1163
1115
for node_index, sub_keys in nodes_and_keys:
1164
1116
if not sub_keys:
1173
1125
yield (self, next_sub_key, value)
1175
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1176
"""Find the parent_map information for the set of keys.
1178
This populates the parent_map dict and missing_keys set based on the
1179
queried keys. It also can fill out an arbitrary number of parents that
1180
it finds while searching for the supplied keys.
1182
It is unlikely that you want to call this directly. See
1183
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1185
:param keys: A keys whose ancestry we want to return
1186
Every key will either end up in 'parent_map' or 'missing_keys'.
1187
:param ref_list_num: This index in the ref_lists is the parents we
1189
:param parent_map: {key: parent_keys} for keys that are present in this
1190
index. This may contain more entries than were in 'keys', that are
1191
reachable ancestors of the keys requested.
1192
:param missing_keys: keys which are known to be missing in this index.
1193
This may include parents that were not directly requested, but we
1194
were able to determine that they are not present in this index.
1195
:return: search_keys parents that were found but not queried to know
1196
if they are missing or present. Callers can re-query this index for
1197
those keys, and they will be placed into parent_map or missing_keys
1199
if not self.key_count():
1200
# We use key_count() to trigger reading the root node and
1201
# determining info about this BTreeGraphIndex
1202
# If we don't have any keys, then everything is missing
1203
missing_keys.update(keys)
1205
if ref_list_num >= self.node_ref_lists:
1206
raise ValueError('No ref list %d, index has %d ref lists'
1207
% (ref_list_num, self.node_ref_lists))
1209
# The main trick we are trying to accomplish is that when we find a
1210
# key listing its parents, we expect that the parent key is also likely
1211
# to sit on the same page. Allowing us to expand parents quickly
1212
# without suffering the full stack of bisecting, etc.
1213
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1215
# These are parent keys which could not be immediately resolved on the
1216
# page where the child was present. Note that we may already be
1217
# searching for that key, and it may actually be present [or known
1218
# missing] on one of the other pages we are reading.
1220
# We could try searching for them in the immediate previous or next
1221
# page. If they occur "later" we could put them in a pending lookup
1222
# set, and then for each node we read thereafter we could check to
1223
# see if they are present.
1224
# However, we don't know the impact of keeping this list of things
1225
# that I'm going to search for every node I come across from here on
1227
# It doesn't handle the case when the parent key is missing on a
1228
# page that we *don't* read. So we already have to handle being
1229
# re-entrant for that.
1230
# Since most keys contain a date string, they are more likely to be
1231
# found earlier in the file than later, but we would know that right
1232
# away (key < min_key), and wouldn't keep searching it on every other
1233
# page that we read.
1234
# Mostly, it is an idea, one which should be benchmarked.
1235
parents_not_on_page = set()
1237
for node_index, sub_keys in nodes_and_keys:
1240
# sub_keys is all of the keys we are looking for that should exist
1241
# on this page, if they aren't here, then they won't be found
1242
node = nodes[node_index]
1243
node_keys = node.keys
1244
parents_to_check = set()
1245
for next_sub_key in sub_keys:
1246
if next_sub_key not in node_keys:
1247
# This one is just not present in the index at all
1248
missing_keys.add(next_sub_key)
1250
value, refs = node_keys[next_sub_key]
1251
parent_keys = refs[ref_list_num]
1252
parent_map[next_sub_key] = parent_keys
1253
parents_to_check.update(parent_keys)
1254
# Don't look for things we've already found
1255
parents_to_check = parents_to_check.difference(parent_map)
1256
# this can be used to test the benefit of having the check loop
1258
# parents_not_on_page.update(parents_to_check)
1260
while parents_to_check:
1261
next_parents_to_check = set()
1262
for key in parents_to_check:
1263
if key in node_keys:
1264
value, refs = node_keys[key]
1265
parent_keys = refs[ref_list_num]
1266
parent_map[key] = parent_keys
1267
next_parents_to_check.update(parent_keys)
1269
# This parent either is genuinely missing, or should be
1270
# found on another page. Perf test whether it is better
1271
# to check if this node should fit on this page or not.
1272
# in the 'everything-in-one-pack' scenario, this *not*
1273
# doing the check is 237ms vs 243ms.
1274
# So slightly better, but I assume the standard 'lots
1275
# of packs' is going to show a reasonable improvement
1276
# from the check, because it avoids 'going around
1277
# again' for everything that is in another index
1278
# parents_not_on_page.add(key)
1279
# Missing for some reason
1280
if key < node.min_key:
1281
# in the case of bzr.dev, 3.4k/5.3k misses are
1282
# 'earlier' misses (65%)
1283
parents_not_on_page.add(key)
1284
elif key > node.max_key:
1285
# This parent key would be present on a different
1287
parents_not_on_page.add(key)
1289
# assert key != node.min_key and key != node.max_key
1290
# If it was going to be present, it would be on
1291
# *this* page, so mark it missing.
1292
missing_keys.add(key)
1293
parents_to_check = next_parents_to_check.difference(parent_map)
1294
# Might want to do another .difference() from missing_keys
1295
# parents_not_on_page could have been found on a different page, or be
1296
# known to be missing. So cull out everything that has already been
1298
search_keys = parents_not_on_page.difference(
1299
parent_map).difference(missing_keys)
1302
1127
def iter_entries_prefix(self, keys):
1303
1128
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
