diff --git a/storage/db/db.go b/storage/db/db.go
index 35b696f..c0aef58 100644
--- a/storage/db/db.go
+++ b/storage/db/db.go
@@ -9,7 +9,6 @@
 import (
 	"bytes"
 	"database/sql"
-	"errors"
 	"fmt"
 	"io"
 	"regexp"
@@ -369,37 +368,44 @@
 	qparts := splitQueryWords(q)
 
 	var args []interface{}
-Words:
-	for _, part := range qparts {
-		for i, c := range part {
-			switch {
-			case c == ':':
-				args = append(args, part[:i], part[i+1:])
-				continue Words
-			case c == '>' || c == '<':
-				// TODO
-				return &Query{err: errors.New("unsupported operator")}
-			case unicode.IsSpace(c) || unicode.IsUpper(c):
-				return &Query{err: fmt.Errorf("query part %q has invalid key", part)}
-			}
-		}
-		return &Query{err: fmt.Errorf("query part %q is missing operator", part)}
-	}
-
 	query := "SELECT r.Content FROM "
-	for i := 0; i < len(args)/2; i++ {
+	for i, part := range qparts {
 		if i > 0 {
 			query += " INNER JOIN "
 		}
-		query += fmt.Sprintf("(SELECT UploadID, RecordID FROM RecordLabels WHERE Name = ? AND Value = ?) t%d", i)
+		sepIndex := strings.IndexFunc(part, func(r rune) bool {
+			return r == ':' || r == '>' || r == '<' || unicode.IsSpace(r) || unicode.IsUpper(r)
+		})
+		if sepIndex < 0 {
+			return &Query{err: fmt.Errorf("query part %q is missing operator", part)}
+		}
+		key, sep, value := part[:sepIndex], part[sepIndex], part[sepIndex+1:]
+		switch sep {
+		case ':':
+			if value == "" {
+				// TODO(quentin): Implement support for searching for missing labels.
+				return &Query{err: fmt.Errorf("missing value for query part %q", part)}
+			}
+			query += fmt.Sprintf("(SELECT UploadID, RecordID FROM RecordLabels WHERE Name = ? AND Value = ?) t%d", i)
+			args = append(args, key, value)
+		case '>', '<':
+			query += fmt.Sprintf("(SELECT UploadID, RecordID FROM RecordLabels WHERE Name = ? AND Value %c ?) t%d", sep, i)
+			args = append(args, key, value)
+		default:
+			return &Query{err: fmt.Errorf("query part %q has invalid key", part)}
+		}
 		if i > 0 {
 			query += " USING (UploadID, RecordID)"
 		}
 	}
 
-	// TODO(quentin): Handle empty query string.
-
-	query += " LEFT JOIN Records r USING (UploadID, RecordID)"
+	if len(qparts) > 0 {
+		query += " LEFT JOIN"
+	}
+	query += " Records r"
+	if len(qparts) > 0 {
+		query += " USING (UploadID, RecordID)"
+	}
 
 	rows, err := db.sql.Query(query, args...)
 	if err != nil {
diff --git a/storage/db/db_test.go b/storage/db/db_test.go
index 154f4b1..046622e 100644
--- a/storage/db/db_test.go
+++ b/storage/db/db_test.go
@@ -263,7 +263,10 @@
 		t.Fatalf("NewUpload: %v", err)
 	}
 
+	var allRecords []int
+
 	for i := 0; i < 1024; i++ {
+		allRecords = append(allRecords, i)
 		r := &benchfmt.Result{Labels: make(map[string]string), NameLabels: make(map[string]string), Content: "BenchmarkName 1 ns/op"}
 		for j := uint(0); j < 10; j++ {
 			r.Labels[fmt.Sprintf("label%d", j)] = fmt.Sprintf("%d", i/(1<<j))
@@ -286,6 +289,9 @@
 		{"label0:5 name:Name", []int{5}},
 		{"label0:0 label0:5", []int{}},
 		{"bogus query", nil},
+		{"label1<2 label3:0", []int{0, 1, 2, 3}},
+		{"label1>510", []int{1022, 1023}},
+		{"", allRecords},
 	}
 	for _, test := range tests {
 		t.Run("query="+test.q, func(t *testing.T) {