Region redirect does not honor scheme
Bucket in us-west-2

```
$ aws s3api get-bucket-location --bucket jamesls-test-sync
{
    "LocationConstraint": "us-west-2"
}
```

Specifying an http endpoint to us standard instead of us-west-2:

```
aws s3 cp /tmp/foo.txt s3://jamesls-test-sync/ --endpoint-url http://s3.amazonaws.com/ --debug
```

I can see we have the redirect logic now, but I can see it getting redirected from http to https:

```
2016-07-08 08:57:31,621 - Updating URI from http://s3.amazonaws.com/jamesls-test-sync to https://s3-us-west-2.amazonaws.com/jamesls-test-sync
```

I would expect that if we're going to change the URl we should still honor the scheme they've requested right?

cc @JordonPhillips 

diff --git a/botocore/auth.py b/botocore/auth.py
index 6b21abf3c..77b433e17 100644
--- a/botocore/auth.py
+++ b/botocore/auth.py
@@ -171,7 +171,6 @@ class SigV4Auth(BaseSigner):
         return header_map
 
     def canonical_query_string(self, request):
-        cqs = ''
         # The query string can come from two parts.  One is the
         # params attribute of the request.  The other is from the request
         # url (in which case we have to re-split the url into its components
@@ -180,33 +179,31 @@ class SigV4Auth(BaseSigner):
             return self._canonical_query_string_params(request.params)
         else:
             return self._canonical_query_string_url(urlsplit(request.url))
-        return cqs
 
     def _canonical_query_string_params(self, params):
         l = []
-        for param in params:
+        for param in sorted(params):
             value = str(params[param])
             l.append('%s=%s' % (quote(param, safe='-_.~'),
                                 quote(value, safe='-_.~')))
-        l = sorted(l)
         cqs = '&'.join(l)
         return cqs
 
     def _canonical_query_string_url(self, parts):
-        buf = ''
+        canonical_query_string = ''
         if parts.query:
-            qsa = parts.query.split('&')
-            qsa = [a.split('=', 1) for a in qsa]
-            split_qsa = []
-            for q in qsa:
-                if len(q) == 2:
-                    split_qsa.append('%s=%s' % (q[0], q[1]))
-                elif len(q) == 1:
-                    split_qsa.append('%s=' % q[0])
-            if len(split_qsa) > 0:
-                split_qsa.sort()
-                buf += '&'.join(split_qsa)
-        return buf
+            # [(key, value), (key2, value2)]
+            key_val_pairs = []
+            for pair in parts.query.split('&'):
+                key, _, value = pair.partition('=')
+                key_val_pairs.append((key, value))
+            sorted_key_vals = []
+            # Sort by the key names, and in the case of
+            # repeated keys, then sort by the value.
+            for key, value in sorted(key_val_pairs):
+                sorted_key_vals.append('%s=%s' % (key, value))
+            canonical_query_string = '&'.join(sorted_key_vals)
+        return canonical_query_string
 
     def canonical_headers(self, headers_to_sign):
         """
diff --git a/tests/unit/auth/test_signers.py b/tests/unit/auth/test_signers.py
index b66609735..f6a7468d5 100644
--- a/tests/unit/auth/test_signers.py
+++ b/tests/unit/auth/test_signers.py
@@ -290,6 +290,31 @@ class TestS3SigV4Auth(unittest.TestCase):
         self.assertEqual('marker=%C3%A4%C3%B6%C3%BC-01.txt&prefix=', cqs)
 
 
+class TestSigV4(unittest.TestCase):
+    def setUp(self):
+        self.credentials = botocore.credentials.Credentials(
+            access_key='foo', secret_key='bar')
+
+    def test_canonical_query_string(self):
+        request = AWSRequest()
+        request.url = (
+            'https://search-testdomain1-j67dwxlet67gf7ghwfmik2c67i.us-west-2.'
+            'cloudsearch.amazonaws.com/'
+            '2013-01-01/search?format=sdk&pretty=true&'
+            'q.options=%7B%22defaultOperator%22%3A%20%22and%22%2C%20%22'
+            'fields%22%3A%5B%22directors%5E10%22%5D%7D&q=George%20Lucas'
+        )
+        request.method = 'GET'
+        auth = botocore.auth.SigV4Auth(
+            self.credentials, 'cloudsearchdomain', 'us-west-2')
+        actual = auth.canonical_query_string(request)
+        # Here 'q' should come before 'q.options'.
+        expected = ("format=sdk&pretty=true&q=George%20Lucas&q.options=%7B%22"
+                    "defaultOperator%22%3A%20%22and%22%2C%20%22fields%22%3A%5B"
+                    "%22directors%5E10%22%5D%7D")
+        self.assertEqual(actual, expected)
+
+
 class TestSigV4Resign(unittest.TestCase):
 
     maxDiff = None
['botocore/auth.py', 'tests/unit/auth/test_signers.py']