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 3f17a61..2a3d65c 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
@@ -1228,12 +1228,20 @@
 		}
 		src.numRead[shardIdx]++
 		key := iter.Key()
-		if !bytes.HasPrefix(key, []byte{src.keyPrefix}) {
-			if lg.DebugEnabled() {
-				lg.Debugf("Can't populate: Iterator for shard %s does not have prefix %s\n",
-					shdPath, string(src.keyPrefix))
-			}
+		if len(key) < 1 {
+			lg.Warnf("Encountered invalid zero-byte key in shard %s.\n", shdPath)
+			break
+		}
+		ret := src.checkKeyPrefix(key[0], iter)
+		if ret == NOT_SATISFIED {
 			break // Can't read past end of indexed section
+		} else if ret == NOT_YET_SATISFIED {
+			if src.pred.Op.IsDescending() {
+				iter.Prev()
+			} else {
+				iter.Next()
+			}
+			continue // Try again because we are not yet at the indexed section.
 		}
 		var span *common.Span
 		var sid common.SpanId
@@ -1265,7 +1273,7 @@
 		} else {
 			iter.Next()
 		}
-		ret := src.pred.satisfiedBy(span)
+		ret = src.pred.satisfiedBy(span)
 		switch ret {
 		case NOT_SATISFIED:
 			break // This and subsequent entries don't satisfy predicate
@@ -1284,6 +1292,26 @@
 	src.iters[shardIdx] = nil
 }
 
+// Check the key prefix against the key prefix of the query.
+func (src *source) checkKeyPrefix(kp byte, iter *levigo.Iterator) satisfiedByReturn {
+	if kp == src.keyPrefix {
+		return SATISFIED
+	} else if kp < src.keyPrefix {
+		if src.pred.Op.IsDescending() {
+			return NOT_SATISFIED
+		} else {
+			return NOT_YET_SATISFIED
+		}
+	} else {
+		if src.pred.Op.IsDescending() {
+			return NOT_YET_SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
+	}
+}
+
+
 func (src *source) next() *common.Span {
 	for shardIdx := range src.shards {
 		src.populateNextFromShard(shardIdx)
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 05fabfd..4fc400a 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
@@ -390,6 +390,20 @@
 		},
 		Lim: 500,
 	}, []common.Span{TEST_QUERIES5_SPANS[0], TEST_QUERIES5_SPANS[2]})
+
+	testQuery(t, ht, &common.Query{
+		Predicates: []common.Predicate{
+			common.Predicate{
+				Op:    common.LESS_THAN_OR_EQUALS,
+				Field: common.END_TIME,
+				Val:   "999",
+			},
+		},
+		Lim: 500,
+	}, []common.Span{TEST_QUERIES5_SPANS[2],
+		TEST_QUERIES5_SPANS[0],
+		TEST_QUERIES5_SPANS[1],
+	})
 }
 
 func BenchmarkDatastoreWrites(b *testing.B) {