[Feature] [BE] Supporting partial pattern match

[baiqiushi]

@HazelYuAhiru , please copy the example query pair in your slide to describe what the partial pattern match means and how it can help to make our rules more general.

[HazelYuAhiru]

Case 1:

As shown in the graph above, partial matching involves matching the rule to a subtree of the input query, rather than to the entire input query tree. For example, consider two rules in the knowledge base:

# Rule 1:
pattern = '<x1> = <x2> OR <x1> = <x3>'
rewrite = '<x1> IN (<x2>, <x3>)'

# Rule 2:
pattern = '<x1> IN (<<y1>>) OR <x1> = <x4>'
rewrite = '<x1> IN (<<y1>>,  <x4>)'

If we are given the input query:

Q =    “x = 1 or x = 2 or x = 3 or x = 4”

We first partially match rule 1, so Q becomes:

Q1 =   “x IN (1,2) or x = 3 or x = 4”

Then we keep applying rule 2 to get:

Q2 = 'x IN (1,2,3) or x = 4'
Q3 = 'x IN (1,2,3,4)'

Case 2: "Reversed" Partial Matching

In this case, we match the entire input query tree to a subtree of a rule pattern. (However, I think this partial match only works in specific cases, such as when C3 does not play a "significant role" in the rule.).

For example, consider a rule in the knowledge base:

# pattern:
SELECT DISTINCT <<x2>> FROM <<x1>> WHERE <<y1>>
# rewrite:
SELECT <<x2>> FROM <<x1>> WHERE <<y1>> GROUP BY <<x2>>

If we are given the input query:

SELECT DISTINCT <<x2>> FROM <<x1>> 

Without partial matching, the above rule cannot apply since the input query is missing a WHERE clause. However, with partial matching, we can partially apply the rule without WHERE and rewrite the query as:

SELECT <<x2>> FROM <<x1>>  GROUP BY <<x2>>

This optimization aligns the query better with human understanding.

[baiqiushi]

I meant the other one for multiple ORs into an IN predicate. By partial, we mean if the input query has a tree with root R and three children C1, C2, C3, and the pattern in the rule is a tree with root R and two children C1 and C2, then the input query tree can partially match and replace the C1 and C2 with a new child D1, but the original non-matching child C3 won’t be affected. And the final result is the query tree becomes root R and two children D1 and C3. What you described is the reversed version.

…

On Thu, Jan 16, 2025 at 14:33 Yihong Yu ***@***.***> wrote: Partial matching refers to the ability to partially match a rule to an input query, accepting a match from a subtree rather than requiring the entire parsing tree. This approach gives greater flexibility, enabling more rules in the knowledge base to apply to input queries that partially conform to a rule pattern. For example, consider a rule in the knowledge base: # pattern: SELECT DISTINCT <<x2>> FROM <<x1>> WHERE <<y1>> # rewrite: SELECT <<x2>> FROM <<x1>> WHERE <<y1>> GROUP BY <<x2>> If we are given the input query: SELECT DISTINCT <<x2>> FROM <<x1>> Without partial matching, the above rule cannot apply since the input query is missing a WHERE clause. However, with partial matching, we can partially apply the rule and rewrite the query as: SELECT <<x2>> FROM <<x1>> GROUP BY <<x2>> This optimization aligns the query better with human understanding. — Reply to this email directly, view it on GitHub <#53 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AB542BWBG67NIHTR2FUCSIL2LAXU7AVCNFSM6AAAAABVKLUZDWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKOJXGA2DGMBXGY> . You are receiving this because you were assigned.Message ID: ***@***.***>

[HazelYuAhiru]

I meant the other one for multiple ORs into an IN predicate.

By partial, we mean if the input query has a tree with root R and three
children C1, C2, C3, and the pattern in the rule is a tree with root R and
two children C1 and C2, then the input query tree can partially match and
replace the C1 and C2 with a new child D1, but the original non-matching
child C3 won’t be affected. And the final result is the query tree becomes
root R and two children D1 and C3.

What you described is the reversed version.
…

Got it! I'll edit my comment to align with this definition.