1039
1045
output.append(cur_out)
1048
def _walk_through_internal_nodes(self, keys):
1049
"""Take the given set of keys, and find the corresponding LeafNodes.
1051
:param keys: An unsorted iterable of keys to search for
1052
:return: (nodes, index_and_keys)
1053
nodes is a dict mapping {index: LeafNode}
1054
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1056
# 6 seconds spent in miss_torture using the sorted() line.
1057
# Even with out of order disk IO it seems faster not to sort it when
1058
# large queries are being made.
1059
keys_at_index = [(0, sorted(keys))]
1061
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1062
node_indexes = [idx for idx, s_keys in keys_at_index]
1063
nodes = self._get_internal_nodes(node_indexes)
1065
next_nodes_and_keys = []
1066
for node_index, sub_keys in keys_at_index:
1067
node = nodes[node_index]
1068
positions = self._multi_bisect_right(sub_keys, node.keys)
1069
node_offset = next_row_start + node.offset
1070
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1071
for pos, s_keys in positions])
1072
keys_at_index = next_nodes_and_keys
1073
# We should now be at the _LeafNodes
1074
node_indexes = [idx for idx, s_keys in keys_at_index]
1076
# TODO: We may *not* want to always read all the nodes in one
1077
# big go. Consider setting a max size on this.
1078
nodes = self._get_leaf_nodes(node_indexes)
1079
return nodes, keys_at_index
1042
1081
def iter_entries(self, keys):
1043
1082
"""Iterate over keys within the index.
1082
1121
needed_keys = keys
1083
1122
if not 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)
1124
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1111
1125
for node_index, sub_keys in nodes_and_keys:
1112
1126
if not sub_keys:
1121
1135
yield (self, next_sub_key, value)
1137
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1138
"""Find the parent_map information for the set of keys.
1140
This populates the parent_map dict and missing_keys set based on the
1141
queried keys. It also can fill out an arbitrary number of parents that
1142
it finds while searching for the supplied keys.
1144
It is unlikely that you want to call this directly. See
1145
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1147
:param keys: A keys whose ancestry we want to return
1148
Every key will either end up in 'parent_map' or 'missing_keys'.
1149
:param ref_list_num: This index in the ref_lists is the parents we
1151
:param parent_map: {key: parent_keys} for keys that are present in this
1152
index. This may contain more entries than were in 'keys', that are
1153
reachable ancestors of the keys requested.
1154
:param missing_keys: keys which are known to be missing in this index.
1155
This may include parents that were not directly requested, but we
1156
were able to determine that they are not present in this index.
1157
:return: search_keys parents that were found but not queried to know
1158
if they are missing or present. Callers can re-query this index for
1159
those keys, and they will be placed into parent_map or missing_keys
1161
if not self.key_count():
1162
# We use key_count() to trigger reading the root node and
1163
# determining info about this BTreeGraphIndex
1164
# If we don't have any keys, then everything is missing
1165
missing_keys.update(keys)
1167
if ref_list_num >= self.node_ref_lists:
1168
raise ValueError('No ref list %d, index has %d ref lists'
1169
% (ref_list_num, self.node_ref_lists))
1171
# The main trick we are trying to accomplish is that when we find a
1172
# key listing its parents, we expect that the parent key is also likely
1173
# to sit on the same page. Allowing us to expand parents quickly
1174
# without suffering the full stack of bisecting, etc.
1175
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1177
# These are parent keys which could not be immediately resolved on the
1178
# page where the child was present. Note that we may already be
1179
# searching for that key, and it may actually be present [or known
1180
# missing] on one of the other pages we are reading.
1182
# We could try searching for them in the immediate previous or next
1183
# page. If they occur "later" we could put them in a pending lookup
1184
# set, and then for each node we read thereafter we could check to
1185
# see if they are present.
1186
# However, we don't know the impact of keeping this list of things
1187
# that I'm going to search for every node I come across from here on
1189
# It doesn't handle the case when the parent key is missing on a
1190
# page that we *don't* read. So we already have to handle being
1191
# re-entrant for that.
1192
# Since most keys contain a date string, they are more likely to be
1193
# found earlier in the file than later, but we would know that right
1194
# away (key < min_key), and wouldn't keep searching it on every other
1195
# page that we read.
1196
# Mostly, it is an idea, one which should be benchmarked.
1197
parents_not_on_page = set()
1199
for node_index, sub_keys in nodes_and_keys:
1202
# sub_keys is all of the keys we are looking for that should exist
1203
# on this page, if they aren't here, then they won't be found
1204
node = nodes[node_index]
1205
node_keys = node.keys
1206
parents_to_check = set()
1207
for next_sub_key in sub_keys:
1208
if next_sub_key not in node_keys:
1209
# This one is just not present in the index at all
1210
missing_keys.add(next_sub_key)
1212
value, refs = node_keys[next_sub_key]
1213
parent_keys = refs[ref_list_num]
1214
parent_map[next_sub_key] = parent_keys
1215
parents_to_check.update(parent_keys)
1216
# Don't look for things we've already found
1217
parents_to_check = parents_to_check.difference(parent_map)
1218
# this can be used to test the benefit of having the check loop
1220
# parents_not_on_page.update(parents_to_check)
1222
while parents_to_check:
1223
next_parents_to_check = set()
1224
for key in parents_to_check:
1225
if key in node_keys:
1226
value, refs = node_keys[key]
1227
parent_keys = refs[ref_list_num]
1228
parent_map[key] = parent_keys
1229
next_parents_to_check.update(parent_keys)
1231
# This parent either is genuinely missing, or should be
1232
# found on another page. Perf test whether it is better
1233
# to check if this node should fit on this page or not.
1234
# in the 'everything-in-one-pack' scenario, this *not*
1235
# doing the check is 237ms vs 243ms.
1236
# So slightly better, but I assume the standard 'lots
1237
# of packs' is going to show a reasonable improvement
1238
# from the check, because it avoids 'going around
1239
# again' for everything that is in another index
1240
# parents_not_on_page.add(key)
1241
# Missing for some reason
1242
if key < node.min_key:
1243
# in the case of bzr.dev, 3.4k/5.3k misses are
1244
# 'earlier' misses (65%)
1245
parents_not_on_page.add(key)
1246
elif key > node.max_key:
1247
# This parent key would be present on a different
1249
parents_not_on_page.add(key)
1251
# assert key != node.min_key and key != node.max_key
1252
# If it was going to be present, it would be on
1253
# *this* page, so mark it missing.
1254
missing_keys.add(key)
1255
parents_to_check = next_parents_to_check.difference(parent_map)
1256
# Might want to do another .difference() from missing_keys
1257
# parents_not_on_page could have been found on a different page, or be
1258
# known to be missing. So cull out everything that has already been
1260
search_keys = parents_not_on_page.difference(
1261
parent_map).difference(missing_keys)
1123
1264
def iter_entries_prefix(self, keys):
1124
1265
"""Iterate over keys within the index using prefix matching.
added
removed
bzrlib/btree_index.py
