All the code you need to mess with query params successfully. Works for pretty much any scenario, including python 2 AND 3.

query_params.py

#
# This is for python 2/3 compatibility. 
#
try:
    import urlparse
    from urllib import urlencode
except:
    import urllib.parse as urlparse
    from urllib.parse import urlencode



# URL = 'https://foo.com'
URL = 'https://foo.com?hello=world'

# First we parse the url into its constituent parts. Under the hood this logic is based on RFCs :)
PARSED = urlparse.urlparse(URL)

# Now we got some new query params that came from somewhere...
# This can contain any key/value pairs you want.
NEW_PARAMS = dict(
    relay_state=True,
    token='<token>',
    # hello='override',
)

# This extracts the existing query params from the URL into a dict.
EXISTING_PARAMS = urlparse.parse_qs(PARSED.query)

# This combines NEW and EXISTING params into a new dict.
# This prefers NEW_PARAMS to EXISTING ones if there is a collision.
ALL_PARAMS = dict(
    (k, v) for d in (EXISTING_PARAMS, NEW_PARAMS)
    for k, v in d.items()
)

# This creates an object representation of our new URL.
PARSED = PARSED._replace(query=urlencode(ALL_PARAMS, doseq=True))

# Print it!
print(urlparse.urlunparse(PARSED))