Repository: prometheus/prometheus
Pull request #7009 (2020-03-19 12:39:52)

Merge release-2.17 into master
So that master can also benefit from all the sweet bug fixes.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 2f8745c22..5dcfcadfc 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,28 @@
+## 2.17.0-rc.3 / 2020-03-18
+
+This release implements isolation in TSDB. API queries and recording rules are
+guaranteed to only see full scrapes and full recording rules. This comes with a
+certain overhead in resource usage. Depending on the situation, there might be
+some increase in memory usage, CPU usage, or query latency.
+
+* [FEATURE] TSDB: Support isolation #6841
+* [ENHANCEMENT] PromQL: Allow more keywords as metric names #6933
+* [ENHANCEMENT] React UI: Add normalization of localhost URLs in targets page #6794
+* [ENHANCEMENT] Remote read: Read from remote storage concurrently #6770
+* [ENHANCEMENT] Rules: Mark deleted rule series as stale after a reload #6745
+* [ENHANCEMENT] Scrape: Log scrape append failures as debug rather than warn #6852
+* [ENHANCEMENT] TSDB: Improve query performance for queries that partially hit the head #6676
+* [ENHANCEMENT] Consul SD: Expose service health as meta label #5313
+* [ENHANCEMENT] EC2 SD: Expose EC2 instance lifecycle as meta label #6914
+* [ENHANCEMENT] Kubernetes SD: Expose service type as meta label for K8s service role #6684
+* [ENHANCEMENT] Kubernetes SD: Expose label_selector and field_selector #6807
+* [ENHANCEMENT] Openstack SD: Expose hypervisor id as meta label #6962
+* [BUGFIX] PromQL: Do not escape HTML-like chars in query log #6834 #6795
+* [BUGFIX] React UI: Fix data table matrix values #6896
+* [BUGFIX] React UI: Fix new targets page not loading when using non-ASCII characters #6892
+* [BUGFIX] Scrape: Prevent removal of metric names upon relabeling #6891
+* [BUGFIX] Scrape: Fix 'superfluous response.WriteHeader call' errors when scrape fails under some circonstances #6986
+
 ## 2.16.0 / 2020-02-13
 
 * [FEATURE] React UI: Support local timezone on /graph #6692
diff --git a/VERSION b/VERSION
index 752490696..9dba67016 100644
--- a/VERSION
+++ b/VERSION
@@ -1,1 +1,1 @@
-2.16.0
+2.17.0-rc.3
diff --git a/cmd/prometheus/main.go b/cmd/prometheus/main.go
index 1a4635122..05d1fbd96 100644
--- a/cmd/prometheus/main.go
+++ b/cmd/prometheus/main.go
@@ -618,6 +618,7 @@ func main() {
 			func() error {
 				select {
 				case <-dbOpen:
+					break
 				// In case a shutdown is initiated before the dbOpen is released
 				case <-cancel:
 					reloadReady.Close()
diff --git a/go.mod b/go.mod
index 1d02853c3..437c7c5af 100644
--- a/go.mod
+++ b/go.mod
@@ -33,7 +33,7 @@ require (
 	github.com/opentracing/opentracing-go v1.1.0
 	github.com/pkg/errors v0.9.1
 	github.com/prometheus/alertmanager v0.20.0
-	github.com/prometheus/client_golang v1.5.0
+	github.com/prometheus/client_golang v1.5.1
 	github.com/prometheus/client_model v0.2.0
 	github.com/prometheus/common v0.9.1
 	github.com/samuel/go-zookeeper v0.0.0-20190923202752-2cc03de413da
diff --git a/go.sum b/go.sum
index 3412ca796..efd013974 100644
--- a/go.sum
+++ b/go.sum
@@ -459,8 +459,8 @@ github.com/prometheus/client_golang v0.9.3-0.20190127221311-3c4408c8b829/go.mod
 github.com/prometheus/client_golang v1.0.0/go.mod h1:db9x61etRT2tGnBNRi70OPL5FsnadC4Ky3P0J6CfImo=
 github.com/prometheus/client_golang v1.2.1/go.mod h1:XMU6Z2MjaRKVu/dC1qupJI9SiNkDYzz3xecMgSW/F+U=
 github.com/prometheus/client_golang v1.3.0/go.mod h1:hJaj2vgQTGQmVCsAACORcieXFeDPbaTKGT+JTgUa3og=
-github.com/prometheus/client_golang v1.5.0 h1:Ctq0iGpCmr3jeP77kbF2UxgvRwzWWz+4Bh9/vJTyg1A=
-github.com/prometheus/client_golang v1.5.0/go.mod h1:e9GMxYsXl05ICDXkRhurwBS4Q3OK1iX/F2sw+iXX5zU=
+github.com/prometheus/client_golang v1.5.1 h1:bdHYieyGlH+6OLEk2YQha8THib30KP0/yD0YH9m6xcA=
+github.com/prometheus/client_golang v1.5.1/go.mod h1:e9GMxYsXl05ICDXkRhurwBS4Q3OK1iX/F2sw+iXX5zU=
 github.com/prometheus/client_model v0.0.0-20180712105110-5c3871d89910/go.mod h1:MbSGuTsp3dbXC40dX6PRTWyKYBIrTGTE9sqQNg2J8bo=
 github.com/prometheus/client_model v0.0.0-20190115171406-56726106282f/go.mod h1:MbSGuTsp3dbXC40dX6PRTWyKYBIrTGTE9sqQNg2J8bo=
 github.com/prometheus/client_model v0.0.0-20190129233127-fd36f4220a90/go.mod h1:xMI15A0UPsDsEKsMN9yxemIoYk6Tm2C1GtYGdfGttqA=
diff --git a/promql/engine.go b/promql/engine.go
index 2e8c568fc..ba52501b4 100644
--- a/promql/engine.go
+++ b/promql/engine.go
@@ -502,15 +502,16 @@ func durationMilliseconds(d time.Duration) int64 {
 // execEvalStmt evaluates the expression of an evaluation statement for the given time range.
 func (ng *Engine) execEvalStmt(ctx context.Context, query *query, s *parser.EvalStmt) (parser.Value, storage.Warnings, error) {
 	prepareSpanTimer, ctxPrepare := query.stats.GetSpanTimer(ctx, stats.QueryPreparationTime, ng.metrics.queryPrepareTime)
-	querier, warnings, err := ng.populateSeries(ctxPrepare, query.queryable, s)
-	prepareSpanTimer.Finish()
-
-	// XXX(fabxc): the querier returned by populateSeries might be instantiated
-	// we must not return without closing irrespective of the error.
-	// TODO: make this semantically saner.
-	if querier != nil {
-		defer querier.Close()
+	mint := ng.findMinTime(s)
+	querier, err := query.queryable.Querier(ctxPrepare, timestamp.FromTime(mint), timestamp.FromTime(s.End))
+	if err != nil {
+		prepareSpanTimer.Finish()
+		return nil, nil, err
 	}
+	defer querier.Close()
+
+	warnings, err := ng.populateSeries(ctxPrepare, querier, s)
+	prepareSpanTimer.Finish()
 
 	if err != nil {
 		return nil, warnings, err
@@ -616,7 +617,7 @@ func (ng *Engine) cumulativeSubqueryOffset(path []parser.Node) time.Duration {
 	return subqOffset
 }
 
-func (ng *Engine) populateSeries(ctx context.Context, q storage.Queryable, s *parser.EvalStmt) (storage.Querier, storage.Warnings, error) {
+func (ng *Engine) findMinTime(s *parser.EvalStmt) time.Time {
 	var maxOffset time.Duration
 	parser.Inspect(s.Expr, func(node parser.Node, path []parser.Node) error {
 		subqOffset := ng.cumulativeSubqueryOffset(path)
@@ -638,25 +639,23 @@ func (ng *Engine) populateSeries(ctx context.Context, q storage.Queryable, s *pa
 		}
 		return nil
 	})
+	return s.Start.Add(-maxOffset)
+}
 
-	mint := s.Start.Add(-maxOffset)
-
-	querier, err := q.Querier(ctx, timestamp.FromTime(mint), timestamp.FromTime(s.End))
-	if err != nil {
-		return nil, nil, err
-	}
-
-	var warnings storage.Warnings
-
-	// Whenever a MatrixSelector is evaluated this variable is set to the corresponding range.
-	// The evaluation of the VectorSelector inside then evaluates the given range and unsets
-	// the variable.
-	var evalRange time.Duration
+func (ng *Engine) populateSeries(ctx context.Context, querier storage.Querier, s *parser.EvalStmt) (storage.Warnings, error) {
+	var (
+		// Whenever a MatrixSelector is evaluated, evalRange is set to the corresponding range.
+		// The evaluation of the VectorSelector inside then evaluates the given range and unsets
+		// the variable.
+		evalRange time.Duration
+		warnings  storage.Warnings
+		err       error
+	)
 
 	parser.Inspect(s.Expr, func(node parser.Node, path []parser.Node) error {
 		var set storage.SeriesSet
 		var wrn storage.Warnings
-		hints := &storage.SelectHints{
+		params := &storage.SelectParams{
 			Start: timestamp.FromTime(s.Start),
 			End:   timestamp.FromTime(s.End),
 			Step:  durationToInt64Millis(s.Interval),
@@ -668,29 +667,29 @@ func (ng *Engine) populateSeries(ctx context.Context, q storage.Queryable, s *pa
 		// from end also.
 		subqOffset := ng.cumulativeSubqueryOffset(path)
 		offsetMilliseconds := durationMilliseconds(subqOffset)
-		hints.Start = hints.Start - offsetMilliseconds
+		params.Start = params.Start - offsetMilliseconds
 
 		switch n := node.(type) {
 		case *parser.VectorSelector:
 			if evalRange == 0 {
-				hints.Start = hints.Start - durationMilliseconds(ng.lookbackDelta)
+				params.Start = params.Start - durationMilliseconds(ng.lookbackDelta)
 			} else {
-				hints.Range = durationMilliseconds(evalRange)
+				params.Range = durationMilliseconds(evalRange)
 				// For all matrix queries we want to ensure that we have (end-start) + range selected
 				// this way we have `range` data before the start time
-				hints.Start = hints.Start - durationMilliseconds(evalRange)
+				params.Start = params.Start - durationMilliseconds(evalRange)
 				evalRange = 0
 			}
 
-			hints.Func = extractFuncFromPath(path)
-			hints.By, hints.Grouping = extractGroupsFromPath(path)
+			params.Func = extractFuncFromPath(path)
+			params.By, params.Grouping = extractGroupsFromPath(path)
 			if n.Offset > 0 {
 				offsetMilliseconds := durationMilliseconds(n.Offset)
-				hints.Start = hints.Start - offsetMilliseconds
-				hints.End = hints.End - offsetMilliseconds
+				params.Start = params.Start - offsetMilliseconds
+				params.End = params.End - offsetMilliseconds
 			}
 
-			set, wrn, err = querier.Select(false, hints, n.LabelMatchers...)
+			set, wrn, err = querier.Select(params, n.LabelMatchers...)
 			warnings = append(warnings, wrn...)
 			if err != nil {
 				level.Error(ng.logger).Log("msg", "error selecting series set", "err", err)
@@ -703,7 +702,7 @@ func (ng *Engine) populateSeries(ctx context.Context, q storage.Queryable, s *pa
 		}
 		return nil
 	})
-	return querier, warnings, err
+	return warnings, err
 }
 
 // extractFuncFromPath walks up the path and searches for the first instance of
diff --git a/promql/parser/parse.go b/promql/parser/parse.go
index 1b6d8a930..79424dd98 100644
--- a/promql/parser/parse.go
+++ b/promql/parser/parse.go
@@ -242,11 +242,6 @@ func (p *parser) addParseErr(positionRange PositionRange, err error) {
 func (p *parser) unexpected(context string, expected string) {
 	var errMsg strings.Builder
 
-	// Do not report lexer errors twice
-	if p.yyParser.lval.item.Typ == ERROR {
-		return
-	}
-
 	errMsg.WriteString("unexpected ")
 	errMsg.WriteString(p.yyParser.lval.item.desc())
 
@@ -307,15 +302,10 @@ func (p *parser) Lex(lval *yySymType) int {
 	}
 
 	switch typ {
-	case ERROR:
-		pos := PositionRange{
-			Start: p.lex.start,
-			End:   Pos(len(p.lex.input)),
-		}
-		p.addParseErr(pos, errors.New(p.yyParser.lval.item.Val))
 
-		// Tells yacc that this is the end of input.
-		return 0
+	case ERROR:
+		p.addParseErrf(lval.item.PositionRange(), "%s", lval.item.Val)
+		p.InjectItem(0)
 	case EOF:
 		lval.item.Typ = EOF
 		p.InjectItem(0)
diff --git a/rules/manager.go b/rules/manager.go
index b777c9a01..425fb01a8 100644
--- a/rules/manager.go
+++ b/rules/manager.go
@@ -590,9 +590,16 @@ func (g *Group) Eval(ctx context.Context, ts time.Time) {
 
 			app := g.opts.Appendable.Appender()
 			seriesReturned := make(map[string]labels.Labels, len(g.seriesInPreviousEval[i]))
+			defer func() {
+				if err := app.Commit(); err != nil {
+					level.Warn(g.logger).Log("msg", "rule sample appending failed", "err", err)
+					return
+				}
+				g.seriesInPreviousEval[i] = seriesReturned
+			}()
 			for _, s := range vector {
 				if _, err := app.Add(s.Metric, s.T, s.V); err != nil {
-					switch err {
+					switch errors.Cause(err) {
 					case storage.ErrOutOfOrderSample:
 						numOutOfOrder++
 						level.Debug(g.logger).Log("msg", "Rule evaluation result discarded", "err", err, "sample", s)
@@ -617,7 +624,7 @@ func (g *Group) Eval(ctx context.Context, ts time.Time) {
 				if _, ok := seriesReturned[metric]; !ok {
 					// Series no longer exposed, mark it stale.
 					_, err = app.Add(lset, timestamp.FromTime(ts), math.Float64frombits(value.StaleNaN))
-					switch err {
+					switch errors.Cause(err) {
 					case nil:
 					case storage.ErrOutOfOrderSample, storage.ErrDuplicateSampleForTimestamp:
 						// Do not count these in logging, as this is expected if series
@@ -627,11 +634,6 @@ func (g *Group) Eval(ctx context.Context, ts time.Time) {
 					}
 				}
 			}
-			if err := app.Commit(); err != nil {
-				level.Warn(g.logger).Log("msg", "rule sample appending failed", "err", err)
-			} else {
-				g.seriesInPreviousEval[i] = seriesReturned
-			}
 		}(i, rule)
 	}
 	g.cleanupStaleSeries(ts)
@@ -645,7 +647,7 @@ func (g *Group) cleanupStaleSeries(ts time.Time) {
 	for _, s := range g.staleSeries {
 		// Rule that produced series no longer configured, mark it stale.
 		_, err := app.Add(s, timestamp.FromTime(ts), math.Float64frombits(value.StaleNaN))
-		switch err {
+		switch errors.Cause(err) {
 		case nil:
 		case storage.ErrOutOfOrderSample, storage.ErrDuplicateSampleForTimestamp:
 			// Do not count these in logging, as this is expected if series
@@ -705,7 +707,7 @@ func (g *Group) RestoreForState(ts time.Time) {
 				matchers = append(matchers, mt)
 			}
 
-			sset, err, _ := q.Select(false, nil, matchers...)
+			sset, err, _ := q.Select(nil, matchers...)
 			if err != nil {
 				level.Error(g.logger).Log("msg", "Failed to restore 'for' state",
 					labels.AlertName, alertRule.Name(), "stage", "Select", "err", err)
diff --git a/scrape/scrape.go b/scrape/scrape.go
index e0077e9fa..fbabba247 100644
--- a/scrape/scrape.go
+++ b/scrape/scrape.go
@@ -1069,6 +1069,19 @@ func (sl *scrapeLoop) append(b []byte, contentType string, ts time.Time) (total,
 	)
 	var sampleLimitErr error
 
+	defer func() {
+		if err != nil {
+			app.Rollback()
+			return
+		}
+		if err = app.Commit(); err != nil {
+			return
+		}
+		// Only perform cache cleaning if the scrape was not empty.
+		// An empty scrape (usually) is used to indicate a failed scrape.
+		sl.cache.iterDone(len(b) > 0)
+	}()
+
 loop:
 	for {
 		var et textparse.Entry
@@ -1108,7 +1121,7 @@ loop:
 		}
 		ce, ok := sl.cache.get(yoloString(met))
 		if ok {
-			switch err = app.AddFast(ce.ref, t, v); err {
+			switch err = app.AddFast(ce.ref, t, v); errors.Cause(err) {
 			case nil:
 				if tp == nil {
 					sl.cache.trackStaleness(ce.hash, ce.lset)
@@ -1163,7 +1176,7 @@ loop:
 
 			var ref uint64
 			ref, err = app.Add(lset, t, v)
-			switch err {
+			switch errors.Cause(err) {
 			case nil:
 			case storage.ErrOutOfOrderSample:
 				err = nil
@@ -1220,7 +1233,7 @@ loop:
 		sl.cache.forEachStale(func(lset labels.Labels) bool {
 			// Series no longer exposed, mark it stale.
 			_, err = app.Add(lset, defTime, math.Float64frombits(value.StaleNaN))
-			switch err {
+			switch errors.Cause(err) {
 			case storage.ErrOutOfOrderSample, storage.ErrDuplicateSampleForTimestamp:
 				// Do not count these in logging, as this is expected if a target
 				// goes away and comes back again with a new scrape loop.
@@ -1229,19 +1242,7 @@ loop:
 			return err == nil
 		})
 	}
-	if err != nil {
-		app.Rollback()
-		return total, added, seriesAdded, err
-	}
-	if err := app.Commit(); err != nil {
-		return total, added, seriesAdded, err
-	}
-
-	// Only perform cache cleaning if the scrape was not empty.
-	// An empty scrape (usually) is used to indicate a failed scrape.
-	sl.cache.iterDone(len(b) > 0)
-
-	return total, added, seriesAdded, nil
+	return
 }
 
 func yoloString(b []byte) string {
@@ -1258,74 +1259,78 @@ const (
 	scrapeSeriesAddedMetricName  = "scrape_series_added" + "\xff"
 )
 
-func (sl *scrapeLoop) report(start time.Time, duration time.Duration, scraped, appended, seriesAdded int, err error) error {
-	sl.scraper.Report(start, duration, err)
+func (sl *scrapeLoop) report(start time.Time, duration time.Duration, scraped, appended, seriesAdded int, scrapeErr error) (err error) {
+	sl.scraper.Report(start, duration, scrapeErr)
 
 	ts := timestamp.FromTime(start)
 
 	var health float64
-	if err == nil {
+	if scrapeErr == nil {
 		health = 1
 	}
 	app := sl.appender()
+	defer func() {
+		if err != nil {
+			app.Rollback()
+			return
+		}
+		err = app.Commit()
+	}()
 
-	if err := sl.addReportSample(app, scrapeHealthMetricName, ts, health); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeHealthMetricName, ts, health); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeDurationMetricName, ts, duration.Seconds()); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeDurationMetricName, ts, duration.Seconds()); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeSamplesMetricName, ts, float64(scraped)); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeSamplesMetricName, ts, float64(scraped)); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, samplesPostRelabelMetricName, ts, float64(appended)); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, samplesPostRelabelMetricName, ts, float64(appended)); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeSeriesAddedMetricName, ts, float64(seriesAdded)); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeSeriesAddedMetricName, ts, float64(seriesAdded)); err != nil {
+		return
 	}
-	return app.Commit()
+	return
 }
 
-func (sl *scrapeLoop) reportStale(start time.Time) error {
+func (sl *scrapeLoop) reportStale(start time.Time) (err error) {
 	ts := timestamp.FromTime(start)
 	app := sl.appender()
+	defer func() {
+		if err != nil {
+			app.Rollback()
+			return
+		}
+		err = app.Commit()
+	}()
 
 	stale := math.Float64frombits(value.StaleNaN)
 
-	if err := sl.addReportSample(app, scrapeHealthMetricName, ts, stale); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeHealthMetricName, ts, stale); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeDurationMetricName, ts, stale); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeDurationMetricName, ts, stale); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeSamplesMetricName, ts, stale); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeSamplesMetricName, ts, stale); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, samplesPostRelabelMetricName, ts, stale); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, samplesPostRelabelMetricName, ts, stale); err != nil {
+		return
 	}
-	if err := sl.addReportSample(app, scrapeSeriesAddedMetricName, ts, stale); err != nil {
-		app.Rollback()
-		return err
+	if err = sl.addReportSample(app, scrapeSeriesAddedMetricName, ts, stale); err != nil {
+		return
 	}
-	return app.Commit()
+	return
 }
 
 func (sl *scrapeLoop) addReportSample(app storage.Appender, s string, t int64, v float64) error {
 	ce, ok := sl.cache.get(s)
 	if ok {
 		err := app.AddFast(ce.ref, t, v)
-		switch err {
+		switch errors.Cause(err) {
 		case nil:
 			return nil
 		case storage.ErrNotFound:
@@ -1349,7 +1354,7 @@ func (sl *scrapeLoop) addReportSample(app storage.Appender, s string, t int64, v
 	lset = sl.reportSampleMutator(lset)
 
 	ref, err := app.Add(lset, t, v)
-	switch err {
+	switch errors.Cause(err) {
 	case nil:
 		sl.cache.addRef(s, ref, lset, hash)
 		return nil
diff --git a/storage/fanout.go b/storage/fanout.go
index 4646aae2d..f55f4c8dc 100644
--- a/storage/fanout.go
+++ b/storage/fanout.go
@@ -221,16 +221,20 @@ func NewMergeQuerier(primaryQuerier Querier, queriers []Querier) Querier {
 }
 
 // Select returns a set of series that matches the given label matchers.
-func (q *mergeQuerier) Select(sortSeries bool, hints *SelectHints, matchers ...*labels.Matcher) (SeriesSet, Warnings, error) {
-	if len(q.queriers) == 1 {
-		return q.queriers[0].Select(sortSeries, hints, matchers...)
+func (q *mergeQuerier) Select(params *SelectParams, matchers ...*labels.Matcher) (SeriesSet, Warnings, error) {
+	if len(q.queriers) != 1 {
+		// We need to sort for NewMergeSeriesSet to work.
+		return q.SelectSorted(params, matchers...)
 	}
+	return q.queriers[0].Select(params, matchers...)
+}
+
+// SelectSorted returns a set of sorted series that matches the given label matchers.
+func (q *mergeQuerier) SelectSorted(params *SelectParams, matchers ...*labels.Matcher) (SeriesSet, Warnings, error) {
+	seriesSets := make([]SeriesSet, 0, len(q.queriers))
+	var warnings Warnings
 
-	var (
-		seriesSets = make([]SeriesSet, 0, len(q.queriers))
-		warnings   Warnings
-		priErr     error
-	)
+	var priErr error = nil
 	type queryResult struct {
 		qr          Querier
 		set         SeriesSet
@@ -238,11 +242,9 @@ func (q *mergeQuerier) Select(sortSeries bool, hints *SelectHints, matchers ...*
 		selectError error
 	}
 	queryResultChan := make(chan *queryResult)
-
 	for _, querier := range q.queriers {
 		go func(qr Querier) {
-			// We need to sort for NewMergeSeriesSet to work.
-			set, wrn, err := qr.Select(true, hints, matchers...)
+			set, wrn, err := qr.SelectSorted(params, matchers...)
 			queryResultChan <- &queryResult{qr: qr, set: set, wrn: wrn, selectError: err}
 		}(querier)
 	}
@@ -260,6 +262,7 @@ func (q *mergeQuerier) Select(sortSeries bool, hints *SelectHints, matchers ...*
 			} else {
 				priErr = qryResult.selectError
 			}
+			continue
 		}
 		seriesSets = append(seriesSets, qryResult.set)
 	}
diff --git a/storage/interface.go b/storage/interface.go
index 4ac799ebb..e85a159e4 100644
--- a/storage/interface.go
+++ b/storage/interface.go
@@ -60,9 +60,10 @@ type Queryable interface {
 // time range.
 type Querier interface {
 	// Select returns a set of series that matches the given label matchers.
-	// Caller can specify if it requires returned series to be sorted. Prefer not requiring sorting for better performance.
-	// It allows passing hints that can help in optimising select, but it's up to implementation how this is used if used at all.
-	Select(sortSeries bool, hints *SelectHints, matchers ...*labels.Matcher) (SeriesSet, Warnings, error)
+	Select(*SelectParams, ...*labels.Matcher) (SeriesSet, Warnings, error)
+
+	// SelectSorted returns a sorted set of series that matches the given label matchers.
+	SelectSorted(*SelectParams, ...*labels.Matcher) (SeriesSet, Warnings, error)
 
 	// LabelValues returns all potential values for a label name.
 	// It is not safe to use the strings beyond the lifefime of the querier.
@@ -75,9 +76,8 @@ type Querier interface {
 	Close() error
 }
 
-// SelectHints specifies hints passed for data selections.
-// This is used only as an option for implementation to use.
-type SelectHints struct {
+// SelectParams specifies parameters passed to data selections.
+type SelectParams struct {
 	Start int64 // Start time in milliseconds for this select.
 	End   int64 // End time in milliseconds for this select.
 
diff --git a/storage/noop.go b/storage/noop.go
index 4c0383233..a8be634fd 100644
--- a/storage/noop.go
+++ b/storage/noop.go
@@ -24,7 +24,11 @@ func NoopQuerier() Querier {
 	return noopQuerier{}
 }
 
-func (noopQuerier) Select(bool, *SelectHints, ...*labels.Matcher) (SeriesSet, Warnings, error) {
+func (noopQuerier) Select(*SelectParams, ...*labels.Matcher) (SeriesSet, Warnings, error) {
+	return NoopSeriesSet(), nil, nil
+}
+
+func (noopQuerier) SelectSorted(*SelectParams, ...*labels.Matcher) (SeriesSet, Warnings, error) {
 	return NoopSeriesSet(), nil, nil
 }
 
diff --git a/storage/remote/codec.go b/storage/remote/codec.go
index 3b6556a12..8f07eb0d1 100644
--- a/storage/remote/codec.go
+++ b/storage/remote/codec.go
@@ -79,22 +79,22 @@ func EncodeReadResponse(resp *prompb.ReadResponse, w http.ResponseWriter) error
 }
 
 // ToQuery builds a Query proto.
-func ToQuery(from, to int64, matchers []*labels.Matcher, hints *storage.SelectHints) (*prompb.Query, error) {
+func ToQuery(from, to int64, matchers []*labels.Matcher, p *storage.SelectParams) (*prompb.Query, error) {
 	ms, err := toLabelMatchers(matchers)
 	if err != nil {
 		return nil, err
 	}
 
 	var rp *prompb.ReadHints
-	if hints != nil {
+	if p != nil {
 		rp = &prompb.ReadHints{
-			StartMs:  hints.Start,
-			EndMs:    hints.End,
-			StepMs:   hints.Step,
-			Func:     hints.Func,
-			Grouping: hints.Grouping,
-			By:       hints.By,
-			RangeMs:  hints.Range,
+			StepMs:   p.Step,
+			Func:     p.Func,
+			StartMs:  p.Start,
+			EndMs:    p.End,
+			Grouping: p.Grouping,
+			By:       p.By,
+			RangeMs:  p.Range,
 		}
 	}
 
@@ -145,7 +145,7 @@ func ToQueryResult(ss storage.SeriesSet, sampleLimit int) (*prompb.QueryResult,
 }
 
 // FromQueryResult unpacks and sorts a QueryResult proto.
-func FromQueryResult(sortSeries bool, res *prompb.QueryResult) storage.SeriesSet {
+func FromQueryResult(res *prompb.QueryResult) storage.SeriesSet {
 	series := make([]storage.Series, 0, len(res.Timeseries))
 	for _, ts := range res.Timeseries {
 		labels := labelProtosToLabels(ts.Labels)
@@ -158,10 +158,7 @@ func FromQueryResult(sortSeries bool, res *prompb.QueryResult) storage.SeriesSet
 			samples: ts.Samples,
 		})
 	}
-
-	if sortSeries {
-		sort.Sort(byLabel(series))
-	}
+	sort.Sort(byLabel(series))
 	return &concreteSeriesSet{
 		series: series,
 	}
diff --git a/storage/remote/read.go b/storage/remote/read.go
index b03bb8869..3e5c9573c 100644
--- a/storage/remote/read.go
+++ b/storage/remote/read.go
@@ -57,9 +57,16 @@ type querier struct {
 	client     *Client
 }
 
-// Select implements storage.Querier and uses the given matchers to read series sets from the Client.
-func (q *querier) Select(sortSeries bool, hints *storage.SelectHints, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
-	query, err := ToQuery(q.mint, q.maxt, matchers, hints)
+// Select implements storage.Querier and uses the given matchers to read series
+// sets from the Client.
+func (q *querier) Select(p *storage.SelectParams, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return q.SelectSorted(p, matchers...)
+}
+
+// SelectSorted implements storage.Querier and uses the given matchers to read series
+// sets from the Client.
+func (q *querier) SelectSorted(p *storage.SelectParams, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	query, err := ToQuery(q.mint, q.maxt, matchers, p)
 	if err != nil {
 		return nil, nil, err
 	}
@@ -73,11 +80,12 @@ func (q *querier) Select(sortSeries bool, hints *storage.SelectHints, matchers .
 		return nil, nil, fmt.Errorf("remote_read: %v", err)
 	}
 
-	return FromQueryResult(sortSeries, res), nil, nil
+	// FromQueryResult sorts.
+	return FromQueryResult(res), nil, nil
 }
 
 // LabelValues implements storage.Querier and is a noop.
-func (q *querier) LabelValues(string) ([]string, storage.Warnings, error) {
+func (q *querier) LabelValues(name string) ([]string, storage.Warnings, error) {
 	// TODO implement?
 	return nil, nil, nil
 }
@@ -116,9 +124,9 @@ type externalLabelsQuerier struct {
 // Select adds equality matchers for all external labels to the list of matchers
 // before calling the wrapped storage.Queryable. The added external labels are
 // removed from the returned series sets.
-func (q externalLabelsQuerier) Select(sortSeries bool, hints *storage.SelectHints, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q externalLabelsQuerier) Select(p *storage.SelectParams, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	m, added := q.addExternalLabels(matchers)
-	s, warnings, err := q.Querier.Select(sortSeries, hints, m...)
+	s, warnings, err := q.Querier.Select(p, m...)
 	if err != nil {
 		return nil, warnings, err
 	}
@@ -169,7 +177,7 @@ type requiredMatchersQuerier struct {
 
 // Select returns a NoopSeriesSet if the given matchers don't match the label
 // set of the requiredMatchersQuerier. Otherwise it'll call the wrapped querier.
-func (q requiredMatchersQuerier) Select(sortSeries bool, hints *storage.SelectHints, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q requiredMatchersQuerier) Select(p *storage.SelectParams, matchers ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	ms := q.requiredMatchers
 	for _, m := range matchers {
 		for i, r := range ms {
@@ -185,7 +193,7 @@ func (q requiredMatchersQuerier) Select(sortSeries bool, hints *storage.SelectHi
 	if len(ms) > 0 {
 		return storage.NoopSeriesSet(), nil, nil
 	}
-	return q.Querier.Select(sortSeries, hints, matchers...)
+	return q.Querier.Select(p, matchers...)
 }
 
 // addExternalLabels adds matchers for each external label. External labels
diff --git a/tsdb/block.go b/tsdb/block.go
index 536940ec9..bcdec5c88 100644
--- a/tsdb/block.go
+++ b/tsdb/block.go
@@ -77,7 +77,7 @@ type IndexReader interface {
 
 	// Series populates the given labels and chunk metas for the series identified
 	// by the reference.
-	// Returns ErrNotFound if the ref does not resolve to a known series.
+	// Returns storage.ErrNotFound if the ref does not resolve to a known series.
 	Series(ref uint64, lset *labels.Labels, chks *[]chunks.Meta) error
 
 	// LabelNames returns all the unique label names present in the index in sorted order.
diff --git a/tsdb/cmd/tsdb/main.go b/tsdb/cmd/tsdb/main.go
index 1d9229c2f..458ed5351 100644
--- a/tsdb/cmd/tsdb/main.go
+++ b/tsdb/cmd/tsdb/main.go
@@ -34,6 +34,7 @@ import (
 	"github.com/go-kit/kit/log"
 	"github.com/pkg/errors"
 	"github.com/prometheus/prometheus/pkg/labels"
+	"github.com/prometheus/prometheus/storage"
 	"github.com/prometheus/prometheus/tsdb"
 	"github.com/prometheus/prometheus/tsdb/chunks"
 	tsdb_errors "github.com/prometheus/prometheus/tsdb/errors"
@@ -309,7 +310,7 @@ func (b *writeBenchmark) ingestScrapesShard(lbls []labels.Labels, scrapeCount in
 				s.ref = &ref
 			} else if err := app.AddFast(*s.ref, ts, float64(s.value)); err != nil {
 
-				if errors.Cause(err) != tsdb.ErrNotFound {
+				if errors.Cause(err) != storage.ErrNotFound {
 					panic(err)
 				}
 
@@ -616,7 +617,7 @@ func dumpSamples(db *tsdb.DBReadOnly, mint, maxt int64) (err error) {
 		err = merr.Err()
 	}()
 
-	ss, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchRegexp, "", ".*"))
+	ss, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchRegexp, "", ".*"))
 	if err != nil {
 		return err
 	}
diff --git a/tsdb/head.go b/tsdb/head.go
index 0de043000..bbdfead9d 100644
--- a/tsdb/head.go
+++ b/tsdb/head.go
@@ -39,21 +39,6 @@ import (
 )
 
 var (
-	// ErrNotFound is returned if a looked up resource was not found.
-	ErrNotFound = errors.Errorf("not found")
-
-	// ErrOutOfOrderSample is returned if an appended sample has a
-	// timestamp smaller than the most recent sample.
-	ErrOutOfOrderSample = errors.New("out of order sample")
-
-	// ErrAmendSample is returned if an appended sample has the same timestamp
-	// as the most recent sample but a different value.
-	ErrAmendSample = errors.New("amending sample")
-
-	// ErrOutOfBounds is returned if an appended sample is out of the
-	// writable time range.
-	ErrOutOfBounds = errors.New("out of bounds")
-
 	// ErrInvalidSample is returned if an appended sample is not valid and can't
 	// be ingested.
 	ErrInvalidSample = errors.New("invalid sample")
@@ -841,7 +826,7 @@ func (a *initAppender) Add(lset labels.Labels, t int64, v float64) (uint64, erro
 
 func (a *initAppender) AddFast(ref uint64, t int64, v float64) error {
 	if a.app == nil {
-		return ErrNotFound
+		return storage.ErrNotFound
 	}
 	return a.app.AddFast(ref, t, v)
 }
@@ -954,7 +939,7 @@ type headAppender struct {
 
 func (a *headAppender) Add(lset labels.Labels, t int64, v float64) (uint64, error) {
 	if t < a.minValidTime {
-		return 0, ErrOutOfBounds
+		return 0, storage.ErrOutOfBounds
 	}
 
 	// Ensure no empty labels have gotten through.
@@ -980,12 +965,12 @@ func (a *headAppender) Add(lset labels.Labels, t int64, v float64) (uint64, erro
 
 func (a *headAppender) AddFast(ref uint64, t int64, v float64) error {
 	if t < a.minValidTime {
-		return ErrOutOfBounds
+		return storage.ErrOutOfBounds
 	}
 
 	s := a.head.series.getByID(ref)
 	if s == nil {
-		return errors.Wrap(ErrNotFound, "unknown series")
+		return errors.Wrap(storage.ErrNotFound, "unknown series")
 	}
 	s.Lock()
 	if err := s.appendable(t, v); err != nil {
@@ -1079,7 +1064,10 @@ func (a *headAppender) Commit() error {
 }
 
 func (a *headAppender) Rollback() error {
-	a.head.metrics.activeAppenders.Dec()
+	defer a.head.metrics.activeAppenders.Dec()
+	defer a.head.iso.closeAppend(a.appendID)
+	defer a.head.putSeriesBuffer(a.sampleSeries)
+
 	var series *memSeries
 	for i := range a.samples {
 		series = a.sampleSeries[i]
@@ -1090,8 +1078,6 @@ func (a *headAppender) Rollback() error {
 	}
 	a.head.putAppendBuffer(a.samples)
 	a.samples = nil
-	a.head.putSeriesBuffer(a.sampleSeries)
-	a.head.iso.closeAppend(a.appendID)
 
 	// Series are created in the head memory regardless of rollback. Thus we have
 	// to log them to the WAL in any case.
@@ -1115,7 +1101,9 @@ func (h *Head) Delete(mint, maxt int64, ms ...*labels.Matcher) error {
 	for p.Next() {
 		series := h.series.getByID(p.At())
 
+		series.RLock()
 		t0, t1 := series.minTime(), series.maxTime()
+		series.RUnlock()
 		if t0 == math.MinInt64 || t1 == math.MinInt64 {
 			continue
 		}
@@ -1315,7 +1303,7 @@ func (h *headChunkReader) Chunk(ref uint64) (chunkenc.Chunk, error) {
 	s := h.head.series.getByID(sid)
 	// This means that the series has been garbage collected.
 	if s == nil {
-		return nil, ErrNotFound
+		return nil, storage.ErrNotFound
 	}
 
 	s.Lock()
@@ -1325,7 +1313,7 @@ func (h *headChunkReader) Chunk(ref uint64) (chunkenc.Chunk, error) {
 	// the specified range.
 	if c == nil || !c.OverlapsClosedInterval(h.mint, h.maxt) {
 		s.Unlock()
-		return nil, ErrNotFound
+		return nil, storage.ErrNotFound
 	}
 	s.Unlock()
 
@@ -1423,9 +1411,11 @@ func (h *headIndexReader) Postings(name string, values ...string) (index.Posting
 				level.Debug(h.head.logger).Log("msg", "looked up series not found")
 				continue
 			}
+			s.RLock()
 			if s.minTime() <= h.maxt && s.maxTime() >= h.mint {
 				filtered = append(filtered, p.At())
 			}
+			s.RUnlock()
 		}
 		if p.Err() != nil {
 			return nil, p.Err()
@@ -1469,7 +1459,7 @@ func (h *headIndexReader) Series(ref uint64, lbls *labels.Labels, chks *[]chunks
 
 	if s == nil {
 		h.head.metrics.seriesNotFound.Inc()
-		return ErrNotFound
+		return storage.ErrNotFound
 	}
 	*lbls = append((*lbls)[:0], s.lset...)
 
@@ -1732,7 +1722,7 @@ func (s sample) V() float64 {
 // memSeries is the in-memory representation of a series. None of its methods
 // are goroutine safe and it is the caller's responsibility to lock it.
 type memSeries struct {
-	sync.Mutex
+	sync.RWMutex
 
 	ref          uint64
 	lset         labels.Labels
@@ -1813,12 +1803,12 @@ func (s *memSeries) appendable(t int64, v float64) error {
 		return nil
 	}
 	if t < c.maxTime {
-		return ErrOutOfOrderSample
+		return storage.ErrOutOfOrderSample
 	}
 	// We are allowing exact duplicates as we can encounter them in valid cases
 	// like federation and erroring out at that time would be extremely noisy.
 	if math.Float64bits(s.sampleBuf[3].v) != math.Float64bits(v) {
-		return ErrAmendSample
+		return storage.ErrDuplicateSampleForTimestamp
 	}
 	return nil
 }
diff --git a/tsdb/querier.go b/tsdb/querier.go
index 2a64d57ea..83f7b6ad6 100644
--- a/tsdb/querier.go
+++ b/tsdb/querier.go
@@ -85,21 +85,23 @@ func (q *querier) lvals(qs []storage.Querier, n string) ([]string, storage.Warni
 	return mergeStrings(s1, s2), ws, nil
 }
 
-func (q *querier) Select(sortSeries bool, hints *storage.SelectHints, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q *querier) Select(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	if len(q.blocks) != 1 {
+		return q.SelectSorted(p, ms...)
+	}
+	// Sorting Head series is slow, and unneeded when only the
+	// Head is being queried. Sorting blocks is a noop.
+	return q.blocks[0].Select(p, ms...)
+}
+
+func (q *querier) SelectSorted(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	if len(q.blocks) == 0 {
 		return storage.EmptySeriesSet(), nil, nil
 	}
-	if len(q.blocks) == 1 {
-		// Sorting Head series is slow, and unneeded when only the
-		// Head is being queried.
-		return q.blocks[0].Select(sortSeries, hints, ms...)
-	}
-
 	ss := make([]storage.SeriesSet, len(q.blocks))
 	var ws storage.Warnings
 	for i, b := range q.blocks {
-		// We have to sort if blocks > 1 as MergedSeriesSet requires it.
-		s, w, err := b.Select(true, hints, ms...)
+		s, w, err := b.SelectSorted(p, ms...)
 		ws = append(ws, w...)
 		if err != nil {
 			return nil, ws, err
@@ -125,26 +127,30 @@ type verticalQuerier struct {
 	querier
 }
 
-func (q *verticalQuerier) Select(sortSeries bool, hints *storage.SelectHints, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
-	return q.sel(sortSeries, hints, q.blocks, ms)
+func (q *verticalQuerier) Select(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return q.sel(p, q.blocks, ms)
+}
+
+func (q *verticalQuerier) SelectSorted(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return q.sel(p, q.blocks, ms)
 }
 
-func (q *verticalQuerier) sel(sortSeries bool, hints *storage.SelectHints, qs []storage.Querier, ms []*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q *verticalQuerier) sel(p *storage.SelectParams, qs []storage.Querier, ms []*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	if len(qs) == 0 {
 		return storage.EmptySeriesSet(), nil, nil
 	}
 	if len(qs) == 1 {
-		return qs[0].Select(sortSeries, hints, ms...)
+		return qs[0].SelectSorted(p, ms...)
 	}
 	l := len(qs) / 2
 
 	var ws storage.Warnings
-	a, w, err := q.sel(sortSeries, hints, qs[:l], ms)
+	a, w, err := q.sel(p, qs[:l], ms)
 	ws = append(ws, w...)
 	if err != nil {
 		return nil, ws, err
 	}
-	b, w, err := q.sel(sortSeries, hints, qs[l:], ms)
+	b, w, err := q.sel(p, qs[l:], ms)
 	ws = append(ws, w...)
 	if err != nil {
 		return nil, ws, err
@@ -189,24 +195,42 @@ type blockQuerier struct {
 	mint, maxt int64
 }
 
-func (q *blockQuerier) Select(sortSeries bool, hints *storage.SelectHints, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
-	var base storage.ChunkSeriesSet
-	var err error
+func (q *blockQuerier) Select(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	base, err := LookupChunkSeries(q.index, q.tombstones, ms...)
+	if err != nil {
+		return nil, nil, err
+	}
 
-	if sortSeries {
-		base, err = LookupChunkSeriesSorted(q.index, q.tombstones, ms...)
-	} else {
-		base, err = LookupChunkSeries(q.index, q.tombstones, ms...)
+	mint := q.mint
+	maxt := q.maxt
+	if p != nil {
+		mint = p.Start
+		maxt = p.End
 	}
+	return &blockSeriesSet{
+		set: &populatedChunkSeries{
+			set:    base,
+			chunks: q.chunks,
+			mint:   mint,
+			maxt:   maxt,
+		},
+
+		mint: mint,
+		maxt: maxt,
+	}, nil, nil
+}
+
+func (q *blockQuerier) SelectSorted(p *storage.SelectParams, ms ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	base, err := LookupChunkSeriesSorted(q.index, q.tombstones, ms...)
 	if err != nil {
 		return nil, nil, err
 	}
 
 	mint := q.mint
 	maxt := q.maxt
-	if hints != nil {
-		mint = hints.Start
-		maxt = hints.End
+	if p != nil {
+		mint = p.Start
+		maxt = p.End
 	}
 	return &blockSeriesSet{
 		set: &populatedChunkSeries{
@@ -715,7 +739,7 @@ func (s *baseChunkSeries) Next() bool {
 		ref := s.p.At()
 		if err := s.index.Series(ref, &lset, &chkMetas); err != nil {
 			// Postings may be stale. Skip if no underlying series exists.
-			if errors.Cause(err) == ErrNotFound {
+			if errors.Cause(err) == storage.ErrNotFound {
 				continue
 			}
 			s.err = err
@@ -795,7 +819,7 @@ func (s *populatedChunkSeries) Next() bool {
 			c.Chunk, s.err = s.chunks.Chunk(c.Ref)
 			if s.err != nil {
 				// This means that the chunk has be garbage collected. Remove it from the list.
-				if s.err == ErrNotFound {
+				if s.err == storage.ErrNotFound {
 					s.err = nil
 					// Delete in-place.
 					s.chks = append(chks[:j], chks[j+1:]...)
diff --git a/tsdb/wal/checkpoint.go b/tsdb/wal/checkpoint.go
index d205c6121..6b0ecd54f 100644
--- a/tsdb/wal/checkpoint.go
+++ b/tsdb/wal/checkpoint.go
@@ -21,7 +21,6 @@ import (
 	"math"
 	"os"
 	"path/filepath"
-	"sort"
 	"strconv"
 	"strings"
 
@@ -45,32 +44,46 @@ type CheckpointStats struct {
 // LastCheckpoint returns the directory name and index of the most recent checkpoint.
 // If dir does not contain any checkpoints, ErrNotFound is returned.
 func LastCheckpoint(dir string) (string, int, error) {
-	checkpoints, err := listCheckpoints(dir)
+	files, err := ioutil.ReadDir(dir)
 	if err != nil {
 		return "", 0, err
 	}
+	// Traverse list backwards since there may be multiple checkpoints left.
+	for i := len(files) - 1; i >= 0; i-- {
+		fi := files[i]
 
-	if len(checkpoints) == 0 {
-		return "", 0, record.ErrNotFound
+		if !strings.HasPrefix(fi.Name(), checkpointPrefix) {
+			continue
+		}
+		if !fi.IsDir() {
+			return "", 0, errors.Errorf("checkpoint %s is not a directory", fi.Name())
+		}
+		idx, err := strconv.Atoi(fi.Name()[len(checkpointPrefix):])
+		if err != nil {
+			continue
+		}
+		return filepath.Join(dir, fi.Name()), idx, nil
 	}
-
-	checkpoint := checkpoints[len(checkpoints)-1]
-	return filepath.Join(dir, checkpoint.name), checkpoint.index, nil
+	return "", 0, record.ErrNotFound
 }
 
 // DeleteCheckpoints deletes all checkpoints in a directory below a given index.
 func DeleteCheckpoints(dir string, maxIndex int) error {
-	checkpoints, err := listCheckpoints(dir)
+	var errs tsdb_errors.MultiError
+
+	files, err := ioutil.ReadDir(dir)
 	if err != nil {
 		return err
 	}
-
-	var errs tsdb_errors.MultiError
-	for _, checkpoint := range checkpoints {
-		if checkpoint.index >= maxIndex {
-			break
+	for _, fi := range files {
+		if !strings.HasPrefix(fi.Name(), checkpointPrefix) {
+			continue
+		}
+		index, err := strconv.Atoi(fi.Name()[len(checkpointPrefix):])
+		if err != nil || index >= maxIndex {
+			continue
 		}
-		if err := os.RemoveAll(filepath.Join(dir, checkpoint.name)); err != nil {
+		if err := os.RemoveAll(filepath.Join(dir, fi.Name())); err != nil {
 			errs.Add(err)
 		}
 	}
@@ -117,7 +130,7 @@ func Checkpoint(w *WAL, from, to int, keep func(id uint64) bool, mint int64) (*C
 		defer sgmReader.Close()
 	}
 
-	cpdir := checkpointDir(w.Dir(), to)
+	cpdir := filepath.Join(w.Dir(), fmt.Sprintf(checkpointPrefix+"%06d", to))
 	cpdirtmp := cpdir + ".tmp"
 
 	if err := os.RemoveAll(cpdirtmp); err != nil {
@@ -251,41 +264,3 @@ func Checkpoint(w *WAL, from, to int, keep func(id uint64) bool, mint int64) (*C
 
 	return stats, nil
 }
-
-func checkpointDir(dir string, i int) string {
-	return filepath.Join(dir, fmt.Sprintf(checkpointPrefix+"%08d", i))
-}
-
-type checkpointRef struct {
-	name  string
-	index int
-}
-
-func listCheckpoints(dir string) (refs []checkpointRef, err error) {
-	files, err := ioutil.ReadDir(dir)
-	if err != nil {
-		return nil, err
-	}
-
-	for i := 0; i < len(files); i++ {
-		fi := files[i]
-		if !strings.HasPrefix(fi.Name(), checkpointPrefix) {
-			continue
-		}
-		if !fi.IsDir() {
-			return nil, errors.Errorf("checkpoint %s is not a directory", fi.Name())
-		}
-		idx, err := strconv.Atoi(fi.Name()[len(checkpointPrefix):])
-		if err != nil {
-			continue
-		}
-
-		refs = append(refs, checkpointRef{name: fi.Name(), index: idx})
-	}
-
-	sort.Slice(refs, func(i, j int) bool {
-		return refs[i].index < refs[j].index
-	})
-
-	return refs, nil
-}
diff --git a/vendor/github.com/prometheus/client_golang/prometheus/promhttp/delegator.go b/vendor/github.com/prometheus/client_golang/prometheus/promhttp/delegator.go
index d1354b101..5070e72e2 100644
--- a/vendor/github.com/prometheus/client_golang/prometheus/promhttp/delegator.go
+++ b/vendor/github.com/prometheus/client_golang/prometheus/promhttp/delegator.go
@@ -53,12 +53,16 @@ func (r *responseWriterDelegator) Written() int64 {
 }
 
 func (r *responseWriterDelegator) WriteHeader(code int) {
+	if r.observeWriteHeader != nil && !r.wroteHeader {
+		// Only call observeWriteHeader for the 1st time. It's a bug if
+		// WriteHeader is called more than once, but we want to protect
+		// against it here. Note that we still delegate the WriteHeader
+		// to the original ResponseWriter to not mask the bug from it.
+		r.observeWriteHeader(code)
+	}
 	r.status = code
 	r.wroteHeader = true
 	r.ResponseWriter.WriteHeader(code)
-	if r.observeWriteHeader != nil {
-		r.observeWriteHeader(code)
-	}
 }
 
 func (r *responseWriterDelegator) Write(b []byte) (int, error) {
diff --git a/vendor/github.com/prometheus/client_golang/prometheus/promhttp/http.go b/vendor/github.com/prometheus/client_golang/prometheus/promhttp/http.go
index b0ee4678e..5e1c4546c 100644
--- a/vendor/github.com/prometheus/client_golang/prometheus/promhttp/http.go
+++ b/vendor/github.com/prometheus/client_golang/prometheus/promhttp/http.go
@@ -167,15 +167,12 @@ func HandlerFor(reg prometheus.Gatherer, opts HandlerOpts) http.Handler {
 
 		enc := expfmt.NewEncoder(w, contentType)
 
-		var lastErr error
-
 		// handleError handles the error according to opts.ErrorHandling
 		// and returns true if we have to abort after the handling.
 		handleError := func(err error) bool {
 			if err == nil {
 				return false
 			}
-			lastErr = err
 			if opts.ErrorLog != nil {
 				opts.ErrorLog.Println("error encoding and sending metric family:", err)
 			}
@@ -184,7 +181,10 @@ func HandlerFor(reg prometheus.Gatherer, opts HandlerOpts) http.Handler {
 			case PanicOnError:
 				panic(err)
 			case HTTPErrorOnError:
-				httpError(rsp, err)
+				// We cannot really send an HTTP error at this
+				// point because we most likely have written
+				// something to rsp already. But at least we can
+				// stop sending.
 				return true
 			}
 			// Do nothing in all other cases, including ContinueOnError.
@@ -202,10 +202,6 @@ func HandlerFor(reg prometheus.Gatherer, opts HandlerOpts) http.Handler {
 				return
 			}
 		}
-
-		if lastErr != nil {
-			httpError(rsp, lastErr)
-		}
 	})
 
 	if opts.Timeout <= 0 {
@@ -276,7 +272,12 @@ type HandlerErrorHandling int
 // errors are encountered.
 const (
 	// Serve an HTTP status code 500 upon the first error
-	// encountered. Report the error message in the body.
+	// encountered. Report the error message in the body. Note that HTTP
+	// errors cannot be served anymore once the beginning of a regular
+	// payload has been sent. Thus, in the (unlikely) case that encoding the
+	// payload into the negotiated wire format fails, serving the response
+	// will simply be aborted. Set an ErrorLog in HandlerOpts to detect
+	// those errors.
 	HTTPErrorOnError HandlerErrorHandling = iota
 	// Ignore errors and try to serve as many metrics as possible.  However,
 	// if no metrics can be served, serve an HTTP status code 500 and the
@@ -365,11 +366,9 @@ func gzipAccepted(header http.Header) bool {
 }
 
 // httpError removes any content-encoding header and then calls http.Error with
-// the provided error and http.StatusInternalServerErrer. Error contents is
-// supposed to be uncompressed plain text. However, same as with a plain
-// http.Error, any header settings will be void if the header has already been
-// sent. The error message will still be written to the writer, but it will
-// probably be of limited use.
+// the provided error and http.StatusInternalServerError. Error contents is
+// supposed to be uncompressed plain text. Same as with a plain http.Error, this
+// must not be called if the header or any payload has already been sent.
 func httpError(rsp http.ResponseWriter, err error) {
 	rsp.Header().Del(contentEncodingHeader)
 	http.Error(
diff --git a/vendor/modules.txt b/vendor/modules.txt
index 4872d8522..e4ff4a4c9 100644
--- a/vendor/modules.txt
+++ b/vendor/modules.txt
@@ -272,7 +272,7 @@ github.com/opentracing/opentracing-go/log
 github.com/pkg/errors
 # github.com/prometheus/alertmanager v0.20.0
 github.com/prometheus/alertmanager/api/v2/models
-# github.com/prometheus/client_golang v1.5.0
+# github.com/prometheus/client_golang v1.5.1
 github.com/prometheus/client_golang/api
 github.com/prometheus/client_golang/api/prometheus/v1
 github.com/prometheus/client_golang/prometheus
diff --git a/web/api/v1/api.go b/web/api/v1/api.go
index 204b2ff38..5ea367fa2 100644
--- a/web/api/v1/api.go
+++ b/web/api/v1/api.go
@@ -531,7 +531,7 @@ func (api *API) series(r *http.Request) apiFuncResult {
 	var sets []storage.SeriesSet
 	var warnings storage.Warnings
 	for _, mset := range matcherSets {
-		s, wrn, err := q.Select(false, nil, mset...)
+		s, wrn, err := q.Select(nil, mset...) //TODO
 		warnings = append(warnings, wrn...)
 		if err != nil {
 			return apiFuncResult{nil, &apiError{errorExec, err}, warnings, nil}
@@ -1161,9 +1161,10 @@ func (api *API) remoteRead(w http.ResponseWriter, r *http.Request) {
 			return
 		}
 		for i, query := range req.Queries {
-			err := api.remoteReadQuery(ctx, query, externalLabels, func(querier storage.Querier, hints *storage.SelectHints, filteredMatchers []*labels.Matcher) error {
-				// The streaming API has to provide the series sorted.
-				set, _, err := querier.Select(true, hints, filteredMatchers...)
+			err := api.remoteReadQuery(ctx, query, externalLabels, func(querier storage.Querier, selectParams *storage.SelectParams, filteredMatchers []*labels.Matcher) error {
+				// The streaming API provides sorted series.
+				// TODO(bwplotka): Handle warnings via query log.
+				set, _, err := querier.SelectSorted(selectParams, filteredMatchers...)
 				if err != nil {
 					return err
 				}
@@ -1194,8 +1195,8 @@ func (api *API) remoteRead(w http.ResponseWriter, r *http.Request) {
 			Results: make([]*prompb.QueryResult, len(req.Queries)),
 		}
 		for i, query := range req.Queries {
-			err := api.remoteReadQuery(ctx, query, externalLabels, func(querier storage.Querier, hints *storage.SelectHints, filteredMatchers []*labels.Matcher) error {
-				set, _, err := querier.Select(false, hints, filteredMatchers...)
+			err := api.remoteReadQuery(ctx, query, externalLabels, func(querier storage.Querier, selectParams *storage.SelectParams, filteredMatchers []*labels.Matcher) error {
+				set, _, err := querier.Select(selectParams, filteredMatchers...)
 				if err != nil {
 					return err
 				}
@@ -1253,7 +1254,7 @@ func filterExtLabelsFromMatchers(pbMatchers []*prompb.LabelMatcher, externalLabe
 	return filteredMatchers, nil
 }
 
-func (api *API) remoteReadQuery(ctx context.Context, query *prompb.Query, externalLabels map[string]string, seriesHandleFn func(querier storage.Querier, hints *storage.SelectHints, filteredMatchers []*labels.Matcher) error) error {
+func (api *API) remoteReadQuery(ctx context.Context, query *prompb.Query, externalLabels map[string]string, seriesHandleFn func(querier storage.Querier, selectParams *storage.SelectParams, filteredMatchers []*labels.Matcher) error) error {
 	filteredMatchers, err := filterExtLabelsFromMatchers(query.Matchers, externalLabels)
 	if err != nil {
 		return err
@@ -1263,25 +1264,23 @@ func (api *API) remoteReadQuery(ctx context.Context, query *prompb.Query, extern
 	if err != nil {
 		return err
 	}
+
+	var selectParams *storage.SelectParams
+	if query.Hints != nil {
+		selectParams = &storage.SelectParams{
+			Start: query.Hints.StartMs,
+			End:   query.Hints.EndMs,
+			Step:  query.Hints.StepMs,
+			Func:  query.Hints.Func,
+		}
+	}
+
 	defer func() {
 		if err := querier.Close(); err != nil {
 			level.Warn(api.logger).Log("msg", "error on querier close", "err", err.Error())
 		}
 	}()
-
-	var hints *storage.SelectHints
-	if query.Hints != nil {
-		hints = &storage.SelectHints{
-			Start:    query.Hints.StartMs,
-			End:      query.Hints.EndMs,
-			Step:     query.Hints.StepMs,
-			Func:     query.Hints.Func,
-			Grouping: query.Hints.Grouping,
-			Range:    query.Hints.RangeMs,
-			By:       query.Hints.By,
-		}
-	}
-	return seriesHandleFn(querier, hints, filteredMatchers)
+	return seriesHandleFn(querier, selectParams, filteredMatchers)
 }
 
 func (api *API) deleteSeries(r *http.Request) apiFuncResult {
diff --git a/web/federate.go b/web/federate.go
index 93c9aece3..e358a3dab 100644
--- a/web/federate.go
+++ b/web/federate.go
@@ -81,11 +81,14 @@ func (h *Handler) federation(w http.ResponseWriter, req *http.Request) {
 
 	vec := make(promql.Vector, 0, 8000)
 
-	hints := &storage.SelectHints{Start: mint, End: maxt}
+	params := &storage.SelectParams{
+		Start: mint,
+		End:   maxt,
+	}
 
 	var sets []storage.SeriesSet
 	for _, mset := range matcherSets {
-		s, wrns, err := q.Select(false, hints, mset...)
+		s, wrns, err := q.Select(params, mset...)
 		if wrns != nil {
 			level.Debug(h.logger).Log("msg", "federation select returned warnings", "warnings", wrns)
 			federationWarnings.Add(float64(len(wrns)))
diff --git a/web/ui/react-app/src/pages/graph/Legend.tsx b/web/ui/react-app/src/pages/graph/Legend.tsx
index 8a4068897..991db94c2 100644
--- a/web/ui/react-app/src/pages/graph/Legend.tsx
+++ b/web/ui/react-app/src/pages/graph/Legend.tsx
@@ -23,12 +23,12 @@ export class Legend extends PureComponent<LegendProps, LegendState> {
       this.setState({ selectedIndexes: [] });
     }
   }
-  handleSeriesSelect = (index: number) => (ev: React.MouseEvent<HTMLDivElement, MouseEvent>) => {
+  handleSeriesSelect = (index: number) => (ev: any) => {
     // TODO: add proper event type
     const { selectedIndexes } = this.state;
 
     let selected = [index];
-    if (ev.ctrlKey || ev.metaKey) {
+    if (ev.ctrlKey) {
       const { chartData } = this.props;
       if (selectedIndexes.includes(index)) {
         selected = selectedIndexes.filter(idx => idx !== index);
@@ -68,7 +68,7 @@ export class Legend extends PureComponent<LegendProps, LegendState> {
         ))}
         {chartData.length > 1 && (
           <div className="pl-1 mt-1 text-muted" style={{ fontSize: 13 }}>
-            Click: select series, {navigator.platform.includes('Mac') ? 'CMD' : 'CTRL'} + click: toggle multiple series
+            Click: select series, CTRL + click: toggle multiple series
           </div>
         )}
       </div>


Test patch:
diff --git a/promql/engine_test.go b/promql/engine_test.go
index 96204b392..e75c27bca 100644
--- a/promql/engine_test.go
+++ b/promql/engine_test.go
@@ -175,12 +175,15 @@ type errQuerier struct {
 	err error
 }
 
-func (q *errQuerier) Select(bool, *storage.SelectHints, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q *errQuerier) Select(*storage.SelectParams, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	return errSeriesSet{err: q.err}, nil, q.err
 }
-func (*errQuerier) LabelValues(string) ([]string, storage.Warnings, error) { return nil, nil, nil }
-func (*errQuerier) LabelNames() ([]string, storage.Warnings, error)        { return nil, nil, nil }
-func (*errQuerier) Close() error                                           { return nil }
+func (q *errQuerier) SelectSorted(*storage.SelectParams, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return errSeriesSet{err: q.err}, nil, q.err
+}
+func (*errQuerier) LabelValues(name string) ([]string, storage.Warnings, error) { return nil, nil, nil }
+func (*errQuerier) LabelNames() ([]string, storage.Warnings, error)             { return nil, nil, nil }
+func (*errQuerier) Close() error                                                { return nil }
 
 // errSeriesSet implements storage.SeriesSet which always returns error.
 type errSeriesSet struct {
@@ -221,9 +224,9 @@ func TestQueryError(t *testing.T) {
 	testutil.Equals(t, errStorage, res.Err)
 }
 
-// hintCheckerQuerier implements storage.Querier which checks the start and end times
-// in hints.
-type hintCheckerQuerier struct {
+// paramCheckerQuerier implements storage.Querier which checks the start and end times
+// in params.
+type paramCheckerQuerier struct {
 	start    int64
 	end      int64
 	grouping []string
@@ -234,7 +237,10 @@ type hintCheckerQuerier struct {
 	t *testing.T
 }
 
-func (q *hintCheckerQuerier) Select(_ bool, sp *storage.SelectHints, _ ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (q *paramCheckerQuerier) Select(sp *storage.SelectParams, m ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return q.SelectSorted(sp, m...)
+}
+func (q *paramCheckerQuerier) SelectSorted(sp *storage.SelectParams, _ ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	testutil.Equals(q.t, q.start, sp.Start)
 	testutil.Equals(q.t, q.end, sp.End)
 	testutil.Equals(q.t, q.grouping, sp.Grouping)
@@ -244,11 +250,11 @@ func (q *hintCheckerQuerier) Select(_ bool, sp *storage.SelectHints, _ ...*label
 
 	return errSeriesSet{err: nil}, nil, nil
 }
-func (*hintCheckerQuerier) LabelValues(string) ([]string, storage.Warnings, error) {
+func (*paramCheckerQuerier) LabelValues(name string) ([]string, storage.Warnings, error) {
 	return nil, nil, nil
 }
-func (*hintCheckerQuerier) LabelNames() ([]string, storage.Warnings, error) { return nil, nil, nil }
-func (*hintCheckerQuerier) Close() error                                    { return nil }
+func (*paramCheckerQuerier) LabelNames() ([]string, storage.Warnings, error) { return nil, nil, nil }
+func (*paramCheckerQuerier) Close() error                                    { return nil }
 
 func TestParamsSetCorrectly(t *testing.T) {
 	opts := EngineOpts{
@@ -429,7 +435,7 @@ func TestParamsSetCorrectly(t *testing.T) {
 	for _, tc := range cases {
 		engine := NewEngine(opts)
 		queryable := storage.QueryableFunc(func(ctx context.Context, mint, maxt int64) (storage.Querier, error) {
-			return &hintCheckerQuerier{start: tc.paramStart * 1000, end: tc.paramEnd * 1000, grouping: tc.paramGrouping, by: tc.paramBy, selRange: tc.paramRange, function: tc.paramFunc, t: t}, nil
+			return &paramCheckerQuerier{start: tc.paramStart * 1000, end: tc.paramEnd * 1000, grouping: tc.paramGrouping, by: tc.paramBy, selRange: tc.paramRange, function: tc.paramFunc, t: t}, nil
 		})
 
 		var (
diff --git a/promql/parser/parse_test.go b/promql/parser/parse_test.go
index 2cb9467b0..f99c4762c 100644
--- a/promql/parser/parse_test.go
+++ b/promql/parser/parse_test.go
@@ -2592,16 +2592,6 @@ func TestParseExpressions(t *testing.T) {
 		} else {
 			testutil.NotOk(t, err)
 			testutil.Assert(t, strings.Contains(err.Error(), test.errMsg), "unexpected error on input '%s', expected '%s', got '%s'", test.input, test.errMsg, err.Error())
-
-			errorList, ok := err.(ParseErrors)
-
-			testutil.Assert(t, ok, "unexpected error type")
-
-			for _, e := range errorList {
-				testutil.Assert(t, 0 <= e.PositionRange.Start, "parse error has negative position\nExpression '%s'\nError: %v", test.input, e)
-				testutil.Assert(t, e.PositionRange.Start <= e.PositionRange.End, "parse error has negative length\nExpression '%s'\nError: %v", test.input, e)
-				testutil.Assert(t, e.PositionRange.End <= Pos(len(test.input)), "parse error is not contained in input\nExpression '%s'\nError: %v", test.input, e)
-			}
 		}
 	}
 }
diff --git a/promql/test_test.go b/promql/test_test.go
index 7de4387f5..f03f6d203 100644
--- a/promql/test_test.go
+++ b/promql/test_test.go
@@ -133,7 +133,7 @@ func TestLazyLoader_WithSamplesTill(t *testing.T) {
 					}
 
 					// Get the series for the matcher.
-					ss, _, err := querier.Select(false, nil, matchers...)
+					ss, _, err := querier.Select(nil, matchers...)
 					testutil.Ok(t, err)
 					testutil.Assert(t, ss.Next(), "")
 					storageSeries := ss.At()
diff --git a/rules/manager_test.go b/rules/manager_test.go
index 4d26885c8..ac74f9ea0 100644
--- a/rules/manager_test.go
+++ b/rules/manager_test.go
@@ -512,8 +512,8 @@ func TestForStateRestore(t *testing.T) {
 }
 
 func TestStaleness(t *testing.T) {
-	st := teststorage.New(t)
-	defer st.Close()
+	storage := teststorage.New(t)
+	defer storage.Close()
 	engineOpts := promql.EngineOpts{
 		Logger:     nil,
 		Reg:        nil,
@@ -522,9 +522,9 @@ func TestStaleness(t *testing.T) {
 	}
 	engine := promql.NewEngine(engineOpts)
 	opts := &ManagerOptions{
-		QueryFunc:  EngineQueryFunc(engine, st),
-		Appendable: st,
-		TSDB:       st,
+		QueryFunc:  EngineQueryFunc(engine, storage),
+		Appendable: storage,
+		TSDB:       storage,
 		Context:    context.Background(),
 		Logger:     log.NewNopLogger(),
 	}
@@ -541,7 +541,7 @@ func TestStaleness(t *testing.T) {
 	})
 
 	// A time series that has two samples and then goes stale.
-	app := st.Appender()
+	app := storage.Appender()
 	app.Add(labels.FromStrings(model.MetricNameLabel, "a"), 0, 1)
 	app.Add(labels.FromStrings(model.MetricNameLabel, "a"), 1000, 2)
 	app.Add(labels.FromStrings(model.MetricNameLabel, "a"), 2000, math.Float64frombits(value.StaleNaN))
@@ -556,14 +556,14 @@ func TestStaleness(t *testing.T) {
 	group.Eval(ctx, time.Unix(1, 0))
 	group.Eval(ctx, time.Unix(2, 0))
 
-	querier, err := st.Querier(context.Background(), 0, 2000)
+	querier, err := storage.Querier(context.Background(), 0, 2000)
 	testutil.Ok(t, err)
 	defer querier.Close()
 
 	matcher, err := labels.NewMatcher(labels.MatchEqual, model.MetricNameLabel, "a_plus_one")
 	testutil.Ok(t, err)
 
-	set, _, err := querier.Select(false, nil, matcher)
+	set, _, err := querier.Select(nil, matcher)
 	testutil.Ok(t, err)
 
 	samples, err := readSeriesSet(set)
@@ -658,8 +658,8 @@ func TestCopyState(t *testing.T) {
 }
 
 func TestDeletedRuleMarkedStale(t *testing.T) {
-	st := teststorage.New(t)
-	defer st.Close()
+	storage := teststorage.New(t)
+	defer storage.Close()
 	oldGroup := &Group{
 		rules: []Rule{
 			NewRecordingRule("rule1", nil, labels.Labels{{Name: "l1", Value: "v1"}}),
@@ -672,21 +672,21 @@ func TestDeletedRuleMarkedStale(t *testing.T) {
 		rules:                []Rule{},
 		seriesInPreviousEval: []map[string]labels.Labels{},
 		opts: &ManagerOptions{
-			Appendable: st,
+			Appendable: storage,
 		},
 	}
 	newGroup.CopyState(oldGroup)
 
 	newGroup.Eval(context.Background(), time.Unix(0, 0))
 
-	querier, err := st.Querier(context.Background(), 0, 2000)
+	querier, err := storage.Querier(context.Background(), 0, 2000)
 	testutil.Ok(t, err)
 	defer querier.Close()
 
 	matcher, err := labels.NewMatcher(labels.MatchEqual, "l1", "v1")
 	testutil.Ok(t, err)
 
-	set, _, err := querier.Select(false, nil, matcher)
+	set, _, err := querier.Select(nil, matcher)
 	testutil.Ok(t, err)
 
 	samples, err := readSeriesSet(set)
@@ -704,8 +704,8 @@ func TestUpdate(t *testing.T) {
 	expected := map[string]labels.Labels{
 		"test": labels.FromStrings("name", "value"),
 	}
-	st := teststorage.New(t)
-	defer st.Close()
+	storage := teststorage.New(t)
+	defer storage.Close()
 	opts := promql.EngineOpts{
 		Logger:     nil,
 		Reg:        nil,
@@ -714,9 +714,9 @@ func TestUpdate(t *testing.T) {
 	}
 	engine := promql.NewEngine(opts)
 	ruleManager := NewManager(&ManagerOptions{
-		Appendable: st,
-		TSDB:       st,
-		QueryFunc:  EngineQueryFunc(engine, st),
+		Appendable: storage,
+		TSDB:       storage,
+		QueryFunc:  EngineQueryFunc(engine, storage),
 		Context:    context.Background(),
 		Logger:     log.NewNopLogger(),
 	})
@@ -1096,16 +1096,16 @@ func TestMetricsStalenessOnManagerShutdown(t *testing.T) {
 	testutil.Equals(t, 0, countStaleNaN(t, storage), "invalid count of staleness markers after stopping the engine")
 }
 
-func countStaleNaN(t *testing.T, st storage.Storage) int {
+func countStaleNaN(t *testing.T, storage storage.Storage) int {
 	var c int
-	querier, err := st.Querier(context.Background(), 0, time.Now().Unix()*1000)
+	querier, err := storage.Querier(context.Background(), 0, time.Now().Unix()*1000)
 	testutil.Ok(t, err)
 	defer querier.Close()
 
 	matcher, err := labels.NewMatcher(labels.MatchEqual, model.MetricNameLabel, "test_2")
 	testutil.Ok(t, err)
 
-	set, _, err := querier.Select(false, nil, matcher)
+	set, _, err := querier.Select(nil, matcher)
 	testutil.Ok(t, err)
 
 	samples, err := readSeriesSet(set)
diff --git a/scrape/scrape_test.go b/scrape/scrape_test.go
index 8bc45a72e..608c956b8 100644
--- a/scrape/scrape_test.go
+++ b/scrape/scrape_test.go
@@ -1571,7 +1571,7 @@ func TestScrapeLoopDiscardDuplicateLabels(t *testing.T) {
 
 	q, err := s.Querier(ctx, time.Time{}.UnixNano(), 0)
 	testutil.Ok(t, err)
-	series, _, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
+	series, _, err := q.Select(&storage.SelectParams{}, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, false, series.Next(), "series found in tsdb")
 
@@ -1581,7 +1581,7 @@ func TestScrapeLoopDiscardDuplicateLabels(t *testing.T) {
 
 	q, err = s.Querier(ctx, time.Time{}.UnixNano(), 0)
 	testutil.Ok(t, err)
-	series, _, err = q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "le", "500"))
+	series, _, err = q.Select(&storage.SelectParams{}, labels.MustNewMatcher(labels.MatchEqual, "le", "500"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, true, series.Next(), "series not found in tsdb")
 	testutil.Equals(t, false, series.Next(), "more than one series found in tsdb")
@@ -1617,7 +1617,7 @@ func TestScrapeLoopDiscardUnnamedMetrics(t *testing.T) {
 
 	q, err := s.Querier(ctx, time.Time{}.UnixNano(), 0)
 	testutil.Ok(t, err)
-	series, _, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
+	series, _, err := q.Select(&storage.SelectParams{}, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, false, series.Next(), "series found in tsdb")
 }
@@ -1807,3 +1807,35 @@ func TestReuseScrapeCache(t *testing.T) {
 		}
 	}
 }
+
+func TestScrapeAddFast(t *testing.T) {
+	s := teststorage.New(t)
+	defer s.Close()
+
+	app := s.Appender()
+
+	ctx, cancel := context.WithCancel(context.Background())
+	sl := newScrapeLoop(ctx,
+		&testScraper{},
+		nil, nil,
+		nopMutator,
+		nopMutator,
+		func() storage.Appender { return app },
+		nil,
+		0,
+		true,
+	)
+	defer cancel()
+
+	_, _, _, err := sl.append([]byte("up 1\n"), "", time.Time{})
+	testutil.Ok(t, err)
+
+	// Poison the cache. There is just one entry, and one series in the
+	// storage. Changing the ref will create a 'not found' error.
+	for _, v := range sl.getCache().series {
+		v.ref++
+	}
+
+	_, _, _, err = sl.append([]byte("up 1\n"), "", time.Time{}.Add(time.Second))
+	testutil.Ok(t, err)
+}
diff --git a/storage/fanout/fanout_test.go b/storage/fanout/fanout_test.go
index e26106cca..7afb04202 100644
--- a/storage/fanout/fanout_test.go
+++ b/storage/fanout/fanout_test.go
@@ -15,6 +15,7 @@ package storage
 
 import (
 	"context"
+	"errors"
 
 	"github.com/prometheus/common/model"
 	"github.com/prometheus/prometheus/pkg/labels"
@@ -26,7 +27,6 @@ import (
 )
 
 func TestSelectSorted(t *testing.T) {
-
 	inputLabel := labels.FromStrings(model.MetricNameLabel, "a")
 	outputLabel := labels.FromStrings(model.MetricNameLabel, "a")
 
@@ -79,7 +79,7 @@ func TestSelectSorted(t *testing.T) {
 	matcher, err := labels.NewMatcher(labels.MatchEqual, model.MetricNameLabel, "a")
 	testutil.Ok(t, err)
 
-	seriesSet, _, err := querier.Select(true, nil, matcher)
+	seriesSet, _, err := querier.SelectSorted(nil, matcher)
 	testutil.Ok(t, err)
 
 	result := make(map[int64]float64)
@@ -97,5 +97,94 @@ func TestSelectSorted(t *testing.T) {
 
 	testutil.Equals(t, labelsResult, outputLabel)
 	testutil.Equals(t, inputTotalSize, len(result))
+}
+
+func TestFanoutErrors(t *testing.T) {
+	workingStorage := teststorage.New(t)
+	defer workingStorage.Close()
+
+	cases := []struct {
+		primary   storage.Storage
+		secondary storage.Storage
+		warnings  storage.Warnings
+		err       error
+	}{
+		{
+			primary:   workingStorage,
+			secondary: errStorage{},
+			warnings:  storage.Warnings{errSelect},
+			err:       nil,
+		},
+		{
+			primary:   errStorage{},
+			secondary: workingStorage,
+			warnings:  nil,
+			err:       errSelect,
+		},
+	}
+
+	for _, tc := range cases {
+		fanoutStorage := storage.NewFanout(nil, tc.primary, tc.secondary)
+
+		querier, err := fanoutStorage.Querier(context.Background(), 0, 8000)
+		testutil.Ok(t, err)
+		defer querier.Close()
+
+		matcher := labels.MustNewMatcher(labels.MatchEqual, "a", "b")
+		ss, warnings, err := querier.SelectSorted(nil, matcher)
+		testutil.Equals(t, tc.err, err)
+		testutil.Equals(t, tc.warnings, warnings)
+
+		// Only test series iteration if there are no errors.
+		if err != nil {
+			continue
+		}
+
+		for ss.Next() {
+			ss.At()
+		}
+		testutil.Ok(t, ss.Err())
+	}
+}
+
+var errSelect = errors.New("select error")
+
+type errStorage struct{}
+
+func (errStorage) Querier(_ context.Context, _, _ int64) (storage.Querier, error) {
+	return errQuerier{}, nil
+}
+
+func (errStorage) Appender() storage.Appender {
+	return nil
+}
+
+func (errStorage) StartTime() (int64, error) {
+	return 0, nil
+}
+
+func (errStorage) Close() error {
+	return nil
+}
+
+type errQuerier struct{}
+
+func (errQuerier) Select(*storage.SelectParams, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return nil, nil, errSelect
+}
+
+func (errQuerier) SelectSorted(*storage.SelectParams, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+	return nil, nil, errSelect
+}
+
+func (errQuerier) LabelValues(name string) ([]string, storage.Warnings, error) {
+	return nil, nil, errors.New("label values error")
+}
+
+func (errQuerier) LabelNames() ([]string, storage.Warnings, error) {
+	return nil, nil, errors.New("label names error")
+}
 
+func (errQuerier) Close() error {
+	return nil
 }
diff --git a/storage/remote/codec_test.go b/storage/remote/codec_test.go
index d694b487c..9f7b2c218 100644
--- a/storage/remote/codec_test.go
+++ b/storage/remote/codec_test.go
@@ -178,7 +178,7 @@ func TestFromQueryResultWithDuplicates(t *testing.T) {
 		},
 	}
 
-	series := FromQueryResult(false, &res)
+	series := FromQueryResult(&res)
 
 	errSeries, isErrSeriesSet := series.(errSeriesSet)
 
diff --git a/storage/remote/read_test.go b/storage/remote/read_test.go
index 0706d7bff..28dfa79fb 100644
--- a/storage/remote/read_test.go
+++ b/storage/remote/read_test.go
@@ -117,7 +117,7 @@ func TestExternalLabelsQuerierSelect(t *testing.T) {
 		},
 	}
 	want := newSeriesSetFilter(mockSeriesSet{}, q.externalLabels)
-	have, _, err := q.Select(false, nil, matchers...)
+	have, _, err := q.Select(nil, matchers...)
 	if err != nil {
 		t.Error(err)
 	}
@@ -219,7 +219,7 @@ func TestSeriesSetFilter(t *testing.T) {
 	}
 
 	for i, tc := range tests {
-		filtered := newSeriesSetFilter(FromQueryResult(true, tc.in), tc.toRemove)
+		filtered := newSeriesSetFilter(FromQueryResult(tc.in), tc.toRemove)
 		have, err := ToQueryResult(filtered, 1e6)
 		if err != nil {
 			t.Fatal(err)
@@ -242,7 +242,7 @@ type mockSeriesSet struct {
 	storage.SeriesSet
 }
 
-func (mockQuerier) Select(bool, *storage.SelectHints, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
+func (mockQuerier) Select(*storage.SelectParams, ...*labels.Matcher) (storage.SeriesSet, storage.Warnings, error) {
 	return mockSeriesSet{}, nil, nil
 }
 
@@ -398,7 +398,7 @@ func TestRequiredLabelsQuerierSelect(t *testing.T) {
 			requiredMatchers: test.requiredMatchers,
 		}
 
-		have, _, err := q.Select(false, nil, test.matchers...)
+		have, _, err := q.Select(nil, test.matchers...)
 		if err != nil {
 			t.Error(err)
 		}
diff --git a/tsdb/block_test.go b/tsdb/block_test.go
index f812d2970..d1ef6c524 100644
--- a/tsdb/block_test.go
+++ b/tsdb/block_test.go
@@ -203,7 +203,7 @@ func TestCorruptedChunk(t *testing.T) {
 			querier, err := NewBlockQuerier(b, 0, 1)
 			testutil.Ok(t, err)
 			defer func() { testutil.Ok(t, querier.Close()) }()
-			set, ws, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+			set, ws, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 			testutil.Ok(t, err)
 			testutil.Equals(t, 0, len(ws))
 
diff --git a/tsdb/db_test.go b/tsdb/db_test.go
index dfd7f304e..e824b0c40 100644
--- a/tsdb/db_test.go
+++ b/tsdb/db_test.go
@@ -67,7 +67,7 @@ func openTestDB(t testing.TB, opts *Options, rngs []int64) (db *DB, close func()
 
 // query runs a matcher query against the querier and fully expands its data.
 func query(t testing.TB, q storage.Querier, matchers ...*labels.Matcher) map[string][]tsdbutil.Sample {
-	ss, ws, err := q.Select(false, nil, matchers...)
+	ss, ws, err := q.Select(nil, matchers...)
 	defer func() {
 		testutil.Ok(t, q.Close())
 	}()
@@ -215,7 +215,7 @@ func TestDBAppenderAddRef(t *testing.T) {
 	testutil.Ok(t, err)
 
 	err = app2.AddFast(9999999, 1, 1)
-	testutil.Equals(t, ErrNotFound, errors.Cause(err))
+	testutil.Equals(t, storage.ErrNotFound, errors.Cause(err))
 
 	testutil.Ok(t, app2.Commit())
 
@@ -315,7 +315,7 @@ Outer:
 		q, err := db.Querier(context.TODO(), 0, numSamples)
 		testutil.Ok(t, err)
 
-		res, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+		res, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -363,7 +363,7 @@ func TestAmendDatapointCausesError(t *testing.T) {
 
 	app = db.Appender()
 	_, err = app.Add(labels.Labels{{Name: "a", Value: "b"}}, 0, 1)
-	testutil.Equals(t, ErrAmendSample, err)
+	testutil.Equals(t, storage.ErrDuplicateSampleForTimestamp, err)
 	testutil.Ok(t, app.Rollback())
 }
 
@@ -398,7 +398,7 @@ func TestNonDuplicateNaNDatapointsCausesAmendError(t *testing.T) {
 
 	app = db.Appender()
 	_, err = app.Add(labels.Labels{{Name: "a", Value: "b"}}, 0, math.Float64frombits(0x7ff0000000000002))
-	testutil.Equals(t, ErrAmendSample, err)
+	testutil.Equals(t, storage.ErrDuplicateSampleForTimestamp, err)
 }
 
 func TestEmptyLabelsetCausesError(t *testing.T) {
@@ -491,7 +491,7 @@ func TestDB_Snapshot(t *testing.T) {
 	defer func() { testutil.Ok(t, querier.Close()) }()
 
 	// sum values
-	seriesSet, ws, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	seriesSet, ws, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 
@@ -546,7 +546,7 @@ func TestDB_Snapshot_ChunksOutsideOfCompactedRange(t *testing.T) {
 	defer func() { testutil.Ok(t, querier.Close()) }()
 
 	// Sum values.
-	seriesSet, ws, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	seriesSet, ws, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 
@@ -618,7 +618,7 @@ Outer:
 		testutil.Ok(t, err)
 		defer func() { testutil.Ok(t, q.Close()) }()
 
-		res, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+		res, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -792,7 +792,7 @@ func TestDB_e2e(t *testing.T) {
 			q, err := db.Querier(context.TODO(), mint, maxt)
 			testutil.Ok(t, err)
 
-			ss, ws, err := q.Select(false, nil, qry.ms...)
+			ss, ws, err := q.Select(nil, qry.ms...)
 			testutil.Ok(t, err)
 			testutil.Equals(t, 0, len(ws))
 
@@ -951,7 +951,7 @@ func TestTombstoneClean(t *testing.T) {
 		testutil.Ok(t, err)
 		defer q.Close()
 
-		res, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+		res, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -1289,7 +1289,7 @@ func TestNotMatcherSelectsLabelsUnsetSeries(t *testing.T) {
 	defer func() { testutil.Ok(t, q.Close()) }()
 
 	for _, c := range cases {
-		ss, ws, err := q.Select(false, nil, c.selector...)
+		ss, ws, err := q.Select(nil, c.selector...)
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -1660,7 +1660,7 @@ func TestNoEmptyBlocks(t *testing.T) {
 
 		app = db.Appender()
 		_, err = app.Add(defaultLabel, 1, 0)
-		testutil.Assert(t, err == ErrOutOfBounds, "the head should be truncated so no samples in the past should be allowed")
+		testutil.Assert(t, err == storage.ErrOutOfBounds, "the head should be truncated so no samples in the past should be allowed")
 
 		// Adding new blocks.
 		currentTime := db.Head().MaxTime()
@@ -2486,7 +2486,7 @@ func TestDBReadOnly_FlushWAL(t *testing.T) {
 	defer func() { testutil.Ok(t, querier.Close()) }()
 
 	// Sum the values.
-	seriesSet, ws, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, defaultLabelName, "flush"))
+	seriesSet, ws, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, defaultLabelName, "flush"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 
@@ -2551,7 +2551,7 @@ func TestDBCannotSeePartialCommits(t *testing.T) {
 			testutil.Ok(t, err)
 			defer querier.Close()
 
-			ss, _, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+			ss, _, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 			testutil.Ok(t, err)
 
 			_, seriesSet, err := expandSeriesSet(ss)
@@ -2591,13 +2591,13 @@ func TestDBQueryDoesntSeeAppendsAfterCreation(t *testing.T) {
 	defer querierAfterAddButBeforeCommit.Close()
 
 	// None of the queriers should return anything after the Add but before the commit.
-	ss, _, err := querierBeforeAdd.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	ss, _, err := querierBeforeAdd.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	_, seriesSet, err := expandSeriesSet(ss)
 	testutil.Ok(t, err)
 	testutil.Equals(t, map[string][]sample{}, seriesSet)
 
-	ss, _, err = querierAfterAddButBeforeCommit.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	ss, _, err = querierAfterAddButBeforeCommit.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	_, seriesSet, err = expandSeriesSet(ss)
 	testutil.Ok(t, err)
@@ -2608,14 +2608,14 @@ func TestDBQueryDoesntSeeAppendsAfterCreation(t *testing.T) {
 	testutil.Ok(t, err)
 
 	// Nothing returned for querier created before the Add.
-	ss, _, err = querierBeforeAdd.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	ss, _, err = querierBeforeAdd.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	_, seriesSet, err = expandSeriesSet(ss)
 	testutil.Ok(t, err)
 	testutil.Equals(t, map[string][]sample{}, seriesSet)
 
 	// Series exists but has no samples for querier created after Add.
-	ss, _, err = querierAfterAddButBeforeCommit.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	ss, _, err = querierAfterAddButBeforeCommit.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	_, seriesSet, err = expandSeriesSet(ss)
 	testutil.Ok(t, err)
@@ -2626,7 +2626,7 @@ func TestDBQueryDoesntSeeAppendsAfterCreation(t *testing.T) {
 	defer querierAfterCommit.Close()
 
 	// Samples are returned for querier created after Commit.
-	ss, _, err = querierAfterCommit.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+	ss, _, err = querierAfterCommit.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 	testutil.Ok(t, err)
 	_, seriesSet, err = expandSeriesSet(ss)
 	testutil.Ok(t, err)
diff --git a/tsdb/head_test.go b/tsdb/head_test.go
index a8b55f91b..f7aa9975c 100644
--- a/tsdb/head_test.go
+++ b/tsdb/head_test.go
@@ -23,6 +23,7 @@ import (
 	"path/filepath"
 	"sort"
 	"strconv"
+	"sync"
 	"testing"
 
 	"github.com/pkg/errors"
@@ -565,7 +566,7 @@ func TestHeadDeleteSimple(t *testing.T) {
 				for _, h := range []*Head{head, reloadedHead} {
 					q, err := NewBlockQuerier(h, h.MinTime(), h.MaxTime())
 					testutil.Ok(t, err)
-					actSeriesSet, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, lblDefault.Name, lblDefault.Value))
+					actSeriesSet, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, lblDefault.Name, lblDefault.Value))
 					testutil.Ok(t, err)
 					testutil.Equals(t, 0, len(ws))
 
@@ -612,7 +613,7 @@ func TestDeleteUntilCurMax(t *testing.T) {
 	// Test the series returns no samples. The series is cleared only after compaction.
 	q, err := NewBlockQuerier(hb, 0, 100000)
 	testutil.Ok(t, err)
-	res, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+	res, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 	testutil.Assert(t, res.Next(), "series is not present")
@@ -627,7 +628,7 @@ func TestDeleteUntilCurMax(t *testing.T) {
 	testutil.Ok(t, app.Commit())
 	q, err = NewBlockQuerier(hb, 0, 100000)
 	testutil.Ok(t, err)
-	res, ws, err = q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
+	res, ws, err = q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "b"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 	testutil.Assert(t, res.Next(), "series don't exist")
@@ -803,7 +804,7 @@ func TestDelete_e2e(t *testing.T) {
 			q, err := NewBlockQuerier(hb, 0, 100000)
 			testutil.Ok(t, err)
 			defer q.Close()
-			ss, ws, err := q.Select(true, nil, del.ms...)
+			ss, ws, err := q.SelectSorted(nil, del.ms...)
 			testutil.Ok(t, err)
 			testutil.Equals(t, 0, len(ws))
 			// Build the mockSeriesSet.
@@ -1011,7 +1012,7 @@ func TestGCChunkAccess(t *testing.T) {
 	testutil.Ok(t, h.Truncate(1500)) // Remove a chunk.
 
 	_, err = cr.Chunk(chunks[0].Ref)
-	testutil.Equals(t, ErrNotFound, err)
+	testutil.Equals(t, storage.ErrNotFound, err)
 	_, err = cr.Chunk(chunks[1].Ref)
 	testutil.Ok(t, err)
 }
@@ -1065,9 +1066,9 @@ func TestGCSeriesAccess(t *testing.T) {
 	testutil.Equals(t, (*memSeries)(nil), h.series.getByID(1))
 
 	_, err = cr.Chunk(chunks[0].Ref)
-	testutil.Equals(t, ErrNotFound, err)
+	testutil.Equals(t, storage.ErrNotFound, err)
 	_, err = cr.Chunk(chunks[1].Ref)
-	testutil.Equals(t, ErrNotFound, err)
+	testutil.Equals(t, storage.ErrNotFound, err)
 }
 
 func TestUncommittedSamplesNotLostOnTruncate(t *testing.T) {
@@ -1091,7 +1092,7 @@ func TestUncommittedSamplesNotLostOnTruncate(t *testing.T) {
 	testutil.Ok(t, err)
 	defer q.Close()
 
-	ss, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "1"))
+	ss, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "1"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 
@@ -1119,7 +1120,7 @@ func TestRemoveSeriesAfterRollbackAndTruncate(t *testing.T) {
 	testutil.Ok(t, err)
 	defer q.Close()
 
-	ss, ws, err := q.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "a", "1"))
+	ss, ws, err := q.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "a", "1"))
 	testutil.Ok(t, err)
 	testutil.Equals(t, 0, len(ws))
 
@@ -1336,6 +1337,7 @@ func TestHeadSeriesWithTimeBoundaries(t *testing.T) {
 	h, err := NewHead(nil, nil, nil, 15, DefaultStripeSize)
 	testutil.Ok(t, err)
 	defer h.Close()
+	testutil.Ok(t, h.Init(0))
 	app := h.Appender()
 
 	s1, err := app.Add(labels.FromStrings("foo1", "bar"), 2, 0)
@@ -1403,7 +1405,7 @@ func TestHeadSeriesWithTimeBoundaries(t *testing.T) {
 
 		seriesCount := 0
 		samplesCount := 0
-		ss, _, err := q.Select(false, nil, matcher)
+		ss, _, err := q.Select(nil, matcher)
 		testutil.Ok(t, err)
 		for ss.Next() {
 			i := ss.At().Iterator()
@@ -1443,7 +1445,7 @@ func TestMemSeriesIsolation(t *testing.T) {
 		testutil.Ok(t, err)
 		defer querier.Close()
 
-		ss, _, err := querier.Select(false, nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
+		ss, _, err := querier.Select(nil, labels.MustNewMatcher(labels.MatchEqual, "foo", "bar"))
 		testutil.Ok(t, err)
 
 		_, seriesSet, err := expandSeriesSet(ss)
@@ -1594,3 +1596,42 @@ func TestIsolationAppendIDZeroIsNoop(t *testing.T) {
 	testutil.Assert(t, ok, "Series append failed.")
 	testutil.Equals(t, 0, s.txs.txIDCount, "Series should not have an appendID after append with appendID=0.")
 }
+
+func TestHeadSeriesChunkRace(t *testing.T) {
+	for i := 0; i < 1000; i++ {
+		testHeadSeriesChunkRace(t)
+	}
+}
+
+func testHeadSeriesChunkRace(t *testing.T) {
+	h, err := NewHead(nil, nil, nil, 30, DefaultStripeSize)
+	testutil.Ok(t, err)
+	defer h.Close()
+	testutil.Ok(t, h.Init(0))
+	app := h.Appender()
+
+	s2, err := app.Add(labels.FromStrings("foo2", "bar"), 5, 0)
+	testutil.Ok(t, err)
+	for ts := int64(6); ts < 11; ts++ {
+		err = app.AddFast(s2, ts, 0)
+		testutil.Ok(t, err)
+	}
+	testutil.Ok(t, app.Commit())
+
+	var wg sync.WaitGroup
+	matcher := labels.MustNewMatcher(labels.MatchEqual, "", "")
+	q, err := NewBlockQuerier(h, 18, 22)
+	testutil.Ok(t, err)
+	defer q.Close()
+
+	wg.Add(1)
+	go func() {
+		h.updateMinMaxTime(20, 25)
+		h.gc()
+		wg.Done()
+	}()
+	ss, _, err := q.Select(nil, matcher)
+	testutil.Ok(t, err)
+	testutil.Ok(t, ss.Err())
+	wg.Wait()
+}
diff --git a/tsdb/querier_bench_test.go b/tsdb/querier_bench_test.go
index 95502be95..765435203 100644
--- a/tsdb/querier_bench_test.go
+++ b/tsdb/querier_bench_test.go
@@ -22,6 +22,7 @@ import (
 	"testing"
 
 	"github.com/prometheus/prometheus/pkg/labels"
+	"github.com/prometheus/prometheus/storage"
 	"github.com/prometheus/prometheus/util/testutil"
 )
 
@@ -146,7 +147,12 @@ func BenchmarkQuerierSelect(b *testing.B) {
 
 				b.ResetTimer()
 				for i := 0; i < b.N; i++ {
-					ss, _, err := q.Select(sorted, nil, matcher)
+					var ss storage.SeriesSet
+					if sorted {
+						ss, _, err = q.SelectSorted(nil, matcher)
+					} else {
+						ss, _, err = q.Select(nil, matcher)
+					}
 					testutil.Ok(b, err)
 					for ss.Next() {
 					}
diff --git a/tsdb/querier_test.go b/tsdb/querier_test.go
index 5c31897f8..52e316051 100644
--- a/tsdb/querier_test.go
+++ b/tsdb/querier_test.go
@@ -373,7 +373,7 @@ Outer:
 			maxt: c.maxt,
 		}
 
-		res, ws, err := querier.Select(false, nil, c.ms...)
+		res, ws, err := querier.Select(nil, c.ms...)
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -536,7 +536,7 @@ Outer:
 			maxt: c.maxt,
 		}
 
-		res, ws, err := querier.Select(false, nil, c.ms...)
+		res, ws, err := querier.Select(nil, c.ms...)
 		testutil.Ok(t, err)
 		testutil.Equals(t, 0, len(ws))
 
@@ -1491,7 +1491,7 @@ func (m mockIndex) SortedPostings(p index.Postings) index.Postings {
 func (m mockIndex) Series(ref uint64, lset *labels.Labels, chks *[]chunks.Meta) error {
 	s, ok := m.series[ref]
 	if !ok {
-		return ErrNotFound
+		return storage.ErrNotFound
 	}
 	*lset = append((*lset)[:0], s.l...)
 	*chks = append((*chks)[:0], s.chunks...)
@@ -1710,7 +1710,7 @@ func BenchmarkQuerySeek(b *testing.B) {
 				b.ResetTimer()
 				b.ReportAllocs()
 
-				ss, ws, err := sq.Select(false, nil, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
+				ss, ws, err := sq.Select(nil, labels.MustNewMatcher(labels.MatchRegexp, "__name__", ".*"))
 				for ss.Next() {
 					it := ss.At().Iterator()
 					for t := mint; t <= maxt; t++ {
@@ -1848,7 +1848,7 @@ func BenchmarkSetMatcher(b *testing.B) {
 			b.ResetTimer()
 			b.ReportAllocs()
 			for n := 0; n < b.N; n++ {
-				_, ws, err := que.Select(false, nil, labels.MustNewMatcher(labels.MatchRegexp, "test", c.pattern))
+				_, ws, err := que.Select(nil, labels.MustNewMatcher(labels.MatchRegexp, "test", c.pattern))
 				testutil.Ok(b, err)
 				testutil.Equals(b, 0, len(ws))
 			}
@@ -2297,7 +2297,7 @@ func benchQuery(b *testing.B, expExpansions int, q storage.Querier, selectors la
 	b.ResetTimer()
 	b.ReportAllocs()
 	for i := 0; i < b.N; i++ {
-		ss, ws, err := q.Select(false, nil, selectors...)
+		ss, ws, err := q.Select(nil, selectors...)
 		testutil.Ok(b, err)
 		testutil.Equals(b, 0, len(ws))
 		var actualExpansions int
diff --git a/tsdb/wal/checkpoint_test.go b/tsdb/wal/checkpoint_test.go
index eb0e22a4b..48ae84236 100644
--- a/tsdb/wal/checkpoint_test.go
+++ b/tsdb/wal/checkpoint_test.go
@@ -62,18 +62,6 @@ func TestLastCheckpoint(t *testing.T) {
 	testutil.Ok(t, err)
 	testutil.Equals(t, filepath.Join(dir, "checkpoint.1000"), s)
 	testutil.Equals(t, 1000, k)
-
-	testutil.Ok(t, os.MkdirAll(filepath.Join(dir, "checkpoint.99999999"), 0777))
-	s, k, err = LastCheckpoint(dir)
-	testutil.Ok(t, err)
-	testutil.Equals(t, filepath.Join(dir, "checkpoint.99999999"), s)
-	testutil.Equals(t, 99999999, k)
-
-	testutil.Ok(t, os.MkdirAll(filepath.Join(dir, "checkpoint.100000000"), 0777))
-	s, k, err = LastCheckpoint(dir)
-	testutil.Ok(t, err)
-	testutil.Equals(t, filepath.Join(dir, "checkpoint.100000000"), s)
-	testutil.Equals(t, 100000000, k)
 }
 
 func TestDeleteCheckpoints(t *testing.T) {
@@ -95,16 +83,6 @@ func TestDeleteCheckpoints(t *testing.T) {
 	files, err := fileutil.ReadDir(dir)
 	testutil.Ok(t, err)
 	testutil.Equals(t, []string{"checkpoint.02", "checkpoint.03"}, files)
-
-	testutil.Ok(t, os.MkdirAll(filepath.Join(dir, "checkpoint.99999999"), 0777))
-	testutil.Ok(t, os.MkdirAll(filepath.Join(dir, "checkpoint.100000000"), 0777))
-	testutil.Ok(t, os.MkdirAll(filepath.Join(dir, "checkpoint.100000001"), 0777))
-
-	testutil.Ok(t, DeleteCheckpoints(dir, 100000000))
-
-	files, err = fileutil.ReadDir(dir)
-	testutil.Ok(t, err)
-	testutil.Equals(t, []string{"checkpoint.100000000", "checkpoint.100000001"}, files)
 }
 
 func TestCheckpoint(t *testing.T) {
@@ -181,9 +159,9 @@ func TestCheckpoint(t *testing.T) {
 			files, err := fileutil.ReadDir(dir)
 			testutil.Ok(t, err)
 			testutil.Equals(t, 1, len(files))
-			testutil.Equals(t, "checkpoint.00000106", files[0])
+			testutil.Equals(t, "checkpoint.000106", files[0])
 
-			sr, err := NewSegmentsReader(filepath.Join(dir, "checkpoint.00000106"))
+			sr, err := NewSegmentsReader(filepath.Join(dir, "checkpoint.000106"))
 			testutil.Ok(t, err)
 			defer sr.Close()
 
diff --git a/web/api/v1/api_test.go b/web/api/v1/api_test.go
index 2c8a7c6ac..bfac2d4f1 100644
--- a/web/api/v1/api_test.go
+++ b/web/api/v1/api_test.go
@@ -488,9 +488,9 @@ func setupRemote(s storage.Storage) *httptest.Server {
 				return
 			}
 
-			var hints *storage.SelectHints
+			var selectParams *storage.SelectParams
 			if query.Hints != nil {
-				hints = &storage.SelectHints{
+				selectParams = &storage.SelectParams{
 					Start: query.Hints.StartMs,
 					End:   query.Hints.EndMs,
 					Step:  query.Hints.StepMs,
@@ -505,7 +505,7 @@ func setupRemote(s storage.Storage) *httptest.Server {
 			}
 			defer querier.Close()
 
-			set, _, err := querier.Select(false, hints, matchers...)
+			set, _, err := querier.Select(selectParams, matchers...)
 			if err != nil {
 				http.Error(w, err.Error(), http.StatusInternalServerError)
 				return
@@ -1615,7 +1615,7 @@ func TestSampledReadEndpoint(t *testing.T) {
 	matcher2, err := labels.NewMatcher(labels.MatchEqual, "d", "e")
 	testutil.Ok(t, err)
 
-	query, err := remote.ToQuery(0, 1, []*labels.Matcher{matcher1, matcher2}, &storage.SelectHints{Step: 0, Func: "avg"})
+	query, err := remote.ToQuery(0, 1, []*labels.Matcher{matcher1, matcher2}, &storage.SelectParams{Step: 0, Func: "avg"})
 	testutil.Ok(t, err)
 
 	req := &prompb.ReadRequest{Queries: []*prompb.Query{query}}
@@ -1714,7 +1714,7 @@ func TestStreamReadEndpoint(t *testing.T) {
 	matcher3, err := labels.NewMatcher(labels.MatchEqual, "foo", "bar1")
 	testutil.Ok(t, err)
 
-	query1, err := remote.ToQuery(0, 14400001, []*labels.Matcher{matcher1, matcher2}, &storage.SelectHints{
+	query1, err := remote.ToQuery(0, 14400001, []*labels.Matcher{matcher1, matcher2}, &storage.SelectParams{
 		Step:  1,
 		Func:  "avg",
 		Start: 0,
@@ -1722,7 +1722,7 @@ func TestStreamReadEndpoint(t *testing.T) {
 	})
 	testutil.Ok(t, err)
 
-	query2, err := remote.ToQuery(0, 14400001, []*labels.Matcher{matcher1, matcher3}, &storage.SelectHints{
+	query2, err := remote.ToQuery(0, 14400001, []*labels.Matcher{matcher1, matcher3}, &storage.SelectParams{
 		Step:  1,
 		Func:  "avg",
 		Start: 0,