Merge lp:~jameinel/bzr/1.17-chk-multilevel into lp:~bzr/bzr/trunk-old

[John A Meinel]

[John A Meinel (jameinel)]

This is a slightly better fix for bug #390563. The main changes are:

1) Rewrite iter_interesting_nodes using a class, rather than maintaining state between functions
2) Split up the processing of root nodes into:
  a) Read all uninteresting roots, and find uninteresting chks and items
  b) Filter out any interesting root keys that were found in (a)
  c) Read all remaining root pages and yield them
  d) Find interesting references that are not in (a) (and interesting items)
     Note the search key prefixes for these references and items, and queue
     them up to be returned later.
  e) Filter out uninteresting chk pages based on the search key prefixes in (d)

(d) and (e) are the main differences.
For (d) Robert found an edge case where we could return a non-interesting item (which would, in turn, be a text key, which would then be a failure for fetch) when one side had an immediate leaf node, and the other side had a deep tree. The only real change is to just defer returning interesting *items* until all uninteresting pages have been read.

(e) Before we used the 'intersection of interesting references', whereas now we filter simply based on prefix. Likely to be a small win if there are lots of uninteresting pages (lots of merge parents that are not being transmitted).

3) After processing root nodes
  a) Process the uninteresing queue until completion
  b) Process the interesting queue, filtering out all uninteresting items.
     (some minor things here, like doing batch '.difference()' checks rather than .difference on every record processed)

I looked at trying to use a heapq to unify things more with 'iter_changes' but the constraints are *very* different.

1) CHKMap.iter_changes() is symmetric. In that we need to return a record for (source, target, extra), for iter_interesting_nodes, we *only* need to return information for the 'target' side.
2) CHKMap.iter_changes() only ever effects 2 records, a single source and a single target. iter_interesting_nodes is looking at a many-to-many comparison.
3) CHKMap.iter_changes() only cares about the actual keys, and not about sending the raw byte records to be transmitted for fetch.
4) iter_interesting_nodes is much more concerned about batching because of its many-to-many nature, and the fact it is used for fetch. We really don't want to be doing a round trip per page.
5) The only gain for doing heapq is if we could figure out the algorithm for filtering out nodes that we thought we would want to read, but really don't. However,
  a) I do this at the root level, because it is fairly straightforward. So any further improvements only effect trees that are deeper than 2 (1 root, 1+ internal, 1 leaf), however this only happens for trees > 50k items.
  b) Reading extra chk pages isn't "incorrect", just "inefficient" (the stacking code ensures all referenced chk pages are present in the stacked-on branch, just like we ensure compression texts.)
  c) The best I could come up with would be to split the reads up by prefix. So you would page in the 'a' references, then the 'b' references, etc. However, that forces us to split the requests up even further, rather than larger batches of requests. (more...

[Robert Collins (lifeless)]

Shallow immediate review:

The docstring for the class, and perhaps the class name could be better.

In terms of sets its:
interesting - uninteresting

So perhaps
CHKMapDifference

as a class name. And for the docstring, something like

"""Iterate the stored pages and key,value pairs for (new - old).

This class provides a generator over the stored CHK pages and the
key,value pairs that are in any of the new maps and not in any of the
old maps.
"""

-Rob

=== modified file 'bzrlib/chk_map.py'
--- bzrlib/chk_map.py	2009-06-26 09:24:34 +0000
+++ bzrlib/chk_map.py	2009-07-01 22:35:14 +0000
@@ -1398,106 +1398,202 @@
     return node
 
 
-def _find_children_info(store, interesting_keys, uninteresting_keys, pb):
-    """Read the associated records, and determine what is interesting."""
-    uninteresting_keys = set(uninteresting_keys)
-    chks_to_read = uninteresting_keys.union(interesting_keys)
-    next_uninteresting = set()
-    next_interesting = set()
-    next_interesting_intersection = None
-    uninteresting_items = set()
-    interesting_items = set()
-    interesting_to_yield = []
-    for record in store.get_record_stream(chks_to_read, 'unordered', True):
-        # records_read.add(record.key())
-        if pb is not None:
-            pb.tick()
-        bytes = record.get_bytes_as('fulltext')
-        # We don't care about search_key_func for this code, because we only
-        # care about external references.
-        node = _deserialise(bytes, record.key, search_key_func=None)
-        if record.key in uninteresting_keys:
-            if type(node) is InternalNode:
-                next_uninteresting.update(node.refs())
-            else:
-                # We know we are at a LeafNode, so we can pass None for the
-                # store
-                uninteresting_items.update(node.iteritems(None))
-        else:
-            interesting_to_yield.append(record.key)
-            if type(node) is InternalNode:
-                if next_interesting_intersection is None:
-                    next_interesting_intersection = set(node.refs())
-                else:
-                    next_interesting_intersection = \
-                        next_interesting_intersection.intersection(node.refs())
-                next_interesting.update(node.refs())
-            else:
-                interesting_items.update(node.iteritems(None))
-    return (next_uninteresting, uninteresting_items,
-            next_interesting, interesting_to_yield, interesting_items,
-            next_interesting_intersection)
-
-
-def _find_all_uninteresting(store, interesting_root_keys,
-                            uninteresting_root_keys, pb):
-    """Determine the full set of uninteresting keys."""
-    # What about duplicates between interesting_root_keys and
-    # uninteresting_root_keys?
-    if not uninteresting_root_keys:
-        # Shortcut case. We know there is nothing uninteresting to filter out
-        # So we just let the rest of the algorithm do the work
-        # We know there is nothing uninteresting, and we didn't have to read
-        # any interesting records yet.
-        return (set(), set(), set(interesting_root_keys), [], set())
-    all_uninteresting_chks = set(uninteresting_root_keys)
-    all_uninteresting_items = set()
-
-    # First step, find the direct children of both the interesting and
-    # uninteresting set
-    (uninteresting_keys, uninteresting_items,
-     interesting_keys, interesting_to_yield,
-     interesting_items, interesting_intersection,
-     ) = _find_children_info(store, interesting_root_keys,
-                                              uninteresting_root_keys,
-                                              pb=pb)
-    all_uninteresting_chks.update(uninteresting_keys)
-    all_uninteresting_items.update(uninteresting_items)
-    del uninteresting_items
-    # Do not examine in detail pages common to all interesting trees.
-    # Pages that are common to all interesting trees will have their
-    # older versions found via the uninteresting tree traversal. Some pages
-    # found via the interesting trees traversal will be uninteresting for
-    # other of the interesting trees, which is why we require the pages to be
-    # common for us to trim them.
-    if interesting_intersection is not None:
-        uninteresting_keys.difference_update(interesting_intersection)
-
-    # Second, find the full set of uninteresting bits reachable by the
-    # uninteresting roots
-    chks_to_read = uninteresting_keys
-    while chks_to_read:
-        next_chks = set()
-        for record in store.get_record_stream(chks_to_read, 'unordered', False):
-            # TODO: Handle 'absent'
-            if pb is not None:
-                pb.tick()
+class InterestingNodeIterator(object):
+    """Determine the nodes and items that are 'interesting'
+
+    This is defined as being present in the interesting set, but not being
+    present in the uninteresting set.
+    """
+
+    def __init__(self, store, interesting_root_keys, uninteresting_root_keys,
+                 search_key_func, pb=None):
+        self._store = store
+        self._interesting_root_keys = interesting_root_keys
+        self._uninteresting_root_keys = uninteresting_root_keys
+        self._pb = pb
+        # All uninteresting chks that we have seen. By the time they are added
+        # here, they should be either fully ignored, or queued up for
+        # processing
+        self._all_uninteresting_chks = set(self._uninteresting_root_keys)
+        # All items that we have seen from the uninteresting_root_keys
+        self._all_uninteresting_items = set()
+        # These are interesting items which were either read, or already in the
+        # interesting queue (so we don't need to walk them again)
+        self._processed_interesting_refs = set()
+        self._search_key_func = search_key_func
+
+        # The uninteresting and interesting nodes to be searched
+        self._uninteresting_queue = []
+        self._interesting_queue = []
+        # Holds the (key, value) items found when processing the root nodes,
+        # waiting for the uninteresting nodes to be walked
+        self._interesting_item_queue = []
+        self._state = None
+
+    def _read_nodes_from_store(self, keys):
+        # We chose not to use _page_cache, because we think in terms of records
+        # to be yielded. Also, we expect to touch each page only 1 time during
+        # this code. (We may want to evaluate saving the raw bytes into the
+        # page cache, which would allow a working tree update after the fetch
+        # to not have to read the bytes again.)
+        stream = self._store.get_record_stream(keys, 'unordered', True)
+        for record in stream:
+            if self._pb is not None:
+                self._pb.tick()
+            if record.storage_kind == 'absent':
+                raise errors.NoSuchRevision(self._store, record.key)
             bytes = record.get_bytes_as('fulltext')
-            # We don't care about search_key_func for this code, because we
-            # only care about external references.
-            node = _deserialise(bytes, record.key, search_key_func=None)
+            node = _deserialise(bytes, record.key,
+                                search_key_func=self._search_key_func)
             if type(node) is InternalNode:
-                # uninteresting_prefix_chks.update(node._items.iteritems())
-                chks = node._items.values()
-                # TODO: We remove the entries that are already in
-                #       uninteresting_chks ?
-                next_chks.update(chks)
-                all_uninteresting_chks.update(chks)
+                # Note we don't have to do node.refs() because we know that
+                # there are no children that have been pushed into this node
+                prefix_refs = node._items.items()
+                items = []
             else:
-                all_uninteresting_items.update(node._items.iteritems())
-        chks_to_read = next_chks
-    return (all_uninteresting_chks, all_uninteresting_items,
-            interesting_keys, interesting_to_yield, interesting_items)
+                prefix_refs = []
+                items = node._items.items()
+            yield record, node, prefix_refs, items
+
+    def _read_uninteresting_roots(self):
+        uninteresting_chks_to_enqueue = []
+        all_uninteresting_chks = self._all_uninteresting_chks
+        for record, node, prefix_refs, items in \
+                self._read_nodes_from_store(self._uninteresting_root_keys):
+            # Uninteresting node
+            prefix_refs = [p_r for p_r in prefix_refs
+                                if p_r[1] not in all_uninteresting_chks]
+            new_refs = [p_r[1] for p_r in prefix_refs]
+            all_uninteresting_chks.update(new_refs)
+            self._all_uninteresting_items.update(items)
+            # Queue up the uninteresting references
+            # Don't actually put them in the 'to-read' queue until we have
+            # finished checking the interesting references
+            uninteresting_chks_to_enqueue.extend(prefix_refs)
+        return uninteresting_chks_to_enqueue
+
+    def _enqueue_uninteresting(self, interesting_prefixes,
+                               uninteresting_chks_to_enqueue):
+        # At this point, we have read all the uninteresting and interesting
+        # items, so we can queue up the uninteresting stuff, knowing that we've
+        # handled the interesting ones
+        for prefix, ref in uninteresting_chks_to_enqueue:
+            not_interesting = True
+            for i in xrange(len(prefix), 0, -1):
+                if prefix[:i] in interesting_prefixes:
+                    not_interesting = False
+                    break
+            if not_interesting:
+                # This prefix is not part of the remaining 'interesting set'
+                continue
+            self._uninteresting_queue.append(ref)
+
+    def _read_all_roots(self):
+        """Read the root pages.
+
+        This is structured as a generator, so that the root records can be
+        yielded up to whoever needs them without any buffering.
+        """
+        # This is the bootstrap phase
+        if not self._uninteresting_root_keys:
+            # With no uninteresting_root_keys we can just shortcut and be ready
+            # for _flush_interesting_queue
+            self._interesting_queue = list(self._interesting_root_keys)
+            return
+        uninteresting_chks_to_enqueue = self._read_uninteresting_roots()
+        # filter out any root keys that are already known to be uninteresting
+        interesting_keys = set(self._interesting_root_keys).difference(
+                                self._all_uninteresting_chks)
+        # These are prefixes that are present in interesting_keys that we are
+        # thinking to yield
+        interesting_prefixes = set()
+        # We are about to yield all of these, so we don't want them getting
+        # added a second time
+        processed_interesting_refs = self._processed_interesting_refs
+        processed_interesting_refs.update(interesting_keys)
+        for record, node, prefix_refs, items in \
+                self._read_nodes_from_store(interesting_keys):
+            # At this level, we now know all the uninteresting references
+            # So we filter and queue up whatever is remaining
+            prefix_refs = [p_r for p_r in prefix_refs
+                           if p_r[1] not in self._all_uninteresting_chks
+                              and p_r[1] not in processed_interesting_refs]
+            refs = [p_r[1] for p_r in prefix_refs]
+            interesting_prefixes.update([p_r[0] for p_r in prefix_refs])
+            self._interesting_queue.extend(refs)
+            # TODO: We can potentially get multiple items here, however the
+            #       current design allows for this, as callers will do the work
+            #       to make the results unique. We might profile whether we
+            #       gain anything by ensuring unique return values for items
+            interesting_items = [item for item in items
+                                 if item not in self._all_uninteresting_items]
+            self._interesting_item_queue.extend(interesting_items)
+            interesting_prefixes.update([self._search_key_func(item[0])
+                                         for item in interesting_items])
+            processed_interesting_refs.update(refs)
+            yield record
+        # For interesting_prefixes we have the full length prefixes queued up.
+        # However, we also need possible prefixes. (If we have a known ref to
+        # 'ab', then we also need to include 'a'.) So expand the
+        # interesting_prefixes to include all shorter prefixes
+        for prefix in list(interesting_prefixes):
+            interesting_prefixes.update([prefix[:i]
+                                         for i in xrange(1, len(prefix))])
+        self._enqueue_uninteresting(interesting_prefixes,
+                                    uninteresting_chks_to_enqueue)
+
+    def _flush_interesting_queue(self):
+        # No need to maintain the heap invariant anymore, just pull things out
+        # and process them
+        refs = set(self._interesting_queue)
+        self._interesting_queue = []
+        # First pass, flush all interesting items and convert to using direct refs
+        all_uninteresting_chks = self._all_uninteresting_chks
+        processed_interesting_refs = self._processed_interesting_refs
+        all_uninteresting_items = self._all_uninteresting_items
+        interesting_items = [item for item in self._interesting_item_queue
+                                   if item not in all_uninteresting_items]
+        self._interesting_item_queue = []
+        if interesting_items:
+            yield None, interesting_items
+        refs = refs.difference(all_uninteresting_chks)
+        while refs:
+            next_refs = set()
+            next_refs_update = next_refs.update
+            # Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
+            # from 1m54s to 1m51s. Consider it.
+            for record, _, p_refs, items in self._read_nodes_from_store(refs):
+                items = [item for item in items
+                         if item not in all_uninteresting_items]
+                yield record, items
+                next_refs_update([p_r[1] for p_r in p_refs])
+            next_refs = next_refs.difference(all_uninteresting_chks)
+            next_refs = next_refs.difference(processed_interesting_refs)
+            processed_interesting_refs.update(next_refs)
+            refs = next_refs
+
+    def _process_next_uninteresting(self):
+        # Since we don't filter uninteresting any further than during
+        # _read_all_roots, process the whole queue in a single pass.
+        refs = self._uninteresting_queue
+        self._uninteresting_queue = []
+        all_uninteresting_chks = self._all_uninteresting_chks
+        for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
+            self._all_uninteresting_items.update(items)
+            refs = [r for _,r in prefix_refs if r not in all_uninteresting_chks]
+            self._uninteresting_queue.extend(refs)
+            all_uninteresting_chks.update(refs)
+
+    def _process_queues(self):
+        while self._uninteresting_queue:
+            self._process_next_uninteresting()
+        return self._flush_interesting_queue()
+
+    def process(self):
+        for record in self._read_all_roots():
+            yield record, []
+        for record, items in self._process_queues():
+            yield record, items
 
 
 def iter_interesting_nodes(store, interesting_root_keys,
@@ -1514,72 +1610,11 @@
     :return: Yield
         (interesting record, {interesting key:values})
     """
-    # TODO: consider that it may be more memory efficient to use the 20-byte
-    #       sha1 string, rather than tuples of hexidecimal sha1 strings.
-    # TODO: Try to factor out a lot of the get_record_stream() calls into a
-    #       helper function similar to _read_bytes. This function should be
-    #       able to use nodes from the _page_cache as well as actually
-    #       requesting bytes from the store.
-
-    (all_uninteresting_chks, all_uninteresting_items, interesting_keys,
-     interesting_to_yield, interesting_items) = _find_all_uninteresting(store,
-        interesting_root_keys, uninteresting_root_keys, pb)
-
-    # Now that we know everything uninteresting, we can yield information from
-    # our first request
-    interesting_items.difference_update(all_uninteresting_items)
-    interesting_to_yield = set(interesting_to_yield) - all_uninteresting_chks
-    if interesting_items:
-        yield None, interesting_items
-    if interesting_to_yield:
-        # We request these records again, rather than buffering the root
-        # records, most likely they are still in the _group_cache anyway.
-        for record in store.get_record_stream(interesting_to_yield,
-                                              'unordered', False):
-            yield record, []
-    all_uninteresting_chks.update(interesting_to_yield)
-    interesting_keys.difference_update(all_uninteresting_chks)
-
-    chks_to_read = interesting_keys
-    counter = 0
-    while chks_to_read:
-        next_chks = set()
-        for record in store.get_record_stream(chks_to_read, 'unordered', False):
-            counter += 1
-            if pb is not None:
-                pb.update('find chk pages', counter)
-            # TODO: Handle 'absent'?
-            bytes = record.get_bytes_as('fulltext')
-            # We don't care about search_key_func for this code, because we
-            # only care about external references.
-            node = _deserialise(bytes, record.key, search_key_func=None)
-            if type(node) is InternalNode:
-                # all_uninteresting_chks grows large, as it lists all nodes we
-                # don't want to process (including already seen interesting
-                # nodes).
-                # small.difference_update(large) scales O(large), but
-                # small.difference(large) scales O(small).
-                # Also, we know we just _deserialised this node, so we can
-                # access the dict directly.
-                chks = set(node._items.itervalues()).difference(
-                            all_uninteresting_chks)
-                # Is set() and .difference_update better than:
-                # chks = [chk for chk in node.refs()
-                #              if chk not in all_uninteresting_chks]
-                next_chks.update(chks)
-                # These are now uninteresting everywhere else
-                all_uninteresting_chks.update(chks)
-                interesting_items = []
-            else:
-                interesting_items = [item for item in node._items.iteritems()
-                                     if item not in all_uninteresting_items]
-                # TODO: Do we need to filter out items that we have already
-                #       seen on other pages? We don't really want to buffer the
-                #       whole thing, but it does mean that callers need to
-                #       understand they may get duplicate values.
-                # all_uninteresting_items.update(interesting_items)
-            yield record, interesting_items
-        chks_to_read = next_chks
+    iterator = InterestingNodeIterator(store, interesting_root_keys,
+                                       uninteresting_root_keys,
+                                       search_key_func=store._search_key_func,
+                                       pb=pb)
+    return iterator.process()
 
 
 try:
 
=== modified file 'bzrlib/repofmt/groupcompress_repo.py'
--- bzrlib/repofmt/groupcompress_repo.py	2009-06-29 14:51:13 +0000
+++ bzrlib/repofmt/groupcompress_repo.py	2009-07-01 22:35:14 +0000
@@ -652,6 +652,9 @@
                 parents=False, is_locked=self.is_locked,
                 inconsistency_fatal=False),
             access=self._pack_collection.chk_index.data_access)
+        search_key_name = self._format._serializer.search_key_name
+        search_key_func = chk_map.search_key_registry.get(search_key_name)
+        self.chk_bytes._search_key_func = search_key_func
         # True when the repository object is 'write locked' (as opposed to the
         # physical lock only taken out around changes to the pack-names list.)
         # Another way to represent this would be a decorator around the control
 
=== modified file 'bzrlib/tests/test_chk_map.py'
--- bzrlib/tests/test_chk_map.py	2009-06-26 09:24:34 +0000
+++ bzrlib/tests/test_chk_map.py	2009-07-01 22:35:14 +0000
@@ -20,6 +20,7 @@
 
 from bzrlib import (
     chk_map,
+    groupcompress,
     osutils,
     tests,
     )
@@ -59,17 +60,14 @@
         self.assertCommonPrefix('', '', '')
 
 
-class TestCaseWithStore(tests.TestCaseWithTransport):
+class TestCaseWithStore(tests.TestCaseWithMemoryTransport):
 
     def get_chk_bytes(self):
         # The easiest way to get a CHK store is a development6 repository and
         # then work with the chk_bytes attribute directly.
-        repo = self.make_repository(".", format="development6-rich-root")
-        repo.lock_write()
-        self.addCleanup(repo.unlock)
-        repo.start_write_group()
-        self.addCleanup(repo.abort_write_group)
-        return repo.chk_bytes
+        factory = groupcompress.make_pack_factory(False, False, 1)
+        self.chk_bytes = factory(self.get_transport())
+        return self.chk_bytes
 
     def _get_map(self, a_dict, maximum_size=0, chk_bytes=None, key_width=1,
                  search_key_func=None):
@@ -97,6 +95,246 @@
         return dict(node.iteritems(*args))
 
 
+class TestCaseWithExampleMaps(TestCaseWithStore):
+
+    def get_chk_bytes(self):
+        if getattr(self, '_chk_bytes', None) is None:
+            self._chk_bytes = super(TestCaseWithExampleMaps,
+                                    self).get_chk_bytes()
+        return self._chk_bytes
+
+    def get_map(self, a_dict, maximum_size=100, search_key_func=None):
+        c_map = self._get_map(a_dict, maximum_size=maximum_size,
+                              chk_bytes=self.get_chk_bytes(),
+                              search_key_func=search_key_func)
+        return c_map
+
+    def make_root_only_map(self, search_key_func=None):
+        return self.get_map({
+            ('aaa',): 'initial aaa content',
+            ('abb',): 'initial abb content',
+        }, search_key_func=search_key_func)
+
+    def make_root_only_aaa_ddd_map(self, search_key_func=None):
+        return self.get_map({
+            ('aaa',): 'initial aaa content',
+            ('ddd',): 'initial ddd content',
+        }, search_key_func=search_key_func)
+
+    def make_one_deep_map(self, search_key_func=None):
+        # Same as root_only_map, except it forces an InternalNode at the root
+        return self.get_map({
+            ('aaa',): 'initial aaa content',
+            ('abb',): 'initial abb content',
+            ('ccc',): 'initial ccc content',
+            ('ddd',): 'initial ddd content',
+        }, search_key_func=search_key_func)
+
+    def make_two_deep_map(self, search_key_func=None):
+        # Carefully chosen so that it creates a 2-deep map for both
+        # _search_key_plain and for _search_key_16
+        # Also so that things line up with make_one_deep_two_prefix_map
+        return self.get_map({
+            ('aaa',): 'initial aaa content',
+            ('abb',): 'initial abb content',
+            ('acc',): 'initial acc content',
+            ('ace',): 'initial ace content',
+            ('add',): 'initial add content',
+            ('adh',): 'initial adh content',
+            ('adl',): 'initial adl content',
+            ('ccc',): 'initial ccc content',
+            ('ddd',): 'initial ddd content',
+        }, search_key_func=search_key_func)
+
+    def make_one_deep_two_prefix_map(self, search_key_func=None):
+        """Create a map with one internal node, but references are extra long.
+
+        Otherwise has similar content to make_two_deep_map.
+        """
+        return self.get_map({
+            ('aaa',): 'initial aaa content',
+            ('add',): 'initial add content',
+            ('adh',): 'initial adh content',
+            ('adl',): 'initial adl content',
+        }, search_key_func=search_key_func)
+
+    def make_one_deep_one_prefix_map(self, search_key_func=None):
+        """Create a map with one internal node, but references are extra long.
+
+        Similar to make_one_deep_two_prefix_map, except the split is at the
+        first char, rather than the second.
+        """
+        return self.get_map({
+            ('add',): 'initial add content',
+            ('adh',): 'initial adh content',
+            ('adl',): 'initial adl content',
+            ('bbb',): 'initial bbb content',
+        }, search_key_func=search_key_func)
+
+
+class TestTestCaseWithExampleMaps(TestCaseWithExampleMaps):
+    """Actual tests for the provided examples."""
+
+    def test_root_only_map_plain(self):
+        c_map = self.make_root_only_map()
+        self.assertEqualDiff(
+            "'' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('abb',) 'initial abb content'\n",
+            c_map._dump_tree())
+
+    def test_root_only_map_16(self):
+        c_map = self.make_root_only_map(search_key_func=chk_map._search_key_16)
+        self.assertEqualDiff(
+            "'' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('abb',) 'initial abb content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_map_plain(self):
+        c_map = self.make_one_deep_map()
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  'a' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('abb',) 'initial abb content'\n"
+            "  'c' LeafNode\n"
+            "      ('ccc',) 'initial ccc content'\n"
+            "  'd' LeafNode\n"
+            "      ('ddd',) 'initial ddd content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_map_16(self):
+        c_map = self.make_one_deep_map(search_key_func=chk_map._search_key_16)
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  '2' LeafNode\n"
+            "      ('ccc',) 'initial ccc content'\n"
+            "  '4' LeafNode\n"
+            "      ('abb',) 'initial abb content'\n"
+            "  'F' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('ddd',) 'initial ddd content'\n",
+            c_map._dump_tree())
+
+    def test_root_only_aaa_ddd_plain(self):
+        c_map = self.make_root_only_aaa_ddd_map()
+        self.assertEqualDiff(
+            "'' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('ddd',) 'initial ddd content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_map_16(self):
+        c_map = self.make_root_only_aaa_ddd_map(
+                search_key_func=chk_map._search_key_16)
+        # We use 'aaa' and 'ddd' because they happen to map to 'F' when using
+        # _search_key_16
+        self.assertEqualDiff(
+            "'' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "      ('ddd',) 'initial ddd content'\n",
+            c_map._dump_tree())
+
+    def test_two_deep_map_plain(self):
+        c_map = self.make_two_deep_map()
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  'a' InternalNode\n"
+            "    'aa' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "    'ab' LeafNode\n"
+            "      ('abb',) 'initial abb content'\n"
+            "    'ac' LeafNode\n"
+            "      ('acc',) 'initial acc content'\n"
+            "      ('ace',) 'initial ace content'\n"
+            "    'ad' LeafNode\n"
+            "      ('add',) 'initial add content'\n"
+            "      ('adh',) 'initial adh content'\n"
+            "      ('adl',) 'initial adl content'\n"
+            "  'c' LeafNode\n"
+            "      ('ccc',) 'initial ccc content'\n"
+            "  'd' LeafNode\n"
+            "      ('ddd',) 'initial ddd content'\n",
+            c_map._dump_tree())
+
+    def test_two_deep_map_16(self):
+        c_map = self.make_two_deep_map(search_key_func=chk_map._search_key_16)
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  '2' LeafNode\n"
+            "      ('acc',) 'initial acc content'\n"
+            "      ('ccc',) 'initial ccc content'\n"
+            "  '4' LeafNode\n"
+            "      ('abb',) 'initial abb content'\n"
+            "  'C' LeafNode\n"
+            "      ('ace',) 'initial ace content'\n"
+            "  'F' InternalNode\n"
+            "    'F0' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "    'F3' LeafNode\n"
+            "      ('adl',) 'initial adl content'\n"
+            "    'F4' LeafNode\n"
+            "      ('adh',) 'initial adh content'\n"
+            "    'FB' LeafNode\n"
+            "      ('ddd',) 'initial ddd content'\n"
+            "    'FD' LeafNode\n"
+            "      ('add',) 'initial add content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_two_prefix_map_plain(self):
+        c_map = self.make_one_deep_two_prefix_map()
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  'aa' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "  'ad' LeafNode\n"
+            "      ('add',) 'initial add content'\n"
+            "      ('adh',) 'initial adh content'\n"
+            "      ('adl',) 'initial adl content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_two_prefix_map_16(self):
+        c_map = self.make_one_deep_two_prefix_map(
+            search_key_func=chk_map._search_key_16)
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  'F0' LeafNode\n"
+            "      ('aaa',) 'initial aaa content'\n"
+            "  'F3' LeafNode\n"
+            "      ('adl',) 'initial adl content'\n"
+            "  'F4' LeafNode\n"
+            "      ('adh',) 'initial adh content'\n"
+            "  'FD' LeafNode\n"
+            "      ('add',) 'initial add content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_one_prefix_map_plain(self):
+        c_map = self.make_one_deep_one_prefix_map()
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  'a' LeafNode\n"
+            "      ('add',) 'initial add content'\n"
+            "      ('adh',) 'initial adh content'\n"
+            "      ('adl',) 'initial adl content'\n"
+            "  'b' LeafNode\n"
+            "      ('bbb',) 'initial bbb content'\n",
+            c_map._dump_tree())
+
+    def test_one_deep_one_prefix_map_16(self):
+        c_map = self.make_one_deep_one_prefix_map(
+            search_key_func=chk_map._search_key_16)
+        self.assertEqualDiff(
+            "'' InternalNode\n"
+            "  '4' LeafNode\n"
+            "      ('bbb',) 'initial bbb content'\n"
+            "  'F' LeafNode\n"
+            "      ('add',) 'initial add content'\n"
+            "      ('adh',) 'initial adh content'\n"
+            "      ('adl',) 'initial adl content'\n",
+            c_map._dump_tree())
+
+
 class TestMap(TestCaseWithStore):
 
     def assertHasABMap(self, chk_bytes):
@@ -1886,62 +2124,408 @@
 # 1-4K get0
 
 
-class TestIterInterestingNodes(TestCaseWithStore):
-
-    def get_chk_bytes(self):
-        if getattr(self, '_chk_bytes', None) is None:
-            self._chk_bytes = super(TestIterInterestingNodes,
-                                    self).get_chk_bytes()
-        return self._chk_bytes
+class TestInterestingNodeIterator(TestCaseWithExampleMaps):
+
+    def get_iterator(self, interesting_roots, uninteresting_roots,
+                     search_key_func=None):
+        if search_key_func is None:
+            search_key_func = chk_map._search_key_plain
+        return chk_map.InterestingNodeIterator(self.get_chk_bytes(),
+            interesting_roots, uninteresting_roots, search_key_func)
+
+    def test__init__(self):
+        c_map = self.make_root_only_map()
+        key1 = c_map.key()
+        c_map.map(('aaa',), 'new aaa content')
+        key2 = c_map._save()
+        iterator = self.get_iterator([key2], [key1])
+        self.assertEqual(set([key1]), iterator._all_uninteresting_chks)
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual([], iterator._interesting_queue)
+
+    def help__read_all_roots(self, search_key_func):
+        c_map = self.make_root_only_map(search_key_func=search_key_func)
+        key1 = c_map.key()
+        c_map.map(('aaa',), 'new aaa content')
+        key2 = c_map._save()
+        iterator = self.get_iterator([key2], [key1], search_key_func)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # We should have queued up only items that aren't in the uninteresting
+        # set
+        self.assertEqual([(('aaa',), 'new aaa content')],
+                         iterator._interesting_item_queue)
+        self.assertEqual([], iterator._interesting_queue)
+        # And there are no uninteresting references, so that queue should be
+        # empty
+        self.assertEqual([], iterator._uninteresting_queue)
+
+    def test__read_all_roots_plain(self):
+        self.help__read_all_roots(search_key_func=chk_map._search_key_plain)
+
+    def test__read_all_roots_16(self):
+        self.help__read_all_roots(search_key_func=chk_map._search_key_16)
+
+    def test__read_all_roots_skips_known_uninteresting(self):
+        c_map = self.make_one_deep_map(chk_map._search_key_plain)
+        key1 = c_map.key()
+        c_map2 = self.make_root_only_map(chk_map._search_key_plain)
+        key2 = c_map2.key()
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        # We should have no results. key2 is completely contained within key1,
+        # and we should have seen that in the first pass
+        self.assertEqual([], root_results)
+
+    def test__read_all_roots_prepares_queues(self):
+        c_map = self.make_one_deep_map(chk_map._search_key_plain)
+        key1 = c_map.key()
+        c_map._dump_tree() # load everything
+        key1_a = c_map._root_node._items['a'].key()
+        c_map.map(('abb',), 'new abb content')
+        key2 = c_map._save()
+        key2_a = c_map._root_node._items['a'].key()
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # At this point, we should have queued up only the 'a' Leaf on both
+        # sides, both 'c' and 'd' are known to not have changed on both sides
+        self.assertEqual([key2_a], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+        self.assertEqual([key1_a], iterator._uninteresting_queue)
+
+    def test__read_all_roots_multi_interesting_prepares_queues(self):
+        c_map = self.make_one_deep_map(chk_map._search_key_plain)
+        key1 = c_map.key()
+        c_map._dump_tree() # load everything
+        key1_a = c_map._root_node._items['a'].key()
+        key1_c = c_map._root_node._items['c'].key()
+        c_map.map(('abb',), 'new abb content')
+        key2 = c_map._save()
+        key2_a = c_map._root_node._items['a'].key()
+        key2_c = c_map._root_node._items['c'].key()
+        c_map = chk_map.CHKMap(self.get_chk_bytes(), key1,
+                               chk_map._search_key_plain)
+        c_map.map(('ccc',), 'new ccc content')
+        key3 = c_map._save()
+        key3_a = c_map._root_node._items['a'].key()
+        key3_c = c_map._root_node._items['c'].key()
+        iterator = self.get_iterator([key2, key3], [key1],
+                                     chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual(sorted([key2, key3]), sorted(root_results))
+        # We should have queued up key2_a, and key3_c, but not key2_c or key3_c
+        self.assertEqual([key2_a, key3_c], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+        # And we should have queued up both a and c for the uninteresting set
+        self.assertEqual([key1_a, key1_c], iterator._uninteresting_queue)
+
+    def test__read_all_roots_different_depths(self):
+        c_map = self.make_two_deep_map(chk_map._search_key_plain)
+        c_map._dump_tree() # load everything
+        key1 = c_map.key()
+        key1_a = c_map._root_node._items['a'].key()
+        key1_c = c_map._root_node._items['c'].key()
+        key1_d = c_map._root_node._items['d'].key()
+
+        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
+        c_map2._dump_tree()
+        key2 = c_map2.key()
+        key2_aa = c_map2._root_node._items['aa'].key()
+        key2_ad = c_map2._root_node._items['ad'].key()
+
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # Only the 'a' subset should be queued up, since 'c' and 'd' cannot be
+        # present
+        self.assertEqual([key1_a], iterator._uninteresting_queue)
+        self.assertEqual([key2_aa, key2_ad], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+        iterator = self.get_iterator([key1], [key2], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key1], root_results)
+
+        self.assertEqual([key2_aa, key2_ad], iterator._uninteresting_queue)
+        self.assertEqual([key1_a, key1_c, key1_d], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_different_depths_16(self):
+        c_map = self.make_two_deep_map(chk_map._search_key_16)
+        c_map._dump_tree() # load everything
+        key1 = c_map.key()
+        key1_2 = c_map._root_node._items['2'].key()
+        key1_4 = c_map._root_node._items['4'].key()
+        key1_C = c_map._root_node._items['C'].key()
+        key1_F = c_map._root_node._items['F'].key()
+
+        c_map2 = self.make_one_deep_two_prefix_map(chk_map._search_key_16)
+        c_map2._dump_tree()
+        key2 = c_map2.key()
+        key2_F0 = c_map2._root_node._items['F0'].key()
+        key2_F3 = c_map2._root_node._items['F3'].key()
+        key2_F4 = c_map2._root_node._items['F4'].key()
+        key2_FD = c_map2._root_node._items['FD'].key()
+
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_16)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # Only the subset of keys that may be present should be queued up.
+        self.assertEqual([key1_F], iterator._uninteresting_queue)
+        self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
+                         sorted(iterator._interesting_queue))
+        self.assertEqual([], iterator._interesting_item_queue)
+
+        iterator = self.get_iterator([key1], [key2], chk_map._search_key_16)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key1], root_results)
+
+        self.assertEqual(sorted([key2_F0, key2_F3, key2_F4, key2_FD]),
+                         sorted(iterator._uninteresting_queue))
+        self.assertEqual(sorted([key1_2, key1_4, key1_C, key1_F]),
+                         sorted(iterator._interesting_queue))
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_mixed_depth(self):
+        c_map = self.make_one_deep_two_prefix_map(chk_map._search_key_plain)
+        c_map._dump_tree() # load everything
+        key1 = c_map.key()
+        key1_aa = c_map._root_node._items['aa'].key()
+        key1_ad = c_map._root_node._items['ad'].key()
+
+        c_map2 = self.make_one_deep_one_prefix_map(chk_map._search_key_plain)
+        c_map2._dump_tree()
+        key2 = c_map2.key()
+        key2_a = c_map2._root_node._items['a'].key()
+        key2_b = c_map2._root_node._items['b'].key()
+
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # 'ad' matches exactly 'a' on the other side, so it should be removed,
+        # and neither side should have it queued for walking
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual([key2_b], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+        iterator = self.get_iterator([key1], [key2], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key1], root_results)
+        # Note: This is technically not the 'true minimal' set that we could
+        #       use The reason is that 'a' was matched exactly to 'ad' (by sha
+        #       sum).  However, the code gets complicated in the case of more
+        #       than one interesting key, so for now, we live with this
+        #       Consider revising, though benchmarking showing it to be a
+        #       real-world issue should be done
+        self.assertEqual([key2_a], iterator._uninteresting_queue)
+        # self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual([key1_aa], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_yields_extra_deep_records(self):
+        # This is slightly controversial, as we will yield a chk page that we
+        # might later on find out could be filtered out. (If a root node is
+        # referenced deeper in the uninteresting set.)
+        # However, even with stacking, we always have all chk pages that we
+        # will need. So as long as we filter out the referenced keys, we'll
+        # never run into problems.
+        # This allows us to yield a root node record immediately, without any
+        # buffering.
+        c_map = self.make_two_deep_map(chk_map._search_key_plain)
+        c_map._dump_tree() # load all keys
+        key1 = c_map.key()
+        key1_a = c_map._root_node._items['a'].key()
+        c_map2 = self.get_map({
+            ('acc',): 'initial acc content',
+            ('ace',): 'initial ace content',
+        }, maximum_size=100)
+        self.assertEqualDiff(
+            "'' LeafNode\n"
+            "      ('acc',) 'initial acc content'\n"
+            "      ('ace',) 'initial ace content'\n",
+            c_map2._dump_tree())
+        key2 = c_map2.key()
+        iterator = self.get_iterator([key2], [key1], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key2], root_results)
+        # However, even though we have yielded the root node to be fetched,
+        # we should have enqued all of the chk pages to be walked, so that we
+        # can find the keys if they are present
+        self.assertEqual([key1_a], iterator._uninteresting_queue)
+        self.assertEqual([(('acc',), 'initial acc content'),
+                          (('ace',), 'initial ace content'),
+                         ], iterator._interesting_item_queue)
+
+    def test__read_all_roots_multiple_targets(self):
+        c_map = self.make_root_only_map()
+        key1 = c_map.key()
+        c_map = self.make_one_deep_map()
+        key2 = c_map.key()
+        c_map._dump_tree()
+        key2_c = c_map._root_node._items['c'].key()
+        key2_d = c_map._root_node._items['d'].key()
+        c_map.map(('ccc',), 'new ccc value')
+        key3 = c_map._save()
+        key3_c = c_map._root_node._items['c'].key()
+        iterator = self.get_iterator([key2, key3], [key1],
+                                     chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual(sorted([key2, key3]), sorted(root_results))
+        self.assertEqual([], iterator._uninteresting_queue)
+        # the key 'd' is interesting from key2 and key3, but should only be
+        # entered into the queue 1 time
+        self.assertEqual(sorted([key2_c, key3_c, key2_d]),
+                         sorted(iterator._interesting_queue))
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_no_uninteresting(self):
+        # This is the 'initial branch' case. With nothing in the uninteresting
+        # set, we can just queue up all root nodes into interesting queue, and
+        # then have them fast-path flushed via _flush_interesting_queue
+        c_map = self.make_two_deep_map()
+        key1 = c_map.key()
+        iterator = self.get_iterator([key1], [], chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([], root_results)
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual([key1], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+        c_map2 = self.make_one_deep_map()
+        key2 = c_map2.key()
+        iterator = self.get_iterator([key1, key2], [],
+                                     chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([], root_results)
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual(sorted([key1, key2]),
+                         sorted(iterator._interesting_queue))
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_no_uninteresting_16(self):
+        c_map = self.make_two_deep_map(chk_map._search_key_16)
+        key1 = c_map.key()
+        iterator = self.get_iterator([key1], [], chk_map._search_key_16)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([], root_results)
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual([key1], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+        c_map2 = self.make_one_deep_map(chk_map._search_key_16)
+        key2 = c_map2.key()
+        iterator = self.get_iterator([key1, key2], [],
+                                     chk_map._search_key_16)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([], root_results)
+        self.assertEqual([], iterator._uninteresting_queue)
+        self.assertEqual(sorted([key1, key2]),
+                         sorted(iterator._interesting_queue))
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__read_all_roots_multiple_uninteresting(self):
+        c_map = self.make_two_deep_map()
+        key1 = c_map.key()
+        c_map._dump_tree() # load everything
+        key1_a = c_map._root_node._items['a'].key()
+        c_map.map(('ccc',), 'new ccc value')
+        key2 = c_map._save()
+        key2_a = c_map._root_node._items['a'].key()
+        c_map.map(('add',), 'new add value')
+        key3 = c_map._save()
+        key3_a = c_map._root_node._items['a'].key()
+        iterator = self.get_iterator([key3], [key1, key2],
+                                     chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key3], root_results)
+        # the 'a' keys should not be queued up 2 times, since they are
+        # identical
+        self.assertEqual([key1_a], iterator._uninteresting_queue)
+        self.assertEqual([key3_a], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+
+    def test__process_next_uninteresting_batched_no_dupes(self):
+        c_map = self.make_two_deep_map()
+        key1 = c_map.key()
+        c_map._dump_tree() # load everything
+        key1_a = c_map._root_node._items['a'].key()
+        key1_aa = c_map._root_node._items['a']._items['aa'].key()
+        key1_ab = c_map._root_node._items['a']._items['ab'].key()
+        key1_ac = c_map._root_node._items['a']._items['ac'].key()
+        key1_ad = c_map._root_node._items['a']._items['ad'].key()
+        c_map.map(('aaa',), 'new aaa value')
+        key2 = c_map._save()
+        key2_a = c_map._root_node._items['a'].key()
+        key2_aa = c_map._root_node._items['a']._items['aa'].key()
+        c_map.map(('acc',), 'new acc content')
+        key3 = c_map._save()
+        key3_a = c_map._root_node._items['a'].key()
+        key3_ac = c_map._root_node._items['a']._items['ac'].key()
+        iterator = self.get_iterator([key3], [key1, key2],
+                                     chk_map._search_key_plain)
+        root_results = [record.key for record in iterator._read_all_roots()]
+        self.assertEqual([key3], root_results)
+        self.assertEqual(sorted([key1_a, key2_a]),
+                         sorted(iterator._uninteresting_queue))
+        self.assertEqual([key3_a], iterator._interesting_queue)
+        self.assertEqual([], iterator._interesting_item_queue)
+        iterator._process_next_uninteresting()
+        # All of the uninteresting records should be brought in and queued up,
+        # but we should not have any duplicates
+        self.assertEqual(sorted([key1_aa, key1_ab, key1_ac, key1_ad, key2_aa]),
+                         sorted(iterator._uninteresting_queue))
+
+
+class TestIterInterestingNodes(TestCaseWithExampleMaps):
 
     def get_map_key(self, a_dict, maximum_size=10):
-        c_map = self._get_map(a_dict, maximum_size=maximum_size,
-                              chk_bytes=self.get_chk_bytes())
+        c_map = self.get_map(a_dict, maximum_size=maximum_size)
         return c_map.key()
 
-    def assertIterInteresting(self, expected, interesting_keys,
+    def assertIterInteresting(self, records, items, interesting_keys,
                               uninteresting_keys):
         """Check the result of iter_interesting_nodes.
 
-        :param expected: A list of (record_keys, interesting_chk_pages,
-                                    interesting key value pairs)
+        Note that we no longer care how many steps are taken, etc, just that
+        the right contents are returned.
+
+        :param records: A list of record keys that should be yielded
+        :param items: A list of items (key,value) that should be yielded.
         """
         store = self.get_chk_bytes()
+        store._search_key_func = chk_map._search_key_plain
         iter_nodes = chk_map.iter_interesting_nodes(store, interesting_keys,
                                                     uninteresting_keys)
-        nodes = list(iter_nodes)
-        for count, (exp, act) in enumerate(izip(expected, nodes)):
-            exp_record, exp_items = exp
-            record, items = act
-            exp_tuple = (exp_record, sorted(exp_items))
-            if record is None:
-                act_tuple = (None, sorted(items))
-            else:
-                act_tuple = (record.key, sorted(items))
-            self.assertEqual(exp_tuple, act_tuple,
-                             'entry %d did not match expected' % count)
-        self.assertEqual(len(expected), len(nodes))
+        record_keys = []
+        all_items = []
+        for record, new_items in iter_nodes:
+            if record is not None:
+                record_keys.append(record.key)
+            if new_items:
+                all_items.extend(new_items)
+        self.assertEqual(sorted(records), sorted(record_keys))
+        self.assertEqual(sorted(items), sorted(all_items))
 
     def test_empty_to_one_keys(self):
         target = self.get_map_key({('a',): 'content'})
-        self.assertIterInteresting(
-            [(target, [(('a',), 'content')]),
-            ], [target], [])
+        self.assertIterInteresting([target],
+                                   [(('a',), 'content')],
+                                   [target], [])
 
     def test_none_to_one_key(self):
         basis = self.get_map_key({})
         target = self.get_map_key({('a',): 'content'})
-        self.assertIterInteresting(
-            [(None, [(('a',), 'content')]),
-             (target, []),
-            ], [target], [basis])
+        self.assertIterInteresting([target],
+                                   [(('a',), 'content')],
+                                   [target], [basis])
 
     def test_one_to_none_key(self):
         basis = self.get_map_key({('a',): 'content'})
         target = self.get_map_key({})
-        self.assertIterInteresting(
-            [(target, [])],
-            [target], [basis])
+        self.assertIterInteresting([target],
+                                   [],
+                                   [target], [basis])
 
     def test_common_pages(self):
         basis = self.get_map_key({('a',): 'content',
@@ -1964,10 +2548,9 @@
             target_map._dump_tree())
         b_key = target_map._root_node._items['b'].key()
         # This should return the root node, and the node for the 'b' key
-        self.assertIterInteresting(
-            [(target, []),
-             (b_key, [(('b',), 'other content')])],
-            [target], [basis])
+        self.assertIterInteresting([target, b_key],
+                                   [(('b',), 'other content')],
+                                   [target], [basis])
 
     def test_common_sub_page(self):
         basis = self.get_map_key({('aaa',): 'common',
@@ -1991,12 +2574,11 @@
         # The key for the internal aa node
         a_key = target_map._root_node._items['a'].key()
         # The key for the leaf aab node
+        # aaa_key = target_map._root_node._items['a']._items['aaa'].key()
         aab_key = target_map._root_node._items['a']._items['aab'].key()
-        self.assertIterInteresting(
-            [(target, []),
-             (a_key, []),
-             (aab_key, [(('aab',), 'new')])],
-            [target], [basis])
+        self.assertIterInteresting([target, a_key, aab_key],
+                                   [(('aab',), 'new')],
+                                   [target], [basis])
 
     def test_common_leaf(self):
         basis = self.get_map_key({})
@@ -2040,29 +2622,22 @@
         a_key = target3_map._root_node._items['a'].key()
         aac_key = target3_map._root_node._items['a']._items['aac'].key()
         self.assertIterInteresting(
-            [(None, [(('aaa',), 'common')]),
-             (target1, []),
-             (target2, []),
-             (target3, []),
-             (b_key, [(('bbb',), 'new')]),
-             (a_key, []),
-             (aac_key, [(('aac',), 'other')]),
-            ], [target1, target2, target3], [basis])
-
-        self.assertIterInteresting(
-            [(target2, []),
-             (target3, []),
-             (b_key, [(('bbb',), 'new')]),
-             (a_key, []),
-             (aac_key, [(('aac',), 'other')]),
-            ], [target2, target3], [target1])
-
-        # This may be a case that we relax. A root node is a deep child of the
-        # excluded set. The cost is buffering root nodes until we have
-        # determined all possible exclusions. (Because a prefix of '', cannot
-        # be excluded.)
-        self.assertIterInteresting(
-            [], [target1], [target3])
+            [target1, target2, target3, a_key, aac_key, b_key],
+            [(('aaa',), 'common'), (('bbb',), 'new'), (('aac',), 'other')],
+            [target1, target2, target3], [basis])
+
+        self.assertIterInteresting(
+            [target2, target3, a_key, aac_key, b_key],
+            [(('bbb',), 'new'), (('aac',), 'other')],
+            [target2, target3], [target1])
+
+        # Technically, target1 could be filtered out, but since it is a root
+        # node, we yield it immediately, rather than waiting to find out much
+        # later on.
+        self.assertIterInteresting(
+            [target1],
+            [],
+            [target1], [target3])
 
     def test_multiple_maps(self):
         basis1 = self.get_map_key({('aaa',): 'common',
@@ -2111,13 +2686,9 @@
         # The key for the leaf bba node
         bba_key = target2_map._root_node._items['b']._items['bba'].key()
         self.assertIterInteresting(
-            [(target1, []),
-             (target2, []),
-             (a_key, []),
-             (b_key, []),
-             (aac_key, [(('aac',), 'target1')]),
-             (bba_key, [(('bba',), 'target2')]),
-            ], [target1, target2], [basis1, basis2])
+            [target1, target2, a_key, aac_key, b_key, bba_key],
+            [(('aac',), 'target1'), (('bba',), 'target2')],
+            [target1, target2], [basis1, basis2])
 
     def test_multiple_maps_overlapping_common_new(self):
         # Test that when a node found through the interesting_keys iteration
@@ -2188,17 +2759,10 @@
             right_map._dump_tree())
         # Keys from the right side target - none, the root is enough.
         # Test behaviour
-        self.expectFailure("we don't properly filter different depths",
-            self.assertIterInteresting,
-            [(left, []),
-             (right, []),
-             (l_d_key, [(('ddd',), 'change')]),
-            ], [left, right], [basis])
         self.assertIterInteresting(
-            [(left, []),
-             (right, []),
-             (l_d_key, [(('ddd',), 'change')]),
-            ], [left, right], [basis])
+            [right, left, l_d_key],
+            [(('ddd',), 'change')],
+            [left, right], [basis])
 
     def test_multiple_maps_similar(self):
         # We want to have a depth=2 tree, with multiple entries in each leaf
@@ -2259,8 +2823,6 @@
         r_a_key = right_map._root_node._items['a'].key()
         r_c_key = right_map._root_node._items['c'].key()
         self.assertIterInteresting(
-            [(left, []),
-             (right, []),
-             (l_a_key, [(('abb',), 'changed left')]),
-             (r_c_key, [(('cbb',), 'changed right')]),
-            ], [left, right], [basis])
+            [right, left, l_a_key, r_c_key],
+            [(('abb',), 'changed left'), (('cbb',), 'changed right')],
+            [left, right], [basis])