Microsoft Workloads on AWS
Formal and Game-theoretic Testing for SQL Query Migration Validation
Kanishk Kaul, Ferhat Erata and Satyajit Gokhale also contributed to the article
Validating that GenAI-translated SQL queries remain functionally equivalent when you migrate databases from Microsoft SQL Server (SQL Server) to Amazon Aurora PostgreSQL-Compatible Edition is challenging. During migration, transformation tools automate the cross-dialect translation of SQL queries from SQL Server’s T-SQL to PostgreSQL’s PL/pgSQL. However, these tools can hallucinate and offer no guarantees of correctness, making equivalence validation essential before translated queries reach production. Subtle differences arise in case sensitivity, trailing-space handling, NULL semantics, and numeric precision. A translated query can return the same results as the original query on some test data and different results on the data that triggers the difference.
This validation capability is part of AWS Transform, the AWS service for agentic migration and modernization of Microsoft workloads.
This post introduces a validation pipeline that combines two complementary approaches: a formal verification stage grounded in mathematical proof, and a game-theoretic testing stage. In the formal stage, the pipeline uses Apache Calcite relational algebra and the Z3 theorem prover to prove equivalence or non-equivalence. The game-theoretic stage is called mutation-score-guided testing. In this stage, the pipeline formulates test generation as a two-player zero-sum game. One player (the seed-data generator) creates database states designed to expose behavioral differences. The opposing player (the query mutant generator) produces subtle query variants designed to survive those tests. This adversarial dynamic progressively strengthens both the test suite and the mutant population. It drives the pipeline toward either a concrete counterexample (proving non-equivalence) or high-confidence equivalence. Together, the formal and game-theoretic stages provide coverage that neither achieves alone.
Solution overview
The validation pipeline takes a pair of queries: the original SQL Server statement and its transformed PostgreSQL counterpart, together with their schemas. It returns a verdict of either equivalent or non-equivalent. Because it runs as part of an AWS Transform database migration, you get this validation automatically, with no separate setup. Instead of relying on manual spot-checks, you get automatic, evidence-backed equivalence results, and when a query is not equivalent, you get a concrete counterexample that shows exactly how it diverges so that you can fix it.
We staged the pipeline so that the strongest evidence is tried first.
- Stage 1, formal verification: Formal methods attempt to prove equivalence or non-equivalence mathematically. A verdict here is a proof and is treated as authoritative.
- Stage 2, mutation-score-guided testing: When formal verification cannot decide, the pipeline generates adversarial test data and queries mutants. It runs them against live containerized databases and compares the results to search for a counterexample.
These two stages are complementary in nature. Formal verification gives mathematical certainty where it applies. Mutation-score-guided testing provides empirical coverage for the large fraction of real-world queries that formal methods cannot handle. Figure 1 illustrates the end-to-end flow.
Figure 1. The two-stage SQL query equivalence validation pipeline.
Walkthrough
The following sections walk through the pipeline end to end: the input it accepts, each of the two validation stages, and a worked example for each stage.
Prerequisites
We explain the validation approach conceptually, therefore, requires no setup to follow along. To apply it to your own migration, you need an AWS account and a database migration in AWS Transform. There are no other prerequisites.
Input format
The pipeline accepts four inputs: the original T-SQL query, the transformed PL/pgSQL query, the source SQL Server schema, and the target PostgreSQL schema.
Stage 1, formal verification
The formal verification stage applies mathematical methods to prove whether the original and transformed queries are equivalent. It escalates through three levels, stopping at the first that decides:
- Structural (string) match: If the two queries match exactly after normalization, they are considered equivalent.
- Apache Calcite AST comparison: It parses the queries into Calcite relational algebra and compares their abstract syntax trees.
- Z3 solver: we use relational-algebra equivalence rules with the Z3 theorem prover to evaluate equivalence or non-equivalence.
Formal verification produces one of three outcomes: equivalent, non-equivalent, or unknown. The first two are highly reliable because they rest on mathematical proof, and the pipeline accepts them directly. The catch is coverage: both queries must be fully translatable into Apache Calcite’s dialect, and formal methods alone cannot fully analyze a large fraction of queries. Any pair marked unknown is forwarded to Stage 2.
Example of formal verification
Consider a query that filters orders by year. The SQL Server version uses the T-SQL function YEAR(OrderDate), while the PostgreSQL version uses EXTRACT(year FROM OrderDate). The two queries are:
-- Microsoft SQL Server
SELECT * FROM Orders WHERE YEAR(OrderDate) = 2023
-- PostgreSQL
SELECT * FROM Orders WHERE EXTRACT(year FROM OrderDate) = 2023
These are textually different, and the string match returns unknown. However, when both are parsed into Apache Calcite relational algebra, they produce the same abstract syntax tree: a filter node applying a year-extraction function to the OrderDate column. The Calcite AST comparison proves equivalence and formal verification never invokes the Z3 solver.
This example illustrates the escalation logic: the strongest evidence that can decide does so, and the pipeline stops without spending time on more expensive validation steps.
Stage 2, mutation-score-guided testing
When formal verification cannot decide, the pipeline switches from proof to empirical falsification. The core idea is straightforward: if two queries ever produce different results on the same database state, they are provably non-equivalent.
The difficulty is generating data that triggers the difference. On data that does not trigger the difference, even genuinely different queries return identical results. Mutation-score-guided testing solves this by treating test generation as an adversarial, two-player game:
- The table mutant generator creates diverse database states. These states are designed to expose as many query mutants as possible, where exposing a mutant means revealing a behavioral difference between the mutant and the original query.
- The query mutant generator produces subtle but valid query variations that are exposed by as few test tables as possible. Two query mutant generators run in parallel, one for the source (SQL Server) and one for the target (PostgreSQL).
This co-evolution progressively strengthens the test suite: the pipeline keeps the test tables that expose the most mutants and the mutants that survive the most tables. Large language models (LLMs) generate both the test data and the mutants, targeting parameter values, boundary conditions, NULL handling, and type edge cases.
Each query, original or mutant, is executed against its engine (SQL Server or PostgreSQL), and the pipeline compares the results. The verdict rests on the original pair: if any generated test table makes the original SQL Server and PostgreSQL queries produce different results, the two are provably non-equivalent. The pipeline then returns that table as a concrete counterexample that the transformation agent can use to reproduce and repair the defect.
Example of mutation testing
Formal verification handles many queries, but some fall outside what it can decide. Consider a report that ranks departments by their average employee rating. The rating column is an integer, and the query wraps an aggregate inside a window function:
-- Original (Microsoft SQL Server)
WITH dept_stats AS (
SELECT department_id, AVG(rating) AS avg_rating
FROM employees WHERE active = 1
GROUP BY department_id)
SELECT department_id, avg_rating,
RANK() OVER (ORDER BY avg_rating DESC) AS dept_rank
FROM dept_stats;
-- Transformed (PostgreSQL)
WITH dept_stats AS (
SELECT department_id, AVG(rating) AS avg_rating
FROM employees WHERE active = TRUE
GROUP BY department_id)
SELECT department_id, avg_rating,
RANK() OVER (ORDER BY avg_rating DESC) AS dept_rank
FROM dept_stats;
The two queries are almost character-for-character identical, and the translation looks faithful. The difference is invisible in the text and lives in the type system. AVG over an integer column returns a truncated integer in SQL Server, but a decimal in PostgreSQL. Because the average then feeds a RANK() window function, that difference in precision can change the final ranking. We also asked a large language model to judge equivalence directly from the two queries; across trials it was correct about half the time, no better than guessing.
This is where the game begins. The query mutant generator produces a probing mutant that forces integer truncation of the average on both dialects:
-- Mutant: force truncation of the average
SELECT department_id, CAST(AVG(rating) AS INT) AS avg_rating, ...
This mutant differs from the original only when some department has a fractional average, because only then does truncation change the value and the rank. That is exactly the data condition that also exposes the translation error, so the mutant acts as a probe: any table that exposes it also distinguishes the faithful original from the incorrect translation. The seed-data generator searches for data that exposes the mutant. It converges on a two-department collision:
Department 10: ratings 5, 4, 4 -> true average 4.33
Department 20: ratings 5, 5, 4, 4 -> true average 4.50
On this data, SQL Server truncates both averages to 4, so the two departments tie and both receive dept_rank = 1. PostgreSQL keeps 4.33 and 4.50, so department 20 ranks first and department 10 second. The result sets differ in both avg_rating and dept_rank, proving non-equivalence. On data where every department average is a whole number, the two queries agree, and neither engine exposes the mutant. This is why naive testing misses the difference and targeted, mutation-score-guided data generation is needed.
When mutation-score-guided testing proves non-equivalence, it provides a concrete proof: the specific test data that triggered the difference, and the actual query results from each database shown side by side.
Cleanup
The validation runs in ephemeral, containerized database instances that AWS Transform provisions and tears down automatically as part of the migration workflow. No cleanup steps are required on your part.
Conclusion
Migrating from SQL Server to PostgreSQL is a high-impact change. The validation pipeline produces evidence by combining two complementary techniques. Formal verification delivers mathematical proof where queries are analyzable. Mutation-score-guided testing empirically searches for counterexamples on databases for the queries that formal methods cannot resolve. While this post focuses on inline SQL queries, the same two-stage pipeline generalizes to stored procedures, functions, triggers, and other database code objects that carry SQL logic across dialects. This validation runs as part of AWS Transform, so you get it built into your migration workflow.
To get started, validate your first SQL Server to PostgreSQL migration with AWS Transform, and use AWS Aurora PostgreSQL-Compatible Edition as your target database.
For more information, see the following resources: