Repository: cayleygraph/cayley
Pull request #814 (2019-08-18 08:04:45)

Define a new iterator interface
## Problem context
Currently, iterators are a mix of two base query types:
- Scanning an index (`Next()`).
- Looking up the index (`Contains()`).

Each iterator contains both methods that makes the implementation of those functions to be intertwined in subtle ways.

Also, it's unclear that `NextPath()` should be called after calling `Contains()`. Because `Next()` is in the same interface, it seems that `NextPath()` should only be called after `Next()` and not after `Contains()`, which is incorrect.

There are also some issues with iterator tree optimization. Iterators are statefull and must be 
`Close`d to avoid leaks. This is tricky, however, because an optimizer may or may not clone iterators. This happens mostly due to inconsistencies in the way how iterators implement `Optimize` and is very error-prone.

Also, previous changes moved most optimizations to `Shape` trees. Thus, it makes sense to try moving other related functionality to shapes.

## Solution details

Having all this in mind, I thinks it's necessary to redefine the `Iterator` interface:
- Make the new interface stateless (except caches).
- Make explicit methods to scan and lookup and return distinct types for each.
- Leave only `Stats` on the new interface, move other methods to scan and lookup interfaces.
- Remove `Reset`, since it's possible to create a new iterator from the new base interface. 
- Pass context to `Stats` and allow returning an error.
- Pass context to `Optimize` (since it calls `Stats`).
- Clean up the interface and types.
- Avoid breaking the existing code.

This PR defines a new `IteratorShape` interface that only provides the following functionality:
- Listing sub-iterators.
- Size and costs for the iterator (no runtime stats).
- Optimization of an iterator.
- Create a new scanning iterator.
- Create a new lookup "iterator".

The `IteratorShape` will later be merged with `shape.Shape`. But for now, the change is introduced separately. 

The new `Scanner` interface is mostly the same as an old `Iterator`, but without the `Contains` method. Also, `Reset`, `Clone`, `Stats`, `Optimize` were removed because they are provided by `IteratorShape`.

Similarly, the new `Index` interface allows looking up values with `Contains`. There is no `Next` on it, and all other methods are same as in the `Scanner`.

To avoid the breakage with the new API, define a compatibility layer that converts `Iterator`s to `IteratorShape`s and back.

To make it work seamlessly, define new temporary interfaces `IteratorFuture` (old iterators that have a new implementation) and `IteratorShapeCompat` (new implementation that can be converted with compatibility layer).

All the publicly defined iterators still implement an old interface, but will try to cast it's own subtree to the new one internally. An old interface will be deprecated in the future (v0.8?).

<!-- 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/814)
<!-- Reviewable:end -->



Patch:
diff --git a/go.sum b/go.sum
index edbfded..efa3a8f 100644
--- a/go.sum
+++ b/go.sum
@@ -108,6 +108,7 @@ github.com/go-sourcemap/sourcemap v2.1.2+incompatible h1:0b/xya7BKGhXuqFESKM4oIi
 github.com/go-sourcemap/sourcemap v2.1.2+incompatible/go.mod h1:F8jJfvm2KbVjc5NqelyYJmf/v5J0dwNLS2mL4sNA1Jg=
 github.com/go-sql-driver/mysql v1.4.1 h1:g24URVg0OFbNUTx9qqY1IRZ9D9z3iPyi5zKhQZpNwpA=
 github.com/go-sql-driver/mysql v1.4.1/go.mod h1:zAC/RDZ24gD3HViQzih4MyKcchzm+sOG5ZlKdlhCg5w=
+github.com/go-stack/stack v1.8.0 h1:5SgMzNM5HxrEjV0ww2lTmX6E2Izsfxas4+YHWRs3Lsk=
 github.com/go-stack/stack v1.8.0/go.mod h1:v0f6uXyyMGvRgIKkXu+yp6POWl0qKG85gN/melR3HDY=
 github.com/gogo/protobuf v1.1.1/go.mod h1:r8qH/GZQm5c6nD/R0oafs1akxWv10x8SbQlK7atdtwQ=
 github.com/gogo/protobuf v1.2.0/go.mod h1:r8qH/GZQm5c6nD/R0oafs1akxWv10x8SbQlK7atdtwQ=
@@ -154,6 +155,7 @@ github.com/hashicorp/hcl v1.0.0 h1:0Anlzjpi4vEasTeNFn2mLJgTSwt0+6sfsiTG8qcWGx4=
 github.com/hashicorp/hcl v1.0.0/go.mod h1:E5yfLk+7swimpb2L/Alb/PJmXilQ/rhwaUYs4T20WEQ=
 github.com/hidal-go/hidalgo v0.0.0-20190630194837-96996d1693f5 h1:UWgp6LNWgqJXxlWtJNTSc4k+CEKepwN4Q22X0W6U0bY=
 github.com/hidal-go/hidalgo v0.0.0-20190630194837-96996d1693f5/go.mod h1:b3eSi7JTaazUL53iaWMGbP5fsOr+LQWlkS7YFOZIwE8=
+github.com/hidal-go/hidalgo v0.0.0-20190814174001-42e03f3b5eaa h1:hBE4LGxApbZiV/3YoEPv7uYlUMWOogG1hwtkpiU87zQ=
 github.com/hidal-go/hidalgo v0.0.0-20190814174001-42e03f3b5eaa/go.mod h1:bPkrxDlroXxigw8BMWTEPTv4W5/rQwNgg2BECXsgyX0=
 github.com/hpcloud/tail v1.0.0 h1:nfCOvKYfkgYP8hkirhJocXT2+zOD8yUNjXaWfTlyFKI=
 github.com/hpcloud/tail v1.0.0/go.mod h1:ab1qPbhIpdTxEkNHXyeSf5vhxWSCs/tWer42PpOxQnU=
@@ -287,13 +289,16 @@ github.com/tylertreat/BoomFilters v0.0.0-20181028192813-611b3dbe80e8 h1:7X4KYG3g
 github.com/tylertreat/BoomFilters v0.0.0-20181028192813-611b3dbe80e8/go.mod h1:OYRfF6eb5wY9VRFkXJH8FFBi3plw2v+giaIu7P054pM=
 github.com/ugorji/go v1.1.4/go.mod h1:uQMGLiO92mf5W77hV/PUCpI3pbzQx3CRekS0kk+RGrc=
 github.com/ugorji/go/codec v0.0.0-20181204163529-d75b2dcb6bc8/go.mod h1:VFNgLljTbGfSG7qAOspJ7OScBnGdDN/yBr0sguwnwf0=
+github.com/xdg/scram v0.0.0-20180814205039-7eeb5667e42c h1:u40Z8hqBAAQyv+vATcGgV0YCnDjqSL7/q/JyPhhJSPk=
 github.com/xdg/scram v0.0.0-20180814205039-7eeb5667e42c/go.mod h1:lB8K/P019DLNhemzwFU4jHLhdvlE6uDZjXFejJXr49I=
+github.com/xdg/stringprep v1.0.0 h1:d9X0esnoa3dFsV0FG35rAT0RIhYFlPq7MiP+DW89La0=
 github.com/xdg/stringprep v1.0.0/go.mod h1:Jhud4/sHMO4oL310DaZAKk9ZaJ08SJfe+sJh0HrGL1Y=
 github.com/xiang90/probing v0.0.0-20190116061207-43a291ad63a2/go.mod h1:UETIi67q53MR2AWcXfiuqkDkRtnGDLqkBTpCHuJHxtU=
 github.com/xordataexchange/crypt v0.0.3-0.20170626215501-b2862e3d0a77/go.mod h1:aYKd//L2LvnjZzWKhF00oedf4jCCReLcmhLdhm1A27Q=
 go.etcd.io/bbolt v1.3.2/go.mod h1:IbVyRI1SCnLcuJnV2u8VeU0CEYM7e686BmAb1XKL+uU=
 go.etcd.io/bbolt v1.3.3 h1:MUGmc65QhB3pIlaQ5bB4LwqSj6GIonVJXpZiaKNyaKk=
 go.etcd.io/bbolt v1.3.3/go.mod h1:IbVyRI1SCnLcuJnV2u8VeU0CEYM7e686BmAb1XKL+uU=
+go.mongodb.org/mongo-driver v1.0.4 h1:bHxbjH6iwh1uInchXadI6hQR107KEbgYsMzoblDONmQ=
 go.mongodb.org/mongo-driver v1.0.4/go.mod h1:u7ryQJ+DOzQmeO7zB6MHyr8jkEQvC8vH7qLUO4lqsUM=
 go.opencensus.io v0.20.1/go.mod h1:6WKK9ahsWS3RSO+PY9ZHZUfv2irvY6gN279GOPZjmmk=
 go.opencensus.io v0.20.2/go.mod h1:6WKK9ahsWS3RSO+PY9ZHZUfv2irvY6gN279GOPZjmmk=
@@ -303,6 +308,7 @@ go.uber.org/zap v1.10.0/go.mod h1:vwi/ZaCAaUcBkycHslxD9B2zi4UTXhF60s6SWpuDF0Q=
 golang.org/x/crypto v0.0.0-20180904163835-0709b304e793/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
 golang.org/x/crypto v0.0.0-20181203042331-505ab145d0a9/go.mod h1:6SG95UA2DQfeDnfUPMdvaQW0Q7yPrPDi9nlGo2tz2b4=
 golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/crypto v0.0.0-20190605123033-f99c8df09eb5 h1:58fnuSXlxZmFdJyvtTFVmVhcMLU6v5fEb/ok4wyqtNU=
 golang.org/x/crypto v0.0.0-20190605123033-f99c8df09eb5/go.mod h1:yigFU9vqHzYiE8UmvKecakEJjdnWj3jj499lnFckfCI=
 golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=
 golang.org/x/lint v0.0.0-20181026193005-c67002cb31c3/go.mod h1:UVdnD1Gm6xHRNCYTkRU2/jEulfH38KcIWyp/GAMgvoE=
@@ -333,6 +339,7 @@ golang.org/x/sync v0.0.0-20180314180146-1d60e4601c6f/go.mod h1:RxMgew5VJxzue5/jJ
 golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sync v0.0.0-20181221193216-37e7f081c4d4/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sync v0.0.0-20190227155943-e225da77a7e6/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
+golang.org/x/sync v0.0.0-20190423024810-112230192c58 h1:8gQV6CLnAEikrhgkHFbMAEhagSSnXWGV915qUMm9mrU=
 golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sys v0.0.0-20180830151530-49385e6e1522/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20180905080454-ebe1bf3edb33/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
diff --git a/graph/gaedatastore/iterator.go b/graph/gaedatastore/iterator.go
index b013a13..6019427 100644
--- a/graph/gaedatastore/iterator.go
+++ b/graph/gaedatastore/iterator.go
@@ -20,14 +20,12 @@ import (
 
 	"github.com/cayleygraph/cayley/clog"
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/quad"
 
 	"google.golang.org/appengine/datastore"
 )
 
 type Iterator struct {
-	uid    uint64
 	size   int64
 	dir    quad.Direction
 	qs     *QuadStore
@@ -77,7 +75,6 @@ func NewIterator(qs *QuadStore, k string, d quad.Direction, val graph.Ref) *Iter
 	size := foundNode.Size
 
 	return &Iterator{
-		uid:   iterator.NextUID(),
 		name:  name,
 		dir:   d,
 		qs:    qs,
@@ -107,7 +104,6 @@ func NewAllIterator(qs *QuadStore, kind string) *Iterator {
 		size = st.Quads.Size
 	}
 	return &Iterator{
-		uid:   iterator.NextUID(),
 		qs:    qs,
 		size:  size,
 		err:   err,
@@ -118,10 +114,6 @@ func NewAllIterator(qs *QuadStore, kind string) *Iterator {
 	}
 }
 
-func (it *Iterator) UID() uint64 {
-	return it.uid
-}
-
 func (it *Iterator) Reset() {
 	it.buffer = nil
 	it.offset = 0
diff --git a/graph/iterate.go b/graph/iterate.go
index b8468e7..bbb41b8 100644
--- a/graph/iterate.go
+++ b/graph/iterate.go
@@ -12,7 +12,8 @@ import (
 // IterateChain is a chain-enabled helper to setup iterator execution.
 type IterateChain struct {
 	ctx context.Context
-	it  Iterator
+	s   IteratorShape
+	it  Scanner
 	qs  QuadStore
 
 	paths    bool
@@ -31,7 +32,7 @@ func Iterate(ctx context.Context, it Iterator) *IterateChain {
 		ctx = context.Background()
 	}
 	return &IterateChain{
-		ctx: ctx, it: it,
+		ctx: ctx, s: AsShape(it),
 		limit: -1, paths: true,
 		optimize: true,
 	}
@@ -62,12 +63,13 @@ func (c *IterateChain) nextPath() bool {
 }
 func (c *IterateChain) start() {
 	if c.optimize {
-		c.it, _ = c.it.Optimize()
+		c.s, _ = c.s.Optimize(c.ctx)
 	}
+	c.it = c.s.Iterate()
 	if !clog.V(2) {
 		return
 	}
-	if b, err := json.MarshalIndent(DescribeIterator(c.it), "", "  "); err != nil {
+	if b, err := json.MarshalIndent(DescribeIterator(AsLegacy(c.s)), "", "  "); err != nil {
 		clog.Infof("failed to format description: %v", err)
 	} else {
 		clog.Infof("%s", b)
@@ -78,7 +80,7 @@ func (c *IterateChain) end() {
 	if !clog.V(2) {
 		return
 	}
-	if b, err := json.MarshalIndent(DumpStats(c.it), "", "  "); err != nil {
+	if b, err := json.MarshalIndent(DumpStats(AsLegacy(c.s)), "", "  "); err != nil {
 		clog.Infof("failed to format stats: %v", err)
 	} else {
 		clog.Infof("%s", b)
@@ -137,14 +139,20 @@ func (c *IterateChain) Each(fnc func(Ref)) error {
 
 // All will return all results of an iterator.
 func (c *IterateChain) Count() (int64, error) {
+	// TODO(dennwc): this should wrap the shape in Count
+	if c.optimize {
+		c.s, _ = c.s.Optimize(c.ctx)
+	}
+	if st, err := c.s.Stats(c.ctx); err != nil {
+		return st.Size.Size, err
+	} else if st.Size.Exact {
+		return st.Size.Size, nil
+	}
 	c.start()
 	defer c.end()
 	if err := c.it.Err(); err != nil {
 		return 0, err
 	}
-	if size, exact := c.it.Size(); exact {
-		return size, nil
-	}
 	done := c.ctx.Done()
 	var cnt int64
 iteration:
diff --git a/graph/iterator.go b/graph/iterator.go
index 6560619..f871608 100644
--- a/graph/iterator.go
+++ b/graph/iterator.go
@@ -37,17 +37,23 @@ type Linkage struct {
 
 // TODO(barakmich): Helper functions as needed, eg, ValuesForDirection(quad.Direction) []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 is a base interface for Tagger and TaggerShape.
+type TaggerBase interface {
 	Tags() []string
 	FixedTags() map[string]Ref
 	AddTags(tag ...string)
 	AddFixedTag(tag string, value Ref)
-	CopyFromTagger(st Tagger)
 }
 
-type Iterator interface {
+// 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.
 	String() string
 
@@ -57,12 +63,6 @@ type Iterator interface {
 	// Returns the current result.
 	Result() Ref
 
-	// 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
-
 	// These methods are the heart and soul of the iterator, as they constitute
 	// the iteration interface.
 	//
@@ -83,12 +83,27 @@ type Iterator interface {
 	// from the bottom up.
 	NextPath(ctx context.Context) bool
 
-	// Contains returns whether the value is within the set held by the iterator.
-	Contains(ctx context.Context, v Ref) bool
-
 	// Err returns any error that was encountered by the Iterator.
 	Err() error
 
+	// TODO: make a requirement that Err should return ErrClosed after Close is called
+
+	// Close the iterator and do internal cleanup.
+	Close() error
+}
+
+type Iterator 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
+
+	// Contains returns whether the value is within the set held by the iterator.
+	Contains(ctx context.Context, v Ref) bool
+
 	// Start iteration from the beginning
 	Reset()
 
@@ -113,21 +128,20 @@ type Iterator interface {
 
 	// Return a slice of the subiterators for this iterator.
 	SubIterators() []Iterator
+}
 
-	// TODO: make a requirement that Err should return ErrClosed after Close is called
-
-	// Close the iterator and do internal cleanup.
-	Close() error
-
-	// UID returns the unique identifier of the iterator.
-	UID() uint64
+// 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:  it.UID(),
+		UID:  uint64(reflect.ValueOf(it).Pointer()),
 		Name: it.String(),
 		Type: reflect.TypeOf(it).String(),
 		Size: sz, Exact: exact,
@@ -165,6 +179,15 @@ func Height(it Iterator, filter func(Iterator) bool) int {
 	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
@@ -173,6 +196,31 @@ 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
@@ -200,7 +248,7 @@ func DumpStats(it Iterator) StatsContainer {
 	var out StatsContainer
 	out.IteratorStats = it.Stats()
 	out.Type = reflect.TypeOf(it).String()
-	out.UID = it.UID()
+	out.UID = uint64(reflect.ValueOf(it).Pointer())
 	for _, sub := range it.SubIterators() {
 		out.SubIts = append(out.SubIts, DumpStats(sub))
 	}
diff --git a/graph/iterator/all.go b/graph/iterator/all.go
deleted file mode 100644
index 1886da5..0000000
--- a/graph/iterator/all.go
+++ /dev/null
@@ -1,167 +0,0 @@
-// Copyright 2014 The Cayley Authors. All rights reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//     http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package iterator
-
-// Defines one of the base iterators, the All iterator. Which, logically
-// enough, represents all nodes or all links in the graph.
-//
-// This particular file is actually vestigial. It's up to the QuadStore to give
-// us an All iterator that represents all things in the graph. So this is
-// really the All iterator for the memstore.QuadStore. That said, it *is* one of
-// the base iterators, and it helps just to see it here.
-
-import (
-	"context"
-	"fmt"
-
-	"github.com/cayleygraph/cayley/graph"
-)
-
-var _ graph.Iterator = &Int64{}
-
-// An All iterator across a range of int64 values, from `max` to `min`.
-type Int64 struct {
-	node     bool
-	uid      uint64
-	max, min int64
-	at       int64
-	result   int64
-	runstats graph.IteratorStats
-}
-
-type Int64Node int64
-
-func (v Int64Node) Key() interface{} { return v }
-
-func (Int64Node) IsNode() bool { return true }
-
-type Int64Quad int64
-
-func (v Int64Quad) Key() interface{} { return v }
-
-func (Int64Quad) IsNode() bool { return false }
-
-// Creates a new Int64 with the given range.
-func NewInt64(min, max int64, node bool) *Int64 {
-	return &Int64{
-		uid:  NextUID(),
-		node: node,
-		min:  min,
-		max:  max,
-		at:   min,
-	}
-}
-
-func (it *Int64) UID() uint64 {
-	return it.uid
-}
-
-// Start back at the beginning
-func (it *Int64) Reset() {
-	it.at = it.min
-}
-
-func (it *Int64) Close() error {
-	return nil
-}
-
-func (it *Int64) TagResults(dst map[string]graph.Ref) {}
-
-func (it *Int64) 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
-	if it.at == -1 {
-		return false
-	}
-	val := it.at
-	it.at = it.at + 1
-	if it.at > it.max {
-		it.at = -1
-	}
-	it.result = val
-	return true
-}
-
-func (it *Int64) Err() error {
-	return nil
-}
-
-func (it *Int64) toValue(v int64) graph.Ref {
-	if it.node {
-		return Int64Node(v)
-	}
-	return Int64Quad(v)
-}
-
-func (it *Int64) Result() graph.Ref {
-	return it.toValue(it.result)
-}
-
-func (it *Int64) NextPath(ctx context.Context) bool {
-	return false
-}
-
-// No sub-iterators.
-func (it *Int64) SubIterators() []graph.Iterator {
-	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 valToInt64(v graph.Ref) int64 {
-	if v, ok := v.(Int64Node); ok {
-		return int64(v)
-	}
-	return int64(v.(Int64Quad))
-}
-
-// 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
-	v := valToInt64(tsv)
-	if it.min <= v && v <= it.max {
-		it.result = v
-		return true
-	}
-	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/and.go b/graph/iterator/and.go
index 0bfbe07..a32933a 100644
--- a/graph/iterator/and.go
+++ b/graph/iterator/and.go
@@ -21,91 +21,121 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &And{}
+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 {
-	uid uint64
-
-	primary   graph.Iterator
-	sub       []graph.Iterator
-	opt       []graph.Iterator
-	optCheck  []bool
-	checkList []graph.Iterator
-
-	runstats graph.IteratorStats
-	result   graph.Ref
-	err      error
+	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{
-		uid: NextUID(),
-		sub: make([]graph.Iterator, 0, 20),
+		it: newAnd(),
 	}
 	for _, s := range sub {
-		it.AddSubIterator(s)
+		it.it.AddSubIterator(graph.AsShape(s))
 	}
+	it.Iterator = graph.NewLegacy(it.it, it)
 	return it
 }
 
-func (it *And) UID() uint64 {
-	return it.uid
+func (it *And) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-// Reset all internal iterators
-func (it *And) Reset() {
-	it.result = nil
-	it.primary.Reset()
-	for _, sub := range it.sub {
-		sub.Reset()
+// 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
+}
+
+// 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{
+		sub: make([]graph.IteratorShape, 0, 20),
 	}
-	it.checkList = nil
+	for _, s := range sub {
+		it.AddSubIterator(s)
+	}
+	return it
 }
 
-// An extended TagResults, as it needs to add it's own results and
-// recurse down it's subiterators.
-func (it *And) TagResults(dst map[string]graph.Ref) {
-	if it.primary != nil {
-		it.primary.TagResults(dst)
+func (it *and) Iterate() graph.Scanner {
+	if len(it.sub) == 0 {
+		return newNull().Iterate()
 	}
-	for _, sub := range it.sub {
-		sub.TagResults(dst)
+	sub := make([]graph.Index, 0, len(it.sub)-1)
+	for _, s := range it.sub[1:] {
+		sub = append(sub, s.Lookup())
 	}
-	for i, sub := range it.opt {
-		if !it.optCheck[i] {
-			continue
-		}
-		sub.TagResults(dst)
+	opt := make([]graph.Index, 0, len(it.opt))
+	for _, s := range it.opt {
+		opt = append(opt, s.Lookup())
 	}
+	return newAndNext(it.sub[0].Iterate(), newAndContains(sub, opt))
 }
 
-// subIterators is like SubIterators but excludes optional.
-func (it *And) subIterators() []graph.Iterator {
-	iters := make([]graph.Iterator, 0, 1+len(it.sub))
-	if it.primary != nil {
-		iters = append(iters, it.primary)
+func (it *and) Lookup() graph.Index {
+	if len(it.sub) == 0 {
+		return newNull().Lookup()
 	}
-	iters = append(iters, it.sub...)
-	// exclude optional
-	return iters
+	sub := make([]graph.Index, 0, len(it.sub))
+	check := it.checkList
+	if check == nil {
+		check = it.sub
+	}
+	for _, s := range check {
+		sub = append(sub, s.Lookup())
+	}
+	opt := make([]graph.Index, 0, len(it.opt))
+	for _, s := range it.opt {
+		opt = append(opt, s.Lookup())
+	}
+	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.Iterator {
-	iters := make([]graph.Iterator, 0, 1+len(it.sub)+len(it.opt))
-	if it.primary != nil {
-		iters = append(iters, it.primary)
-	}
+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"
 }
 
@@ -115,44 +145,147 @@ 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.Iterator) {
-	if it.primary == nil {
-		it.primary = sub
-		return
+func (it *and) AddSubIterator(sub graph.IteratorShape) {
+	if sub == nil {
+		panic("nil iterator")
 	}
 	it.sub = append(it.sub, 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 {
+func (it *and) AddOptionalIterator(sub graph.IteratorShape) *and {
 	it.opt = append(it.opt, sub)
-	it.optCheck = append(it.optCheck, false)
 	return it
 }
 
+// The And iterator. Consists of a number of subiterators, the primary of which will
+// be Next()ed if next is called.
+type andNext struct {
+	primary   graph.Scanner
+	secondary graph.Index
+	result    graph.Ref
+}
+
+// NewAnd creates an And iterator. `qs` is only required when needing a handle
+// for QuadStore-specific optimizations, otherwise nil is acceptable.
+func newAndNext(pri graph.Scanner, sec graph.Index) graph.Scanner {
+	return &andNext{
+		primary:   pri,
+		secondary: sec,
+	}
+}
+
+// An extended TagResults, as it needs to add it's own results and
+// recurse down it's subiterators.
+func (it *andNext) TagResults(dst map[string]graph.Ref) {
+	it.primary.TagResults(dst)
+	it.secondary.TagResults(dst)
+}
+
+func (it *andNext) String() string {
+	return "AndNext"
+}
+
 // Returns advances the And iterator. Because the And is the intersection of its
 // subiterators, it must choose one subiterator to produce a candidate, and check
 // this value against the subiterators. A productive choice of primary iterator
 // is therefore very important.
-func (it *And) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
+func (it *andNext) Next(ctx context.Context) bool {
 	for it.primary.Next(ctx) {
 		cur := it.primary.Result()
-		if it.subContain(ctx, cur, nil) {
+		if it.secondary.Contains(ctx, cur) {
 			it.result = cur
 			return true
 		}
 	}
-	it.err = it.primary.Err()
 	return false
 }
 
-func (it *And) Err() error {
-	if err := it.err; err != nil {
+func (it *andNext) Err() error {
+	if err := it.primary.Err(); err != nil {
 		return err
 	}
-	if err := it.primary.Err(); err != nil {
+	if err := it.secondary.Err(); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (it *andNext) Result() graph.Ref {
+	return it.result
+}
+
+// An And has no NextPath of its own -- that is, there are no other values
+// which satisfy our previous result that are not the result itself. Our
+// subiterators might, however, so just pass the call recursively.
+func (it *andNext) NextPath(ctx context.Context) bool {
+	if it.primary.NextPath(ctx) {
+		return true
+	} else if err := it.primary.Err(); err != nil {
+		return false
+	}
+	if it.secondary.NextPath(ctx) {
+		return true
+	} else if err := it.secondary.Err(); err != nil {
+		return false
+	}
+	return false
+}
+
+// Close this iterator, and, by extension, close the subiterators.
+// Close should be idempotent, and it follows that if it's subiterators
+// follow this contract, the And follows the contract.  It closes all
+// subiterators it can, but returns the first error it encounters.
+func (it *andNext) Close() error {
+	err := it.primary.Close()
+	if err2 := it.secondary.Close(); err2 != nil && err == nil {
+		err = err2
+	}
+	return err
+}
+
+// The And iterator. Consists of a number of subiterators, the primary of which will
+// be Next()ed if next is called.
+type andContains struct {
+	base     graph.IteratorShape
+	sub      []graph.Index
+	opt      []graph.Index
+	optCheck []bool
+
+	result graph.Ref
+	err    error
+}
+
+// NewAnd creates an And iterator. `qs` is only required when needing a handle
+// for QuadStore-specific optimizations, otherwise nil is acceptable.
+func newAndContains(sub, opt []graph.Index) graph.Index {
+	return &andContains{
+		sub: sub,
+		opt: opt, optCheck: make([]bool, len(opt)),
+	}
+}
+
+// An extended TagResults, as it needs to add it's own results and
+// recurse down it's subiterators.
+func (it *andContains) TagResults(dst map[string]graph.Ref) {
+	for _, sub := range it.sub {
+		sub.TagResults(dst)
+	}
+	for i, sub := range it.opt {
+		if !it.optCheck[i] {
+			continue
+		}
+		sub.TagResults(dst)
+	}
+}
+
+func (it *andContains) String() string {
+	return "AndContains"
+}
+
+func (it *andContains) Err() error {
+	if err := it.err; err != nil {
 		return err
 	}
 	for _, si := range it.sub {
@@ -168,19 +301,14 @@ func (it *And) Err() error {
 	return nil
 }
 
-func (it *And) Result() graph.Ref {
+func (it *andContains) Result() graph.Ref {
 	return it.result
 }
 
-func (it *And) checkOpt(ctx context.Context, val graph.Ref) {
-	for i, sub := range it.opt {
-		// remember if we will need to call TagResults on it, nothing more
-		it.optCheck[i] = sub.Contains(ctx, val)
-	}
-}
-
-func (it *And) allContains(ctx context.Context, check []graph.Iterator, val, prev graph.Ref) bool {
-	for i, sub := range check {
+// Check a value against the entire iterator, in order.
+func (it *andContains) Contains(ctx context.Context, val graph.Ref) bool {
+	prev := it.result
+	for i, sub := range it.sub {
 		if !sub.Contains(ctx, val) {
 			if err := sub.Err(); err != nil {
 				it.err = err
@@ -195,8 +323,8 @@ func (it *And) allContains(ctx context.Context, check []graph.Iterator, val, pre
 			// which will be 'true'
 			if prev != nil {
 				for j := 0; j < i; j++ {
-					check[j].Contains(ctx, prev)
-					if err := check[j].Err(); err != nil {
+					it.sub[j].Contains(ctx, prev)
+					if err := it.sub[j].Err(); err != nil {
 						it.err = err
 						return false
 					}
@@ -206,63 +334,17 @@ func (it *And) allContains(ctx context.Context, check []graph.Iterator, val, pre
 		}
 	}
 	it.result = val
-	it.checkOpt(ctx, val)
-	return true
-}
-
-// subContain checks a value against the non-primary iterators, in order.
-func (it *And) subContain(ctx context.Context, cur, prev graph.Ref) bool {
-	return it.allContains(ctx, it.sub, cur, prev)
-}
-
-// checkContain is like subContain but uses optimized order of iterators stored in it.checkList, which includes primary.
-func (it *And) checkContain(ctx context.Context, cur, prev graph.Ref) bool {
-	return it.allContains(ctx, it.checkList, cur, prev)
-}
-
-// Check a value against the entire iterator, in order.
-func (it *And) Contains(ctx context.Context, val graph.Ref) bool {
-	it.runstats.Contains += 1
-	prev := it.result
-	if it.checkList != nil {
-		return it.checkContain(ctx, val, prev)
-	}
-	if it.primary.Contains(ctx, val) && it.subContain(ctx, val, prev) {
-		it.result = val
-		return true
-	}
-	if prev != nil {
-		it.primary.Contains(ctx, prev)
-	}
-	return false
-}
-
-// Returns the approximate size of the And iterator. Because we're dealing
-// 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) Size() (int64, bool) {
-	sz, exact := it.primary.Size()
-	for _, sub := range it.sub {
-		sz2, exact2 := sub.Size()
-		if sz > sz2 {
-			sz = sz2
-		}
-		exact = exact2 && exact
+	for i, sub := range it.opt {
+		// remember if we will need to call TagResults on it, nothing more
+		it.optCheck[i] = sub.Contains(ctx, val)
 	}
-	return sz, exact
+	return true
 }
 
 // An And has no NextPath of its own -- that is, there are no other values
 // which satisfy our previous result that are not the result itself. Our
 // subiterators might, however, so just pass the call recursively.
-func (it *And) NextPath(ctx context.Context) bool {
-	if it.primary.NextPath(ctx) {
-		return true
-	} else if err := it.primary.Err(); err != nil {
-		it.err = err
-		return false
-	}
+func (it *andContains) NextPath(ctx context.Context) bool {
 	for _, sub := range it.sub {
 		if sub.NextPath(ctx) {
 			return true
@@ -289,8 +371,8 @@ func (it *And) NextPath(ctx context.Context) bool {
 // Close should be idempotent, and it follows that if it's subiterators
 // follow this contract, the And follows the contract.  It closes all
 // subiterators it can, but returns the first error it encounters.
-func (it *And) Close() error {
-	err := it.primary.Close()
+func (it *andContains) Close() error {
+	var err error
 	for _, sub := range it.sub {
 		if err2 := sub.Close(); err2 != nil && err == nil {
 			err = err2
diff --git a/graph/iterator/and_optimize.go b/graph/iterator/and_optimize.go
index 09ece87..a158d1c 100644
--- a/graph/iterator/and_optimize.go
+++ b/graph/iterator/and_optimize.go
@@ -15,6 +15,7 @@
 package iterator
 
 import (
+	"context"
 	"sort"
 
 	"github.com/cayleygraph/cayley/clog"
@@ -40,74 +41,58 @@ 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() (graph.Iterator, 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.subIterators()
+	old := it.sub
 	if len(old) == 0 {
-		it.Close()
-		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 := optimizeSubIterators(old)
+	its := optimizeSubIterators2(ctx, old)
 
 	// If we can find only one subiterator which is equivalent to this whole and,
 	// we can replace the And...
 	if out := optimizeReplacement(its); out != nil && len(it.opt) == 0 {
-		// ...Close everyone except `out`, our replacement...
-		closeIteratorList(its, out)
 		// ...And return it.
 		return out, true
 	}
 
 	// And now, without changing any of the iterators, we reorder them. it_list is
 	// now a permutation of itself, but the contents are unchanged.
-	its = optimizeOrder(its)
+	its = optimizeOrder(ctx, its)
 
-	its = materializeIts(its)
+	its, _ = materializeIts(ctx, its)
 
 	// Okay! At this point we have an optimized order.
 
 	// The easiest thing to do at this point is merely to create a new And iterator
 	// and replace ourselves with our (reordered, optimized) clone.
-	newAnd := NewAnd()
-
 	// Add the subiterators in order.
-	for _, sub := range its {
-		newAnd.AddSubIterator(sub)
-	}
-	opt := optimizeSubIterators(it.opt)
+	newAnd := newAnd(its...)
+
+	opt := optimizeSubIterators2(ctx, it.opt)
 	for _, sub := range opt {
 		newAnd.AddOptionalIterator(sub)
 	}
 
-	newAnd.optimizeContains()
+	_ = newAnd.optimizeContains(ctx)
 	if clog.V(3) {
-		clog.Infof("%v become %v", it.UID(), newAnd.UID())
+		clog.Infof("%p become %p", it, newAnd)
 	}
 	return newAnd, true
 }
 
-// Closes a list of iterators, except the one passed in `except`. Closes all
-// of the iterators in the list if `except` is nil.
-func closeIteratorList(its []graph.Iterator, except graph.Iterator) {
-	for _, it := range its {
-		if it != except {
-			it.Close()
-		}
-	}
-}
-
 // Find if there is a single subiterator which is a valid replacement for this
 // And.
-func optimizeReplacement(its []graph.Iterator) graph.Iterator {
+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.
@@ -117,19 +102,19 @@ func optimizeReplacement(its []graph.Iterator) graph.Iterator {
 	// 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
 }
 
 // optimizeOrder(l) takes a list and returns a list, containing the same contents
 // but with a new ordering, however it wishes.
-func optimizeOrder(its []graph.Iterator) []graph.Iterator {
+func optimizeOrder(ctx context.Context, its []graph.IteratorShape) []graph.IteratorShape {
 	var (
 		// bad contains iterators that can't be (efficiently) nexted, such as
 		// graph.Optional or graph.Not. Separate them out and tack them on at the end.
-		bad      []graph.Iterator
-		best     graph.Iterator
+		bad      []graph.IteratorShape
+		best     graph.IteratorShape
 		bestCost = int64(1 << 62)
 	)
 
@@ -138,18 +123,18 @@ func optimizeOrder(its []graph.Iterator) []graph.Iterator {
 	// all of it's contents, and to Contains() each of those against everyone
 	// else.
 	for _, root := range its {
-		rootStats := root.Stats()
+		rootStats, _ := root.Stats(ctx)
 		cost := rootStats.NextCost
 		for _, f := range its {
 			if f == root {
 				continue
 			}
-			stats := f.Stats()
-			cost += stats.ContainsCost * (1 + (rootStats.Size / (stats.Size + 1)))
+			stats, _ := f.Stats(ctx)
+			cost += stats.ContainsCost * (1 + (rootStats.Size.Size / (stats.Size.Size + 1)))
 		}
-		cost *= rootStats.Size
+		cost *= rootStats.Size.Size
 		if clog.V(3) {
-			clog.Infof("And: Root: %v Total Cost: %v Best: %v", root.UID(), cost, bestCost)
+			clog.Infof("And: Root: %p Total Cost: %v Best: %v", root, cost, bestCost)
 		}
 		if cost < bestCost {
 			best = root
@@ -157,14 +142,14 @@ func optimizeOrder(its []graph.Iterator) []graph.Iterator {
 		}
 	}
 	if clog.V(3) {
-		clog.Infof("And: Choosing: %v Best: %v", best.UID(), bestCost)
+		clog.Infof("And: Choosing: %p Best: %v", best, bestCost)
 	}
 
 	// TODO(barakmich): Optimization of order need not stop here. Picking a smart
 	// Contains() order based on probability of getting a false Contains() first is
 	// useful (fail faster).
 
-	var out []graph.Iterator
+	var out []graph.IteratorShape
 	// Put the best iterator (the one we wish to Next()) at the front...
 	if best != nil {
 		out = append(out, best)
@@ -181,21 +166,47 @@ func optimizeOrder(its []graph.Iterator) []graph.Iterator {
 	return append(out, bad...)
 }
 
-type byCost []graph.Iterator
+func sortByContainsCost(ctx context.Context, arr []graph.IteratorShape) error {
+	cost := make([]graph.IteratorCosts, 0, len(arr))
+	var last error
+	for _, s := range arr {
+		c, err := s.Stats(ctx)
+		if err != nil {
+			last = err
+		}
+		cost = append(cost, c)
+	}
+	sort.Sort(byCost{
+		list: arr,
+		cost: cost,
+	})
+	return last
+}
 
-func (c byCost) Len() int           { return len(c) }
-func (c byCost) Less(i, j int) bool { return c[i].Stats().ContainsCost < c[j].Stats().ContainsCost }
-func (c byCost) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
+// TODO(dennwc): store stats slice once
+type byCost struct {
+	list []graph.IteratorShape
+	cost []graph.IteratorCosts
+}
+
+func (c byCost) Len() int { return len(c.list) }
+func (c byCost) Less(i, j int) bool {
+	return c.cost[i].ContainsCost < c.cost[j].ContainsCost
+}
+func (c byCost) Swap(i, j int) {
+	c.list[i], c.list[j] = c.list[j], c.list[i]
+	c.cost[i], c.cost[j] = c.cost[j], c.cost[i]
+}
 
 // optimizeContains() creates an alternate check list, containing the same contents
 // but with a new ordering, however it wishes.
-func (it *And) optimizeContains() {
+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.
 	// Generally this is a worthwhile thing to do in other places as well.
-	it.checkList = it.subIterators()
-	sort.Sort(byCost(it.checkList))
+	it.checkList = append([]graph.IteratorShape{}, it.sub...)
+	return sortByContainsCost(ctx, it.checkList)
 }
 
 // optimizeSubIterators(l) takes a list of iterators and calls Optimize() on all
@@ -211,81 +222,103 @@ func optimizeSubIterators(its []graph.Iterator) []graph.Iterator {
 	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 {
+	out := make([]graph.IteratorShape, 0, len(its))
+	for _, it := range its {
+		o, _ := it.Optimize(ctx)
+		out = append(out, o)
+	}
+	return out
+}
+
 // Check a list of iterators for any Null iterators.
-func hasAnyNullIterators(its []graph.Iterator) bool {
+func hasAnyNullIterators(its []graph.IteratorShape) bool {
 	for _, it := range its {
-		if _, ok := it.(*Null); ok {
+		if IsNull2(it) {
 			return true
 		}
 	}
 	return false
 }
 
-func materializeIts(its []graph.Iterator) []graph.Iterator {
-	var out []graph.Iterator
+func materializeIts(ctx context.Context, its []graph.IteratorShape) ([]graph.IteratorShape, error) {
+	var out []graph.IteratorShape
 
-	allStats, stats := getStatsForSlice(its, nil)
+	allStats, stats, err := getStatsForSlice(ctx, its, nil)
 	out = append(out, its[0])
 	for i, it := range its[1:] {
 		st := stats[i+1]
-		if st.Size*st.NextCost < (st.ContainsCost * (1 + (st.Size / (allStats.Size + 1)))) {
-			if graph.Height(it, func(it graph.Iterator) bool {
+		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 {
 				_, ok := it.(*Materialize)
 				return !ok
 			}) > 10 {
-				out = append(out, NewMaterialize(it))
+				out = append(out, newMaterialize(it))
 				continue
 			}
 		}
 		out = append(out, it)
 	}
-	return out
+	return out, err
 }
 
-func getStatsForSlice(its, opt []graph.Iterator) (graph.IteratorStats, []graph.IteratorStats) {
+func getStatsForSlice(ctx context.Context, its, opt []graph.IteratorShape) (graph.IteratorCosts, []graph.IteratorCosts, error) {
 	if len(its) == 0 {
-		return graph.IteratorStats{}, nil
+		return graph.IteratorCosts{}, nil, nil
 	}
 
-	arr := make([]graph.IteratorStats, 0, len(its))
+	arr := make([]graph.IteratorCosts, 0, len(its))
 
-	primaryStats := its[0].Stats()
+	primaryStats, _ := its[0].Stats(ctx)
 	arr = append(arr, primaryStats)
 
 	containsCost := primaryStats.ContainsCost
 	nextCost := primaryStats.NextCost
-	size := primaryStats.Size
-	exact := primaryStats.ExactSize
+	size := primaryStats.Size.Size
+	exact := primaryStats.Size.Exact
 
+	var last error
 	for _, sub := range its[1:] {
-		stats := sub.Stats()
+		stats, err := sub.Stats(ctx)
+		if err != nil {
+			last = err
+		}
 		arr = append(arr, stats)
-		nextCost += stats.ContainsCost * (1 + (primaryStats.Size / (stats.Size + 1)))
+		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Size / (stats.Size.Size + 1)))
 		containsCost += stats.ContainsCost
-		if size > stats.Size {
-			size = stats.Size
-			exact = stats.ExactSize
+		if size > stats.Size.Size {
+			size = stats.Size.Size
+			exact = stats.Size.Exact
 		}
 	}
 	for _, sub := range opt {
-		stats := sub.Stats()
-		nextCost += stats.ContainsCost * (1 + (primaryStats.Size / (stats.Size + 1)))
+		stats, _ := sub.Stats(ctx)
+		nextCost += stats.ContainsCost * (1 + (primaryStats.Size.Size / (stats.Size.Size + 1)))
 		containsCost += stats.ContainsCost
 	}
-	return graph.IteratorStats{
+	return graph.IteratorCosts{
 		ContainsCost: containsCost,
 		NextCost:     nextCost,
-		Size:         size,
-		ExactSize:    exact,
-	}, arr
+		Size: graph.Size{
+			Size:  size,
+			Exact: exact,
+		},
+	}, arr, last
 }
 
 // and.Stats() lives here in and-iterator-optimize.go because it may
 // in the future return different statistics based on how it is optimized.
 // For now, however, it's pretty static.
-func (it *And) Stats() graph.IteratorStats {
-	stats, _ := getStatsForSlice(it.subIterators(), it.opt)
-	stats.Next = it.runstats.Next
-	stats.Contains = it.runstats.Contains
-	return stats
+//
+// Returns the approximate size of the And iterator. Because we're dealing
+// 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) {
+	stats, _, err := getStatsForSlice(ctx, it.sub, it.opt)
+	return stats, err
 }
diff --git a/graph/iterator/count.go b/graph/iterator/count.go
index f505f3d..c9b6fd4 100644
--- a/graph/iterator/count.go
+++ b/graph/iterator/count.go
@@ -7,114 +7,196 @@ import (
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = &Count{}
+var _ graph.IteratorFuture = &Count{}
 
 // Count iterator returns one element with size of underlying iterator.
 type Count struct {
-	uid    uint64
-	it     graph.Iterator
-	done   bool
-	result quad.Value
-	qs     graph.Namer
+	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(it graph.Iterator, qs graph.Namer) *Count {
-	return &Count{
-		uid: NextUID(),
-		it:  it, qs: qs,
+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) UID() uint64 {
-	return it.uid
+func (it *Count) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-// Reset resets the internal iterators and the iterator itself.
-func (it *Count) Reset() {
-	it.done = false
-	it.result = nil
-	it.it.Reset()
+var _ graph.IteratorShapeCompat = &count{}
+
+// Count iterator returns one element with size of underlying iterator.
+type count struct {
+	it graph.IteratorShape
+	qs graph.Namer
 }
 
-func (it *Count) TagResults(dst map[string]graph.Ref) {}
+// 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{
+		it: it, qs: qs,
+	}
+}
+
+func (it *count) Iterate() graph.Scanner {
+	return newCountNext(it.it)
+}
+
+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.Iterator {
-	return []graph.Iterator{it.it}
+func (it *count) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.it}
+}
+
+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) {
+	stats := graph.IteratorCosts{
+		NextCost: 1,
+		Size: graph.Size{
+			Size:  1,
+			Exact: true,
+		},
+	}
+	if sub, err := it.it.Stats(ctx); err == nil && !sub.Size.Exact {
+		stats.NextCost = sub.NextCost * sub.Size.Size
+	}
+	stats.ContainsCost = stats.NextCost
+	return stats, nil
+}
+
+func (it *count) String() string { return "Count" }
+
+// Count iterator returns one element with size of underlying iterator.
+type countNext struct {
+	it     graph.IteratorShape
+	done   bool
+	result quad.Value
+	err    error
+}
+
+// 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 newCountNext(it graph.IteratorShape) *countNext {
+	return &countNext{
+		it: it,
+	}
 }
 
+func (it *countNext) TagResults(dst map[string]graph.Ref) {}
+
 // Next counts a number of results in underlying iterator.
-func (it *Count) Next(ctx context.Context) bool {
+func (it *countNext) Next(ctx context.Context) bool {
 	if it.done {
 		return false
 	}
-	size, exact := it.it.Size()
-	if !exact {
-		for size = 0; it.it.Next(ctx); size++ {
-			for ; it.it.NextPath(ctx); size++ {
+	// TODO(dennwc): this most likely won't include the NextPath
+	st, err := it.it.Stats(ctx)
+	if err != nil {
+		it.err = err
+		return false
+	}
+	if !st.Size.Exact {
+		sit := it.it.Iterate()
+		defer sit.Close()
+		for st.Size.Size = 0; sit.Next(ctx); st.Size.Size++ {
+			// TODO(dennwc): it's unclear if we should call it here or not
+			for ; sit.NextPath(ctx); st.Size.Size++ {
 			}
 		}
+		it.err = sit.Err()
 	}
-	it.result = quad.Int(size)
+	it.result = quad.Int(st.Size.Size)
 	it.done = true
 	return true
 }
 
-func (it *Count) Err() error {
-	return it.it.Err()
+func (it *countNext) Err() error {
+	return it.err
 }
 
-func (it *Count) Result() graph.Ref {
+func (it *countNext) Result() graph.Ref {
 	if it.result == nil {
 		return nil
 	}
 	return graph.PreFetched(it.result)
 }
 
-func (it *Count) Contains(ctx context.Context, val graph.Ref) bool {
-	if !it.done {
-		it.Next(ctx)
-	}
-	if v, ok := val.(graph.PreFetchedValue); ok {
-		return v.NameOf() == it.result
-	}
-	if it.qs != nil {
-		return it.qs.NameOf(val) == it.result
-	}
+func (it *countNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Count) NextPath(ctx context.Context) bool {
-	return false
+func (it *countNext) Close() error {
+	return nil
 }
 
-func (it *Count) Close() error {
-	return it.it.Close()
+func (it *countNext) String() string { return "CountNext" }
+
+// Count iterator returns one element with size of underlying iterator.
+type countContains struct {
+	it *countNext
+	qs graph.Namer
 }
 
-func (it *Count) Optimize() (graph.Iterator, bool) {
-	sub, optimized := it.it.Optimize()
-	it.it = sub
-	return it, optimized
+// 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 newCountContains(it graph.IteratorShape, qs graph.Namer) *countContains {
+	return &countContains{
+		it: newCountNext(it),
+		qs: qs,
+	}
+}
+
+func (it *countContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *countContains) Err() error {
+	return it.it.Err()
+}
+
+func (it *countContains) Result() graph.Ref {
+	return it.it.Result()
 }
 
-func (it *Count) Stats() graph.IteratorStats {
-	stats := graph.IteratorStats{
-		NextCost:  1,
-		Size:      1,
-		ExactSize: true,
+func (it *countContains) Contains(ctx context.Context, val graph.Ref) bool {
+	if !it.it.done {
+		it.it.Next(ctx)
+	}
+	if v, ok := val.(graph.PreFetchedValue); ok {
+		return v.NameOf() == it.it.result
 	}
-	if sub := it.it.Stats(); !sub.ExactSize {
-		stats.NextCost = sub.NextCost * sub.Size
+	if it.qs != nil {
+		return it.qs.NameOf(val) == it.it.result
 	}
-	stats.ContainsCost = stats.NextCost
-	return stats
+	return false
 }
 
-func (it *Count) Size() (int64, bool) {
-	return 1, true
+func (it *countContains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *countContains) Close() error {
+	return it.it.Close()
 }
 
-func (it *Count) String() string { return "Count" }
+func (it *countContains) String() string { return "CountContains" }
diff --git a/graph/iterator/fixed.go b/graph/iterator/fixed.go
index d9ae219..b34fec5 100644
--- a/graph/iterator/fixed.go
+++ b/graph/iterator/fixed.go
@@ -27,125 +27,214 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Fixed{}
+var _ graph.IteratorFuture = &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 {
-	uid       uint64
-	values    []graph.Ref
-	lastIndex int
-	result    graph.Ref
+	it *fixed
+	graph.Iterator
 }
 
 // Creates a new Fixed iterator with a custom comparator.
 func NewFixed(vals ...graph.Ref) *Fixed {
 	it := &Fixed{
-		uid:    NextUID(),
-		values: make([]graph.Ref, 0, 20),
-	}
-	for _, v := range vals {
-		it.Add(v)
+		it: newFixed(vals...),
 	}
+	it.Iterator = graph.AsLegacy(it.it)
 	return it
 }
 
-func (it *Fixed) UID() uint64 {
-	return it.uid
+// 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)
 }
 
-func (it *Fixed) Reset() {
-	it.lastIndex = 0
+// 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) Close() error {
-	return nil
+func (it *Fixed) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-func (it *Fixed) TagResults(dst map[string]graph.Ref) {}
+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{
+		values: append([]graph.Ref{}, vals...),
+	}
+}
+
+func (it *fixed) Iterate() graph.Scanner {
+	return newFixedNext(it.values)
+}
+
+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 should not be modified.
-func (it *Fixed) Values() []graph.Ref {
+// Values returns a list of values stored in iterator. Slice must not be modified.
+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)
 }
 
-// Check if the passed value is equal to one of the values stored in the iterator.
-func (it *Fixed) Contains(ctx context.Context, v graph.Ref) bool {
-	// Could be optimized by keeping it sorted or using a better datastructure.
-	// However, for fixed iterators, which are by definition kind of tiny, this
-	// isn't a big issue.
-	vk := graph.ToKey(v)
-	for _, x := range it.values {
-		if graph.ToKey(x) == vk {
-			it.result = x
-			return true
-		}
+// No sub-iterators.
+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) {
+	if len(it.values) == 1 && it.values[0] == nil {
+		return newNull(), true
 	}
-	return false
+
+	return it, false
+}
+
+// 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) {
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     1,
+		Size: graph.Size{
+			Size:  int64(len(it.values)),
+			Exact: true,
+		},
+	}, nil
+}
+
+// A Fixed iterator consists of it's values, an index (where it is in the process of Next()ing) and
+// an equality function.
+type fixedNext struct {
+	values []graph.Ref
+	ind    int
+	result graph.Ref
+}
+
+// Creates a new Fixed iterator with a custom comparator.
+func newFixedNext(vals []graph.Ref) *fixedNext {
+	return &fixedNext{
+		values: vals,
+	}
+}
+
+func (it *fixedNext) Close() error {
+	return nil
+}
+
+func (it *fixedNext) TagResults(dst map[string]graph.Ref) {}
+
+func (it *fixedNext) String() string {
+	return fmt.Sprintf("Fixed(%v)", it.values)
 }
 
 // Next advances the iterator.
-func (it *Fixed) Next(ctx context.Context) bool {
-	if it.lastIndex == len(it.values) {
+func (it *fixedNext) Next(ctx context.Context) bool {
+	if it.ind >= len(it.values) {
 		return false
 	}
-	out := it.values[it.lastIndex]
+	out := it.values[it.ind]
 	it.result = out
-	it.lastIndex++
+	it.ind++
 	return true
 }
 
-func (it *Fixed) Err() error {
+func (it *fixedNext) Err() error {
 	return nil
 }
 
-func (it *Fixed) Result() graph.Ref {
+func (it *fixedNext) Result() graph.Ref {
 	return it.result
 }
 
-func (it *Fixed) NextPath(ctx context.Context) bool {
+func (it *fixedNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
-// No sub-iterators.
-func (it *Fixed) SubIterators() []graph.Iterator {
-	return nil
+// A Fixed iterator consists of it's values, an index (where it is in the process of Next()ing) and
+// an equality function.
+type fixedContains struct {
+	values []graph.Ref
+	keys   []interface{}
+	result graph.Ref
 }
 
-// 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() (graph.Iterator, bool) {
-	if len(it.values) == 1 && it.values[0] == nil {
-		return NewNull(), true
+// Creates a new Fixed iterator with a custom comparator.
+func newFixedContains(vals []graph.Ref) *fixedContains {
+	keys := make([]interface{}, 0, len(vals))
+	for _, v := range vals {
+		keys = append(keys, graph.ToKey(v))
+	}
+	return &fixedContains{
+		values: vals,
+		keys:   keys,
 	}
+}
 
-	return it, false
+func (it *fixedContains) Close() error {
+	return nil
 }
 
-// Size is the number of values stored.
-func (it *Fixed) Size() (int64, bool) {
-	return int64(len(it.values)), true
+func (it *fixedContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *fixedContains) String() string {
+	return fmt.Sprintf("Fixed(%v)", it.values)
 }
 
-// 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() graph.IteratorStats {
-	s, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: s,
-		NextCost:     s,
-		Size:         s,
-		ExactSize:    exact,
+// Check if the passed value is equal to one of the values stored in the iterator.
+func (it *fixedContains) Contains(ctx context.Context, v graph.Ref) bool {
+	// Could be optimized by keeping it sorted or using a better datastructure.
+	// However, for fixed iterators, which are by definition kind of tiny, this
+	// isn't a big issue.
+	vk := graph.ToKey(v)
+	for i, x := range it.keys {
+		if x == vk {
+			it.result = it.values[i]
+			return true
+		}
 	}
+	return false
+}
+
+func (it *fixedContains) Err() error {
+	return nil
+}
+
+func (it *fixedContains) Result() graph.Ref {
+	return it.result
+}
+
+func (it *fixedContains) NextPath(ctx context.Context) bool {
+	return false
 }
diff --git a/graph/iterator/hasa.go b/graph/iterator/hasa.go
index 8f74dab..1cc43ed 100644
--- a/graph/iterator/hasa.go
+++ b/graph/iterator/hasa.go
@@ -42,118 +42,256 @@ import (
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = &HasA{}
+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 {
-	uid       uint64
-	qs        graph.QuadIndexer
-	primaryIt graph.Iterator
-	dir       quad.Direction
-	resultIt  graph.Iterator
-	result    graph.Ref
-	runstats  graph.IteratorStats
-	err       error
+	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 {
-	return &HasA{
-		uid:       NextUID(),
-		qs:        qs,
-		primaryIt: subIt,
-		dir:       d,
+	it := &HasA{
+		it: newHasA(qs, graph.AsShape(subIt), d),
 	}
+	it.Iterator = graph.NewLegacy(it.it, it)
+	return it
 }
 
-func (it *HasA) UID() uint64 {
-	return it.uid
+func (it *HasA) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-// Return our sole subiterator.
-func (it *HasA) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.primaryIt}
+// 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
 }
 
-func (it *HasA) Reset() {
-	it.primaryIt.Reset()
-	if it.resultIt != nil {
-		it.resultIt.Close()
+// 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{
+		qs:      qs,
+		primary: subIt,
+		dir:     d,
 	}
 }
 
+func (it *hasA) Iterate() graph.Scanner {
+	return newHasANext(it.qs, it.primary.Iterate(), it.dir)
+}
+
+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 {
+	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() (graph.Iterator, bool) {
-	newPrimary, changed := it.primaryIt.Optimize()
+func (it *hasA) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	newPrimary, changed := it.primary.Optimize(ctx)
 	if changed {
-		it.primaryIt = newPrimary
-		if _, ok := it.primaryIt.(*Null); ok {
-			return it.primaryIt, true
+		it.primary = newPrimary
+		if IsNull2(it.primary) {
+			return it.primary, true
 		}
 	}
 	return it, false
 }
 
+func (it *hasA) String() string {
+	return fmt.Sprintf("HasA(%v)", it.dir)
+}
+
+// GetStats() returns the statistics on the HasA iterator. This is curious. Next
+// cost is easy, it's an extra call or so on top of the subiterator Next cost.
+// ContainsCost involves going to the graph.QuadStore, iterating out values, and hoping
+// 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) {
+	subitStats, err := it.primary.Stats(ctx)
+	// TODO(barakmich): These should really come from the quadstore itself
+	// and be optimized.
+	faninFactor := int64(1)
+	fanoutFactor := int64(30)
+	nextConstant := int64(2)
+	quadConstant := int64(1)
+	return graph.IteratorCosts{
+		NextCost:     quadConstant + subitStats.NextCost,
+		ContainsCost: (fanoutFactor * nextConstant) * subitStats.ContainsCost,
+		Size: graph.Size{
+			Size:  faninFactor * subitStats.Size.Size,
+			Exact: false,
+		},
+	}, err
+}
+
+// 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 hasANext struct {
+	qs      graph.QuadIndexer
+	primary graph.Scanner
+	dir     quad.Direction
+	result  graph.Ref
+}
+
+// Construct a new HasA iterator, given the quad subiterator, and the quad
+// direction for which it stands.
+func newHasANext(qs graph.QuadIndexer, subIt graph.Scanner, d quad.Direction) *hasANext {
+	return &hasANext{
+		qs:      qs,
+		primary: subIt,
+		dir:     d,
+	}
+}
+
+// Direction accessor.
+func (it *hasANext) Direction() quad.Direction { return it.dir }
+
 // Pass the TagResults down the chain.
-func (it *HasA) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+func (it *hasANext) TagResults(dst map[string]graph.Ref) {
+	it.primary.TagResults(dst)
 }
 
-func (it *HasA) String() string {
-	return fmt.Sprintf("HasA(%v)", it.dir)
+func (it *hasANext) String() string {
+	return fmt.Sprintf("HasANext(%v)", it.dir)
+}
+
+// Get the next result that matches this branch.
+func (it *hasANext) NextPath(ctx context.Context) bool {
+	return it.primary.NextPath(ctx)
+}
+
+// Next advances the iterator. This is simpler than Contains. We have a
+// subiterator we can get a value from, and we can take that resultant quad,
+// pull our direction out of it, and return that.
+func (it *hasANext) Next(ctx context.Context) bool {
+	if !it.primary.Next(ctx) {
+		return false
+	}
+	it.result = it.qs.QuadDirection(it.primary.Result(), it.dir)
+	return true
+}
+
+func (it *hasANext) Err() error {
+	return it.primary.Err()
+}
+
+func (it *hasANext) Result() graph.Ref {
+	return it.result
+}
+
+// Close the subiterator, the result iterator (if any) and the HasA. It closes
+// all subiterators it can, but returns the first error it encounters.
+func (it *hasANext) Close() error {
+	return it.primary.Close()
+}
+
+// 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 hasAContains struct {
+	qs      graph.QuadIndexer
+	primary graph.Index
+	dir     quad.Direction
+	results graph.Scanner
+	result  graph.Ref
+	err     error
+}
+
+// Construct a new HasA iterator, given the quad subiterator, and the quad
+// direction for which it stands.
+func newHasAContains(qs graph.QuadIndexer, subIt graph.Index, d quad.Direction) graph.Index {
+	return &hasAContains{
+		qs:      qs,
+		primary: subIt,
+		dir:     d,
+	}
+}
+
+// Direction accessor.
+func (it *hasAContains) Direction() quad.Direction { return it.dir }
+
+// Pass the TagResults down the chain.
+func (it *hasAContains) TagResults(dst map[string]graph.Ref) {
+	it.primary.TagResults(dst)
+}
+
+func (it *hasAContains) String() string {
+	return fmt.Sprintf("HasAContains(%v)", it.dir)
 }
 
 // Check a value against our internal iterator. In order to do this, we must first open a new
 // iterator of "quads that have `val` in our direction", given to us by the quad store,
 // and then Next() values out of that iterator and Contains() them against our subiterator.
-func (it *HasA) Contains(ctx context.Context, val graph.Ref) bool {
-	it.runstats.Contains += 1
+func (it *hasAContains) Contains(ctx context.Context, val graph.Ref) bool {
 	if clog.V(4) {
 		clog.Infof("Id is %v", val)
 	}
 	// TODO(barakmich): Optimize this
-	if it.resultIt != nil {
-		it.resultIt.Close()
+	if it.results != nil {
+		it.results.Close()
 	}
-	it.resultIt = it.qs.QuadIterator(it.dir, val)
-	ok := it.NextContains(ctx)
+	it.results = graph.AsShape(it.qs.QuadIterator(it.dir, val)).Iterate()
+	ok := it.nextContains(ctx)
 	if it.err != nil {
 		return false
 	}
 	return ok
 }
 
-// NextContains() is shared code between Contains() and GetNextResult() -- calls next on the
+// nextContains() is shared code between Contains() and GetNextResult() -- calls next on the
 // result iterator (a quad iterator based on the last checked value) and returns true if
 // another match is made.
-func (it *HasA) NextContains(ctx context.Context) bool {
-	if it.resultIt == nil {
+func (it *hasAContains) nextContains(ctx context.Context) bool {
+	if it.results == nil {
 		return false
 	}
-	for it.resultIt.Next(ctx) {
-		it.runstats.ContainsNext += 1
-		link := it.resultIt.Result()
+	for it.results.Next(ctx) {
+		link := it.results.Result()
 		if clog.V(4) {
 			clog.Infof("Quad is %v", it.qs.Quad(link))
 		}
-		if it.primaryIt.Contains(ctx, link) {
+		if it.primary.Contains(ctx, link) {
 			it.result = it.qs.QuadDirection(link, it.dir)
 			return true
 		}
 	}
-	it.err = it.resultIt.Err()
+	it.err = it.results.Err()
 	return false
 }
 
 // Get the next result that matches this branch.
-func (it *HasA) NextPath(ctx context.Context) bool {
+func (it *hasAContains) NextPath(ctx context.Context) bool {
 	// Order here is important. If the subiterator has a NextPath, then we
 	// need do nothing -- there is a next result, and we shouldn't move forward.
 	// However, we then need to get the next result from our last Contains().
@@ -161,94 +299,42 @@ func (it *HasA) NextPath(ctx context.Context) bool {
 	// The upshot is, the end of NextPath() bubbles up from the bottom of the
 	// iterator tree up, and we need to respect that.
 	if clog.V(4) {
-		clog.Infof("HASA %v NextPath", it.UID())
+		clog.Infof("HASA %p NextPath", it)
 	}
-	if it.primaryIt.NextPath(ctx) {
+	if it.primary.NextPath(ctx) {
 		return true
 	}
-	it.err = it.primaryIt.Err()
+	it.err = it.primary.Err()
 	if it.err != nil {
 		return false
 	}
 
-	result := it.NextContains(ctx) // Sets it.err if there's an error
+	result := it.nextContains(ctx) // Sets it.err if there's an error
 	if it.err != nil {
 		return false
 	}
 	if clog.V(4) {
-		clog.Infof("HASA %v NextPath Returns %v", it.UID(), result)
+		clog.Infof("HASA %p NextPath Returns %v", it, result)
 	}
 	return result
 }
 
-// Next advances the iterator. This is simpler than Contains. We have a
-// subiterator we can get a value from, and we can take that resultant quad,
-// pull our direction out of it, and return that.
-func (it *HasA) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
-	if it.resultIt != nil {
-		it.resultIt.Close()
-	}
-
-	if !it.primaryIt.Next(ctx) {
-		it.err = it.primaryIt.Err()
-		return false
-	}
-	tID := it.primaryIt.Result()
-	val := it.qs.QuadDirection(tID, it.dir)
-	it.result = val
-	return true
-}
-
-func (it *HasA) Err() error {
+func (it *hasAContains) Err() error {
 	return it.err
 }
 
-func (it *HasA) Result() graph.Ref {
+func (it *hasAContains) Result() graph.Ref {
 	return it.result
 }
 
-// GetStats() returns the statistics on the HasA iterator. This is curious. Next
-// cost is easy, it's an extra call or so on top of the subiterator Next cost.
-// ContainsCost involves going to the graph.QuadStore, iterating out values, and hoping
-// 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() graph.IteratorStats {
-	subitStats := it.primaryIt.Stats()
-	// TODO(barakmich): These should really come from the quadstore itself
-	// and be optimized.
-	faninFactor := int64(1)
-	fanoutFactor := int64(30)
-	nextConstant := int64(2)
-	quadConstant := int64(1)
-	return graph.IteratorStats{
-		NextCost:     quadConstant + subitStats.NextCost,
-		ContainsCost: (fanoutFactor * nextConstant) * subitStats.ContainsCost,
-		Size:         faninFactor * subitStats.Size,
-		ExactSize:    false,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-		ContainsNext: it.runstats.ContainsNext,
-	}
-}
-
 // Close the subiterator, the result iterator (if any) and the HasA. It closes
 // all subiterators it can, but returns the first error it encounters.
-func (it *HasA) Close() error {
-	err := it.primaryIt.Close()
-
-	if it.resultIt != nil {
-		_err := it.resultIt.Close()
-		if err == nil {
-			err = _err
+func (it *hasAContains) Close() error {
+	err := it.primary.Close()
+	if it.results != nil {
+		if err2 := it.results.Close(); err2 != nil && err == nil {
+			err = err2
 		}
 	}
-
 	return err
 }
-
-func (it *HasA) Size() (int64, bool) {
-	st := it.Stats()
-	return st.Size, st.ExactSize
-}
diff --git a/graph/iterator/iterator.go b/graph/iterator/iterator.go
index 4998a64..2642eda 100644
--- a/graph/iterator/iterator.go
+++ b/graph/iterator/iterator.go
@@ -19,42 +19,44 @@ package iterator
 import (
 	"context"
 	"fmt"
-	"sync/atomic"
 
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var nextIteratorID uint64
-
-func init() {
-	atomic.StoreUint64(&nextIteratorID, 1)
-}
-
-func NextUID() uint64 {
-	return atomic.AddUint64(&nextIteratorID, 1) - 1
-}
-
 var (
 	_ graph.Iterator = &Null{}
 	_ graph.Iterator = &Error{}
 )
 
 type Morphism func(graph.Iterator) graph.Iterator
+type Morphism2 func(graph.IteratorShape) graph.IteratorShape
+
+func IsNull(it graph.Iterator) 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
+}
 
 // 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 {
-	uid uint64
-}
+type Null struct{}
 
 // Fairly useless New function.
 func NewNull() *Null {
-	return &Null{uid: NextUID()}
-}
-
-func (it *Null) UID() uint64 {
-	return it.uid
+	return &Null{}
 }
 
 // Fill the map based on the tags assigned to this iterator.
@@ -109,16 +111,11 @@ func (it *Null) Stats() graph.IteratorStats {
 
 // Error iterator always returns a single error with no other results.
 type Error struct {
-	uid uint64
 	err error
 }
 
 func NewError(err error) *Error {
-	return &Error{uid: NextUID(), err: err}
-}
-
-func (it *Error) UID() uint64 {
-	return it.uid
+	return &Error{err: err}
 }
 
 // Fill the map based on the tags assigned to this iterator.
@@ -167,3 +164,140 @@ func (it *Error) Close() error {
 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) {
+	return graph.IteratorCosts{}, nil
+}
diff --git a/graph/iterator/limit.go b/graph/iterator/limit.go
index c5dc9e1..1097cde 100644
--- a/graph/iterator/limit.go
+++ b/graph/iterator/limit.go
@@ -7,46 +7,105 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Limit{}
+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.
 type Limit struct {
-	uid       uint64
-	limit     int64
-	count     int64
-	primaryIt graph.Iterator
+	it *limit
+	graph.Iterator
 }
 
 func NewLimit(primaryIt graph.Iterator, limit int64) *Limit {
-	return &Limit{
-		uid:       NextUID(),
-		limit:     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
+}
+
+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 (it *Limit) UID() uint64 {
-	return it.uid
+func (it *limit) Iterate() graph.Scanner {
+	return newLimitNext(it.primaryIt.Iterate(), it.limit)
 }
 
-// Reset resets the internal iterators and the iterator itself.
-func (it *Limit) Reset() {
-	it.count = 0
-	it.primaryIt.Reset()
+func (it *limit) Lookup() graph.Index {
+	return newLimitContains(it.primaryIt.Lookup(), it.limit)
 }
 
-func (it *Limit) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+func (it *limit) AsLegacy() graph.Iterator {
+	it2 := &Limit{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
 }
 
 // SubIterators returns a slice of the sub iterators.
-func (it *Limit) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.primaryIt}
+func (it *limit) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.primaryIt}
+}
+
+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
+	}
+	it.primaryIt = optimizedPrimaryIt
+	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
+	}
+	return primaryStats, err
+}
+
+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.
+type limitNext struct {
+	limit     int64
+	count     int64
+	primaryIt graph.Scanner
+}
+
+func newLimitNext(primaryIt graph.Scanner, limit int64) *limitNext {
+	return &limitNext{
+		limit:     limit,
+		primaryIt: primaryIt,
+	}
+}
+
+func (it *limitNext) TagResults(dst map[string]graph.Ref) {
+	it.primaryIt.TagResults(dst)
 }
 
 // Next advances the Limit iterator. It will stop iteration if limit was reached.
-func (it *Limit) Next(ctx context.Context) bool {
+func (it *limitNext) Next(ctx context.Context) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
@@ -57,21 +116,17 @@ func (it *Limit) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *Limit) Err() error {
+func (it *limitNext) Err() error {
 	return it.primaryIt.Err()
 }
 
-func (it *Limit) Result() graph.Ref {
+func (it *limitNext) Result() graph.Ref {
 	return it.primaryIt.Result()
 }
 
-func (it *Limit) Contains(ctx context.Context, val graph.Ref) bool {
-	return it.primaryIt.Contains(ctx, val) // FIXME(dennwc): limit is ignored in this case
-}
-
 // NextPath checks whether there is another path. Will call primary iterator
 // if limit is not reached yet.
-func (it *Limit) NextPath(ctx context.Context) bool {
+func (it *limitNext) NextPath(ctx context.Context) bool {
 	if it.limit > 0 && it.count >= it.limit {
 		return false
 	}
@@ -84,35 +139,71 @@ func (it *Limit) 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 *Limit) Close() error {
+func (it *limitNext) Close() error {
 	return it.primaryIt.Close()
 }
 
-func (it *Limit) Optimize() (graph.Iterator, bool) {
-	optimizedPrimaryIt, optimized := it.primaryIt.Optimize()
-	if it.limit <= 0 { // no limit
-		return optimizedPrimaryIt, true
+func (it *limitNext) String() string {
+	return fmt.Sprintf("LimitNext(%d)", it.limit)
+}
+
+// Limit iterator will stop iterating if certain a number of values were encountered.
+// Zero and negative limit values means no limit.
+type limitContains struct {
+	limit     int64
+	count     int64
+	primaryIt graph.Index
+}
+
+func newLimitContains(primaryIt graph.Index, limit int64) *limitContains {
+	return &limitContains{
+		limit:     limit,
+		primaryIt: primaryIt,
 	}
-	it.primaryIt = optimizedPrimaryIt
-	return it, optimized
 }
 
-func (it *Limit) Stats() graph.IteratorStats {
-	primaryStats := it.primaryIt.Stats()
-	if it.limit > 0 && primaryStats.Size > it.limit {
-		primaryStats.Size = it.limit
+func (it *limitContains) TagResults(dst map[string]graph.Ref) {
+	it.primaryIt.TagResults(dst)
+}
+
+func (it *limitContains) Err() error {
+	return it.primaryIt.Err()
+}
+
+func (it *limitContains) Result() graph.Ref {
+	return it.primaryIt.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) {
+		it.count++
+		return true
 	}
-	return primaryStats
+	return false
 }
 
-func (it *Limit) Size() (int64, bool) {
-	primarySize, exact := it.primaryIt.Size()
-	if it.limit > 0 && primarySize > it.limit {
-		primarySize = it.limit
+// NextPath checks whether there is another path. Will call primary iterator
+// if limit is not reached yet.
+func (it *limitContains) NextPath(ctx context.Context) bool {
+	if it.limit > 0 && it.count >= it.limit {
+		return false
 	}
-	return primarySize, exact
+	if it.primaryIt.NextPath(ctx) {
+		it.count++
+		return true
+	}
+	return false
 }
 
-func (it *Limit) String() string {
-	return fmt.Sprintf("Limit(%d)", it.limit)
+// 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()
+}
+
+func (it *limitContains) String() string {
+	return fmt.Sprintf("LimitContains(%d)", it.limit)
 }
diff --git a/graph/iterator/linksto.go b/graph/iterator/linksto.go
index 57c9077..31a5349 100644
--- a/graph/iterator/linksto.go
+++ b/graph/iterator/linksto.go
@@ -37,95 +37,174 @@ import (
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = &LinksTo{}
+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 {
-	uid       uint64
-	qs        graph.QuadIndexer
-	primaryIt graph.Iterator
-	dir       quad.Direction
-	nextIt    graph.Iterator
-	result    graph.Ref
-	runstats  graph.IteratorStats
-	err       error
+	it *linksTo
+	graph.Iterator
 }
 
 // Construct a new LinksTo iterator around a direction and a subiterator of
 // nodes.
-func NewLinksTo(qs graph.QuadIndexer, it graph.Iterator, d quad.Direction) *LinksTo {
-	return &LinksTo{
-		uid:       NextUID(),
-		qs:        qs,
-		primaryIt: it,
-		dir:       d,
-		nextIt:    &Null{},
+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) UID() uint64 {
-	return it.uid
+func (it *LinksTo) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-func (it *LinksTo) Reset() {
-	it.primaryIt.Reset()
-	if it.nextIt != nil {
-		it.nextIt.Close()
+// 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
+	size    graph.Size
+}
+
+// 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{
+		qs:      qs,
+		primary: it,
+		dir:     d,
 	}
-	it.nextIt = &Null{}
 }
 
 // Return the direction under consideration.
-func (it *LinksTo) Direction() quad.Direction { return it.dir }
+func (it *linksTo) Direction() quad.Direction { return it.dir }
 
-// Tag these results, and our subiterator's results.
-func (it *LinksTo) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+func (it *linksTo) Iterate() graph.Scanner {
+	return newLinksToNext(it.qs, it.primary.Iterate(), it.dir)
 }
 
-func (it *LinksTo) String() string {
-	return fmt.Sprintf("LinksTo(%v)", it.dir)
+func (it *linksTo) Lookup() graph.Index {
+	return newLinksToContains(it.qs, it.primary.Lookup(), it.dir)
 }
 
-// If it checks in the right direction for the subiterator, it is a valid link
-// for the LinksTo.
-func (it *LinksTo) Contains(ctx context.Context, val graph.Ref) bool {
-	it.runstats.Contains += 1
-	node := it.qs.QuadDirection(val, it.dir)
-	if it.primaryIt.Contains(ctx, node) {
-		it.result = val
-		return true
-	}
-	it.err = it.primaryIt.Err()
-	return false
+func (it *linksTo) AsLegacy() graph.Iterator {
+	it2 := &LinksTo{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
+}
+
+func (it *linksTo) String() string {
+	return fmt.Sprintf("LinksTo(%v)", it.dir)
 }
 
 // Return a list containing only our subiterator.
-func (it *LinksTo) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.primaryIt}
+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() (graph.Iterator, bool) {
-	newPrimary, changed := it.primaryIt.Optimize()
+func (it *linksTo) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	newPrimary, changed := it.primary.Optimize(ctx)
 	if changed {
-		it.primaryIt = newPrimary
-		if _, ok := it.primaryIt.(*Null); ok {
-			it.nextIt.Close()
-			return it.primaryIt, true
+		it.primary = newPrimary
+		if IsNull2(it.primary) {
+			return it.primary, true
 		}
 	}
 	return it, false
 }
 
+// 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) {
+	subitStats, err := it.primary.Stats(ctx)
+	// TODO(barakmich): These should really come from the quadstore itself
+	checkConstant := int64(1)
+	nextConstant := int64(2)
+	return graph.IteratorCosts{
+		NextCost:     nextConstant + subitStats.NextCost,
+		ContainsCost: checkConstant + subitStats.ContainsCost,
+		Size:         it.getSize(ctx),
+	}, err
+}
+
+func (it *linksTo) getSize(ctx context.Context) graph.Size {
+	if it.size.Size != 0 {
+		return it.size
+	}
+	if fixed, ok := graph.AsLegacy(it.primary).(*Fixed); ok {
+		// get real sizes from sub iterators
+		var (
+			sz    int64
+			exact = true
+		)
+		for _, v := range fixed.Values() {
+			sit := it.qs.QuadIterator(it.dir, v)
+			n, ex := sit.Size()
+			sit.Close()
+			sz += n
+			exact = exact && ex
+		}
+		it.size.Size, 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
+	return it.size
+}
+
+// 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 linksToNext struct {
+	qs      graph.QuadIndexer
+	primary graph.Scanner
+	dir     quad.Direction
+	nextIt  graph.Scanner
+	result  graph.Ref
+	err     error
+}
+
+// Construct a new LinksTo iterator around a direction and a subiterator of
+// nodes.
+func newLinksToNext(qs graph.QuadIndexer, it graph.Scanner, d quad.Direction) graph.Scanner {
+	return &linksToNext{
+		qs:      qs,
+		primary: it,
+		dir:     d,
+		nextIt:  newNull().Iterate(),
+	}
+}
+
+// Return the direction under consideration.
+func (it *linksToNext) Direction() quad.Direction { return it.dir }
+
+// Tag these results, and our subiterator's results.
+func (it *linksToNext) TagResults(dst map[string]graph.Ref) {
+	it.primary.TagResults(dst)
+}
+
+func (it *linksToNext) String() string {
+	return fmt.Sprintf("LinksToNext(%v)", it.dir)
+}
+
 // Next()ing a LinksTo operates as described above.
-func (it *LinksTo) Next(ctx context.Context) bool {
+func (it *linksToNext) Next(ctx context.Context) bool {
 	for {
-		it.runstats.Next += 1
 		if it.nextIt.Next(ctx) {
-			it.runstats.ContainsNext += 1
 			it.result = it.nextIt.Result()
 			return true
 		}
@@ -137,34 +216,34 @@ func (it *LinksTo) Next(ctx context.Context) bool {
 		}
 
 		// Subiterator is empty, get another one
-		if !it.primaryIt.Next(ctx) {
+		if !it.primary.Next(ctx) {
 			// Possibly save error
-			it.err = it.primaryIt.Err()
+			it.err = it.primary.Err()
 
 			// We're out of nodes in our subiterator, so we're done as well.
 			return false
 		}
 		it.nextIt.Close()
-		it.nextIt = it.qs.QuadIterator(it.dir, it.primaryIt.Result())
+		it.nextIt = it.qs.QuadIterator(it.dir, it.primary.Result())
 
 		// Continue -- return the first in the next set.
 	}
 }
 
-func (it *LinksTo) Err() error {
+func (it *linksToNext) Err() error {
 	return it.err
 }
 
-func (it *LinksTo) Result() graph.Ref {
+func (it *linksToNext) Result() graph.Ref {
 	return it.result
 }
 
 // Close closes the iterator.  It closes all subiterators it can, but
 // returns the first error it encounters.
-func (it *LinksTo) Close() error {
+func (it *linksToNext) Close() error {
 	err := it.nextIt.Close()
 
-	_err := it.primaryIt.Close()
+	_err := it.primary.Close()
 	if _err != nil && err == nil {
 		err = _err
 	}
@@ -173,55 +252,72 @@ func (it *LinksTo) Close() error {
 }
 
 // We won't ever have a new result, but our subiterators might.
-func (it *LinksTo) NextPath(ctx context.Context) bool {
-	ok := it.primaryIt.NextPath(ctx)
+func (it *linksToNext) NextPath(ctx context.Context) bool {
+	ok := it.primary.NextPath(ctx)
 	if !ok {
-		it.err = it.primaryIt.Err()
+		it.err = it.primary.Err()
 	}
 	return ok
 }
 
-// Return a guess as to how big or costly it is to next the iterator.
-func (it *LinksTo) Stats() graph.IteratorStats {
-	subitStats := it.primaryIt.Stats()
-	// TODO(barakmich): These should really come from the quadstore itself
-	checkConstant := int64(1)
-	nextConstant := int64(2)
-	st := graph.IteratorStats{
-		NextCost:     nextConstant + subitStats.NextCost,
-		ContainsCost: checkConstant + subitStats.ContainsCost,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-		ContainsNext: it.runstats.ContainsNext,
-	}
-	st.Size, st.ExactSize = it.Size()
-	return st
+// 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 linksToContains struct {
+	qs      graph.QuadIndexer
+	primary graph.Index
+	dir     quad.Direction
+	result  graph.Ref
 }
 
-func (it *LinksTo) Size() (int64, bool) {
-	if it.runstats.Size != 0 {
-		return it.runstats.Size, it.runstats.ExactSize
+// Construct a new LinksTo iterator around a direction and a subiterator of
+// nodes.
+func newLinksToContains(qs graph.QuadIndexer, it graph.Index, d quad.Direction) graph.Index {
+	return &linksToContains{
+		qs:      qs,
+		primary: it,
+		dir:     d,
 	}
-	if fixed, ok := it.primaryIt.(*Fixed); ok {
-		// get real sizes from sub iterators
-		var (
-			sz    int64
-			exact = true
-		)
-		for _, v := range fixed.Values() {
-			sit := it.qs.QuadIterator(it.dir, v)
-			n, ex := sit.Size()
-			sit.Close()
-			sz += n
-			exact = exact && ex
-		}
-		it.runstats.Size, it.runstats.ExactSize = sz, exact
-		return sz, exact
+}
+
+// Return the direction under consideration.
+func (it *linksToContains) Direction() quad.Direction { return it.dir }
+
+// Tag these results, and our subiterator's results.
+func (it *linksToContains) TagResults(dst map[string]graph.Ref) {
+	it.primary.TagResults(dst)
+}
+
+func (it *linksToContains) String() string {
+	return fmt.Sprintf("LinksToContains(%v)", it.dir)
+}
+
+// If it checks in the right direction for the subiterator, it is a valid link
+// for the LinksTo.
+func (it *linksToContains) Contains(ctx context.Context, val graph.Ref) bool {
+	node := it.qs.QuadDirection(val, it.dir)
+	if it.primary.Contains(ctx, node) {
+		it.result = val
+		return true
 	}
-	// TODO(barakmich): It should really come from the quadstore itself
-	const fanoutFactor = 20
-	sz, _ := it.primaryIt.Size()
-	sz *= fanoutFactor
-	it.runstats.Size, it.runstats.ExactSize = sz, false
-	return sz, false
+	return false
+}
+
+func (it *linksToContains) Err() error {
+	return it.primary.Err()
+}
+
+func (it *linksToContains) Result() graph.Ref {
+	return it.result
+}
+
+// Close closes the iterator.  It closes all subiterators it can, but
+// returns the first error it encounters.
+func (it *linksToContains) Close() error {
+	return it.primary.Close()
+}
+
+// We won't ever have a new result, but our subiterators might.
+func (it *linksToContains) NextPath(ctx context.Context) bool {
+	return it.primary.NextPath(ctx)
 }
diff --git a/graph/iterator/materialize.go b/graph/iterator/materialize.go
index 76544ea..204f088 100644
--- a/graph/iterator/materialize.go
+++ b/graph/iterator/materialize.go
@@ -23,8 +23,6 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Materialize{}
-
 const MaterializeLimit = 1000
 
 type result struct {
@@ -32,57 +30,138 @@ type result struct {
 	tags map[string]graph.Ref
 }
 
+var _ graph.IteratorFuture = &Materialize{}
+
 type Materialize struct {
-	uid         uint64
+	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 newMaterializeWithSize(sub graph.IteratorShape, size int64) *materialize {
+	return &materialize{
+		sub:        sub,
+		expectSize: size,
+	}
+}
+
+func (it *materialize) Iterate() graph.Scanner {
+	return newMaterializeNext(it.sub)
+}
+
+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 {
+	return "Materialize"
+}
+
+func (it *materialize) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.sub}
+}
+
+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) {
+			return it.sub, true
+		}
+	}
+	return it, false
+}
+
+// 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) {
+	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}
+	} else {
+		size = subitStats.Size
+	}
+	return graph.IteratorCosts{
+		ContainsCost: overhead * subitStats.NextCost,
+		NextCost:     overhead * subitStats.NextCost,
+		Size:         size,
+	}, err
+}
+
+type materializeNext struct {
+	sub  graph.IteratorShape
+	next graph.Scanner
+
 	containsMap map[interface{}]int
 	values      [][]result
-	actualSize  int64
-	expectSize  int64
 	index       int
 	subindex    int
-	subIt       graph.Iterator
 	hasRun      bool
 	aborted     bool
-	runstats    graph.IteratorStats
 	err         error
 }
 
-func NewMaterialize(sub graph.Iterator) *Materialize {
-	return NewMaterializeWithSize(sub, 0)
-}
-
-func NewMaterializeWithSize(sub graph.Iterator, size int64) *Materialize {
-	return &Materialize{
-		uid:         NextUID(),
-		expectSize:  size,
+func newMaterializeNext(sub graph.IteratorShape) *materializeNext {
+	return &materializeNext{
 		containsMap: make(map[interface{}]int),
-		subIt:       sub,
+		sub:         sub,
+		next:        sub.Iterate(),
 		index:       -1,
 	}
 }
 
-func (it *Materialize) UID() uint64 {
-	return it.uid
-}
-
-func (it *Materialize) Reset() {
-	it.subIt.Reset()
-	it.index = -1
-}
-
-func (it *Materialize) Close() error {
+func (it *materializeNext) Close() error {
 	it.containsMap = nil
 	it.values = nil
 	it.hasRun = false
-	return it.subIt.Close()
+	return it.next.Close()
 }
 
-func (it *Materialize) TagResults(dst map[string]graph.Ref) {
+func (it *materializeNext) TagResults(dst map[string]graph.Ref) {
 	if !it.hasRun {
 		return
 	}
 	if it.aborted {
-		it.subIt.TagResults(dst)
+		it.next.TagResults(dst)
 		return
 	}
 	if it.Result() == nil {
@@ -93,13 +172,13 @@ func (it *Materialize) TagResults(dst map[string]graph.Ref) {
 	}
 }
 
-func (it *Materialize) String() string {
+func (it *materializeNext) String() string {
 	return "Materialize"
 }
 
-func (it *Materialize) Result() graph.Ref {
+func (it *materializeNext) Result() graph.Ref {
 	if it.aborted {
-		return it.subIt.Result()
+		return it.next.Result()
 	}
 	if len(it.values) == 0 {
 		return nil
@@ -113,62 +192,7 @@ func (it *Materialize) Result() graph.Ref {
 	return it.values[it.index][it.subindex].id
 }
 
-func (it *Materialize) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.subIt}
-}
-
-func (it *Materialize) Optimize() (graph.Iterator, bool) {
-	newSub, changed := it.subIt.Optimize()
-	if changed {
-		it.subIt = newSub
-		if _, ok := it.subIt.(*Null); ok {
-			return it.subIt, true
-		}
-	}
-	return it, false
-}
-
-// Size is the number of values stored, if we've got them all.
-// Otherwise, guess based on the size of the subiterator.
-func (it *Materialize) Size() (int64, bool) {
-	if it.hasRun && !it.aborted {
-		if clog.V(2) {
-			clog.Infof("returning size %v", it.actualSize)
-		}
-		return it.actualSize, true
-	}
-	if clog.V(2) {
-		clog.Infof("bailing size %v", it.actualSize)
-	}
-	return it.subIt.Size()
-}
-
-// The entire point of Materialize is to amortize the cost by
-// putting it all up front.
-func (it *Materialize) Stats() graph.IteratorStats {
-	overhead := int64(2)
-	var (
-		size  int64
-		exact bool
-	)
-	if it.expectSize > 0 {
-		size, exact = it.expectSize, false
-	} else {
-		size, exact = it.Size()
-	}
-	subitStats := it.subIt.Stats()
-	return graph.IteratorStats{
-		ContainsCost: overhead * subitStats.NextCost,
-		NextCost:     overhead * subitStats.NextCost,
-		Size:         size,
-		ExactSize:    exact,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-	}
-}
-
-func (it *Materialize) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
+func (it *materializeNext) Next(ctx context.Context) bool {
 	if !it.hasRun {
 		it.materializeSet(ctx)
 	}
@@ -176,8 +200,8 @@ func (it *Materialize) Next(ctx context.Context) bool {
 		return false
 	}
 	if it.aborted {
-		n := it.subIt.Next(ctx)
-		it.err = it.subIt.Err()
+		n := it.next.Next(ctx)
+		it.err = it.next.Err()
 		return n
 	}
 
@@ -189,12 +213,11 @@ func (it *Materialize) Next(ctx context.Context) bool {
 	return true
 }
 
-func (it *Materialize) Err() error {
+func (it *materializeNext) Err() error {
 	return it.err
 }
 
-func (it *Materialize) Contains(ctx context.Context, v graph.Ref) bool {
-	it.runstats.Contains += 1
+func (it *materializeNext) NextPath(ctx context.Context) bool {
 	if !it.hasRun {
 		it.materializeSet(ctx)
 	}
@@ -202,26 +225,7 @@ func (it *Materialize) Contains(ctx context.Context, v graph.Ref) bool {
 		return false
 	}
 	if it.aborted {
-		return it.subIt.Contains(ctx, v)
-	}
-	key := graph.ToKey(v)
-	if i, ok := it.containsMap[key]; ok {
-		it.index = i
-		it.subindex = 0
-		return true
-	}
-	return false
-}
-
-func (it *Materialize) NextPath(ctx context.Context) bool {
-	if !it.hasRun {
-		it.materializeSet(ctx)
-	}
-	if it.err != nil {
-		return false
-	}
-	if it.aborted {
-		return it.subIt.NextPath(ctx)
+		return it.next.NextPath(ctx)
 	}
 
 	it.subindex++
@@ -233,16 +237,16 @@ func (it *Materialize) NextPath(ctx context.Context) bool {
 	return true
 }
 
-func (it *Materialize) materializeSet(ctx context.Context) {
+func (it *materializeNext) materializeSet(ctx context.Context) {
 	i := 0
 	mn := 0
-	for it.subIt.Next(ctx) {
+	for it.next.Next(ctx) {
 		i++
 		if i > MaterializeLimit {
 			it.aborted = true
 			break
 		}
-		id := it.subIt.Result()
+		id := it.next.Result()
 		val := graph.ToKey(id)
 		if _, ok := it.containsMap[val]; !ok {
 			it.containsMap[val] = len(it.values)
@@ -250,35 +254,122 @@ func (it *Materialize) materializeSet(ctx context.Context) {
 		}
 		index := it.containsMap[val]
 		tags := make(map[string]graph.Ref, mn)
-		it.subIt.TagResults(tags)
+		it.next.TagResults(tags)
 		if n := len(tags); n > mn {
 			n = mn
 		}
 		it.values[index] = append(it.values[index], result{id: id, tags: tags})
-		it.actualSize += 1
-		for it.subIt.NextPath(ctx) {
+		for it.next.NextPath(ctx) {
 			i++
 			if i > MaterializeLimit {
 				it.aborted = true
 				break
 			}
 			tags := make(map[string]graph.Ref, mn)
-			it.subIt.TagResults(tags)
+			it.next.TagResults(tags)
 			if n := len(tags); n > mn {
 				n = mn
 			}
 			it.values[index] = append(it.values[index], result{id: id, tags: tags})
-			it.actualSize += 1
 		}
 	}
-	it.err = it.subIt.Err()
+	it.err = it.next.Err()
 	if it.err == nil && it.aborted {
 		if clog.V(2) {
 			clog.Infof("Aborting subiterator")
 		}
 		it.values = nil
 		it.containsMap = nil
-		it.subIt.Reset()
+		_ = it.next.Close()
+		it.next = it.sub.Iterate()
 	}
 	it.hasRun = true
 }
+
+type materializeContains struct {
+	next *materializeNext
+	sub  graph.Index // only set if aborted
+}
+
+func newMaterializeContains(sub graph.IteratorShape) *materializeContains {
+	return &materializeContains{
+		next: newMaterializeNext(sub),
+	}
+}
+
+func (it *materializeContains) Close() error {
+	err := it.next.Close()
+	if it.sub != nil {
+		if err2 := it.sub.Close(); err2 != nil && err == nil {
+			err = err2
+		}
+	}
+	return err
+}
+
+func (it *materializeContains) TagResults(dst map[string]graph.Ref) {
+	if it.sub != nil {
+		it.sub.TagResults(dst)
+		return
+	}
+	it.next.TagResults(dst)
+}
+
+func (it *materializeContains) String() string {
+	return "MaterializeContains"
+}
+
+func (it *materializeContains) Result() graph.Ref {
+	if it.sub != nil {
+		return it.sub.Result()
+	}
+	return it.next.Result()
+}
+
+func (it *materializeContains) Err() error {
+	if err := it.next.Err(); err != nil {
+		return err
+	} else if it.sub == nil {
+		return nil
+	}
+	return it.sub.Err()
+}
+
+func (it *materializeContains) run(ctx context.Context) {
+	it.next.materializeSet(ctx)
+	if it.next.aborted {
+		it.sub = it.next.sub.Lookup()
+	}
+}
+
+func (it *materializeContains) Contains(ctx context.Context, v graph.Ref) bool {
+	if !it.next.hasRun {
+		it.run(ctx)
+	}
+	if it.next.Err() != nil {
+		return false
+	}
+	if it.sub != nil {
+		return it.sub.Contains(ctx, v)
+	}
+	key := graph.ToKey(v)
+	if i, ok := it.next.containsMap[key]; ok {
+		it.next.index = i
+		it.next.subindex = 0
+		return true
+	}
+	return false
+}
+
+func (it *materializeContains) NextPath(ctx context.Context) bool {
+	if !it.next.hasRun {
+		it.run(ctx)
+	}
+	if it.next.Err() != nil {
+		return false
+	}
+	if it.sub != nil {
+		return it.sub.NextPath(ctx)
+	}
+	return it.next.NextPath(ctx)
+}
diff --git a/graph/iterator/misc.go b/graph/iterator/misc.go
new file mode 100644
index 0000000..d8a7b56
--- /dev/null
+++ b/graph/iterator/misc.go
@@ -0,0 +1,29 @@
+// Copyright 2014 The Cayley Authors. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package iterator
+
+// Defines one of the base iterators, the All iterator. Which, logically
+// enough, represents all nodes or all links in the graph.
+//
+// This particular file is actually vestigial. It's up to the QuadStore to give
+// us an All iterator that represents all things in the graph. So this is
+// really the All iterator for the memstore.QuadStore. That said, it *is* one of
+// the base iterators, and it helps just to see it here.
+
+type Int64Node int64
+
+func (v Int64Node) Key() interface{} { return v }
+
+func (Int64Node) IsNode() bool { return true }
diff --git a/graph/iterator/not.go b/graph/iterator/not.go
index a32e68e..156afe3 100644
--- a/graph/iterator/not.go
+++ b/graph/iterator/not.go
@@ -6,144 +6,219 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Not{}
+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 {
-	uid       uint64
-	primaryIt graph.Iterator
-	allIt     graph.Iterator
-	result    graph.Ref
-	runstats  graph.IteratorStats
-	err       error
+	it *not
+	graph.Iterator
 }
 
 func NewNot(primaryIt, allIt graph.Iterator) *Not {
-	return &Not{
-		uid:       NextUID(),
-		primaryIt: primaryIt,
-		allIt:     allIt,
+	it := &Not{
+		it: newNot(graph.AsShape(primaryIt), graph.AsShape(allIt)),
 	}
+	it.Iterator = graph.NewLegacy(it.it, it)
+	return it
 }
 
-func (it *Not) UID() uint64 {
-	return it.uid
+func (it *Not) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-// Reset resets the internal iterators and the iterator itself.
-func (it *Not) Reset() {
-	it.result = nil
-	it.primaryIt.Reset()
-	it.allIt.Reset()
+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 (it *Not) TagResults(dst map[string]graph.Ref) {
-	if it.primaryIt != nil {
-		it.primaryIt.TagResults(dst)
+func newNot(primaryIt, allIt graph.IteratorShape) *not {
+	return &not{
+		primary: primaryIt,
+		allIt:   allIt,
 	}
 }
 
+func (it *not) Iterate() graph.Scanner {
+	return newNotNext(it.primary.Lookup(), it.allIt.Iterate())
+}
+
+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.Iterator {
-	return []graph.Iterator{it.primaryIt, it.allIt}
+func (it *not) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.primary, it.allIt}
+}
+
+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)
+	return it, false
+}
+
+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 {
+		err = err2
+	}
+	return graph.IteratorCosts{
+		NextCost:     allStats.NextCost + primaryStats.ContainsCost,
+		ContainsCost: primaryStats.ContainsCost,
+		Size: graph.Size{
+			Size:  allStats.Size.Size - primaryStats.Size.Size,
+			Exact: false,
+		},
+	}, err
+}
+
+func (it *not) String() string {
+	return "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 notNext struct {
+	primaryIt graph.Index
+	allIt     graph.Scanner
+	result    graph.Ref
+}
+
+func newNotNext(primaryIt graph.Index, allIt graph.Scanner) *notNext {
+	return &notNext{
+		primaryIt: primaryIt,
+		allIt:     allIt,
+	}
+}
+
+func (it *notNext) TagResults(dst map[string]graph.Ref) {
+	if it.primaryIt != nil {
+		it.primaryIt.TagResults(dst)
+	}
 }
 
 // Next advances the Not iterator. It returns whether there is another valid
 // new value. It fetches the next value of the all iterator which is not
 // contained by the primary iterator.
-func (it *Not) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
-
+func (it *notNext) Next(ctx context.Context) bool {
 	for it.allIt.Next(ctx) {
 		if curr := it.allIt.Result(); !it.primaryIt.Contains(ctx, curr) {
 			it.result = curr
-			it.runstats.ContainsNext += 1
 			return true
 		}
 	}
-	it.err = it.allIt.Err()
 	return false
 }
 
-func (it *Not) Err() error {
+func (it *notNext) Err() error {
+	if err := it.allIt.Err(); err != nil {
+		return err
+	}
+	if err := it.primaryIt.Err(); err != nil {
+		return err
+	}
+	return nil
+}
+
+func (it *notNext) Result() graph.Ref {
+	return it.result
+}
+
+// NextPath checks whether there is another path. Not applicable, hence it will
+// return false.
+func (it *notNext) NextPath(ctx context.Context) bool {
+	return false
+}
+
+// Close closes the primary and all iterators.  It closes all subiterators
+// it can, but returns the first error it encounters.
+func (it *notNext) Close() error {
+	err := it.primaryIt.Close()
+	if err2 := it.allIt.Close(); err2 != nil && err == nil {
+		err = err2
+	}
+	return err
+}
+
+func (it *notNext) String() string {
+	return "NotNext"
+}
+
+// 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 notContains struct {
+	primaryIt graph.Index
+	result    graph.Ref
+	err       error
+}
+
+func newNotContains(primaryIt graph.Index) *notContains {
+	return &notContains{
+		primaryIt: primaryIt,
+	}
+}
+
+func (it *notContains) TagResults(dst map[string]graph.Ref) {
+	if it.primaryIt != nil {
+		it.primaryIt.TagResults(dst)
+	}
+}
+
+func (it *notContains) Err() error {
 	return it.err
 }
 
-func (it *Not) Result() graph.Ref {
+func (it *notContains) Result() graph.Ref {
 	return it.result
 }
 
 // Contains checks whether the passed value is part of the primary iterator's
 // complement. For a valid value, it updates the Result returned by the iterator
 // to the value itself.
-func (it *Not) Contains(ctx context.Context, val graph.Ref) bool {
-	it.runstats.Contains += 1
-
+func (it *notContains) Contains(ctx context.Context, val graph.Ref) bool {
 	if it.primaryIt.Contains(ctx, val) {
 		return false
 	}
-
 	it.err = it.primaryIt.Err()
 	if it.err != nil {
 		// Explicitly return 'false', since an error occurred.
 		return false
 	}
-
 	it.result = val
 	return true
 }
 
 // NextPath checks whether there is another path. Not applicable, hence it will
 // return false.
-func (it *Not) NextPath(ctx context.Context) bool {
+func (it *notContains) NextPath(ctx context.Context) bool {
 	return false
 }
 
 // Close closes the primary and all iterators.  It closes all subiterators
 // it can, but returns the first error it encounters.
-func (it *Not) Close() error {
-	err := it.primaryIt.Close()
-
-	_err := it.allIt.Close()
-	if _err != nil && err == nil {
-		err = _err
-	}
-
-	return err
+func (it *notContains) Close() error {
+	return it.primaryIt.Close()
 }
 
-func (it *Not) Optimize() (graph.Iterator, bool) {
-	// TODO - consider wrapping the primaryIt with a MaterializeIt
-	optimizedPrimaryIt, optimized := it.primaryIt.Optimize()
-	if optimized {
-		it.primaryIt = optimizedPrimaryIt
-	}
-	it.primaryIt = NewMaterialize(it.primaryIt)
-	return it, false
-}
-
-func (it *Not) Stats() graph.IteratorStats {
-	primaryStats := it.primaryIt.Stats()
-	allStats := it.allIt.Stats()
-	return graph.IteratorStats{
-		NextCost:     allStats.NextCost + primaryStats.ContainsCost,
-		ContainsCost: primaryStats.ContainsCost,
-		Size:         allStats.Size - primaryStats.Size,
-		ExactSize:    false,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-		ContainsNext: it.runstats.ContainsNext,
-	}
-}
-
-func (it *Not) Size() (int64, bool) {
-	st := it.Stats()
-	return st.Size, st.ExactSize
-}
-
-func (it *Not) String() string {
-	return "Not"
+func (it *notContains) String() string {
+	return "NotContains"
 }
diff --git a/graph/iterator/or.go b/graph/iterator/or.go
index f4b1901..f3f4f23 100644
--- a/graph/iterator/or.go
+++ b/graph/iterator/or.go
@@ -27,22 +27,61 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Or{}
+var _ graph.IteratorFuture = &Or{}
 
 type Or struct {
-	uid               uint64
+	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
-	internalIterators []graph.Iterator
-	currentIterator   int
+	sub               []graph.IteratorShape
+	curInd            int
 	result            graph.Ref
 	err               error
 }
 
-func NewOr(sub ...graph.Iterator) *Or {
-	it := &Or{
-		uid:               NextUID(),
-		internalIterators: make([]graph.Iterator, 0, 20),
-		currentIterator:   -1,
+func newOr(sub ...graph.IteratorShape) *or {
+	it := &or{
+		sub:    make([]graph.IteratorShape, 0, 20),
+		curInd: -1,
 	}
 	for _, s := range sub {
 		it.AddSubIterator(s)
@@ -50,61 +89,141 @@ func NewOr(sub ...graph.Iterator) *Or {
 	return it
 }
 
-func NewShortCircuitOr() *Or {
-	return &Or{
-		uid:               NextUID(),
-		internalIterators: make([]graph.Iterator, 0, 20),
+func newShortCircuitOr(sub ...graph.IteratorShape) *or {
+	it := &or{
+		sub:               make([]graph.IteratorShape, 0, 20),
 		isShortCircuiting: true,
-		currentIterator:   -1,
+		curInd:            -1,
 	}
+	for _, s := range sub {
+		it.AddSubIterator(s)
+	}
+	return it
 }
 
-func (it *Or) UID() uint64 {
-	return it.uid
+func (it *or) Iterate() graph.Scanner {
+	sub := make([]graph.Scanner, 0, len(it.sub))
+	for _, s := range it.sub {
+		sub = append(sub, s.Iterate())
+	}
+	return newOrNext(sub, it.isShortCircuiting)
 }
 
-// Reset all internal iterators
-func (it *Or) Reset() {
-	for _, sub := range it.internalIterators {
-		sub.Reset()
+func (it *or) Lookup() graph.Index {
+	sub := make([]graph.Index, 0, len(it.sub))
+	for _, s := range it.sub {
+		sub = append(sub, s.Lookup())
 	}
-	it.currentIterator = -1
+	return newOrContains(sub, it.isShortCircuiting)
 }
 
-// Returns a list.List of the subiterators, in order. The returned slice must not be modified.
-func (it *Or) SubIterators() []graph.Iterator {
-	return it.internalIterators
+func (it *or) AsLegacy() graph.Iterator {
+	it2 := &Or{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
 }
 
-// Overrides BaseIterator TagResults, as it needs to add it's own results and
-// recurse down it's subiterators.
-func (it *Or) TagResults(dst map[string]graph.Ref) {
-	it.internalIterators[it.currentIterator].TagResults(dst)
+// Returns a list.List of the subiterators, in order. The returned slice must not be modified.
+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.Iterator) {
-	it.internalIterators = append(it.internalIterators, sub)
+func (it *or) AddSubIterator(sub graph.IteratorShape) {
+	it.sub = append(it.sub, sub)
+}
+
+func (it *or) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	old := it.SubIterators()
+	optIts := optimizeSubIterators2(ctx, old)
+	newOr := newOr()
+	newOr.isShortCircuiting = it.isShortCircuiting
+
+	// Add the subiterators in order.
+	for _, o := range optIts {
+		newOr.AddSubIterator(o)
+	}
+	return newOr, true
+}
+
+// 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) {
+	ContainsCost := int64(0)
+	NextCost := int64(0)
+	Size := graph.Size{
+		Size:  0,
+		Exact: true,
+	}
+	var last error
+	for _, sub := range it.sub {
+		stats, err := sub.Stats(ctx)
+		if err != nil {
+			last = err
+		}
+		NextCost += stats.NextCost
+		ContainsCost += stats.ContainsCost
+		if it.isShortCircuiting {
+			if Size.Size < stats.Size.Size {
+				Size = stats.Size
+			}
+		} else {
+			Size.Size += stats.Size.Size
+			Size.Exact = Size.Exact && stats.Size.Exact
+		}
+	}
+	return graph.IteratorCosts{
+		ContainsCost: ContainsCost,
+		NextCost:     NextCost,
+		Size:         Size,
+	}, last
+}
+
+type orNext struct {
+	shortCircuit bool
+	sub          []graph.Scanner
+	curInd       int
+	result       graph.Ref
+	err          error
+}
+
+func newOrNext(sub []graph.Scanner, shortCircuit bool) *orNext {
+	return &orNext{
+		sub:          sub,
+		curInd:       -1,
+		shortCircuit: shortCircuit,
+	}
+}
+
+// Overrides BaseIterator TagResults, as it needs to add it's own results and
+// recurse down it's subiterators.
+func (it *orNext) TagResults(dst map[string]graph.Ref) {
+	it.sub[it.curInd].TagResults(dst)
+}
+
+func (it *orNext) String() string {
+	return "OrNext"
 }
 
 // Next advances the Or graph.iterator. Because the Or is the union of its
 // subiterators, it must produce from all subiterators -- unless it it
 // shortcircuiting, in which case, it is the first one that returns anything.
-func (it *Or) Next(ctx context.Context) bool {
-	if it.currentIterator >= len(it.internalIterators) {
+func (it *orNext) Next(ctx context.Context) bool {
+	if it.curInd >= len(it.sub) {
 		return false
 	}
 	var first bool
 	for {
-		if it.currentIterator == -1 {
-			it.currentIterator = 0
+		if it.curInd == -1 {
+			it.curInd = 0
 			first = true
 		}
-		curIt := it.internalIterators[it.currentIterator]
+		curIt := it.sub[it.curInd]
 
 		if curIt.Next(ctx) {
 			it.result = curIt.Result()
@@ -116,11 +235,11 @@ func (it *Or) Next(ctx context.Context) bool {
 			return false
 		}
 
-		if it.isShortCircuiting && !first {
+		if it.shortCircuit && !first {
 			break
 		}
-		it.currentIterator++
-		if it.currentIterator >= len(it.internalIterators) {
+		it.curInd++
+		if it.curInd >= len(it.sub) {
 			break
 		}
 	}
@@ -128,21 +247,88 @@ func (it *Or) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *Or) Err() error {
+func (it *orNext) Err() error {
+	return it.err
+}
+
+func (it *orNext) Result() graph.Ref {
+	return it.result
+}
+
+// An Or has no NextPath of its own -- that is, there are no other values
+// which satisfy our previous result that are not the result itself. Our
+// subiterators might, however, so just pass the call recursively. In the case of
+// shortcircuiting, only allow new results from the currently checked graph.iterator
+func (it *orNext) NextPath(ctx context.Context) bool {
+	if it.curInd != -1 {
+		currIt := it.sub[it.curInd]
+		ok := currIt.NextPath(ctx)
+		if !ok {
+			it.err = currIt.Err()
+		}
+		return ok
+	}
+	return false
+}
+
+// Close this graph.iterator, and, by extension, close the subiterators.
+// Close should be idempotent, and it follows that if it's subiterators
+// follow this contract, the Or follows the contract.  It closes all
+// subiterators it can, but returns the first error it encounters.
+func (it *orNext) Close() error {
+	var err error
+	for _, sub := range it.sub {
+		_err := sub.Close()
+		if _err != nil && err == nil {
+			err = _err
+		}
+	}
+	return err
+}
+
+var _ graph.Iterator = &Or{}
+
+type orContains struct {
+	shortCircuit bool
+	sub          []graph.Index
+	curInd       int
+	result       graph.Ref
+	err          error
+}
+
+func newOrContains(sub []graph.Index, shortCircuit bool) *orContains {
+	return &orContains{
+		sub:          sub,
+		curInd:       -1,
+		shortCircuit: shortCircuit,
+	}
+}
+
+// Overrides BaseIterator TagResults, as it needs to add it's own results and
+// recurse down it's subiterators.
+func (it *orContains) TagResults(dst map[string]graph.Ref) {
+	it.sub[it.curInd].TagResults(dst)
+}
+
+func (it *orContains) String() string {
+	return "OrContains"
+}
+
+func (it *orContains) Err() error {
 	return it.err
 }
 
-func (it *Or) Result() graph.Ref {
+func (it *orContains) Result() graph.Ref {
 	return it.result
 }
 
 // Checks a value against the iterators, in order.
-func (it *Or) subItsContain(ctx context.Context, val graph.Ref) (bool, error) {
-	var subIsGood = false
-	for i, sub := range it.internalIterators {
+func (it *orContains) subItsContain(ctx context.Context, val graph.Ref) (bool, error) {
+	subIsGood := false
+	for i, sub := range it.sub {
 		subIsGood = sub.Contains(ctx, val)
 		if subIsGood {
-			it.currentIterator = i
+			it.curInd = i
 			break
 		}
 
@@ -155,7 +341,7 @@ func (it *Or) subItsContain(ctx context.Context, val graph.Ref) (bool, error) {
 }
 
 // Check a value against the entire graph.iterator, in order.
-func (it *Or) Contains(ctx context.Context, val graph.Ref) bool {
+func (it *orContains) Contains(ctx context.Context, val graph.Ref) bool {
 	anyGood, err := it.subItsContain(ctx, val)
 	if err != nil {
 		it.err = err
@@ -167,113 +353,34 @@ func (it *Or) Contains(ctx context.Context, val graph.Ref) bool {
 	return true
 }
 
-// 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) Size() (int64, bool) {
-	var val int64
-	var b bool
-	if it.isShortCircuiting {
-		val = 0
-		b = true
-		for _, sub := range it.internalIterators {
-			newval, newb := sub.Size()
-			if val < newval {
-				val = newval
-			}
-			b = newb && b
-		}
-	} else {
-		val = 0
-		b = true
-		for _, sub := range it.internalIterators {
-			newval, newb := sub.Size()
-			val += newval
-			b = newb && b
-		}
-	}
-	return val, b
-}
-
 // An Or has no NextPath of its own -- that is, there are no other values
 // which satisfy our previous result that are not the result itself. Our
 // subiterators might, however, so just pass the call recursively. In the case of
 // shortcircuiting, only allow new results from the currently checked graph.iterator
-func (it *Or) NextPath(ctx context.Context) bool {
-	if it.currentIterator != -1 {
-		currIt := it.internalIterators[it.currentIterator]
+func (it *orContains) NextPath(ctx context.Context) bool {
+	if it.curInd != -1 {
+		currIt := it.sub[it.curInd]
 		ok := currIt.NextPath(ctx)
 		if !ok {
 			it.err = currIt.Err()
 		}
 		return ok
 	}
+	// TODO(dennwc): this should probably list matches from other sub-iterators
 	return false
 }
 
-// Perform or-specific cleanup, of which there currently is none.
-func (it *Or) cleanUp() {}
-
 // Close this graph.iterator, and, by extension, close the subiterators.
 // Close should be idempotent, and it follows that if it's subiterators
 // follow this contract, the Or follows the contract.  It closes all
 // subiterators it can, but returns the first error it encounters.
-func (it *Or) Close() error {
-	it.cleanUp()
-
+func (it *orContains) Close() error {
 	var err error
-	for _, sub := range it.internalIterators {
+	for _, sub := range it.sub {
 		_err := sub.Close()
 		if _err != nil && err == nil {
 			err = _err
 		}
 	}
-
 	return err
 }
-
-func (it *Or) Optimize() (graph.Iterator, bool) {
-	old := it.SubIterators()
-	optIts := optimizeSubIterators(old)
-	newOr := NewOr()
-	newOr.isShortCircuiting = it.isShortCircuiting
-
-	// Add the subiterators in order.
-	for _, o := range optIts {
-		newOr.AddSubIterator(o)
-	}
-
-	// And close ourselves but not our subiterators -- some may still be alive in
-	// the new And (they were unchanged upon calling Optimize() on them, at the
-	// start).
-	it.cleanUp()
-	return newOr, true
-}
-
-func (it *Or) Stats() graph.IteratorStats {
-	ContainsCost := int64(0)
-	NextCost := int64(0)
-	Size := int64(0)
-	Exact := true
-	for _, sub := range it.internalIterators {
-		stats := sub.Stats()
-		NextCost += stats.NextCost
-		ContainsCost += stats.ContainsCost
-		if it.isShortCircuiting {
-			if Size < stats.Size {
-				Size = stats.Size
-				Exact = stats.ExactSize
-			}
-		} else {
-			Size += stats.Size
-			Exact = Exact && stats.ExactSize
-		}
-	}
-	return graph.IteratorStats{
-		ContainsCost: ContainsCost,
-		NextCost:     NextCost,
-		Size:         Size,
-		ExactSize:    Exact,
-	}
-
-}
diff --git a/graph/iterator/query_shape.go b/graph/iterator/query_shape.go
index 8808d57..889ae81 100644
--- a/graph/iterator/query_shape.go
+++ b/graph/iterator/query_shape.go
@@ -142,9 +142,9 @@ func (s *queryShape) makeNode(n *Node, it graph.Iterator) *Node {
 		}
 	case *HasA:
 		hasa := it
-		s.PushHasa(n.ID, hasa.dir)
+		s.PushHasa(n.ID, hasa.it.dir)
 		s.nodeID++
-		newNode := s.MakeNode(hasa.primaryIt)
+		newNode := s.MakeNode(graph.AsLegacy(hasa.it.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(lto.primaryIt)
+		newNode := s.MakeNode(graph.AsLegacy(lto.it.primary))
 		hasaID, hasaDir := s.LastHasa()
-		if (hasaDir == quad.Subject && lto.dir == quad.Object) ||
-			(hasaDir == quad.Object && lto.dir == quad.Subject) {
+		if (hasaDir == quad.Subject && lto.it.dir == quad.Object) ||
+			(hasaDir == quad.Object && lto.it.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 := lto.primaryIt.(*Fixed); ok {
+		} else if _, ok := graph.AsLegacy(lto.it.primary).(*Fixed); ok {
 			s.StealNode(n, newNode)
 		} else {
 			s.AddNode(newNode)
diff --git a/graph/iterator/recursive.go b/graph/iterator/recursive.go
index 4e06c18..631bbb1 100644
--- a/graph/iterator/recursive.go
+++ b/graph/iterator/recursive.go
@@ -8,25 +8,14 @@ import (
 	"github.com/cayleygraph/cayley/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 {
-	uid      uint64
-	subIt    graph.Iterator
-	result   seenAt
-	runstats graph.IteratorStats
-	err      error
-
-	morphism      Morphism
-	seen          map[interface{}]seenAt
-	nextIt        graph.Iterator
-	depth         int
-	maxDepth      int
-	pathMap       map[interface{}][]map[string]graph.Ref
-	pathIndex     int
-	containsValue graph.Ref
-	depthTags     []string
-	depthCache    []graph.Ref
-	baseIt        graph.FixedIterator
+	it *recursive
+	graph.Iterator
 }
 
 type seenAt struct {
@@ -34,52 +23,136 @@ type seenAt struct {
 	val   graph.Ref
 }
 
-var _ graph.Iterator = &Recursive{}
-
 var DefaultMaxRecursiveSteps = 50
 
-func NewRecursive(it graph.Iterator, morphism Morphism, maxDepth int) *Recursive {
+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 {
+	subIt     graph.IteratorShape
+	morphism  Morphism2
+	maxDepth  int
+	depthTags []string
+}
+
+func newRecursive(it graph.IteratorShape, morphism Morphism2, maxDepth int) *recursive {
 	if maxDepth == 0 {
 		maxDepth = DefaultMaxRecursiveSteps
 	}
+	return &recursive{
+		subIt:    it,
+		morphism: morphism,
+		maxDepth: maxDepth,
+	}
+}
+
+func (it *recursive) Iterate() graph.Scanner {
+	return newRecursiveNext(it.subIt.Iterate(), it.morphism, it.maxDepth, it.depthTags)
+}
 
-	return &Recursive{
-		uid:   NextUID(),
-		subIt: it,
+func (it *recursive) Lookup() graph.Index {
+	return newRecursiveContains(newRecursiveNext(it.subIt.Iterate(), it.morphism, it.maxDepth, it.depthTags))
+}
 
-		morphism:      morphism,
-		seen:          make(map[interface{}]seenAt),
-		nextIt:        &Null{},
-		baseIt:        NewFixed(),
-		pathMap:       make(map[interface{}][]map[string]graph.Ref),
-		containsValue: nil,
-		maxDepth:      maxDepth,
+func (it *recursive) AsLegacy() graph.Iterator {
+	it2 := &Recursive{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
+}
+
+func (it *recursive) AddDepthTag(s string) {
+	it.depthTags = append(it.depthTags, s)
+}
+
+func (it *recursive) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.subIt}
+}
+
+func (it *recursive) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	newIt, optimized := it.subIt.Optimize(ctx)
+	if optimized {
+		it.subIt = newIt
 	}
+	return it, false
 }
 
-func (it *Recursive) UID() uint64 {
-	return it.uid
+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)
+	subitStats, err2 := it.subIt.Stats(ctx)
+	if err == nil {
+		err = err2
+	}
+	size := int64(math.Pow(float64(subitStats.Size.Size*fanoutStats.Size.Size), 5))
+	return graph.IteratorCosts{
+		NextCost:     subitStats.NextCost + fanoutStats.NextCost,
+		ContainsCost: (subitStats.NextCost+fanoutStats.NextCost)*(size/10) + subitStats.ContainsCost,
+		Size: graph.Size{
+			Size:  size,
+			Exact: false,
+		},
+	}, err
 }
 
-func (it *Recursive) Reset() {
-	it.result.val = nil
-	it.result.depth = 0
-	it.err = nil
-	it.subIt.Reset()
-	it.seen = make(map[interface{}]seenAt)
-	it.pathMap = make(map[interface{}][]map[string]graph.Ref)
-	it.containsValue = nil
-	it.pathIndex = 0
-	it.nextIt = &Null{}
-	it.baseIt = NewFixed()
-	it.depth = 0
+func (it *recursive) String() string {
+	return "Recursive"
 }
 
-func (it *Recursive) AddDepthTag(s string) {
-	it.depthTags = append(it.depthTags, s)
+// Recursive iterator takes a base iterator and a morphism to be applied recursively, for each result.
+type recursiveNext struct {
+	subIt  graph.Scanner
+	result seenAt
+	err    error
+
+	morphism      Morphism2
+	seen          map[interface{}]seenAt
+	nextIt        graph.Scanner
+	depth         int
+	maxDepth      int
+	pathMap       map[interface{}][]map[string]graph.Ref
+	pathIndex     int
+	containsValue graph.Ref
+	depthTags     []string
+	depthCache    []graph.Ref
+	baseIt        *fixed
+}
+
+func newRecursiveNext(it graph.Scanner, morphism Morphism2, maxDepth int, depthTags []string) *recursiveNext {
+	return &recursiveNext{
+		subIt:     it,
+		morphism:  morphism,
+		maxDepth:  maxDepth,
+		depthTags: depthTags,
+
+		seen:    make(map[interface{}]seenAt),
+		nextIt:  &Null{},
+		baseIt:  newFixed(),
+		pathMap: make(map[interface{}][]map[string]graph.Ref),
+	}
 }
 
-func (it *Recursive) TagResults(dst map[string]graph.Ref) {
+func (it *recursiveNext) TagResults(dst map[string]graph.Ref) {
 	for _, tag := range it.depthTags {
 		dst[tag] = graph.PreFetched(quad.Int(it.result.depth))
 	}
@@ -94,15 +167,11 @@ func (it *Recursive) TagResults(dst map[string]graph.Ref) {
 	}
 	if it.nextIt != nil {
 		it.nextIt.TagResults(dst)
-		delete(dst, "__base_recursive")
+		delete(dst, recursiveBaseTag)
 	}
 }
 
-func (it *Recursive) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.subIt}
-}
-
-func (it *Recursive) Next(ctx context.Context) bool {
+func (it *recursiveNext) Next(ctx context.Context) bool {
 	it.pathIndex = 0
 	if it.depth == 0 {
 		for it.subIt.Next(ctx) {
@@ -128,12 +197,12 @@ func (it *Recursive) 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(Tag(it.baseIt, "__base_recursive"))
+			it.nextIt = it.morphism(TagShape(it.baseIt, recursiveBaseTag)).Iterate()
 			continue
 		}
 		val := it.nextIt.Result()
@@ -142,7 +211,7 @@ func (it *Recursive) Next(ctx context.Context) bool {
 		key := graph.ToKey(val)
 		if _, seen := it.seen[key]; !seen {
 			it.seen[key] = seenAt{
-				val:   results["__base_recursive"],
+				val:   results[recursiveBaseTag],
 				depth: it.depth,
 			}
 			it.result.depth = it.depth
@@ -154,15 +223,15 @@ func (it *Recursive) Next(ctx context.Context) bool {
 	}
 }
 
-func (it *Recursive) Err() error {
+func (it *recursiveNext) Err() error {
 	return it.err
 }
 
-func (it *Recursive) Result() graph.Ref {
+func (it *recursiveNext) Result() graph.Ref {
 	return it.result.val
 }
 
-func (it *Recursive) getBaseValue(val graph.Ref) graph.Ref {
+func (it *recursiveNext) getBaseValue(val graph.Ref) graph.Ref {
 	var at seenAt
 	var ok bool
 	if at, ok = it.seen[graph.ToKey(val)]; !ok {
@@ -177,24 +246,7 @@ func (it *Recursive) getBaseValue(val graph.Ref) graph.Ref {
 	return at.val
 }
 
-func (it *Recursive) Contains(ctx context.Context, val graph.Ref) bool {
-	it.pathIndex = 0
-	key := graph.ToKey(val)
-	if at, ok := it.seen[key]; ok {
-		it.containsValue = it.getBaseValue(val)
-		it.result.depth = at.depth
-		it.result.val = val
-		return true
-	}
-	for it.Next(ctx) {
-		if graph.ToKey(it.Result()) == key {
-			return true
-		}
-	}
-	return false
-}
-
-func (it *Recursive) NextPath(ctx context.Context) bool {
+func (it *recursiveNext) NextPath(ctx context.Context) bool {
 	if it.pathIndex+1 >= len(it.pathMap[graph.ToKey(it.containsValue)]) {
 		return false
 	}
@@ -202,7 +254,7 @@ func (it *Recursive) NextPath(ctx context.Context) bool {
 	return true
 }
 
-func (it *Recursive) Close() error {
+func (it *recursiveNext) Close() error {
 	err := it.subIt.Close()
 	if err != nil {
 		return err
@@ -215,36 +267,58 @@ func (it *Recursive) Close() error {
 	return it.err
 }
 
-func (it *Recursive) Optimize() (graph.Iterator, bool) {
-	newIt, optimized := it.subIt.Optimize()
-	if optimized {
-		it.subIt = newIt
+func (it *recursiveNext) String() string {
+	return "RecursiveNext"
+}
+
+// Recursive iterator takes a base iterator and a morphism to be applied recursively, for each result.
+type recursiveContains struct {
+	next *recursiveNext
+}
+
+func newRecursiveContains(next *recursiveNext) *recursiveContains {
+	return &recursiveContains{
+		next: next,
 	}
-	return it, false
 }
 
-func (it *Recursive) Size() (int64, bool) {
-	return it.Stats().Size, false
+func (it *recursiveContains) TagResults(dst map[string]graph.Ref) {
+	it.next.TagResults(dst)
 }
 
-func (it *Recursive) Stats() graph.IteratorStats {
-	base := NewFixed()
-	base.Add(Int64Node(20))
-	fanoutit := it.morphism(base)
-	fanoutStats := fanoutit.Stats()
-	subitStats := it.subIt.Stats()
+func (it *recursiveContains) Err() error {
+	return it.next.Err()
+}
 
-	size := int64(math.Pow(float64(subitStats.Size*fanoutStats.Size), 5))
-	return graph.IteratorStats{
-		NextCost:     subitStats.NextCost + fanoutStats.NextCost,
-		ContainsCost: (subitStats.NextCost+fanoutStats.NextCost)*(size/10) + subitStats.ContainsCost,
-		Size:         size,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-		ContainsNext: it.runstats.ContainsNext,
+func (it *recursiveContains) Result() graph.Ref {
+	return it.next.Result()
+}
+
+func (it *recursiveContains) Contains(ctx context.Context, val graph.Ref) bool {
+	it.next.pathIndex = 0
+	key := graph.ToKey(val)
+	if at, ok := it.next.seen[key]; ok {
+		it.next.containsValue = it.next.getBaseValue(val)
+		it.next.result.depth = at.depth
+		it.next.result.val = val
+		return true
+	}
+	for it.next.Next(ctx) {
+		if graph.ToKey(it.next.Result()) == key {
+			return true
+		}
 	}
+	return false
 }
 
-func (it *Recursive) String() string {
-	return "Recursive"
+func (it *recursiveContains) NextPath(ctx context.Context) bool {
+	return it.next.NextPath(ctx)
+}
+
+func (it *recursiveContains) Close() error {
+	return it.next.Close()
+}
+
+func (it *recursiveContains) String() string {
+	return "RecursiveContains(" + it.next.String() + ")"
 }
diff --git a/graph/iterator/resolver.go b/graph/iterator/resolver.go
index 8f32aae..8dbb77f 100644
--- a/graph/iterator/resolver.go
+++ b/graph/iterator/resolver.go
@@ -22,151 +22,239 @@ import (
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = &Resolver{}
+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 {
-	qs     graph.QuadStore
-	uid    uint64
-	tags   graph.Tagger
-	order  []quad.Value
-	values map[quad.Value]graph.Ref
-	nodes  map[interface{}]quad.Value
-	cached bool
-	index  int
-	err    error
-	result graph.Ref
+	it *resolver
+	graph.Iterator
 }
 
 // Creates a new Resolver iterator.
 func NewResolver(qs graph.QuadStore, nodes ...quad.Value) *Resolver {
 	it := &Resolver{
-		uid:   NextUID(),
+		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{
 		qs:    qs,
 		order: make([]quad.Value, len(nodes)),
-		// Generally there are going to be no/few duplicates given
-		// so allocate maps large enough to accommodate all
-		values: make(map[quad.Value]graph.Ref, len(nodes)),
-		nodes:  make(map[interface{}]quad.Value, len(nodes)),
 	}
 	copy(it.order, nodes)
 	return it
 }
 
-func (it *Resolver) UID() uint64 {
-	return it.uid
+func (it *resolver) Iterate() graph.Scanner {
+	return newResolverNext(it.qs, it.order)
+}
+
+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) Reset() {
-	it.index = 0
-	it.err = nil
-	it.result = nil
+func (it *resolver) String() string {
+	return fmt.Sprintf("Resolver(%v)", it.order)
 }
 
-func (it *Resolver) Close() error {
+func (it *resolver) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *Resolver) Tagger() *graph.Tagger {
-	return &it.tags
+// 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) {
+	if len(it.order) == 0 {
+		return newNull(), true
+	}
+	return it, false
 }
 
-func (it *Resolver) TagResults(dst map[string]graph.Ref) {}
+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)),
+			Exact: true,
+		},
+	}, nil
+}
 
-func (it *Resolver) String() string {
-	return fmt.Sprintf("Resolver(%v)", it.order)
+// 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 resolverNext struct {
+	qs     graph.QuadStore
+	order  []quad.Value
+	values []graph.Ref
+	cached bool
+	index  int
+	err    error
+	result graph.Ref
+}
+
+// Creates a new Resolver iterator.
+func newResolverNext(qs graph.QuadStore, nodes []quad.Value) *resolverNext {
+	it := &resolverNext{
+		qs:    qs,
+		order: make([]quad.Value, len(nodes)),
+	}
+	copy(it.order, nodes)
+	return it
+}
+
+func (it *resolverNext) Close() error {
+	return nil
+}
+
+func (it *resolverNext) TagResults(dst map[string]graph.Ref) {}
+
+func (it *resolverNext) String() string {
+	return fmt.Sprintf("ResolverNext(%v, %v)", it.order, it.values)
 }
 
 // Resolve nodes to values
-func (it *Resolver) resolve(ctx context.Context) error {
+func (it *resolverNext) resolve(ctx context.Context) error {
 	values, err := graph.RefsOf(ctx, it.qs, it.order)
 	if err != nil {
 		return err
 	}
-	for index, value := range values {
-		node := it.order[index]
-		it.values[node] = value
-		it.nodes[value.Key()] = node
+	it.values = make([]graph.Ref, len(it.order))
+	for i, value := range values {
+		it.values[i] = value
 	}
+	it.order = nil
 	it.cached = true
 	return nil
 }
 
-// Check if the passed value is equal to one of the order stored in the iterator.
-func (it *Resolver) Contains(ctx context.Context, value graph.Ref) bool {
-	if !it.cached {
-		it.err = it.resolve(ctx)
-		if it.err != nil {
-			return false
-		}
-	}
-	_, ok := it.nodes[value.Key()]
-	return ok
-}
-
 // Next advances the iterator.
-func (it *Resolver) Next(ctx context.Context) bool {
-	if it.index >= len(it.order) {
-		it.result = nil
-		return false
-	}
+func (it *resolverNext) Next(ctx context.Context) bool {
 	if !it.cached {
 		it.err = it.resolve(ctx)
 		if it.err != nil {
 			return false
 		}
 	}
-	node := it.order[it.index]
-	value, ok := it.values[node]
-	if !ok {
+	if it.index >= len(it.values) {
 		it.result = nil
-		it.err = fmt.Errorf("not found: %v", node)
 		return false
 	}
-	it.result = value
+	it.result = it.values[it.index]
 	it.index++
 	return true
 }
 
-func (it *Resolver) Err() error {
+func (it *resolverNext) Err() error {
 	return it.err
 }
 
-func (it *Resolver) Result() graph.Ref {
+func (it *resolverNext) Result() graph.Ref {
 	return it.result
 }
 
-func (it *Resolver) NextPath(ctx context.Context) bool {
+func (it *resolverNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Resolver) SubIterators() []graph.Iterator {
-	return 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 resolverContains struct {
+	qs     graph.QuadStore
+	order  []quad.Value
+	nodes  map[interface{}]quad.Value
+	cached bool
+	err    error
+	result graph.Ref
 }
 
-// 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() (graph.Iterator, bool) {
-	if len(it.order) == 0 {
-		return NewNull(), true
+// Creates a new Resolver iterator.
+func newResolverContains(qs graph.QuadStore, nodes []quad.Value) *resolverContains {
+	it := &resolverContains{
+		qs:    qs,
+		order: make([]quad.Value, len(nodes)),
 	}
-	return it, false
+	copy(it.order, nodes)
+	return it
 }
 
-// Size is the number of m stored.
-func (it *Resolver) Size() (int64, bool) {
-	return int64(len(it.order)), true
+func (it *resolverContains) Close() error {
+	return nil
 }
 
-func (it *Resolver) Stats() graph.IteratorStats {
-	s, exact := it.Size()
-	return graph.IteratorStats{
-		// Lookup cost is size of set
-		ContainsCost: s,
-		// Next is (presumably) O(1) from store
-		NextCost:  1,
-		Size:      s,
-		ExactSize: exact,
+func (it *resolverContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *resolverContains) String() string {
+	return fmt.Sprintf("ResolverContains(%v, %v)", it.order, it.nodes)
+}
+
+// Resolve nodes to values
+func (it *resolverContains) resolve(ctx context.Context) error {
+	values, err := graph.RefsOf(ctx, it.qs, it.order)
+	if err != nil {
+		return err
+	}
+	// Generally there are going to be no/few duplicates given
+	// so allocate maps large enough to accommodate all
+	it.nodes = make(map[interface{}]quad.Value, len(it.order))
+	for index, value := range values {
+		node := it.order[index]
+		it.nodes[value.Key()] = node
 	}
+	it.order = nil
+	it.cached = true
+	return nil
+}
+
+// Check if the passed value is equal to one of the order stored in the iterator.
+func (it *resolverContains) Contains(ctx context.Context, value graph.Ref) bool {
+	if !it.cached {
+		it.err = it.resolve(ctx)
+		if it.err != nil {
+			return false
+		}
+	}
+	_, ok := it.nodes[value.Key()]
+	if ok {
+		it.result = value
+	}
+	return ok
+}
+
+func (it *resolverContains) Err() error {
+	return it.err
+}
+
+func (it *resolverContains) Result() graph.Ref {
+	return it.result
+}
+
+func (it *resolverContains) NextPath(ctx context.Context) bool {
+	return false
 }
diff --git a/graph/iterator/save.go b/graph/iterator/save.go
index 37863e7..1d240fe 100644
--- a/graph/iterator/save.go
+++ b/graph/iterator/save.go
@@ -8,41 +8,114 @@ import (
 )
 
 var (
-	_ graph.Iterator = (*Save)(nil)
-	_ graph.Tagger   = (*Save)(nil)
+	_ graph.IteratorFuture = (*Save)(nil)
+	_ graph.Tagger         = (*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 {
+	if s, ok := it.(graph.TaggerShape); ok {
+		s.AddTags(tag)
+		return s
+	} else if s, ok := graph.AsLegacy(it).(graph.Tagger); ok {
+		s.AddTags(tag)
+		return graph.AsShape(s)
+	}
+	return newSave(it, tag)
+}
+
 func NewSave(on graph.Iterator, tags ...string) *Save {
-	s := &Save{uid: NextUID(), it: on}
+	it := &Save{
+		it: newSave(graph.AsShape(on), tags...),
+	}
+	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)
+}
+
+var (
+	_ graph.IteratorShapeCompat = (*save)(nil)
+	_ graph.TaggerShape         = (*save)(nil)
+)
+
+func newSave(on graph.IteratorShape, tags ...string) *save {
+	s := &save{it: on}
 	s.AddTags(tags...)
 	return s
 }
 
-type Save struct {
-	uid       uint64
+type save struct {
+	it        graph.IteratorShape
 	tags      []string
 	fixedTags map[string]graph.Ref
-	it        graph.Iterator
 }
 
-func (it *Save) String() string {
+func (it *save) Iterate() graph.Scanner {
+	return newSaveNext(it.it.Iterate(), it.tags, it.fixedTags)
+}
+
+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 {
 	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)
 	}
@@ -50,16 +123,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.Tagger) {
+func (it *save) CopyFromTagger(st graph.TaggerBase) {
 	it.tags = append(it.tags, st.Tags()...)
 
 	fixed := st.FixedTags()
@@ -74,7 +147,49 @@ func (it *Save) CopyFromTagger(st graph.Tagger) {
 	}
 }
 
-func (it *Save) TagResults(dst map[string]graph.Ref) {
+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) {
+	sub, ok := it.it.Optimize(ctx)
+	if len(it.tags) == 0 && len(it.fixedTags) == 0 {
+		return sub, true
+	}
+	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.CopyFromTagger(it)
+	return s, true
+}
+
+func (it *save) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.it}
+}
+
+func newSaveNext(it graph.Scanner, tags []string, fixed map[string]graph.Ref) *saveNext {
+	return &saveNext{it: it, tags: tags, fixedTags: fixed}
+}
+
+type saveNext struct {
+	it        graph.Scanner
+	tags      []string
+	fixedTags map[string]graph.Ref
+}
+
+func (it *saveNext) String() string {
+	return fmt.Sprintf("Save(%v, %v)", it.tags, it.fixedTags)
+}
+
+func (it *saveNext) TagResults(dst map[string]graph.Ref) {
 	it.it.TagResults(dst)
 
 	v := it.Result()
@@ -87,63 +202,69 @@ func (it *Save) TagResults(dst map[string]graph.Ref) {
 	}
 }
 
-func (it *Save) Result() graph.Ref {
+func (it *saveNext) Result() graph.Ref {
 	return it.it.Result()
 }
 
-func (it *Save) Next(ctx context.Context) bool {
+func (it *saveNext) Next(ctx context.Context) bool {
 	return it.it.Next(ctx)
 }
 
-func (it *Save) NextPath(ctx context.Context) bool {
+func (it *saveNext) NextPath(ctx context.Context) bool {
 	return it.it.NextPath(ctx)
 }
 
-func (it *Save) Contains(ctx context.Context, v graph.Ref) bool {
-	return it.it.Contains(ctx, v)
+func (it *saveNext) Err() error {
+	return it.it.Err()
 }
 
-func (it *Save) Err() error {
-	return it.it.Err()
+func (it *saveNext) Close() error {
+	return it.it.Close()
 }
 
-func (it *Save) Reset() {
-	it.it.Reset()
+func newSaveContains(it graph.Index, tags []string, fixed map[string]graph.Ref) *saveContains {
+	return &saveContains{it: it, tags: tags, fixed: fixed}
 }
 
-func (it *Save) Stats() graph.IteratorStats {
-	return it.it.Stats()
+type saveContains struct {
+	it    graph.Index
+	tags  []string
+	fixed map[string]graph.Ref
 }
 
-func (it *Save) Size() (int64, bool) {
-	return it.it.Size()
+func (it *saveContains) String() string {
+	return fmt.Sprintf("SaveContains(%v, %v)", it.tags, it.fixed)
 }
 
-func (it *Save) Optimize() (nit graph.Iterator, no bool) {
-	sub, ok := it.it.Optimize()
-	if len(it.tags) == 0 && len(it.fixedTags) == 0 {
-		return sub, true
-	}
-	if st, ok2 := sub.(graph.Tagger); ok2 {
-		st.CopyFromTagger(it)
-		return st, true
+func (it *saveContains) TagResults(dst map[string]graph.Ref) {
+	it.it.TagResults(dst)
+
+	v := it.Result()
+	for _, tag := range it.tags {
+		dst[tag] = v
 	}
-	if !ok {
-		return it, false
+
+	for tag, value := range it.fixed {
+		dst[tag] = value
 	}
-	s := NewSave(sub)
-	s.CopyFromTagger(it)
-	return s, true
 }
 
-func (it *Save) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.it}
+func (it *saveContains) Result() graph.Ref {
+	return it.it.Result()
 }
 
-func (it *Save) Close() error {
-	return it.it.Close()
+func (it *saveContains) NextPath(ctx context.Context) bool {
+	return it.it.NextPath(ctx)
+}
+
+func (it *saveContains) Contains(ctx context.Context, v graph.Ref) bool {
+	return it.it.Contains(ctx, v)
+}
+
+func (it *saveContains) Err() error {
+	return it.it.Err()
 }
 
-func (it *Save) UID() uint64 {
-	return it.uid
+func (it *saveContains) Close() error {
+	return it.it.Close()
 }
diff --git a/graph/iterator/skip.go b/graph/iterator/skip.go
index b687605..e0eca02 100644
--- a/graph/iterator/skip.go
+++ b/graph/iterator/skip.go
@@ -7,46 +7,106 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Skip{}
+var _ graph.IteratorFuture = &Skip{}
 
 // Skip iterator will skip certain number of values from primary iterator.
 type Skip struct {
-	uid       uint64
-	skip      int64
-	skipped   int64
-	primaryIt graph.Iterator
+	it *skip
+	graph.Iterator
 }
 
 func NewSkip(primaryIt graph.Iterator, skip int64) *Skip {
-	return &Skip{
-		uid:       NextUID(),
-		skip:      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{
+		skip:      off,
 		primaryIt: primaryIt,
 	}
 }
 
-func (it *Skip) UID() uint64 {
-	return it.uid
+func (it *skip) Iterate() graph.Scanner {
+	return newSkipNext(it.primaryIt.Iterate(), it.skip)
 }
 
-// Reset resets the internal iterators and the iterator itself.
-func (it *Skip) Reset() {
-	it.skipped = 0
-	it.primaryIt.Reset()
+func (it *skip) Lookup() graph.Index {
+	return newSkipContains(it.primaryIt.Lookup(), it.skip)
 }
 
-func (it *Skip) TagResults(dst map[string]graph.Ref) {
-	it.primaryIt.TagResults(dst)
+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.Iterator {
-	return []graph.Iterator{it.primaryIt}
+func (it *skip) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.primaryIt}
+}
+
+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
+	}
+	it.primaryIt = optimizedPrimaryIt
+	return it, optimized
+}
+
+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
+		}
+	}
+	return primaryStats, err
+}
+
+func (it *skip) String() string {
+	return fmt.Sprintf("Skip(%d)", it.skip)
+}
+
+// Skip iterator will skip certain number of values from primary iterator.
+type skipNext struct {
+	skip      int64
+	skipped   int64
+	primaryIt graph.Scanner
+}
+
+func newSkipNext(primaryIt graph.Scanner, skip int64) *skipNext {
+	return &skipNext{
+		skip:      skip,
+		primaryIt: primaryIt,
+	}
+}
+
+func (it *skipNext) TagResults(dst map[string]graph.Ref) {
+	it.primaryIt.TagResults(dst)
 }
 
 // Next advances the Skip iterator. It will skip all initial values
 // before returning actual result.
-func (it *Skip) Next(ctx context.Context) bool {
+func (it *skipNext) Next(ctx context.Context) bool {
 	for ; it.skipped < it.skip; it.skipped++ {
 		if !it.primaryIt.Next(ctx) {
 			return false
@@ -58,21 +118,17 @@ func (it *Skip) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *Skip) Err() error {
+func (it *skipNext) Err() error {
 	return it.primaryIt.Err()
 }
 
-func (it *Skip) Result() graph.Ref {
+func (it *skipNext) Result() graph.Ref {
 	return it.primaryIt.Result()
 }
 
-func (it *Skip) Contains(ctx context.Context, val graph.Ref) bool {
-	return it.primaryIt.Contains(ctx, val) // FIXME(dennwc): will not skip anything in this case
-}
-
 // NextPath checks whether there is another path. It will skip first paths
 // according to iterator parameter.
-func (it *Skip) NextPath(ctx context.Context) bool {
+func (it *skipNext) NextPath(ctx context.Context) bool {
 	for ; it.skipped < it.skip; it.skipped++ {
 		if !it.primaryIt.NextPath(ctx) {
 			return false
@@ -83,39 +139,94 @@ func (it *Skip) 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 *Skip) Close() error {
+func (it *skipNext) Close() error {
 	return it.primaryIt.Close()
 }
 
-func (it *Skip) Optimize() (graph.Iterator, bool) {
-	optimizedPrimaryIt, optimized := it.primaryIt.Optimize()
-	if it.skip == 0 { // nothing to skip
-		return optimizedPrimaryIt, true
+func (it *skipNext) String() string {
+	return fmt.Sprintf("SkipNext(%d)", it.skip)
+}
+
+// Skip iterator will skip certain number of values from primary iterator.
+type skipContains struct {
+	skip      int64
+	skipped   int64
+	primaryIt graph.Index
+}
+
+func newSkipContains(primaryIt graph.Index, skip int64) *skipContains {
+	return &skipContains{
+		skip:      skip,
+		primaryIt: primaryIt,
 	}
-	it.primaryIt = optimizedPrimaryIt
-	return it, optimized
 }
 
-func (it *Skip) Stats() graph.IteratorStats {
-	primaryStats := it.primaryIt.Stats()
-	primaryStats.Size -= it.skip
-	if primaryStats.Size < 0 {
-		primaryStats.Size = 0
+func (it *skipContains) TagResults(dst map[string]graph.Ref) {
+	it.primaryIt.TagResults(dst)
+}
+
+func (it *skipContains) Err() error {
+	return it.primaryIt.Err()
+}
+
+func (it *skipContains) Result() graph.Ref {
+	return it.primaryIt.Result()
+}
+
+func (it *skipContains) Contains(ctx context.Context, val graph.Ref) bool {
+	inNextPath := false
+	for it.skipped <= it.skip {
+		// skipping main iterator results
+		inNextPath = false
+		if !it.primaryIt.Contains(ctx, val) {
+			return false
+		}
+		it.skipped++
+
+		// TODO(dennwc): we don't really know if we should call NextPath or not,
+		//               and there is no good way to know
+		if it.skipped <= it.skip {
+			// skipping NextPath results
+			inNextPath = true
+			if !it.primaryIt.NextPath(ctx) {
+				// main path exists, but we skipped it
+				// and we skipped all alternative paths now
+				// so we definitely "don't have" this value
+				return false
+			}
+			it.skipped++
+
+			for it.skipped <= it.skip {
+				if !it.primaryIt.NextPath(ctx) {
+					return false
+				}
+				it.skipped++
+			}
+		}
+	}
+	if inNextPath && it.primaryIt.NextPath(ctx) {
+		return true
 	}
-	return primaryStats
+	return it.primaryIt.Contains(ctx, val)
 }
 
-func (it *Skip) Size() (int64, bool) {
-	primarySize, exact := it.primaryIt.Size()
-	if exact {
-		primarySize -= it.skip
-		if primarySize < 0 {
-			primarySize = 0
+// NextPath checks whether there is another path. It will skip first paths
+// according to iterator parameter.
+func (it *skipContains) NextPath(ctx context.Context) bool {
+	for ; it.skipped < it.skip; it.skipped++ {
+		if !it.primaryIt.NextPath(ctx) {
+			return false
 		}
 	}
-	return primarySize, exact
+	return it.primaryIt.NextPath(ctx)
 }
 
-func (it *Skip) String() string {
-	return fmt.Sprintf("Skip(%d)", it.skip)
+// Close closes the primary and all iterators.  It closes all subiterators
+// it can, but returns the first error it encounters.
+func (it *skipContains) Close() error {
+	return it.primaryIt.Close()
+}
+
+func (it *skipContains) String() string {
+	return fmt.Sprintf("SkipContains(%d)", it.skip)
 }
diff --git a/graph/iterator/unique.go b/graph/iterator/unique.go
index 10874f3..f640328 100644
--- a/graph/iterator/unique.go
+++ b/graph/iterator/unique.go
@@ -6,54 +6,110 @@ import (
 	"github.com/cayleygraph/cayley/graph"
 )
 
-var _ graph.Iterator = &Unique{}
+var _ graph.IteratorFuture = &Unique{}
 
 // Unique iterator removes duplicate values from it's subiterator.
 type Unique struct {
-	uid      uint64
-	subIt    graph.Iterator
-	result   graph.Ref
-	runstats graph.IteratorStats
-	err      error
-	seen     map[interface{}]bool
+	it *unique
+	graph.Iterator
 }
 
 func NewUnique(subIt graph.Iterator) *Unique {
-	return &Unique{
-		uid:   NextUID(),
-		subIt: subIt,
-		seen:  make(map[interface{}]bool),
+	it := &Unique{
+		it: newUnique(graph.AsShape(subIt)),
 	}
+	it.Iterator = graph.NewLegacy(it.it, it)
+	return it
 }
 
-func (it *Unique) UID() uint64 {
-	return it.uid
+func (it *Unique) AsShape() graph.IteratorShape {
+	it.Close()
+	return it.it
 }
 
-// Reset resets the internal iterators and the iterator itself.
-func (it *Unique) Reset() {
-	it.result = nil
-	it.subIt.Reset()
-	it.seen = make(map[interface{}]bool)
+var _ graph.IteratorShapeCompat = (*unique)(nil)
+
+// Unique iterator removes duplicate values from it's subiterator.
+type unique struct {
+	subIt graph.IteratorShape
 }
 
-func (it *Unique) TagResults(dst map[string]graph.Ref) {
-	if it.subIt != nil {
-		it.subIt.TagResults(dst)
+func newUnique(subIt graph.IteratorShape) *unique {
+	return &unique{
+		subIt: subIt,
 	}
 }
 
+func (it *unique) Iterate() graph.Scanner {
+	return newUniqueNext(it.subIt.Iterate())
+}
+
+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.Iterator {
-	return []graph.Iterator{it.subIt}
+func (it *unique) SubIterators() []graph.IteratorShape {
+	return []graph.IteratorShape{it.subIt}
+}
+
+func (it *unique) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	newIt, optimized := it.subIt.Optimize(ctx)
+	if optimized {
+		it.subIt = newIt
+	}
+	return it, false
+}
+
+const uniquenessFactor = 2
+
+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,
+			Exact: false,
+		},
+	}, err
+}
+
+func (it *unique) String() string {
+	return "Unique"
+}
+
+// Unique iterator removes duplicate values from it's subiterator.
+type uniqueNext struct {
+	subIt  graph.Scanner
+	result graph.Ref
+	err    error
+	seen   map[interface{}]bool
+}
+
+func newUniqueNext(subIt graph.Scanner) *uniqueNext {
+	return &uniqueNext{
+		subIt: subIt,
+		seen:  make(map[interface{}]bool),
+	}
+}
+
+func (it *uniqueNext) TagResults(dst map[string]graph.Ref) {
+	if it.subIt != nil {
+		it.subIt.TagResults(dst)
+	}
 }
 
 // Next advances the subiterator, continuing until it returns a value which it
 // has not previously seen.
-func (it *Unique) Next(ctx context.Context) bool {
-	it.runstats.Next += 1
-
+func (it *uniqueNext) Next(ctx context.Context) bool {
 	for it.subIt.Next(ctx) {
 		curr := it.subIt.Result()
 		key := graph.ToKey(curr)
@@ -67,62 +123,74 @@ func (it *Unique) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *Unique) Err() error {
+func (it *uniqueNext) Err() error {
 	return it.err
 }
 
-func (it *Unique) Result() graph.Ref {
+func (it *uniqueNext) Result() graph.Ref {
 	return it.result
 }
 
-// Contains checks whether the passed value is part of the primary iterator,
-// which is irrelevant for uniqueness.
-func (it *Unique) Contains(ctx context.Context, val graph.Ref) bool {
-	it.runstats.Contains += 1
-	return it.subIt.Contains(ctx, val)
-}
-
 // NextPath for unique always returns false. If we were to return multiple
 // paths, we'd no longer be a unique result, so we have to choose only the first
 // path that got us here. Unique is serious on this point.
-func (it *Unique) NextPath(ctx context.Context) bool {
+func (it *uniqueNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
 // Close closes the primary iterators.
-func (it *Unique) Close() error {
+func (it *uniqueNext) Close() error {
 	it.seen = nil
 	return it.subIt.Close()
 }
 
-func (it *Unique) Optimize() (graph.Iterator, bool) {
-	newIt, optimized := it.subIt.Optimize()
-	if optimized {
-		it.subIt = newIt
-	}
-	return it, false
+func (it *uniqueNext) String() string {
+	return "UniqueNext"
 }
 
-const uniquenessFactor = 2
+// Unique iterator removes duplicate values from it's subiterator.
+type uniqueContains struct {
+	subIt graph.Index
+}
 
-func (it *Unique) Stats() graph.IteratorStats {
-	subStats := it.subIt.Stats()
-	return graph.IteratorStats{
-		NextCost:     subStats.NextCost * uniquenessFactor,
-		ContainsCost: subStats.ContainsCost,
-		Size:         subStats.Size / uniquenessFactor,
-		ExactSize:    false,
-		Next:         it.runstats.Next,
-		Contains:     it.runstats.Contains,
-		ContainsNext: it.runstats.ContainsNext,
+func newUniqueContains(subIt graph.Index) *uniqueContains {
+	return &uniqueContains{
+		subIt: subIt,
+	}
+}
+
+func (it *uniqueContains) TagResults(dst map[string]graph.Ref) {
+	if it.subIt != nil {
+		it.subIt.TagResults(dst)
 	}
 }
 
-func (it *Unique) Size() (int64, bool) {
-	st := it.Stats()
-	return st.Size, st.ExactSize
+func (it *uniqueContains) Err() error {
+	return it.subIt.Err()
 }
 
-func (it *Unique) String() string {
-	return "Unique"
+func (it *uniqueContains) Result() graph.Ref {
+	return it.subIt.Result()
+}
+
+// Contains checks whether the passed value is part of the primary iterator,
+// which is irrelevant for uniqueness.
+func (it *uniqueContains) Contains(ctx context.Context, val graph.Ref) bool {
+	return it.subIt.Contains(ctx, val)
+}
+
+// NextPath for unique always returns false. If we were to return multiple
+// paths, we'd no longer be a unique result, so we have to choose only the first
+// path that got us here. Unique is serious on this point.
+func (it *uniqueContains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+// Close closes the primary iterators.
+func (it *uniqueContains) Close() error {
+	return it.subIt.Close()
+}
+
+func (it *uniqueContains) String() string {
+	return "UniqueContains"
 }
diff --git a/graph/iterator/value_filter.go b/graph/iterator/value_filter.go
index f449d49..628530c 100644
--- a/graph/iterator/value_filter.go
+++ b/graph/iterator/value_filter.go
@@ -21,33 +21,103 @@ import (
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = &ValueFilter{}
+var _ graph.IteratorFuture = &ValueFilter{}
 
 type ValueFilter struct {
-	uid    uint64
-	sub    graph.Iterator
-	filter ValueFilterFunc
-	qs     graph.Namer
-	result graph.Ref
-	err    error
+	it *valueFilter
+	graph.Iterator
 }
 
 type ValueFilterFunc func(quad.Value) (bool, error)
 
 func NewValueFilter(qs graph.Namer, sub graph.Iterator, filter ValueFilterFunc) *ValueFilter {
-	return &ValueFilter{
-		uid:    NextUID(),
+	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 {
+	sub    graph.IteratorShape
+	filter ValueFilterFunc
+	qs     graph.Namer
+}
+
+func newValueFilter(qs graph.Namer, sub graph.IteratorShape, filter ValueFilterFunc) *valueFilter {
+	return &valueFilter{
 		sub:    sub,
 		qs:     qs,
 		filter: filter,
 	}
 }
 
-func (it *ValueFilter) UID() uint64 {
-	return it.uid
+func (it *valueFilter) Iterate() graph.Scanner {
+	return newValueFilterNext(it.qs, it.sub.Iterate(), it.filter)
+}
+
+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 {
+	return []graph.IteratorShape{it.sub}
 }
 
-func (it *ValueFilter) doFilter(val graph.Ref) bool {
+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) {
+	newSub, changed := it.sub.Optimize(ctx)
+	if changed {
+		it.sub = newSub
+	}
+	return it, true
+}
+
+// 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) {
+	st, err := it.sub.Stats(ctx)
+	st.Size.Size = st.Size.Size/2 + 1
+	st.Size.Exact = false
+	return st, err
+}
+
+type valueFilterNext struct {
+	sub    graph.Scanner
+	filter ValueFilterFunc
+	qs     graph.Namer
+	result graph.Ref
+	err    error
+}
+
+func newValueFilterNext(qs graph.Namer, sub graph.Scanner, filter ValueFilterFunc) *valueFilterNext {
+	return &valueFilterNext{
+		sub:    sub,
+		qs:     qs,
+		filter: filter,
+	}
+}
+
+func (it *valueFilterNext) doFilter(val graph.Ref) bool {
 	qval := it.qs.NameOf(val)
 	ok, err := it.filter(qval)
 	if err != nil {
@@ -56,17 +126,11 @@ func (it *ValueFilter) doFilter(val graph.Ref) bool {
 	return ok
 }
 
-func (it *ValueFilter) Close() error {
+func (it *valueFilterNext) Close() error {
 	return it.sub.Close()
 }
 
-func (it *ValueFilter) Reset() {
-	it.sub.Reset()
-	it.err = nil
-	it.result = nil
-}
-
-func (it *ValueFilter) Next(ctx context.Context) bool {
+func (it *valueFilterNext) Next(ctx context.Context) bool {
 	for it.sub.Next(ctx) {
 		val := it.sub.Result()
 		if it.doFilter(val) {
@@ -78,34 +142,70 @@ func (it *ValueFilter) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *ValueFilter) Err() error {
+func (it *valueFilterNext) Err() error {
 	return it.err
 }
 
-func (it *ValueFilter) Result() graph.Ref {
+func (it *valueFilterNext) Result() graph.Ref {
 	return it.result
 }
 
-func (it *ValueFilter) NextPath(ctx context.Context) bool {
-	for {
-		hasNext := it.sub.NextPath(ctx)
-		if !hasNext {
-			it.err = it.sub.Err()
-			return false
-		}
-		if it.doFilter(it.sub.Result()) {
-			break
-		}
+func (it *valueFilterNext) NextPath(ctx context.Context) bool {
+	return it.sub.NextPath(ctx)
+}
+
+// If we failed the check, then the subiterator should not contribute to the result
+// set. Otherwise, go ahead and tag it.
+func (it *valueFilterNext) TagResults(dst map[string]graph.Ref) {
+	it.sub.TagResults(dst)
+}
+
+func (it *valueFilterNext) String() string {
+	return "ValueFilterNext"
+}
+
+type valueFilterContains struct {
+	sub    graph.Index
+	filter ValueFilterFunc
+	qs     graph.Namer
+	result graph.Ref
+	err    error
+}
+
+func newValueFilterContains(qs graph.Namer, sub graph.Index, filter ValueFilterFunc) *valueFilterContains {
+	return &valueFilterContains{
+		sub:    sub,
+		qs:     qs,
+		filter: filter,
+	}
+}
+
+func (it *valueFilterContains) doFilter(val graph.Ref) bool {
+	qval := it.qs.NameOf(val)
+	ok, err := it.filter(qval)
+	if err != nil {
+		it.err = err
 	}
-	it.result = it.sub.Result()
-	return true
+	return ok
 }
 
-func (it *ValueFilter) SubIterators() []graph.Iterator {
-	return []graph.Iterator{it.sub}
+func (it *valueFilterContains) Close() error {
+	return it.sub.Close()
 }
 
-func (it *ValueFilter) Contains(ctx context.Context, val graph.Ref) bool {
+func (it *valueFilterContains) Err() error {
+	return it.err
+}
+
+func (it *valueFilterContains) Result() graph.Ref {
+	return it.result
+}
+
+func (it *valueFilterContains) NextPath(ctx context.Context) bool {
+	return it.sub.NextPath(ctx)
+}
+
+func (it *valueFilterContains) Contains(ctx context.Context, val graph.Ref) bool {
 	if !it.doFilter(val) {
 		return false
 	}
@@ -118,33 +218,10 @@ func (it *ValueFilter) Contains(ctx context.Context, val graph.Ref) bool {
 
 // If we failed the check, then the subiterator should not contribute to the result
 // set. Otherwise, go ahead and tag it.
-func (it *ValueFilter) TagResults(dst map[string]graph.Ref) {
+func (it *valueFilterContains) TagResults(dst map[string]graph.Ref) {
 	it.sub.TagResults(dst)
 }
 
-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() (graph.Iterator, bool) {
-	newSub, changed := it.sub.Optimize()
-	if changed {
-		it.sub.Close()
-		it.sub = newSub
-	}
-	return it, false
-}
-
-// We're only as expensive as our subiterator.
-// Again, optimized value comparison iterators should do better.
-func (it *ValueFilter) Stats() graph.IteratorStats {
-	return it.sub.Stats()
-}
-
-func (it *ValueFilter) Size() (int64, bool) {
-	sz, _ := it.sub.Size()
-	return sz / 2, false
+func (it *valueFilterContains) String() string {
+	return "ValueFilterContains"
 }
diff --git a/graph/kv/all_iterator.go b/graph/kv/all_iterator.go
index 0ab3a0a..0dcfcc7 100644
--- a/graph/kv/all_iterator.go
+++ b/graph/kv/all_iterator.go
@@ -18,12 +18,101 @@ import (
 	"context"
 
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/graph/proto"
 	"github.com/cayleygraph/cayley/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
+	cons  *constraint
+}
+
+func newAllIterator(nodes bool, qs *QuadStore, 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,
+		cons:  cons,
+	}
+}
+
+func (it *allIterator) Iterate() graph.Scanner {
+	return newAllIteratorNext(it.nodes, it.qs, 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
+}
+
+// No subiterators.
+func (it *allIterator) SubIterators() []graph.IteratorShape {
+	return nil
+}
+
+func (it *allIterator) Size() (int64, bool) {
+	return it.qs.Size(), false
+}
+
+func (it *allIterator) String() string {
+	return "KVAll"
+}
+
+func (it *allIterator) Sorted() bool { return false }
+
+func (it *allIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	return it, false
+}
+
+func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     2,
+		Size: graph.Size{
+			Size:  it.qs.Size(),
+			Exact: false,
+		},
+	}, nil
+}
+
+type allIteratorNext struct {
 	nodes   bool
 	id      uint64
 	buf     []*proto.Primitive
@@ -31,49 +120,32 @@ type AllIterator struct {
 	horizon int64
 	qs      *QuadStore
 	err     error
-	uid     uint64
 	cons    *constraint
 }
 
-var _ graph.Iterator = &AllIterator{}
-
-type constraint struct {
-	dir quad.Direction
-	val Int64Value
-}
-
-func NewAllIterator(nodes bool, qs *QuadStore, cons *constraint) *AllIterator {
+func newAllIteratorNext(nodes bool, qs *QuadStore, cons *constraint) *allIteratorNext {
 	if nodes && cons != nil {
 		panic("cannot use a kv all iterator across nodes with a constraint")
 	}
-	return &AllIterator{
+	return &allIteratorNext{
 		nodes:   nodes,
 		qs:      qs,
 		horizon: qs.horizon(context.TODO()),
-		uid:     iterator.NextUID(),
 		cons:    cons,
 	}
 }
 
-func (it *AllIterator) UID() uint64 {
-	return it.uid
-}
+func (it *allIteratorNext) TagResults(dst map[string]graph.Ref) {}
 
-func (it *AllIterator) Reset() {
-	it.id = 0
-}
-
-func (it *AllIterator) TagResults(dst map[string]graph.Ref) {}
-
-func (it *AllIterator) Close() error {
+func (it *allIteratorNext) Close() error {
 	return nil
 }
 
-func (it *AllIterator) Err() error {
+func (it *allIteratorNext) Err() error {
 	return it.err
 }
 
-func (it *AllIterator) Result() graph.Ref {
+func (it *allIteratorNext) Result() graph.Ref {
 	if it.id > uint64(it.horizon) {
 		return nil
 	}
@@ -86,14 +158,9 @@ func (it *AllIterator) Result() graph.Ref {
 	return it.prim
 }
 
-// No subiterators.
-func (it *AllIterator) SubIterators() []graph.Iterator {
-	return nil
-}
-
 const nextBatch = 100
 
-func (it *AllIterator) Next(ctx context.Context) bool {
+func (it *allIteratorNext) Next(ctx context.Context) bool {
 	if it.err != nil {
 		return false
 	}
@@ -142,11 +209,70 @@ func (it *AllIterator) Next(ctx context.Context) bool {
 	}
 }
 
-func (it *AllIterator) NextPath(ctx context.Context) bool {
+func (it *allIteratorNext) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *allIteratorNext) String() string {
+	return "KVAllNext"
+}
+
+func (it *allIteratorNext) Sorted() bool { return false }
+
+type allIteratorContains struct {
+	nodes   bool
+	id      uint64
+	prim    *proto.Primitive
+	horizon int64
+	qs      *QuadStore
+	err     error
+	cons    *constraint
+}
+
+func newAllIteratorContains(nodes bool, qs *QuadStore, 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,
+		horizon: qs.horizon(context.TODO()),
+		cons:    cons,
+	}
+}
+
+func (it *allIteratorContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *allIteratorContains) Close() error {
+	return nil
+}
+
+func (it *allIteratorContains) Err() error {
+	return it.err
+}
+
+func (it *allIteratorContains) Result() graph.Ref {
+	if it.id > uint64(it.horizon) {
+		return nil
+	}
+	if it.nodes {
+		return Int64Value(it.id)
+	}
+	if it.prim == nil {
+		return nil
+	}
+	return it.prim
+}
+
+func (it *allIteratorContains) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *AllIterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *allIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
+	// TODO(dennwc): This method doesn't check if the primitive still exists in the store.
+	//               It's okay if we assume we provide the snapshot of data, though.
+	//               However, passing a hand-crafted Ref will cause invalid results.
+	//               Same is true for QuadIterator.
 	if it.nodes {
 		x, ok := v.(Int64Value)
 		if !ok {
@@ -170,26 +296,8 @@ func (it *AllIterator) Contains(ctx context.Context, v graph.Ref) bool {
 	return true
 }
 
-func (it *AllIterator) Size() (int64, bool) {
-	return it.qs.Size(), false
-}
-
-func (it *AllIterator) String() string {
-	return "KVAll"
+func (it *allIteratorContains) String() string {
+	return "KVAllContains"
 }
 
-func (it *AllIterator) Sorted() bool { return false }
-
-func (it *AllIterator) Optimize() (graph.Iterator, bool) {
-	return it, false
-}
-
-func (it *AllIterator) Stats() graph.IteratorStats {
-	s, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: 1,
-		NextCost:     2,
-		Size:         s,
-		ExactSize:    exact,
-	}
-}
+func (it *allIteratorContains) Sorted() bool { return false }
diff --git a/graph/kv/quad_iterator.go b/graph/kv/quad_iterator.go
index be859a7..eb6141b 100644
--- a/graph/kv/quad_iterator.go
+++ b/graph/kv/quad_iterator.go
@@ -19,18 +19,111 @@ import (
 	"fmt"
 
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/graph/proto"
 	"github.com/hidal-go/hidalgo/kv"
 )
 
+var _ graph.IteratorFuture = &QuadIterator{}
+
 type QuadIterator struct {
-	uid     uint64
-	qs      *QuadStore
-	ind     QuadIndex
-	horizon int64
-	vals    []uint64
-	size    graph.Size
+	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
+
+	size graph.Size
+	err  error
+}
+
+func newQuadIterator(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIterator {
+	return &quadIterator{
+		qs:   qs,
+		ind:  ind,
+		vals: vals,
+		size: graph.Size{Size: -1},
+	}
+}
+
+func (it *quadIterator) Iterate() graph.Scanner {
+	return newQuadIteratorNext(it.qs, it.ind, it.vals)
+}
+
+func (it *quadIterator) Lookup() graph.Index {
+	return newQuadIteratorContains(it.qs, 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 {
+	return nil
+}
+
+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 {
+		return it.size, nil
+	}
+	if len(it.ind.Dirs) == len(it.vals) {
+		sz, err := it.qs.indexSize(ctx, it.ind, it.vals)
+		if err != nil {
+			it.err = err
+			return graph.Size{}, it.err
+		}
+		it.size = sz
+		return sz, nil
+	}
+	return graph.Size{Size: 1 + it.qs.Size()/2, Exact: false}, nil
+}
+
+func (it *quadIterator) String() string {
+	return fmt.Sprintf("KVQuads(%v)", it.ind)
+}
+
+func (it *quadIterator) Sorted() bool { return true }
+
+func (it *quadIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	return it, false
+}
+
+func (it *quadIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	s, err := it.getSize(ctx)
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     2,
+		Size:         s,
+	}, err
+}
+
+type quadIteratorNext struct {
+	qs   *QuadStore
+	ind  QuadIndex
+	vals []uint64
 
 	tx   kv.Tx
 	it   kv.Iterator
@@ -43,37 +136,17 @@ type QuadIterator struct {
 	prim *proto.Primitive
 }
 
-var _ graph.Iterator = &QuadIterator{}
-
-func NewQuadIterator(qs *QuadStore, ind QuadIndex, vals []uint64) *QuadIterator {
-	return &QuadIterator{
-		qs:      qs,
-		ind:     ind,
-		horizon: qs.horizon(context.TODO()),
-		uid:     iterator.NextUID(),
-		vals:    vals,
-		size:    graph.Size{Size: -1},
+func newQuadIteratorNext(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIteratorNext {
+	return &quadIteratorNext{
+		qs:   qs,
+		ind:  ind,
+		vals: vals,
 	}
 }
 
-func (it *QuadIterator) UID() uint64 {
-	return it.uid
-}
+func (it *quadIteratorNext) TagResults(dst map[string]graph.Ref) {}
 
-func (it *QuadIterator) Reset() {
-	it.off = 0
-	it.ids = nil
-	it.buf = nil
-	it.done = false
-	if it.it != nil {
-		it.it.Close()
-		it.it = it.tx.Scan(it.ind.Key(it.vals))
-	}
-}
-
-func (it *QuadIterator) TagResults(dst map[string]graph.Ref) {}
-
-func (it *QuadIterator) Close() error {
+func (it *quadIteratorNext) Close() error {
 	if it.it != nil {
 		if err := it.it.Close(); err != nil && it.err == nil {
 			it.err = err
@@ -87,18 +160,18 @@ func (it *QuadIterator) Close() error {
 	return it.err
 }
 
-func (it *QuadIterator) Err() error {
+func (it *quadIteratorNext) Err() error {
 	return it.err
 }
 
-func (it *QuadIterator) Result() graph.Ref {
+func (it *quadIteratorNext) Result() graph.Ref {
 	if it.off < 0 || it.prim == nil {
 		return nil
 	}
 	return it.prim
 }
 
-func (it *QuadIterator) ensureTx() bool {
+func (it *quadIteratorNext) ensureTx() bool {
 	if it.tx != nil {
 		return true
 	}
@@ -109,7 +182,7 @@ func (it *QuadIterator) ensureTx() bool {
 	return true
 }
 
-func (it *QuadIterator) Next(ctx context.Context) bool {
+func (it *quadIteratorNext) Next(ctx context.Context) bool {
 	it.prim = nil
 	if it.err != nil || it.done {
 		return false
@@ -156,18 +229,64 @@ func (it *QuadIterator) Next(ctx context.Context) bool {
 			if p == nil || p.Deleted {
 				continue
 			}
+			// TODO(dennwc): shouldn't this check the horizon?
 			it.prim = p
 			return true
 		}
 	}
 }
 
-func (it *QuadIterator) NextPath(ctx context.Context) bool {
+func (it *quadIteratorNext) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *quadIteratorNext) String() string {
+	return fmt.Sprintf("KVQuadsNext(%v)", it.ind)
+}
+
+func (it *quadIteratorNext) Sorted() bool { return true }
+
+type quadIteratorContains struct {
+	qs   *QuadStore
+	ind  QuadIndex
+	vals []uint64
+
+	err  error
+	prim *proto.Primitive
+}
+
+func newQuadIteratorContains(qs *QuadStore, ind QuadIndex, vals []uint64) *quadIteratorContains {
+	return &quadIteratorContains{
+		qs:   qs,
+		ind:  ind,
+		vals: vals,
+	}
+}
+
+func (it *quadIteratorContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *quadIteratorContains) Close() error {
+	return it.err
+}
+
+func (it *quadIteratorContains) Err() error {
+	return it.err
+}
+
+func (it *quadIteratorContains) Result() graph.Ref {
+	if it.prim == nil {
+		return nil
+	}
+	return it.prim
+}
+
+func (it *quadIteratorContains) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *QuadIterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *quadIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
 	it.prim = nil
+	// TODO(dennwc): shouldn't this check the horizon?
 	p, ok := v.(*proto.Primitive)
 	if !ok {
 		return false
@@ -177,48 +296,12 @@ func (it *QuadIterator) Contains(ctx context.Context, v graph.Ref) bool {
 			return false
 		}
 	}
+	it.prim = p
 	return true
 }
 
-func (it *QuadIterator) SubIterators() []graph.Iterator {
-	return nil
-}
-
-func (it *QuadIterator) Size() (int64, bool) {
-	if it.err != nil {
-		return 0, false
-	} else if it.size.Size >= 0 {
-		return it.size.Size, it.size.Exact
-	}
-	ctx := context.TODO()
-	if len(it.ind.Dirs) == len(it.vals) {
-		sz, err := it.qs.indexSize(ctx, it.ind, it.vals)
-		if err != nil {
-			it.err = err
-			return 0, false
-		}
-		it.size = sz
-		return sz.Size, sz.Exact
-	}
-	return 1 + it.qs.Size()/2, false
-}
-
-func (it *QuadIterator) String() string {
-	return fmt.Sprintf("KVQuads(%v)", it.ind)
-}
-
-func (it *QuadIterator) Sorted() bool { return true }
-
-func (it *QuadIterator) Optimize() (graph.Iterator, bool) {
-	return it, false
+func (it *quadIteratorContains) String() string {
+	return fmt.Sprintf("KVQuadsContains(%v)", it.ind)
 }
 
-func (it *QuadIterator) Stats() graph.IteratorStats {
-	s, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: 1,
-		NextCost:     2,
-		Size:         s,
-		ExactSize:    exact,
-	}
-}
+func (it *quadIteratorContains) Sorted() bool { return true }
diff --git a/graph/memstore/all_iterator.go b/graph/memstore/all_iterator.go
index a5e9838..9cab3a3 100644
--- a/graph/memstore/all_iterator.go
+++ b/graph/memstore/all_iterator.go
@@ -18,50 +18,113 @@ import (
 	"context"
 
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 )
 
-var _ graph.Iterator = (*AllIterator)(nil)
+var _ graph.IteratorFuture = (*AllIterator)(nil)
 
 type AllIterator struct {
-	uid uint64
+	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 {
 	qs    *QuadStore
 	all   []*primitive
 	maxid int64 // id of last observed insert (prim id)
 	nodes bool
-
-	i    int // index into qs.all
-	cur  *primitive
-	done bool
 }
 
-func newAllIterator(qs *QuadStore, nodes bool, maxid int64) *AllIterator {
-	return &AllIterator{
-		uid: iterator.NextUID(),
-		qs:  qs, all: qs.cloneAll(), nodes: nodes,
-		i: -1, maxid: maxid,
+func newAllIterator2(qs *QuadStore, nodes bool, maxid int64) *allIterator {
+	return &allIterator{
+		qs: qs, all: qs.cloneAll(), nodes: nodes,
+		maxid: maxid,
 	}
 }
 
-func (it *AllIterator) Reset() {
-	it.i = -1
-	it.cur = nil
-	it.done = false
+func (it *allIterator) Iterate() graph.Scanner {
+	return newAllIteratorNext(it.qs, it.nodes, it.maxid, it.all)
 }
 
-func (it *AllIterator) ok(p *primitive) bool {
-	if p.ID > it.maxid {
+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
+}
+
+func (it *allIterator) SubIterators() []graph.IteratorShape { return nil }
+func (it *allIterator) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	return it, false
+}
+
+func (it *allIterator) String() string {
+	return "MemStoreAll"
+}
+
+func (it *allIterator) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	return graph.IteratorCosts{
+		NextCost:     1,
+		ContainsCost: 1,
+		Size: graph.Size{
+			// TODO(dennwc): use maxid?
+			Size:  int64(len(it.all)),
+			Exact: true,
+		},
+	}, nil
+}
+
+func (p *primitive) filter(isNode bool, maxid int64) bool {
+	if p.ID > maxid {
 		return false
-	} else if it.nodes && p.Value != nil {
+	} else if isNode && p.Value != nil {
 		return true
-	} else if !it.nodes && !p.Quad.Zero() {
+	} else if !isNode && !p.Quad.Zero() {
 		return true
 	}
 	return false
 }
 
-func (it *AllIterator) Next(ctx context.Context) bool {
+type allIteratorNext struct {
+	qs    *QuadStore
+	all   []*primitive
+	maxid int64 // id of last observed insert (prim id)
+	nodes bool
+
+	i    int // index into qs.all
+	cur  *primitive
+	done bool
+}
+
+func newAllIteratorNext(qs *QuadStore, nodes bool, maxid int64, all []*primitive) *allIteratorNext {
+	return &allIteratorNext{
+		qs: qs, all: all, nodes: nodes,
+		i: -1, maxid: maxid,
+	}
+}
+
+func (it *allIteratorNext) ok(p *primitive) bool {
+	return p.filter(it.nodes, it.maxid)
+}
+
+func (it *allIteratorNext) Next(ctx context.Context) bool {
 	it.cur = nil
 	if it.done {
 		return false
@@ -86,7 +149,51 @@ func (it *AllIterator) Next(ctx context.Context) bool {
 	return false
 }
 
-func (it *AllIterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *allIteratorNext) Result() graph.Ref {
+	if it.cur == nil {
+		return nil
+	}
+	if !it.cur.Quad.Zero() {
+		return qprim{p: it.cur}
+	}
+	return bnode(it.cur.ID)
+}
+
+func (it *allIteratorNext) Err() error { return nil }
+func (it *allIteratorNext) Close() error {
+	it.done = true
+	it.all = nil
+	return nil
+}
+
+func (it *allIteratorNext) TagResults(dst map[string]graph.Ref) {}
+
+func (it *allIteratorNext) String() string {
+	return "MemStoreAllNext"
+}
+func (it *allIteratorNext) NextPath(ctx context.Context) bool { return false }
+
+type allIteratorContains struct {
+	qs    *QuadStore
+	maxid int64 // id of last observed insert (prim id)
+	nodes bool
+
+	cur  *primitive
+	done bool
+}
+
+func newAllIteratorContains(qs *QuadStore, nodes bool, maxid int64) *allIteratorContains {
+	return &allIteratorContains{
+		qs: qs, nodes: nodes,
+		maxid: maxid,
+	}
+}
+
+func (it *allIteratorContains) ok(p *primitive) bool {
+	return p.filter(it.nodes, it.maxid)
+}
+
+func (it *allIteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
 	it.cur = nil
 	if it.done {
 		return false
@@ -105,7 +212,7 @@ func (it *AllIterator) Contains(ctx context.Context, v graph.Ref) bool {
 	it.cur = p
 	return true
 }
-func (it *AllIterator) Result() graph.Ref {
+func (it *allIteratorContains) Result() graph.Ref {
 	if it.cur == nil {
 		return nil
 	}
@@ -115,32 +222,15 @@ func (it *AllIterator) Result() graph.Ref {
 	return bnode(it.cur.ID)
 }
 
-func (it *AllIterator) Err() error { return nil }
-func (it *AllIterator) Close() error {
+func (it *allIteratorContains) Err() error { return nil }
+func (it *allIteratorContains) Close() error {
 	it.done = true
-	it.all = nil
 	return nil
 }
 
-func (it *AllIterator) TagResults(dst map[string]graph.Ref) {}
-
-func (it *AllIterator) SubIterators() []graph.Iterator   { return nil }
-func (it *AllIterator) Optimize() (graph.Iterator, bool) { return it, false }
+func (it *allIteratorContains) TagResults(dst map[string]graph.Ref) {}
 
-func (it *AllIterator) UID() uint64 {
-	return it.uid
-}
-func (it *AllIterator) String() string {
-	return "MemStoreAll"
-}
-func (it *AllIterator) NextPath(ctx context.Context) bool { return false }
-
-func (it *AllIterator) Size() (int64, bool) {
-	// TODO: use maxid?
-	return int64(len(it.all)), true
-}
-func (it *AllIterator) Stats() graph.IteratorStats {
-	st := graph.IteratorStats{NextCost: 1, ContainsCost: 1}
-	st.Size, st.ExactSize = it.Size()
-	return st
+func (it *allIteratorContains) String() string {
+	return "MemStoreAllContains"
 }
+func (it *allIteratorContains) NextPath(ctx context.Context) bool { return false }
diff --git a/graph/memstore/iterator.go b/graph/memstore/iterator.go
index 4d6b0cb..d24b362 100644
--- a/graph/memstore/iterator.go
+++ b/graph/memstore/iterator.go
@@ -21,30 +21,42 @@ import (
 	"math"
 
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/quad"
 )
 
 var _ graph.Iterator = &Iterator{}
 
 type Iterator struct {
-	nodes bool
-	uid   uint64
-	qs    *QuadStore
-	tree  *Tree
+	it *iterator2
+	graph.Iterator
+}
 
-	iter *Enumerator
-	cur  *primitive
-	err  error
+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) *Iterator {
-	return &Iterator{
-		nodes: d == 0,
-		uid:   iterator.NextUID(),
+func newIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iterator2 {
+	return &iterator2{
 		qs:    qs,
 		tree:  tree,
 		d:     d,
@@ -52,23 +64,73 @@ func NewIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *Iter
 	}
 }
 
-func (it *Iterator) UID() uint64 {
-	return it.uid
+func (it *iterator2) 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)
 }
 
-func (it *Iterator) Reset() {
-	it.iter = nil
-	it.err = nil
-	it.cur = nil
+func (it *iterator2) Lookup() graph.Index {
+	return newIteratorContains(it.tree, it.qs, it.d, it.value)
 }
 
-func (it *Iterator) TagResults(dst map[string]graph.Ref) {}
+func (it *iterator2) AsLegacy() graph.Iterator {
+	it2 := &Iterator{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
+}
 
-func (it *Iterator) Close() error {
+func (it *iterator2) SubIterators() []graph.IteratorShape {
 	return nil
 }
 
-func (it *Iterator) Next(ctx context.Context) bool {
+func (it *iterator2) String() string {
+	return fmt.Sprintf("MemStore(%v)", it.d)
+}
+
+func (it *iterator2) Sorted() bool { return true }
+
+func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	return it, false
+}
+
+func (it *iterator2) 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()),
+			Exact: true,
+		},
+	}, nil
+}
+
+type iteratorNext struct {
+	nodes bool
+	qs    *QuadStore
+	tree  *Tree
+	d     quad.Direction
+
+	iter *Enumerator
+	cur  *primitive
+	err  error
+}
+
+func newIteratorNext(tree *Tree, qs *QuadStore, d quad.Direction) *iteratorNext {
+	return &iteratorNext{
+		nodes: d == 0,
+		d:     d,
+		qs:    qs,
+		tree:  tree,
+	}
+}
+
+func (it *iteratorNext) TagResults(dst map[string]graph.Ref) {}
+
+func (it *iteratorNext) Close() error {
+	return nil
+}
+
+func (it *iteratorNext) Next(ctx context.Context) bool {
 	if it.iter == nil {
 		it.iter, it.err = it.tree.SeekFirst()
 		if it.err == io.EOF || it.iter == nil {
@@ -91,31 +153,70 @@ func (it *Iterator) Next(ctx context.Context) bool {
 	}
 }
 
-func (it *Iterator) Err() error {
+func (it *iteratorNext) Err() error {
 	return it.err
 }
 
-func (it *Iterator) Result() graph.Ref {
+func (it *iteratorNext) Result() graph.Ref {
 	if it.cur == nil {
 		return nil
 	}
 	return qprim{p: it.cur}
 }
 
-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 {
+func (it *iteratorNext) String() string {
+	return fmt.Sprintf("MemStoreNext(%v)", it.d)
+}
+
+func (it *iteratorNext) Sorted() bool { return true }
+
+type iteratorContains struct {
+	nodes bool
+	qs    *QuadStore
+	tree  *Tree
+
+	cur *primitive
+
+	d     quad.Direction
+	value int64
+}
+
+func newIteratorContains(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *iteratorContains {
+	return &iteratorContains{
+		nodes: d == 0,
+		qs:    qs,
+		tree:  tree,
+		d:     d,
+		value: value,
+	}
+}
+
+func (it *iteratorContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *iteratorContains) Close() error {
+	return nil
+}
+
+func (it *iteratorContains) Err() error {
 	return nil
 }
 
-func (it *Iterator) Size() (int64, bool) {
-	return int64(it.tree.Len()), true
+func (it *iteratorContains) Result() graph.Ref {
+	if it.cur == nil {
+		return nil
+	}
+	return qprim{p: it.cur}
 }
 
-func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *iteratorContains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
 	if v == nil {
 		return false
 	}
@@ -134,21 +235,8 @@ func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
 	return false
 }
 
-func (it *Iterator) String() string {
-	return fmt.Sprintf("MemStore(%v)", it.d)
+func (it *iteratorContains) String() string {
+	return fmt.Sprintf("MemStoreContains(%v)", it.d)
 }
 
-func (it *Iterator) Sorted() bool { return true }
-
-func (it *Iterator) Optimize() (graph.Iterator, bool) {
-	return it, false
-}
-
-func (it *Iterator) Stats() graph.IteratorStats {
-	return graph.IteratorStats{
-		ContainsCost: int64(math.Log(float64(it.tree.Len()))) + 1,
-		NextCost:     1,
-		Size:         int64(it.tree.Len()),
-		ExactSize:    true,
-	}
-}
+func (it *iteratorContains) Sorted() bool { return true }
diff --git a/graph/nosql/iterator.go b/graph/nosql/iterator.go
index 6ccd537..8f5ddb7 100644
--- a/graph/nosql/iterator.go
+++ b/graph/nosql/iterator.go
@@ -22,31 +22,14 @@ import (
 
 	"github.com/cayleygraph/cayley/clog"
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/quad"
 )
 
-var _ graph.Iterator = (*Iterator)(nil)
-
 type Linkage struct {
 	Dir quad.Direction
 	Val NodeHash
 }
 
-type Iterator struct {
-	uid        uint64
-	qs         *QuadStore
-	collection string
-	limit      int64
-	constraint []nosql.FieldFilter
-	links      []Linkage // used in Contains
-
-	iter   nosql.DocIterator
-	result graph.Ref
-	size   int64
-	err    error
-}
-
 func linkageToFilters(links []Linkage) []nosql.FieldFilter {
 	filters := make([]nosql.FieldFilter, 0, len(links))
 	for _, l := range links {
@@ -59,53 +42,163 @@ 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
+	constraint []nosql.FieldFilter
+	links      []Linkage // used in Contains
+
+	size graph.Size
+	err  error
+}
+
+func newLinksToIterator(qs *QuadStore, collection string, links []Linkage) *iterator2 {
 	filters := linkageToFilters(links)
-	it := NewIterator(qs, collection, filters...)
+	it := newIterator(qs, collection, filters...)
 	it.links = links
 	return it
 }
 
-func (it *Iterator) makeIterator() nosql.DocIterator {
-	q := it.qs.db.Query(it.collection)
-	if len(it.constraint) != 0 {
-		q = q.WithFields(it.constraint...)
+func newIterator(qs *QuadStore, collection string, constraints ...nosql.FieldFilter) *iterator2 {
+	return &iterator2{
+		qs:         qs,
+		constraint: constraints,
+		collection: collection,
+		size:       graph.Size{Size: -1},
 	}
-	if it.limit > 0 {
-		q = q.Limit(int(it.limit))
+}
+
+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 *iterator2) AsLegacy() graph.Iterator {
+	it2 := &Iterator{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
+}
+
+func (it *iterator2) SubIterators() []graph.IteratorShape {
+	return nil
+}
+
+func (it *iterator2) getSize(ctx context.Context) (graph.Size, error) {
+	if it.size.Size == -1 {
+		size, err := it.qs.getSize(it.collection, it.constraint)
+		if err != nil {
+			it.err = err
+		}
+		it.size = graph.Size{
+			Size:  size,
+			Exact: true,
+		}
 	}
-	return q.Iterate()
+	if it.limit > 0 && it.size.Size > it.limit {
+		it.size.Size = it.limit
+	}
+	if it.size.Size < 0 {
+		return graph.Size{
+			Size:  it.qs.Size(),
+			Exact: false,
+		}, it.err
+	}
+	return it.size, nil
 }
 
-func NewIterator(qs *QuadStore, collection string, constraints ...nosql.FieldFilter) *Iterator {
-	return &Iterator{
-		uid:        iterator.NextUID(),
+func (it *iterator2) Sorted() bool                                             { return true }
+func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) { return it, false }
+
+func (it *iterator2) String() string {
+	return fmt.Sprintf("NoSQL(%v)", it.collection)
+}
+
+func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	size, err := it.getSize(ctx)
+	return graph.IteratorCosts{
+		ContainsCost: 1,
+		NextCost:     5,
+		Size:         size,
+	}, err
+}
+
+type iteratorNext struct {
+	qs         *QuadStore
+	collection string
+	limit      int64
+	constraint []nosql.FieldFilter
+
+	iter   nosql.DocIterator
+	result graph.Ref
+	err    error
+}
+
+func newIteratorNext(qs *QuadStore, collection string, constraints []nosql.FieldFilter, limit int64) *iteratorNext {
+	return &iteratorNext{
 		qs:         qs,
 		constraint: constraints,
 		collection: collection,
-		size:       -1,
+		limit:      limit,
 	}
 }
 
-func (it *Iterator) UID() uint64 {
-	return it.uid
-}
-
-func (it *Iterator) Reset() {
-	it.Close()
-	it.iter = it.makeIterator()
+func (it *iteratorNext) makeIterator() nosql.DocIterator {
+	q := it.qs.db.Query(it.collection)
+	if len(it.constraint) != 0 {
+		q = q.WithFields(it.constraint...)
+	}
+	if it.limit > 0 {
+		q = q.Limit(int(it.limit))
+	}
+	return q.Iterate()
 }
 
-func (it *Iterator) Close() error {
+func (it *iteratorNext) Close() error {
 	if it.iter != nil {
 		return it.iter.Close()
 	}
 	return nil
 }
 
-func (it *Iterator) TagResults(dst map[string]graph.Ref) {}
+func (it *iteratorNext) TagResults(dst map[string]graph.Ref) {}
 
-func (it *Iterator) Next(ctx context.Context) bool {
+func (it *iteratorNext) Next(ctx context.Context) bool {
 	if it.iter == nil {
 		it.iter = it.makeIterator()
 	}
@@ -139,23 +232,79 @@ 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) Result() graph.Ref {
+func (it *iteratorNext) Result() graph.Ref {
 	return it.result
 }
 
-func (it *Iterator) NextPath(ctx context.Context) bool {
+func (it *iteratorNext) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Iterator) SubIterators() []graph.Iterator {
+func (it *iteratorNext) Sorted() bool { return true }
+
+func (it *iteratorNext) String() string {
+	return fmt.Sprintf("NoSQLNext(%v)", it.collection)
+}
+
+type iteratorContains struct {
+	qs         *QuadStore
+	collection string
+	limit      int64 // FIXME(dennwc): doesn't work right now
+	constraint []nosql.FieldFilter
+	links      []Linkage
+
+	iter   nosql.DocIterator
+	result graph.Ref
+	err    error
+}
+
+func newIteratorContains(qs *QuadStore, collection string, constraints []nosql.FieldFilter, links []Linkage, limit int64) *iteratorContains {
+	return &iteratorContains{
+		qs:         qs,
+		collection: collection,
+		constraint: constraints,
+		links:      links,
+		limit:      limit,
+	}
+}
+
+func (it *iteratorContains) makeIterator() nosql.DocIterator {
+	q := it.qs.db.Query(it.collection)
+	if len(it.constraint) != 0 {
+		q = q.WithFields(it.constraint...)
+	}
+	if it.limit > 0 {
+		q = q.Limit(int(it.limit))
+	}
+	return q.Iterate()
+}
+
+func (it *iteratorContains) Close() error {
+	if it.iter != nil {
+		return it.iter.Close()
+	}
 	return nil
 }
 
-func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *iteratorContains) TagResults(dst map[string]graph.Ref) {}
+
+func (it *iteratorContains) Err() error {
+	return it.err
+}
+
+func (it *iteratorContains) Result() graph.Ref {
+	return it.result
+}
+
+func (it *iteratorContains) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
 	if len(it.links) != 0 {
 		qh := v.(QuadHash)
 		for _, l := range it.links {
@@ -184,36 +333,8 @@ func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
 	return true
 }
 
-func (it *Iterator) Size() (int64, bool) {
-	if it.size == -1 {
-		var err error
-		it.size, err = it.qs.getSize(it.collection, it.constraint)
-		if err != nil {
-			it.err = err
-		}
-	}
-	if it.limit > 0 && it.size > it.limit {
-		it.size = it.limit
-	}
-	if it.size < 0 {
-		return it.qs.Size(), false
-	}
-	return it.size, true
-}
-
-func (it *Iterator) Sorted() bool                     { return true }
-func (it *Iterator) Optimize() (graph.Iterator, bool) { return it, false }
-
-func (it *Iterator) String() string {
-	return fmt.Sprintf("NoSQL(%v)", it.collection)
-}
+func (it *iteratorContains) Sorted() bool { return true }
 
-func (it *Iterator) Stats() graph.IteratorStats {
-	size, exact := it.Size()
-	return graph.IteratorStats{
-		ContainsCost: 1,
-		NextCost:     5,
-		Size:         size,
-		ExactSize:    exact,
-	}
+func (it *iteratorContains) String() string {
+	return fmt.Sprintf("NoSQLContains(%v)", it.collection)
 }
diff --git a/graph/shape.go b/graph/shape.go
new file mode 100644
index 0000000..a849822
--- /dev/null
+++ b/graph/shape.go
@@ -0,0 +1,310 @@
+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/sql/iterator.go b/graph/sql/iterator.go
index 9124ed3..f8785a4 100644
--- a/graph/sql/iterator.go
+++ b/graph/sql/iterator.go
@@ -21,7 +21,6 @@ import (
 	"strings"
 
 	"github.com/cayleygraph/cayley/graph"
-	"github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/graph/shape"
 	"github.com/cayleygraph/cayley/quad"
 )
@@ -57,45 +56,218 @@ func (qs *QuadStore) Query(ctx context.Context, s Shape) (*sql.Rows, error) {
 	return rows, nil
 }
 
-var _ graph.Iterator = (*Iterator)(nil)
+var _ graph.IteratorFuture = (*Iterator)(nil)
 
 func (qs *QuadStore) NewIterator(s Select) *Iterator {
-	return &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{
 		qs:    qs,
-		uid:   iterator.NextUID(),
 		query: s,
 	}
 }
 
-type Iterator struct {
+type iterator2 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 *iterator2) AsLegacy() graph.Iterator {
+	it2 := &Iterator{it: it}
+	it2.Iterator = graph.NewLegacy(it, it2)
+	return it2
+}
+
+func (it *iterator2) Stats(ctx context.Context) (graph.IteratorCosts, error) {
+	sz, err := it.getSize(ctx)
+	return graph.IteratorCosts{
+		NextCost:     1,
+		ContainsCost: 10,
+		Size:         sz,
+	}, err
+}
+
+func (it *iterator2) estimateSize(ctx context.Context) int64 {
+	if it.query.Limit > 0 {
+		return it.query.Limit
+	}
+	st, err := it.qs.Stats(ctx, false)
+	if err != nil && it.err == nil {
+		it.err = err
+	}
+	return st.Quads.Size
+}
+
+func (it *iterator2) 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 sz, nil
+}
+
+func (it *iterator2) Optimize(ctx context.Context) (graph.IteratorShape, bool) {
+	return it, false
+}
+
+func (it *iterator2) SubIterators() []graph.IteratorShape {
+	return nil
+}
+
+func (it *iterator2) String() string {
+	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
+}
+
+func newIteratorBase(qs *QuadStore, s Select) iteratorBase {
+	return iteratorBase{
+		qs:    qs,
+		query: s,
+	}
+}
+
+type iteratorBase struct {
 	qs    *QuadStore
-	uid   uint64
 	query Select
 
 	cols []string
 	cind map[quad.Direction]int
 
-	err    error
-	res    graph.Ref
-	tags   map[string]graph.Ref
-	cursor *sql.Rows
+	err  error
+	res  graph.Ref
+	tags map[string]graph.Ref
+}
+
+func (it *iteratorBase) TagResults(m map[string]graph.Ref) {
+	for tag, val := range it.tags {
+		m[tag] = val
+	}
+}
+
+func (it *iteratorBase) Result() graph.Ref {
+	return it.res
 }
 
-func (it *Iterator) UID() uint64 {
-	return it.uid
+func (it *iteratorBase) ensureColumns() {
+	if it.cols != nil {
+		return
+	}
+	it.cols = it.query.Columns()
+	it.cind = make(map[quad.Direction]int, len(quad.Directions)+1)
+	for i, name := range it.cols {
+		if !strings.HasPrefix(name, tagPref) {
+			continue
+		}
+		if name == tagNode {
+			it.cind[quad.Any] = i
+			continue
+		}
+		name = name[len(tagPref):]
+		for _, d := range quad.Directions {
+			if name == d.String() {
+				it.cind[d] = i
+				break
+			}
+		}
+	}
+}
+
+func (it *iteratorBase) scanValue(r *sql.Rows) bool {
+	it.ensureColumns()
+	nodes := make([]NodeHash, len(it.cols))
+	pointers := make([]interface{}, len(nodes))
+	for i := range pointers {
+		pointers[i] = &nodes[i]
+	}
+	if err := r.Scan(pointers...); err != nil {
+		it.err = err
+		return false
+	}
+	it.tags = make(map[string]graph.Ref)
+	for i, name := range it.cols {
+		if !strings.Contains(name, tagPref) {
+			it.tags[name] = nodes[i].ValueHash
+		}
+	}
+	if len(it.cind) > 1 {
+		var q QuadHashes
+		for _, d := range quad.Directions {
+			i, ok := it.cind[d]
+			if !ok {
+				it.err = fmt.Errorf("cannot find quad %v in query output (columns: %v)", d, it.cols)
+				return false
+			}
+			q.Set(d, nodes[i].ValueHash)
+		}
+		it.res = q
+		return true
+	}
+	i, ok := it.cind[quad.Any]
+	if !ok {
+		it.err = fmt.Errorf("cannot find node hash in query output (columns: %v, cind: %v)", it.cols, it.cind)
+		return false
+	}
+	it.res = nodes[i]
+	return true
+}
+
+func (it *iteratorBase) Err() error {
+	return it.err
+}
+
+func (it *iteratorBase) String() string {
+	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
+}
+
+func newIteratorNext(qs *QuadStore, s Select) *iteratorNext {
+	return &iteratorNext{
+		iteratorBase: newIteratorBase(qs, s),
+	}
 }
 
-func (it *Iterator) TagResults(m map[string]graph.Ref) {
+type iteratorNext struct {
+	iteratorBase
+	cursor *sql.Rows
+}
+
+func (it *iteratorNext) TagResults(m map[string]graph.Ref) {
 	for tag, val := range it.tags {
 		m[tag] = val
 	}
 }
 
-func (it *Iterator) Result() graph.Ref {
+func (it *iteratorNext) Result() graph.Ref {
 	return it.res
 }
 
-func (it *Iterator) ensureColumns() {
+func (it *iteratorNext) ensureColumns() {
 	if it.cols != nil {
 		return
 	}
@@ -119,7 +291,7 @@ func (it *Iterator) ensureColumns() {
 	}
 }
 
-func (it *Iterator) scanValue(r *sql.Rows) bool {
+func (it *iteratorNext) scanValue(r *sql.Rows) bool {
 	it.ensureColumns()
 	nodes := make([]NodeHash, len(it.cols))
 	pointers := make([]interface{}, len(nodes))
@@ -158,7 +330,7 @@ func (it *Iterator) scanValue(r *sql.Rows) bool {
 	return true
 }
 
-func (it *Iterator) Next(ctx context.Context) bool {
+func (it *iteratorNext) Next(ctx context.Context) bool {
 	if it.err != nil {
 		return false
 	}
@@ -176,11 +348,114 @@ func (it *Iterator) Next(ctx context.Context) bool {
 	return it.scanValue(it.cursor)
 }
 
-func (it *Iterator) NextPath(ctx context.Context) bool {
+func (it *iteratorNext) NextPath(ctx context.Context) bool {
+	return false
+}
+
+func (it *iteratorNext) Err() error {
+	return it.err
+}
+
+func (it *iteratorNext) String() string {
+	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
+}
+
+func (it *iteratorNext) Close() error {
+	if it.cursor != nil {
+		it.cursor.Close()
+		it.cursor = nil
+	}
+	return nil
+}
+
+func newIteratorContains(qs *QuadStore, s Select) *iteratorContains {
+	return &iteratorContains{
+		iteratorBase: newIteratorBase(qs, s),
+	}
+}
+
+type iteratorContains struct {
+	iteratorBase
+}
+
+func (it *iteratorContains) TagResults(m map[string]graph.Ref) {
+	for tag, val := range it.tags {
+		m[tag] = val
+	}
+}
+
+func (it *iteratorContains) Result() graph.Ref {
+	return it.res
+}
+
+func (it *iteratorContains) ensureColumns() {
+	if it.cols != nil {
+		return
+	}
+	it.cols = it.query.Columns()
+	it.cind = make(map[quad.Direction]int, len(quad.Directions)+1)
+	for i, name := range it.cols {
+		if !strings.HasPrefix(name, tagPref) {
+			continue
+		}
+		if name == tagNode {
+			it.cind[quad.Any] = i
+			continue
+		}
+		name = name[len(tagPref):]
+		for _, d := range quad.Directions {
+			if name == d.String() {
+				it.cind[d] = i
+				break
+			}
+		}
+	}
+}
+
+func (it *iteratorContains) scanValue(r *sql.Rows) bool {
+	it.ensureColumns()
+	nodes := make([]NodeHash, len(it.cols))
+	pointers := make([]interface{}, len(nodes))
+	for i := range pointers {
+		pointers[i] = &nodes[i]
+	}
+	if err := r.Scan(pointers...); err != nil {
+		it.err = err
+		return false
+	}
+	it.tags = make(map[string]graph.Ref)
+	for i, name := range it.cols {
+		if !strings.Contains(name, tagPref) {
+			it.tags[name] = nodes[i].ValueHash
+		}
+	}
+	if len(it.cind) > 1 {
+		var q QuadHashes
+		for _, d := range quad.Directions {
+			i, ok := it.cind[d]
+			if !ok {
+				it.err = fmt.Errorf("cannot find quad %v in query output (columns: %v)", d, it.cols)
+				return false
+			}
+			q.Set(d, nodes[i].ValueHash)
+		}
+		it.res = q
+		return true
+	}
+	i, ok := it.cind[quad.Any]
+	if !ok {
+		it.err = fmt.Errorf("cannot find node hash in query output (columns: %v, cind: %v)", it.cols, it.cind)
+		return false
+	}
+	it.res = nodes[i]
+	return true
+}
+
+func (it *iteratorContains) NextPath(ctx context.Context) bool {
 	return false
 }
 
-func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
+func (it *iteratorContains) Contains(ctx context.Context, v graph.Ref) bool {
 	it.ensureColumns()
 	sel := it.query
 	sel.Where = append([]Where{}, sel.Where...)
@@ -222,66 +497,14 @@ func (it *Iterator) Contains(ctx context.Context, v graph.Ref) bool {
 	return it.scanValue(rows)
 }
 
-func (it *Iterator) Err() error {
+func (it *iteratorContains) Err() error {
 	return it.err
 }
 
-func (it *Iterator) Reset() {
-	it.cols = nil
-	it.cind = nil
-	it.res = nil
-	it.err = nil
-	if it.cursor != nil {
-		it.cursor.Close()
-		it.cursor = nil
-	}
-}
-
-func (it *Iterator) Stats() graph.IteratorStats {
-	sz, exact := it.Size()
-	return graph.IteratorStats{
-		NextCost:     1,
-		ContainsCost: 10,
-		Size:         sz, ExactSize: exact,
-	}
-}
-
-func (it *Iterator) estimateSize() int64 {
-	if it.query.Limit > 0 {
-		return it.query.Limit
-	}
-	st, err := it.qs.Stats(context.TODO(), false)
-	if err != nil && it.err == nil {
-		it.err = err
-	}
-	return st.Quads.Size
-}
-
-func (it *Iterator) Size() (int64, bool) {
-	sz, err := it.qs.querySize(context.TODO(), it.query)
-	if err != nil {
-		it.err = err
-		return it.estimateSize(), false
-	}
-	return sz.Size, sz.Exact
-}
-
-func (it *Iterator) Optimize() (graph.Iterator, bool) {
-	return it, false
-}
-
-func (it *Iterator) SubIterators() []graph.Iterator {
-	return nil
-}
-
-func (it *Iterator) String() string {
+func (it *iteratorContains) String() string {
 	return it.query.SQL(NewBuilder(it.qs.flavor.QueryDialect))
 }
 
-func (it *Iterator) Close() error {
-	if it.cursor != nil {
-		it.cursor.Close()
-		it.cursor = nil
-	}
+func (it *iteratorContains) Close() error {
 	return nil
 }


Test patch:
diff --git a/graph/graphtest/graphtest.go b/graph/graphtest/graphtest.go
index 5751542..b77c6e3 100644
--- a/graph/graphtest/graphtest.go
+++ b/graph/graphtest/graphtest.go
@@ -541,7 +541,7 @@ func TestIterator(t testing.TB, gen testutil.DatabaseFunc, _ *Config) {
 	//}
 
 	optIt, changed := it.Optimize()
-	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T", changed, optIt)
+	require.True(t, !changed && optIt == it, "Optimize unexpectedly changed iterator: %v, %T(%p) vs %T(%p)", changed, optIt, optIt, it, it)
 
 	expect := []string{
 		"A",
@@ -958,9 +958,10 @@ func TestIteratorsAndNextResultOrderA(t testing.TB, gen testutil.DatabaseFunc, c
 
 	all := qs.NodesAllIterator()
 
+	const allTag = "all"
 	innerAnd := iterator.NewAnd(
 		iterator.NewLinksTo(qs, fixed2, quad.Predicate),
-		iterator.NewLinksTo(qs, all, quad.Object),
+		iterator.NewLinksTo(qs, iterator.Tag(all, allTag), quad.Object),
 	)
 
 	hasa := iterator.NewHasA(qs, innerAnd, quad.Subject)
@@ -976,7 +977,9 @@ func TestIteratorsAndNextResultOrderA(t testing.TB, gen testutil.DatabaseFunc, c
 		expect = []string{"B", "D"}
 	)
 	for {
-		got = append(got, quad.ToString(qs.NameOf(all.Result())))
+		m := make(map[string]graph.Ref, 1)
+		outerAnd.TagResults(m)
+		got = append(got, quad.ToString(qs.NameOf(m[allTag])))
 		if !outerAnd.NextPath(ctx) {
 			break
 		}
diff --git a/graph/iterator/and_optimize_test.go b/graph/iterator/and_optimize_test.go
index 56f31a6..e902812 100644
--- a/graph/iterator/and_optimize_test.go
+++ b/graph/iterator/and_optimize_test.go
@@ -24,7 +24,7 @@ import (
 )
 
 func TestNullIteratorAnd(t *testing.T) {
-	all := NewInt64(1, 3, true)
+	all := newInt64(1, 3, true)
 	null := NewNull()
 	a := NewAnd(all, null)
 	newIt, changed := a.Optimize()
@@ -57,8 +57,8 @@ func TestReorderWithTag(t *testing.T) {
 }
 
 func TestAndStatistics(t *testing.T) {
-	all := NewInt64(100, 300, true)
-	all2 := NewInt64(1, 30000, true)
+	all := newInt64(100, 300, true)
+	all2 := newInt64(1, 30000, true)
 	a := NewAnd()
 	// Make all2 the default iterator
 	a.AddSubIterator(all2)
diff --git a/graph/iterator/and_test.go b/graph/iterator/and_test.go
index 1baf3d8..67f43d3 100644
--- a/graph/iterator/and_test.go
+++ b/graph/iterator/and_test.go
@@ -69,7 +69,7 @@ func TestAndAndFixedIterators(t *testing.T) {
 	// Should be as big as smallest subiterator
 	size, accurate := and.Size()
 	if size != 3 {
-		t.Error("Incorrect size")
+		t.Error("Incorrect size:", size)
 	}
 	if !accurate {
 		t.Error("not accurate")
@@ -122,8 +122,8 @@ func TestNonOverlappingFixedIterators(t *testing.T) {
 
 func TestAllIterators(t *testing.T) {
 	ctx := context.TODO()
-	all1 := NewInt64(1, 5, true)
-	all2 := NewInt64(4, 10, true)
+	all1 := newInt64(1, 5, true)
+	all2 := newInt64(4, 10, true)
 	and := NewAnd(all2, all1)
 
 	if !and.Next(ctx) || and.Result().(Int64Node) != Int64Node(4) {
@@ -146,13 +146,13 @@ func TestAndIteratorErr(t *testing.T) {
 
 	and := NewAnd(
 		allErr,
-		NewInt64(1, 5, true),
+		newInt64(1, 5, true),
 	)
 
 	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")
+		t.Errorf("And iterator did not pass through underlying Err: %v", and.Err())
 	}
 }
diff --git a/graph/iterator/count_test.go b/graph/iterator/count_test.go
index 675af5c..648d6be 100644
--- a/graph/iterator/count_test.go
+++ b/graph/iterator/count_test.go
@@ -31,7 +31,7 @@ func TestCount(t *testing.T) {
 		graph.PreFetched(quad.String("b")),
 		graph.PreFetched(quad.String("d")),
 	)
-	it = NewCount(NewAnd(nil, fixed, fixed2), nil)
+	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))
diff --git a/graph/iterator/hasa_test.go b/graph/iterator/hasa_test.go
index 38224bd..8d902ab 100644
--- a/graph/iterator/hasa_test.go
+++ b/graph/iterator/hasa_test.go
@@ -21,6 +21,7 @@ import (
 
 	. "github.com/cayleygraph/cayley/graph/iterator"
 	"github.com/cayleygraph/cayley/quad"
+	"github.com/stretchr/testify/require"
 )
 
 func TestHasAIteratorErr(t *testing.T) {
@@ -31,10 +32,6 @@ func TestHasAIteratorErr(t *testing.T) {
 	// TODO(andrew-d): pass a non-nil quadstore
 	hasa := NewHasA(nil, errIt, quad.Subject)
 
-	if hasa.Next(ctx) != false {
-		t.Errorf("HasA iterator did not pass through initial 'false'")
-	}
-	if hasa.Err() != wantErr {
-		t.Errorf("HasA iterator did not pass through underlying Err")
-	}
+	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 0f3d144..05a0f9a 100644
--- a/graph/iterator/iterator_test.go
+++ b/graph/iterator/iterator_test.go
@@ -2,6 +2,7 @@ package iterator_test
 
 import (
 	"context"
+	"fmt"
 
 	"github.com/cayleygraph/cayley/graph"
 	. "github.com/cayleygraph/cayley/graph/iterator"
@@ -9,7 +10,7 @@ import (
 
 // A testing iterator that returns the given values for Next() and Err().
 type testIterator struct {
-	*Fixed
+	graph.Iterator
 
 	NextVal bool
 	ErrVal  error
@@ -17,9 +18,9 @@ type testIterator struct {
 
 func newTestIterator(next bool, err error) graph.Iterator {
 	return &testIterator{
-		Fixed:   NewFixed(),
-		NextVal: next,
-		ErrVal:  err,
+		Iterator: NewFixed(),
+		NextVal:  next,
+		ErrVal:   err,
 	}
 }
 
@@ -30,3 +31,128 @@ func (it *testIterator) Next(ctx context.Context) bool {
 func (it *testIterator) Err() error {
 	return it.ErrVal
 }
+
+type Int64Quad int64
+
+func (v Int64Quad) Key() interface{} { return v }
+
+func (Int64Quad) IsNode() bool { return false }
+
+var _ graph.Iterator = &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
+}
+
+// Creates a new Int64 with the given range.
+func newInt64(min, max int64, node bool) *Int64 {
+	return &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) Close() error {
+	return nil
+}
+
+func (it *Int64) TagResults(dst map[string]graph.Ref) {}
+
+func (it *Int64) 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
+	if it.at == -1 {
+		return false
+	}
+	val := it.at
+	it.at = it.at + 1
+	if it.at > it.max {
+		it.at = -1
+	}
+	it.result = val
+	return true
+}
+
+func (it *Int64) Err() error {
+	return nil
+}
+
+func (it *Int64) toValue(v int64) graph.Ref {
+	if it.node {
+		return Int64Node(v)
+	}
+	return Int64Quad(v)
+}
+
+func (it *Int64) Result() graph.Ref {
+	return it.toValue(it.result)
+}
+
+func (it *Int64) NextPath(ctx context.Context) bool {
+	return false
+}
+
+// No sub-iterators.
+func (it *Int64) SubIterators() []graph.Iterator {
+	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 valToInt64(v graph.Ref) int64 {
+	if v, ok := v.(Int64Node); ok {
+		return int64(v)
+	}
+	return int64(v.(Int64Quad))
+}
+
+// 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
+	v := valToInt64(tsv)
+	if it.min <= v && v <= it.max {
+		it.result = v
+		return true
+	}
+	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 7cf9519..f94aa6d 100644
--- a/graph/iterator/limit_test.go
+++ b/graph/iterator/limit_test.go
@@ -40,9 +40,21 @@ func TestLimitIteratorBasics(t *testing.T) {
 		t.Errorf("Failed to iterate Limit correctly: got:%v expected:%v", got, expect)
 	}
 
-	for _, v := range []int{1, 2, 3, 4, 5} {
+	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")
+	}
+	u.Reset()
+	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")
+	}
 }
diff --git a/graph/iterator/materialize_test.go b/graph/iterator/materialize_test.go
index 5326f14..44564ff 100644
--- a/graph/iterator/materialize_test.go
+++ b/graph/iterator/materialize_test.go
@@ -48,7 +48,7 @@ func TestMaterializeIteratorErrorAbort(t *testing.T) {
 	// underlying iterator is larger than our 'abort at' value, and then
 	// returns an error.
 	or := NewOr(
-		NewInt64(1, int64(MaterializeLimit+1), true),
+		newInt64(1, int64(MaterializeLimit+1), true),
 		errIt,
 	)
 
diff --git a/graph/iterator/or_test.go b/graph/iterator/or_test.go
index 1925d75..d0286fe 100644
--- a/graph/iterator/or_test.go
+++ b/graph/iterator/or_test.go
@@ -100,6 +100,7 @@ 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)
@@ -112,6 +113,7 @@ func TestShortCircuitingOrBasics(t *testing.T) {
 	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) {
@@ -130,6 +132,7 @@ func TestShortCircuitingOrBasics(t *testing.T) {
 	or = NewShortCircuitOr()
 	or.AddSubIterator(f1)
 	or.AddSubIterator(f2)
+	f2.Reset()
 	for _, v := range []int{2, 3, 21} {
 		if !or.Contains(ctx, Int64Node(v)) {
 			t.Errorf("Failed to correctly check %d as true", v)
@@ -145,6 +148,7 @@ func TestShortCircuitingOrBasics(t *testing.T) {
 	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) {
@@ -169,7 +173,7 @@ func TestOrIteratorErr(t *testing.T) {
 	or := NewOr(
 		fix1,
 		orErr,
-		NewInt64(1, 5, true),
+		newInt64(1, 5, true),
 	)
 
 	if !or.Next(ctx) {
@@ -194,7 +198,7 @@ func TestShortCircuitOrIteratorErr(t *testing.T) {
 
 	or := NewOr(
 		orErr,
-		NewInt64(1, 5, true),
+		newInt64(1, 5, true),
 	)
 
 	if or.Next(ctx) != false {
diff --git a/graph/iterator/query_shape_test.go b/graph/iterator/query_shape_test.go
index 2c892fe..afe4274 100644
--- a/graph/iterator/query_shape_test.go
+++ b/graph/iterator/query_shape_test.go
@@ -53,11 +53,11 @@ func TestQueryShape(t *testing.T) {
 
 	nodes := shape["nodes"].([]Node)
 	if len(nodes) != 3 {
-		t.Errorf("Failed to get correct number of nodes, got:%d expect:4", len(nodes))
+		t.Fatalf("Failed to get correct number of nodes, got:%d expect:3", len(nodes))
 	}
 	links := shape["links"].([]Link)
 	if len(nodes) != 3 {
-		t.Errorf("Failed to get correct number of links, got:%d expect:1", len(links))
+		t.Fatalf("Failed to get correct number of links, got:%d expect:1", len(links))
 	}
 
 	// Nodes should be correctly tagged.
diff --git a/graph/iterator/skip_test.go b/graph/iterator/skip_test.go
index a9aa019..a9fc169 100644
--- a/graph/iterator/skip_test.go
+++ b/graph/iterator/skip_test.go
@@ -40,9 +40,29 @@ func TestSkipIteratorBasics(t *testing.T) {
 		t.Errorf("Failed to iterate Skip correctly: got:%v expected:%v", got, expect)
 	}
 
-	for _, v := range []int{1, 2, 3, 4, 5} {
+	u.Reset()
+	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.")
+		}
+	}
+	for _, v := range []int{4, 5} {
+		if !u.Contains(ctx, Int64Node(v)) {
+			t.Errorf("Failed to find a correct value in the Skip iterator.")
+		}
+	}
+
+	u.Reset()
+	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.")
+		}
+	}
+	for _, v := range []int{1, 2} {
 		if !u.Contains(ctx, Int64Node(v)) {
 			t.Errorf("Failed to find a correct value in the Skip iterator.")
 		}
 	}
+
+	// TODO(dennwc): check with NextPath
 }
diff --git a/graph/memstore/quadstore_test.go b/graph/memstore/quadstore_test.go
index 1774572..9f1997b 100644
--- a/graph/memstore/quadstore_test.go
+++ b/graph/memstore/quadstore_test.go
@@ -134,9 +134,10 @@ func TestIteratorsAndNextResultOrderA(t *testing.T) {
 
 	all := qs.NodesAllIterator()
 
+	const allTag = "all"
 	innerAnd := iterator.NewAnd(
 		iterator.NewLinksTo(qs, fixed2, quad.Predicate),
-		iterator.NewLinksTo(qs, all, quad.Object),
+		iterator.NewLinksTo(qs, iterator.Tag(all, allTag), quad.Object),
 	)
 
 	hasa := iterator.NewHasA(qs, innerAnd, quad.Subject)
@@ -155,7 +156,9 @@ func TestIteratorsAndNextResultOrderA(t *testing.T) {
 		expect = []string{"B", "D"}
 	)
 	for {
-		got = append(got, quad.ToString(qs.NameOf(all.Result())))
+		m := make(map[string]graph.Ref, 1)
+		outerAnd.TagResults(m)
+		got = append(got, quad.ToString(qs.NameOf(m[allTag])))
 		if !outerAnd.NextPath(ctx) {
 			break
 		}