Learning how to navigate/ modify tree-like structure with parsed AST SQL

noah_g · July 5, 2026, 12:44am

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 operation (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. (Ex. 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 construct a real BinaryOp tree from my mirrored version to actually use in the AST.

nerditation · July 5, 2026, 12:33pm

a disclaimer first, I don't know much about SQL, but I'd like share some thoughts based on my own experiences. feel free to follow up with informations and questions if you find something interesting for your particular problem.

I would say, it's best to avoid explicit parent links if possible. sometimes, it is unnecessary to store a back link in the node if you rearrange the way your algorithm traverses the tree. so it depends on the algorithms.

due to the ownership model and borrow checker, parent links cannot work the same way as "normal" pointers, because they create cycles, which essentially turns a tree into a graph. if your tree must have parent links however, they need some special treatments.

if you use owning pointers (Box, Rc, Arc) and containers (Vec) for the child links, the parent link is usally implemented in two ways: raw pointers or the weak counterpart of the reference counted pointers.

but it is possible to allow cycles in the graph, usually the nodes are stored in a centralized container, and identified by their index or unique key, as opposed to their memory address, so all the links are integers instead of pointers. a similar idea is to make nodes allocated from an arena allocator, and use something like Cell<&'arena Node> for the link type, in which case you typically also need Cell for the fields of the node type too.

the "transplant" operation can be decomposed to a remove operation and an insert operation, both of which can be easily implemented.

this is a bit tricky, sometimes impossible, in (safe) rust. again, it depends on the algorithm. for example, you cannot have &mut references to a node and its parent node at the same time, it's plain UB.

in a typical recursive tree traversal with &mut access to the node, the information of the parent nodes (and all the ancestor nodes along the path) do exist, but they live in the caller's stack frames and are inaccessible, that's why the borrow checker accepts such recursion.

that is not to say, you cannot access the ancestor nodes at all, you just cannot have a &mut reference to the whole node, you can still have references (including &mut references) to fields of the nodes that are disjoint with the child links. this is required for certain algorithms, for example, when you need to check if a node is on the left-most path. but you do need to explicitly pass the information down as you recursively descend into child nodes.

did you know the technique with layered trees, used in some text editor tools for resillient parsing (such as rust-analyzer)? these are usually referred as green tree and red tree. your idea sounds to me very similar to a red tree (or I would like to call it an "overlay" tree). its also the similar idea of zippers in functional languages.

note, here I'm mainly refering to algorithms with in-place mutations. there's no problems at all in rust to write functional style tree operations, by which I mean pure, side effect free, functions that take an immutable tree as input and returns a new tree as output. in most cases, if the problem fits, this is the first solution I reach for.

I don't understand your particular problem of the BinaryOp validity, but the solution you described sounds very reasonable to me.

some algorithms require complex traversal order, and I would prefer to decompose it into multiple traversal passes with simple traversals.

btw, your example diagrams for the expression parser is very helpful to understand the data shape, but I don't have the domain knowledge to figure out what's the transformation are supposed to do with the AST, and the description of AND OR splitting the sides is very vague to me.

what do you mean by "split" one side valid and other invalid? what happens to the subtree after the "split", is the "invalid" subtree removed? or moved to a different location? what about the "valid" side? examples would be great for an outsider to grasp the problem domain quickly.

ProgramCrafter · July 5, 2026, 12:45pm

From what I understood, there is SQL query loading data from a remote source and filtering it; some of the filters can be evaluated fully on remote side, which would make it faster and consume less network bandwidth, and therefore they must be moved into "OPENQUERY" part.

marlez · July 5, 2026, 3:28pm

Given, (1) your objective:

(2) the example you've provided:

Details

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'

(3) the AST which sqlparser provides for you, as well as (4) a rather non-trivial conditional update of the underlying syntax tree, clearly not limited to "rearranging" a few WHERE clauses alone:

neither of the two _visit_expr(), nor matching on any of BinaryOp trees seem sufficient here. Visiting individual expressions is great for mapping/updating those very individual expressions, not for transforming the entire statement (SELECT) or some of its parts (server.catalog.dbo.remote) depending on the exact arrangement/sequence of the clauses within it (WHERE).

Choose the statements you want to be dealing with, first: is it only SELECT, or do you need/want to be able to update every INSERT, UPDATE, and DELETE just as well? Figure out exactly which of the clauses need to be passed along into your OPENQUERY function, as well as how they should be "moved", if at all: do you need to account only for the WHERE's, or something else too?

Match on/visit the statements you're interested in, break them down into their constituent parts, reconstruct your OPENQUERY with the clauses you want to account for; then std::mem::swap the &mut Statement with your new &mut modified version. Consider "flattening" any of the binary expressions encountered into a single list of individual clauses, separating the "required" top-level AND's from all of the OR's; to avoid dealing with all the "branches". In your example:

WHERE l.Type = 'New' AND r.Active = 1
--> 1. assume any non-r clauses to be true
TRUE AND r.Active = 1
--> 2. becomes
r.Active = 1
--> 3. pass into OPENQUERY(..)

In a bit more complex of a case, you might have:

WHERE (l.Count > 5 OR r.Count = 1) 
  AND (r.Active = 0 OR l.Active = 1) 
  AND (r.Type = 'Type')
--> 1. same as above:
(TRUE OR r.Count = 1) AND (r.Active = 0 OR TRUE) AND (r.Type = 'Type')
--> 2. becomes:
TRUE AND TRUE AND r.Type = 'Type'
--> 3. becomes:
r.Type = 'Type'
--> 4. pass into to OPENQUERY(..)

noah_g · July 5, 2026, 8:25pm

Thank you for your response, I wasn't aware of the red/ green layered trees! I'll do my best to explain the problem domain without going too deep into OPENQUERY() (I believe it can be somewhat of a niche topic in SQL).

As @ProgramCrafter stated in their reply using OPENQUERY() for remote accessed tables is for performance, as it will be faster than using the four part name. However the cost of using OPENQUERY() is local context, due to the string SQL that is passed to the linked server. The linked server handles the query entirely on its end and then returns the result, meaning the remote server is only aware of its own remote tables (which is local relative to itself).

This query uses the four part name and will work with local and remote context mixed together.

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

This query will not work, because the remote sever does not know anything about the dbo.local table.

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

So instead moving only what the remote server will know into an OPENQUERY() and keeping everything it doesn't know outside of it will work, as long as the overall query returns the same results as the original (as performance isn't worth different results).

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'

The problem domain I'm facing is how to handle the WHERE clause specifically. I've already been successful with moving the remote tables (and remote joins) into an OPENQUERY(), but determining which filtering conditions to bring with it can be a bit more complex. I believe the data shape of the BinaryOp variant makes sense, but now I'll provide a few examples on what conditions can be moved over or not.

At the moment anything that is filtering on the remote table's columns with a hardcoded value should be brought over if it the end result query yields the same results.

-- Input, one binary operation.
SELECT * FROM server.catalog.dbo.remote AS r
WHERE r.Active = 1

-- Output, it is moved into the OPENQUERY().
SELECT * FROM OPENQUERY([server], 'SELECT * FROM server.catalog.dbo.remote AS r WHERE r.Active = 1') AS r

This original example uses an AND which is also fairly simple, you can see what I mean by "splitting" the AND's conditions if one side is valid to bring over and the other is invalid. This splitting is allowed because the results of the new query are still the same as the original.

-- Input, three binary operations.
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

-- Output, the AND isn't totally valid as one condition is local. Splitting is allowed.
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'

Lastly here is an example of using an OR where splitting isn't allowed, as it will change the results of the query. (Note, in this case performance isn't ideal and the original four part name may be faster.)

-- Input, three binary operations.
SELECT * FROM dbo.local AS l
INNER JOIN server.catalog.dbo.remote AS r ON r.ID = l.ID
WHERE l.Type = 'New' OR r.Active = 1

-- Output, the OR isn't totally valid as one condition is local. The entire condition must not be moved.
SELECT * FROM dbo.local AS l
INNER JOIN OPENQUERY([cloud], 'SELECT * FROM dbo.remote AS r') AS r ON r.ID = l.ID
WHERE l.Type = 'New' OR r.Active = 1

To respond to your information, the layered trees sound awesome! I'm still reading into it and wrapping my mind around it, but the green tree sounds of interest to me because it only moves downwards. Since these nodes would contain the meaning behind these BinaryOps, it could be traversed downwards a few times to determine validity. Although again, I'm still wrapping my mind around it.

Going with a mirrored tree solution, it would be created from the original query's WHERE clause (with references or clones of the actual Expr enum). After evaluating the validity of each node with a few passes, it could be re-arranged with another empty tree to the side. I'd imagine that anything that is valid from the first tree is moved to the second tree. Both trees are turned into actual BinaryOp variants and the first is used by the query outside of the OPENQUERY(), and the second is used for the query inside of it. If either of them have no nodes, it can be empty. (Thankfully the AST represents this with an Option<Expr>).

noah_g · July 5, 2026, 9:54pm

Yes, you are correct! I'm currently on the WHERE clause portion of moving remote tables into an OPENQUERY(). I have already been able to target a specific table in the original query and mutate it into an OPENQUERY() with a newly made Select struct. This new struct contains all of the collected information from the original query (such as what remote table(s) are being selected from, the columns to select, and the conditions to bring over). I then ensure that whatever is collected into the OPENQUERY() is removed from the original query.

I have decided that only SELECT statements will be turned into OPENQUERY() (if needed), anything else will be ignored and returned as the original query. I'm accounting for the WHERE clause before I move on to bringing remote projections (the columns) into the OPENQUERY(), because I'll work on having the projections be brought over at a minimum:

-- Input, the remote query is being filtered on a column that isn't being projected.
SELECT l.ID, l.Type, r.InsertTime 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

--> 1. Moved the remote condition.
SELECT l.ID, l.Type, r.InsertTime 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'

--> 2. Copied the remote projections into the OPENQUERY().
SELECT l.ID, l.Type, r.InsertTime FROM dbo.local AS l
INNER JOIN OPENQUERY([cloud], 'SELECT r.InsertTime FROM dbo.remote AS r WHERE r.Active = 1') AS r ON r.ID = l.ID
WHERE l.Type = 'New'

Here is the same example but with an OR, both column projections are brought into the OPENQUERY() because of the WHERE condition not being valid.

--> 1. Can't move the remote condition, as it would change the query results.
SELECT l.ID, l.Type, r.InsertTime FROM dbo.local AS l
INNER JOIN OPENQUERY([cloud], 'SELECT _ FROM dbo.remote AS r') AS r ON r.ID = l.ID
WHERE l.Type = 'New' OR r.Active = 1

--> 2. Copied the remote projections into the OPENQUERY().
SELECT l.ID, l.Type, r.InsertTime FROM dbo.local AS l
INNER JOIN OPENQUERY([cloud], 'SELECT r.InsertTime, r.Active FROM dbo.remote AS r') AS r ON r.ID = l.ID
WHERE l.Type = 'New' OR r.Active = 1

This is an awesome approach! Do you have any advice/ direction on turning the BinaryOp tree structure into this single list? Would it be a Vec of operations with a common grouping?

// Psudeo
struct OperationItem {
    grouping: Option<Group>, // AND, OR
    expression: Expr,
}

The only questions I have with this approach is (1) how to reconstruct the list back into a root Expr and (2) how I could preserve the original query's WHERE clause with anything that is supposed to be left over? Say your original example of flattening it:

The r.Active = 1 is moved into the OPENQUERY(), but what about the l.Type = 'New' that is supposed to stay outside. Is it just remaining in the original list? I'm assuming I would use the original list for the local WHERE clause after it is turned back into an Expr.

Thank you for your input!

nerditation · July 6, 2026, 1:46am

with these detailed examples, now I understand what you mean by "valid".

it was confusing to me before because I don't know what OPENQUERY is, and words like "re-arange", "split", "leftover" gave me the wrong impression.

so let me try to re-state the problem in another way, a little bit more abstract, which should hopefully give some different perspectives and insights to the problem.

given an expression e1 (a parsed AST node type Expr) of variables from two sets L (for "local") and R (for "remote"), which evaluates a boolean value TRUE or FALSE, construct a expression e2 such that:

e2 contains only variables in R;

so it can be evaluated independently without L
for all possible values of L and R, if e1 evaluates to TRUE, e2 must evaluates to TRUE

the condition is one directional, the converse does not hold: e2 is allowed to evaluate to TRUE even if e1 evaluates to FALSE

in other words, as a filter condition, e2 is allowed to give "false positive" but no "false negative".
(informal) e2 should resemble a "simplified" view of e1.

this criteria is hard to formally specify, but it should be intuitively understandable.

with this in place, we can inductively define a procedure f that mechanically transforms an Expr (in pseudo code):

f: Expr L R -> Expr R
f FALSE = FALSE
f TRUE = TRUE
f x where x: L = TRUE
f x where x: R = x
f (x AND y) = (f x) AND (f y)
f (x OR y) = (f x) OR (f y)

I use a haskell-like syntax, but I think it is straghtforward to understand without actually knowing any haskell.

if you extend this formulation with the truth table of AND and OR (a.k.a. shortcircuit simplification), you naturally get what @marlez shows.

btw, this transformation is localized, you can implement it recursively as a simple traversal in post order, no need to access the ancestor nodes. of course you can do additional optimization passes, but the basic transformation I described needs only a single pass.

a short word for the "leftover" part. this is short because if you think about it, it is pretty much the same as we have already done, but with key differences: e3 is NOT limited to only L, and no "false positive" allowed for the final result:

given expressions e1 and e2 as defined previously, find an expression e3 in L and R such that e2 AND e3 = e1 for all possible L and R

the exact formula is left as an exercise.

hint:

baseline: because the way we constructed e2, the identity transformation is guaranteed to be correct.
you can take advantage of the fact that for any subexpression in R only, e2 is guaranteed to evaluate to TRUE

side note:

did you notice how I make this definition in a declarative way? I use "construct" and avoid verbs like "re-arrange", "split", or "move". I feel like imperative thinking focuses on the implementation details but misses the bigger picture.

ultimately, your goal is to construct an Expr for the OPENQUERY() as the WHERE clause (and as a bonus, to simplify the original WHERE clause), but if you only think in terms of "splitting", "valid to move", or "invalid to be leftover", you'll have a hard time reasoning why the transformation will give the correct result, or you might miss optimizaiton opportunity due because you want to be convervative.

marlez · July 6, 2026, 10:17am

My first instinct would be to recurse through the tree itself first, as @nerditation pointed out:

Every TRUE AND/OR EXPR(r) can be flattened in-place into an EXPR(r) (for AND) or a plain (TRUE for OR), as established earlier. Look up a CNF/DNF solver (or implement one yourself, if you're up for a challenge) to reduce the final tree form into a plain AND of OR's / OR of AND's, as necessary.

I would do the same: keeping the original list intact is the easiest option here. If the CNF route is up your alley, feel to experiment with the reduction of the entire original list into a normalized AND of OR's as well. Any sub-clause in the final normalized form that only deals with your remote r will always be safe to "move" from your original SELECT into your OPENQUERY mapping.

Topic		Replies	Views
Most efficient way to convert relational data to nested Rust structs	8	1242	April 20, 2024
Isn't Polars code too unreadable? help	16	4501	November 26, 2022
Suggestions for graph API code review	4	626	June 22, 2021
Getting rid of recursive AST evaluation in a custom language help	5	984	December 11, 2022
Kuchiki: a (Edit: no longer vaporware) HTML/XML tree manipulation library	57	24104	June 23, 2017

Learning how to navigate/ modify tree-like structure with parsed AST SQL

Context

Challenge

Examples

Potential solution?

Related topics