How we write our query filter engine on our REST API (part 2)
After covering the solutions in part 1, we decided to build a query filter engine because we want to give our api consumers the most flexible way to work with our api–even in our product (that also uses our rest api). And, we need the option to filter entities using “Or operator”.
Our tech view solution
The hardest thing about building the query filter engine is related to what your query language is. So first, I map out all the needs in our system:
- Support “And/Or operator”
- Support complex conditions
- Support nested fields conditions
After spending some time (and a lot of investigation on the internet like a good developer 🙂) I came up with this query language (that can be implemented in any rest api).
I thought of the filter condition as a regular math condition and I came up with the next solution. Each condition will be wrapped with parentheses in case the condition has more than one filter. Think of it like a math equation — the ‘or’ is + and the ‘and’ is *. For example, (5+4)10 = 5*10+4*10. The result is the same, so we simply want to let users know about the most elegant format for the condition.
In our case, each condition that needs to share the same logic can be wrapped in parentheses (the same as we did in the equation example) and put “And operator”. Let’s check the next example (condition1 Or condition2) And condition3 = condition1 And condition3 Or condition2 And condition3 Now we have talked about what this condition is — it’s simple as its filter sets are separated with “Or” (it can be only one filter too).
Lastly, let’s talk about what our filters are going to look like. Each filter starts with the field (or nested field separate with dot), the relevant operator symbol (we are going to support all kinds of operators — we will cover it soon), and the value. If the value is string, it will be separated with an apostrophe (‘’). The last thing is a negative operation. If a condition should be negative, for example, and not equal, we will put the “!” symbol at the beginning.
So once we understand how to work with the condition, all we need to do is define our query language. In our case it would be:
//filter operators
= => equal
!= => not equal
! => negative
> => greater then
< => lower then
<= => greater equal then
>= => lower equal then
//condition separate with the flowwing operators
| => Or
& => andNow that we covered the query language, it’s time for some examples 😇
Let’s say that we want to get all employees whose first names are “Adam” and their salary is greater than 1,000 dollars with our query language. It’s super easy and intuitive.
https://demo/v1/employees?search=firstName:’adam’&salary>1000. Let’s filter something that is more complex. Let’s say that we want to find all the people on vacation whose salaries are lower than 1,000 dollars, or people that work 10 days a month in the office and whose names are Robert. https://demo/v1/employees?search=((isOnVacation:true&salary<1000)|numberOfDaysInOffice:10)&firstName:’Robert’ As you can see, we can build any search query that we want with no effort.
Implementation details:
Our rest api server builds on express but the concepts are the same. First, let’s talk about what the parts are that we need to build:
- Middleware — to catch the query and parse it
- Condition parser and field parsers
- Normalize the data to filter the object
- Generic function that gets the filter object and returns a db query
Now let deep dive to each one of the parts.
Middleware
We need to build a middleware that will run before all our routes and will be responsible for putting the filter object on a global variable on the req (request object form express, or any other variable that has access to the controllers).
The middleware will get the entity of the api request and will run the match filter creator. In other words, the filter creator is a factory function that runs the desired entities parsers and creates the filter object for the requested entity. For instance, in our example, we have only one entity (employee) so we will only have one factory. But if we have more than one entity, each one has to have a factory that will create the relevant filters.
Let see the next code that implements this middleware:
//this is the facotry object
const entityParserFactory = {
employee: (query: string) => {} //here we will have to call the employee factory
}
const searchExtractMiddleware =
(req: Request<{ entity: string }, unknown, unknown, { search?: string }>, res: Response, next: NextFunction) => {
//here we extract the search qeury from the request
const { search } = req.query;
if (!search) {
return next();
}
//Each one of the entities have it's own path
const { entity } = req.params;
//this is the filter object SearchParamsDataType is a type that hold all the avilable filter with there avilable fileds and types
let filterObject: SearchParamsDataType | undefined;
try {
//to work simplt we convert our search query into condition
const condtionString = convertConditionToConditionIndex(search);
// we check that our condition are valid
const conditionValid = validateConditionParentheses(condtionString);
if (!conditionValid.isValid) {
throw 'condition not valid'
}
//we are checking that our entity support filtering
if (entityParserFactory[entity]) {
//get the filter object from the factory
filterObject = entityParserFactory[entity](search);
}
if (searchParams) {
//we are putting the filter object in the request variable
req.search = filterObject;
}
} catch (error) {
return next(error);
}
return next();
};The middleware gets the entity name from the params and checks that our query search is valid. Then, it checks that we support filtering for the entity that we got, then it runs the factory function that creates the filter object and puts it on the request under search (so all routes can use it).
Condition parser and fields parsers
The condition parser responsible for creating conditions (separating the parentheses and connecting the relevant conditions) from the search query does so by creating a matrix of conditions, Each cell of the matrix is a filter index and each row of the matrix is a condition. Once we have the matrix, we can run over it and create the filter object, each row creating a filter separated with “And operator”. For example, let’s say we have the flowing api:
https://demo/v1/employees?search=((isOnVacation:true&salary<1000)|numberOfDaysInOffice:10)&firstName:’Robert’the search query is ((isOnVacation:true&salary<1000)|numberOfDaysInOffice=10)&firstName:’Robert’ Once we run the condition parser, it will convert our filter to indexes (so it will be easy to work with) so the result from the conversion will be:
((1&2)|3)&4 Once we have the converted search query, we will create a binary tree that will help us create the condition matrix. the binary tree will look like this:
Each one of the nodes will be an action or condition node (the red circles are actions and the purple circle are conditions)
The binary tree will look like this:
{“action”: “and”, “left”: {“action”: “or”, “left”: {“action”: “and”, “left”: {“conditionIndex”: 1, “type”: “condition”}, “right”: {“conditionIndex”: 2, “type”: “condition”}, “type”: “action”}, “right”: {“conditionIndex”: 3, “type”: “condition”}, “type”: “action”}, “right”: {“conditionIndex”: 4, “type”: “condition”}, “type”: “action”}
Once we have the binary tree, we can easily create the matrix with the flowing code:
type ConditionNodeAction = 'and' | 'or'
type ConditionNodeType = 'action' | 'condition'
//we can craete this type differently but just to make thing easier i did it like this
type ConditionNode = {
action?: ConditionNodeAction,
left?: ConditionNode,
right?: ConditionNode,
type: ConditionNodeType,
conditionIndex?: number
}
//we are getting the conditino Node
const conditionNodeToArray = (conditionNode: ConditionNode): Array<number[]> => {
//If the node is condition we expected that it's will include the condition index
if (conditionNode.type === 'condition') {
if (conditionNode.conditionIndex === undefined) {
throw new Error('no condition index')
}
//we return an array with the condition index
return [[conditionNode.conditionIndex]];
}
//if the node is action we expected that both nodes will be populated
if (conditionNode.type === 'action') {
if (!conditionNode.left || !conditionNode.right) {
throw new Error('action node must contain right and left node');
}
// we get the left and the right trees
const leftConditionIndex = conditionNodeToArray(conditionNode.left);
const rightConditionIndex = conditionNodeToArray(conditionNode.right);
//if the condition action is or we return an array with both rows (of the fight and left node)
if (conditionNode.action === ConditionActionEnum.or) {
return [...leftConditionIndex, ...rightConditionIndex];
}
//if the condition action is and we return the cobination of the left and the right tres
if (conditionNode.action === ConditionActionEnum.and) {
return openArrayParenthesis(leftConditionIndex, rightConditionIndex);
}
}
throw 'unsupported action type';
};
//this is open the parenthesis for example if we get [[1,2]] and [[3,4]] the result will be [[1,3],[1,4],[2,3],[2,4]]
const openArrayParenthesis = (left: number[][], right: number[][]): number[][] => {
const result: Array<number[]> = [];
left.forEach((conditionLeft) => {
right.forEach((conditionRight) => {
result.push([...conditionLeft, ...conditionRight]);
});
});
return result;
};With this code, we will get our condition matrix and we will get the flowing matrix from our last example ((1&2)|3)&4:
Once we run the condition parser, we will get the following matrix:
[
[1, 2, 4],
[3, 4]
]Now, let’s jump to the condition field. Each one of the fields from our api entities can be used as a filter. In our example, we have firstName,lastName, salary, isOnVacation fields and we need to parse them to an action, value, key, and condition index object (once do it, we will be able to create our filter object and we are done!).
We are going back to the original search query that we got, in our example:
((isOnVacation:true&salary<1000)|numberOfDaysInOffice=10)&firstName:’Robert’ ,
We will build a parser for each entity. Let’s see the parser for this entity:
export enum SearchAction {
equal,
notEqual,
greaterThan,
lowerThen,
lowerEqualThen,
greaterEqualThan,
}
type searchFiledParam = {
key: string;
value: string;
action: SearchAction;
conditionIndex: number;
};
export const extractSearchParams = (search: string): searchFiledParam[] => {
//this is the regex that we need to seperate to group so it will be easy to work with
const regex = /(!?)([\w.]+)([><=]+)([[\d]+]?|['[\w\d@#,\. ]+']?)/gm
/* eslint-enable */
const regexArrayResult = [...search.matchAll(regex)];
const searchField: Array<searchFiledParam | null> = regexArrayResult.map((regexMatch, index) => {
// we are getting the data from our regex groups
const key = regexMatch[SearchRegexGroupEnum.key];
const value = regexMatch[SearchRegexGroupEnum.value];
const isNegative = regexMatch[SearchRegexGroupEnum.isNegative];
const action = regexMatch[SearchRegexGroupEnum.action];
let actionToReturn: SearchAction = SearchAction.equal;
switch (action) {
// an example of action
case FilterAction.equal: {
if (isNegative) {
actionToReturn = SearchAction.notEqual;
} else {
actionToReturn = SearchAction.equal;
}
break;
}
//here we will put the rest of our actions
default:
throw unSupportedFilterAction(action);
}
return {
action: actionToReturn,
key,
value: value.replace(/'/g, ''),
conditionIndex: index,
};
});
return searchField
};
//i woldn't put all the typescript types here but it's shuold be easy to define them
//query string is the query
// queryMapper is an object to map the keys from the query to the actual keys in our db (for api versioning)
//in our exmaple we leave every field with the name in the db so it's will look like
const queryMapper = {
isOnVacation: 'isOnVacation',
firstName: 'firstName',
numberOfDaysInOffice: 'numberOfDaysInOffice',
salary: 'salary'
}
export const employeeParser = ({ queryString, queryMapper }) => {
const searchObjResult: EntityConditionFilters<'User'> = [];
//we are using our helper function to get the search params
const searchParams = extractSearchParams(queryString);
searchParams.forEach((param) => {
const { key, action, value, conditionIndex } = param;
switch (key) {
case 'salary': {
//here we can validate the value and throw an error in case the value is not respected
if (isNaN(value)) {
throw 'error salary should be number';
}
//pusing the filter to the result
searchObjResult.push({
salary: {
action,
value: Number(value),
},
index: conditionIndex,
});
break;
}
//the rest of the filed will be here
}
});
return searchObjResult;
};In this blog post, we covering our query language that supports And/Or operator and showing some examples, it was demonstrated how simple it is to use our filter API.
We also discussed how to build middleware that gets a filter query, runs the correct factory functions, and stores the filter object on a global variable. We also covered the condition parser that is related to building the condition metrics and we showed how to build an entity parser. Keep on reading to find out how everything is connected and to see how we make the filter DB query that returns the filtered data.
