@bosek/rsql-optimizer

Optimizer written in TypeScript for RSQL ASTs. Feed it the output of @rsql/parser and get back a smaller, equivalent tree that’s easier to evaluate or translate to SQL/ORM queries. The real benefit is getting rid of tautologies and contradictions to lower the amount of DB calls(see example #5).

• Runtime targets Node(CJS, ESM) & Browser(CJS, ESM, IIFE)
• ~150 tests
• Single dependency @rsql/ast

Install

npm i @bosek/rsql-optimizer
# or
pnpm add @bosek/rsql-optimizer

Quick start

import { emit } from '@rsql/emitter';
import { parse } from '@rsql/parser';
import { optimize } from '@bosek/rsql-optimizer';

const fieldSchema = {
    year: createField("number"),
    genre: createField("string"),
};

const input = "year<=1980;genre=in=(fantasy,scifi);year<=2000;genre!=fantasy";

const ast = parse(input);
const optimized = optimize(ast, schema);
const output = emit(optimized);
//    input  = "year<=1980;genre=in=(fantasy,scifi);year<=2000;genre!=fantasy"
//    output = "year<=1980;genre==scifi"

Features

• Operator normalization – unifies logical/comparison verbose operator variants
• Deduplication – removes duplicate conditions in AND/OR groups
• Range & set merging – combines bounds, equalities, and IN/OUT into minimal form
• Contradiction / tautology detection – spots impossible or always-true filters
• OR simplifications – unions equalities into IN, non-equalities into OUT, keeps weakest bounds, applies safe != rules

*Not an exhaustive list. Please take a look at tests to see it in action!

Disclaimer

This library is not battle-tested and as you can probably imagine is hard to write tests for. I am sure there are still some edge cases that are not properly handled. I welcome any feedback, bug reports or pull requests.

API

import type { ExpressionNode } from '@rsql/ast';

export type FieldType = "number" | "string" | "date";
export type Field = { type: FieldType; caseInsensitive?: boolean };
export type FieldSchema = {
    [key: string]: Field;
};

export function createField(type: FieldType, caseInsensitive?: boolean): Field;
export function optimize(node: ExpressionNode, schema: FieldSchema): ExpressionNode | undefined;

The optimizer does not evaluate data or talk to your DB. It only rewrites the AST to hopefuly reduce the number of DB calls. Zero assumptions.

Examples

1. OR dedupe (with caseInsensitive: true)

Duplicate comparisons collapse, case insensitive in this case.

input:  city==Brno,city==brno
output: city==brno

2. List dedupe

Does not care about order of elements in lists.

With caseInsensitive: true:

input:  city=in=(Ostrava,Brno,Prague),city=in=(Prague,brno,Ostrava)
output: city=in=(Ostrava,Brno,Prague)

With caseInsensitive: false:

input:  city=in=(Ostrava,Brno,Prague),city=in=(Prague,brno,Ostrava)
output: city=in=(Ostrava,Brno,Prague,brno)

3. AND range merge

Tightest lower bound kept and merged with upper bound. Operator normalization.

input:  age>=18 and age>21 and age<=65
output: age>=21;age<=65

4. Bound dominance

Tightest lower bound kept and other fields(status) are unchanged.

input:  (age==18,age==21,status==active),age>=18,age>18
output: age>=18,status==active

5. NEQ behavior in OR + IN interaction

Removes redundant IN when NEQ present(and IN does not include NEQ value).

input:  age!=13,age=in=(18,19),city==brno
output: age!=13,city==brno

Compare to:

input:  age!=13,age=in=(13,19),city==brno
output: undefined

This example would lead to tautology - always true. So our string would return all records if translated to SQL query.

5. Mixed nesting, contradictions and bounds

Per-field OR(bounds + points) and a separate AND branch

input:  (salary>100000,salary>=100000,salary==100000),(department==eng;salary>=90000),(department=in=(eng,sales))
output: department==eng;salary>=90000,salary>=100000,department=in=(eng,sales)

Parentheses around AND groups are redundant(and cosmetic) as according to RSQL spec AND has precedence over OR by default:

By default, the AND operator takes precedence (i.e. it’s evaluated before any OR operators are). However, a parenthesized expression can be used to change the precedence, yielding whatever the contained expression yields.

Plans

Distinction between tautology/contradiction can be implemented. I am not sure right now if it needs to be there. Please let me know if you'd find it useful.

License

MIT © 2025 Tomas Bosek