diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
index 816123a..3f17a61 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
@@ -1013,20 +1013,51 @@
 	}
 }
 
-// Returns true if the predicate is satisfied by the given span.
-func (pred *predicateData) satisfiedBy(span *common.Span) bool {
+type satisfiedByReturn int
+
+const (
+	NOT_SATISFIED satisfiedByReturn = iota
+	NOT_YET_SATISFIED = iota
+	SATISFIED = iota
+)
+
+// Determine whether the predicate is satisfied by the given span.
+func (pred *predicateData) satisfiedBy(span *common.Span) satisfiedByReturn {
 	val := pred.extractRelevantSpanData(span)
 	switch pred.Op {
 	case common.CONTAINS:
-		return bytes.Contains(val, pred.key)
+		if bytes.Contains(val, pred.key) {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.EQUALS:
-		return bytes.Equal(val, pred.key)
+		if bytes.Equal(val, pred.key) {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.LESS_THAN_OR_EQUALS:
-		return bytes.Compare(val, pred.key) <= 0
+		if bytes.Compare(val, pred.key) <= 0 {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.GREATER_THAN_OR_EQUALS:
-		return bytes.Compare(val, pred.key) >= 0
+		if bytes.Compare(val, pred.key) >= 0 {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.GREATER_THAN:
-		return bytes.Compare(val, pred.key) > 0
+		cmp := bytes.Compare(val, pred.key)
+		if cmp < 0 {
+			return NOT_SATISFIED
+		} else if cmp == 0 {
+			return NOT_YET_SATISFIED
+		} else {
+			return SATISFIED
+		}
 	default:
 		panic(fmt.Sprintf("unknown Op type %s should have been caught "+
 			"during normalization", pred.Op))
@@ -1176,25 +1207,6 @@
 	return src, nil
 }
 
-// Return true if this operation may require skipping the first result we get back from leveldb.
-func mayRequireOneSkip(op common.Op) bool {
-	switch op {
-	// When dealing with descending predicates, the first span we read might not satisfy
-	// the predicate, even though subsequent ones will.  This is because the iter.Seek()
-	// function "moves the iterator the position of the key given or, if the key doesn't
-	// exist, the next key that does exist in the database."  So if we're on that "next
-	// key" it will not satisfy the predicate, but the keys previous to it might.
-	case common.LESS_THAN_OR_EQUALS:
-		return true
-	// iter.Seek basically takes us to the key which is "greater than or equal to" some
-	// value.  Since we want greater than (not greater than or equal to) we may have to
-	// skip the first key.
-	case common.GREATER_THAN:
-		return true
-	}
-	return false
-}
-
 // Fill in the entry in the 'next' array for a specific shard.
 func (src *source) populateNextFromShard(shardIdx int) {
 	lg := src.store.lg
@@ -1253,20 +1265,18 @@
 		} else {
 			iter.Next()
 		}
-		if src.pred.satisfiedBy(span) {
-			lg.Debugf("Populated valid span %v from shard %s.\n", sid, shdPath)
+		ret := src.pred.satisfiedBy(span)
+		switch ret {
+		case NOT_SATISFIED:
+			break // This and subsequent entries don't satisfy predicate
+		case SATISFIED:
+			if lg.DebugEnabled() {
+				lg.Debugf("Populated valid span %v from shard %s.\n", sid, shdPath)
+			}
 			src.nexts[shardIdx] = span // Found valid entry
 			return
-		} else {
-			if lg.DebugEnabled() {
-				lg.Debugf("Span %s from shard %s does not satisfy the predicate.\n",
-					sid.String(), shdPath)
-			}
-			if src.numRead[shardIdx] <= 1 && mayRequireOneSkip(src.pred.Op) {
-				continue
-			}
-			// This and subsequent entries don't satisfy predicate
-			break
+		case NOT_YET_SATISFIED:
+			continue // try again
 		}
 	}
 	lg.Debugf("Closing iterator for shard %s.\n", shdPath)
@@ -1361,7 +1371,7 @@
 		}
 		satisfied := true
 		for predIdx := range preds {
-			if !preds[predIdx].satisfiedBy(span) {
+			if preds[predIdx].satisfiedBy(span) != SATISFIED {
 				satisfied = false
 				break
 			}
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
index b13112b..05fabfd 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
@@ -330,6 +330,68 @@
 	}, []common.Span{SIMPLE_TEST_SPANS[2]})
 }
 
+var TEST_QUERIES5_SPANS []common.Span = []common.Span{
+	common.Span{Id: common.TestId("10000000000000000000000000000001"),
+		SpanData: common.SpanData{
+			Begin:       123,
+			End:         456,
+			Description: "span1",
+			Parents:     []common.SpanId{},
+			TracerId:    "myTracer",
+		}},
+	common.Span{Id: common.TestId("10000000000000000000000000000002"),
+		SpanData: common.SpanData{
+			Begin:       123,
+			End:         200,
+			Description: "span2",
+			Parents:     []common.SpanId{common.TestId("10000000000000000000000000000001")},
+			TracerId:    "myTracer",
+		}},
+	common.Span{Id: common.TestId("10000000000000000000000000000003"),
+		SpanData: common.SpanData{
+			Begin:       124,
+			End:         457,
+			Description: "span3",
+			Parents:     []common.SpanId{common.TestId("10000000000000000000000000000001")},
+			TracerId:    "myTracer",
+		}},
+}
+
+func TestQueries5(t *testing.T) {
+	t.Parallel()
+	htraceBld := &MiniHTracedBuilder{Name: "TestQueries5",
+		WrittenSpans: common.NewSemaphore(0),
+		DataDirs: make([]string, 1),
+	}
+	ht, err := htraceBld.Build()
+	if err != nil {
+		panic(err)
+	}
+	defer ht.Close()
+	createSpans(TEST_QUERIES5_SPANS, ht.Store)
+
+	testQuery(t, ht, &common.Query{
+		Predicates: []common.Predicate{
+			common.Predicate{
+				Op:    common.GREATER_THAN,
+				Field: common.BEGIN_TIME,
+				Val:   "123",
+			},
+		},
+		Lim: 5,
+	}, []common.Span{TEST_QUERIES5_SPANS[2]})
+	testQuery(t, ht, &common.Query{
+		Predicates: []common.Predicate{
+			common.Predicate{
+				Op:    common.GREATER_THAN,
+				Field: common.END_TIME,
+				Val:   "200",
+			},
+		},
+		Lim: 500,
+	}, []common.Span{TEST_QUERIES5_SPANS[0], TEST_QUERIES5_SPANS[2]})
+}
+
 func BenchmarkDatastoreWrites(b *testing.B) {
 	htraceBld := &MiniHTracedBuilder{Name: "BenchmarkDatastoreWrites",
 		Cnf: map[string]string{