A Tiny SQL Engine

Write query(records, sql) that runs a small SQL query over records, a list of dictionaries that all have the same fields, and returns the result rows as a list of tuples. Field values are whole numbers or strings.

A query has this shape, where the parts in square brackets are optional and always come in this order:

SELECT columns [WHERE condition] [ORDER BY field [ASC|DESC], ...] [LIMIT n]

• columns is * or field names separated by commas. Each result row is a tuple of those fields' values, in that order; * means every field, in the records' own key order.
• WHERE keeps the records for which the condition is true. A condition is made of comparisons field op value, where op is one of =, !=, <, <=, >, >= and value is a whole number (possibly negative) or text in single quotes, such as 'Lima'. Comparisons are joined with AND and OR; as in SQL, AND binds tighter than OR, and parentheses group parts of a condition. A number field is always compared with a number and a text field with text, in Python's string order.
• ORDER BY sorts by one or more fields separated by commas, each followed by ASC (smallest first, also used when neither word is written) or DESC. Records that are equal on every ORDER BY field keep their order from records. Without ORDER BY, rows come in the order of records.
• LIMIT n keeps only the first n rows, where n is a whole number from 0 up.

Keywords (SELECT, WHERE, AND, OR, ORDER, BY, ASC, DESC, LIMIT) may be written in any case. Field names are made of letters, digits and underscores, are case-sensitive, and are never keywords. Spaces can be left out around symbols (age>=30), and text in quotes may contain spaces but no quote marks. Every field a query names exists in the records.

If the query does not follow this shape, for example a missing value, an unknown operator, a parenthesis or quote that is never closed, or extra words at the end, raise ValueError.

Examples

people = [
    {'name': 'Ana', 'age': 34, 'city': 'Lima'},
    {'name': 'Ben', 'age': 28, 'city': 'Oslo'},
    {'name': 'Cy', 'age': 45, 'city': 'Lima'},
    {'name': 'Dee', 'age': 34, 'city': 'Rome'},
]
query(people, 'SELECT name, age WHERE age > 30 ORDER BY age DESC LIMIT 2')
# returns [('Cy', 45), ('Ana', 34)]
query(people, "select name where age < 30 or city = 'Lima' and age > 40")
# returns [('Ben',), ('Cy',)]
query(people, 'SELECT * ORDER BY city, age DESC')
# returns [('Cy', 45, 'Lima'), ('Ana', 34, 'Lima'), ('Ben', 28, 'Oslo'), ('Dee', 34, 'Rome')]

In the first query Ana and Dee are both 34; Ana comes first in people, so she takes second place. The second condition means age < 30 OR (city = 'Lima' AND age > 40).

Constraints

• Up to 50,000 records, and queries up to 1,000 characters long.