Repository: cayleygraph/cayley
Pull request #871 (2019-10-15 08:11:27)

Drop old iterators and switch to a new ones
Previously we introduced a new iterator interface, but all the implementations were hidden under a compatibility layer.

This change removes an old type and exposes new ones, changing the code accordingly.

Addresses #862

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cayleygraph/cayley/871)
<!-- Reviewable:end -->



Patch:
diff --git a/cmd/cayley/command/dedup.go b/cmd/cayley/command/dedup.go
index ac424dd..9c7f576 100644
--- a/cmd/cayley/command/dedup.go
+++ b/cmd/cayley/command/dedup.go
@@ -140,7 +140,7 @@ func dedupProperties(ctx context.Context, h *graph.Handle, pred, typ quad.IRI) e
 	}
 	err := p.Iterate(ictx).Each(func(s graph.Ref) {
 		cnt++
-		it := qs.QuadIterator(quad.Subject, s)
+		it := qs.QuadIterator(quad.Subject, s).Iterate()
 		defer it.Close()
 		m := make(map[interface{}]property)
 		for it.Next(ictx) {
@@ -180,7 +180,7 @@ func dedupProperties(ctx context.Context, h *graph.Handle, pred, typ quad.IRI) e
 
 func dedupValueTx(ctx context.Context, h *graph.Handle, tx *graph.Transaction, a, b graph.Ref) error {
 	v := h.NameOf(b)
-	it := h.QuadIterator(quad.Object, a)
+	it := h.QuadIterator(quad.Object, a).Iterate()
 	defer it.Close()
 	for it.Next(ctx) {
 		// TODO(dennwc): we should be able to add "raw" quads without getting values for directions
@@ -194,7 +194,7 @@ func dedupValueTx(ctx context.Context, h *graph.Handle, tx *graph.Transaction, a
 	}
 	it.Close()
 
-	it = h.QuadIterator(quad.Subject, a)
+	it = h.QuadIterator(quad.Subject, a).Iterate()
 	defer it.Close()
 	for it.Next(ctx) {
 		q := h.Quad(it.Result())
diff --git a/examples/hello_bolt/main.go b/examples/hello_bolt/main.go
index 5a31132..3e59003 100644
--- a/examples/hello_bolt/main.go
+++ b/examples/hello_bolt/main.go
@@ -42,14 +42,15 @@ func main() {
 	// This is more advanced example of the query.
 	// Simpler equivalent can be found in hello_world example.
 
+	ctx := context.TODO()
 	// Now we get an iterator for the path and optimize it.
 	// The second return is if it was optimized, but we don't care for now.
-	it, _ := p.BuildIterator().Optimize()
+	its, _ := p.BuildIterator().Optimize(ctx)
+	it := its.Iterate()
 
 	// remember to cleanup after yourself
 	defer it.Close()
 
-	ctx := context.TODO()
 	// While we have items
 	for it.Next(ctx) {
 		token := it.Result()                // get a ref to a node (backend-specific)
diff --git a/examples/hello_schema/main.go b/examples/hello_schema/main.go
index fc1a3dc..55d7690 100644
--- a/examples/hello_schema/main.go
+++ b/examples/hello_schema/main.go
@@ -122,7 +122,8 @@ func main() {
 	// Print quads
 	fmt.Println("\nquads:")
 	ctx := context.TODO()
-	it := store.QuadsAllIterator()
+	it := store.QuadsAllIterator().Iterate()
+	defer it.Close()
 	for it.Next(ctx) {
 		fmt.Println(store.Quad(it.Result()))
 	}
diff --git a/graph/gaedatastore/iterator.go b/graph/gaedatastore/iterator.go
index 95e55ab..a848c75 100644
--- a/graph/gaedatastore/iterator.go
+++ b/graph/gaedatastore/iterator.go
@@ -25,8 +25,120 @@ import (
 	"google.golang.org/appengine/datastore"
 )
 
+var _ graph.IteratorShape = &Iterator{}
+
+const (
+	bufferSize = 50
+)
+
 type Iterator struct {
-	size   int64
+	size  int64
+	dir   quad.Direction
+	qs    *QuadStore
+	t     *Token
+	isAll bool
+	kind  string
+}
+
+func (it *Iterator) Iterate() graph.Scanner {
+	if it.isAll {
+		return newAllIteratorNext(it.qs, it.kind)
+	}
+	return newIteratorNext(it.qs, it.kind, it.dir, it.t)
+}
+
+func (it *Iterator) Lookup() graph.Index {
+	if it.isAll {
+		return newAllIteratorContains(it.qs, it.kind)
+	}
+	return newIteratorContains(it.qs, it.kind, it.dir, it.t)
+}
+
+func (qs *QuadStore) newIterator(k string, d quad.Direction, val graph.Ref) *Iterator {
+	t := val.(*Token)
+	if t == nil {
+		clog.Errorf("Token == nil")
+	}
+	return &Iterator{
+		dir:   d,
+		qs:    qs,
+		isAll: false,
+		t:     t,
+		kind:  k,
+	}
+}
+
+func (qs *QuadStore) newAllIterator(kind string) *Iterator {
+	return &Iterator{
+		qs:    qs,
+		dir:   quad.Any,
+		isAll: true,
+		kind:  kind,
+	}
+}
+
+// No subiterators.
+func (it *Iterator) SubIterators() []graph.IteratorShape {
+	return nil
+}
+
+func (it *Iterator) Sorted() bool                                             { return false }
+func (it *Iterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
+func (it *Iterator) String() string {
+	name := ""
+	if it.t != nil {
+		name = quad.StringOf(it.qs.NameOf(it.t)) + "/" + it.t.Hash
+	}
+	return fmt.Sprintf("GAE(%s)", name)
+}
+
+func (it *Iterator) getSize(ctx context.Context) (graph.Size, error) {
+	if it.size != 0 {
+		return graph.Size{
+			Value: it.size,
+			Exact: true,
+		}, nil
+	}
+	if !it.isAll {
+		// The number of references to this node is held in the nodes entity
+		key := it.qs.createKeyFromToken(it.t)
+		foundNode := new(NodeEntry)
+		err := datastore.Get(it.qs.context, key, foundNode)
+		if err != datastore.ErrNoSuchEntity {
+			err = nil
+		}
+		size := foundNode.Size
+		it.size = size
+		return graph.Size{
+			Value: it.size,
+			Exact: err == nil,
+		}, err
+	}
+	var size int64
+	st, err := it.qs.Stats(context.Background(), true)
+	if it.kind == nodeKind {
+		size = st.Nodes.Value
+	} else {
+		size = st.Quads.Value
+	}
+	it.size = size
+	return graph.Size{
+		Value: it.size,
+		Exact: err == nil,
+	}, err
+}
+
+func (it *Iterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	sz, err := it.getSize(ctx)
+	// TODO (panamafrancis) calculate costs
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     5,
+		Size:         sz,
+	}, err
+}
+
+type iteratorNext struct {
 	dir    quad.Direction
 	qs     *QuadStore
 	name   string
@@ -41,44 +153,27 @@ type Iterator struct {
 	err    error
 }
 
-var (
-	bufferSize = 50
-)
-
-func NewIterator(qs *QuadStore, k string, d quad.Direction, val graph.Ref) *Iterator {
-	t := val.(*Token)
+func newIteratorNext(qs *QuadStore, k string, d quad.Direction, t *Token) *iteratorNext {
 	if t == nil {
 		clog.Errorf("Token == nil")
 	}
 	if t.Kind != nodeKind {
 		clog.Errorf("Cannot create an iterator from a non-node value")
-		return &Iterator{done: true}
+		return &iteratorNext{done: true}
 	}
 	if k != nodeKind && k != quadKind {
 		clog.Errorf("Cannot create iterator for unknown kind")
-		return &Iterator{done: true}
+		return &iteratorNext{done: true}
 	}
 	if qs.context == nil {
 		clog.Errorf("Cannot create iterator without a valid context")
-		return &Iterator{done: true}
+		return &iteratorNext{done: true}
 	}
 	name := quad.StringOf(qs.NameOf(t))
-
-	// The number of references to this node is held in the nodes entity
-	key := qs.createKeyFromToken(t)
-	foundNode := new(NodeEntry)
-	err := datastore.Get(qs.context, key, foundNode)
-	if err != nil && err != datastore.ErrNoSuchEntity {
-		clog.Errorf("Error: %v", err)
-		return &Iterator{done: true}
-	}
-	size := foundNode.Size
-
-	return &Iterator{
+	return &iteratorNext{
 		name:  name,
 		dir:   d,
 		qs:    qs,
-		size:  size,
 		isAll: false,
 		kind:  k,
 		hash:  t.Hash,
@@ -86,43 +181,24 @@ func NewIterator(qs *QuadStore, k string, d quad.Direction, val graph.Ref) *Iter
 	}
 }
 
-func NewAllIterator(qs *QuadStore, kind string) *Iterator {
+func newAllIteratorNext(qs *QuadStore, kind string) *iteratorNext {
 	if kind != nodeKind && kind != quadKind {
 		clog.Errorf("Cannot create iterator for an unknown kind")
-		return &Iterator{done: true}
+		return &iteratorNext{done: true}
 	}
 	if qs.context == nil {
 		clog.Errorf("Cannot create iterator without a valid context")
-		return &Iterator{done: true}
-	}
-
-	st, err := qs.Stats(context.Background(), true)
-	var size int64
-	if kind == nodeKind {
-		size = st.Nodes.Size
-	} else {
-		size = st.Quads.Size
+		return &iteratorNext{done: true}
 	}
-	return &Iterator{
+	return &iteratorNext{
 		qs:    qs,
-		size:  size,
-		err:   err,
 		dir:   quad.Any,
 		isAll: true,
 		kind:  kind,
-		done:  err != nil,
 	}
 }
 
-func (it *Iterator) Reset() {
-	it.buffer = nil
-	it.offset = 0
-	it.done = false
-	it.last = ""
-	it.result = nil
-}
-
-func (it *Iterator) Close() error {
+func (it *iteratorNext) Close() error {
 	it.buffer = nil
 	it.offset = 0
 	it.done = true
@@ -131,56 +207,17 @@ func (it *Iterator) Close() error {
 	return nil
 }
 
-func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
-	if it.isAll {
-		// The result needs to be set, so when contains is called, the result can be retrieved
-		it.result = v
-		return true
-	}
-	t := v.(*Token)
-	if t == nil {
-		clog.Errorf("Could not cast to token")
-		return false
-	}
-	if t.Kind == nodeKind {
-		clog.Errorf("Contains does not work with node values")
-		return false
-	}
-	// Contains is for when you want to know that an iterator refers to a quad
-	var offset int
-	switch it.dir {
-	case quad.Subject:
-		offset = 0
-	case quad.Predicate:
-		offset = (quad.HashSize * 2)
-	case quad.Object:
-		offset = (quad.HashSize * 2) * 2
-	case quad.Label:
-		offset = (quad.HashSize * 2) * 3
-	}
-	val := t.Hash[offset : offset+(quad.HashSize*2)]
-	if val == it.hash {
-		return true
-	}
-	return false
-}
-
-func (it *Iterator) TagResults(dst map[string]graph.Ref) {}
+func (it *iteratorNext) TagResults(dst map[string]graph.Ref) {}
 
-func (it *Iterator) NextPath(ctx context.Context) bool {
+func (it *iteratorNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
-// No subiterators.
-func (it *Iterator) SubIterators() []graph.Iterator {
-	return nil
-}
-
-func (it *Iterator) Result() graph.Ref {
+func (it *iteratorNext) Result() graph.Ref {
 	return it.result
 }
 
-func (it *Iterator) Next(ctx context.Context) bool {
+func (it *iteratorNext) Next(ctx context.Context) bool {
 	if it.offset+1 < len(it.buffer) {
 		it.offset++
 		it.result = &Token{Kind: it.kind, Hash: it.buffer[it.offset]}
@@ -254,29 +291,127 @@ func (it *Iterator) Next(ctx context.Context) bool {
 	return true
 }
 
-func (it *Iterator) Err() error {
+func (it *iteratorNext) Err() error {
 	return it.err
 }
 
-func (it *Iterator) Size() (int64, bool) {
-	return it.size, true
+func (it *iteratorNext) Sorted() bool { return false }
+func (it *iteratorNext) String() string {
+	return fmt.Sprintf("GAE(%s/%s)", it.name, it.hash)
 }
 
-func (it *Iterator) Sorted() bool                     { return false }
-func (it *Iterator) Optimize() (graph.Iterator, bool) { return it, false }
-func (it *Iterator) String() string {
-	return fmt.Sprintf("GAE(%s/%s)", it.name, it.hash)
+type iteratorContains struct {
+	dir    quad.Direction
+	qs     *QuadStore
+	name   string
+	isAll  bool
+	kind   string
+	hash   string
+	done   bool
+	result graph.Ref
+	err    error
 }
 
-// TODO (panamafrancis) calculate costs
-func (it *Iterator) Stats() graph.IteratorStats {
-	size, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: 1,
-		NextCost:     5,
-		Size:         size,
-		ExactSize:    exact,
+func newIteratorContains(qs *QuadStore, k string, d quad.Direction, t *Token) *iteratorContains {
+	if t == nil {
+		clog.Errorf("Token == nil")
+	}
+	if t.Kind != nodeKind {
+		clog.Errorf("Cannot create an iterator from a non-node value")
+		return &iteratorContains{done: true}
+	}
+	if k != nodeKind && k != quadKind {
+		clog.Errorf("Cannot create iterator for unknown kind")
+		return &iteratorContains{done: true}
+	}
+	if qs.context == nil {
+		clog.Errorf("Cannot create iterator without a valid context")
+		return &iteratorContains{done: true}
+	}
+	name := quad.StringOf(qs.NameOf(t))
+	return &iteratorContains{
+		name:  name,
+		dir:   d,
+		qs:    qs,
+		isAll: false,
+		kind:  k,
+		hash:  t.Hash,
+		done:  false,
+	}
+}
+
+func newAllIteratorContains(qs *QuadStore, kind string) *iteratorContains {
+	if kind != nodeKind && kind != quadKind {
+		clog.Errorf("Cannot create iterator for an unknown kind")
+		return &iteratorContains{done: true}
+	}
+	if qs.context == nil {
+		clog.Errorf("Cannot create iterator without a valid context")
+		return &iteratorContains{done: true}
+	}
+	return &iteratorContains{
+		qs:    qs,
+		dir:   quad.Any,
+		isAll: true,
+		kind:  kind,
+	}
+}
+
+func (it *iteratorContains) Close() error {
+	it.done = true
+	it.result = nil
+	return nil
+}
+
+func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
+	if it.isAll {
+		// The result needs to be set, so when contains is called, the result can be retrieved
+		it.result = v
+		return true
+	}
+	t := v.(*Token)
+	if t == nil {
+		clog.Errorf("Could not cast to token")
+		return false
+	}
+	if t.Kind == nodeKind {
+		clog.Errorf("Contains does not work with node values")
+		return false
+	}
+	// Contains is for when you want to know that an iterator refers to a quad
+	var offset int
+	switch it.dir {
+	case quad.Subject:
+		offset = 0
+	case quad.Predicate:
+		offset = (quad.HashSize * 2)
+	case quad.Object:
+		offset = (quad.HashSize * 2) * 2
+	case quad.Label:
+		offset = (quad.HashSize * 2) * 3
+	}
+	val := t.Hash[offset : offset+(quad.HashSize*2)]
+	if val == it.hash {
+		return true
 	}
+	return false
 }
 
-var _ graph.Iterator = &Iterator{}
+func (it *iteratorContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *iteratorContains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *iteratorContains) Result() graph.Ref {
+	return it.result
+}
+
+func (it *iteratorContains) Err() error {
+	return it.err
+}
+
+func (it *iteratorContains) Sorted() bool { return false }
+func (it *iteratorContains) String() string {
+	return fmt.Sprintf("GAE(%s/%s)", it.name, it.hash)
+}
diff --git a/graph/gaedatastore/quadstore.go b/graph/gaedatastore/quadstore.go
index bc62810..c5946dc 100644
--- a/graph/gaedatastore/quadstore.go
+++ b/graph/gaedatastore/quadstore.go
@@ -437,16 +437,16 @@ func (qs *QuadStore) updateLog(in []graph.Delta) ([]int64, error) {
 	return out, nil
 }
 
-func (qs *QuadStore) QuadIterator(dir quad.Direction, v graph.Ref) graph.Iterator {
-	return NewIterator(qs, quadKind, dir, v)
+func (qs *QuadStore) QuadIterator(dir quad.Direction, v graph.Ref) graph.IteratorShape {
+	return qs.newIterator(quadKind, dir, v)
 }
 
-func (qs *QuadStore) NodesAllIterator() graph.Iterator {
-	return NewAllIterator(qs, nodeKind)
+func (qs *QuadStore) NodesAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(nodeKind)
 }
 
-func (qs *QuadStore) QuadsAllIterator() graph.Iterator {
-	return NewAllIterator(qs, quadKind)
+func (qs *QuadStore) QuadsAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(quadKind)
 }
 
 func (qs *QuadStore) ValueOf(s quad.Value) graph.Ref {
@@ -525,11 +525,11 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 	}
 	return graph.Stats{
 		Nodes: graph.Size{
-			Size:  m.NodeCount,
+			Value: m.NodeCount,
 			Exact: true,
 		},
 		Quads: graph.Size{
-			Size:  m.QuadCount,
+			Value: m.QuadCount,
 			Exact: true,
 		},
 	}, nil
@@ -538,7 +538,7 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, val graph.Ref) (graph.Size, error) {
 	t, ok := val.(*Token)
 	if !ok || t.Kind != nodeKind {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	} else if qs.context == nil {
 		return graph.Size{}, errors.New("cannot count iterator without a valid context")
 	}
@@ -548,7 +548,7 @@ func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, val
 	if err != nil && err != datastore.ErrNoSuchEntity {
 		return graph.Size{}, err
 	}
-	return graph.Size{Size: n.Size, Exact: true}, nil
+	return graph.Size{Value: n.Size, Exact: true}, nil
 }
 
 func (qs *QuadStore) Close() error {
diff --git a/graph/graphmock/graphmock.go b/graph/graphmock/graphmock.go
index 57e321e..c5d9a72 100644
--- a/graph/graphmock/graphmock.go
+++ b/graph/graphmock/graphmock.go
@@ -26,7 +26,7 @@ func (s StringNode) Key() interface{} { return s }
 type Oldstore struct {
 	Parse bool
 	Data  []string
-	Iter  graph.Iterator
+	Iter  graph.IteratorShape
 }
 
 func (qs *Oldstore) valueAt(i int) quad.Value {
@@ -74,18 +74,18 @@ func (qs *Oldstore) ApplyDeltas([]graph.Delta, graph.IgnoreOpts) error { return
 
 func (qs *Oldstore) Quad(graph.Ref) quad.Quad { return quad.Quad{} }
 
-func (qs *Oldstore) QuadIterator(d quad.Direction, i graph.Ref) graph.Iterator {
+func (qs *Oldstore) QuadIterator(d quad.Direction, i graph.Ref) graph.IteratorShape {
 	return qs.Iter
 }
 
 func (qs *Oldstore) QuadIteratorSize(ctx context.Context, d quad.Direction, val graph.Ref) (graph.Size, error) {
-	sz, exact := qs.Iter.Size()
-	return graph.Size{Size: sz, Exact: exact}, nil
+	st, err := qs.Iter.Stats(ctx)
+	return st.Size, err
 }
 
-func (qs *Oldstore) NodesAllIterator() graph.Iterator { return &iterator.Null{} }
+func (qs *Oldstore) NodesAllIterator() graph.IteratorShape { return &iterator.Null{} }
 
-func (qs *Oldstore) QuadsAllIterator() graph.Iterator { return &iterator.Null{} }
+func (qs *Oldstore) QuadsAllIterator() graph.IteratorShape { return &iterator.Null{} }
 
 func (qs *Oldstore) NameOf(v graph.Ref) quad.Value {
 	switch v := v.(type) {
@@ -109,8 +109,8 @@ func (qs *Oldstore) Size() int64 { return 0 }
 
 func (qs *Oldstore) DebugPrint() {}
 
-func (qs *Oldstore) OptimizeIterator(it graph.Iterator) (graph.Iterator, bool) {
-	return &iterator.Null{}, false
+func (qs *Oldstore) OptimizeIterator(it graph.IteratorShape) (graph.IteratorShape, bool) {
+	return iterator.NewNull(), false
 }
 
 func (qs *Oldstore) Close() error { return nil }
@@ -173,7 +173,7 @@ func (qs *Store) Close() error { return nil }
 
 func (qs *Store) DebugPrint() {}
 
-func (qs *Store) QuadIterator(d quad.Direction, i graph.Ref) graph.Iterator {
+func (qs *Store) QuadIterator(d quad.Direction, i graph.Ref) graph.IteratorShape {
 	fixed := iterator.NewFixed()
 	v := i.(graph.PreFetchedValue).NameOf()
 	for _, q := range qs.Data {
@@ -189,13 +189,13 @@ func (qs *Store) QuadIteratorSize(ctx context.Context, d quad.Direction, val gra
 	sz := graph.Size{Exact: true}
 	for _, q := range qs.Data {
 		if q.Get(d) == v {
-			sz.Size++
+			sz.Value++
 		}
 	}
 	return sz, nil
 }
 
-func (qs *Store) NodesAllIterator() graph.Iterator {
+func (qs *Store) NodesAllIterator() graph.IteratorShape {
 	set := make(map[string]bool)
 	for _, q := range qs.Data {
 		for _, d := range quad.Directions {
@@ -212,7 +212,7 @@ func (qs *Store) NodesAllIterator() graph.Iterator {
 	return fixed
 }
 
-func (qs *Store) QuadsAllIterator() graph.Iterator {
+func (qs *Store) QuadsAllIterator() graph.IteratorShape {
 	fixed := iterator.NewFixed()
 	for _, q := range qs.Data {
 		fixed.Add(quadValue{q})
@@ -231,7 +231,7 @@ func (qs *Store) Stats(ctx context.Context, exact bool) (graph.Stats, error) {
 		}
 	}
 	return graph.Stats{
-		Nodes: graph.Size{Size: int64(len(set)), Exact: true},
-		Quads: graph.Size{Size: int64(len(qs.Data)), Exact: true},
+		Nodes: graph.Size{Value: int64(len(set)), Exact: true},
+		Quads: graph.Size{Value: int64(len(qs.Data)), Exact: true},
 	}, nil
 }
diff --git a/graph/iterate.go b/graph/iterate.go
index 0982ec2..ca94414 100644
--- a/graph/iterate.go
+++ b/graph/iterate.go
@@ -2,10 +2,8 @@ package graph
 
 import (
 	"context"
-	"encoding/json"
 	"fmt"
 
-	"github.com/cayleygraph/cayley/clog"
 	"github.com/cayleygraph/quad"
 )
 
@@ -27,12 +25,12 @@ type IterateChain struct {
 // Iterator will be optimized and closed after execution.
 //
 // By default, iteration has no limit and includes sub-paths.
-func Iterate(ctx context.Context, it Iterator) *IterateChain {
+func Iterate(ctx context.Context, it IteratorShape) *IterateChain {
 	if ctx == nil {
 		ctx = context.Background()
 	}
 	return &IterateChain{
-		ctx: ctx, s: AsShape(it),
+		ctx: ctx, s: it,
 		limit: -1, paths: true,
 		optimize: true,
 	}
@@ -66,25 +64,10 @@ func (c *IterateChain) start() {
 		c.s, _ = c.s.Optimize(c.ctx)
 	}
 	c.it = c.s.Iterate()
-	if !clog.V(2) {
-		return
-	}
-	if b, err := json.MarshalIndent(DescribeIterator(AsLegacy(c.s)), "", "  "); err != nil {
-		clog.Infof("failed to format description: %v", err)
-	} else {
-		clog.Infof("%s", b)
-	}
 }
+
 func (c *IterateChain) end() {
 	c.it.Close()
-	if !clog.V(2) {
-		return
-	}
-	if b, err := json.MarshalIndent(DumpStats(AsLegacy(c.s)), "", "  "); err != nil {
-		clog.Infof("failed to format stats: %v", err)
-	} else {
-		clog.Infof("%s", b)
-	}
 }
 
 // Limit limits a total number of results returned.
@@ -144,9 +127,9 @@ func (c *IterateChain) Count() (int64, error) {
 		c.s, _ = c.s.Optimize(c.ctx)
 	}
 	if st, err := c.s.Stats(c.ctx); err != nil {
-		return st.Size.Size, err
+		return st.Size.Value, err
 	} else if st.Size.Exact {
-		return st.Size.Size, nil
+		return st.Size.Value, nil
 	}
 	c.start()
 	defer c.end()
diff --git a/graph/iterator.go b/graph/iterator.go
index fa412ba..febd585 100644
--- a/graph/iterator.go
+++ b/graph/iterator.go
@@ -18,7 +18,6 @@ package graph
 
 import (
 	"context"
-	"reflect"
 
 	"github.com/cayleygraph/quad"
 )
@@ -45,13 +44,6 @@ type TaggerBase interface {
 	AddFixedTag(tag string, value Ref)
 }
 
-// Tagger is an interface for iterators that can tag values. Tags are returned as a part of TagResults call.
-type Tagger interface {
-	Iterator
-	TaggerBase
-	CopyFromTagger(st TaggerBase)
-}
-
 // IteratorBase is a set of common methods for Scanner and Index iterators.
 type IteratorBase interface {
 	// String returns a short textual representation of an iterator.
@@ -92,7 +84,8 @@ type IteratorBase interface {
 	Close() error
 }
 
-type Iterator interface {
+// Scanner is an iterator that lists all results sequentially, but not necessarily in a sorted order.
+type Scanner interface {
 	IteratorBase
 
 	// Next advances the iterator to the next value, which will then be available through
@@ -100,12 +93,49 @@ type Iterator interface {
 	// error was encountered during iteration.  Err should be consulted to distinguish
 	// between the two cases.
 	Next(ctx context.Context) bool
+}
+
+// Index is an index lookup iterator. It allows to check if an index contains a specific value.
+type Index interface {
+	IteratorBase
 
 	// Contains returns whether the value is within the set held by the iterator.
+	//
+	// It will set Result to the matching subtree. TagResults can be used to collect values from tree branches.
 	Contains(ctx context.Context, v Ref) bool
+}
 
-	// Start iteration from the beginning
-	Reset()
+// Tagger is an interface for iterators that can tag values. Tags are returned as a part of TagResults call.
+type TaggerShape interface {
+	IteratorShape
+	TaggerBase
+	CopyFromTagger(st TaggerBase)
+}
+
+type IteratorCosts struct {
+	ContainsCost int64
+	NextCost     int64
+	Size         Size
+}
+
+// Shape is an iterator shape, similar to a query plan. But the plan is not specific in this
+// case - it is used to reorder query branches, and the decide what branches will be scanned
+// and what branches will lookup values (hopefully from the index, but not necessarily).
+type IteratorShape interface {
+	// TODO(dennwc): merge with shape.Shape
+
+	// String returns a short textual representation of an iterator.
+	String() string
+
+	// Iterate starts this iterator in scanning mode. Resulting iterator will list all
+	// results sequentially, but not necessary in the sorted order. Caller must close
+	// the iterator.
+	Iterate() Scanner
+
+	// Lookup starts this iterator in an index lookup mode. Depending on the iterator type,
+	// this may still involve database scans. Resulting iterator allows to check an index
+	// contains a specified value. Caller must close the iterator.
+	Lookup() Index
 
 	// These methods relate to choosing the right iterator, or optimizing an
 	// iterator tree
@@ -114,80 +144,28 @@ type Iterator interface {
 	// this iterator, as well as the size. Roughly, it will take NextCost * Size
 	// "cost units" to get everything out of the iterator. This is a wibbly-wobbly
 	// thing, and not exact, but a useful heuristic.
-	Stats() IteratorStats
-
-	// Helpful accessor for the number of things in the iterator. The first return
-	// value is the size, and the second return value is whether that number is exact,
-	// or a conservative estimate.
-	Size() (int64, bool)
+	Stats(ctx context.Context) (IteratorCosts, error)
 
 	// Optimizes an iterator. Can replace the iterator, or merely move things
 	// around internally. if it chooses to replace it with a better iterator,
 	// returns (the new iterator, true), if not, it returns (self, false).
-	Optimize() (Iterator, bool)
+	Optimize(ctx context.Context) (IteratorShape, bool)
 
 	// Return a slice of the subiterators for this iterator.
-	SubIterators() []Iterator
-}
-
-// IteratorFuture is an optional interface for legacy Iterators that support direct conversion
-// to an IteratorShape. This interface should be avoided an will be deprecated in the future.
-type IteratorFuture interface {
-	Iterator
-	AsShape() IteratorShape
-}
-
-// DescribeIterator returns a description of the iterator tree.
-func DescribeIterator(it Iterator) Description {
-	sz, exact := it.Size()
-	d := Description{
-		UID:  uint64(reflect.ValueOf(it).Pointer()),
-		Name: it.String(),
-		Type: reflect.TypeOf(it).String(),
-		Size: sz, Exact: exact,
-	}
-	if tg, ok := it.(Tagger); ok {
-		d.Tags = tg.Tags()
-	}
-	if sub := it.SubIterators(); len(sub) != 0 {
-		d.Iterators = make([]Description, 0, len(sub))
-		for _, sit := range sub {
-			d.Iterators = append(d.Iterators, DescribeIterator(sit))
-		}
-	}
-	return d
-}
-
-type Description struct {
-	UID       uint64        `json:",omitempty"`
-	Name      string        `json:",omitempty"`
-	Type      string        `json:",omitempty"`
-	Tags      []string      `json:",omitempty"`
-	Size      int64         `json:",omitempty"`
-	Exact     bool          `json:",omitempty"`
-	Iterators []Description `json:",omitempty"`
+	SubIterators() []IteratorShape
 }
 
 // ApplyMorphism is a curried function that can generates a new iterator based on some prior iterator.
-type ApplyMorphism func(QuadStore, Iterator) Iterator
+type ApplyMorphism func(QuadStore, IteratorShape) IteratorShape
 
 // Height is a convienence function to measure the height of an iterator tree.
-func Height(it Iterator, filter func(Iterator) bool) int {
+func Height(it IteratorShape, filter func(IteratorShape) bool) int {
 	if filter != nil && !filter(it) {
 		return 1
 	}
 	subs := it.SubIterators()
 	maxDepth := 0
 	for _, sub := range subs {
-		if s, ok := sub.(IteratorFuture); ok {
-			h := Height2(s.AsShape(), func(it IteratorShape) bool {
-				return filter(AsLegacy(it))
-			})
-			if h > maxDepth {
-				maxDepth = h
-			}
-			continue
-		}
 		h := Height(sub, filter)
 		if h > maxDepth {
 			maxDepth = h
@@ -196,37 +174,6 @@ func Height(it Iterator, filter func(Iterator) bool) int {
 	return maxDepth + 1
 }
 
-// Height is a convienence function to measure the height of an iterator tree.
-func Height2(it IteratorShape, filter func(IteratorShape) bool) int {
-	if filter != nil && !filter(it) {
-		return 1
-	}
-	subs := it.SubIterators()
-	maxDepth := 0
-	for _, sub := range subs {
-		if s, ok := sub.(IteratorShapeCompat); ok {
-			h := Height(s.AsLegacy(), func(it Iterator) bool {
-				return filter(AsShape(it))
-			})
-			if h > maxDepth {
-				maxDepth = h
-			}
-			continue
-		}
-		h := Height2(sub, filter)
-		if h > maxDepth {
-			maxDepth = h
-		}
-	}
-	return maxDepth + 1
-}
-
-// FixedIterator wraps iterators that are modifiable by addition of fixed value sets.
-type FixedIterator interface {
-	Iterator
-	Add(Ref)
-}
-
 type IteratorStats struct {
 	ContainsCost int64
 	NextCost     int64
@@ -236,21 +183,3 @@ type IteratorStats struct {
 	Contains     int64
 	ContainsNext int64
 }
-
-type StatsContainer struct {
-	UID  uint64
-	Type string
-	IteratorStats
-	SubIts []StatsContainer
-}
-
-func DumpStats(it Iterator) StatsContainer {
-	var out StatsContainer
-	out.IteratorStats = it.Stats()
-	out.Type = reflect.TypeOf(it).String()
-	out.UID = uint64(reflect.ValueOf(it).Pointer())
-	for _, sub := range it.SubIterators() {
-		out.SubIts = append(out.SubIts, DumpStats(sub))
-	}
-	return out
-}
diff --git a/graph/iterator/and.go b/graph/iterator/and.go
index a32933a..8493f84 100644
--- a/graph/iterator/and.go
+++ b/graph/iterator/and.go
@@ -21,55 +21,9 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &And{}
-
 // The And iterator. Consists of a number of subiterators, the primary of which will
 // be Next()ed if next is called.
 type And struct {
-	it *and
-	graph.Iterator
-}
-
-// NewAnd creates an And iterator. `qs` is only required when needing a handle
-// for QuadStore-specific optimizations, otherwise nil is acceptable.
-func NewAnd(sub ...graph.Iterator) *And {
-	it := &And{
-		it: newAnd(),
-	}
-	for _, s := range sub {
-		it.it.AddSubIterator(graph.AsShape(s))
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *And) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-// Add a subiterator to this And iterator.
-//
-// The first iterator that is added becomes the primary iterator. This is
-// important. Calling Optimize() is the way to change the order based on
-// subiterator statistics. Without Optimize(), the order added is the order
-// used.
-func (it *And) AddSubIterator(sub graph.Iterator) {
-	it.it.AddSubIterator(graph.AsShape(sub))
-}
-
-// AddOptionalIterator adds an iterator that will only be Contain'ed and will not affect iteration results.
-// Only tags will be propagated from this iterator.
-func (it *And) AddOptionalIterator(sub graph.Iterator) *And {
-	it.it.AddOptionalIterator(graph.AsShape(sub))
-	return it
-}
-
-var _ graph.IteratorShapeCompat = &and{}
-
-// The And iterator. Consists of a number of subiterators, the primary of which will
-// be Next()ed if next is called.
-type and struct {
 	sub       []graph.IteratorShape
 	checkList []graph.IteratorShape // special order for Contains
 	opt       []graph.IteratorShape
@@ -77,8 +31,8 @@ type and struct {
 
 // NewAnd creates an And iterator. `qs` is only required when needing a handle
 // for QuadStore-specific optimizations, otherwise nil is acceptable.
-func newAnd(sub ...graph.IteratorShape) *and {
-	it := &and{
+func NewAnd(sub ...graph.IteratorShape) *And {
+	it := &And{
 		sub: make([]graph.IteratorShape, 0, 20),
 	}
 	for _, s := range sub {
@@ -87,9 +41,9 @@ func newAnd(sub ...graph.IteratorShape) *and {
 	return it
 }
 
-func (it *and) Iterate() graph.Scanner {
+func (it *And) Iterate() graph.Scanner {
 	if len(it.sub) == 0 {
-		return newNull().Iterate()
+		return NewNull().Iterate()
 	}
 	sub := make([]graph.Index, 0, len(it.sub)-1)
 	for _, s := range it.sub[1:] {
@@ -102,9 +56,9 @@ func (it *and) Iterate() graph.Scanner {
 	return newAndNext(it.sub[0].Iterate(), newAndContains(sub, opt))
 }
 
-func (it *and) Lookup() graph.Index {
+func (it *And) Lookup() graph.Index {
 	if len(it.sub) == 0 {
-		return newNull().Lookup()
+		return NewNull().Lookup()
 	}
 	sub := make([]graph.Index, 0, len(it.sub))
 	check := it.checkList
@@ -121,21 +75,15 @@ func (it *and) Lookup() graph.Index {
 	return newAndContains(sub, opt)
 }
 
-func (it *and) AsLegacy() graph.Iterator {
-	it2 := &And{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // Returns a slice of the subiterators, in order (primary iterator first).
-func (it *and) SubIterators() []graph.IteratorShape {
+func (it *And) SubIterators() []graph.IteratorShape {
 	iters := make([]graph.IteratorShape, 0, len(it.sub)+len(it.opt))
 	iters = append(iters, it.sub...)
 	iters = append(iters, it.opt...)
 	return iters
 }
 
-func (it *and) String() string {
+func (it *And) String() string {
 	return "And"
 }
 
@@ -145,7 +93,7 @@ func (it *and) String() string {
 // important. Calling Optimize() is the way to change the order based on
 // subiterator statistics. Without Optimize(), the order added is the order
 // used.
-func (it *and) AddSubIterator(sub graph.IteratorShape) {
+func (it *And) AddSubIterator(sub graph.IteratorShape) {
 	if sub == nil {
 		panic("nil iterator")
 	}
@@ -154,7 +102,7 @@ func (it *and) AddSubIterator(sub graph.IteratorShape) {
 
 // AddOptionalIterator adds an iterator that will only be Contain'ed and will not affect iteration results.
 // Only tags will be propagated from this iterator.
-func (it *and) AddOptionalIterator(sub graph.IteratorShape) *and {
+func (it *And) AddOptionalIterator(sub graph.IteratorShape) *And {
 	it.opt = append(it.opt, sub)
 	return it
 }
diff --git a/graph/iterator/and_optimize.go b/graph/iterator/and_optimize.go
index a158d1c..adc000f 100644
--- a/graph/iterator/and_optimize.go
+++ b/graph/iterator/and_optimize.go
@@ -41,19 +41,19 @@ import (
 
 // Optimizes the And, by picking the most efficient way to Next() and
 // Contains() its subiterators. For SQL fans, this is equivalent to JOIN.
-func (it *and) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *And) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	// First, let's get the slice of iterators, in order (first one is Next()ed,
 	// the rest are Contains()ed)
 	old := it.sub
 	if len(old) == 0 {
-		return newNull(), true
+		return NewNull(), true
 	}
 
 	// And call Optimize() on our subtree, replacing each one in the order we
 	// found them. it_list is the newly optimized versions of these, and changed
 	// is another list, of only the ones that have returned replacements and
 	// changed.
-	its := optimizeSubIterators2(ctx, old)
+	its := optimizeSubIterators(ctx, old)
 
 	// If we can find only one subiterator which is equivalent to this whole and,
 	// we can replace the And...
@@ -73,9 +73,9 @@ func (it *and) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	// The easiest thing to do at this point is merely to create a new And iterator
 	// and replace ourselves with our (reordered, optimized) clone.
 	// Add the subiterators in order.
-	newAnd := newAnd(its...)
+	newAnd := NewAnd(its...)
 
-	opt := optimizeSubIterators2(ctx, it.opt)
+	opt := optimizeSubIterators(ctx, it.opt)
 	for _, sub := range opt {
 		newAnd.AddOptionalIterator(sub)
 	}
@@ -92,7 +92,7 @@ func (it *and) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 func optimizeReplacement(its []graph.IteratorShape) graph.IteratorShape {
 	// If we were created with no SubIterators, we're as good as Null.
 	if len(its) == 0 {
-		return newNull()
+		return NewNull()
 	}
 	if len(its) == 1 {
 		// When there's only one iterator, there's only one choice.
@@ -102,7 +102,7 @@ func optimizeReplacement(its []graph.IteratorShape) graph.IteratorShape {
 	// there's no point in continuing the branch, we will have no results
 	// and we are null as well.
 	if hasAnyNullIterators(its) {
-		return newNull()
+		return NewNull()
 	}
 	return nil
 }
@@ -130,9 +130,9 @@ func optimizeOrder(ctx context.Context, its []graph.IteratorShape) []graph.Itera
 				continue
 			}
 			stats, _ := f.Stats(ctx)
-			cost += stats.ContainsCost * (1 + (rootStats.Size.Size / (stats.Size.Size + 1)))
+			cost += stats.ContainsCost * (1 + (rootStats.Size.Value / (stats.Size.Value + 1)))
 		}
-		cost *= rootStats.Size.Size
+		cost *= rootStats.Size.Value
 		if clog.V(3) {
 			clog.Infof("And: Root: %p Total Cost: %v Best: %v", root, cost, bestCost)
 		}
@@ -200,7 +200,7 @@ func (c byCost) Swap(i, j int) {
 
 // optimizeContains() creates an alternate check list, containing the same contents
 // but with a new ordering, however it wishes.
-func (it *and) optimizeContains(ctx context.Context) error {
+func (it *And) optimizeContains(ctx context.Context) error {
 	// GetSubIterators allocates, so this is currently safe.
 	// TODO(kortschak) Reuse it.checkList if possible.
 	// This involves providing GetSubIterators with a slice to fill.
@@ -213,20 +213,7 @@ func (it *and) optimizeContains(ctx context.Context) error {
 // of them. It returns two lists -- the first contains the same list as l, where
 // any replacements are made by Optimize() and the second contains the originals
 // which were replaced.
-func optimizeSubIterators(its []graph.Iterator) []graph.Iterator {
-	out := make([]graph.Iterator, 0, len(its))
-	for _, it := range its {
-		o, _ := it.Optimize()
-		out = append(out, o)
-	}
-	return out
-}
-
-// optimizeSubIterators(l) takes a list of iterators and calls Optimize() on all
-// of them. It returns two lists -- the first contains the same list as l, where
-// any replacements are made by Optimize() and the second contains the originals
-// which were replaced.
-func optimizeSubIterators2(ctx context.Context, its []graph.IteratorShape) []graph.IteratorShape {
+func optimizeSubIterators(ctx context.Context, its []graph.IteratorShape) []graph.IteratorShape {
 	out := make([]graph.IteratorShape, 0, len(its))
 	for _, it := range its {
 		o, _ := it.Optimize(ctx)
@@ -238,7 +225,7 @@ func optimizeSubIterators2(ctx context.Context, its []graph.IteratorShape) []gra
 // Check a list of iterators for any Null iterators.
 func hasAnyNullIterators(its []graph.IteratorShape) bool {
 	for _, it := range its {
-		if IsNull2(it) {
+		if IsNull(it) {
 			return true
 		}
 	}
@@ -252,12 +239,12 @@ func materializeIts(ctx context.Context, its []graph.IteratorShape) ([]graph.Ite
 	out = append(out, its[0])
 	for i, it := range its[1:] {
 		st := stats[i+1]
-		if st.Size.Size*st.NextCost < (st.ContainsCost * (1 + (st.Size.Size / (allStats.Size.Size + 1)))) {
-			if graph.Height(graph.AsLegacy(it), func(it graph.Iterator) bool {
+		if st.Size.Value*st.NextCost < (st.ContainsCost * (1 + (st.Size.Value / (allStats.Size.Value + 1)))) {
+			if graph.Height(it, func(it graph.IteratorShape) bool {
 				_, ok := it.(*Materialize)
 				return !ok
 			}) > 10 {
-				out = append(out, newMaterialize(it))
+				out = append(out, NewMaterialize(it))
 				continue
 			}
 		}
@@ -278,7 +265,7 @@ func getStatsForSlice(ctx context.Context, its, opt []graph.IteratorShape) (grap
 
 	containsCost := primaryStats.ContainsCost
 	nextCost := primaryStats.NextCost
-	size := primaryStats.Size.Size
+	size := primaryStats.Size.Value
 	exact := primaryStats.Size.Exact
 
 	var last error
@@ -288,23 +275,23 @@ func getStatsForSlice(ctx context.Context, its, opt []graph.IteratorShape) (grap
 			last = err
 		}
 		arr = append(arr, stats)
-		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Size / (stats.Size.Size + 1)))
+		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Value / (stats.Size.Value + 1)))
 		containsCost += stats.ContainsCost
-		if size > stats.Size.Size {
-			size = stats.Size.Size
+		if size > stats.Size.Value {
+			size = stats.Size.Value
 			exact = stats.Size.Exact
 		}
 	}
 	for _, sub := range opt {
 		stats, _ := sub.Stats(ctx)
-		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Size / (stats.Size.Size + 1)))
+		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Value / (stats.Size.Value + 1)))
 		containsCost += stats.ContainsCost
 	}
 	return graph.IteratorCosts{
 		ContainsCost: containsCost,
 		NextCost:     nextCost,
 		Size: graph.Size{
-			Size:  size,
+			Value: size,
 			Exact: exact,
 		},
 	}, arr, last
@@ -318,7 +305,7 @@ func getStatsForSlice(ctx context.Context, its, opt []graph.IteratorShape) (grap
 // with an intersection, we know that the largest we can be is the size of the
 // smallest iterator. This is the heuristic we shall follow. Better heuristics
 // welcome.
-func (it *and) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *And) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	stats, _, err := getStatsForSlice(ctx, it.sub, it.opt)
 	return stats, err
 }
diff --git a/graph/iterator/count.go b/graph/iterator/count.go
index 0b2e35f..5b96f36 100644
--- a/graph/iterator/count.go
+++ b/graph/iterator/count.go
@@ -7,86 +7,55 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &Count{}
-
 // Count iterator returns one element with size of underlying iterator.
 type Count struct {
-	it *count
-	graph.Iterator
-}
-
-// NewCount creates a new iterator to count a number of results from a provided subiterator.
-// qs may be nil - it's used to check if count Contains (is) a given value.
-func NewCount(sub graph.Iterator, qs graph.Namer) *Count {
-	it := &Count{
-		it: newCount(graph.AsShape(sub), qs),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Count) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = &count{}
-
-// Count iterator returns one element with size of underlying iterator.
-type count struct {
 	it graph.IteratorShape
 	qs graph.Namer
 }
 
 // NewCount creates a new iterator to count a number of results from a provided subiterator.
 // qs may be nil - it's used to check if count Contains (is) a given value.
-func newCount(it graph.IteratorShape, qs graph.Namer) *count {
-	return &count{
+func NewCount(it graph.IteratorShape, qs graph.Namer) *Count {
+	return &Count{
 		it: it, qs: qs,
 	}
 }
 
-func (it *count) Iterate() graph.Scanner {
+func (it *Count) Iterate() graph.Scanner {
 	return newCountNext(it.it)
 }
 
-func (it *count) Lookup() graph.Index {
+func (it *Count) Lookup() graph.Index {
 	return newCountContains(it.it, it.qs)
 }
 
-func (it *count) AsLegacy() graph.Iterator {
-	it2 := &Count{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // SubIterators returns a slice of the sub iterators.
-func (it *count) SubIterators() []graph.IteratorShape {
+func (it *Count) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.it}
 }
 
-func (it *count) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Count) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	sub, optimized := it.it.Optimize(ctx)
 	it.it = sub
 	return it, optimized
 }
 
-func (it *count) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Count) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	stats := graph.IteratorCosts{
 		NextCost: 1,
 		Size: graph.Size{
-			Size:  1,
+			Value: 1,
 			Exact: true,
 		},
 	}
 	if sub, err := it.it.Stats(ctx); err == nil && !sub.Size.Exact {
-		stats.NextCost = sub.NextCost * sub.Size.Size
+		stats.NextCost = sub.NextCost * sub.Size.Value
 	}
 	stats.ContainsCost = stats.NextCost
 	return stats, nil
 }
 
-func (it *count) String() string { return "Count" }
+func (it *Count) String() string { return "Count" }
 
 // Count iterator returns one element with size of underlying iterator.
 type countNext struct {
@@ -120,14 +89,14 @@ func (it *countNext) Next(ctx context.Context) bool {
 	if !st.Size.Exact {
 		sit := it.it.Iterate()
 		defer sit.Close()
-		for st.Size.Size = 0; sit.Next(ctx); st.Size.Size++ {
+		for st.Size.Value = 0; sit.Next(ctx); st.Size.Value++ {
 			// TODO(dennwc): it's unclear if we should call it here or not
-			for ; sit.NextPath(ctx); st.Size.Size++ {
+			for ; sit.NextPath(ctx); st.Size.Value++ {
 			}
 		}
 		it.err = sit.Err()
 	}
-	it.result = quad.Int(st.Size.Size)
+	it.result = quad.Int(st.Size.Value)
 	it.done = true
 	return true
 }
diff --git a/graph/iterator/fixed.go b/graph/iterator/fixed.go
index b34fec5..e50b07e 100644
--- a/graph/iterator/fixed.go
+++ b/graph/iterator/fixed.go
@@ -27,95 +27,55 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Fixed{}
+var _ graph.IteratorShape = &Fixed{}
 
 // A Fixed iterator consists of it's values, an index (where it is in the process of Next()ing) and
 // an equality function.
 type Fixed struct {
-	it *fixed
-	graph.Iterator
-}
-
-// Creates a new Fixed iterator with a custom comparator.
-func NewFixed(vals ...graph.Ref) *Fixed {
-	it := &Fixed{
-		it: newFixed(vals...),
-	}
-	it.Iterator = graph.AsLegacy(it.it)
-	return it
-}
-
-// Add a value to the iterator. The array now contains this value.
-// TODO(barakmich): This ought to be a set someday, disallowing repeated values.
-func (it *Fixed) Add(v graph.Ref) {
-	it.it.Add(v)
-}
-
-// Values returns a list of values stored in iterator. Slice should not be modified.
-func (it *Fixed) Values() []graph.Ref {
-	return it.it.Values()
-}
-
-func (it *Fixed) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShape = &fixed{}
-
-// A Fixed iterator consists of it's values, an index (where it is in the process of Next()ing) and
-// an equality function.
-type fixed struct {
 	values []graph.Ref
 }
 
 // Creates a new Fixed iterator with a custom comparator.
-func newFixed(vals ...graph.Ref) *fixed {
-	return &fixed{
+func NewFixed(vals ...graph.Ref) *Fixed {
+	return &Fixed{
 		values: append([]graph.Ref{}, vals...),
 	}
 }
 
-func (it *fixed) Iterate() graph.Scanner {
+func (it *Fixed) Iterate() graph.Scanner {
 	return newFixedNext(it.values)
 }
 
-func (it *fixed) Lookup() graph.Index {
+func (it *Fixed) Lookup() graph.Index {
 	return newFixedContains(it.values)
 }
 
-func (it *fixed) AsLegacy() graph.Iterator {
-	it2 := &Fixed{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // Add a value to the iterator. The array now contains this value.
 // TODO(barakmich): This ought to be a set someday, disallowing repeated values.
-func (it *fixed) Add(v graph.Ref) {
+func (it *Fixed) Add(v graph.Ref) {
 	it.values = append(it.values, v)
 }
 
 // Values returns a list of values stored in iterator. Slice must not be modified.
-func (it *fixed) Values() []graph.Ref {
+func (it *Fixed) Values() []graph.Ref {
 	return it.values
 }
 
-func (it *fixed) String() string {
+func (it *Fixed) String() string {
 	return fmt.Sprintf("Fixed(%v)", it.values)
 }
 
 // No sub-iterators.
-func (it *fixed) SubIterators() []graph.IteratorShape {
+func (it *Fixed) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
 // Optimize() for a Fixed iterator is simple. Returns a Null iterator if it's empty
 // (so that other iterators upstream can treat this as null) or there is no
 // optimization.
-func (it *fixed) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Fixed) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	if len(it.values) == 1 && it.values[0] == nil {
-		return newNull(), true
+		return NewNull(), true
 	}
 
 	return it, false
@@ -123,12 +83,12 @@ func (it *fixed) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 
 // As we right now have to scan the entire list, Next and Contains are linear with the
 // size. However, a better data structure could remove these limits.
-func (it *fixed) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Fixed) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	return graph.IteratorCosts{
 		ContainsCost: 1,
 		NextCost:     1,
 		Size: graph.Size{
-			Size:  int64(len(it.values)),
+			Value: int64(len(it.values)),
 			Exact: true,
 		},
 	}, nil
diff --git a/graph/iterator/hasa.go b/graph/iterator/hasa.go
index 73b3cb6..6235df0 100644
--- a/graph/iterator/hasa.go
+++ b/graph/iterator/hasa.go
@@ -42,40 +42,10 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &HasA{}
-
 // A HasA consists of a reference back to the graph.QuadStore that it references,
 // a primary subiterator, a direction in which the quads for that subiterator point,
 // and a temporary holder for the iterator generated on Contains().
 type HasA struct {
-	it *hasA
-	graph.Iterator
-}
-
-// Construct a new HasA iterator, given the quad subiterator, and the quad
-// direction for which it stands.
-func NewHasA(qs graph.QuadIndexer, subIt graph.Iterator, d quad.Direction) *HasA {
-	it := &HasA{
-		it: newHasA(qs, graph.AsShape(subIt), d),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *HasA) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-// Direction accessor.
-func (it *HasA) Direction() quad.Direction { return it.it.Direction() }
-
-var _ graph.IteratorShapeCompat = &hasA{}
-
-// A HasA consists of a reference back to the graph.QuadStore that it references,
-// a primary subiterator, a direction in which the quads for that subiterator point,
-// and a temporary holder for the iterator generated on Contains().
-type hasA struct {
 	qs      graph.QuadIndexer
 	primary graph.IteratorShape
 	dir     quad.Direction
@@ -83,50 +53,44 @@ type hasA struct {
 
 // Construct a new HasA iterator, given the quad subiterator, and the quad
 // direction for which it stands.
-func newHasA(qs graph.QuadIndexer, subIt graph.IteratorShape, d quad.Direction) *hasA {
-	return &hasA{
+func NewHasA(qs graph.QuadIndexer, subIt graph.IteratorShape, d quad.Direction) *HasA {
+	return &HasA{
 		qs:      qs,
 		primary: subIt,
 		dir:     d,
 	}
 }
 
-func (it *hasA) Iterate() graph.Scanner {
+func (it *HasA) Iterate() graph.Scanner {
 	return newHasANext(it.qs, it.primary.Iterate(), it.dir)
 }
 
-func (it *hasA) Lookup() graph.Index {
+func (it *HasA) Lookup() graph.Index {
 	return newHasAContains(it.qs, it.primary.Lookup(), it.dir)
 }
 
-func (it *hasA) AsLegacy() graph.Iterator {
-	it2 := &HasA{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // Return our sole subiterator.
-func (it *hasA) SubIterators() []graph.IteratorShape {
+func (it *HasA) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.primary}
 }
 
 // Direction accessor.
-func (it *hasA) Direction() quad.Direction { return it.dir }
+func (it *HasA) Direction() quad.Direction { return it.dir }
 
 // Pass the Optimize() call along to the subiterator. If it becomes Null,
 // then the HasA becomes Null (there are no quads that have any directions).
-func (it *hasA) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *HasA) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newPrimary, changed := it.primary.Optimize(ctx)
 	if changed {
 		it.primary = newPrimary
-		if IsNull2(it.primary) {
+		if IsNull(it.primary) {
 			return it.primary, true
 		}
 	}
 	return it, false
 }
 
-func (it *hasA) String() string {
+func (it *HasA) String() string {
 	return fmt.Sprintf("HasA(%v)", it.dir)
 }
 
@@ -136,7 +100,7 @@ func (it *hasA) String() string {
 // one sticks -- potentially expensive, depending on fanout. Size, however, is
 // potentially smaller. we know at worst it's the size of the subiterator, but
 // if there are many repeated values, it could be much smaller in totality.
-func (it *hasA) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *HasA) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	subitStats, err := it.primary.Stats(ctx)
 	// TODO(barakmich): These should really come from the quadstore itself
 	// and be optimized.
@@ -148,7 +112,7 @@ func (it *hasA) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 		NextCost:     quadConstant + subitStats.NextCost,
 		ContainsCost: (fanoutFactor * nextConstant) * subitStats.ContainsCost,
 		Size: graph.Size{
-			Size:  faninFactor * subitStats.Size.Size,
+			Value: faninFactor * subitStats.Size.Value,
 			Exact: false,
 		},
 	}, err
@@ -261,7 +225,7 @@ func (it *hasAContains) Contains(ctx context.Context, val graph.Ref) bool {
 	if it.results != nil {
 		it.results.Close()
 	}
-	it.results = graph.AsShape(it.qs.QuadIterator(it.dir, val)).Iterate()
+	it.results = it.qs.QuadIterator(it.dir, val).Iterate()
 	ok := it.nextContains(ctx)
 	if it.err != nil {
 		return false
diff --git a/graph/iterator/iterator.go b/graph/iterator/iterator.go
index 2642eda..90a3289 100644
--- a/graph/iterator/iterator.go
+++ b/graph/iterator/iterator.go
@@ -24,27 +24,15 @@ import (
 )
 
 var (
-	_ graph.Iterator = &Null{}
-	_ graph.Iterator = &Error{}
+	_ graph.IteratorShape = &Null{}
+	_ graph.IteratorShape = &Error{}
 )
 
-type Morphism func(graph.Iterator) graph.Iterator
-type Morphism2 func(graph.IteratorShape) graph.IteratorShape
+type Morphism func(graph.IteratorShape) graph.IteratorShape
 
-func IsNull(it graph.Iterator) bool {
+func IsNull(it graph.IteratorShape) bool {
 	if _, ok := it.(*Null); ok {
 		return true
-	} else if _, ok := graph.AsShape(it).(*null); ok {
-		return true
-	}
-	return false
-}
-
-func IsNull2(it graph.IteratorShape) bool {
-	if _, ok := it.(*null); ok {
-		return true
-	} else if _, ok := graph.AsLegacy(it).(*Null); ok {
-		return true
 	}
 	return false
 }
@@ -59,6 +47,14 @@ func NewNull() *Null {
 	return &Null{}
 }
 
+func (it *Null) Iterate() graph.Scanner {
+	return it
+}
+
+func (it *Null) Lookup() graph.Index {
+	return it
+}
+
 // Fill the map based on the tags assigned to this iterator.
 func (it *Null) TagResults(dst map[string]graph.Ref) {}
 
@@ -68,7 +64,7 @@ func (it *Null) Contains(ctx context.Context, v graph.Ref) bool {
 
 // A good iterator will close itself when it returns true.
 // Null has nothing it needs to do.
-func (it *Null) Optimize() (graph.Iterator, bool) { return it, false }
+func (it *Null) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
 
 func (it *Null) String() string {
 	return "Null"
@@ -86,7 +82,7 @@ func (it *Null) Result() graph.Ref {
 	return nil
 }
 
-func (it *Null) SubIterators() []graph.Iterator {
+func (it *Null) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
@@ -94,10 +90,6 @@ func (it *Null) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Null) Size() (int64, bool) {
-	return 0, true
-}
-
 func (it *Null) Reset() {}
 
 func (it *Null) Close() error {
@@ -105,8 +97,8 @@ func (it *Null) Close() error {
 }
 
 // A null iterator costs nothing. Use it!
-func (it *Null) Stats() graph.IteratorStats {
-	return graph.IteratorStats{}
+func (it *Null) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	return graph.IteratorCosts{}, nil
 }
 
 // Error iterator always returns a single error with no other results.
@@ -118,6 +110,14 @@ func NewError(err error) *Error {
 	return &Error{err: err}
 }
 
+func (it *Error) Iterate() graph.Scanner {
+	return it
+}
+
+func (it *Error) Lookup() graph.Index {
+	return it
+}
+
 // Fill the map based on the tags assigned to this iterator.
 func (it *Error) TagResults(dst map[string]graph.Ref) {}
 
@@ -125,7 +125,7 @@ func (it *Error) Contains(ctx context.Context, v graph.Ref) bool {
 	return false
 }
 
-func (it *Error) Optimize() (graph.Iterator, bool) { return it, false }
+func (it *Error) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
 
 func (it *Error) String() string {
 	return fmt.Sprintf("Error(%v)", it.err)
@@ -143,7 +143,7 @@ func (it *Error) Result() graph.Ref {
 	return nil
 }
 
-func (it *Error) SubIterators() []graph.Iterator {
+func (it *Error) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
@@ -151,153 +151,12 @@ func (it *Error) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Error) Size() (int64, bool) {
-	return 0, true
-}
-
 func (it *Error) Reset() {}
 
 func (it *Error) Close() error {
 	return it.err
 }
 
-func (it *Error) Stats() graph.IteratorStats {
-	return graph.IteratorStats{}
-}
-
-var (
-	_ graph.IteratorShapeCompat = &null{}
-	_ graph.IteratorShapeCompat = &error2{}
-)
-
-// Here we define the simplest iterator -- the Null iterator. It contains nothing.
-// It is the empty set. Often times, queries that contain one of these match nothing,
-// so it's important to give it a special iterator.
-type null struct{}
-
-// Fairly useless New function.
-func newNull() *null {
-	return &null{}
-}
-
-func (it *null) Iterate() graph.Scanner {
-	return it
-}
-
-func (it *null) Lookup() graph.Index {
-	return it
-}
-
-func (it *null) AsLegacy() graph.Iterator {
-	return NewNull()
-}
-
-// Fill the map based on the tags assigned to this iterator.
-func (it *null) TagResults(dst map[string]graph.Ref) {}
-
-func (it *null) Contains(ctx context.Context, v graph.Ref) bool {
-	return false
-}
-
-// A good iterator will close itself when it returns true.
-// Null has nothing it needs to do.
-func (it *null) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
-
-func (it *null) String() string {
-	return "Null"
-}
-
-func (it *null) Next(ctx context.Context) bool {
-	return false
-}
-
-func (it *null) Err() error {
-	return nil
-}
-
-func (it *null) Result() graph.Ref {
-	return nil
-}
-
-func (it *null) SubIterators() []graph.IteratorShape {
-	return nil
-}
-
-func (it *null) NextPath(ctx context.Context) bool {
-	return false
-}
-
-func (it *null) Reset() {}
-
-func (it *null) Close() error {
-	return nil
-}
-
-// A null iterator costs nothing. Use it!
-func (it *null) Stats(ctx context.Context) (graph.IteratorCosts, error) {
-	return graph.IteratorCosts{}, nil
-}
-
-// Error iterator always returns a single error with no other results.
-type error2 struct {
-	err error
-}
-
-func newError2(err error) *error2 {
-	return &error2{err: err}
-}
-
-func (it *error2) Iterate() graph.Scanner {
-	return it
-}
-
-func (it *error2) Lookup() graph.Index {
-	return it
-}
-
-func (it *error2) AsLegacy() graph.Iterator {
-	return NewError(it.err)
-}
-
-// Fill the map based on the tags assigned to this iterator.
-func (it *error2) TagResults(dst map[string]graph.Ref) {}
-
-func (it *error2) Contains(ctx context.Context, v graph.Ref) bool {
-	return false
-}
-
-func (it *error2) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
-
-func (it *error2) String() string {
-	return fmt.Sprintf("Error(%v)", it.err)
-}
-
-func (it *error2) Next(ctx context.Context) bool {
-	return false
-}
-
-func (it *error2) Err() error {
-	return it.err
-}
-
-func (it *error2) Result() graph.Ref {
-	return nil
-}
-
-func (it *error2) SubIterators() []graph.IteratorShape {
-	return nil
-}
-
-func (it *error2) NextPath(ctx context.Context) bool {
-	return false
-}
-
-func (it *error2) Reset() {}
-
-func (it *error2) Close() error {
-	return it.err
-}
-
-func (it *error2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Error) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	return graph.IteratorCosts{}, nil
 }
diff --git a/graph/iterator/limit.go b/graph/iterator/limit.go
index 1097cde..f04bef4 100644
--- a/graph/iterator/limit.go
+++ b/graph/iterator/limit.go
@@ -7,109 +7,79 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Limit{}
-
 // Limit iterator will stop iterating if certain a number of values were encountered.
-// Zero and negative limit values means no limit.
+// Zero and negative Limit values means no Limit.
 type Limit struct {
-	it *limit
-	graph.Iterator
-}
-
-func NewLimit(primaryIt graph.Iterator, limit int64) *Limit {
-	it := &Limit{
-		it: newLimit(graph.AsShape(primaryIt), limit),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Limit) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
+	limit int64
+	it    graph.IteratorShape
 }
 
-var _ graph.IteratorShapeCompat = &limit{}
-
-// Limit iterator will stop iterating if certain a number of values were encountered.
-// Zero and negative limit values means no limit.
-type limit struct {
-	limit     int64
-	primaryIt graph.IteratorShape
-}
-
-func newLimit(primaryIt graph.IteratorShape, max int64) *limit {
-	return &limit{
-		limit:     max,
-		primaryIt: primaryIt,
+func NewLimit(it graph.IteratorShape, max int64) *Limit {
+	return &Limit{
+		limit: max,
+		it:    it,
 	}
 }
 
-func (it *limit) Iterate() graph.Scanner {
-	return newLimitNext(it.primaryIt.Iterate(), it.limit)
-}
-
-func (it *limit) Lookup() graph.Index {
-	return newLimitContains(it.primaryIt.Lookup(), it.limit)
+func (it *Limit) Iterate() graph.Scanner {
+	return NewLimitNext(it.it.Iterate(), it.limit)
 }
 
-func (it *limit) AsLegacy() graph.Iterator {
-	it2 := &Limit{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
+func (it *Limit) Lookup() graph.Index {
+	return newLimitContains(it.it.Lookup(), it.limit)
 }
 
 // SubIterators returns a slice of the sub iterators.
-func (it *limit) SubIterators() []graph.IteratorShape {
-	return []graph.IteratorShape{it.primaryIt}
+func (it *Limit) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.it}
 }
 
-func (it *limit) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
-	optimizedPrimaryIt, optimized := it.primaryIt.Optimize(ctx)
-	if it.limit <= 0 { // no limit
-		return optimizedPrimaryIt, true
+func (it *Limit) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	nit, optimized := it.it.Optimize(ctx)
+	if it.limit <= 0 { // no Limit
+		return nit, true
 	}
-	it.primaryIt = optimizedPrimaryIt
+	it.it = nit
 	return it, optimized
 }
 
-func (it *limit) Stats(ctx context.Context) (graph.IteratorCosts, error) {
-	primaryStats, err := it.primaryIt.Stats(ctx)
-	if it.limit > 0 && primaryStats.Size.Size > it.limit {
-		primaryStats.Size.Size = it.limit
+func (it *Limit) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	st, err := it.it.Stats(ctx)
+	if it.limit > 0 && st.Size.Value > it.limit {
+		st.Size.Value = it.limit
 	}
-	return primaryStats, err
+	return st, err
 }
 
-func (it *limit) String() string {
+func (it *Limit) String() string {
 	return fmt.Sprintf("Limit(%d)", it.limit)
 }
 
 // Limit iterator will stop iterating if certain a number of values were encountered.
-// Zero and negative limit values means no limit.
+// Zero and negative Limit values means no Limit.
 type limitNext struct {
-	limit     int64
-	count     int64
-	primaryIt graph.Scanner
+	limit int64
+	count int64
+	it    graph.Scanner
 }
 
-func newLimitNext(primaryIt graph.Scanner, limit int64) *limitNext {
+func NewLimitNext(it graph.Scanner, limit int64) graph.Scanner {
 	return &limitNext{
-		limit:     limit,
-		primaryIt: primaryIt,
+		limit: limit,
+		it:    it,
 	}
 }
 
 func (it *limitNext) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+	it.it.TagResults(dst)
 }
 
-// Next advances the Limit iterator. It will stop iteration if limit was reached.
+// Next advances the Limit iterator. It will stop iteration if Limit was reached.
 func (it *limitNext) Next(ctx context.Context) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
-	if it.primaryIt.Next(ctx) {
+	if it.it.Next(ctx) {
 		it.count++
 		return true
 	}
@@ -117,20 +87,20 @@ func (it *limitNext) Next(ctx context.Context) bool {
 }
 
 func (it *limitNext) Err() error {
-	return it.primaryIt.Err()
+	return it.it.Err()
 }
 
 func (it *limitNext) Result() graph.Ref {
-	return it.primaryIt.Result()
+	return it.it.Result()
 }
 
 // NextPath checks whether there is another path. Will call primary iterator
-// if limit is not reached yet.
+// if Limit is not reached yet.
 func (it *limitNext) NextPath(ctx context.Context) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
-	if it.primaryIt.NextPath(ctx) {
+	if it.it.NextPath(ctx) {
 		it.count++
 		return true
 	}
@@ -140,7 +110,7 @@ func (it *limitNext) NextPath(ctx context.Context) bool {
 // Close closes the primary and all iterators.  It closes all subiterators
 // it can, but returns the first error it encounters.
 func (it *limitNext) Close() error {
-	return it.primaryIt.Close()
+	return it.it.Close()
 }
 
 func (it *limitNext) String() string {
@@ -148,37 +118,37 @@ func (it *limitNext) String() string {
 }
 
 // Limit iterator will stop iterating if certain a number of values were encountered.
-// Zero and negative limit values means no limit.
+// Zero and negative Limit values means no Limit.
 type limitContains struct {
-	limit     int64
-	count     int64
-	primaryIt graph.Index
+	limit int64
+	count int64
+	it    graph.Index
 }
 
-func newLimitContains(primaryIt graph.Index, limit int64) *limitContains {
+func newLimitContains(it graph.Index, limit int64) *limitContains {
 	return &limitContains{
-		limit:     limit,
-		primaryIt: primaryIt,
+		limit: limit,
+		it:    it,
 	}
 }
 
 func (it *limitContains) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+	it.it.TagResults(dst)
 }
 
 func (it *limitContains) Err() error {
-	return it.primaryIt.Err()
+	return it.it.Err()
 }
 
 func (it *limitContains) Result() graph.Ref {
-	return it.primaryIt.Result()
+	return it.it.Result()
 }
 
 func (it *limitContains) Contains(ctx context.Context, val graph.Ref) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
-	if it.primaryIt.Contains(ctx, val) {
+	if it.it.Contains(ctx, val) {
 		it.count++
 		return true
 	}
@@ -186,12 +156,12 @@ func (it *limitContains) Contains(ctx context.Context, val graph.Ref) bool {
 }
 
 // NextPath checks whether there is another path. Will call primary iterator
-// if limit is not reached yet.
+// if Limit is not reached yet.
 func (it *limitContains) NextPath(ctx context.Context) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
-	if it.primaryIt.NextPath(ctx) {
+	if it.it.NextPath(ctx) {
 		it.count++
 		return true
 	}
@@ -201,7 +171,7 @@ func (it *limitContains) NextPath(ctx context.Context) bool {
 // Close closes the primary and all iterators.  It closes all subiterators
 // it can, but returns the first error it encounters.
 func (it *limitContains) Close() error {
-	return it.primaryIt.Close()
+	return it.it.Close()
 }
 
 func (it *limitContains) String() string {
diff --git a/graph/iterator/linksto.go b/graph/iterator/linksto.go
index e43bb5a..ccbb8de 100644
--- a/graph/iterator/linksto.go
+++ b/graph/iterator/linksto.go
@@ -37,40 +37,10 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &LinksTo{}
-
 // A LinksTo has a reference back to the graph.QuadStore (to create the iterators
 // for each node) the subiterator, and the direction the iterator comes from.
 // `next_it` is the tempoarary iterator held per result in `primary_it`.
 type LinksTo struct {
-	it *linksTo
-	graph.Iterator
-}
-
-// Construct a new LinksTo iterator around a direction and a subiterator of
-// nodes.
-func NewLinksTo(qs graph.QuadIndexer, sub graph.Iterator, d quad.Direction) *LinksTo {
-	it := &LinksTo{
-		it: newLinksTo(qs, graph.AsShape(sub), d),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *LinksTo) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-// Return the direction under consideration.
-func (it *LinksTo) Direction() quad.Direction { return it.it.Direction() }
-
-var _ graph.IteratorShapeCompat = &linksTo{}
-
-// A LinksTo has a reference back to the graph.QuadStore (to create the iterators
-// for each node) the subiterator, and the direction the iterator comes from.
-// `next_it` is the tempoarary iterator held per result in `primary_it`.
-type linksTo struct {
 	qs      graph.QuadIndexer
 	primary graph.IteratorShape
 	dir     quad.Direction
@@ -79,8 +49,8 @@ type linksTo struct {
 
 // Construct a new LinksTo iterator around a direction and a subiterator of
 // nodes.
-func newLinksTo(qs graph.QuadIndexer, it graph.IteratorShape, d quad.Direction) *linksTo {
-	return &linksTo{
+func NewLinksTo(qs graph.QuadIndexer, it graph.IteratorShape, d quad.Direction) *LinksTo {
+	return &LinksTo{
 		qs:      qs,
 		primary: it,
 		dir:     d,
@@ -88,37 +58,31 @@ func newLinksTo(qs graph.QuadIndexer, it graph.IteratorShape, d quad.Direction)
 }
 
 // Return the direction under consideration.
-func (it *linksTo) Direction() quad.Direction { return it.dir }
+func (it *LinksTo) Direction() quad.Direction { return it.dir }
 
-func (it *linksTo) Iterate() graph.Scanner {
+func (it *LinksTo) Iterate() graph.Scanner {
 	return newLinksToNext(it.qs, it.primary.Iterate(), it.dir)
 }
 
-func (it *linksTo) Lookup() graph.Index {
+func (it *LinksTo) Lookup() graph.Index {
 	return newLinksToContains(it.qs, it.primary.Lookup(), it.dir)
 }
 
-func (it *linksTo) AsLegacy() graph.Iterator {
-	it2 := &LinksTo{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *linksTo) String() string {
+func (it *LinksTo) String() string {
 	return fmt.Sprintf("LinksTo(%v)", it.dir)
 }
 
 // Return a list containing only our subiterator.
-func (it *linksTo) SubIterators() []graph.IteratorShape {
+func (it *LinksTo) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.primary}
 }
 
 // Optimize the LinksTo, by replacing it if it can be.
-func (it *linksTo) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *LinksTo) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newPrimary, changed := it.primary.Optimize(ctx)
 	if changed {
 		it.primary = newPrimary
-		if IsNull2(it.primary) {
+		if IsNull(it.primary) {
 			return it.primary, true
 		}
 	}
@@ -126,7 +90,7 @@ func (it *linksTo) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 }
 
 // Return a guess as to how big or costly it is to next the iterator.
-func (it *linksTo) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *LinksTo) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	subitStats, err := it.primary.Stats(ctx)
 	// TODO(barakmich): These should really come from the quadstore itself
 	checkConstant := int64(1)
@@ -138,11 +102,11 @@ func (it *linksTo) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	}, err
 }
 
-func (it *linksTo) getSize(ctx context.Context) graph.Size {
-	if it.size.Size != 0 {
+func (it *LinksTo) getSize(ctx context.Context) graph.Size {
+	if it.size.Value != 0 {
 		return it.size
 	}
-	if fixed, ok := graph.AsLegacy(it.primary).(*Fixed); ok {
+	if fixed, ok := it.primary.(*Fixed); ok {
 		// get real sizes from sub iterators
 		var (
 			sz    int64
@@ -150,19 +114,18 @@ func (it *linksTo) getSize(ctx context.Context) graph.Size {
 		)
 		for _, v := range fixed.Values() {
 			sit := it.qs.QuadIterator(it.dir, v)
-			n, ex := sit.Size()
-			sit.Close()
-			sz += n
-			exact = exact && ex
+			st, _ := sit.Stats(ctx)
+			sz += st.Size.Value
+			exact = exact && st.Size.Exact
 		}
-		it.size.Size, it.size.Exact = sz, exact
+		it.size.Value, it.size.Exact = sz, exact
 		return it.size
 	}
 	// TODO(barakmich): It should really come from the quadstore itself
 	const fanoutFactor = 20
 	st, _ := it.primary.Stats(ctx)
-	st.Size.Size *= fanoutFactor
-	it.size.Size, it.size.Exact = st.Size.Size, false
+	st.Size.Value *= fanoutFactor
+	it.size.Value, it.size.Exact = st.Size.Value, false
 	return it.size
 }
 
@@ -185,7 +148,7 @@ func newLinksToNext(qs graph.QuadIndexer, it graph.Scanner, d quad.Direction) gr
 		qs:      qs,
 		primary: it,
 		dir:     d,
-		nextIt:  newNull().Iterate(),
+		nextIt:  NewNull().Iterate(),
 	}
 }
 
@@ -224,7 +187,7 @@ func (it *linksToNext) Next(ctx context.Context) bool {
 			return false
 		}
 		it.nextIt.Close()
-		it.nextIt = it.qs.QuadIterator(it.dir, it.primary.Result())
+		it.nextIt = it.qs.QuadIterator(it.dir, it.primary.Result()).Iterate()
 
 		// Continue -- return the first in the next set.
 	}
diff --git a/graph/iterator/materialize.go b/graph/iterator/materialize.go
index 204f088..5f24efc 100644
--- a/graph/iterator/materialize.go
+++ b/graph/iterator/materialize.go
@@ -30,79 +30,43 @@ type result struct {
 	tags map[string]graph.Ref
 }
 
-var _ graph.IteratorFuture = &Materialize{}
-
 type Materialize struct {
-	it *materialize
-	graph.Iterator
-}
-
-func NewMaterialize(sub graph.Iterator) *Materialize {
-	it := &Materialize{
-		it: newMaterialize(graph.AsShape(sub)),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func NewMaterializeWithSize(sub graph.Iterator, size int64) *Materialize {
-	it := &Materialize{
-		it: newMaterializeWithSize(graph.AsShape(sub), size),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Materialize) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = &materialize{}
-
-type materialize struct {
 	sub        graph.IteratorShape
 	expectSize int64
 }
 
-func newMaterialize(sub graph.IteratorShape) *materialize {
-	return newMaterializeWithSize(sub, 0)
+func NewMaterialize(sub graph.IteratorShape) *Materialize {
+	return NewMaterializeWithSize(sub, 0)
 }
 
-func newMaterializeWithSize(sub graph.IteratorShape, size int64) *materialize {
-	return &materialize{
+func NewMaterializeWithSize(sub graph.IteratorShape, size int64) *Materialize {
+	return &Materialize{
 		sub:        sub,
 		expectSize: size,
 	}
 }
 
-func (it *materialize) Iterate() graph.Scanner {
+func (it *Materialize) Iterate() graph.Scanner {
 	return newMaterializeNext(it.sub)
 }
 
-func (it *materialize) Lookup() graph.Index {
+func (it *Materialize) Lookup() graph.Index {
 	return newMaterializeContains(it.sub)
 }
 
-func (it *materialize) AsLegacy() graph.Iterator {
-	it2 := &Materialize{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *materialize) String() string {
+func (it *Materialize) String() string {
 	return "Materialize"
 }
 
-func (it *materialize) SubIterators() []graph.IteratorShape {
+func (it *Materialize) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.sub}
 }
 
-func (it *materialize) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Materialize) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newSub, changed := it.sub.Optimize(ctx)
 	if changed {
 		it.sub = newSub
-		if IsNull2(it.sub) {
+		if IsNull(it.sub) {
 			return it.sub, true
 		}
 	}
@@ -111,12 +75,12 @@ func (it *materialize) Optimize(ctx context.Context) (graph.IteratorShape, bool)
 
 // The entire point of Materialize is to amortize the cost by
 // putting it all up front.
-func (it *materialize) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Materialize) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	overhead := int64(2)
 	var size graph.Size
 	subitStats, err := it.sub.Stats(ctx)
 	if it.expectSize > 0 {
-		size = graph.Size{Size: it.expectSize, Exact: false}
+		size = graph.Size{Value: it.expectSize, Exact: false}
 	} else {
 		size = subitStats.Size
 	}
diff --git a/graph/iterator/not.go b/graph/iterator/not.go
index 156afe3..c0d3bac 100644
--- a/graph/iterator/not.go
+++ b/graph/iterator/not.go
@@ -6,76 +6,46 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Not{}
-
 // Not iterator acts like a complement for the primary iterator.
 // It will return all the vertices which are not part of the primary iterator.
 type Not struct {
-	it *not
-	graph.Iterator
-}
-
-func NewNot(primaryIt, allIt graph.Iterator) *Not {
-	it := &Not{
-		it: newNot(graph.AsShape(primaryIt), graph.AsShape(allIt)),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Not) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = (*not)(nil)
-
-// Not iterator acts like a complement for the primary iterator.
-// It will return all the vertices which are not part of the primary iterator.
-type not struct {
 	primary graph.IteratorShape
 	allIt   graph.IteratorShape
 }
 
-func newNot(primaryIt, allIt graph.IteratorShape) *not {
-	return &not{
+func NewNot(primaryIt, allIt graph.IteratorShape) *Not {
+	return &Not{
 		primary: primaryIt,
 		allIt:   allIt,
 	}
 }
 
-func (it *not) Iterate() graph.Scanner {
+func (it *Not) Iterate() graph.Scanner {
 	return newNotNext(it.primary.Lookup(), it.allIt.Iterate())
 }
 
-func (it *not) Lookup() graph.Index {
+func (it *Not) Lookup() graph.Index {
 	return newNotContains(it.primary.Lookup())
 }
 
-func (it *not) AsLegacy() graph.Iterator {
-	it2 := &Not{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // SubIterators returns a slice of the sub iterators.
 // The first iterator is the primary iterator, for which the complement
 // is generated.
-func (it *not) SubIterators() []graph.IteratorShape {
+func (it *Not) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.primary, it.allIt}
 }
 
-func (it *not) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Not) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	// TODO - consider wrapping the primary with a MaterializeIt
 	optimizedPrimaryIt, optimized := it.primary.Optimize(ctx)
 	if optimized {
 		it.primary = optimizedPrimaryIt
 	}
-	it.primary = newMaterialize(it.primary)
+	it.primary = NewMaterialize(it.primary)
 	return it, false
 }
 
-func (it *not) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Not) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	primaryStats, err := it.primary.Stats(ctx)
 	allStats, err2 := it.allIt.Stats(ctx)
 	if err == nil {
@@ -85,13 +55,13 @@ func (it *not) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 		NextCost:     allStats.NextCost + primaryStats.ContainsCost,
 		ContainsCost: primaryStats.ContainsCost,
 		Size: graph.Size{
-			Size:  allStats.Size.Size - primaryStats.Size.Size,
+			Value: allStats.Size.Value - primaryStats.Size.Value,
 			Exact: false,
 		},
 	}, err
 }
 
-func (it *not) String() string {
+func (it *Not) String() string {
 	return "Not"
 }
 
diff --git a/graph/iterator/or.go b/graph/iterator/or.go
index f3f4f23..d986367 100644
--- a/graph/iterator/or.go
+++ b/graph/iterator/or.go
@@ -27,50 +27,7 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Or{}
-
 type Or struct {
-	it *or
-	graph.Iterator
-}
-
-func NewOr(sub ...graph.Iterator) *Or {
-	in := make([]graph.IteratorShape, 0, len(sub))
-	for _, s := range sub {
-		in = append(in, graph.AsShape(s))
-	}
-	it := &Or{
-		it: newOr(in...),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func NewShortCircuitOr(sub ...graph.Iterator) *Or {
-	in := make([]graph.IteratorShape, 0, len(sub))
-	for _, s := range sub {
-		in = append(in, graph.AsShape(s))
-	}
-	it := &Or{
-		it: newShortCircuitOr(in...),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Or) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-// Add a subiterator to this Or graph.iterator. Order matters.
-func (it *Or) AddSubIterator(sub graph.Iterator) {
-	it.it.AddSubIterator(graph.AsShape(sub))
-}
-
-var _ graph.IteratorShapeCompat = &or{}
-
-type or struct {
 	isShortCircuiting bool
 	sub               []graph.IteratorShape
 	curInd            int
@@ -78,8 +35,8 @@ type or struct {
 	err               error
 }
 
-func newOr(sub ...graph.IteratorShape) *or {
-	it := &or{
+func NewOr(sub ...graph.IteratorShape) *Or {
+	it := &Or{
 		sub:    make([]graph.IteratorShape, 0, 20),
 		curInd: -1,
 	}
@@ -89,8 +46,8 @@ func newOr(sub ...graph.IteratorShape) *or {
 	return it
 }
 
-func newShortCircuitOr(sub ...graph.IteratorShape) *or {
-	it := &or{
+func NewShortCircuitOr(sub ...graph.IteratorShape) *Or {
+	it := &Or{
 		sub:               make([]graph.IteratorShape, 0, 20),
 		isShortCircuiting: true,
 		curInd:            -1,
@@ -101,7 +58,7 @@ func newShortCircuitOr(sub ...graph.IteratorShape) *or {
 	return it
 }
 
-func (it *or) Iterate() graph.Scanner {
+func (it *Or) Iterate() graph.Scanner {
 	sub := make([]graph.Scanner, 0, len(it.sub))
 	for _, s := range it.sub {
 		sub = append(sub, s.Iterate())
@@ -109,7 +66,7 @@ func (it *or) Iterate() graph.Scanner {
 	return newOrNext(sub, it.isShortCircuiting)
 }
 
-func (it *or) Lookup() graph.Index {
+func (it *Or) Lookup() graph.Index {
 	sub := make([]graph.Index, 0, len(it.sub))
 	for _, s := range it.sub {
 		sub = append(sub, s.Lookup())
@@ -117,30 +74,24 @@ func (it *or) Lookup() graph.Index {
 	return newOrContains(sub, it.isShortCircuiting)
 }
 
-func (it *or) AsLegacy() graph.Iterator {
-	it2 := &Or{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // Returns a list.List of the subiterators, in order. The returned slice must not be modified.
-func (it *or) SubIterators() []graph.IteratorShape {
+func (it *Or) SubIterators() []graph.IteratorShape {
 	return it.sub
 }
 
-func (it *or) String() string {
+func (it *Or) String() string {
 	return "Or"
 }
 
 // Add a subiterator to this Or graph.iterator. Order matters.
-func (it *or) AddSubIterator(sub graph.IteratorShape) {
+func (it *Or) AddSubIterator(sub graph.IteratorShape) {
 	it.sub = append(it.sub, sub)
 }
 
-func (it *or) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Or) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	old := it.SubIterators()
-	optIts := optimizeSubIterators2(ctx, old)
-	newOr := newOr()
+	optIts := optimizeSubIterators(ctx, old)
+	newOr := NewOr()
 	newOr.isShortCircuiting = it.isShortCircuiting
 
 	// Add the subiterators in order.
@@ -153,11 +104,11 @@ func (it *or) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 // Returns the approximate size of the Or graph.iterator. Because we're dealing
 // with a union, we know that the largest we can be is the sum of all the iterators,
 // or in the case of short-circuiting, the longest.
-func (it *or) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Or) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	ContainsCost := int64(0)
 	NextCost := int64(0)
 	Size := graph.Size{
-		Size:  0,
+		Value: 0,
 		Exact: true,
 	}
 	var last error
@@ -169,11 +120,11 @@ func (it *or) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 		NextCost += stats.NextCost
 		ContainsCost += stats.ContainsCost
 		if it.isShortCircuiting {
-			if Size.Size < stats.Size.Size {
+			if Size.Value < stats.Size.Value {
 				Size = stats.Size
 			}
 		} else {
-			Size.Size += stats.Size.Size
+			Size.Value += stats.Size.Value
 			Size.Exact = Size.Exact && stats.Size.Exact
 		}
 	}
@@ -286,8 +237,6 @@ func (it *orNext) Close() error {
 	return err
 }
 
-var _ graph.Iterator = &Or{}
-
 type orContains struct {
 	shortCircuit bool
 	sub          []graph.Index
diff --git a/graph/iterator/query_shape.go b/graph/iterator/query_shape.go
index e33849f..a8f08b2 100644
--- a/graph/iterator/query_shape.go
+++ b/graph/iterator/query_shape.go
@@ -43,7 +43,7 @@ type queryShape struct {
 	hasaDirs []quad.Direction
 }
 
-func OutputQueryShapeForIterator(it graph.Iterator, qs graph.Namer, outputMap map[string]interface{}) {
+func OutputQueryShapeForIterator(it graph.IteratorShape, qs graph.Namer, outputMap map[string]interface{}) {
 	s := &queryShape{
 		qs:     qs,
 		nodeID: 1,
@@ -106,19 +106,19 @@ func (s *queryShape) StealNode(left *Node, right *Node) {
 	}
 }
 
-func (s *queryShape) MakeNode(it graph.Iterator) *Node {
+func (s *queryShape) MakeNode(it graph.IteratorShape) *Node {
 	n := Node{ID: s.nodeID}
 	return s.makeNode(&n, it)
 }
-func (s *queryShape) makeNode(n *Node, it graph.Iterator) *Node {
-	if tg, ok := it.(graph.Tagger); ok {
+func (s *queryShape) makeNode(n *Node, it graph.IteratorShape) *Node {
+	if tg, ok := it.(graph.TaggerShape); ok {
 		for _, tag := range tg.Tags() {
 			n.Tags = append(n.Tags, tag)
 		}
 		for k := range tg.FixedTags() {
 			n.Tags = append(n.Tags, k)
 		}
-		if sub := tg.SubIterators(); len(sub) == 1 {
+		if sub := it.SubIterators(); len(sub) == 1 {
 			return s.makeNode(n, sub[0])
 		}
 	}
@@ -142,9 +142,9 @@ func (s *queryShape) makeNode(n *Node, it graph.Iterator) *Node {
 		}
 	case *HasA:
 		hasa := it
-		s.PushHasa(n.ID, hasa.it.dir)
+		s.PushHasa(n.ID, hasa.dir)
 		s.nodeID++
-		newNode := s.MakeNode(graph.AsLegacy(hasa.it.primary))
+		newNode := s.MakeNode(hasa.primary)
 		s.AddNode(newNode)
 		s.RemoveHasa()
 	case *Or:
@@ -162,17 +162,17 @@ func (s *queryShape) makeNode(n *Node, it graph.Iterator) *Node {
 		n.IsLinkNode = true
 		lto := it
 		s.nodeID++
-		newNode := s.MakeNode(graph.AsLegacy(lto.it.primary))
+		newNode := s.MakeNode(lto.primary)
 		hasaID, hasaDir := s.LastHasa()
-		if (hasaDir == quad.Subject && lto.it.dir == quad.Object) ||
-			(hasaDir == quad.Object && lto.it.dir == quad.Subject) {
+		if (hasaDir == quad.Subject && lto.dir == quad.Object) ||
+			(hasaDir == quad.Object && lto.dir == quad.Subject) {
 			s.AddNode(newNode)
 			if hasaDir == quad.Subject {
 				s.AddLink(&Link{hasaID, newNode.ID, 0, n.ID})
 			} else {
 				s.AddLink(&Link{newNode.ID, hasaID, 0, n.ID})
 			}
-		} else if _, ok := graph.AsLegacy(lto.it.primary).(*Fixed); ok {
+		} else if _, ok := lto.primary.(*Fixed); ok {
 			s.StealNode(n, newNode)
 		} else {
 			s.AddNode(newNode)
diff --git a/graph/iterator/recursive.go b/graph/iterator/recursive.go
index 7351251..16975bf 100644
--- a/graph/iterator/recursive.go
+++ b/graph/iterator/recursive.go
@@ -8,16 +8,8 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &Recursive{}
-
 const recursiveBaseTag = "__base_recursive"
 
-// Recursive iterator takes a base iterator and a morphism to be applied recursively, for each result.
-type Recursive struct {
-	it *recursive
-	graph.Iterator
-}
-
 type seenAt struct {
 	depth int
 	tags  map[string]graph.Ref
@@ -26,69 +18,42 @@ type seenAt struct {
 
 var DefaultMaxRecursiveSteps = 50
 
-func NewRecursive(sub graph.Iterator, morphism Morphism, maxDepth int) *Recursive {
-	it := &Recursive{
-		it: newRecursive(graph.AsShape(sub), func(it graph.IteratorShape) graph.IteratorShape {
-			return graph.AsShape(morphism(graph.AsLegacy(it)))
-		}, maxDepth),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Recursive) AddDepthTag(s string) {
-	it.it.AddDepthTag(s)
-}
-
-func (it *Recursive) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = &recursive{}
-
 // Recursive iterator takes a base iterator and a morphism to be applied recursively, for each result.
-type recursive struct {
+type Recursive struct {
 	subIt     graph.IteratorShape
-	morphism  Morphism2
+	morphism  Morphism
 	maxDepth  int
 	depthTags []string
 }
 
-func newRecursive(it graph.IteratorShape, morphism Morphism2, maxDepth int) *recursive {
+func NewRecursive(it graph.IteratorShape, morphism Morphism, maxDepth int) *Recursive {
 	if maxDepth == 0 {
 		maxDepth = DefaultMaxRecursiveSteps
 	}
-	return &recursive{
+	return &Recursive{
 		subIt:    it,
 		morphism: morphism,
 		maxDepth: maxDepth,
 	}
 }
 
-func (it *recursive) Iterate() graph.Scanner {
+func (it *Recursive) Iterate() graph.Scanner {
 	return newRecursiveNext(it.subIt.Iterate(), it.morphism, it.maxDepth, it.depthTags)
 }
 
-func (it *recursive) Lookup() graph.Index {
+func (it *Recursive) Lookup() graph.Index {
 	return newRecursiveContains(newRecursiveNext(it.subIt.Iterate(), it.morphism, it.maxDepth, it.depthTags))
 }
 
-func (it *recursive) AsLegacy() graph.Iterator {
-	it2 := &Recursive{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *recursive) AddDepthTag(s string) {
+func (it *Recursive) AddDepthTag(s string) {
 	it.depthTags = append(it.depthTags, s)
 }
 
-func (it *recursive) SubIterators() []graph.IteratorShape {
+func (it *Recursive) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.subIt}
 }
 
-func (it *recursive) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Recursive) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newIt, optimized := it.subIt.Optimize(ctx)
 	if optimized {
 		it.subIt = newIt
@@ -96,8 +61,8 @@ func (it *recursive) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, false
 }
 
-func (it *recursive) Stats(ctx context.Context) (graph.IteratorCosts, error) {
-	base := newFixed()
+func (it *Recursive) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	base := NewFixed()
 	base.Add(Int64Node(20))
 	fanoutit := it.morphism(base)
 	fanoutStats, err := fanoutit.Stats(ctx)
@@ -105,18 +70,18 @@ func (it *recursive) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	if err == nil {
 		err = err2
 	}
-	size := int64(math.Pow(float64(subitStats.Size.Size*fanoutStats.Size.Size), 5))
+	size := int64(math.Pow(float64(subitStats.Size.Value*fanoutStats.Size.Value), 5))
 	return graph.IteratorCosts{
 		NextCost:     subitStats.NextCost + fanoutStats.NextCost,
 		ContainsCost: (subitStats.NextCost+fanoutStats.NextCost)*(size/10) + subitStats.ContainsCost,
 		Size: graph.Size{
-			Size:  size,
+			Value: size,
 			Exact: false,
 		},
 	}, err
 }
 
-func (it *recursive) String() string {
+func (it *Recursive) String() string {
 	return "Recursive"
 }
 
@@ -126,7 +91,7 @@ type recursiveNext struct {
 	result seenAt
 	err    error
 
-	morphism      Morphism2
+	morphism      Morphism
 	seen          map[interface{}]seenAt
 	nextIt        graph.Scanner
 	depth         int
@@ -136,10 +101,10 @@ type recursiveNext struct {
 	containsValue graph.Ref
 	depthTags     []string
 	depthCache    []graph.Ref
-	baseIt        *fixed
+	baseIt        *Fixed
 }
 
-func newRecursiveNext(it graph.Scanner, morphism Morphism2, maxDepth int, depthTags []string) *recursiveNext {
+func newRecursiveNext(it graph.Scanner, morphism Morphism, maxDepth int, depthTags []string) *recursiveNext {
 	return &recursiveNext{
 		subIt:     it,
 		morphism:  morphism,
@@ -148,7 +113,7 @@ func newRecursiveNext(it graph.Scanner, morphism Morphism2, maxDepth int, depthT
 
 		seen:    make(map[interface{}]seenAt),
 		nextIt:  &Null{},
-		baseIt:  newFixed(),
+		baseIt:  NewFixed(),
 		pathMap: make(map[interface{}][]map[string]graph.Ref),
 	}
 }
@@ -198,12 +163,12 @@ func (it *recursiveNext) Next(ctx context.Context) bool {
 				return false
 			}
 			it.depth++
-			it.baseIt = newFixed(it.depthCache...)
+			it.baseIt = NewFixed(it.depthCache...)
 			it.depthCache = nil
 			if it.nextIt != nil {
 				it.nextIt.Close()
 			}
-			it.nextIt = it.morphism(TagShape(it.baseIt, recursiveBaseTag)).Iterate()
+			it.nextIt = it.morphism(Tag(it.baseIt, recursiveBaseTag)).Iterate()
 			continue
 		}
 		val := it.nextIt.Result()
diff --git a/graph/iterator/regex.go b/graph/iterator/regex.go
index b9b56dd..de0f12b 100644
--- a/graph/iterator/regex.go
+++ b/graph/iterator/regex.go
@@ -21,7 +21,7 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-func newRegex(qs graph.Namer, sub graph.Iterator, re *regexp.Regexp, refs bool) graph.Iterator {
+func newRegex(qs graph.Namer, sub graph.IteratorShape, re *regexp.Regexp, refs bool) graph.IteratorShape {
 	return NewValueFilter(qs, sub, func(v quad.Value) (bool, error) {
 		switch v := v.(type) {
 		case quad.String:
@@ -48,7 +48,7 @@ func newRegex(qs graph.Namer, sub graph.Iterator, re *regexp.Regexp, refs bool)
 // subiterator. It works similarly to gremlin's filter{it.matches('exp')},
 // reducing the iterator set to values whose string representation passes a
 // regular expression test.
-func NewRegex(sub graph.Iterator, re *regexp.Regexp, qs graph.Namer) graph.Iterator {
+func NewRegex(sub graph.IteratorShape, re *regexp.Regexp, qs graph.Namer) graph.IteratorShape {
 	return newRegex(qs, sub, re, false)
 }
 
@@ -65,6 +65,6 @@ func NewRegex(sub graph.Iterator, re *regexp.Regexp, qs graph.Namer) graph.Itera
 //
 // The right way is to explicitly link graph nodes and query them by this relation:
 // 	<http://example.org/page/foo> <type> <http://example.org/page>
-func NewRegexWithRefs(sub graph.Iterator, re *regexp.Regexp, qs graph.Namer) graph.Iterator {
+func NewRegexWithRefs(sub graph.IteratorShape, re *regexp.Regexp, qs graph.Namer) graph.IteratorShape {
 	return newRegex(qs, sub, re, true)
 }
diff --git a/graph/iterator/resolver.go b/graph/iterator/resolver.go
index b9b4ee0..8f40b80 100644
--- a/graph/iterator/resolver.go
+++ b/graph/iterator/resolver.go
@@ -22,41 +22,16 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &Resolver{}
-
 // A Resolver iterator consists of it's order, an index (where it is in the,
 // process of iterating) and a store to resolve values from.
 type Resolver struct {
-	it *resolver
-	graph.Iterator
-}
-
-// Creates a new Resolver iterator.
-func NewResolver(qs graph.QuadStore, nodes ...quad.Value) *Resolver {
-	it := &Resolver{
-		it: newResolver(qs, nodes...),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Resolver) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = (*resolver)(nil)
-
-// A Resolver iterator consists of it's order, an index (where it is in the,
-// process of iterating) and a store to resolve values from.
-type resolver struct {
 	qs    graph.QuadStore
 	order []quad.Value
 }
 
 // Creates a new Resolver iterator.
-func newResolver(qs graph.QuadStore, nodes ...quad.Value) *resolver {
-	it := &resolver{
+func NewResolver(qs graph.QuadStore, nodes ...quad.Value) *Resolver {
+	it := &Resolver{
 		qs:    qs,
 		order: make([]quad.Value, len(nodes)),
 	}
@@ -64,44 +39,38 @@ func newResolver(qs graph.QuadStore, nodes ...quad.Value) *resolver {
 	return it
 }
 
-func (it *resolver) Iterate() graph.Scanner {
+func (it *Resolver) Iterate() graph.Scanner {
 	return newResolverNext(it.qs, it.order)
 }
 
-func (it *resolver) Lookup() graph.Index {
+func (it *Resolver) Lookup() graph.Index {
 	return newResolverContains(it.qs, it.order)
 }
 
-func (it *resolver) AsLegacy() graph.Iterator {
-	it2 := &Resolver{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *resolver) String() string {
+func (it *Resolver) String() string {
 	return fmt.Sprintf("Resolver(%v)", it.order)
 }
 
-func (it *resolver) SubIterators() []graph.IteratorShape {
+func (it *Resolver) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
 // Returns a Null iterator if it's empty so that upstream iterators can optimize it
 // away, otherwise there is no optimization.
-func (it *resolver) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Resolver) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	if len(it.order) == 0 {
-		return newNull(), true
+		return NewNull(), true
 	}
 	return it, false
 }
 
-func (it *resolver) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Resolver) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	return graph.IteratorCosts{
 		// Next is (presumably) O(1) from store
 		NextCost:     1,
 		ContainsCost: 1,
 		Size: graph.Size{
-			Size:  int64(len(it.order)),
+			Value: int64(len(it.order)),
 			Exact: true,
 		},
 	}, nil
diff --git a/graph/iterator/save.go b/graph/iterator/save.go
index 1d240fe..ced39a7 100644
--- a/graph/iterator/save.go
+++ b/graph/iterator/save.go
@@ -8,114 +8,55 @@ import (
 )
 
 var (
-	_ graph.IteratorFuture = (*Save)(nil)
-	_ graph.Tagger         = (*Save)(nil)
+	_ graph.TaggerBase = (*Save)(nil)
 )
 
-func Tag(it graph.Iterator, tag string) graph.Iterator {
-	if s, ok := it.(graph.Tagger); ok {
-		s.AddTags(tag)
-		return s
-	} else if s, ok := graph.AsShape(it).(graph.TaggerShape); ok {
-		s.AddTags(tag)
-		return graph.AsLegacy(s)
-	}
-	return NewSave(it, tag)
-}
-
-func TagShape(it graph.IteratorShape, tag string) graph.IteratorShape {
+func Tag(it graph.IteratorShape, tag string) graph.IteratorShape {
 	if s, ok := it.(graph.TaggerShape); ok {
 		s.AddTags(tag)
 		return s
-	} else if s, ok := graph.AsLegacy(it).(graph.Tagger); ok {
+	} else if s, ok := it.(graph.TaggerShape); ok {
 		s.AddTags(tag)
-		return graph.AsShape(s)
-	}
-	return newSave(it, tag)
-}
-
-func NewSave(on graph.Iterator, tags ...string) *Save {
-	it := &Save{
-		it: newSave(graph.AsShape(on), tags...),
+		return s
 	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-type Save struct {
-	it *save
-	graph.Iterator
-}
-
-func (it *Save) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-// Add a tag to the iterator.
-func (it *Save) AddTags(tag ...string) {
-	it.it.AddTags(tag...)
-}
-
-func (it *Save) AddFixedTag(tag string, value graph.Ref) {
-	it.it.AddFixedTag(tag, value)
-}
-
-// Tags returns the tags held in the tagger. The returned value must not be mutated.
-func (it *Save) Tags() []string {
-	return it.it.Tags()
-}
-
-// Fixed returns the fixed tags held in the tagger. The returned value must not be mutated.
-func (it *Save) FixedTags() map[string]graph.Ref {
-	return it.it.FixedTags()
-}
-
-func (it *Save) CopyFromTagger(st graph.TaggerBase) {
-	it.it.CopyFromTagger(st)
+	return NewSave(it, tag)
 }
 
 var (
-	_ graph.IteratorShapeCompat = (*save)(nil)
-	_ graph.TaggerShape         = (*save)(nil)
+	_ graph.IteratorShape = (*Save)(nil)
+	_ graph.TaggerShape   = (*Save)(nil)
 )
 
-func newSave(on graph.IteratorShape, tags ...string) *save {
-	s := &save{it: on}
+func NewSave(on graph.IteratorShape, tags ...string) *Save {
+	s := &Save{it: on}
 	s.AddTags(tags...)
 	return s
 }
 
-type save struct {
+type Save struct {
 	it        graph.IteratorShape
 	tags      []string
 	fixedTags map[string]graph.Ref
 }
 
-func (it *save) Iterate() graph.Scanner {
+func (it *Save) Iterate() graph.Scanner {
 	return newSaveNext(it.it.Iterate(), it.tags, it.fixedTags)
 }
 
-func (it *save) Lookup() graph.Index {
+func (it *Save) Lookup() graph.Index {
 	return newSaveContains(it.it.Lookup(), it.tags, it.fixedTags)
 }
 
-func (it *save) AsLegacy() graph.Iterator {
-	it2 := &Save{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *save) String() string {
+func (it *Save) String() string {
 	return fmt.Sprintf("Save(%v, %v)", it.tags, it.fixedTags)
 }
 
 // Add a tag to the iterator.
-func (it *save) AddTags(tag ...string) {
+func (it *Save) AddTags(tag ...string) {
 	it.tags = append(it.tags, tag...)
 }
 
-func (it *save) AddFixedTag(tag string, value graph.Ref) {
+func (it *Save) AddFixedTag(tag string, value graph.Ref) {
 	if it.fixedTags == nil {
 		it.fixedTags = make(map[string]graph.Ref)
 	}
@@ -123,16 +64,16 @@ func (it *save) AddFixedTag(tag string, value graph.Ref) {
 }
 
 // Tags returns the tags held in the tagger. The returned value must not be mutated.
-func (it *save) Tags() []string {
+func (it *Save) Tags() []string {
 	return it.tags
 }
 
 // Fixed returns the fixed tags held in the tagger. The returned value must not be mutated.
-func (it *save) FixedTags() map[string]graph.Ref {
+func (it *Save) FixedTags() map[string]graph.Ref {
 	return it.fixedTags
 }
 
-func (it *save) CopyFromTagger(st graph.TaggerBase) {
+func (it *Save) CopyFromTagger(st graph.TaggerBase) {
 	it.tags = append(it.tags, st.Tags()...)
 
 	fixed := st.FixedTags()
@@ -147,11 +88,11 @@ func (it *save) CopyFromTagger(st graph.TaggerBase) {
 	}
 }
 
-func (it *save) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Save) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	return it.it.Stats(ctx)
 }
 
-func (it *save) Optimize(ctx context.Context) (nit graph.IteratorShape, no bool) {
+func (it *Save) Optimize(ctx context.Context) (nit graph.IteratorShape, no bool) {
 	sub, ok := it.it.Optimize(ctx)
 	if len(it.tags) == 0 && len(it.fixedTags) == 0 {
 		return sub, true
@@ -159,19 +100,16 @@ func (it *save) Optimize(ctx context.Context) (nit graph.IteratorShape, no bool)
 	if st, ok2 := sub.(graph.TaggerShape); ok2 {
 		st.CopyFromTagger(it)
 		return st, true
-	} else if st, ok2 := graph.AsLegacy(sub).(graph.Tagger); ok2 {
-		st.CopyFromTagger(it)
-		return graph.AsShape(st), true
 	}
 	if !ok {
 		return it, false
 	}
-	s := newSave(sub)
+	s := NewSave(sub)
 	s.CopyFromTagger(it)
 	return s, true
 }
 
-func (it *save) SubIterators() []graph.IteratorShape {
+func (it *Save) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.it}
 }
 
diff --git a/graph/iterator/skip.go b/graph/iterator/skip.go
index e0eca02..6fcd2b3 100644
--- a/graph/iterator/skip.go
+++ b/graph/iterator/skip.go
@@ -7,62 +7,33 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Skip{}
-
 // Skip iterator will skip certain number of values from primary iterator.
 type Skip struct {
-	it *skip
-	graph.Iterator
-}
-
-func NewSkip(primaryIt graph.Iterator, skip int64) *Skip {
-	it := &Skip{
-		it: newSkip(graph.AsShape(primaryIt), skip),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Skip) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = &skip{}
-
-// Skip iterator will skip certain number of values from primary iterator.
-type skip struct {
 	skip      int64
 	primaryIt graph.IteratorShape
 }
 
-func newSkip(primaryIt graph.IteratorShape, off int64) *skip {
-	return &skip{
+func NewSkip(primaryIt graph.IteratorShape, off int64) *Skip {
+	return &Skip{
 		skip:      off,
 		primaryIt: primaryIt,
 	}
 }
 
-func (it *skip) Iterate() graph.Scanner {
+func (it *Skip) Iterate() graph.Scanner {
 	return newSkipNext(it.primaryIt.Iterate(), it.skip)
 }
 
-func (it *skip) Lookup() graph.Index {
+func (it *Skip) Lookup() graph.Index {
 	return newSkipContains(it.primaryIt.Lookup(), it.skip)
 }
 
-func (it *skip) AsLegacy() graph.Iterator {
-	it2 := &Skip{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // SubIterators returns a slice of the sub iterators.
-func (it *skip) SubIterators() []graph.IteratorShape {
+func (it *Skip) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.primaryIt}
 }
 
-func (it *skip) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Skip) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	optimizedPrimaryIt, optimized := it.primaryIt.Optimize(ctx)
 	if it.skip == 0 { // nothing to skip
 		return optimizedPrimaryIt, true
@@ -71,18 +42,18 @@ func (it *skip) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, optimized
 }
 
-func (it *skip) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Skip) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	primaryStats, err := it.primaryIt.Stats(ctx)
 	if primaryStats.Size.Exact {
-		primaryStats.Size.Size -= it.skip
-		if primaryStats.Size.Size < 0 {
-			primaryStats.Size.Size = 0
+		primaryStats.Size.Value -= it.skip
+		if primaryStats.Size.Value < 0 {
+			primaryStats.Size.Value = 0
 		}
 	}
 	return primaryStats, err
 }
 
-func (it *skip) String() string {
+func (it *Skip) String() string {
 	return fmt.Sprintf("Skip(%d)", it.skip)
 }
 
diff --git a/graph/iterator/sort.go b/graph/iterator/sort.go
index e643c33..35ee336 100644
--- a/graph/iterator/sort.go
+++ b/graph/iterator/sort.go
@@ -7,57 +7,31 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Sort{}
-
 // Sort iterator orders values from it's subiterator.
 type Sort struct {
-	it *sortIt
-	graph.Iterator
+	namer graph.Namer
+	subIt graph.IteratorShape
 }
 
 // NewSort creates a new Sort iterator.
 // TODO(dennwc): This iterator must not be used inside And: it may be moved to a Contains branch and won't do anything.
 //               We should make And/Intersect account for this.
-func NewSort(namer graph.Namer, it graph.Iterator) *Sort {
-	return &Sort{
-		it: newSort(namer, graph.AsShape(it)),
-	}
+func NewSort(namer graph.Namer, subIt graph.IteratorShape) *Sort {
+	return &Sort{namer, subIt}
 }
 
-// AsShape returns Sort's underlying iterator shape
-func (it *Sort) AsShape() graph.IteratorShape {
-	return it.it
-}
-
-type sortIt struct {
-	namer graph.Namer
-	subIt graph.IteratorShape
-}
-
-var _ graph.IteratorShapeCompat = (*sortIt)(nil)
-
-func newSort(namer graph.Namer, subIt graph.IteratorShape) *sortIt {
-	return &sortIt{namer, subIt}
-}
-
-func (it *sortIt) Iterate() graph.Scanner {
+func (it *Sort) Iterate() graph.Scanner {
 	return newSortNext(it.namer, it.subIt.Iterate())
 }
 
-func (it *sortIt) AsLegacy() graph.Iterator {
-	it2 := &Sort{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *sortIt) Lookup() graph.Index {
+func (it *Sort) Lookup() graph.Index {
 	// TODO(dennwc): Lookup doesn't need any sorting. Using it this way is a bug in the optimizer.
 	//               But instead of failing here, let still allow the query to execute. It won't be sorted,
 	//               but it will work at least. Later consider changing returning an error here.
 	return it.subIt.Lookup()
 }
 
-func (it *sortIt) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Sort) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newIt, optimized := it.subIt.Optimize(ctx)
 	if optimized {
 		it.subIt = newIt
@@ -65,25 +39,25 @@ func (it *sortIt) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, false
 }
 
-func (it *sortIt) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Sort) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	subStats, err := it.subIt.Stats(ctx)
 	return graph.IteratorCosts{
 		// TODO(dennwc): better cost calculation; we probably need an InitCost defined in graph.IteratorCosts
 		NextCost:     subStats.NextCost * 2,
 		ContainsCost: subStats.ContainsCost,
 		Size: graph.Size{
-			Size:  subStats.Size.Size,
+			Value: subStats.Size.Value,
 			Exact: true,
 		},
 	}, err
 }
 
-func (it *sortIt) String() string {
+func (it *Sort) String() string {
 	return "Sort"
 }
 
 // SubIterators returns a slice of the sub iterators.
-func (it *sortIt) SubIterators() []graph.IteratorShape {
+func (it *Sort) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.subIt}
 }
 
diff --git a/graph/iterator/unique.go b/graph/iterator/unique.go
index f640328..c4ebd9e 100644
--- a/graph/iterator/unique.go
+++ b/graph/iterator/unique.go
@@ -6,61 +6,32 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = &Unique{}
-
 // Unique iterator removes duplicate values from it's subiterator.
 type Unique struct {
-	it *unique
-	graph.Iterator
-}
-
-func NewUnique(subIt graph.Iterator) *Unique {
-	it := &Unique{
-		it: newUnique(graph.AsShape(subIt)),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Unique) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = (*unique)(nil)
-
-// Unique iterator removes duplicate values from it's subiterator.
-type unique struct {
 	subIt graph.IteratorShape
 }
 
-func newUnique(subIt graph.IteratorShape) *unique {
-	return &unique{
+func NewUnique(subIt graph.IteratorShape) *Unique {
+	return &Unique{
 		subIt: subIt,
 	}
 }
 
-func (it *unique) Iterate() graph.Scanner {
+func (it *Unique) Iterate() graph.Scanner {
 	return newUniqueNext(it.subIt.Iterate())
 }
 
-func (it *unique) Lookup() graph.Index {
+func (it *Unique) Lookup() graph.Index {
 	return newUniqueContains(it.subIt.Lookup())
 }
 
-func (it *unique) AsLegacy() graph.Iterator {
-	it2 := &Unique{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
 // SubIterators returns a slice of the sub iterators. The first iterator is the
 // primary iterator, for which the complement is generated.
-func (it *unique) SubIterators() []graph.IteratorShape {
+func (it *Unique) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.subIt}
 }
 
-func (it *unique) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Unique) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newIt, optimized := it.subIt.Optimize(ctx)
 	if optimized {
 		it.subIt = newIt
@@ -70,19 +41,19 @@ func (it *unique) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 
 const uniquenessFactor = 2
 
-func (it *unique) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Unique) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	subStats, err := it.subIt.Stats(ctx)
 	return graph.IteratorCosts{
 		NextCost:     subStats.NextCost * uniquenessFactor,
 		ContainsCost: subStats.ContainsCost,
 		Size: graph.Size{
-			Size:  subStats.Size.Size / uniquenessFactor,
+			Value: subStats.Size.Value / uniquenessFactor,
 			Exact: false,
 		},
 	}, err
 }
 
-func (it *unique) String() string {
+func (it *Unique) String() string {
 	return "Unique"
 }
 
diff --git a/graph/iterator/value_comparison.go b/graph/iterator/value_comparison.go
index 6a309c7..970fe37 100644
--- a/graph/iterator/value_comparison.go
+++ b/graph/iterator/value_comparison.go
@@ -59,7 +59,7 @@ const (
 	// Why no Equals? Because that's usually an AndIterator.
 )
 
-func NewComparison(sub graph.Iterator, op Operator, val quad.Value, qs graph.Namer) graph.Iterator {
+func NewComparison(sub graph.IteratorShape, op Operator, val quad.Value, qs graph.Namer) graph.IteratorShape {
 	return NewValueFilter(qs, sub, func(qval quad.Value) (bool, error) {
 		switch cVal := val.(type) {
 		case quad.Int:
diff --git a/graph/iterator/value_filter.go b/graph/iterator/value_filter.go
index a678c11..45bdb0e 100644
--- a/graph/iterator/value_filter.go
+++ b/graph/iterator/value_filter.go
@@ -21,70 +21,42 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &ValueFilter{}
-
-type ValueFilter struct {
-	it *valueFilter
-	graph.Iterator
-}
-
 type ValueFilterFunc func(quad.Value) (bool, error)
 
-func NewValueFilter(qs graph.Namer, sub graph.Iterator, filter ValueFilterFunc) *ValueFilter {
-	it := &ValueFilter{
-		it: newValueFilter(qs, graph.AsShape(sub), filter),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *ValueFilter) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = (*valueFilter)(nil)
-
-type valueFilter struct {
+type ValueFilter struct {
 	sub    graph.IteratorShape
 	filter ValueFilterFunc
 	qs     graph.Namer
 }
 
-func newValueFilter(qs graph.Namer, sub graph.IteratorShape, filter ValueFilterFunc) *valueFilter {
-	return &valueFilter{
+func NewValueFilter(qs graph.Namer, sub graph.IteratorShape, filter ValueFilterFunc) *ValueFilter {
+	return &ValueFilter{
 		sub:    sub,
 		qs:     qs,
 		filter: filter,
 	}
 }
 
-func (it *valueFilter) Iterate() graph.Scanner {
+func (it *ValueFilter) Iterate() graph.Scanner {
 	return newValueFilterNext(it.qs, it.sub.Iterate(), it.filter)
 }
 
-func (it *valueFilter) Lookup() graph.Index {
+func (it *ValueFilter) Lookup() graph.Index {
 	return newValueFilterContains(it.qs, it.sub.Lookup(), it.filter)
 }
 
-func (it *valueFilter) AsLegacy() graph.Iterator {
-	it2 := &ValueFilter{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *valueFilter) SubIterators() []graph.IteratorShape {
+func (it *ValueFilter) SubIterators() []graph.IteratorShape {
 	return []graph.IteratorShape{it.sub}
 }
 
-func (it *valueFilter) String() string {
+func (it *ValueFilter) String() string {
 	return "ValueFilter"
 }
 
 // There's nothing to optimize, locally, for a value-comparison iterator.
 // Replace the underlying iterator if need be.
 // potentially replace it.
-func (it *valueFilter) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *ValueFilter) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	newSub, changed := it.sub.Optimize(ctx)
 	if changed {
 		it.sub = newSub
@@ -94,9 +66,9 @@ func (it *valueFilter) Optimize(ctx context.Context) (graph.IteratorShape, bool)
 
 // We're only as expensive as our subiterator.
 // Again, optimized value comparison iterators should do better.
-func (it *valueFilter) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *ValueFilter) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	st, err := it.sub.Stats(ctx)
-	st.Size.Size = st.Size.Size/2 + 1
+	st.Size.Value = st.Size.Value/2 + 1
 	st.Size.Exact = false
 	return st, err
 }
diff --git a/graph/kv/all_iterator.go b/graph/kv/all_iterator.go
index d6ccb2d..2ca968d 100644
--- a/graph/kv/all_iterator.go
+++ b/graph/kv/all_iterator.go
@@ -22,64 +22,34 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.IteratorFuture = &AllIterator{}
-
-type AllIterator struct {
-	it *allIterator
-	graph.Iterator
-}
-
 type constraint struct {
 	dir quad.Direction
 	val Int64Value
 }
 
-func NewAllIterator(nodes bool, qs *QuadStore, cons *constraint) *AllIterator {
-	it := &AllIterator{
-		it: newAllIterator(nodes, qs, cons),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *AllIterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-func (it *AllIterator) Sorted() bool { return false }
-
-var _ graph.IteratorShapeCompat = &allIterator{}
-
 type allIterator struct {
-	nodes bool
 	qs    *QuadStore
+	nodes bool
 	cons  *constraint
 }
 
-func newAllIterator(nodes bool, qs *QuadStore, cons *constraint) *allIterator {
+func (qs *QuadStore) newAllIterator(nodes bool, cons *constraint) *allIterator {
 	if nodes && cons != nil {
 		panic("cannot use a kv all iterator across nodes with a constraint")
 	}
 	return &allIterator{
-		nodes: nodes,
 		qs:    qs,
+		nodes: nodes,
 		cons:  cons,
 	}
 }
 
 func (it *allIterator) Iterate() graph.Scanner {
-	return newAllIteratorNext(it.nodes, it.qs, it.cons)
+	return it.qs.newAllIteratorNext(it.nodes, it.cons)
 }
 
 func (it *allIterator) Lookup() graph.Index {
-	return newAllIteratorContains(it.nodes, it.qs, it.cons)
-}
-
-func (it *allIterator) AsLegacy() graph.Iterator {
-	it2 := &AllIterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
+	return it.qs.newAllIteratorContains(it.nodes, it.cons)
 }
 
 // No subiterators.
@@ -106,7 +76,7 @@ func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 		ContainsCost: 1,
 		NextCost:     2,
 		Size: graph.Size{
-			Size:  it.qs.Size(),
+			Value: it.qs.Size(),
 			Exact: false,
 		},
 	}, nil
@@ -123,13 +93,13 @@ type allIteratorNext struct {
 	cons    *constraint
 }
 
-func newAllIteratorNext(nodes bool, qs *QuadStore, cons *constraint) *allIteratorNext {
+func (qs *QuadStore) newAllIteratorNext(nodes bool, cons *constraint) *allIteratorNext {
 	if nodes && cons != nil {
-		panic("cannot use a kv all iterator across nodes with a constraint")
+		panic("cannot use a kv all iterator across nodes with a constraint\n")
 	}
 	return &allIteratorNext{
-		nodes:   nodes,
 		qs:      qs,
+		nodes:   nodes,
 		horizon: qs.horizon(context.TODO()),
 		cons:    cons,
 	}
@@ -229,13 +199,13 @@ type allIteratorContains struct {
 	cons    *constraint
 }
 
-func newAllIteratorContains(nodes bool, qs *QuadStore, cons *constraint) *allIteratorContains {
+func (qs *QuadStore) newAllIteratorContains(nodes bool, cons *constraint) *allIteratorContains {
 	if nodes && cons != nil {
 		panic("cannot use a kv all iterator across nodes with a constraint")
 	}
 	return &allIteratorContains{
-		nodes:   nodes,
 		qs:      qs,
+		nodes:   nodes,
 		horizon: qs.horizon(context.TODO()),
 		cons:    cons,
 	}
diff --git a/graph/kv/iterators.go b/graph/kv/iterators.go
index 15fc3f9..81d61a7 100644
--- a/graph/kv/iterators.go
+++ b/graph/kv/iterators.go
@@ -12,12 +12,12 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-func (qs *QuadStore) NodesAllIterator() graph.Iterator {
-	return NewAllIterator(true, qs, nil)
+func (qs *QuadStore) NodesAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(true, nil)
 }
 
-func (qs *QuadStore) QuadsAllIterator() graph.Iterator {
-	return NewAllIterator(false, qs, nil)
+func (qs *QuadStore) QuadsAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(false, nil)
 }
 
 func (qs *QuadStore) indexSize(ctx context.Context, ind QuadIndex, vals []uint64) (graph.Size, error) {
@@ -38,12 +38,12 @@ func (qs *QuadStore) indexSize(ctx context.Context, ind QuadIndex, vals []uint64
 	}
 	if len(ind.Dirs) == len(vals) {
 		return graph.Size{
-			Size:  sz,
+			Value: sz,
 			Exact: true,
 		}, nil
 	}
 	return graph.Size{
-		Size:  1 + sz/2,
+		Value: 1 + sz/2,
 		Exact: false,
 	}, nil
 }
@@ -51,7 +51,7 @@ func (qs *QuadStore) indexSize(ctx context.Context, ind QuadIndex, vals []uint64
 func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v graph.Ref) (graph.Size, error) {
 	vi, ok := v.(Int64Value)
 	if !ok {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	}
 	qs.indexes.RLock()
 	all := qs.indexes.all
@@ -66,12 +66,12 @@ func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v g
 		return graph.Size{}, err
 	}
 	return graph.Size{
-		Size:  1 + st.Quads.Size/2,
+		Value: 1 + st.Quads.Value/2,
 		Exact: false,
 	}, nil
 }
 
-func (qs *QuadStore) QuadIterator(dir quad.Direction, v graph.Ref) graph.Iterator {
+func (qs *QuadStore) QuadIterator(dir quad.Direction, v graph.Ref) graph.IteratorShape {
 	if v == nil {
 		return iterator.NewNull()
 	}
@@ -82,10 +82,10 @@ func (qs *QuadStore) QuadIterator(dir quad.Direction, v graph.Ref) graph.Iterato
 	// Find the best index for this direction.
 	if ind := qs.bestIndexes([]quad.Direction{dir}); len(ind) == 1 {
 		// this will scan the prefix automatically
-		return NewQuadIterator(qs, ind[0], []uint64{uint64(vi)})
+		return qs.newQuadIterator(ind[0], []uint64{uint64(vi)})
 	}
 	// Fallback: iterate all quads and check the corresponding direction.
-	return NewAllIterator(false, qs, &constraint{
+	return qs.newAllIterator(false, &constraint{
 		dir: dir,
 		val: vi,
 	})
@@ -127,12 +127,12 @@ type IndexScan struct {
 	Values []uint64
 }
 
-func (s IndexScan) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s IndexScan) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	kqs, ok := qs.(*QuadStore)
 	if !ok {
 		return iterator.NewError(fmt.Errorf("expected KV quadstore, got: %T", qs))
 	}
-	return NewQuadIterator(kqs, s.Index, s.Values)
+	return kqs.newQuadIterator(s.Index, s.Values)
 }
 
 func (s IndexScan) Optimize(r shape.Optimizer) (shape.Shape, bool) {
diff --git a/graph/kv/quad_iterator.go b/graph/kv/quad_iterator.go
index 14cae26..1c3c7b7 100644
--- a/graph/kv/quad_iterator.go
+++ b/graph/kv/quad_iterator.go
@@ -23,31 +23,7 @@ import (
 	"github.com/hidal-go/hidalgo/kv"
 )
 
-var _ graph.IteratorFuture = &QuadIterator{}
-
 type QuadIterator struct {
-	it *quadIterator
-	graph.Iterator
-}
-
-func NewQuadIterator(qs *QuadStore, ind QuadIndex, vals []uint64) *QuadIterator {
-	it := &QuadIterator{
-		it: newQuadIterator(qs, ind, vals),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *QuadIterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-func (it *QuadIterator) Sorted() bool { return true }
-
-var _ graph.IteratorShapeCompat = &quadIterator{}
-
-type quadIterator struct {
 	qs   *QuadStore
 	ind  QuadIndex
 	vals []uint64
@@ -56,37 +32,31 @@ type quadIterator struct {
 	err  error
 }
 
-func newQuadIterator(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIterator {
-	return &quadIterator{
+func (qs *QuadStore) newQuadIterator(ind QuadIndex, vals []uint64) *QuadIterator {
+	return &QuadIterator{
 		qs:   qs,
 		ind:  ind,
 		vals: vals,
-		size: graph.Size{Size: -1},
+		size: graph.Size{Value: -1},
 	}
 }
 
-func (it *quadIterator) Iterate() graph.Scanner {
-	return newQuadIteratorNext(it.qs, it.ind, it.vals)
+func (it *QuadIterator) Iterate() graph.Scanner {
+	return it.qs.newQuadIteratorNext(it.ind, it.vals)
 }
 
-func (it *quadIterator) Lookup() graph.Index {
-	return newQuadIteratorContains(it.qs, it.ind, it.vals)
+func (it *QuadIterator) Lookup() graph.Index {
+	return it.qs.newQuadIteratorContains(it.ind, it.vals)
 }
 
-func (it *quadIterator) AsLegacy() graph.Iterator {
-	it2 := &QuadIterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *quadIterator) SubIterators() []graph.IteratorShape {
+func (it *QuadIterator) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *quadIterator) getSize(ctx context.Context) (graph.Size, error) {
+func (it *QuadIterator) getSize(ctx context.Context) (graph.Size, error) {
 	if it.err != nil {
 		return graph.Size{}, it.err
-	} else if it.size.Size >= 0 {
+	} else if it.size.Value >= 0 {
 		return it.size, nil
 	}
 	if len(it.ind.Dirs) == len(it.vals) {
@@ -98,20 +68,20 @@ func (it *quadIterator) getSize(ctx context.Context) (graph.Size, error) {
 		it.size = sz
 		return sz, nil
 	}
-	return graph.Size{Size: 1 + it.qs.Size()/2, Exact: false}, nil
+	return graph.Size{Value: 1 + it.qs.Size()/2, Exact: false}, nil
 }
 
-func (it *quadIterator) String() string {
+func (it *QuadIterator) String() string {
 	return fmt.Sprintf("KVQuads(%v)", it.ind)
 }
 
-func (it *quadIterator) Sorted() bool { return true }
+func (it *QuadIterator) Sorted() bool { return true }
 
-func (it *quadIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *QuadIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, false
 }
 
-func (it *quadIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *QuadIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	s, err := it.getSize(ctx)
 	return graph.IteratorCosts{
 		ContainsCost: 1,
@@ -136,7 +106,7 @@ type quadIteratorNext struct {
 	prim *proto.Primitive
 }
 
-func newQuadIteratorNext(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIteratorNext {
+func (qs *QuadStore) newQuadIteratorNext(ind QuadIndex, vals []uint64) *quadIteratorNext {
 	return &quadIteratorNext{
 		qs:   qs,
 		ind:  ind,
@@ -256,7 +226,7 @@ type quadIteratorContains struct {
 	prim *proto.Primitive
 }
 
-func newQuadIteratorContains(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIteratorContains {
+func (qs *QuadStore) newQuadIteratorContains(ind QuadIndex, vals []uint64) *quadIteratorContains {
 	return &quadIteratorContains{
 		qs:   qs,
 		ind:  ind,
diff --git a/graph/kv/quadstore.go b/graph/kv/quadstore.go
index 8dbcfd9..fb72ae6 100644
--- a/graph/kv/quadstore.go
+++ b/graph/kv/quadstore.go
@@ -234,21 +234,21 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 	}
 	st := graph.Stats{
 		Nodes: graph.Size{
-			Size:  sz / 3,
+			Value: sz / 3,
 			Exact: false, // TODO(dennwc): store nodes count
 		},
 		Quads: graph.Size{
-			Size:  sz,
+			Value: sz,
 			Exact: true,
 		},
 	}
 	if exact {
 		// calculate the exact number of nodes
-		st.Nodes.Size = 0
-		it := qs.NodesAllIterator()
+		st.Nodes.Value = 0
+		it := qs.NodesAllIterator().Iterate()
 		defer it.Close()
 		for it.Next(ctx) {
-			st.Nodes.Size++
+			st.Nodes.Value++
 		}
 		if err := it.Err(); err != nil {
 			return st, err
diff --git a/graph/memstore/all_iterator.go b/graph/memstore/all_iterator.go
index 9cab3a3..71a6484 100644
--- a/graph/memstore/all_iterator.go
+++ b/graph/memstore/all_iterator.go
@@ -20,26 +20,6 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.IteratorFuture = (*AllIterator)(nil)
-
-type AllIterator struct {
-	it *allIterator
-	graph.Iterator
-}
-
-func newAllIterator(qs *QuadStore, nodes bool, maxid int64) *AllIterator {
-	it := &AllIterator{
-		it: newAllIterator2(qs, nodes, maxid),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *AllIterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
 var _ graph.IteratorShape = (*allIterator)(nil)
 
 type allIterator struct {
@@ -49,7 +29,7 @@ type allIterator struct {
 	nodes bool
 }
 
-func newAllIterator2(qs *QuadStore, nodes bool, maxid int64) *allIterator {
+func (qs *QuadStore) newAllIterator(nodes bool, maxid int64) *allIterator {
 	return &allIterator{
 		qs: qs, all: qs.cloneAll(), nodes: nodes,
 		maxid: maxid,
@@ -57,17 +37,11 @@ func newAllIterator2(qs *QuadStore, nodes bool, maxid int64) *allIterator {
 }
 
 func (it *allIterator) Iterate() graph.Scanner {
-	return newAllIteratorNext(it.qs, it.nodes, it.maxid, it.all)
+	return it.qs.newAllIteratorNext(it.nodes, it.maxid, it.all)
 }
 
 func (it *allIterator) Lookup() graph.Index {
-	return newAllIteratorContains(it.qs, it.nodes, it.maxid)
-}
-
-func (it *allIterator) AsLegacy() graph.Iterator {
-	it2 := &AllIterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
+	return it.qs.newAllIteratorContains(it.nodes, it.maxid)
 }
 
 func (it *allIterator) SubIterators() []graph.IteratorShape { return nil }
@@ -85,7 +59,7 @@ func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 		ContainsCost: 1,
 		Size: graph.Size{
 			// TODO(dennwc): use maxid?
-			Size:  int64(len(it.all)),
+			Value: int64(len(it.all)),
 			Exact: true,
 		},
 	}, nil
@@ -113,7 +87,7 @@ type allIteratorNext struct {
 	done bool
 }
 
-func newAllIteratorNext(qs *QuadStore, nodes bool, maxid int64, all []*primitive) *allIteratorNext {
+func (qs *QuadStore) newAllIteratorNext(nodes bool, maxid int64, all []*primitive) *allIteratorNext {
 	return &allIteratorNext{
 		qs: qs, all: all, nodes: nodes,
 		i: -1, maxid: maxid,
@@ -182,7 +156,7 @@ type allIteratorContains struct {
 	done bool
 }
 
-func newAllIteratorContains(qs *QuadStore, nodes bool, maxid int64) *allIteratorContains {
+func (qs *QuadStore) newAllIteratorContains(nodes bool, maxid int64) *allIteratorContains {
 	return &allIteratorContains{
 		qs: qs, nodes: nodes,
 		maxid: maxid,
diff --git a/graph/memstore/iterator.go b/graph/memstore/iterator.go
index 8c9b67a..fb1b926 100644
--- a/graph/memstore/iterator.go
+++ b/graph/memstore/iterator.go
@@ -24,39 +24,15 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-var _ graph.Iterator = &Iterator{}
-
 type Iterator struct {
-	it *iterator2
-	graph.Iterator
-}
-
-func NewIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *Iterator {
-	it := &Iterator{
-		it: newIterator(tree, qs, d, value),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func (it *Iterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-func (it *Iterator) Sorted() bool { return true }
-
-var _ graph.IteratorShapeCompat = &iterator2{}
-
-type iterator2 struct {
 	qs    *QuadStore
 	tree  *Tree
 	d     quad.Direction
 	value int64
 }
 
-func newIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iterator2 {
-	return &iterator2{
+func (qs *QuadStore) newIterator(tree *Tree, d quad.Direction, value int64) *Iterator {
+	return &Iterator{
 		qs:    qs,
 		tree:  tree,
 		d:     d,
@@ -64,41 +40,35 @@ func newIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iter
 	}
 }
 
-func (it *iterator2) Iterate() graph.Scanner {
+func (it *Iterator) Iterate() graph.Scanner {
 	// TODO(dennwc): it doesn't check the direction and value, while Contains does; is it expected?
-	return newIteratorNext(it.tree, it.qs, it.d)
+	return it.qs.newIteratorNext(it.tree, it.d)
 }
 
-func (it *iterator2) Lookup() graph.Index {
-	return newIteratorContains(it.tree, it.qs, it.d, it.value)
+func (it *Iterator) Lookup() graph.Index {
+	return it.qs.newIteratorContains(it.tree, it.d, it.value)
 }
 
-func (it *iterator2) AsLegacy() graph.Iterator {
-	it2 := &Iterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
-}
-
-func (it *iterator2) SubIterators() []graph.IteratorShape {
+func (it *Iterator) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *iterator2) String() string {
+func (it *Iterator) String() string {
 	return fmt.Sprintf("MemStore(%v)", it.d)
 }
 
-func (it *iterator2) Sorted() bool { return true }
+func (it *Iterator) Sorted() bool { return true }
 
-func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Iterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, false
 }
 
-func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Iterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	return graph.IteratorCosts{
 		ContainsCost: int64(math.Log(float64(it.tree.Len()))) + 1,
 		NextCost:     1,
 		Size: graph.Size{
-			Size:  int64(it.tree.Len()),
+			Value: int64(it.tree.Len()),
 			Exact: true,
 		},
 	}, nil
@@ -115,7 +85,7 @@ type iteratorNext struct {
 	err  error
 }
 
-func newIteratorNext(tree *Tree, qs *QuadStore, d quad.Direction) *iteratorNext {
+func (qs *QuadStore) newIteratorNext(tree *Tree, d quad.Direction) *iteratorNext {
 	return &iteratorNext{
 		nodes: d == 0,
 		d:     d,
@@ -185,7 +155,7 @@ type iteratorContains struct {
 	value int64
 }
 
-func newIteratorContains(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iteratorContains {
+func (qs *QuadStore) newIteratorContains(tree *Tree, d quad.Direction, value int64) *iteratorContains {
 	return &iteratorContains{
 		nodes: d == 0,
 		qs:    qs,
diff --git a/graph/memstore/quadstore.go b/graph/memstore/quadstore.go
index a5126b3..3c8f3ec 100644
--- a/graph/memstore/quadstore.go
+++ b/graph/memstore/quadstore.go
@@ -476,14 +476,14 @@ func (qs *QuadStore) Quad(index graph.Ref) quad.Quad {
 	return qs.lookupQuadDirs(q)
 }
 
-func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Ref) graph.Iterator {
+func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Ref) graph.IteratorShape {
 	id, ok := asID(value)
 	if !ok {
 		return iterator.NewNull()
 	}
 	index, ok := qs.index.Get(d, id)
 	if ok && index.Len() != 0 {
-		return NewIterator(index, qs, d, id)
+		return qs.newIterator(index, d, id)
 	}
 	return iterator.NewNull()
 }
@@ -491,23 +491,23 @@ func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Ref) graph.Itera
 func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v graph.Ref) (graph.Size, error) {
 	id, ok := asID(v)
 	if !ok {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	}
 	index, ok := qs.index.Get(d, id)
 	if !ok {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	}
-	return graph.Size{Size: int64(index.Len()), Exact: true}, nil
+	return graph.Size{Value: int64(index.Len()), Exact: true}, nil
 }
 
 func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error) {
 	return graph.Stats{
 		Nodes: graph.Size{
-			Size:  int64(len(qs.vals)),
+			Value: int64(len(qs.vals)),
 			Exact: true,
 		},
 		Quads: graph.Size{
-			Size:  int64(len(qs.quads)),
+			Value: int64(len(qs.quads)),
 			Exact: true,
 		},
 	}, nil
@@ -540,8 +540,8 @@ func (qs *QuadStore) NameOf(v graph.Ref) quad.Value {
 	return qs.lookupVal(n)
 }
 
-func (qs *QuadStore) QuadsAllIterator() graph.Iterator {
-	return newAllIterator(qs, false, qs.last)
+func (qs *QuadStore) QuadsAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(false, qs.last)
 }
 
 func (qs *QuadStore) QuadDirection(val graph.Ref, d quad.Direction) graph.Ref {
@@ -556,8 +556,8 @@ func (qs *QuadStore) QuadDirection(val graph.Ref, d quad.Direction) graph.Ref {
 	return bnode(id)
 }
 
-func (qs *QuadStore) NodesAllIterator() graph.Iterator {
-	return newAllIterator(qs, true, qs.last)
+func (qs *QuadStore) NodesAllIterator() graph.IteratorShape {
+	return qs.newAllIterator(true, qs.last)
 }
 
 func (qs *QuadStore) Close() error { return nil }
diff --git a/graph/nosql/iterator.go b/graph/nosql/iterator.go
index 170add6..4c2c41c 100644
--- a/graph/nosql/iterator.go
+++ b/graph/nosql/iterator.go
@@ -42,39 +42,7 @@ func linkageToFilters(links []Linkage) []nosql.FieldFilter {
 	return filters
 }
 
-var _ graph.IteratorFuture = (*Iterator)(nil)
-
-func NewLinksToIterator(qs *QuadStore, collection string, links []Linkage) *Iterator {
-	it := &Iterator{
-		it: newLinksToIterator(qs, collection, links),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-func NewIterator(qs *QuadStore, collection string, constraints ...nosql.FieldFilter) *Iterator {
-	it := &Iterator{
-		it: newIterator(qs, collection, constraints...),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
 type Iterator struct {
-	it *iterator2
-	graph.Iterator
-}
-
-func (it *Iterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-func (it *Iterator) Sorted() bool { return true }
-
-var _ graph.IteratorShapeCompat = (*iterator2)(nil)
-
-type iterator2 struct {
 	qs         *QuadStore
 	collection string
 	limit      int64
@@ -85,71 +53,65 @@ type iterator2 struct {
 	err  error
 }
 
-func newLinksToIterator(qs *QuadStore, collection string, links []Linkage) *iterator2 {
+func (qs *QuadStore) newLinksToIterator(collection string, links []Linkage) *Iterator {
 	filters := linkageToFilters(links)
-	it := newIterator(qs, collection, filters...)
+	it := qs.newIterator(collection, filters...)
 	it.links = links
 	return it
 }
 
-func newIterator(qs *QuadStore, collection string, constraints ...nosql.FieldFilter) *iterator2 {
-	return &iterator2{
+func (qs *QuadStore) newIterator(collection string, constraints ...nosql.FieldFilter) *Iterator {
+	return &Iterator{
 		qs:         qs,
 		constraint: constraints,
 		collection: collection,
-		size:       graph.Size{Size: -1},
+		size:       graph.Size{Value: -1},
 	}
 }
 
-func (it *iterator2) Iterate() graph.Scanner {
-	return newIteratorNext(it.qs, it.collection, it.constraint, it.limit)
-}
-
-func (it *iterator2) Lookup() graph.Index {
-	return newIteratorContains(it.qs, it.collection, it.constraint, it.links, it.limit)
+func (it *Iterator) Iterate() graph.Scanner {
+	return it.qs.newIteratorNext(it.collection, it.constraint, it.limit)
 }
 
-func (it *iterator2) AsLegacy() graph.Iterator {
-	it2 := &Iterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
+func (it *Iterator) Lookup() graph.Index {
+	return it.qs.newIteratorContains(it.collection, it.constraint, it.links, it.limit)
 }
 
-func (it *iterator2) SubIterators() []graph.IteratorShape {
+func (it *Iterator) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *iterator2) getSize(ctx context.Context) (graph.Size, error) {
-	if it.size.Size == -1 {
+func (it *Iterator) getSize(ctx context.Context) (graph.Size, error) {
+	if it.size.Value == -1 {
 		size, err := it.qs.getSize(it.collection, it.constraint)
 		if err != nil {
 			it.err = err
 		}
 		it.size = graph.Size{
-			Size:  size,
+			Value: size,
 			Exact: true,
 		}
 	}
-	if it.limit > 0 && it.size.Size > it.limit {
-		it.size.Size = it.limit
+	if it.limit > 0 && it.size.Value > it.limit {
+		it.size.Value = it.limit
 	}
-	if it.size.Size < 0 {
+	if it.size.Value < 0 {
 		return graph.Size{
-			Size:  it.qs.Size(),
+			Value: it.qs.Size(),
 			Exact: false,
 		}, it.err
 	}
 	return it.size, nil
 }
 
-func (it *iterator2) Sorted() bool                                             { return true }
-func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
+func (it *Iterator) Sorted() bool                                             { return true }
+func (it *Iterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
 
-func (it *iterator2) String() string {
+func (it *Iterator) String() string {
 	return fmt.Sprintf("NoSQL(%v)", it.collection)
 }
 
-func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Iterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	size, err := it.getSize(ctx)
 	return graph.IteratorCosts{
 		ContainsCost: 1,
@@ -169,7 +131,7 @@ type iteratorNext struct {
 	err    error
 }
 
-func newIteratorNext(qs *QuadStore, collection string, constraints []nosql.FieldFilter, limit int64) *iteratorNext {
+func (qs *QuadStore) newIteratorNext(collection string, constraints []nosql.FieldFilter, limit int64) *iteratorNext {
 	return &iteratorNext{
 		qs:         qs,
 		constraint: constraints,
@@ -262,7 +224,7 @@ type iteratorContains struct {
 	err    error
 }
 
-func newIteratorContains(qs *QuadStore, collection string, constraints []nosql.FieldFilter, links []Linkage, limit int64) *iteratorContains {
+func (qs *QuadStore) newIteratorContains(collection string, constraints []nosql.FieldFilter, links []Linkage, limit int64) *iteratorContains {
 	return &iteratorContains{
 		qs:         qs,
 		collection: collection,
diff --git a/graph/nosql/quadstore.go b/graph/nosql/quadstore.go
index 9fe914b..1a19d55 100644
--- a/graph/nosql/quadstore.go
+++ b/graph/nosql/quadstore.go
@@ -618,35 +618,35 @@ func (qs *QuadStore) Quad(val graph.Ref) quad.Quad {
 	}
 }
 
-func (qs *QuadStore) QuadIterator(d quad.Direction, val graph.Ref) graph.Iterator {
+func (qs *QuadStore) QuadIterator(d quad.Direction, val graph.Ref) graph.IteratorShape {
 	h, ok := val.(NodeHash)
 	if !ok {
 		return iterator.NewNull()
 	}
-	return NewLinksToIterator(qs, "quads", []Linkage{{Dir: d, Val: h}})
+	return qs.newLinksToIterator("quads", []Linkage{{Dir: d, Val: h}})
 }
 
 func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, v graph.Ref) (graph.Size, error) {
 	h, ok := v.(NodeHash)
 	if !ok {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	}
 	sz, err := qs.getSize("quads", linkageToFilters([]Linkage{{Dir: d, Val: h}}))
 	if err != nil {
 		return graph.Size{}, err
 	}
 	return graph.Size{
-		Size:  sz,
+		Value: sz,
 		Exact: true,
 	}, nil
 }
 
-func (qs *QuadStore) NodesAllIterator() graph.Iterator {
-	return NewIterator(qs, "nodes")
+func (qs *QuadStore) NodesAllIterator() graph.IteratorShape {
+	return qs.newIterator("nodes")
 }
 
-func (qs *QuadStore) QuadsAllIterator() graph.Iterator {
-	return NewIterator(qs, "quads")
+func (qs *QuadStore) QuadsAllIterator() graph.IteratorShape {
+	return qs.newIterator("quads")
 }
 
 func (qs *QuadStore) hashOf(s quad.Value) NodeHash {
@@ -702,11 +702,11 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 	}
 	return graph.Stats{
 		Nodes: graph.Size{
-			Size:  nodes,
+			Value: nodes,
 			Exact: true,
 		},
 		Quads: graph.Size{
-			Size:  quads,
+			Value: quads,
 			Exact: true,
 		},
 	}, nil
diff --git a/graph/nosql/shapes.go b/graph/nosql/shapes.go
index b52637c..130d082 100644
--- a/graph/nosql/shapes.go
+++ b/graph/nosql/shapes.go
@@ -38,12 +38,12 @@ type Shape struct {
 	Limit      int64               // limits a number of documents
 }
 
-func (s Shape) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Shape) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	db, ok := qs.(*QuadStore)
 	if !ok {
 		return iterator.NewError(fmt.Errorf("not a nosql database: %T", qs))
 	}
-	return NewIterator(db, s.Collection, s.Filters...)
+	return db.newIterator(s.Collection, s.Filters...)
 }
 
 func (s Shape) Optimize(r shape.Optimizer) (shape.Shape, bool) {
@@ -56,12 +56,12 @@ type Quads struct {
 	Limit int64     // limits a number of documents
 }
 
-func (s Quads) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Quads) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	db, ok := qs.(*QuadStore)
 	if !ok {
 		return iterator.NewError(fmt.Errorf("not a nosql database: %T", qs))
 	}
-	return NewLinksToIterator(db, colQuads, s.Links)
+	return db.newLinksToIterator(colQuads, s.Links)
 }
 
 func (s Quads) Optimize(r shape.Optimizer) (shape.Shape, bool) {
diff --git a/graph/path/morphism_apply_functions.go b/graph/path/morphism_apply_functions.go
index 47460dc..7c17b95 100644
--- a/graph/path/morphism_apply_functions.go
+++ b/graph/path/morphism_apply_functions.go
@@ -228,11 +228,11 @@ func savePredicatesMorphism(isIn bool, tag string) morphism {
 }
 
 type iteratorShape struct {
-	it   graph.Iterator
+	it   graph.IteratorShape
 	sent bool
 }
 
-func (s *iteratorShape) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s *iteratorShape) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if s.sent {
 		return iterator.NewError(fmt.Errorf("iterator already used in query"))
 	}
@@ -245,7 +245,7 @@ func (s *iteratorShape) Optimize(r shape.Optimizer) (shape.Shape, bool) {
 }
 
 // iteratorMorphism simply tacks the input iterator onto the chain.
-func iteratorMorphism(it graph.Iterator) morphism {
+func iteratorMorphism(it graph.IteratorShape) morphism {
 	return morphism{
 		Reversal: func(ctx *pathContext) (morphism, *pathContext) { return iteratorMorphism(it), ctx },
 		Apply: func(in shape.Shape, ctx *pathContext) (shape.Shape, *pathContext) {
@@ -283,9 +283,9 @@ func followMorphism(p *Path) morphism {
 	}
 }
 
-type iteratorBuilder func(qs graph.QuadStore) graph.Iterator
+type iteratorBuilder func(qs graph.QuadStore) graph.IteratorShape
 
-func (s iteratorBuilder) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s iteratorBuilder) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	return s(qs)
 }
 func (s iteratorBuilder) Optimize(r shape.Optimizer) (shape.Shape, bool) {
@@ -298,7 +298,7 @@ func followRecursiveMorphism(p *Path, maxDepth int, depthTags []string) morphism
 			return followRecursiveMorphism(p.Reverse(), maxDepth, depthTags), ctx
 		},
 		Apply: func(in shape.Shape, ctx *pathContext) (shape.Shape, *pathContext) {
-			return iteratorBuilder(func(qs graph.QuadStore) graph.Iterator {
+			return iteratorBuilder(func(qs graph.QuadStore) graph.IteratorShape {
 				in := in.BuildIterator(qs)
 				it := iterator.NewRecursive(in, p.MorphismFor(qs), maxDepth)
 				for _, s := range depthTags {
diff --git a/graph/path/path.go b/graph/path/path.go
index e60958c..96f1ba1 100644
--- a/graph/path/path.go
+++ b/graph/path/path.go
@@ -101,7 +101,7 @@ func StartPathNodes(qs graph.QuadStore, nodes ...graph.Ref) *Path {
 }
 
 // PathFromIterator creates a new Path from a set of nodes contained in iterator.
-func PathFromIterator(qs graph.QuadStore, it graph.Iterator) *Path {
+func PathFromIterator(qs graph.QuadStore, it graph.IteratorShape) *Path {
 	return newPath(qs, iteratorMorphism(it))
 }
 
@@ -501,7 +501,7 @@ func (p *Path) Back(tag string) *Path {
 // call this with a full path (not a morphism), since a morphism does not have
 // the ability to fetch the underlying quads.  This function will panic if
 // called with a morphism (i.e. if p.IsMorphism() is true).
-func (p *Path) BuildIterator() graph.Iterator {
+func (p *Path) BuildIterator() graph.IteratorShape {
 	if p.IsMorphism() {
 		panic("Building an iterator from a morphism. Bind a QuadStore with BuildIteratorOn(qs)")
 	}
@@ -509,7 +509,7 @@ func (p *Path) BuildIterator() graph.Iterator {
 }
 
 // BuildIteratorOn will return an iterator for this path on the given QuadStore.
-func (p *Path) BuildIteratorOn(qs graph.QuadStore) graph.Iterator {
+func (p *Path) BuildIteratorOn(qs graph.QuadStore) graph.IteratorShape {
 	return shape.BuildIterator(qs, p.Shape())
 }
 
@@ -518,14 +518,14 @@ func (p *Path) BuildIteratorOn(qs graph.QuadStore) graph.Iterator {
 // return a new Iterator that yields the subset of values from the existing
 // iterator matched by the current Path.
 func (p *Path) Morphism() graph.ApplyMorphism {
-	return func(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
+	return func(qs graph.QuadStore, it graph.IteratorShape) graph.IteratorShape {
 		return p.ShapeFrom(&iteratorShape{it: it}).BuildIterator(qs)
 	}
 }
 
 // MorphismFor is the same as Morphism but binds returned function to a specific QuadStore.
 func (p *Path) MorphismFor(qs graph.QuadStore) iterator.Morphism {
-	return func(it graph.Iterator) graph.Iterator {
+	return func(it graph.IteratorShape) graph.IteratorShape {
 		return p.ShapeFrom(&iteratorShape{it: it}).BuildIterator(qs)
 	}
 }
diff --git a/graph/quadstore.go b/graph/quadstore.go
index ecfd490..2ae4101 100644
--- a/graph/quadstore.go
+++ b/graph/quadstore.go
@@ -75,7 +75,7 @@ type QuadIndexer interface {
 
 	// Given a direction and a token, creates an iterator of links which have
 	// that node token in that directional field.
-	QuadIterator(quad.Direction, Ref) Iterator
+	QuadIterator(quad.Direction, Ref) IteratorShape
 
 	// QuadIteratorSize returns an estimated size of an iterator.
 	QuadIteratorSize(ctx context.Context, d quad.Direction, v Ref) (Size, error)
@@ -94,7 +94,7 @@ type QuadIndexer interface {
 
 // Size of a graph (either in nodes or quads).
 type Size struct {
-	Size  int64
+	Value int64
 	Exact bool
 }
 
@@ -117,10 +117,10 @@ type QuadStore interface {
 	NewQuadWriter() (quad.WriteCloser, error)
 
 	// Returns an iterator enumerating all nodes in the graph.
-	NodesAllIterator() Iterator
+	NodesAllIterator() IteratorShape
 
 	// Returns an iterator enumerating all links in the graph.
-	QuadsAllIterator() Iterator
+	QuadsAllIterator() IteratorShape
 
 	// Stats returns the number of nodes and quads currently stored.
 	// Exact flag controls the correctness of the value. It can be an estimation, or a precise calculation.
diff --git a/graph/quadwriter.go b/graph/quadwriter.go
index 56ee8de..d8fe7c8 100644
--- a/graph/quadwriter.go
+++ b/graph/quadwriter.go
@@ -307,16 +307,16 @@ func NewQuadStoreReader(qs QuadStore) quad.ReadSkipCloser {
 // Only quads returned by iterator's Result will be used.
 //
 // Iterator will be closed with the reader.
-func NewResultReader(qs QuadStore, it Iterator) quad.ReadSkipCloser {
+func NewResultReader(qs QuadStore, it Scanner) quad.ReadSkipCloser {
 	if it == nil {
-		it = qs.QuadsAllIterator()
+		it = qs.QuadsAllIterator().Iterate()
 	}
 	return &quadReader{qs: qs, it: it}
 }
 
 type quadReader struct {
 	qs QuadStore
-	it Iterator
+	it Scanner
 }
 
 func (r *quadReader) ReadQuad() (quad.Quad, error) {
diff --git a/graph/shape.go b/graph/shape.go
deleted file mode 100644
index a849822..0000000
--- a/graph/shape.go
+++ /dev/null
@@ -1,310 +0,0 @@
-package graph
-
-import "context"
-
-// Scanner is an iterator that lists all results sequentially, but not necessarily in a sorted order.
-type Scanner interface {
-	IteratorBase
-
-	// Next advances the iterator to the next value, which will then be available through
-	// the Result method. It returns false if no further advancement is possible, or if an
-	// error was encountered during iteration.  Err should be consulted to distinguish
-	// between the two cases.
-	Next(ctx context.Context) bool
-}
-
-// Index is an index lookup iterator. It allows to check if an index contains a specific value.
-type Index interface {
-	IteratorBase
-
-	// Contains returns whether the value is within the set held by the iterator.
-	//
-	// It will set Result to the matching subtree. TagResults can be used to collect values from tree branches.
-	Contains(ctx context.Context, v Ref) bool
-}
-
-// Tagger is an interface for iterators that can tag values. Tags are returned as a part of TagResults call.
-type TaggerShape interface {
-	IteratorShape
-	TaggerBase
-	CopyFromTagger(st TaggerBase)
-}
-
-type IteratorCosts struct {
-	ContainsCost int64
-	NextCost     int64
-	Size         Size
-}
-
-// Shape is an iterator shape, similar to a query plan. But the plan is not specific in this
-// case - it is used to reorder query branches, and the decide what branches will be scanned
-// and what branches will lookup values (hopefully from the index, but not necessarily).
-type IteratorShape interface {
-	// TODO(dennwc): merge with shape.Shape
-
-	// String returns a short textual representation of an iterator.
-	String() string
-
-	// Iterate starts this iterator in scanning mode. Resulting iterator will list all
-	// results sequentially, but not necessary in the sorted order. Caller must close
-	// the iterator.
-	Iterate() Scanner
-
-	// Lookup starts this iterator in an index lookup mode. Depending on the iterator type,
-	// this may still involve database scans. Resulting iterator allows to check an index
-	// contains a specified value. Caller must close the iterator.
-	Lookup() Index
-
-	// These methods relate to choosing the right iterator, or optimizing an
-	// iterator tree
-	//
-	// Stats() returns the relative costs of calling the iteration methods for
-	// this iterator, as well as the size. Roughly, it will take NextCost * Size
-	// "cost units" to get everything out of the iterator. This is a wibbly-wobbly
-	// thing, and not exact, but a useful heuristic.
-	Stats(ctx context.Context) (IteratorCosts, error)
-
-	// Optimizes an iterator. Can replace the iterator, or merely move things
-	// around internally. if it chooses to replace it with a better iterator,
-	// returns (the new iterator, true), if not, it returns (self, false).
-	Optimize(ctx context.Context) (IteratorShape, bool)
-
-	// Return a slice of the subiterators for this iterator.
-	SubIterators() []IteratorShape
-}
-
-// IteratorShapeCompat is an optional interface for iterator Shape that support direct conversion
-// to a legacy Iterator. This interface should be avoided an will be deprecated in the future.
-type IteratorShapeCompat interface {
-	IteratorShape
-	AsLegacy() Iterator
-}
-
-// AsShape converts a legacy Iterator to an iterator Shape.
-func AsShape(it Iterator) IteratorShape {
-	if it == nil {
-		panic("nil iterator")
-	}
-	if it2, ok := it.(IteratorFuture); ok {
-		return it2.AsShape()
-	}
-	return &legacyShape{it}
-}
-
-var _ IteratorShapeCompat = &legacyShape{}
-
-type legacyShape struct {
-	Iterator
-}
-
-func (it *legacyShape) Optimize(ctx context.Context) (IteratorShape, bool) {
-	nit, ok := it.Iterator.Optimize()
-	if !ok {
-		return it, false
-	}
-	return AsShape(nit), true
-}
-
-func (it *legacyShape) SubIterators() []IteratorShape {
-	its := it.Iterator.SubIterators()
-	out := make([]IteratorShape, 0, len(its))
-	for _, s := range its {
-		out = append(out, AsShape(s))
-	}
-	return out
-}
-
-func (it *legacyShape) Stats(ctx context.Context) (IteratorCosts, error) {
-	st := it.Iterator.Stats()
-	return IteratorCosts{
-		NextCost:     st.NextCost,
-		ContainsCost: st.ContainsCost,
-		Size: Size{
-			Size:  st.Size,
-			Exact: st.ExactSize,
-		},
-	}, it.Err()
-}
-
-func (it *legacyShape) Iterate() Scanner {
-	it.Reset()
-	return it
-}
-func (it *legacyShape) Lookup() Index {
-	it.Reset()
-	return it
-}
-func (it *legacyShape) Close() error {
-	// FIXME(dennwc): this is incorrect, but we must do this to prevent closing iterators after
-	//                multiple calls to Iterate and/or Lookup
-	return nil
-}
-func (it *legacyShape) AsLegacy() Iterator {
-	return it.Iterator
-}
-
-// NewLegacy creates a new legacy Iterator from an iterator Shape.
-// This method will always create a new iterator, while AsLegacy will try to unwrap it first.
-func NewLegacy(s IteratorShape, self Iterator) Iterator {
-	if s == nil {
-		panic("nil iterator")
-	}
-	return &legacyIter{s: s, self: self}
-}
-
-// AsLegacy convert an iterator Shape to a legacy Iterator interface.
-func AsLegacy(s IteratorShape) Iterator {
-	if it2, ok := s.(IteratorShapeCompat); ok {
-		return it2.AsLegacy()
-	}
-	return NewLegacy(s, nil)
-}
-
-var _ IteratorFuture = &legacyIter{}
-
-type legacyIter struct {
-	s    IteratorShape
-	self Iterator
-	scan Scanner
-	cont Index
-}
-
-func (it *legacyIter) String() string {
-	return it.s.String()
-}
-
-func (it *legacyIter) AsShape() IteratorShape {
-	it.Close()
-	return it.s
-}
-
-func (it *legacyIter) TagResults(m map[string]Ref) {
-	if it.cont != nil && it.scan != nil {
-		panic("both iterators are set")
-	}
-	if it.scan != nil {
-		it.scan.TagResults(m)
-	} else if it.cont != nil {
-		it.cont.TagResults(m)
-	}
-}
-
-func (it *legacyIter) Result() Ref {
-	if it.cont != nil && it.scan != nil {
-		panic("both iterators are set")
-	}
-	if it.scan != nil {
-		return it.scan.Result()
-	}
-	if it.cont != nil {
-		return it.cont.Result()
-	}
-	return nil
-}
-
-func (it *legacyIter) Next(ctx context.Context) bool {
-	if it.scan == nil {
-		if it.cont != nil {
-			panic("attempt to set a scan iterator on contains")
-		}
-		it.scan = it.s.Iterate()
-	}
-	return it.scan.Next(ctx)
-}
-
-func (it *legacyIter) NextPath(ctx context.Context) bool {
-	if it.cont != nil && it.scan != nil {
-		panic("both iterators are set")
-	}
-	if it.scan != nil {
-		return it.scan.NextPath(ctx)
-	}
-	if it.cont != nil {
-		return it.cont.NextPath(ctx)
-	}
-	panic("calling NextPath before Next or Contains")
-}
-
-func (it *legacyIter) Contains(ctx context.Context, v Ref) bool {
-	if it.cont == nil {
-		// reset iterator by default
-		if it.scan != nil {
-			it.scan.Close()
-			it.scan = nil
-		}
-		it.cont = it.s.Lookup()
-	}
-	return it.cont.Contains(ctx, v)
-}
-
-func (it *legacyIter) Err() error {
-	if it.scan != nil {
-		if err := it.scan.Err(); err != nil {
-			return err
-		}
-	}
-	if it.cont != nil {
-		if err := it.cont.Err(); err != nil {
-			return err
-		}
-	}
-	return nil
-}
-
-func (it *legacyIter) Reset() {
-	if it.scan != nil {
-		_ = it.scan.Close()
-		it.scan = nil
-	}
-	if it.cont != nil {
-		_ = it.cont.Close()
-		it.cont = nil
-	}
-}
-
-func (it *legacyIter) Stats() IteratorStats {
-	st, _ := it.s.Stats(context.Background())
-	return IteratorStats{
-		NextCost:     st.NextCost,
-		ContainsCost: st.ContainsCost,
-		Size:         st.Size.Size,
-		ExactSize:    st.Size.Exact,
-	}
-}
-
-func (it *legacyIter) Size() (int64, bool) {
-	st, _ := it.s.Stats(context.Background())
-	return st.Size.Size, st.Size.Exact
-}
-
-func (it *legacyIter) Optimize() (Iterator, bool) {
-	nit, ok := it.s.Optimize(context.Background())
-	if !ok {
-		if it.self != nil {
-			return it.self, false
-		}
-		return it, false
-	}
-	return AsLegacy(nit), true
-}
-
-func (it *legacyIter) SubIterators() []Iterator {
-	its := it.s.SubIterators()
-	out := make([]Iterator, 0, len(its))
-	for _, s := range its {
-		out = append(out, AsLegacy(s))
-	}
-	return out
-}
-
-func (it *legacyIter) Close() error {
-	if it.scan != nil {
-		it.scan.Close()
-		it.scan = nil
-	}
-	if it.cont != nil {
-		it.cont.Close()
-		it.cont = nil
-	}
-	return nil
-}
diff --git a/graph/shape/shape.go b/graph/shape/shape.go
index d756af5..5534f95 100644
--- a/graph/shape/shape.go
+++ b/graph/shape/shape.go
@@ -20,7 +20,7 @@ var (
 // Shape represent a query tree shape.
 type Shape interface {
 	// BuildIterator constructs an iterator tree from a given shapes and binds it to QuadStore.
-	BuildIterator(qs graph.QuadStore) graph.Iterator
+	BuildIterator(qs graph.QuadStore) graph.IteratorShape
 	// Optimize runs an optimization pass over a query shape.
 	//
 	// It returns a bool that indicates if shape was replaced and should always return a copy of shape in this case.
@@ -204,7 +204,7 @@ func IsNull(s Shape) bool {
 }
 
 // BuildIterator optimizes the shape and builds a corresponding iterator tree.
-func BuildIterator(qs graph.QuadStore, s Shape) graph.Iterator {
+func BuildIterator(qs graph.QuadStore, s Shape) graph.IteratorShape {
 	qs = graph.Unwrap(qs)
 	if s != nil {
 		if debugShapes || clog.V(2) {
@@ -224,7 +224,7 @@ func BuildIterator(qs graph.QuadStore, s Shape) graph.Iterator {
 // Null represent an empty set. Mostly used as a safe alias for nil shape.
 type Null struct{}
 
-func (Null) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (Null) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	return iterator.NewNull()
 }
 func (s Null) Optimize(r Optimizer) (Shape, bool) {
@@ -237,7 +237,7 @@ func (s Null) Optimize(r Optimizer) (Shape, bool) {
 // AllNodes represents all nodes in QuadStore.
 type AllNodes struct{}
 
-func (s AllNodes) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s AllNodes) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	return qs.NodesAllIterator()
 }
 func (s AllNodes) Optimize(r Optimizer) (Shape, bool) {
@@ -253,8 +253,8 @@ type Except struct {
 	From    Shape // a set of all nodes to exclude from; nil means AllNodes
 }
 
-func (s Except) BuildIterator(qs graph.QuadStore) graph.Iterator {
-	var all graph.Iterator
+func (s Except) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
+	var all graph.IteratorShape
 	if s.From != nil {
 		all = s.From.BuildIterator(qs)
 	} else {
@@ -287,7 +287,7 @@ func (s Except) Optimize(r Optimizer) (Shape, bool) {
 
 // ValueFilter is an interface for iterator wrappers that can filter node values.
 type ValueFilter interface {
-	BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator
+	BuildIterator(qs graph.QuadStore, it graph.IteratorShape) graph.IteratorShape
 }
 
 // Filter filters all values from the source using a list of operations.
@@ -296,7 +296,7 @@ type Filter struct {
 	Filters []ValueFilter // filters to apply
 }
 
-func (s Filter) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Filter) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.From) {
 		return iterator.NewNull()
 	}
@@ -332,7 +332,7 @@ type Comparison struct {
 	Val quad.Value
 }
 
-func (f Comparison) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
+func (f Comparison) BuildIterator(qs graph.QuadStore, it graph.IteratorShape) graph.IteratorShape {
 	return iterator.NewComparison(it, f.Op, f.Val, qs)
 }
 
@@ -346,7 +346,7 @@ type Regexp struct {
 	Refs bool // allow to match IRIs
 }
 
-func (f Regexp) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
+func (f Regexp) BuildIterator(qs graph.QuadStore, it graph.IteratorShape) graph.IteratorShape {
 	if f.Refs {
 		return iterator.NewRegexWithRefs(it, f.Re, qs)
 	}
@@ -387,7 +387,7 @@ func (f Wildcard) Regexp() string {
 	return pattern
 }
 
-func (f Wildcard) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
+func (f Wildcard) BuildIterator(qs graph.QuadStore, it graph.IteratorShape) graph.IteratorShape {
 	if f.Pattern == "" {
 		return iterator.NewNull()
 	} else if strings.Trim(f.Pattern, "%") == "" {
@@ -405,8 +405,8 @@ type Count struct {
 	Values Shape
 }
 
-func (s Count) BuildIterator(qs graph.QuadStore) graph.Iterator {
-	var it graph.Iterator
+func (s Count) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
+	var it graph.IteratorShape
 	if IsNull(s.Values) {
 		it = iterator.NewNull()
 	} else {
@@ -439,7 +439,7 @@ type QuadFilter struct {
 }
 
 // buildIterator is not exposed to force to use Quads and group filters together.
-func (s QuadFilter) buildIterator(qs graph.QuadStore) graph.Iterator {
+func (s QuadFilter) buildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if s.Values == nil {
 		return iterator.NewNull()
 	} else if v, ok := One(s.Values); ok {
@@ -459,11 +459,11 @@ type Quads []QuadFilter
 func (s *Quads) Intersect(q ...QuadFilter) {
 	*s = append(*s, q...)
 }
-func (s Quads) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Quads) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if len(s) == 0 {
 		return qs.QuadsAllIterator()
 	}
-	its := make([]graph.Iterator, 0, len(s))
+	its := make([]graph.IteratorShape, 0, len(s))
 	for _, f := range s {
 		its = append(its, f.buildIterator(qs))
 	}
@@ -517,7 +517,7 @@ type NodesFrom struct {
 	Quads Shape
 }
 
-func (s NodesFrom) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s NodesFrom) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.Quads) {
 		return iterator.NewNull()
 	}
@@ -677,7 +677,7 @@ func (s QuadsAction) SimplifyFrom(quads Shape) Shape {
 func (s QuadsAction) Simplify() Shape {
 	return s.simplify()
 }
-func (s QuadsAction) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s QuadsAction) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	h := s.simplify()
 	return h.BuildIterator(qs)
 }
@@ -742,7 +742,7 @@ type Fixed []graph.Ref
 func (s *Fixed) Add(v ...graph.Ref) {
 	*s = append(*s, v...)
 }
-func (s Fixed) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Fixed) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	it := iterator.NewFixed()
 	for _, v := range s {
 		if _, ok := v.(quad.Value); ok {
@@ -770,7 +770,7 @@ type FixedTags struct {
 	On   Shape
 }
 
-func (s FixedTags) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s FixedTags) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.On) {
 		return iterator.NewNull()
 	}
@@ -832,7 +832,7 @@ func (s Lookup) resolve(qs valueResolver) Shape {
 	}
 	return Fixed(vals)
 }
-func (s Lookup) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Lookup) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	f := s.resolve(qs)
 	if IsNull(f) {
 		return iterator.NewNull()
@@ -861,7 +861,7 @@ type Materialize struct {
 	Values Shape
 }
 
-func (s Materialize) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Materialize) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.Values) {
 		return iterator.NewNull()
 	}
@@ -903,11 +903,11 @@ func clearFixedTags(arr []Shape) ([]Shape, map[string]graph.Ref) {
 // Intersect computes an intersection of nodes between multiple queries. Similar to And iterator.
 type Intersect []Shape
 
-func (s Intersect) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Intersect) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if len(s) == 0 {
 		return iterator.NewNull()
 	}
-	sub := make([]graph.Iterator, 0, len(s))
+	sub := make([]graph.IteratorShape, 0, len(s))
 	for _, c := range s {
 		sub = append(sub, c.BuildIterator(qs))
 	}
@@ -1138,7 +1138,7 @@ func (s *IntersectOpt) AddOptional(arr ...Shape) {
 	s.Opt = append(s.Opt, arr...)
 }
 
-func (s IntersectOpt) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s IntersectOpt) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if len(s.Sub) == 0 && len(s.Opt) == 0 {
 		return iterator.NewNull()
 	}
@@ -1148,8 +1148,8 @@ func (s IntersectOpt) BuildIterator(qs graph.QuadStore) graph.Iterator {
 		}
 		s.Sub = Intersect{AllNodes{}}
 	}
-	sub := make([]graph.Iterator, 0, len(s.Sub))
-	opt := make([]graph.Iterator, 0, len(s.Opt))
+	sub := make([]graph.IteratorShape, 0, len(s.Sub))
+	opt := make([]graph.IteratorShape, 0, len(s.Opt))
 	for _, c := range s.Sub {
 		sub = append(sub, c.BuildIterator(qs))
 	}
@@ -1234,11 +1234,11 @@ func (s IntersectOpt) Optimize(r Optimizer) (_ Shape, opt bool) {
 // Union joins results of multiple queries together. It does not make results unique.
 type Union []Shape
 
-func (s Union) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Union) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if len(s) == 0 {
 		return iterator.NewNull()
 	}
-	sub := make([]graph.Iterator, 0, len(s))
+	sub := make([]graph.IteratorShape, 0, len(s))
 	for _, c := range s {
 		sub = append(sub, c.BuildIterator(qs))
 	}
@@ -1303,7 +1303,7 @@ type Page struct {
 	Limit int64 // zero means unlimited
 }
 
-func (s Page) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Page) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.From) {
 		return iterator.NewNull()
 	}
@@ -1360,7 +1360,7 @@ type Unique struct {
 	From Shape
 }
 
-func (s Unique) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Unique) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.From) {
 		return iterator.NewNull()
 	}
@@ -1389,7 +1389,7 @@ type Save struct {
 	From Shape
 }
 
-func (s Save) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Save) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.From) {
 		return iterator.NewNull()
 	}
@@ -1438,7 +1438,7 @@ type Sort struct {
 	From Shape
 }
 
-func (s Sort) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Sort) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	if IsNull(s.From) {
 		return iterator.NewNull()
 	}
diff --git a/graph/sql/iterator.go b/graph/sql/iterator.go
index 58b43b0..740eca9 100644
--- a/graph/sql/iterator.go
+++ b/graph/sql/iterator.go
@@ -56,56 +56,28 @@ func (qs *QuadStore) Query(ctx context.Context, s Shape) (*sql.Rows, error) {
 	return rows, nil
 }
 
-var _ graph.IteratorFuture = (*Iterator)(nil)
-
-func (qs *QuadStore) NewIterator(s Select) *Iterator {
-	it := &Iterator{
-		it: qs.newIterator(s),
-	}
-	it.Iterator = graph.NewLegacy(it.it, it)
-	return it
-}
-
-type Iterator struct {
-	it *iterator2
-	graph.Iterator
-}
-
-func (it *Iterator) AsShape() graph.IteratorShape {
-	it.Close()
-	return it.it
-}
-
-var _ graph.IteratorShapeCompat = (*iterator2)(nil)
-
-func (qs *QuadStore) newIterator(s Select) *iterator2 {
-	return &iterator2{
+func (qs *QuadStore) newIterator(s Select) *Iterator {
+	return &Iterator{
 		qs:    qs,
 		query: s,
 	}
 }
 
-type iterator2 struct {
+type Iterator struct {
 	qs    *QuadStore
 	query Select
 	err   error
 }
 
-func (it *iterator2) Iterate() graph.Scanner {
-	return newIteratorNext(it.qs, it.query)
-}
-
-func (it *iterator2) Lookup() graph.Index {
-	return newIteratorContains(it.qs, it.query)
+func (it *Iterator) Iterate() graph.Scanner {
+	return it.qs.newIteratorNext(it.query)
 }
 
-func (it *iterator2) AsLegacy() graph.Iterator {
-	it2 := &Iterator{it: it}
-	it2.Iterator = graph.NewLegacy(it, it2)
-	return it2
+func (it *Iterator) Lookup() graph.Index {
+	return it.qs.newIteratorContains(it.query)
 }
 
-func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+func (it *Iterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	sz, err := it.getSize(ctx)
 	return graph.IteratorCosts{
 		NextCost:     1,
@@ -114,7 +86,7 @@ func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
 	}, err
 }
 
-func (it *iterator2) estimateSize(ctx context.Context) int64 {
+func (it *Iterator) estimateSize(ctx context.Context) int64 {
 	if it.query.Limit > 0 {
 		return it.query.Limit
 	}
@@ -122,27 +94,27 @@ func (it *iterator2) estimateSize(ctx context.Context) int64 {
 	if err != nil && it.err == nil {
 		it.err = err
 	}
-	return st.Quads.Size
+	return st.Quads.Value
 }
 
-func (it *iterator2) getSize(ctx context.Context) (graph.Size, error) {
+func (it *Iterator) getSize(ctx context.Context) (graph.Size, error) {
 	sz, err := it.qs.querySize(ctx, it.query)
 	if err != nil {
 		it.err = err
-		return graph.Size{Size: it.estimateSize(ctx), Exact: false}, err
+		return graph.Size{Value: it.estimateSize(ctx), Exact: false}, err
 	}
 	return sz, nil
 }
 
-func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+func (it *Iterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
 	return it, false
 }
 
-func (it *iterator2) SubIterators() []graph.IteratorShape {
+func (it *Iterator) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *iterator2) String() string {
+func (it *Iterator) String() string {
 	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
 }
 
@@ -246,7 +218,7 @@ func (it *iteratorBase) String() string {
 	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
 }
 
-func newIteratorNext(qs *QuadStore, s Select) *iteratorNext {
+func (qs *QuadStore) newIteratorNext(s Select) *iteratorNext {
 	return &iteratorNext{
 		iteratorBase: newIteratorBase(qs, s),
 	}
@@ -335,7 +307,7 @@ func (it *iteratorNext) Close() error {
 	return nil
 }
 
-func newIteratorContains(qs *QuadStore, s Select) *iteratorContains {
+func (qs *QuadStore) newIteratorContains(s Select) *iteratorContains {
 	return &iteratorContains{
 		iteratorBase: newIteratorBase(qs, s),
 	}
diff --git a/graph/sql/quadstore.go b/graph/sql/quadstore.go
index 7e77fb2..1db7cb3 100644
--- a/graph/sql/quadstore.go
+++ b/graph/sql/quadstore.go
@@ -539,14 +539,14 @@ func (qs *QuadStore) Quad(val graph.Ref) quad.Quad {
 	}
 }
 
-func (qs *QuadStore) QuadIterator(d quad.Direction, val graph.Ref) graph.Iterator {
+func (qs *QuadStore) QuadIterator(d quad.Direction, val graph.Ref) graph.IteratorShape {
 	v, ok := val.(Value)
 	if !ok {
 		return iterator.NewNull()
 	}
 	sel := AllQuads("")
 	sel.WhereEq("", dirField(d), v)
-	return qs.NewIterator(sel)
+	return qs.newIterator(sel)
 }
 
 func (qs *QuadStore) querySize(ctx context.Context, sel Select) (graph.Size, error) {
@@ -559,7 +559,7 @@ func (qs *QuadStore) querySize(ctx context.Context, sel Select) (graph.Size, err
 		return graph.Size{}, err
 	}
 	return graph.Size{
-		Size:  sz,
+		Value: sz,
 		Exact: true,
 	}, nil
 }
@@ -567,19 +567,19 @@ func (qs *QuadStore) querySize(ctx context.Context, sel Select) (graph.Size, err
 func (qs *QuadStore) QuadIteratorSize(ctx context.Context, d quad.Direction, val graph.Ref) (graph.Size, error) {
 	v, ok := val.(Value)
 	if !ok {
-		return graph.Size{Size: 0, Exact: true}, nil
+		return graph.Size{Value: 0, Exact: true}, nil
 	}
 	sel := AllQuads("")
 	sel.WhereEq("", dirField(d), v)
 	return qs.querySize(ctx, sel)
 }
 
-func (qs *QuadStore) NodesAllIterator() graph.Iterator {
-	return qs.NewIterator(AllNodes())
+func (qs *QuadStore) NodesAllIterator() graph.IteratorShape {
+	return qs.newIterator(AllNodes())
 }
 
-func (qs *QuadStore) QuadsAllIterator() graph.Iterator {
-	return qs.NewIterator(AllQuads(""))
+func (qs *QuadStore) QuadsAllIterator() graph.IteratorShape {
+	return qs.newIterator(AllQuads(""))
 }
 
 func (qs *QuadStore) ValueOf(s quad.Value) graph.Ref {
@@ -741,10 +741,10 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 		Quads: graph.Size{Exact: true},
 	}
 	qs.mu.RLock()
-	st.Quads.Size = qs.quads
-	st.Nodes.Size = qs.nodes
+	st.Quads.Value = qs.quads
+	st.Nodes.Value = qs.nodes
 	qs.mu.RUnlock()
-	if st.Quads.Size >= 0 {
+	if st.Quads.Value >= 0 {
 		return st, nil
 	}
 	query := func(table string) string {
@@ -755,18 +755,18 @@ func (qs *QuadStore) Stats(ctx context.Context, exact bool) (graph.Stats, error)
 		st.Quads.Exact = false
 		st.Nodes.Exact = false
 	}
-	err := qs.db.QueryRow(query("quads")).Scan(&st.Quads.Size)
+	err := qs.db.QueryRow(query("quads")).Scan(&st.Quads.Value)
 	if err != nil {
 		return graph.Stats{}, err
 	}
-	err = qs.db.QueryRow(query("nodes")).Scan(&st.Nodes.Size)
+	err = qs.db.QueryRow(query("nodes")).Scan(&st.Nodes.Value)
 	if err != nil {
 		return graph.Stats{}, err
 	}
 	if st.Quads.Exact {
 		qs.mu.Lock()
-		qs.quads = st.Quads.Size
-		qs.nodes = st.Nodes.Size
+		qs.quads = st.Quads.Value
+		qs.nodes = st.Nodes.Value
 		qs.mu.Unlock()
 	}
 	return st, nil
@@ -785,9 +785,9 @@ func (qs *QuadStore) sizeForIterator(dir quad.Direction, hash NodeHash) int64 {
 	if qs.noSizes {
 		st, _ := qs.Stats(context.TODO(), false)
 		if dir == quad.Predicate {
-			return (st.Quads.Size / 100) + 1
+			return (st.Quads.Value / 100) + 1
 		}
-		return (st.Quads.Size / 1000) + 1
+		return (st.Quads.Value / 1000) + 1
 	}
 	if val, ok := qs.sizes.Get(hash.String() + string(dir.Prefix())); ok {
 		return val.(int64)
diff --git a/graph/sql/shape.go b/graph/sql/shape.go
index 4b98ee1..9aa80e0 100644
--- a/graph/sql/shape.go
+++ b/graph/sql/shape.go
@@ -302,12 +302,12 @@ func (s Select) Columns() []string {
 	return names
 }
 
-func (s Select) BuildIterator(qs graph.QuadStore) graph.Iterator {
+func (s Select) BuildIterator(qs graph.QuadStore) graph.IteratorShape {
 	sq, ok := qs.(*QuadStore)
 	if !ok {
 		return iterator.NewError(fmt.Errorf("not a SQL quadstore: %T", qs))
 	}
-	return sq.NewIterator(s)
+	return sq.newIterator(s)
 }
 
 func (s Select) Optimize(r shape.Optimizer) (shape.Shape, bool) {
diff --git a/imports.go b/imports.go
index 31e23de..8d8216f 100644
--- a/imports.go
+++ b/imports.go
@@ -15,7 +15,7 @@ var (
 	NewTransaction = graph.NewTransaction
 )
 
-type Iterator = graph.Iterator
+type Iterator = graph.IteratorShape
 type QuadStore = graph.QuadStore
 type QuadWriter = graph.QuadWriter
 
diff --git a/internal/gephi/stream.go b/internal/gephi/stream.go
index 10bb1f4..4ff1455 100644
--- a/internal/gephi/stream.go
+++ b/internal/gephi/stream.go
@@ -214,7 +214,7 @@ type graphStreamEvent struct {
 }
 
 func (s *GraphStreamHandler) serveRawQuads(ctx context.Context, gs *GraphStream, quads shape.Shape, limit int) {
-	it := shape.BuildIterator(s.QS, quads)
+	it := shape.BuildIterator(s.QS, quads).Iterate()
 	defer it.Close()
 
 	var sh, oh valHash
@@ -266,7 +266,6 @@ func (s *GraphStreamHandler) serveNodesWithProps(ctx context.Context, gs *GraphS
 	ignore := make(map[quad.Value]struct{})
 
 	nodes := iterator.NewNot(propsPath.BuildIterator(), s.QS.NodesAllIterator())
-	defer nodes.Close()
 
 	ictx, cancel := context.WithCancel(ctx)
 	defer cancel()
@@ -287,7 +286,7 @@ func (s *GraphStreamHandler) serveNodesWithProps(ctx context.Context, gs *GraphS
 		)
 		quad.HashTo(nv, h[:])
 
-		predIt := s.QS.QuadIterator(quad.Subject, nodes.Result())
+		predIt := s.QS.QuadIterator(quad.Subject, v).Iterate()
 		defer predIt.Close()
 		for predIt.Next(ictx) {
 			// this check helps us ignore nodes with no links
diff --git a/query/gizmo/gizmo.go b/query/gizmo/gizmo.go
index 0e0e8b0..15ec49a 100644
--- a/query/gizmo/gizmo.go
+++ b/query/gizmo/gizmo.go
@@ -154,7 +154,7 @@ func (s *Session) tagsToValueMap(m map[string]graph.Ref) map[string]interface{}
 	}
 	return outputMap
 }
-func (s *Session) runIteratorToArray(it graph.Iterator, limit int) ([]map[string]interface{}, error) {
+func (s *Session) runIteratorToArray(it graph.IteratorShape, limit int) ([]map[string]interface{}, error) {
 	ctx := s.context()
 
 	output := make([]map[string]interface{}, 0)
@@ -171,7 +171,7 @@ func (s *Session) runIteratorToArray(it graph.Iterator, limit int) ([]map[string
 	return output, nil
 }
 
-func (s *Session) runIteratorToArrayNoTags(it graph.Iterator, limit int) ([]interface{}, error) {
+func (s *Session) runIteratorToArrayNoTags(it graph.IteratorShape, limit int) ([]interface{}, error) {
 	ctx := s.context()
 
 	output := make([]interface{}, 0)
@@ -186,7 +186,7 @@ func (s *Session) runIteratorToArrayNoTags(it graph.Iterator, limit int) ([]inte
 	return output, nil
 }
 
-func (s *Session) runIteratorWithCallback(it graph.Iterator, callback goja.Value, this goja.FunctionCall, limit int) error {
+func (s *Session) runIteratorWithCallback(it graph.IteratorShape, callback goja.Value, this goja.FunctionCall, limit int) error {
 	fnc, ok := goja.AssertFunction(callback)
 	if !ok {
 		return fmt.Errorf("expected js callback function")
@@ -229,7 +229,7 @@ func (s *Session) send(ctx context.Context, r *Result) bool {
 	return s.limit <= 0 || s.count < s.limit
 }
 
-func (s *Session) runIterator(it graph.Iterator) error {
+func (s *Session) runIterator(it graph.IteratorShape) error {
 	if s.shape != nil {
 		iterator.OutputQueryShapeForIterator(it, s.qs, s.shape)
 		return nil
@@ -250,7 +250,7 @@ func (s *Session) runIterator(it graph.Iterator) error {
 	return err
 }
 
-func (s *Session) countResults(it graph.Iterator) (int64, error) {
+func (s *Session) countResults(it graph.IteratorShape) (int64, error) {
 	if s.shape != nil {
 		iterator.OutputQueryShapeForIterator(it, s.qs, s.shape)
 		return 0, nil
diff --git a/query/gizmo/traversals.go b/query/gizmo/traversals.go
index 171a5d6..5676ee3 100644
--- a/query/gizmo/traversals.go
+++ b/query/gizmo/traversals.go
@@ -80,7 +80,7 @@ func (p *pathObject) clonePath() *path.Path {
 	p.path, np = np, p.path
 	return np
 }
-func (p *pathObject) buildIteratorTree() graph.Iterator {
+func (p *pathObject) buildIteratorTree() graph.IteratorShape {
 	if p.path == nil {
 		return iterator.NewNull()
 	}
diff --git a/query/graphql/graphql.go b/query/graphql/graphql.go
index 5288872..4cd45a9 100644
--- a/query/graphql/graphql.go
+++ b/query/graphql/graphql.go
@@ -149,8 +149,8 @@ type object struct {
 	fields map[string]interface{}
 }
 
-func buildIterator(qs graph.QuadStore, p *path.Path) graph.Iterator {
-	it, _ := p.BuildIterator().Optimize()
+func buildIterator(ctx context.Context, qs graph.QuadStore, p *path.Path) graph.IteratorShape {
+	it, _ := p.BuildIterator().Optimize(ctx)
 	return it
 }
 
@@ -210,7 +210,7 @@ func iterateObject(ctx context.Context, qs graph.QuadStore, f *field, p *path.Pa
 	if f.AllFields {
 		tail()
 
-		it := buildIterator(qs, p)
+		it := buildIterator(ctx, qs, p).Iterate()
 		defer it.Close()
 
 		// we don't care about alternative paths to nodes here, so we will not call NextPath
@@ -228,7 +228,7 @@ func iterateObject(ctx context.Context, qs graph.QuadStore, f *field, p *path.Pa
 			obj := make(map[string]interface{})
 			obj[ValueKey] = qs.NameOf(nv)
 			func() {
-				sit := qs.QuadIterator(quad.Subject, nv)
+				sit := qs.QuadIterator(quad.Subject, nv).Iterate()
 				defer sit.Close()
 				for sit.Next(ctx) {
 					q := qs.Quad(sit.Result())
@@ -278,7 +278,7 @@ func iterateObject(ctx context.Context, qs graph.QuadStore, f *field, p *path.Pa
 	tail()
 
 	// first, collect result node ids and any tags associated with it (flat values)
-	it := buildIterator(qs, p)
+	it := buildIterator(ctx, qs, p).Iterate()
 	defer it.Close()
 
 	var results []object
diff --git a/query/mql/query.go b/query/mql/query.go
index c37dcd0..f6bb9b6 100644
--- a/query/mql/query.go
+++ b/query/mql/query.go
@@ -28,7 +28,7 @@ type (
 
 type Query struct {
 	ses            *Session
-	it             graph.Iterator
+	it             graph.IteratorShape
 	isRepeated     map[Path]bool
 	queryStructure map[Path]map[string]interface{}
 	queryResult    map[ResultPath]map[string]interface{}
diff --git a/query/mql/session.go b/query/mql/session.go
index 0c74c2d..896fda1 100644
--- a/query/mql/session.go
+++ b/query/mql/session.go
@@ -70,7 +70,7 @@ func (s *Session) ShapeOf(query string) (interface{}, error) {
 type mqlIterator struct {
 	q   *Query
 	col query.Collation
-	it  graph.Iterator
+	it  graph.Scanner
 	res []interface{}
 }
 
@@ -132,9 +132,9 @@ func (s *Session) Execute(ctx context.Context, input string, opt query.Options)
 		return nil, q.err
 	}
 
-	it := q.it
+	it := q.it.Iterate()
 	if opt.Limit > 0 {
-		it = iterator.NewLimit(it, int64(opt.Limit))
+		it = iterator.NewLimitNext(it, int64(opt.Limit))
 	}
 	return &mqlIterator{
 		q:   q,
diff --git a/query/sexp/parser.go b/query/sexp/parser.go
index 4096546..471655b 100644
--- a/query/sexp/parser.go
+++ b/query/sexp/parser.go
@@ -23,7 +23,7 @@ import (
 	"github.com/cayleygraph/quad"
 )
 
-func BuildIteratorTreeForQuery(qs graph.QuadStore, query string) graph.Iterator {
+func BuildIteratorTreeForQuery(qs graph.QuadStore, query string) graph.IteratorShape {
 	s, err := BuildShape(query)
 	if err != nil {
 		return iterator.NewError(err)
diff --git a/query/sexp/session.go b/query/sexp/session.go
index 71f88d0..f281e32 100644
--- a/query/sexp/session.go
+++ b/query/sexp/session.go
@@ -81,12 +81,12 @@ func (s *Session) Execute(ctx context.Context, input string, opt query.Options)
 	default:
 		return nil, &query.ErrUnsupportedCollation{Collation: opt.Collation}
 	}
-	it := BuildIteratorTreeForQuery(s.qs, input)
+	it := BuildIteratorTreeForQuery(s.qs, input).Iterate()
 	if err := it.Err(); err != nil {
 		return nil, err
 	}
 	if opt.Limit > 0 {
-		it = iterator.NewLimit(it, int64(opt.Limit))
+		it = iterator.NewLimitNext(it, int64(opt.Limit))
 	}
 	return &results{
 		s:   s,
@@ -98,7 +98,7 @@ func (s *Session) Execute(ctx context.Context, input string, opt query.Options)
 type results struct {
 	s        *Session
 	col      query.Collation
-	it       graph.Iterator
+	it       graph.Scanner
 	nextPath bool
 }
 
diff --git a/schema/global.go b/schema/global.go
index 87152a0..4aea9b6 100644
--- a/schema/global.go
+++ b/schema/global.go
@@ -55,14 +55,14 @@ func LoadNamespaces(ctx context.Context, qs graph.QuadStore, dest *voc.Namespace
 // LoadIteratorToDepth is the same as LoadIteratorTo, but stops at a specified depth.
 //
 // Deprecated: see Config.LoadIteratorToDepth
-func LoadIteratorToDepth(ctx context.Context, qs graph.QuadStore, dst reflect.Value, depth int, list graph.Iterator) error {
+func LoadIteratorToDepth(ctx context.Context, qs graph.QuadStore, dst reflect.Value, depth int, list graph.IteratorShape) error {
 	return global.LoadIteratorToDepth(ctx, qs, dst, depth, list)
 }
 
 // LoadIteratorTo is a lower level version of LoadTo.
 //
 // Deprecated: see Config.LoadIteratorTo
-func LoadIteratorTo(ctx context.Context, qs graph.QuadStore, dst reflect.Value, list graph.Iterator) error {
+func LoadIteratorTo(ctx context.Context, qs graph.QuadStore, dst reflect.Value, list graph.IteratorShape) error {
 	return global.LoadIteratorToDepth(ctx, qs, dst, -1, list)
 }
 
diff --git a/schema/loader.go b/schema/loader.go
index 4df7c6f..ff0fba2 100644
--- a/schema/loader.go
+++ b/schema/loader.go
@@ -99,7 +99,7 @@ func (c *Config) LoadToDepth(ctx context.Context, qs graph.QuadStore, dst interf
 	if dst == nil {
 		return fmt.Errorf("nil destination object")
 	}
-	var it graph.Iterator
+	var it graph.IteratorShape
 	if len(ids) != 0 {
 		fixed := iterator.NewFixed()
 		for _, id := range ids {
@@ -127,13 +127,13 @@ func (c *Config) LoadPathTo(ctx context.Context, qs graph.QuadStore, dst interfa
 // destination value to be obtained via reflect package manually.
 //
 // Nodes iterator can be nil, All iterator will be used in this case.
-func (c *Config) LoadIteratorTo(ctx context.Context, qs graph.QuadStore, dst reflect.Value, list graph.Iterator) error {
+func (c *Config) LoadIteratorTo(ctx context.Context, qs graph.QuadStore, dst reflect.Value, list graph.IteratorShape) error {
 	return c.LoadIteratorToDepth(ctx, qs, dst, -1, list)
 }
 
 // LoadIteratorToDepth is the same as LoadIteratorTo, but stops at a specified depth.
 // Negative value means unlimited depth, and zero means top level only.
-func (c *Config) LoadIteratorToDepth(ctx context.Context, qs graph.QuadStore, dst reflect.Value, depth int, list graph.Iterator) error {
+func (c *Config) LoadIteratorToDepth(ctx context.Context, qs graph.QuadStore, dst reflect.Value, depth int, list graph.IteratorShape) error {
 	if depth >= 0 {
 		// 0 depth means "current level only" for user, but it's easier to make depth=0 a stop condition
 		depth++
@@ -390,12 +390,12 @@ func (l *loader) loadToValue(ctx context.Context, dst reflect.Value, depth int,
 	return nil
 }
 
-func (l *loader) iteratorForType(root graph.Iterator, rt reflect.Type, rootOnly bool) (graph.Iterator, error) {
+func (l *loader) iteratorForType(ctx context.Context, root graph.IteratorShape, rt reflect.Type, rootOnly bool) (graph.IteratorShape, error) {
 	p, err := l.makePathForType(rt, "", rootOnly)
 	if err != nil {
 		return nil, err
 	}
-	return l.iteratorFromPath(root, p)
+	return l.iteratorFromPath(ctx, root, p)
 }
 
 func mergeMap(dst map[string][]graph.Ref, m map[string]graph.Ref) {
@@ -411,7 +411,7 @@ loop:
 	}
 }
 
-func (l *loader) loadIteratorToDepth(ctx context.Context, dst reflect.Value, depth int, list graph.Iterator) error {
+func (l *loader) loadIteratorToDepth(ctx context.Context, dst reflect.Value, depth int, list graph.IteratorShape) error {
 	if ctx == nil {
 		ctx = context.TODO()
 	}
@@ -447,10 +447,11 @@ func (l *loader) loadIteratorToDepth(ctx context.Context, dst reflect.Value, dep
 	}
 
 	rootOnly := depth == 0
-	it, err := l.iteratorForType(list, et, rootOnly)
+	its, err := l.iteratorForType(ctx, list, et, rootOnly)
 	if err != nil {
 		return err
 	}
+	it := its.Iterate()
 	defer it.Close()
 
 	ctx = context.WithValue(ctx, fieldsCtxKey{}, fields)
@@ -532,8 +533,7 @@ func (l *loader) loadIteratorToDepth(ctx context.Context, dst reflect.Value, dep
 	}
 	if list != nil { // TODO(dennwc): optional optimization: do this only if iterator is not "all nodes"
 		// distinguish between missing object and type constraints
-		list.Reset()
-		and := iterator.NewAnd(list, l.qs.NodesAllIterator())
+		and := iterator.NewAnd(list, l.qs.NodesAllIterator()).Iterate()
 		defer and.Close()
 		if and.Next(ctx) {
 			return errRequiredFieldIsMissing
@@ -542,13 +542,13 @@ func (l *loader) loadIteratorToDepth(ctx context.Context, dst reflect.Value, dep
 	return errNotFound
 }
 
-func (l *loader) iteratorFromPath(root graph.Iterator, p *path.Path) (graph.Iterator, error) {
+func (l *loader) iteratorFromPath(ctx context.Context, root graph.IteratorShape, p *path.Path) (graph.IteratorShape, error) {
 	it := p.BuildIteratorOn(l.qs)
 	if root != nil {
 		it = iterator.NewAnd(root, it)
 	}
 	if Optimize {
-		it, _ = it.Optimize()
+		it, _ = it.Optimize(ctx)
 	}
 	return it, nil
 }
diff --git a/server/http/api_v2.go b/server/http/api_v2.go
index b9cbc25..b6f3fa8 100644
--- a/server/http/api_v2.go
+++ b/server/http/api_v2.go
@@ -330,7 +330,7 @@ func (api *APIv2) ServeRead(w http.ResponseWriter, r *http.Request) {
 		valuesFromString(r.FormValue("obj")),
 		valuesFromString(r.FormValue("label")),
 	)
-	it := values.BuildIterator(h.QuadStore)
+	it := values.BuildIterator(h.QuadStore).Iterate()
 	qr := graph.NewResultReader(h.QuadStore, it)
 
 	defer qr.Close()
diff --git a/writer/single.go b/writer/single.go
index e08c402..42a58d4 100644
--- a/writer/single.go
+++ b/writer/single.go
@@ -92,7 +92,7 @@ func (s *Single) RemoveNode(v quad.Value) error {
 	total := 0
 	// TODO(dennwc): QuadStore may remove node without iterations. Consider optional interface for this.
 	for _, d := range []quad.Direction{quad.Subject, quad.Predicate, quad.Object, quad.Label} {
-		r := graph.NewResultReader(s.qs, s.qs.QuadIterator(d, gv))
+		r := graph.NewResultReader(s.qs, s.qs.QuadIterator(d, gv).Iterate())
 		n, err := quad.Copy(del, r)
 		r.Close()
 		if err != nil {


Test patch:
diff --git a/graph/graphtest/graphtest.go b/graph/graphtest/graphtest.go
index 2cd3b78..02a8fb5 100644
--- a/graph/graphtest/graphtest.go
+++ b/graph/graphtest/graphtest.go
@@ -126,7 +126,13 @@ func MakeQuadSet() []quad.Quad {
 	}
 }
 
-func IteratedQuads(t testing.TB, qs graph.QuadStore, it graph.Iterator) []quad.Quad {
+func IteratedQuads(t testing.TB, qs graph.QuadStore, s graph.IteratorShape) []quad.Quad {
+	it := s.Iterate()
+	defer it.Close()
+	return IteratedQuadsNext(t, qs, it)
+}
+
+func IteratedQuadsNext(t testing.TB, qs graph.QuadStore, it graph.Scanner) []quad.Quad {
 	ctx := context.TODO()
 	var res quad.ByQuadString
 	for it.Next(ctx) {
@@ -140,7 +146,7 @@ func IteratedQuads(t testing.TB, qs graph.QuadStore, it graph.Iterator) []quad.Q
 	return res
 }
 
-func ExpectIteratedQuads(t testing.TB, qs graph.QuadStore, it graph.Iterator, exp []quad.Quad, sortQuads bool) {
+func ExpectIteratedQuads(t testing.TB, qs graph.QuadStore, it graph.IteratorShape, exp []quad.Quad, sortQuads bool) {
 	got := IteratedQuads(t, qs, it)
 	if sortQuads {
 		sort.Sort(quad.ByQuadString(exp))
@@ -152,14 +158,14 @@ func ExpectIteratedQuads(t testing.TB, qs graph.QuadStore, it graph.Iterator, ex
 	require.Equal(t, exp, got)
 }
 
-func ExpectIteratedRawStrings(t testing.TB, qs graph.QuadStore, it graph.Iterator, exp []string) {
+func ExpectIteratedRawStrings(t testing.TB, qs graph.QuadStore, it graph.IteratorShape, exp []string) {
 	//sort.Strings(exp)
 	got := IteratedStrings(t, qs, it)
 	//sort.Strings(got)
 	require.Equal(t, exp, got)
 }
 
-func ExpectIteratedValues(t testing.TB, qs graph.QuadStore, it graph.Iterator, exp []quad.Value, sortVals bool) {
+func ExpectIteratedValues(t testing.TB, qs graph.QuadStore, it graph.IteratorShape, exp []quad.Value, sortVals bool) {
 	//sort.Strings(exp)
 	got := IteratedValues(t, qs, it)
 	//sort.Strings(got)
@@ -178,8 +184,10 @@ func ExpectIteratedValues(t testing.TB, qs graph.QuadStore, it graph.Iterator, e
 	}
 }
 
-func IteratedStrings(t testing.TB, qs graph.QuadStore, it graph.Iterator) []string {
+func IteratedStrings(t testing.TB, qs graph.QuadStore, s graph.IteratorShape) []string {
 	ctx := context.TODO()
+	it := s.Iterate()
+	defer it.Close()
 	var res []string
 	for it.Next(ctx) {
 		res = append(res, quad.ToString(qs.NameOf(it.Result())))
@@ -189,8 +197,9 @@ func IteratedStrings(t testing.TB, qs graph.QuadStore, it graph.Iterator) []stri
 	return res
 }
 
-func IteratedValues(t testing.TB, qs graph.QuadStore, it graph.Iterator) []quad.Value {
+func IteratedValues(t testing.TB, qs graph.QuadStore, s graph.IteratorShape) []quad.Value {
 	ctx := context.TODO()
+	it := s.Iterate()
 	var res []quad.Value
 	for it.Next(ctx) {
 		res = append(res, qs.NameOf(it.Result()))
@@ -223,8 +232,8 @@ func TestLoadOneQuad(t testing.TB, gen testutil.DatabaseFunc, c *Config) {
 		require.Equal(t, pq, val, "quad store failed to roundtrip value: %q", pq)
 	}
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 4, Exact: true},
-		Quads: graph.Size{Size: 1, Exact: true},
+		Nodes: graph.Size{Value: 4, Exact: true},
+		Quads: graph.Size{Value: 1, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -257,8 +266,8 @@ func testLoadDup(t testing.TB, gen testutil.DatabaseFunc, c *Config, single bool
 	}
 
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 4, Exact: true},
-		Quads: graph.Size{Size: 1, Exact: true},
+		Nodes: graph.Size{Value: 4, Exact: true},
+		Quads: graph.Size{Value: 1, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -293,8 +302,8 @@ func TestLoadDupRaw(t testing.TB, gen testutil.DatabaseFunc, c *Config) {
 	require.NoError(t, err)
 
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 4, Exact: true},
-		Quads: graph.Size{Size: 1, Exact: true},
+		Nodes: graph.Size{Value: 4, Exact: true},
+		Quads: graph.Size{Value: 1, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -472,8 +481,8 @@ func TestSizes(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 	require.NoError(t, err)
 
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 11, Exact: true},
-		Quads: graph.Size{Size: 11, Exact: true},
+		Nodes: graph.Size{Value: 11, Exact: true},
+		Quads: graph.Size{Value: 11, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -500,16 +509,16 @@ func TestSizes(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 	require.True(t, graph.IsQuadNotExist(err))
 	if !conf.SkipSizeCheckAfterDelete {
 		exp = graph.Stats{
-			Nodes: graph.Size{Size: 10, Exact: true},
-			Quads: graph.Size{Size: 10, Exact: true},
+			Nodes: graph.Size{Value: 10, Exact: true},
+			Quads: graph.Size{Value: 10, Exact: true},
 		}
 		st, err := qs.Stats(context.Background(), true)
 		require.NoError(t, err)
 		require.Equal(t, exp, st, "Unexpected quadstore size after RemoveQuad")
 	} else {
 		exp = graph.Stats{
-			Nodes: graph.Size{Size: 10, Exact: true},
-			Quads: graph.Size{Size: 11, Exact: true},
+			Nodes: graph.Size{Value: 10, Exact: true},
+			Quads: graph.Size{Value: 11, Exact: true},
 		}
 		st, err := qs.Stats(context.Background(), true)
 		require.NoError(t, err)
@@ -529,19 +538,16 @@ func TestIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 
 	testutil.MakeWriter(t, qs, opts, MakeQuadSet()...)
 
-	var it graph.Iterator
+	var it graph.IteratorShape
 
 	it = qs.NodesAllIterator()
 	require.NotNil(t, it)
 
-	size, _ := it.Size()
+	st, _ := it.Stats(ctx)
+	size := st.Size.Value
 	require.True(t, size > 0 && size < 23, "Unexpected size: %v", size)
-	// TODO: leveldb had this test
-	//if exact {
-	//	t.Errorf("Got unexpected exact result.")
-	//}
 
-	optIt, changed := it.Optimize()
+	optIt, changed := it.Optimize(ctx)
 	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T(%p) vs %T(%p)", changed, optIt, optIt, it, it)
 
 	expect := []string{
@@ -562,12 +568,13 @@ func TestIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 		got := IteratedStrings(t, qs, it)
 		sort.Strings(got)
 		require.Equal(t, expect, got, "Unexpected iterated result on repeat %d", i)
-		it.Reset()
 	}
 
+	itc := it.Lookup()
+	defer itc.Close()
 	for _, pq := range expect {
-		ok := it.Contains(ctx, qs.ValueOf(quad.Raw(pq)))
-		require.NoError(t, it.Err())
+		ok := itc.Contains(ctx, qs.ValueOf(quad.Raw(pq)))
+		require.NoError(t, itc.Err())
 		require.True(t, ok, "Failed to find and check %q correctly", pq)
 
 	}
@@ -579,16 +586,17 @@ func TestIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 			}
 		}
 	*/
-	it.Reset()
 
 	it = qs.QuadsAllIterator()
-	optIt, changed = it.Optimize()
+	optIt, changed = it.Optimize(ctx)
 	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T", changed, optIt)
 
-	require.True(t, it.Next(ctx))
+	itn := it.Iterate()
+	defer itn.Close()
+	require.True(t, itn.Next(ctx))
 
-	q := qs.Quad(it.Result())
-	require.Nil(t, it.Err())
+	q := qs.Quad(itn.Result())
+	require.Nil(t, itn.Err())
 	require.True(t, q.IsValid(), "Invalid quad returned: %q", q)
 	set := MakeQuadSet()
 	var ok bool
@@ -607,12 +615,11 @@ func TestHasA(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 
 	testutil.MakeWriter(t, qs, opts, MakeQuadSet()...)
 
-	var it graph.Iterator = iterator.NewHasA(qs,
+	var it graph.IteratorShape = iterator.NewHasA(qs,
 		iterator.NewLinksTo(qs, qs.NodesAllIterator(), quad.Predicate),
 		quad.Predicate)
-	defer it.Close()
 
-	it, _ = it.Optimize()
+	it, _ = it.Optimize(context.TODO())
 
 	var exp []quad.Value
 	for i := 0; i < 8; i++ {
@@ -630,7 +637,7 @@ func TestSetIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 
 	testutil.MakeWriter(t, qs, opts, MakeQuadSet()...)
 
-	expectIteratedQuads := func(it graph.Iterator, exp []quad.Quad) {
+	expectIteratedQuads := func(it graph.IteratorShape, exp []quad.Quad) {
 		ExpectIteratedQuads(t, qs, it, exp, false)
 	}
 
@@ -641,7 +648,6 @@ func TestSetIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 		quad.Make("C", "follows", "B", nil),
 		quad.Make("C", "follows", "D", nil),
 	})
-	it.Reset()
 
 	and := iterator.NewAnd(
 		qs.QuadsAllIterator(),
@@ -687,7 +693,6 @@ func TestSetIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 		quad.Make("D", "status", "cool", "status_graph"),
 		quad.Make("G", "status", "cool", "status_graph"),
 	})
-	it.Reset()
 
 	// Order is important
 	and = iterator.NewAnd(
@@ -698,7 +703,6 @@ func TestSetIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 	expectIteratedQuads(and, []quad.Quad{
 		quad.Make("B", "status", "cool", "status_graph"),
 	})
-	it.Reset()
 
 	// Order is important
 	and = iterator.NewAnd(
@@ -724,14 +728,12 @@ func TestDeleteQuad(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 	ExpectIteratedQuads(t, qs, it, []quad.Quad{
 		quad.Make("E", "follows", "F", nil),
 	}, false)
-	it.Close()
 
 	err := w.RemoveQuad(quad.Make("E", "follows", "F", nil))
 	require.NoError(t, err)
 
 	it = qs.QuadIterator(quad.Subject, qs.ValueOf(quad.Raw("E")))
 	ExpectIteratedQuads(t, qs, it, nil, false)
-	it.Close()
 
 	it = qs.QuadsAllIterator()
 	ExpectIteratedQuads(t, qs, it, []quad.Quad{
@@ -746,7 +748,6 @@ func TestDeleteQuad(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 		quad.Make("D", "status", "cool", "status_graph"),
 		quad.Make("G", "status", "cool", "status_graph"),
 	}, true)
-	it.Close()
 }
 
 func TestDeletedFromIterator(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
@@ -765,8 +766,6 @@ func TestDeletedFromIterator(t testing.TB, gen testutil.DatabaseFunc, conf *Conf
 		quad.Make("E", "follows", "F", nil),
 	}, false)
 
-	it.Reset()
-
 	w.RemoveQuad(quad.Make("E", "follows", "F", nil))
 
 	ExpectIteratedQuads(t, qs, it, nil, false)
@@ -834,8 +833,8 @@ func TestLoadTypedQuads(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 		}
 	}
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 12, Exact: true},
-		Quads: graph.Size{Size: 7, Exact: true},
+		Nodes: graph.Size{Value: 12, Exact: true},
+		Quads: graph.Size{Value: 7, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -856,8 +855,8 @@ func TestAddRemove(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 	w := testutil.MakeWriter(t, qs, opts, MakeQuadSet()...)
 
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 11, Exact: true},
-		Quads: graph.Size{Size: 11, Exact: true},
+		Nodes: graph.Size{Value: 11, Exact: true},
+		Quads: graph.Size{Value: 11, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -889,8 +888,8 @@ func TestAddRemove(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 	assert.Nil(t, err, "AddQuadSet failed")
 
 	exp = graph.Stats{
-		Nodes: graph.Size{Size: 12, Exact: true},
-		Quads: graph.Size{Size: 13, Exact: true},
+		Nodes: graph.Size{Value: 12, Exact: true},
+		Quads: graph.Size{Value: 13, Exact: true},
 	}
 	st, err = qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -933,7 +932,6 @@ func TestAddRemove(t testing.TB, gen testutil.DatabaseFunc, conf *Config) {
 		"status",
 		"status_graph",
 	}
-	ExpectIteratedRawStrings(t, qs, all, nil)
 	all = qs.NodesAllIterator()
 	ExpectIteratedRawStrings(t, qs, all, expect)
 }
@@ -946,8 +944,8 @@ func TestIteratorsAndNextResultOrderA(t testing.TB, gen testutil.DatabaseFunc, c
 	testutil.MakeWriter(t, qs, opts, MakeQuadSet()...)
 
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 11, Exact: true},
-		Quads: graph.Size{Size: 11, Exact: true},
+		Nodes: graph.Size{Value: 11, Exact: true},
+		Quads: graph.Size{Value: 11, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -966,7 +964,7 @@ func TestIteratorsAndNextResultOrderA(t testing.TB, gen testutil.DatabaseFunc, c
 	)
 
 	hasa := iterator.NewHasA(qs, innerAnd, quad.Subject)
-	outerAnd := iterator.NewAnd(fixed, hasa)
+	outerAnd := iterator.NewAnd(fixed, hasa).Iterate()
 
 	require.True(t, outerAnd.Next(ctx), "Expected one matching subtree")
 
diff --git a/graph/iterator/and_optimize_test.go b/graph/iterator/and_optimize_test.go
index e902812..31ae473 100644
--- a/graph/iterator/and_optimize_test.go
+++ b/graph/iterator/and_optimize_test.go
@@ -18,16 +18,18 @@ package iterator_test
 // nonetheless cover a lot of basic cases.
 
 import (
+	"context"
 	"testing"
 
 	. "github.com/cayleygraph/cayley/graph/iterator"
+	"github.com/stretchr/testify/require"
 )
 
 func TestNullIteratorAnd(t *testing.T) {
 	all := newInt64(1, 3, true)
 	null := NewNull()
 	a := NewAnd(all, null)
-	newIt, changed := a.Optimize()
+	newIt, changed := a.Optimize(context.TODO())
 	if !changed {
 		t.Error("Didn't change")
 	}
@@ -49,11 +51,8 @@ func TestReorderWithTag(t *testing.T) {
 	a.AddSubIterator(all2)
 	a.AddSubIterator(all)
 
-	newIt, changed := a.Optimize()
-	if !changed {
-		t.Error("Expected new iterator")
-	}
-	newIt.Close()
+	_, changed := a.Optimize(context.TODO())
+	require.True(t, changed, "expected new iterator")
 }
 
 func TestAndStatistics(t *testing.T) {
@@ -63,12 +62,12 @@ func TestAndStatistics(t *testing.T) {
 	// Make all2 the default iterator
 	a.AddSubIterator(all2)
 	a.AddSubIterator(all)
-	stats1 := a.Stats()
-	newIt, changed := a.Optimize()
-	if !changed {
-		t.Error("Didn't optimize")
-	}
-	stats2 := newIt.Stats()
+	ctx := context.TODO()
+	stats1, _ := a.Stats(ctx)
+	newIt, changed := a.Optimize(ctx)
+	require.True(t, changed, "didn't optimize")
+
+	stats2, _ := newIt.Stats(ctx)
 	if stats2.NextCost > stats1.NextCost {
 		t.Error("And didn't optimize. Next cost old ", stats1.NextCost, "and new ", stats2.NextCost)
 	}
diff --git a/graph/iterator/and_test.go b/graph/iterator/and_test.go
index 67f43d3..15b2b0b 100644
--- a/graph/iterator/and_test.go
+++ b/graph/iterator/and_test.go
@@ -19,6 +19,8 @@ import (
 	"errors"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph"
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
@@ -28,27 +30,20 @@ func TestAndTag(t *testing.T) {
 	ctx := context.TODO()
 	fix1 := NewFixed(Int64Node(234))
 	fix2 := NewFixed(Int64Node(234))
-	var and graph.Iterator = NewAnd(Tag(fix1, "foo")).AddOptionalIterator(Tag(fix2, "baz"))
-	and = Tag(and, "bar")
-
-	if !and.Next(ctx) {
-		t.Errorf("And did not next")
-	}
-	val := and.Result()
-	if val.(Int64Node) != 234 {
-		t.Errorf("Unexpected value")
-	}
+	var ands graph.IteratorShape = NewAnd(Tag(fix1, "foo")).AddOptionalIterator(Tag(fix2, "baz"))
+	ands = Tag(ands, "bar")
+
+	and := ands.Iterate()
+	require.True(t, and.Next(ctx))
+	require.Equal(t, Int64Node(234), and.Result())
+
 	tags := make(map[string]graph.Ref)
 	and.TagResults(tags)
-	if tags["bar"].(Int64Node) != 234 {
-		t.Errorf("no bar tag")
-	}
-	if tags["foo"].(Int64Node) != 234 {
-		t.Errorf("no foo tag")
-	}
-	if tags["baz"].(Int64Node) != 234 {
-		t.Errorf("no baz tag")
-	}
+	require.Equal(t, map[string]graph.Ref{
+		"foo": Int64Node(234),
+		"bar": Int64Node(234),
+		"baz": Int64Node(234),
+	}, tags)
 }
 
 // Do a simple itersection of fixed values.
@@ -65,28 +60,24 @@ func TestAndAndFixedIterators(t *testing.T) {
 		Int64Node(4),
 		Int64Node(5),
 	)
-	and := NewAnd(fix1, fix2)
+	ands := NewAnd(fix1, fix2)
 	// Should be as big as smallest subiterator
-	size, accurate := and.Size()
-	if size != 3 {
-		t.Error("Incorrect size:", size)
-	}
-	if !accurate {
-		t.Error("not accurate")
-	}
-
-	if !and.Next(ctx) || and.Result().(Int64Node) != 3 {
-		t.Error("Incorrect first value")
-	}
-
-	if !and.Next(ctx) || and.Result().(Int64Node) != 4 {
-		t.Error("Incorrect second value")
-	}
-
-	if and.Next(ctx) {
-		t.Error("Too many values")
-	}
+	st, err := ands.Stats(ctx)
+	require.NoError(t, err)
+	require.Equal(t, graph.Size{
+		Value: 3,
+		Exact: true,
+	}, st.Size)
+
+	and := ands.Iterate()
 
+	require.True(t, and.Next(ctx))
+	require.Equal(t, Int64Node(3), and.Result())
+
+	require.True(t, and.Next(ctx))
+	require.Equal(t, Int64Node(4), and.Result())
+
+	require.False(t, and.Next(ctx))
 }
 
 // If there's no intersection, the size should still report the same,
@@ -104,39 +95,32 @@ func TestNonOverlappingFixedIterators(t *testing.T) {
 		Int64Node(6),
 		Int64Node(7),
 	)
-	and := NewAnd(fix1, fix2)
+	ands := NewAnd(fix1, fix2)
 	// Should be as big as smallest subiterator
-	size, accurate := and.Size()
-	if size != 3 {
-		t.Error("Incorrect size")
-	}
-	if !accurate {
-		t.Error("not accurate")
-	}
-
-	if and.Next(ctx) {
-		t.Error("Too many values")
-	}
-
+	st, err := ands.Stats(ctx)
+	require.NoError(t, err)
+	require.Equal(t, graph.Size{
+		Value: 3,
+		Exact: true,
+	}, st.Size)
+
+	and := ands.Iterate()
+	require.False(t, and.Next(ctx))
 }
 
 func TestAllIterators(t *testing.T) {
 	ctx := context.TODO()
 	all1 := newInt64(1, 5, true)
 	all2 := newInt64(4, 10, true)
-	and := NewAnd(all2, all1)
+	and := NewAnd(all2, all1).Iterate()
 
-	if !and.Next(ctx) || and.Result().(Int64Node) != Int64Node(4) {
-		t.Error("Incorrect first value")
-	}
+	require.True(t, and.Next(ctx))
+	require.Equal(t, Int64Node(4), and.Result())
 
-	if !and.Next(ctx) || and.Result().(Int64Node) != Int64Node(5) {
-		t.Error("Incorrect second value")
-	}
+	require.True(t, and.Next(ctx))
+	require.Equal(t, Int64Node(5), and.Result())
 
-	if and.Next(ctx) {
-		t.Error("Too many values")
-	}
+	require.False(t, and.Next(ctx))
 }
 
 func TestAndIteratorErr(t *testing.T) {
@@ -147,12 +131,8 @@ func TestAndIteratorErr(t *testing.T) {
 	and := NewAnd(
 		allErr,
 		newInt64(1, 5, true),
-	)
+	).Iterate()
 
-	if and.Next(ctx) != false {
-		t.Errorf("And iterator did not pass through initial 'false'")
-	}
-	if and.Err() != wantErr {
-		t.Errorf("And iterator did not pass through underlying Err: %v", and.Err())
-	}
+	require.False(t, and.Next(ctx))
+	require.Equal(t, wantErr, and.Err())
 }
diff --git a/graph/iterator/count_test.go b/graph/iterator/count_test.go
index 354f583..a260e98 100644
--- a/graph/iterator/count_test.go
+++ b/graph/iterator/count_test.go
@@ -18,23 +18,29 @@ func TestCount(t *testing.T) {
 		graph.PreFetched(quad.String("d")),
 		graph.PreFetched(quad.String("e")),
 	)
-	it := NewCount(fixed, nil)
-	require.True(t, it.Next(ctx))
-	require.Equal(t, graph.PreFetched(quad.Int(5)), it.Result())
-	require.False(t, it.Next(ctx))
-	require.True(t, it.Contains(ctx, graph.PreFetched(quad.Int(5))))
-	require.False(t, it.Contains(ctx, graph.PreFetched(quad.Int(3))))
+	its := NewCount(fixed, nil)
 
-	fixed.Reset()
+	itn := its.Iterate()
+	require.True(t, itn.Next(ctx))
+	require.Equal(t, graph.PreFetched(quad.Int(5)), itn.Result())
+	require.False(t, itn.Next(ctx))
+
+	itc := its.Lookup()
+	require.True(t, itc.Contains(ctx, graph.PreFetched(quad.Int(5))))
+	require.False(t, itc.Contains(ctx, graph.PreFetched(quad.Int(3))))
 
 	fixed2 := NewFixed(
 		graph.PreFetched(quad.String("b")),
 		graph.PreFetched(quad.String("d")),
 	)
-	it = NewCount(NewAnd(fixed, fixed2), nil)
-	require.True(t, it.Next(ctx))
-	require.Equal(t, graph.PreFetched(quad.Int(2)), it.Result())
-	require.False(t, it.Next(ctx))
-	require.False(t, it.Contains(ctx, graph.PreFetched(quad.Int(5))))
-	require.True(t, it.Contains(ctx, graph.PreFetched(quad.Int(2))))
+	its = NewCount(NewAnd(fixed, fixed2), nil)
+
+	itn = its.Iterate()
+	require.True(t, itn.Next(ctx))
+	require.Equal(t, graph.PreFetched(quad.Int(2)), itn.Result())
+	require.False(t, itn.Next(ctx))
+
+	itc = its.Lookup()
+	require.False(t, itc.Contains(ctx, graph.PreFetched(quad.Int(5))))
+	require.True(t, itc.Contains(ctx, graph.PreFetched(quad.Int(2))))
 }
diff --git a/graph/iterator/hasa_test.go b/graph/iterator/hasa_test.go
index b1e6df0..1bbbfba 100644
--- a/graph/iterator/hasa_test.go
+++ b/graph/iterator/hasa_test.go
@@ -30,7 +30,7 @@ func TestHasAIteratorErr(t *testing.T) {
 	errIt := newTestIterator(false, wantErr)
 
 	// TODO(andrew-d): pass a non-nil quadstore
-	hasa := NewHasA(nil, errIt, quad.Subject)
+	hasa := NewHasA(nil, errIt, quad.Subject).Iterate()
 
 	require.False(t, hasa.Next(ctx), "HasA iterator did not pass through initial 'false'")
 	require.Equal(t, wantErr, hasa.Err(), "HasA iterator did not pass through underlying Err")
diff --git a/graph/iterator/iterator_test.go b/graph/iterator/iterator_test.go
index 05a0f9a..d1ba5da 100644
--- a/graph/iterator/iterator_test.go
+++ b/graph/iterator/iterator_test.go
@@ -10,25 +10,65 @@ import (
 
 // A testing iterator that returns the given values for Next() and Err().
 type testIterator struct {
-	graph.Iterator
+	graph.IteratorShape
 
 	NextVal bool
 	ErrVal  error
 }
 
-func newTestIterator(next bool, err error) graph.Iterator {
+func newTestIterator(next bool, err error) graph.IteratorShape {
 	return &testIterator{
-		Iterator: NewFixed(),
-		NextVal:  next,
-		ErrVal:   err,
+		IteratorShape: NewFixed(),
+		NextVal:       next,
+		ErrVal:        err,
 	}
 }
 
-func (it *testIterator) Next(ctx context.Context) bool {
+func (it *testIterator) Iterate() graph.Scanner {
+	return &testIteratorNext{
+		Scanner: it.IteratorShape.Iterate(),
+		NextVal: it.NextVal,
+		ErrVal:  it.ErrVal,
+	}
+}
+
+func (it *testIterator) Lookup() graph.Index {
+	return &testIteratorContains{
+		Index:   it.IteratorShape.Lookup(),
+		NextVal: it.NextVal,
+		ErrVal:  it.ErrVal,
+	}
+}
+
+// A testing iterator that returns the given values for Next() and Err().
+type testIteratorNext struct {
+	graph.Scanner
+
+	NextVal bool
+	ErrVal  error
+}
+
+func (it *testIteratorNext) Next(ctx context.Context) bool {
 	return it.NextVal
 }
 
-func (it *testIterator) Err() error {
+func (it *testIteratorNext) Err() error {
+	return it.ErrVal
+}
+
+// A testing iterator that returns the given values for Next() and Err().
+type testIteratorContains struct {
+	graph.Index
+
+	NextVal bool
+	ErrVal  error
+}
+
+func (it *testIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
+	return it.NextVal
+}
+
+func (it *testIteratorContains) Err() error {
 	return it.ErrVal
 }
 
@@ -38,15 +78,20 @@ func (v Int64Quad) Key() interface{} { return v }
 
 func (Int64Quad) IsNode() bool { return false }
 
-var _ graph.Iterator = &Int64{}
+var _ graph.IteratorShape = &Int64{}
 
 // An All iterator across a range of int64 values, from `max` to `min`.
 type Int64 struct {
 	node     bool
 	max, min int64
-	at       int64
-	result   int64
-	runstats graph.IteratorStats
+}
+
+func (it *Int64) Iterate() graph.Scanner {
+	return newInt64Next(it.min, it.max, it.node)
+}
+
+func (it *Int64) Lookup() graph.Index {
+	return newInt64Contains(it.min, it.max, it.node)
 }
 
 // Creates a new Int64 with the given range.
@@ -55,29 +100,80 @@ func newInt64(min, max int64, node bool) *Int64 {
 		node: node,
 		min:  min,
 		max:  max,
-		at:   min,
 	}
 }
 
-// Start back at the beginning
-func (it *Int64) Reset() {
-	it.at = it.min
+func (it *Int64) String() string {
+	return fmt.Sprintf("Int64(%d-%d)", it.min, it.max)
 }
 
-func (it *Int64) Close() error {
+// No sub-iterators.
+func (it *Int64) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *Int64) TagResults(dst map[string]graph.Ref) {}
+// The number of elements in an Int64 is the size of the range.
+// The size is exact.
+func (it *Int64) Size() (int64, bool) {
+	sz := (it.max - it.min) + 1
+	return sz, true
+}
 
-func (it *Int64) String() string {
+func valToInt64(v graph.Ref) int64 {
+	if v, ok := v.(Int64Node); ok {
+		return int64(v)
+	}
+	return int64(v.(Int64Quad))
+}
+
+// There's nothing to optimize about this little iterator.
+func (it *Int64) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
+
+// Stats for an Int64 are simple. Super cheap to do any operation,
+// and as big as the range.
+func (it *Int64) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	s, exact := it.Size()
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     1,
+		Size: graph.Size{
+			Value: s,
+			Exact: exact,
+		},
+	}, nil
+}
+
+// An All iterator across a range of int64 values, from `max` to `min`.
+type int64Next struct {
+	node     bool
+	max, min int64
+	at       int64
+	result   int64
+}
+
+// Creates a new Int64 with the given range.
+func newInt64Next(min, max int64, node bool) *int64Next {
+	return &int64Next{
+		node: node,
+		min:  min,
+		max:  max,
+		at:   min,
+	}
+}
+
+func (it *int64Next) Close() error {
+	return nil
+}
+
+func (it *int64Next) TagResults(dst map[string]graph.Ref) {}
+
+func (it *int64Next) String() string {
 	return fmt.Sprintf("Int64(%d-%d)", it.min, it.max)
 }
 
 // Next() on an Int64 all iterator is a simple incrementing counter.
 // Return the next integer, and mark it as the result.
-func (it *Int64) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
+func (it *int64Next) Next(ctx context.Context) bool {
 	if it.at == -1 {
 		return false
 	}
@@ -90,48 +186,80 @@ func (it *Int64) Next(ctx context.Context) bool {
 	return true
 }
 
-func (it *Int64) Err() error {
+func (it *int64Next) Err() error {
 	return nil
 }
 
-func (it *Int64) toValue(v int64) graph.Ref {
+func (it *int64Next) toValue(v int64) graph.Ref {
 	if it.node {
 		return Int64Node(v)
 	}
 	return Int64Quad(v)
 }
 
-func (it *Int64) Result() graph.Ref {
+func (it *int64Next) Result() graph.Ref {
 	return it.toValue(it.result)
 }
 
-func (it *Int64) NextPath(ctx context.Context) bool {
+func (it *int64Next) NextPath(ctx context.Context) bool {
 	return false
 }
 
-// No sub-iterators.
-func (it *Int64) SubIterators() []graph.Iterator {
+// An All iterator across a range of int64 values, from `max` to `min`.
+type int64Contains struct {
+	node     bool
+	max, min int64
+	at       int64
+	result   int64
+}
+
+// Creates a new Int64 with the given range.
+func newInt64Contains(min, max int64, node bool) *int64Contains {
+	return &int64Contains{
+		node: node,
+		min:  min,
+		max:  max,
+		at:   min,
+	}
+}
+
+func (it *int64Contains) Close() error {
 	return nil
 }
 
-// The number of elements in an Int64 is the size of the range.
-// The size is exact.
-func (it *Int64) Size() (int64, bool) {
-	sz := (it.max - it.min) + 1
-	return sz, true
+func (it *int64Contains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *int64Contains) String() string {
+	return fmt.Sprintf("Int64(%d-%d)", it.min, it.max)
 }
 
-func valToInt64(v graph.Ref) int64 {
-	if v, ok := v.(Int64Node); ok {
-		return int64(v)
+func (it *int64Contains) Err() error {
+	return nil
+}
+
+func (it *int64Contains) toValue(v int64) graph.Ref {
+	if it.node {
+		return Int64Node(v)
 	}
-	return int64(v.(Int64Quad))
+	return Int64Quad(v)
+}
+
+func (it *int64Contains) Result() graph.Ref {
+	return it.toValue(it.result)
+}
+
+func (it *int64Contains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+// No sub-iterators.
+func (it *int64Contains) SubIterators() []graph.IteratorShape {
+	return nil
 }
 
 // Contains() for an Int64 is merely seeing if the passed value is
 // within the range, assuming the value is an int64.
-func (it *Int64) Contains(ctx context.Context, tsv graph.Ref) bool {
-	it.runstats.Contains += 1
+func (it *int64Contains) Contains(ctx context.Context, tsv graph.Ref) bool {
 	v := valToInt64(tsv)
 	if it.min <= v && v <= it.max {
 		it.result = v
@@ -139,20 +267,3 @@ func (it *Int64) Contains(ctx context.Context, tsv graph.Ref) bool {
 	}
 	return false
 }
-
-// There's nothing to optimize about this little iterator.
-func (it *Int64) Optimize() (graph.Iterator, bool) { return it, false }
-
-// Stats for an Int64 are simple. Super cheap to do any operation,
-// and as big as the range.
-func (it *Int64) Stats() graph.IteratorStats {
-	s, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: 1,
-		NextCost:     1,
-		Size:         s,
-		ExactSize:    exact,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-	}
-}
diff --git a/graph/iterator/limit_test.go b/graph/iterator/limit_test.go
index f94aa6d..55f2052 100644
--- a/graph/iterator/limit_test.go
+++ b/graph/iterator/limit_test.go
@@ -2,9 +2,10 @@ package iterator_test
 
 import (
 	"context"
-	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
@@ -19,42 +20,25 @@ func TestLimitIteratorBasics(t *testing.T) {
 	)
 
 	u := NewLimit(allIt, 0)
-	expectSz, _ := allIt.Size()
-	if sz, _ := u.Size(); sz != expectSz {
-		t.Errorf("Failed to check Limit size: got:%v expected:%v", sz, expectSz)
-	}
-	expect := []int{1, 2, 3, 4, 5}
-	if got := iterated(u); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate Limit correctly: got:%v expected:%v", got, expect)
-	}
-
-	allIt.Reset()
+	expectSz, _ := allIt.Stats(ctx)
+	sz, _ := u.Stats(ctx)
+	require.Equal(t, expectSz.Size.Value, sz.Size.Value)
+	require.Equal(t, []int{1, 2, 3, 4, 5}, iterated(u))
 
 	u = NewLimit(allIt, 3)
-	expectSz = 3
-	if sz, _ := u.Size(); sz != expectSz {
-		t.Errorf("Failed to check Limit size: got:%v expected:%v", sz, expectSz)
-	}
-	expect = []int{1, 2, 3}
-	if got := iterated(u); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate Limit correctly: got:%v expected:%v", got, expect)
-	}
+	sz, _ = u.Stats(ctx)
+	require.Equal(t, int64(3), sz.Size.Value)
+	require.Equal(t, []int{1, 2, 3}, iterated(u))
 
+	uc := u.Lookup()
 	for _, v := range []int{1, 2, 3} {
-		if !u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Limit iterator.")
-		}
-	}
-	if u.Contains(ctx, Int64Node(4)) {
-		t.Error("should have no more results")
+		require.True(t, uc.Contains(ctx, Int64Node(v)))
 	}
-	u.Reset()
+	require.False(t, uc.Contains(ctx, Int64Node(4)))
+
+	uc = u.Lookup()
 	for _, v := range []int{5, 4, 3} {
-		if !u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Limit iterator.")
-		}
-	}
-	if u.Contains(ctx, Int64Node(2)) {
-		t.Error("should have no more results")
+		require.True(t, uc.Contains(ctx, Int64Node(v)))
 	}
+	require.False(t, uc.Contains(ctx, Int64Node(2)))
 }
diff --git a/graph/iterator/linksto_test.go b/graph/iterator/linksto_test.go
index 62c94f3..8c982e1 100644
--- a/graph/iterator/linksto_test.go
+++ b/graph/iterator/linksto_test.go
@@ -18,6 +18,8 @@ import (
 	"context"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph/graphmock"
 	. "github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/quad"
@@ -31,17 +33,12 @@ func TestLinksTo(t *testing.T) {
 	}
 	qs.Iter.(*Fixed).Add(Int64Quad(2))
 	fixed := NewFixed()
+
 	val := qs.ValueOf(quad.Raw("cool"))
-	if val.(Int64Node) != 1 {
-		t.Fatalf("Failed to return correct value, got:%v expect:1", val)
-	}
+	require.Equal(t, Int64Node(1), val)
+
 	fixed.Add(val)
-	lto := NewLinksTo(qs, fixed, quad.Object)
-	if !lto.Next(ctx) {
-		t.Error("At least one quad matches the fixed object")
-	}
-	val = lto.Result()
-	if val.(Int64Quad) != 2 {
-		t.Errorf("Quad index 2, such as %s, should match %s", qs.Quad(Int64Quad(2)), qs.Quad(val))
-	}
+	lto := NewLinksTo(qs, fixed, quad.Object).Iterate()
+	require.True(t, lto.Next(ctx))
+	require.Equal(t, Int64Quad(2), lto.Result())
 }
diff --git a/graph/iterator/materialize_test.go b/graph/iterator/materialize_test.go
index 44564ff..e2ad1a4 100644
--- a/graph/iterator/materialize_test.go
+++ b/graph/iterator/materialize_test.go
@@ -19,6 +19,8 @@ import (
 	"errors"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
@@ -29,14 +31,10 @@ func TestMaterializeIteratorError(t *testing.T) {
 
 	// This tests that we properly return 0 results and the error when the
 	// underlying iterator returns an error.
-	mIt := NewMaterialize(errIt)
+	mIt := NewMaterialize(errIt).Iterate()
 
-	if mIt.Next(ctx) != false {
-		t.Errorf("Materialize iterator did not pass through underlying 'false'")
-	}
-	if mIt.Err() != wantErr {
-		t.Errorf("Materialize iterator did not pass through underlying Err")
-	}
+	require.False(t, mIt.Next(ctx))
+	require.Equal(t, wantErr, mIt.Err())
 }
 
 func TestMaterializeIteratorErrorAbort(t *testing.T) {
@@ -52,25 +50,15 @@ func TestMaterializeIteratorErrorAbort(t *testing.T) {
 		errIt,
 	)
 
-	mIt := NewMaterialize(or)
+	mIt := NewMaterialize(or).Iterate()
 
 	// We should get all the underlying values...
 	for i := 0; i < MaterializeLimit+1; i++ {
-		if !mIt.Next(ctx) {
-			t.Errorf("Materialize iterator returned spurious 'false' on iteration %d", i)
-			return
-		}
-		if mIt.Err() != nil {
-			t.Errorf("Materialize iterator returned non-nil Err on iteration %d", i)
-			return
-		}
+		require.True(t, mIt.Next(ctx))
+		require.NoError(t, mIt.Err())
 	}
 
 	// ... and then the error value.
-	if mIt.Next(ctx) != false {
-		t.Errorf("Materialize iterator did not pass through underlying 'false'")
-	}
-	if mIt.Err() != wantErr {
-		t.Errorf("Materialize iterator did not pass through underlying Err")
-	}
+	require.False(t, mIt.Next(ctx))
+	require.Equal(t, wantErr, mIt.Err())
 }
diff --git a/graph/iterator/not_test.go b/graph/iterator/not_test.go
index 79a0e7e..cc054e8 100644
--- a/graph/iterator/not_test.go
+++ b/graph/iterator/not_test.go
@@ -3,9 +3,10 @@ package iterator_test
 import (
 	"context"
 	"errors"
-	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
@@ -25,28 +26,21 @@ func TestNotIteratorBasics(t *testing.T) {
 
 	not := NewNot(toComplementIt, allIt)
 
-	if v, _ := not.Size(); v != 2 {
-		t.Errorf("Unexpected iterator size: got:%d, expected: %d", v, 2)
-	}
+	st, _ := not.Stats(ctx)
+	require.Equal(t, int64(2), st.Size.Value)
 
 	expect := []int{1, 3}
 	for i := 0; i < 2; i++ {
-		if got := iterated(not); !reflect.DeepEqual(got, expect) {
-			t.Errorf("Failed to iterate Not correctly on repeat %d: got:%v expected:%v", i, got, expect)
-		}
-		not.Reset()
+		require.Equal(t, expect, iterated(not))
 	}
 
+	nc := not.Lookup()
 	for _, v := range []int{1, 3} {
-		if !not.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as true", v)
-		}
+		require.True(t, nc.Contains(ctx, Int64Node(v)))
 	}
 
 	for _, v := range []int{2, 4} {
-		if not.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as false", v)
-		}
+		require.False(t, nc.Contains(ctx, Int64Node(v)))
 	}
 }
 
@@ -57,12 +51,8 @@ func TestNotIteratorErr(t *testing.T) {
 
 	toComplementIt := NewFixed()
 
-	not := NewNot(toComplementIt, allIt)
+	not := NewNot(toComplementIt, allIt).Iterate()
 
-	if not.Next(ctx) != false {
-		t.Errorf("Not iterator did not pass through initial 'false'")
-	}
-	if not.Err() != wantErr {
-		t.Errorf("Not iterator did not pass through underlying Err")
-	}
+	require.False(t, not.Next(ctx))
+	require.Equal(t, wantErr, not.Err())
 }
diff --git a/graph/iterator/or_test.go b/graph/iterator/or_test.go
index d0286fe..62c2584 100644
--- a/graph/iterator/or_test.go
+++ b/graph/iterator/or_test.go
@@ -17,16 +17,19 @@ package iterator_test
 import (
 	"context"
 	"errors"
-	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph"
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
-func iterated(it graph.Iterator) []int {
+func iterated(s graph.IteratorShape) []int {
 	ctx := context.TODO()
 	var res []int
+	it := s.Iterate()
+	defer it.Close()
 	for it.Next(ctx) {
 		res = append(res, int(it.Result().(Int64Node)))
 	}
@@ -50,34 +53,25 @@ func TestOrIteratorBasics(t *testing.T) {
 	or.AddSubIterator(f1)
 	or.AddSubIterator(f2)
 
-	if v, _ := or.Size(); v != 7 {
-		t.Errorf("Unexpected iterator size, got:%d expected %d", v, 7)
-	}
+	st, _ := or.Stats(ctx)
+	require.Equal(t, int64(7), st.Size.Value)
 
 	expect := []int{1, 2, 3, 3, 9, 20, 21}
 	for i := 0; i < 2; i++ {
-		if got := iterated(or); !reflect.DeepEqual(got, expect) {
-			t.Errorf("Failed to iterate Or correctly on repeat %d, got:%v expect:%v", i, got, expect)
-		}
-		or.Reset()
+		require.Equal(t, expect, iterated(or))
 	}
 
 	// Check that optimization works.
-	optOr, _ := or.Optimize()
-	if got := iterated(optOr); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate optimized Or correctly, got:%v expect:%v", got, expect)
-	}
+	optOr, _ := or.Optimize(ctx)
+	require.Equal(t, expect, iterated(optOr))
 
+	orc := or.Lookup()
 	for _, v := range []int{2, 3, 21} {
-		if !or.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as true", v)
-		}
+		require.True(t, orc.Contains(ctx, Int64Node(v)))
 	}
 
 	for _, v := range []int{22, 5, 0} {
-		if or.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as false", v)
-		}
+		require.False(t, orc.Contains(ctx, Int64Node(v)))
 	}
 }
 
@@ -100,67 +94,50 @@ func TestShortCircuitingOrBasics(t *testing.T) {
 	or = NewShortCircuitOr()
 	or.AddSubIterator(f1)
 	or.AddSubIterator(f2)
-	f2.Reset()
-	size, exact := or.Size()
-	if size != 4 {
-		t.Errorf("Unexpected iterator size, got:%d expected %d", size, 4)
-	}
-	if !exact {
-		t.Error("Size not exact.")
-	}
+	st, _ := or.Stats(ctx)
+	require.Equal(t, graph.Size{
+		Value: 4,
+		Exact: true,
+	}, st.Size)
 
 	// It should extract the first iterators' numbers.
 	or = NewShortCircuitOr()
 	or.AddSubIterator(f1)
 	or.AddSubIterator(f2)
-	f2.Reset()
 	expect := []int{1, 2, 3}
 	for i := 0; i < 2; i++ {
-		if got := iterated(or); !reflect.DeepEqual(got, expect) {
-			t.Errorf("Failed to iterate Or correctly on repeat %d, got:%v expect:%v", i, got, expect)
-		}
-		or.Reset()
+		require.Equal(t, expect, iterated(or))
 	}
 
 	// Check optimization works.
-	optOr, _ := or.Optimize()
-	if got := iterated(optOr); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate optimized Or correctly, got:%v expect:%v", got, expect)
-	}
+	optOr, _ := or.Optimize(ctx)
+	require.Equal(t, expect, iterated(optOr))
 
 	// Check that numbers in either iterator exist.
 	or = NewShortCircuitOr()
 	or.AddSubIterator(f1)
 	or.AddSubIterator(f2)
-	f2.Reset()
+
+	orc := or.Lookup()
 	for _, v := range []int{2, 3, 21} {
-		if !or.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as true", v)
-		}
+		require.True(t, orc.Contains(ctx, Int64Node(v)))
 	}
 	for _, v := range []int{22, 5, 0} {
-		if or.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to correctly check %d as false", v)
-		}
+		require.False(t, orc.Contains(ctx, Int64Node(v)))
 	}
 
 	// Check that it pulls the second iterator's numbers if the first is empty.
 	or = NewShortCircuitOr()
 	or.AddSubIterator(NewFixed())
 	or.AddSubIterator(f2)
-	f2.Reset()
+
 	expect = []int{3, 9, 20, 21}
 	for i := 0; i < 2; i++ {
-		if got := iterated(or); !reflect.DeepEqual(got, expect) {
-			t.Errorf("Failed to iterate Or correctly on repeat %d, got:%v expect:%v", i, got, expect)
-		}
-		or.Reset()
+		require.Equal(t, expect, iterated(or))
 	}
 	// Check optimization works.
-	optOr, _ = or.Optimize()
-	if got := iterated(optOr); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate optimized Or correctly, got:%v expect:%v", got, expect)
-	}
+	optOr, _ = or.Optimize(ctx)
+	require.Equal(t, expect, iterated(optOr))
 }
 
 func TestOrIteratorErr(t *testing.T) {
@@ -174,21 +151,13 @@ func TestOrIteratorErr(t *testing.T) {
 		fix1,
 		orErr,
 		newInt64(1, 5, true),
-	)
+	).Iterate()
 
-	if !or.Next(ctx) {
-		t.Errorf("Failed to iterate Or correctly")
-	}
-	if got := or.Result(); got.(Int64Node) != 1 {
-		t.Errorf("Failed to iterate Or correctly, got:%v expect:1", got)
-	}
+	require.True(t, or.Next(ctx))
+	require.Equal(t, Int64Node(1), or.Result())
 
-	if or.Next(ctx) != false {
-		t.Errorf("Or iterator did not pass through underlying 'false'")
-	}
-	if or.Err() != wantErr {
-		t.Errorf("Or iterator did not pass through underlying Err")
-	}
+	require.False(t, or.Next(ctx))
+	require.Equal(t, wantErr, or.Err())
 }
 
 func TestShortCircuitOrIteratorErr(t *testing.T) {
@@ -199,12 +168,8 @@ func TestShortCircuitOrIteratorErr(t *testing.T) {
 	or := NewOr(
 		orErr,
 		newInt64(1, 5, true),
-	)
+	).Iterate()
 
-	if or.Next(ctx) != false {
-		t.Errorf("Or iterator did not pass through underlying 'false'")
-	}
-	if or.Err() != wantErr {
-		t.Errorf("Or iterator did not pass through underlying Err")
-	}
+	require.False(t, or.Next(ctx))
+	require.Equal(t, wantErr, or.Err())
 }
diff --git a/graph/iterator/query_shape_test.go b/graph/iterator/query_shape_test.go
index 86d140b..69ec5c9 100644
--- a/graph/iterator/query_shape_test.go
+++ b/graph/iterator/query_shape_test.go
@@ -45,7 +45,7 @@ func TestQueryShape(t *testing.T) {
 	}}
 
 	// Given a single linkage iterator's shape.
-	var hasa graph.Iterator = hasaWithTag(qs, qs, "tag", "cool")
+	var hasa graph.IteratorShape = hasaWithTag(qs, qs, "tag", "cool")
 	hasa = Tag(hasa, "top")
 
 	shape := make(map[string]interface{})
@@ -90,11 +90,11 @@ func TestQueryShape(t *testing.T) {
 	// Given a name-of-an-and-iterator's shape.
 	andInternal := NewAnd()
 
-	var hasa1 graph.Iterator = hasaWithTag(qs, qs, "tag1", "cool")
+	var hasa1 graph.IteratorShape = hasaWithTag(qs, qs, "tag1", "cool")
 	hasa1 = Tag(hasa1, "hasa1")
 	andInternal.AddSubIterator(hasa1)
 
-	var hasa2 graph.Iterator = hasaWithTag(qs, qs, "tag2", "fun")
+	var hasa2 graph.IteratorShape = hasaWithTag(qs, qs, "tag2", "fun")
 	hasa2 = Tag(hasa2, "hasa2")
 	andInternal.AddSubIterator(hasa2)
 
diff --git a/graph/iterator/recursive_test.go b/graph/iterator/recursive_test.go
index d1bd516..1fc83b5 100644
--- a/graph/iterator/recursive_test.go
+++ b/graph/iterator/recursive_test.go
@@ -16,10 +16,11 @@ package iterator_test
 
 import (
 	"context"
-	"reflect"
 	"sort"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph"
 	"github.com/cayleygraph/cayley/graph/graphmock"
 	. "github.com/cayleygraph/cayley/graph/iterator"
@@ -27,7 +28,7 @@ import (
 )
 
 func singleHop(qs graph.QuadIndexer, pred string) Morphism {
-	return func(it graph.Iterator) graph.Iterator {
+	return func(it graph.IteratorShape) graph.IteratorShape {
 		fixed := NewFixed()
 		fixed.Add(graph.PreFetched(quad.Raw(pred)))
 		predlto := NewLinksTo(qs, fixed, quad.Predicate)
@@ -39,7 +40,7 @@ func singleHop(qs graph.QuadIndexer, pred string) Morphism {
 	}
 }
 
-var rec_test_qs = &graphmock.Store{
+var recTestQs = &graphmock.Store{
 	Data: []quad.Quad{
 		quad.MakeRaw("alice", "parent", "bob", ""),
 		quad.MakeRaw("bob", "parent", "charlie", ""),
@@ -53,43 +54,39 @@ var rec_test_qs = &graphmock.Store{
 
 func TestRecursiveNext(t *testing.T) {
 	ctx := context.TODO()
-	qs := rec_test_qs
+	qs := recTestQs
 	start := NewFixed()
 	start.Add(graph.PreFetched(quad.Raw("alice")))
-	r := NewRecursive(start, singleHop(qs, "parent"), 0)
-	expected := []string{"bob", "charlie", "dani", "emily"}
+	r := NewRecursive(start, singleHop(qs, "parent"), 0).Iterate()
 
+	expected := []string{"bob", "charlie", "dani", "emily"}
 	var got []string
 	for r.Next(ctx) {
 		got = append(got, quad.ToString(qs.NameOf(r.Result())))
 	}
 	sort.Strings(expected)
 	sort.Strings(got)
-	if !reflect.DeepEqual(got, expected) {
-		t.Errorf("Failed to %s, got: %v, expected: %v", "check basic recursive iterator", got, expected)
-	}
+	require.Equal(t, expected, got)
 }
 
 func TestRecursiveContains(t *testing.T) {
 	ctx := context.TODO()
-	qs := rec_test_qs
+	qs := recTestQs
 	start := NewFixed()
 	start.Add(graph.PreFetched(quad.Raw("alice")))
-	r := NewRecursive(start, singleHop(qs, "parent"), 0)
+	r := NewRecursive(start, singleHop(qs, "parent"), 0).Lookup()
 	values := []string{"charlie", "bob", "not"}
 	expected := []bool{true, true, false}
 
 	for i, v := range values {
 		ok := r.Contains(ctx, qs.ValueOf(quad.Raw(v)))
-		if expected[i] != ok {
-			t.Errorf("Failed to %s, value: %s, got: %v, expected: %v", "check basic recursive contains", v, ok, expected[i])
-		}
+		require.Equal(t, expected[i], ok)
 	}
 }
 
 func TestRecursiveNextPath(t *testing.T) {
 	ctx := context.TODO()
-	qs := rec_test_qs
+	qs := recTestQs
 	start := qs.NodesAllIterator()
 	start = Tag(start, "person")
 	it := singleHop(qs, "follows")(start)
@@ -98,7 +95,7 @@ func TestRecursiveNextPath(t *testing.T) {
 	fixed := NewFixed()
 	fixed.Add(graph.PreFetched(quad.Raw("alice")))
 	and.AddSubIterator(fixed)
-	r := NewRecursive(and, singleHop(qs, "parent"), 0)
+	r := NewRecursive(and, singleHop(qs, "parent"), 0).Iterate()
 
 	expected := []string{"fred", "fred", "fred", "fred", "greg", "greg", "greg", "greg"}
 	var got []string
@@ -114,7 +111,5 @@ func TestRecursiveNextPath(t *testing.T) {
 	}
 	sort.Strings(expected)
 	sort.Strings(got)
-	if !reflect.DeepEqual(got, expected) {
-		t.Errorf("Failed to check NextPath, got: %v, expected: %v", got, expected)
-	}
+	require.Equal(t, expected, got)
 }
diff --git a/graph/iterator/resolver_test.go b/graph/iterator/resolver_test.go
index 8f979d6..57cfb4f 100644
--- a/graph/iterator/resolver_test.go
+++ b/graph/iterator/resolver_test.go
@@ -4,6 +4,8 @@ import (
 	"context"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph"
 	"github.com/cayleygraph/cayley/graph/graphmock"
 	"github.com/cayleygraph/cayley/graph/iterator"
@@ -31,24 +33,14 @@ func TestResolverIteratorIterate(t *testing.T) {
 	for _, node := range nodes {
 		expected[node] = qs.ValueOf(node)
 	}
-	it := iterator.NewResolver(qs, nodes...)
+	it := iterator.NewResolver(qs, nodes...).Iterate()
 	for _, node := range nodes {
-		if it.Next(ctx) != true {
-			t.Fatal("unexpected end of iterator")
-		}
-		if err := it.Err(); err != nil {
-			t.Fatalf("unexpected error: %v", err)
-		}
-		if value := it.Result(); value != expected[node] {
-			t.Fatalf("unexpected quad value: expected %v, got %v", expected[node], value)
-		}
-	}
-	if it.Next(ctx) != false {
-		t.Fatal("expected end of iterator")
-	}
-	if it.Result() != nil {
-		t.Fatal("expected nil result")
+		require.True(t, it.Next(ctx))
+		require.NoError(t, it.Err())
+		require.Equal(t, expected[node], it.Result())
 	}
+	require.False(t, it.Next(ctx))
+	require.Nil(t, it.Result())
 }
 
 func TestResolverIteratorNotFoundError(t *testing.T) {
@@ -73,19 +65,13 @@ func TestResolverIteratorNotFoundError(t *testing.T) {
 		Data: data,
 	}
 	count := 0
-	it := iterator.NewResolver(qs, nodes...)
+	it := iterator.NewResolver(qs, nodes...).Iterate()
 	for it.Next(ctx) {
 		count++
 	}
-	if count != 0 {
-		t.Fatal("expected end of iterator")
-	}
-	if it.Err() == nil {
-		t.Fatal("expected not found error")
-	}
-	if it.Result() != nil {
-		t.Fatal("expected nil result")
-	}
+	require.Equal(t, 0, count)
+	require.Error(t, it.Err())
+	require.Nil(t, it.Result())
 }
 
 func TestResolverIteratorContains(t *testing.T) {
@@ -125,10 +111,8 @@ func TestResolverIteratorContains(t *testing.T) {
 			qs := &graphmock.Store{
 				Data: data,
 			}
-			it := iterator.NewResolver(qs, test.nodes...)
-			if it.Contains(ctx, graph.PreFetched(test.subject)) != test.contains {
-				t.Fatal("unexpected result")
-			}
+			it := iterator.NewResolver(qs, test.nodes...).Lookup()
+			require.Equal(t, test.contains, it.Contains(ctx, graph.PreFetched(test.subject)))
 		})
 	}
 }
diff --git a/graph/iterator/skip_test.go b/graph/iterator/skip_test.go
index a9fc169..1abae4a 100644
--- a/graph/iterator/skip_test.go
+++ b/graph/iterator/skip_test.go
@@ -2,9 +2,10 @@ package iterator_test
 
 import (
 	"context"
-	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
@@ -19,49 +20,33 @@ func TestSkipIteratorBasics(t *testing.T) {
 	)
 
 	u := NewSkip(allIt, 0)
-	expectSz, _ := allIt.Size()
-	if sz, _ := u.Size(); sz != expectSz {
-		t.Errorf("Failed to check Skip size: got:%v expected:%v", sz, expectSz)
-	}
-	expect := []int{1, 2, 3, 4, 5}
-	if got := iterated(u); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate Skip correctly: got:%v expected:%v", got, expect)
-	}
+	expectSz, _ := allIt.Stats(ctx)
+	sz, _ := u.Stats(ctx)
+	require.Equal(t, expectSz.Size.Value, sz.Size.Value)
 
-	allIt.Reset()
+	require.Equal(t, []int{1, 2, 3, 4, 5}, iterated(u))
 
 	u = NewSkip(allIt, 3)
-	expectSz = 2
-	if sz, _ := u.Size(); sz != expectSz {
-		t.Errorf("Failed to check Skip size: got:%v expected:%v", sz, expectSz)
-	}
-	expect = []int{4, 5}
-	if got := iterated(u); !reflect.DeepEqual(got, expect) {
-		t.Errorf("Failed to iterate Skip correctly: got:%v expected:%v", got, expect)
+	expectSz.Size.Value = 2
+	if sz, _ := u.Stats(ctx); sz.Size.Value != expectSz.Size.Value {
+		t.Errorf("Failed to check Skip size: got:%v expected:%v", sz.Size, expectSz.Size)
 	}
+	require.Equal(t, []int{4, 5}, iterated(u))
 
-	u.Reset()
+	uc := u.Lookup()
 	for _, v := range []int{1, 2, 3} {
-		if u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Skip iterator.")
-		}
+		require.False(t, uc.Contains(ctx, Int64Node(v)))
 	}
 	for _, v := range []int{4, 5} {
-		if !u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Skip iterator.")
-		}
+		require.True(t, uc.Contains(ctx, Int64Node(v)))
 	}
 
-	u.Reset()
+	uc = u.Lookup()
 	for _, v := range []int{5, 4, 3} {
-		if u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Skip iterator.")
-		}
+		require.False(t, uc.Contains(ctx, Int64Node(v)))
 	}
 	for _, v := range []int{1, 2} {
-		if !u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the Skip iterator.")
-		}
+		require.True(t, uc.Contains(ctx, Int64Node(v)))
 	}
 
 	// TODO(dennwc): check with NextPath
diff --git a/graph/iterator/unique_test.go b/graph/iterator/unique_test.go
index 9af9193..bfdd910 100644
--- a/graph/iterator/unique_test.go
+++ b/graph/iterator/unique_test.go
@@ -2,9 +2,10 @@ package iterator_test
 
 import (
 	"context"
-	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	. "github.com/cayleygraph/cayley/graph/iterator"
 )
 
@@ -22,15 +23,11 @@ func TestUniqueIteratorBasics(t *testing.T) {
 
 	expect := []int{1, 2, 3}
 	for i := 0; i < 2; i++ {
-		if got := iterated(u); !reflect.DeepEqual(got, expect) {
-			t.Errorf("Failed to iterate Unique correctly on repeat %d: got:%v expected:%v", i, got, expect)
-		}
-		u.Reset()
+		require.Equal(t, expect, iterated(u))
 	}
 
+	uc := u.Lookup()
 	for _, v := range []int{1, 2, 3} {
-		if !u.Contains(ctx, Int64Node(v)) {
-			t.Errorf("Failed to find a correct value in the unique iterator.")
-		}
+		require.True(t, uc.Contains(ctx, Int64Node(v)))
 	}
 }
diff --git a/graph/iterator/value_comparison_test.go b/graph/iterator/value_comparison_test.go
index 61ccbfc..8a67a9d 100644
--- a/graph/iterator/value_comparison_test.go
+++ b/graph/iterator/value_comparison_test.go
@@ -20,6 +20,8 @@ import (
 	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/require"
+
 	"github.com/cayleygraph/cayley/graph"
 	"github.com/cayleygraph/cayley/graph/graphmock"
 	. "github.com/cayleygraph/cayley/graph/iterator"
@@ -142,7 +144,7 @@ func TestValueComparison(t *testing.T) {
 	ctx := context.TODO()
 	for _, test := range comparisonTests {
 		qs := test.qs
-		vc := NewComparison(test.iterator(), test.operator, test.operand, qs)
+		vc := NewComparison(test.iterator(), test.operator, test.operand, qs).Iterate()
 
 		var got []quad.Value
 		for vc.Next(ctx) {
@@ -231,7 +233,7 @@ var vciContainsTests = []struct {
 func TestVCIContains(t *testing.T) {
 	ctx := context.TODO()
 	for _, test := range vciContainsTests {
-		vc := NewComparison(test.iterator(), test.operator, test.val, test.qs)
+		vc := NewComparison(test.iterator(), test.operator, test.val, test.qs).Lookup()
 		if vc.Contains(ctx, test.check) != test.expect {
 			t.Errorf("Failed to show %s", test.message)
 		}
@@ -261,13 +263,9 @@ func TestComparisonIteratorErr(t *testing.T) {
 	errIt := newTestIterator(false, wantErr)
 
 	for _, test := range comparisonIteratorTests {
-		vc := NewComparison(errIt, CompareLT, test.val, test.qs)
+		vc := NewComparison(errIt, CompareLT, test.val, test.qs).Iterate()
 
-		if vc.Next(ctx) != false {
-			t.Errorf("Comparison iterator did not pass through initial 'false': %s", test.message)
-		}
-		if vc.Err() != wantErr {
-			t.Errorf("Comparison iterator did not pass through underlying Err: %s", test.message)
-		}
+		require.False(t, vc.Next(ctx))
+		require.Equal(t, wantErr, vc.Err())
 	}
 }
diff --git a/graph/kv/kvtest/kvtest.go b/graph/kv/kvtest/kvtest.go
index 69ba577..c3a18cb 100644
--- a/graph/kv/kvtest/kvtest.go
+++ b/graph/kv/kvtest/kvtest.go
@@ -99,17 +99,20 @@ func testOptimize(t *testing.T, gen DatabaseFunc, _ *Config) {
 
 	oldIt := shape.BuildIterator(qs, shape.Quads{
 		{Dir: quad.Object, Values: shape.Lookup{quad.Raw("F")}},
-	})
-	newIt, ok := lto.Optimize()
+	}).Iterate()
+	defer oldIt.Close()
+	newIts, ok := lto.Optimize(ctx)
 	if ok {
 		t.Errorf("unexpected optimization step")
 	}
-	if _, ok := newIt.(*kv.QuadIterator); !ok {
-		t.Errorf("Optimized iterator type does not match original, got: %T", newIt)
+	if _, ok := newIts.(*kv.QuadIterator); !ok {
+		t.Errorf("Optimized iterator type does not match original, got: %T", newIts)
 	}
+	newIt := newIts.Iterate()
+	defer newIt.Close()
 
-	newQuads := graphtest.IteratedQuads(t, qs, newIt)
-	oldQuads := graphtest.IteratedQuads(t, qs, oldIt)
+	newQuads := graphtest.IteratedQuadsNext(t, qs, newIt)
+	oldQuads := graphtest.IteratedQuadsNext(t, qs, oldIt)
 	if !reflect.DeepEqual(newQuads, oldQuads) {
 		t.Errorf("Optimized iteration does not match original")
 	}
diff --git a/graph/memstore/quadstore_test.go b/graph/memstore/quadstore_test.go
index 1977a97..31e2499 100644
--- a/graph/memstore/quadstore_test.go
+++ b/graph/memstore/quadstore_test.go
@@ -104,8 +104,8 @@ type pair struct {
 func TestMemstoreValueOf(t *testing.T) {
 	qs, _, index := makeTestStore(simpleGraph)
 	exp := graph.Stats{
-		Nodes: graph.Size{Size: 11, Exact: true},
-		Quads: graph.Size{Size: 11, Exact: true},
+		Nodes: graph.Size{Value: 11, Exact: true},
+		Quads: graph.Size{Value: 11, Exact: true},
 	}
 	st, err := qs.Stats(context.Background(), true)
 	require.NoError(t, err)
@@ -141,7 +141,7 @@ func TestIteratorsAndNextResultOrderA(t *testing.T) {
 	)
 
 	hasa := iterator.NewHasA(qs, innerAnd, quad.Subject)
-	outerAnd := iterator.NewAnd(fixed, hasa)
+	outerAnd := iterator.NewAnd(fixed, hasa).Iterate()
 
 	if !outerAnd.Next(ctx) {
 		t.Error("Expected one matching subtree")
@@ -181,7 +181,7 @@ func TestLinksToOptimization(t *testing.T) {
 		{Dir: quad.Object, Values: shape.Lookup{quad.Raw("cool")}},
 	})
 
-	newIt, changed := lto.Optimize()
+	newIt, changed := lto.Optimize(context.TODO())
 	if changed {
 		t.Errorf("unexpected optimization step")
 	}
@@ -218,8 +218,8 @@ func TestRemoveQuad(t *testing.T) {
 
 	hasa := iterator.NewHasA(qs, innerAnd, quad.Object)
 
-	newIt, _ := hasa.Optimize()
-	if newIt.Next(ctx) {
+	newIt, _ := hasa.Optimize(ctx)
+	if newIt.Iterate().Next(ctx) {
 		t.Error("E should not have any followers.")
 	}
 }
diff --git a/graph/shape/shape_test.go b/graph/shape/shape_test.go
index c61b1ae..ce810a8 100644
--- a/graph/shape/shape_test.go
+++ b/graph/shape/shape_test.go
@@ -52,16 +52,16 @@ func (ValLookup) ApplyDeltas(_ []graph.Delta, _ graph.IgnoreOpts) error {
 func (ValLookup) Quad(_ graph.Ref) quad.Quad {
 	panic("not implemented")
 }
-func (ValLookup) QuadIterator(_ quad.Direction, _ graph.Ref) graph.Iterator {
+func (ValLookup) QuadIterator(_ quad.Direction, _ graph.Ref) graph.IteratorShape {
 	panic("not implemented")
 }
 func (ValLookup) QuadIteratorSize(ctx context.Context, d quad.Direction, val graph.Ref) (graph.Size, error) {
 	panic("not implemented")
 }
-func (ValLookup) NodesAllIterator() graph.Iterator {
+func (ValLookup) NodesAllIterator() graph.IteratorShape {
 	panic("not implemented")
 }
-func (ValLookup) QuadsAllIterator() graph.Iterator {
+func (ValLookup) QuadsAllIterator() graph.IteratorShape {
 	panic("not implemented")
 }
 func (ValLookup) NameOf(_ graph.Ref) quad.Value {
diff --git a/query/sexp/parser_test.go b/query/sexp/parser_test.go
index a9b2311..04925c3 100644
--- a/query/sexp/parser_test.go
+++ b/query/sexp/parser_test.go
@@ -169,7 +169,7 @@ func TestSexp(t *testing.T) {
 			s, _ := BuildShape(test.query)
 			require.Equal(t, test.shape, s, "%s\n%#v\nvs\n%#v", test.message, test.shape, s)
 
-			it := BuildIteratorTreeForQuery(qs, test.query)
+			it := BuildIteratorTreeForQuery(qs, test.query).Iterate()
 			if it.Next(ctx) != (test.expect != "") {
 				t.Errorf("Failed to %s", test.message)
 			}
diff --git a/schema/loader_test.go b/schema/loader_test.go
index a3840d1..76214e7 100644
--- a/schema/loader_test.go
+++ b/schema/loader_test.go
@@ -83,7 +83,7 @@ func TestLoadIteratorTo(t *testing.T) {
 			} else {
 				out = reflect.New(rt)
 			}
-			var it graph.Iterator
+			var it graph.IteratorShape
 			if c.from != nil {
 				fixed := iterator.NewFixed()
 				for _, id := range c.from {