Build JPA Specification from tree

I have created an API which allows users to build out queries using a tree. The tree is built from the SearchOperationRequest class.

SearchOperationRequest

@Data
@ApiModel(value = "SearchOperationRequest", description = "Condition for the query")
public class SearchOperationRequest

@ApiModelProperty(value = "Conditional statement for the where clause", allowableValues = "EQUALS, NOT_EQUALS, GREATER_THAN, LESS_THAN, LIKE, STARTS_WITH, ENDS_WITH, CONTAINS")
private SearchConditionOperation condition;

@ApiModelProperty(value = "Column name to be searched on")
private String column;

@ApiModelProperty(value = "Value of column")
private Object value;

@ApiModelProperty(value = "Value of OR / AND")
private SearchComparator comparator;

@ApiModelProperty(value = "Left node of comparator condition")
private SearchOperationRequest left;

@ApiModelProperty(value = "Right node of comparator condition")
private SearchOperationRequest right;

public boolean isTreeLeaf()
return left == null && right == null;


public boolean isComparator()
return comparator != null;




So from this example I could create a SearchOperationRequest that asks for all WHERE hidden = false AND X = 88

SearchOperationRequest

"searchOperation":
"left":
"column": "Hidden",
"condition": "EQUALS",
"value": false
,
"comparator": "AND",
"right":
"left":
"column": "X",
"condition": "EQUALS",
"value": 88
,
"comparator": "AND"




This request is built into a specification using a generic specification builder.

public class GenericSpecificationsBuilder<U>

public Specification<U> buildSpecificationFromSearchOperationRequest(SearchOperationRequest root, Function<SpecificationSearchCriteria, Specification<U>> converter) !stack.empty())

if (pointer.isTreeLeaf())
specStack.push(converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue())));


if (pointer.isComparator())
comparatorStack.push(pointer);


if (pointer.getRight() != null)
stack.push(pointer.getRight());


if (pointer.getLeft() != null)
pointer.setRight(pointer.getLeft());
pointer.setLeft(null);
else if (!stack.empty())
SearchOperationRequest temp = stack.pop();
pointer.setRight(temp);


pointer = pointer.getRight();



while (specStack.size() <= comparatorStack.size())
comparatorStack.pop();


while (!comparatorStack.empty())

SearchOperationRequest searchOperationRequest = comparatorStack.pop();

Specification<U> operand1 = specStack.pop();
Specification<U> operand2 = specStack.pop();
if (searchOperationRequest.getComparator().equals(SearchComparator.AND))
specStack.push(Specification.where(operand1)
.and(operand2));
else if (searchOperationRequest.getComparator().equals(SearchComparator.OR))
specStack.push(Specification.where(operand1)
.or(operand2));




return specStack.pop();




My current works great for RIGHT heavy tree's. Meaning queries such as:

WHERE X = 6 AND X = 9
WHERE Z = 5 OR T=9
WHERE Z = 5 OR T=9 OR H=6


But it does not work with building more complex trees where the criteria in braces should get precedence and executed first.

WHERE (X = 6 OR Z = 9) AND (T=6 OR H=8)


The model for this more complex SearchOperationRequest would be:

SearchOperationRequest

"searchOperation":
"left":
"left":
"column": "X",
"condition": "EQUALS",
"value": 6
,
"comparator": "AND",
"right":
"column": "Z",
"condition": "EQUALS",
"value": 9

,
"comparator": "AND",
"right":
"left":
"column": "T",
"condition": "EQUALS",
"value": 6
,
"comparator": "AND",
"right":
"column": "H",
"condition": "EQUALS",
"value": 8





How do I modify my GenericSpecificationsBuilder to be able to handle more complex SearchOperationRequest trees?

GenericSpecificationsBuilder

SearchOperationRequest

comparator

1 Answer
1

Let's follow the execution flow using your example tree.

AND
/
leftOR rightOR
/ /
X=6 Z=9 T=6 H=8


When we exit the first while loop, our stacks look like:

while

stack =
comparatorStack = AND, leftOR, rightOR
specStack = X=6, Z=9, T=6, H=8


The same state enters the final while loop.

while

while (!comparatorStack.empty())

SearchOperationRequest searchOperationRequest = comparatorStack.pop();

Specification<U> operand1 = specStack.pop();
Specification<U> operand2 = specStack.pop();
if (searchOperationRequest.getComparator().equals(SearchComparator.AND))
specStack.push(Specification.where(operand1)
.and(operand2));
else if (searchOperationRequest.getComparator().equals(SearchComparator.OR))
specStack.push(Specification.where(operand1)
.or(operand2));




The problem here is you're pushing the result back on the specStack. So at the second iteration, you'll be popping off the result of the first iteration (the rightOR), as well as Z=9, and apply the leftOr logic to it.

specStack

rightOR

Z=9

leftOr

Decomposing the tree

Let's take a step back and look at how you decompose the tree, more specifically:

if (pointer.getLeft() != null)
pointer.setRight(pointer.getLeft());
pointer.setLeft(null);
else if (!stack.empty())
SearchOperationRequest temp = stack.pop();
pointer.setRight(temp);



The problem with this code is you are altering the nodes in the tree. In the first example, at one time our pointer points to the node:

Z=9
/
null rightOR


That doesn't look right. Instead of decomposing the tree using a stack (Depth First Search), you could use a queue (Breadth First Search) and get the ordering you're after for free.

Does that solve the problem of applying each logical operator (comparator) to the right operands? Not quite, to be able to solve both layouts below, we could decompose the operators and operands in different workflows, instead of all of them together.

comparator

AND | rootAND
/ | /
leftOR rightOR | leftOR rightOR
/ / | / /
X=6 Z=9 T=6 H=8 | X=6 AND Z=9 H=8
| /
| T=6 Y=3


Solution

The first json-like representation in your post has an illogical layout, as logical operators are expected to operate on both a left and right operand. Instead you had:

"right":
"left":
"column": "X",
"condition": "EQUALS",
"value": 88
,
"comparator": "AND"



Let's consider a solution for symmetrical representations, one where both a left and right operand are present for each logical operator.

First we process the tree Breadth First, level by level. Meanwhile, we put each comparator on a stack, so we get the last ones out first in our second while loop.

comparator

while

In the second loop we then use a new Queue to store our 'in-between-results' as we work our way back to the root.

Queue

Queue<SearchOperationRequest> queue = new LinkedList<>();
Deque<SearchOperationRequest> comparatorStack = new LinkedList<>();

if (root == null || !root.isComparator()) return;
queue.add(root);
while(!queue.isEmpty())
SearchOperationRequest node = queue.poll();
comparatorStack.push(node);
if(node.left != null && node.left.isComparator()) queue.add(node.left);
if(node.right != null && node.right.isComparator()) queue.add(node.right);


Queue<Specification> specQueue = new LinkedList<>();
while(!comparatorStack.isEmpty())
SearchOperationRequest comparator = comparatorStack.pop();
// reverse operand order so already computed values are polled correctly
Specification operand2;
SearchOperationRequest pointer = comparator.getRight();
if(pointer.isTreeLeaf())
operand2 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
else
operand2 = specQueue.poll();

Specification operand1;
pointer = comparator.getLeft();
if(pointer.isTreeLeaf())
operand1 = converter.apply(new SpecificationSearchCriteria(pointer.getColumn(), pointer.getCondition(), pointer.getValue()));
else
operand1 = specQueue.poll();

if (comparator.equals(SearchComparator.AND))
specQueue.add(Specification.where(operand1).and(operand2));
else if (comparator.equals(SearchComparator.OR))
specQueue.add(Specification.where(operand1).or(operand2));



return specQueue.poll();


I haven't tested the code, but you should be able to extract (and refactor) the workflows.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.