from typing import Optional
from typing import Dict
import re


def search_query_step(line: str) -> Optional[Dict[str, str]]:
    """
    Return any S3-based tables found in the query step (part of a query plan).

    >>> plan = '-> S3 Nested Subquery ex_schema.table location:"s3://bucket/..."'
    >>> search_query_step(plan)
    {'s3_table': 'ex_schema.table'}
    >>> plan = '-> S3 Seq Scan ex_schema.table location:'
    >>> search_query_step(plan)
    {'s3_table': 'ex_schema.table'}
    >>> plan = '-> S3 Seq Scan ex_schema.table alias location:'
    >>> search_query_step(plan)
    {'s3_table': 'ex_schema.table'}
    >>> plan = '-> XN Seq Scan on table'
    >>> search_query_step(plan)
    {'xn_table': 'table'}
    """
    ws_re = re.compile(r"\s+")
    # Note that in the regex below, whitespace outside '[ ]' or '\ ' is ignored.
    scan_re = re.compile(
        r"""->[ ]
            S3\ Nested\ Subquery\ (?P<s3_table_nested>\w+\.\w+)\ location:
            | S3\ Seq\ Scan\ (?P<s3_table_seq>\w+\.\w+)(?:\ \w+)?\ location:
            | XN\ Seq\ Scan\ on\ (?P<xn_table>\w+)
        """,
        re.VERBOSE,
    )
    match = scan_re.search(ws_re.sub(" ", line))
    if not match:
        return None
    values = match.groupdict()
    if values["s3_table_nested"]:
        return {"s3_table": values["s3_table_nested"]}
    if values["s3_table_seq"]:
        return {"s3_table": values["s3_table_seq"]}
    if values["xn_table"]:
        return {"xn_table": values["xn_table"]}
    return None