180
192
combine mem with the first and second indexes, creating a new one of
181
193
size 4x. On the fifth create a single new one, etc.
195
if self._combine_backing_indices:
196
(new_backing_file, size,
197
backing_pos) = self._spill_mem_keys_and_combine()
199
new_backing_file, size = self._spill_mem_keys_without_combining()
200
# Note: The transport here isn't strictly needed, because we will use
201
# direct access to the new_backing._file object
202
new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
204
# GC will clean up the file
205
new_backing._file = new_backing_file
206
if self._combine_backing_indices:
207
if len(self._backing_indices) == backing_pos:
208
self._backing_indices.append(None)
209
self._backing_indices[backing_pos] = new_backing
210
for backing_pos in range(backing_pos):
211
self._backing_indices[backing_pos] = None
213
self._backing_indices.append(new_backing)
215
self._nodes_by_key = None
217
def _spill_mem_keys_without_combining(self):
218
return self._write_nodes(self._iter_mem_nodes(), allow_optimize=False)
220
def _spill_mem_keys_and_combine(self):
183
221
iterators_to_combine = [self._iter_mem_nodes()]
185
223
for pos, backing in enumerate(self._backing_indices):
549
609
For InMemoryGraphIndex the estimate is exact.
551
return len(self._keys) + sum(backing.key_count() for backing in
611
return len(self._nodes) + sum(backing.key_count() for backing in
552
612
self._backing_indices if backing is not None)
554
614
def validate(self):
555
615
"""In memory index's have no known corruption at the moment."""
558
class _LeafNode(object):
618
class _LeafNode(dict):
559
619
"""A leaf node for a serialised B+Tree index."""
621
__slots__ = ('min_key', 'max_key', '_keys')
561
623
def __init__(self, bytes, key_length, ref_list_length):
562
624
"""Parse bytes to create a leaf node object."""
563
625
# splitlines mangles the \r delimiters.. don't use it.
564
self.keys = dict(_btree_serializer._parse_leaf_lines(bytes,
565
key_length, ref_list_length))
626
key_list = _btree_serializer._parse_leaf_lines(bytes,
627
key_length, ref_list_length)
629
self.min_key = key_list[0][0]
630
self.max_key = key_list[-1][0]
632
self.min_key = self.max_key = None
633
super(_LeafNode, self).__init__(key_list)
634
self._keys = dict(self)
637
"""Return a sorted list of (key, (value, refs)) items"""
643
"""Return a sorted list of all keys."""
568
649
class _InternalNode(object):
569
650
"""An internal node for a serialised B+Tree index."""
652
__slots__ = ('keys', 'offset')
571
654
def __init__(self, bytes):
572
655
"""Parse bytes to create an internal node object."""
573
656
# splitlines mangles the \r delimiters.. don't use it.
875
1004
"iter_all_entries scales with size of history.")
876
1005
if not self.key_count():
1007
if self._row_offsets[-1] == 1:
1008
# There is only the root node, and we read that via key_count()
1009
if self.node_ref_lists:
1010
for key, (value, refs) in self._root_node.all_items():
1011
yield (self, key, value, refs)
1013
for key, (value, refs) in self._root_node.all_items():
1014
yield (self, key, value)
878
1016
start_of_leaves = self._row_offsets[-2]
879
1017
end_of_leaves = self._row_offsets[-1]
880
needed_nodes = range(start_of_leaves, end_of_leaves)
1018
needed_offsets = range(start_of_leaves, end_of_leaves)
1019
if needed_offsets == [0]:
1020
# Special case when we only have a root node, as we have already
1022
nodes = [(0, self._root_node)]
1024
nodes = self._read_nodes(needed_offsets)
881
1025
# We iterate strictly in-order so that we can use this function
882
1026
# for spilling index builds to disk.
883
1027
if self.node_ref_lists:
884
for _, node in self._read_nodes(needed_nodes):
885
for key, (value, refs) in sorted(node.keys.items()):
1028
for _, node in nodes:
1029
for key, (value, refs) in node.all_items():
886
1030
yield (self, key, value, refs)
888
for _, node in self._read_nodes(needed_nodes):
889
for key, (value, refs) in sorted(node.keys.items()):
1032
for _, node in nodes:
1033
for key, (value, refs) in node.all_items():
890
1034
yield (self, key, value)
971
1115
output.append(cur_out)
1118
def _walk_through_internal_nodes(self, keys):
1119
"""Take the given set of keys, and find the corresponding LeafNodes.
1121
:param keys: An unsorted iterable of keys to search for
1122
:return: (nodes, index_and_keys)
1123
nodes is a dict mapping {index: LeafNode}
1124
keys_at_index is a list of tuples of [(index, [keys for Leaf])]
1126
# 6 seconds spent in miss_torture using the sorted() line.
1127
# Even with out of order disk IO it seems faster not to sort it when
1128
# large queries are being made.
1129
keys_at_index = [(0, sorted(keys))]
1131
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1132
node_indexes = [idx for idx, s_keys in keys_at_index]
1133
nodes = self._get_internal_nodes(node_indexes)
1135
next_nodes_and_keys = []
1136
for node_index, sub_keys in keys_at_index:
1137
node = nodes[node_index]
1138
positions = self._multi_bisect_right(sub_keys, node.keys)
1139
node_offset = next_row_start + node.offset
1140
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1141
for pos, s_keys in positions])
1142
keys_at_index = next_nodes_and_keys
1143
# We should now be at the _LeafNodes
1144
node_indexes = [idx for idx, s_keys in keys_at_index]
1146
# TODO: We may *not* want to always read all the nodes in one
1147
# big go. Consider setting a max size on this.
1148
nodes = self._get_leaf_nodes(node_indexes)
1149
return nodes, keys_at_index
974
1151
def iter_entries(self, keys):
975
1152
"""Iterate over keys within the index.
1014
1191
needed_keys = keys
1015
1192
if not needed_keys:
1017
# 6 seconds spent in miss_torture using the sorted() line.
1018
# Even with out of order disk IO it seems faster not to sort it when
1019
# large queries are being made.
1020
needed_keys = sorted(needed_keys)
1022
nodes_and_keys = [(0, needed_keys)]
1024
for row_pos, next_row_start in enumerate(self._row_offsets[1:-1]):
1025
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1026
nodes = self._get_internal_nodes(node_indexes)
1028
next_nodes_and_keys = []
1029
for node_index, sub_keys in nodes_and_keys:
1030
node = nodes[node_index]
1031
positions = self._multi_bisect_right(sub_keys, node.keys)
1032
node_offset = next_row_start + node.offset
1033
next_nodes_and_keys.extend([(node_offset + pos, s_keys)
1034
for pos, s_keys in positions])
1035
nodes_and_keys = next_nodes_and_keys
1036
# We should now be at the _LeafNodes
1037
node_indexes = [idx for idx, s_keys in nodes_and_keys]
1039
# TODO: We may *not* want to always read all the nodes in one
1040
# big go. Consider setting a max size on this.
1042
nodes = self._get_leaf_nodes(node_indexes)
1194
nodes, nodes_and_keys = self._walk_through_internal_nodes(needed_keys)
1043
1195
for node_index, sub_keys in nodes_and_keys:
1044
1196
if not sub_keys:
1046
1198
node = nodes[node_index]
1047
1199
for next_sub_key in sub_keys:
1048
if next_sub_key in node.keys:
1049
value, refs = node.keys[next_sub_key]
1200
if next_sub_key in node:
1201
value, refs = node[next_sub_key]
1050
1202
if self.node_ref_lists:
1051
1203
yield (self, next_sub_key, value, refs)
1053
1205
yield (self, next_sub_key, value)
1207
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
1208
"""Find the parent_map information for the set of keys.
1210
This populates the parent_map dict and missing_keys set based on the
1211
queried keys. It also can fill out an arbitrary number of parents that
1212
it finds while searching for the supplied keys.
1214
It is unlikely that you want to call this directly. See
1215
"CombinedGraphIndex.find_ancestry()" for a more appropriate API.
1217
:param keys: A keys whose ancestry we want to return
1218
Every key will either end up in 'parent_map' or 'missing_keys'.
1219
:param ref_list_num: This index in the ref_lists is the parents we
1221
:param parent_map: {key: parent_keys} for keys that are present in this
1222
index. This may contain more entries than were in 'keys', that are
1223
reachable ancestors of the keys requested.
1224
:param missing_keys: keys which are known to be missing in this index.
1225
This may include parents that were not directly requested, but we
1226
were able to determine that they are not present in this index.
1227
:return: search_keys parents that were found but not queried to know
1228
if they are missing or present. Callers can re-query this index for
1229
those keys, and they will be placed into parent_map or missing_keys
1231
if not self.key_count():
1232
# We use key_count() to trigger reading the root node and
1233
# determining info about this BTreeGraphIndex
1234
# If we don't have any keys, then everything is missing
1235
missing_keys.update(keys)
1237
if ref_list_num >= self.node_ref_lists:
1238
raise ValueError('No ref list %d, index has %d ref lists'
1239
% (ref_list_num, self.node_ref_lists))
1241
# The main trick we are trying to accomplish is that when we find a
1242
# key listing its parents, we expect that the parent key is also likely
1243
# to sit on the same page. Allowing us to expand parents quickly
1244
# without suffering the full stack of bisecting, etc.
1245
nodes, nodes_and_keys = self._walk_through_internal_nodes(keys)
1247
# These are parent keys which could not be immediately resolved on the
1248
# page where the child was present. Note that we may already be
1249
# searching for that key, and it may actually be present [or known
1250
# missing] on one of the other pages we are reading.
1252
# We could try searching for them in the immediate previous or next
1253
# page. If they occur "later" we could put them in a pending lookup
1254
# set, and then for each node we read thereafter we could check to
1255
# see if they are present.
1256
# However, we don't know the impact of keeping this list of things
1257
# that I'm going to search for every node I come across from here on
1259
# It doesn't handle the case when the parent key is missing on a
1260
# page that we *don't* read. So we already have to handle being
1261
# re-entrant for that.
1262
# Since most keys contain a date string, they are more likely to be
1263
# found earlier in the file than later, but we would know that right
1264
# away (key < min_key), and wouldn't keep searching it on every other
1265
# page that we read.
1266
# Mostly, it is an idea, one which should be benchmarked.
1267
parents_not_on_page = set()
1269
for node_index, sub_keys in nodes_and_keys:
1272
# sub_keys is all of the keys we are looking for that should exist
1273
# on this page, if they aren't here, then they won't be found
1274
node = nodes[node_index]
1275
parents_to_check = set()
1276
for next_sub_key in sub_keys:
1277
if next_sub_key not in node:
1278
# This one is just not present in the index at all
1279
missing_keys.add(next_sub_key)
1281
value, refs = node[next_sub_key]
1282
parent_keys = refs[ref_list_num]
1283
parent_map[next_sub_key] = parent_keys
1284
parents_to_check.update(parent_keys)
1285
# Don't look for things we've already found
1286
parents_to_check = parents_to_check.difference(parent_map)
1287
# this can be used to test the benefit of having the check loop
1289
# parents_not_on_page.update(parents_to_check)
1291
while parents_to_check:
1292
next_parents_to_check = set()
1293
for key in parents_to_check:
1295
value, refs = node[key]
1296
parent_keys = refs[ref_list_num]
1297
parent_map[key] = parent_keys
1298
next_parents_to_check.update(parent_keys)
1300
# This parent either is genuinely missing, or should be
1301
# found on another page. Perf test whether it is better
1302
# to check if this node should fit on this page or not.
1303
# in the 'everything-in-one-pack' scenario, this *not*
1304
# doing the check is 237ms vs 243ms.
1305
# So slightly better, but I assume the standard 'lots
1306
# of packs' is going to show a reasonable improvement
1307
# from the check, because it avoids 'going around
1308
# again' for everything that is in another index
1309
# parents_not_on_page.add(key)
1310
# Missing for some reason
1311
if key < node.min_key:
1312
# in the case of bzr.dev, 3.4k/5.3k misses are
1313
# 'earlier' misses (65%)
1314
parents_not_on_page.add(key)
1315
elif key > node.max_key:
1316
# This parent key would be present on a different
1318
parents_not_on_page.add(key)
1320
# assert key != node.min_key and key != node.max_key
1321
# If it was going to be present, it would be on
1322
# *this* page, so mark it missing.
1323
missing_keys.add(key)
1324
parents_to_check = next_parents_to_check.difference(parent_map)
1325
# Might want to do another .difference() from missing_keys
1326
# parents_not_on_page could have been found on a different page, or be
1327
# known to be missing. So cull out everything that has already been
1329
search_keys = parents_not_on_page.difference(
1330
parent_map).difference(missing_keys)
1055
1333
def iter_entries_prefix(self, keys):
1056
1334
"""Iterate over keys within the index using prefix matching.
1235
1513
"""Read some nodes from disk into the LRU cache.
1237
1515
This performs a readv to get the node data into memory, and parses each
1238
node, the yields it to the caller. The nodes are requested in the
1516
node, then yields it to the caller. The nodes are requested in the
1239
1517
supplied order. If possible doing sort() on the list before requesting
1240
1518
a read may improve performance.
1242
1520
:param nodes: The nodes to read. 0 - first node, 1 - second node etc.
1523
# may be the byte string of the whole file
1525
# list of (offset, length) regions of the file that should, evenually
1526
# be read in to data_ranges, either from 'bytes' or from the transport
1528
base_offset = self._base_offset
1246
1529
for index in nodes:
1247
offset = index * _PAGE_SIZE
1530
offset = (index * _PAGE_SIZE)
1248
1531
size = _PAGE_SIZE
1250
1533
# Root node - special case
1252
1535
size = min(_PAGE_SIZE, self._size)
1254
stream = self._transport.get(self._name)
1255
start = stream.read(_PAGE_SIZE)
1256
# Avoid doing this again
1257
self._size = len(start)
1258
size = min(_PAGE_SIZE, self._size)
1537
# The only case where we don't know the size, is for very
1538
# small indexes. So we read the whole thing
1539
bytes = self._transport.get_bytes(self._name)
1540
num_bytes = len(bytes)
1541
self._size = num_bytes - base_offset
1542
# the whole thing should be parsed out of 'bytes'
1543
ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1544
for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1260
1547
if offset > self._size:
1261
1548
raise AssertionError('tried to read past the end'
1262
1549
' of the file %s > %s'
1263
1550
% (offset, self._size))
1264
1551
size = min(size, self._size - offset)
1265
ranges.append((offset, size))
1552
ranges.append((base_offset + offset, size))
1268
if self._file is None:
1555
elif bytes is not None:
1556
# already have the whole file
1557
data_ranges = [(start, bytes[start:start+size])
1558
for start, size in ranges]
1559
elif self._file is None:
1269
1560
data_ranges = self._transport.readv(self._name, ranges)
1271
1562
data_ranges = []
added
removed
bzrlib/btree_index.py
