diff --git a/storage/app/app.go b/storage/app/app.go
index adcae63..08f97af 100644
--- a/storage/app/app.go
+++ b/storage/app/app.go
@@ -25,4 +25,5 @@
 func (a *App) RegisterOnMux(mux *http.ServeMux) {
 	// TODO(quentin): Should we just make the App itself be an http.Handler?
 	mux.HandleFunc("/upload", a.upload)
+	mux.HandleFunc("/search", a.search)
 }
diff --git a/storage/app/query.go b/storage/app/query.go
new file mode 100644
index 0000000..9e65397
--- /dev/null
+++ b/storage/app/query.go
@@ -0,0 +1,40 @@
+// Copyright 2017 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package app
+
+import (
+	"net/http"
+
+	"golang.org/x/perf/storage/benchfmt"
+)
+
+func (a *App) search(w http.ResponseWriter, r *http.Request) {
+	if err := r.ParseForm(); err != nil {
+		http.Error(w, err.Error(), 500)
+		return
+	}
+
+	q := r.Form.Get("q")
+	if q == "" {
+		http.Error(w, "missing q parameter", 400)
+		return
+	}
+
+	query := a.DB.Query(q)
+	defer query.Close()
+
+	w.Header().Set("Content-Type", "text/plain; charset=utf-8")
+	bw := benchfmt.NewPrinter(w)
+	for query.Next() {
+		if err := bw.Print(query.Result()); err != nil {
+			http.Error(w, err.Error(), 500)
+			return
+		}
+	}
+	if err := query.Err(); err != nil {
+		http.Error(w, err.Error(), 500)
+		return
+	}
+}
diff --git a/storage/app/upload.go b/storage/app/upload.go
index 8ecdad1..d556839 100644
--- a/storage/app/upload.go
+++ b/storage/app/upload.go
@@ -51,6 +51,7 @@
 		return
 	}
 
+	w.Header().Set("Content-Type", "application/json")
 	if err := json.NewEncoder(w).Encode(result); err != nil {
 		errorf(ctx, "%v", err)
 		http.Error(w, err.Error(), 500)
diff --git a/storage/appengine/app.yaml b/storage/appengine/app.yaml
index 50002ed..edc404e 100644
--- a/storage/appengine/app.yaml
+++ b/storage/appengine/app.yaml
@@ -12,7 +12,7 @@
 handlers:
 - url: /_ah/remote_api
   script: _go_app
-- url: /upload
+- url: /
   script: _go_app
   secure: always
 env_variables:
diff --git a/storage/db/db.go b/storage/db/db.go
index 5ab74cd..ac61a75 100644
--- a/storage/db/db.go
+++ b/storage/db/db.go
@@ -9,14 +9,19 @@
 import (
 	"bytes"
 	"database/sql"
+	"errors"
 	"fmt"
+	"io"
 	"strings"
 	"text/template"
+	"unicode"
 
 	"golang.org/x/net/context"
 	"golang.org/x/perf/storage/benchfmt"
 )
 
+// TODO(quentin): Add Context to every function when App Engine supports Go >=1.8.
+
 // DB is a high-level interface to a database for the storage
 // app. It's safe for concurrent use by multiple goroutines.
 type DB struct {
@@ -202,6 +207,157 @@
 	return nil
 }
 
+// Query searches for results matching the given query string.
+//
+// The query string is first parsed into quoted words (as in the shell)
+// and then each word must be formatted as one of the following:
+// key:value - exact match on label "key" = "value"
+// key>value - value greater than (useful for dates)
+// key<value - value less than (also useful for dates)
+func (db *DB) Query(q string) *Query {
+	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++ {
+		if i > 0 {
+			query += " INNER JOIN "
+		}
+		query += fmt.Sprintf("(SELECT UploadID, RecordID FROM RecordLabels WHERE Name = ? AND Value = ?) t%d", i)
+		if i > 0 {
+			query += " USING (UploadID, RecordID)"
+		}
+	}
+
+	// TODO(quentin): Handle empty query string.
+
+	query += " LEFT JOIN Records r USING (UploadID, RecordID)"
+
+	rows, err := db.sql.Query(query, args...)
+	if err != nil {
+		return &Query{err: err}
+	}
+	return &Query{rows: rows}
+}
+
+// splitQueryWords splits q into words using shell syntax (whitespace
+// can be escaped with double quotes or with a backslash).
+func splitQueryWords(q string) []string {
+	var words []string
+	word := make([]byte, len(q))
+	w := 0
+	quoting := false
+	for r := 0; r < len(q); r++ {
+		switch c := q[r]; {
+		case c == '"' && quoting:
+			quoting = false
+		case quoting:
+			if c == '\\' {
+				r++
+			}
+			if r < len(q) {
+				word[w] = q[r]
+				w++
+			}
+		case c == '"':
+			quoting = true
+		case c == ' ', c == '\t':
+			if w > 0 {
+				words = append(words, string(word[:w]))
+			}
+			w = 0
+		case c == '\\':
+			r++
+			fallthrough
+		default:
+			if r < len(q) {
+				word[w] = q[r]
+				w++
+			}
+		}
+	}
+	if w > 0 {
+		words = append(words, string(word[:w]))
+	}
+	return words
+}
+
+// Query is the result of a query.
+// Use Next to advance through the rows, making sure to call Close when done:
+//
+//   q, err := db.Query("key:value")
+//   defer q.Close()
+//   for q.Next() {
+//     res := q.Result()
+//     ...
+//   }
+//   err = q.Err() // get any error encountered during iteration
+//   ...
+type Query struct {
+	rows *sql.Rows
+	// from last call to Next
+	result *benchfmt.Result
+	err    error
+}
+
+// Next prepares the next result for reading with the Result
+// method. It returns false when there are no more results, either by
+// reaching the end of the input or an error.
+func (q *Query) Next() bool {
+	if q.err != nil {
+		return false
+	}
+	if !q.rows.Next() {
+		return false
+	}
+	var content []byte
+	q.err = q.rows.Scan(&content)
+	if q.err != nil {
+		return false
+	}
+	// TODO(quentin): Needs to change when one row contains multiple Results.
+	q.result, q.err = benchfmt.NewReader(bytes.NewReader(content)).Next()
+	return q.err == nil
+}
+
+// Result returns the most recent result generated by a call to Next.
+func (q *Query) Result() *benchfmt.Result {
+	return q.result
+}
+
+// Err returns the error state of the query.
+func (q *Query) Err() error {
+	if q.err == io.EOF {
+		return nil
+	}
+	return q.err
+}
+
+// Close frees resources associated with the query.
+func (q *Query) Close() error {
+	if q.rows != nil {
+		return q.rows.Close()
+	}
+	return q.err
+}
+
 // Close closes the database connections, releasing any open resources.
 func (db *DB) Close() error {
 	if err := db.insertUpload.Close(); err != nil {
diff --git a/storage/db/db_test.go b/storage/db/db_test.go
index 6c7b681..84845a4 100644
--- a/storage/db/db_test.go
+++ b/storage/db/db_test.go
@@ -6,6 +6,8 @@
 
 import (
 	"context"
+	"fmt"
+	"reflect"
 	"strings"
 	"testing"
 
@@ -16,6 +18,24 @@
 
 // Most of the db package is tested via the end-to-end-tests in perf/storage/app.
 
+func TestSplitQueryWords(t *testing.T) {
+	for _, test := range []struct {
+		q    string
+		want []string
+	}{
+		{"hello world", []string{"hello", "world"}},
+		{"hello\\ world", []string{"hello world"}},
+		{`"key:value two" and\ more`, []string{"key:value two", "and more"}},
+		{`one" two"\ three four`, []string{"one two three", "four"}},
+		{`"4'7\""`, []string{`4'7"`}},
+	} {
+		have := SplitQueryWords(test.q)
+		if !reflect.DeepEqual(have, test.want) {
+			t.Errorf("splitQueryWords(%q) = %+v, want %+v", test.q, have, test.want)
+		}
+	}
+}
+
 // TestNewUpload verifies that NewUpload and InsertRecord wrote the correct rows to the database.
 func TestNewUpload(t *testing.T) {
 	db, err := OpenSQL("sqlite3", ":memory:")
@@ -82,3 +102,72 @@
 		t.Errorf("rows.Err: %v", err)
 	}
 }
+
+func TestQuery(t *testing.T) {
+	db, err := OpenSQL("sqlite3", ":memory:")
+	if err != nil {
+		t.Fatalf("open database: %v", err)
+	}
+	defer db.Close()
+
+	u, err := db.NewUpload(context.Background())
+	if err != nil {
+		t.Fatalf("NewUpload: %v", err)
+	}
+
+	for i := 0; i < 1024; 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))
+		}
+		r.NameLabels["name"] = "Name"
+		if err := u.InsertRecord(r); err != nil {
+			t.Fatalf("InsertRecord: %v", err)
+		}
+	}
+
+	tests := []struct {
+		q    string
+		want []int // nil means we want an error
+	}{
+		{"label0:0", []int{0}},
+		{"label1:0", []int{0, 1}},
+		{"label0:5 name:Name", []int{5}},
+		{"label0:0 label0:5", []int{}},
+		{"bogus query", nil},
+	}
+	for _, test := range tests {
+		t.Run("query="+test.q, func(t *testing.T) {
+			q := db.Query(test.q)
+			if test.want == nil {
+				if q.Next() {
+					t.Fatal("Next() = true, want false")
+				}
+				if err := q.Err(); err == nil {
+					t.Fatal("Err() = nil, want error")
+				}
+				return
+			}
+			defer func() {
+				if err := q.Close(); err != nil {
+					t.Errorf("Close: %v", err)
+				}
+			}()
+			for i, num := range test.want {
+				if !q.Next() {
+					t.Fatalf("#%d: Next() = false", i)
+				}
+				r := q.Result()
+				if r.Labels["label0"] != fmt.Sprintf("%d", num) {
+					t.Errorf("result[%d].label0 = %q, want %d", i, r.Labels["label0"], num)
+				}
+				if r.NameLabels["name"] != "Name" {
+					t.Errorf("result[%d].name = %q, want %q", i, r.NameLabels["name"], "Name")
+				}
+			}
+			if err := q.Err(); err != nil {
+				t.Errorf("Err() = %v, want nil", err)
+			}
+		})
+	}
+}