SAT-TC Rewrite

Copyright © 2024 PawSQL

Definition

SAT-TC(Satisfiability-Transitive Closure) rewrite rule analyzes a set of predicates and try to determine if

1. there is a contradiction (e.g., c_custkey=1 AND c_custkey=0), or
2. new predicates can be inferred from the set (e.g., c_custkey=1 AND c_custkey=o_custkey implies o_custkey=1.
3. predicates can simplified (e.g. c_custkey <> c_custkey or c_name = 'b' can be simplified to c_name = 'b')

SAT and TC optimizations are two closely related and interacting optimization techniques, often used together.

Benefit

• Save unnecessary predicate evaluations (for database optimizer)
• Provide additional access path to the Join Planner (for database optimizer)
• Enable other rewrite rules (for both database optimizer and PawSQL engine)
• Provide more predicates for index recommendation(for PawSQL);

TC (Transitive Closure) Optimization

Transitive closure optimization refers to inferring new predicates from a set of predicates, so as to generate better execution plans during plan generation.

TC Optimization Example

• Original Query

select o_custkey as cust_no, l_extendedprice * (1 - l_discount)
from orders, lineitem
where l_orderkey = o_orderkey  
and l_orderkey = 'ORD1234';

• Rewritten Query

select o_custkey as cust_no, l_extendedprice * (1 - l_discount)
from orders, lineitem 
where l_orderkey = o_orderkey
and l_orderkey = 'ORD1234'
and o_orderkey = 'ORD1234';

TC optimizations supported by PawSQL include:

1. Equality filtering predicate inference (infer t2.c = 1 from t1.c = t2.c and t1.c = 1).

2. Equality join predicate inference (infer t3.c = t1.c from t1.c = t2.c AND t2.c = t3.c).

3. Range predicate inference (infer t2.c > 1 from t1.c = t2.c and t1.c > 1).

4. IN predicate inference (infer t2.c IN (1,2) from t1.c = t2.c and t1.c IN (1, 2)).

SAT (Satisfiability) Optimization

Satisfiability optimization simplifies query conditions through logical evaluation, analyzes if contradictions or redundancies exist in condition expressions, removes redundant and impossible conditions, and replaces original conditions with simplified expressions.

Example:

• Original Query

select c.c_name FROM customer c where c.c_name = 'John' and c.c_name = 'Jessey'

• Rewritten Query

select c.c_name from customer as c where 1 = 0 

SAT optimizations supported by PawSQL include:

Table Constraints	Original Predicate	Simplified Predicate
	T.C = T.C or T.C >=T.C or T.C<=T.C	T.C IS NOT NULL
	T.C <>T.C or T.C > T.C or T.C < T.C	1 = 0
	(1 = 0) AND Condition	1 = 0
	(1 = 0)OR Condition	Condition
	(1 = 1)AND Condition	Condition
	(1 = 1)OR Condition	1 = 1
T.C cannot be NULL	T.C IS NULL	1 = 0
T.C can be NULL	T.C IS NULL AND T.C opr 'a'	1 = 0
T.C can be NULL	T.C IS NOT NULL AND T.C opr 'a'	T.C = 'a'
T.C can be NULL	T.C IS NOT NULL or T.C opr 'a'	T.C IS NOT NULL
T.C cannot be NULL	T.C IS NULL or T.C opr 'a'	T.C opr 'a'
T.C cannot be NULL	T.C IS NOT NULL or T.C opr 'a'	1 = 1

Where:

Condition is any condition

T.C opr 'constant' is any NULL-rejecting predicate, opr can be =, >, > =, <, < =, IN, BETWEEN, etc.

T.C is column C of table T in the database.

About PawSQL

PawSQL is dedicated to automatic and intelligent database performance optimization. The products provided by PawSQL include:

• PawSQL Cloud, an online automated SQL optimization tool that supports SQL auditing, intelligent query rewriting, cost-based index recommendations, suitable for database administrators and data application developers.
• PawSQL Advisor, an IntelliJ plugin that is suitable for data application developers and can be installed via the IDEA/DataGrip marketplace by searching for "PawSQL Advisor" by name.
• PawSQL Engine, which is the backend optimization engine of the PawSQL series of products, can be installed and deployed independently, and provides SQL optimization services through http/json interfaces. PawSQL Engine is provided for deployment and installation as a docker image.

Contact Us

Email: service@pawsql.com

Twitter: https://twitter.com/pawsql