Hello, I would appreciate any feedback or assistance with understanding how to navigate tree-like structures to handle custom "node" logic such as:

• Building a meaningful tree structure of nodes who are aware of their parent/ child relations.
• Moving a node into another tree if it meets a certain condition.
• Calucating the node's condition based of its parent, or grandparent, so on...

I'm unfamiliar with handling tree structures in an efficient way without over complicating it.

As much as I would like to simplify the issue I'm having, I believe it would remove important context. Below is the exact situation I'm facing with my own theorized solution at the end. Please let me know if I can elaborate on anything. Thank you! (apologies for the long write...)

Context

I am handling T-SQL that has been parsed into an AST using the sqlparser-rs crate. The goal is to re-arrange the AST into SQL that uses the OPENQUERY() function for four part named tables that are accessed by a linked server.

Example input, a remote table being joined on a local table with a WHERE clause.

SELECT * FROM dbo.local AS l
INNER JOIN server.catalog.dbo.remote AS r ON r.ID = l.ID
WHERE l.Type = 'New' AND r.Active = 1

The output, the remote table and its WHERE condition moved into an OPENQUERY().

SELECT * FROM dbo.local AS l
INNER JOIN OPENQUERY([cloud], 'SELECT * FROM dbo.remote AS r WHERE r.Active = 1') AS r ON r.ID = l.ID
WHERE l.Type = 'New'

Challenge

The challenge I'm experiencing is re-arranging WHERE clauses due to the AST structure, as it is parsed into a single binary tree (of binary trees...). As shown in the example above the goal is to move specific conditions into the OPENQUERY() if it is valid (meaning the re-arranged query will yield the same results as the original). I'm familiar with the certain rule set on what conditions are valid to move, but I'm unsure on how to actually implement this programmatically due to the structure.

To explain the binary tree structure here is the exact enum variant BinaryOp that encapsulates all conditions into a single BinaryOp along with a few parsing examples (the diagrams are the BinaryOp variant).

enum Expr {
    // ...
    BinaryOp {
        left: Box<Expr>,
        op: BinaryOperator,
        right: Box<Expr>,
    },
    // ...
}

Examples

Example 1.

WHERE l.column = 'value'

Example 2.

WHERE l.column = 'value' AND l.column = 'value'

Example 3.

WHERE l.column = 'value' AND l.column = 'value' OR r.other <> 'value'

The crate exposes two APIs for visiting the AST structure, specifically for the Expr enum. The pre_visit_expr() and post_visit_expr() which are very helpful. Although, I'm unsure how to utilize them to properly re-arrange the WHERE clause.

Potential solution?

Ultimately I need to re-arrange the original WHERE clause so that all valid conditions have been moved outside of it, and eventually placed into the OPENQUERY(). This leaves the original with conditions, and the remote query with conditions. If either the original or remote query end up not having any conditions, it can be removed entirely. I can handle all of that logic fine, I'm only having issues knowing how to navigate the AST Expr tree of BinaryOps in a meaningful way.

The solution I've been exploring is building a mirrored tree of the original using my own custom types that add this meaning I'm looking for:

• A parent and child relation.
• If the node is a left or right sided relation.
• If the BinaryOp is a real operation using values or a grouping operating (such as AND/OR).
• A reference back to the original.
• etc...

Then perform a few passes through this mirrored tree to evaluate if certain nodes are valid to be re-arranged or not. (Such as an AND can be split with only one side being valid, and the other invalid, but an OR requires both sides to be valid). Then finally re-constructing a real BinaryOp tree from my mirrored version to actually use in the AST.

1 post - 1 participant

Read full topic