diff --git a/go/query/query.go b/go/query/query.go
index db94545..0c2e83c 100644
--- a/go/query/query.go
+++ b/go/query/query.go
@@ -36,9 +36,9 @@
 )
 
 var (
-	invalidChar = regexp.MustCompile(`([^a-zA-Z0-9._\-])`)
-	keyRe       = regexp.MustCompile(`^,([a-zA-Z0-9._\-]+=[a-zA-Z0-9._\\-]+,)+$`)
-	paramRe     = regexp.MustCompile(`^[a-zA-Z0-9._\-]+$`)
+	invalidChar = regexp.MustCompile(`([^a-zA-Z0-9\._\-])`)
+	keyRe       = regexp.MustCompile(`^,([a-zA-Z0-9\._\-]+=[a-zA-Z0-9\._\\-]+,)+$`)
+	paramRe     = regexp.MustCompile(`^[a-zA-Z0-9\._\-]+$`)
 
 	QueryWillNeverMatch = errors.New("Query will never match.")
 )
@@ -90,10 +90,8 @@
 		return true
 	}
 	parts = parts[1 : len(parts)-1]
-	if !sort.IsSorted(sort.StringSlice(parts)) {
-		return false
-	}
 	lastName := ""
+	keys := []string{}
 	for _, s := range parts {
 		pair := strings.Split(s, "=")
 		if len(pair) != 2 {
@@ -103,8 +101,9 @@
 			return false
 		}
 		lastName = pair[0]
+		keys = append(keys, pair[0])
 	}
-	return true
+	return sort.IsSorted(sort.StringSlice(keys))
 }
 
 // MakeKey returns a structured key from the given map[string]string, or a
@@ -173,10 +172,8 @@
 		return map[string]string{}, nil
 	}
 	parts = parts[1 : len(parts)-1]
-	if !sort.IsSorted(sort.StringSlice(parts)) {
-		return nil, fmt.Errorf("Key is not valid, params are unsorted: %v", parts)
-	}
 	lastName := ""
+	keys := []string{}
 	for _, s := range parts {
 		pair := strings.Split(s, "=")
 		if len(pair) != 2 {
@@ -187,7 +184,13 @@
 		}
 		ret[pair[0]] = pair[1]
 		lastName = pair[0]
+		keys = append(keys, pair[0])
 	}
+
+	if !sort.IsSorted(sort.StringSlice(keys)) {
+		return nil, fmt.Errorf("Key is not valid, params are unsorted: %v", parts)
+	}
+
 	return ret, nil
 }
 
diff --git a/go/query/query_test.go b/go/query/query_test.go
index b925dfa..463894a 100644
--- a/go/query/query_test.go
+++ b/go/query/query_test.go
@@ -77,6 +77,11 @@
 			valid:  false,
 			reason: "Degenerate case.",
 		},
+		{
+			key:    ",browser=chrome,browser-version=106.0.5196.0,channel=canary,sub-test=date-format-xparb-SP,test=JetStream,type=sub-test,value=score,version=2,",
+			valid:  true,
+			reason: "Only check sort order on the key values, not on key=value, which breaks on this case between 'browser=' and 'browser-'",
+		},
 	}
 	for _, tc := range testCases {
 		if got, want := ValidateKey(tc.key), tc.valid; got != want {
@@ -378,6 +383,21 @@
 			hasError: true,
 			reason:   "Empty string",
 		},
+		{
+			key: ",browser=chrome,browser-version=106.0.5196.0,channel=canary,sub-test=date-format-xparb-SP,test=JetStream,type=sub-test,value=score,version=2,",
+			parsed: map[string]string{
+				"browser":         "chrome",
+				"browser-version": "106.0.5196.0",
+				"channel":         "canary",
+				"sub-test":        "date-format-xparb-SP",
+				"test":            "JetStream",
+				"type":            "sub-test",
+				"value":           "score",
+				"version":         "2",
+			},
+			hasError: false,
+			reason:   "Only check sort order on the key values, not on key=value, which breaks on this case between 'browser=' and 'browser-'",
+		},
 	}
 	for _, tc := range testCases {
 		p, err := ParseKey(tc.key)