diff --git a/storage/db/db.go b/storage/db/db.go
index 5f46634..9cb7745 100644
--- a/storage/db/db.go
+++ b/storage/db/db.go
@@ -155,7 +155,7 @@
 
 // An Upload is a collection of files that share an upload ID.
 type Upload struct {
-	// ID is the value of the "uploadid" key that should be
+	// ID is the value of the "upload" key that should be
 	// associated with every record in this upload.
 	ID string
 
diff --git a/storage/db/db_test.go b/storage/db/db_test.go
index 4206100..6101098 100644
--- a/storage/db/db_test.go
+++ b/storage/db/db_test.go
@@ -250,6 +250,7 @@
 	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"}
+		r.Labels["upload"] = u.ID
 		for j := uint(0); j < 10; j++ {
 			r.Labels[fmt.Sprintf("label%d", j)] = fmt.Sprintf("%d", i/(1<<j))
 		}
@@ -280,6 +281,11 @@
 		{"", allRecords},
 		{"missing>", []int{}},
 		{"label0>", allRecords},
+		{"upload:" + u.ID, allRecords},
+		{"upload:none", []int{}},
+		{"upload>" + u.ID, []int{}},
+		{"upload<" + u.ID, []int{}},
+		{"label0:0 upload:" + u.ID, []int{0}},
 	}
 	for _, test := range tests {
 		t.Run("query="+test.q, func(t *testing.T) {
diff --git a/storage/db/query.go b/storage/db/query.go
index aeaaaca..fea7cfb 100644
--- a/storage/db/query.go
+++ b/storage/db/query.go
@@ -133,6 +133,18 @@
 
 // sql returns a SQL expression and a list of arguments for finding records matching p.
 func (p part) sql() (sql string, args []interface{}, err error) {
+	if p.key == "upload" {
+		switch p.operator {
+		case equals:
+			return "SELECT UploadID, RecordID FROM Records WHERE UploadID = ?", []interface{}{p.value}, nil
+		case lt:
+			return "SELECT UploadID, RecordID FROM Records WHERE UploadID < ?", []interface{}{p.value}, nil
+		case gt:
+			return "SELECT UploadID, RecordID FROM Records WHERE UploadID > ?", []interface{}{p.value}, nil
+		case ltgt:
+			return "SELECT UploadID, RecordID FROM Records WHERE UploadID < ? AND UploadID > ?", []interface{}{p.value, p.value2}, nil
+		}
+	}
 	switch p.operator {
 	case equals:
 		if p.value == "" {