SQL Planner

This is an optimizing SQL planner generating execution plans for SQL queries.

Implemented optimizations:

• CopyPropagation
• DependencyPropagation
• CommonSubexpressionElimination
• Normalization
• Flattening
• ConstantFolding
• UnusedValueElimination
• FilterSplitting
• FilterHoisting
• FilterMerging
• FilterConditionJoinDetection
• JoinReordering
• JoinSourceSwapping
• ExchangeElimination

Usage

> planner_cli.exe ./path/to/query.sql ./path/to/database.json ./path/to/config.json

example query.sql file:

SELECT e.name, e.salary, d.name 
FROM employee AS e, department AS d
WHERE e.department_id = d.id

example database.json file:

{
    "database": {
        "tables": [
            {
                "name": "employee",
                "columns": [
                    {
                        "name": "name",
                        "type": "text"
                    },
                    {
                        "name": "surname",
                        "type": "text"
                    },
                    {
                        "name": "salary",
                        "type": "int"
                    },
                    {
                        "name": "department_id",
                        "type": "int"
                    }
                ],
                "rows": 300
            },
            {
                "name": "department",
                "columns": [
                    {
                        "name": "id",
                        "type": "int"
                    },
                    {
                        "name": "name",
                        "type": "text"
                    }
                ],
                "rows": 10
            }
        ]
    }
}

example config.json file:

{
    "optimizations": {
        "CopyPropagation": true,
        "DependencyPropagation": true,
        "CommonSubexpressionElimination": true,
        "Normalization": true,
        "Flattening": true,
        "ConstantFolding": true,
        "UnusedValueElimination": true,
        "FilterSplitting": true,
        "FilterHoisting": true,
        "FilterMerging": true,
        "FilterConditionJoinDetection": true,
        "JoinReordering": true,
        "JoinSourceSwapping": true,
        "ExchangeElimination": true
    },
    "printing": {
        "transition": {
            "properties": true
        },
        "operators": {
            "stats": true
        },
        "passes": {
            "ast": true,
            "ir": true,
            "queue": true
        }
    }
}

Output snippet:

AST:

(record)Select{
| list{
| | (text)Column`employee.name`1`,
| | (int)Column`employee.salary`1`,
| | (text)Column`department.name`2`
| },
| source{
| | (record)Join`Cross`{
| | | left_source{
| | | | (record)Alias`e`{
| | | | | (record)Scan`employee`
| | | | }
| | | },
| | | right_source{
| | | | (record)Alias`d`{
| | | | | (record)Scan`department`
| | | | }
| | | },
| | | condition{
| | | | <null_ref>
| | | }
| | }
| },
| where{
| | (bool)Operator`=`{
| | | (int)Column`employee.department_id`1`,
| | | (int)Column`department.id`2`
| | }
| }
}

Expressions:

$1 = (Column`employee.name`1`)
$2 = (Column`employee.surname`1`)
$3 = (Column`employee.salary`1`)
$4 = (Column`employee.department_id`1`)
$5 = (Column`department.id`2`)
$6 = (Column`department.name`2`)
$7 = (Operator`=`{Column`employee.department_id`1`, Column`department.id`2`})

Optimized Plan:

Transform `<unknown>` [cost: 0 (total: 19'809'600), rows: 3]
^   |$1|$3|$6|
|   |$1|$3|$6|
|
Join `Inner` [cost: 13'600.0009765625 (total: 19'809'600), rows: 3]
^   |$1|$3|  |$6|  |
|   |$1|$3|$4|$6|$5|
|
+---Transform `Exchange` [cost: 56'000 (total: 596'000), rows: 10]
|   ^   |$6|$5|
|   |   |$6|$5|
|   |
|   Scan `department` [cost: 540'000 (total: 540'000), rows: 10]
|       |$5|$6|
|       |  |  |
|
|
+---Transform `Exchange` [cost: 1'800'000 (total: 19'200'000), rows: 300]
    ^   |$1|$3|$4|
    |   |$1|$3|$4|
    |
    Scan `employee` [cost: 17'400'000 (total: 17'400'000), rows: 300]
        |$1|$3|$4|
        |  |  |  |