We talk here sometimes about how to test SQL dialects with tools like TLP and PQS. One really nice property of those tools is that they let you treat the database like a blackbox.

I'm tinkering with a little SQL planner to mess around with ideas and one feature I added very early was an explicit optimization fence operator that simply blocks any optimizations:

In a query like this:

SELECT * FROM (SELECT a, b, c, d FROM foo, bar WHERE a = c) WHERE b = 1

Which, since I don't have a SQL parser yet, I have to express like this:

q = (join(
    [Scan("foo", [a, b]), Scan("bar", [c, d])],
    [{a, c}],
).filter([ColRef(b).eq(Const(1))]))

As we expect, the b = 1 filter gets down into the join:

Join [a = c]
├── Filter (b = 1)
│   └── Scan foo [a, b]
└── Scan bar [c, d]\

But if we introduce a Fence, we can stop that:

q = (join(
    [Scan("foo", [a, b]), Scan("bar", [c, d])],
    [{a, c}],
).fence().filter([ColRef(b).eq(Const(1))]))

Filter (b = 1)
└── Fence
    └── Join [a = c]
        ├── Scan foo [a, b]
        └── Scan bar [c, d]

This is a useful tool to have, it leads to a very simple metamorphic test: inserting a fence operator somewhere in the tree prior to optimization should be a no-op. Then, with a query generator and a steady hand, we can find bugs.

As an example, I can introduce a bug. Here's a rule that merges to adjacent Filter operators into one. It's meant to be called as a constructor to a Filter, so there's an implied Filter on top of it already:

@rule("merge_filters")
def merge_filters(source, preds):
    """Collapse nested Filters into a single Filter."""
    if isinstance(source, Filter):
        return source.source.filter(source.predicates + preds)
    return None

This is the rule that turns queries like this:

    q = Scan("foo", [a, b]).filter([ColRef(a).eq(Const(1))]).filter([ColRef(b).eq(Const(2))])

Into results like this:

Filter (a = 1) AND (b = 2)
└── Scan foo [a, b]

If we break the rule by, say, throwing away one of the filters instead:

@rule("merge_filters")
def merge_filters(source, preds):
    """Collapse nested Filters into a single Filter."""
    if isinstance(source, Filter):
        return source.source.filter(source.predicates)
    return None

We can get a nice example of the breakage from a generated query. If you're using a high-quality testing library for something like this (I'm using Hypothesis) you can even get a nice, simplified query instead of something large:

E       unoptimized:
E       Aggregate [a0 := count(t0c0)]
E       └── Filter (t0c0 = t0c0) AND (t0c0 < t0c0)
E           └── Fence
E               └── Filter (t0c0 = t0c0)
E                   └── Scan t0 [t0c0]
E       fenced:
E       Aggregate [a0 := count(t0c0)]
E       └── Filter (t0c0 = t0c0) AND (t0c0 < t0c0)
E           └── Fence
E               └── Filter (t0c0 = t0c0)
E                   └── Scan t0 [t0c0]
E       defenced:
E       Aggregate [a0 := count(t0c0)]
E       └── Filter (t0c0 = t0c0)
E           └── Scan t0 [t0c0]

This sort of accomplishes what TLP sets out to do: gives us contexts in which certain optimization rules run and don't run.

This particular technique has its limitations, though. For example, it's blind to bugs in optimization rules that don't span multiple operators. Here's a bug will not be caught by this technique.

Filter expressions in my IR are lists of conjuncts, and an empty list of conjuncts is trivially true, so I have a rule that detects such a thing and replaces a Filter with no predicates with its input:

def eliminate_trivial_filter(source, preds):
    """Replace a filter with no predicates with its source."""
    if len(preds) == 0:
        return source
    return None

If we break this rule by changing its source to:

def eliminate_trivial_filter(source, preds):
    """Replace a filter with no predicates with its source."""
    if len(preds) < 2:
        return source
    return None

We'll now throw away filters that have a single conjunct in them. Not good! Broken! And no positioning of fencing will catch this, we need something stronger. This suggests a technique which is actually a generalization of the previous one.

Remember; we are totally in control of the optimization process here. So we don't actually have to do this whole song-and-dance of tickling the tree by reshaping it: we can directly just enable and disable rules.

So our new test can be: an input unoptimized query, combined with a list of rules to disable. Updating the test to work this way, we can catch it:

E       optimized:
E       Scan t0 [t0c0, t0c1]
E       disabled ['eliminate_trivial_filter']:
E       Filter (t0c0 < t0c0)
E       └── Scan t0 [t0c0, t0c1]

Speaking from experience, this particular trick has its issues: many optimizations are load-bearing. Sometimes, if you turn off stuff like "optimize a filter on top of a cross product into a regular join," queries can become so slow that they won't finish. So it's not a free lunch, there's problems to be solved yet. But I think it's cool!

These are just some testing thoughts I've been having while messing around with this SQL dialect. Maybe I'll keep messing around with it and provide updates. Have a good one.