S interview

s-interview.rs

#![allow(dead_code)]
#![allow(unused_parens)]
#![allow(unused_variables)]

pub struct Schema {
    /// name of each column
    pub fields: Vec<String>,
}

/// the `RelationalOperator` represent operator whose output is relation.
/// the relation have multiple rows and each row have multiple field.
/// all fields of rows in the same relation are the same.
#[derive(Debug, Clone, PartialEq, Eq)]
enum RelationalOperator {
    /// the leaf node in the operator tree, scan columns from the table in storage.
    ScanOperator(ScanData),

    /// select some columns from each rows in input relation
    /// e.g. if the input relation is [row(1,2,3), row(1,1,3), row(2,2,3)]
    /// output_columns is [0,2]
    /// the ProjectOperator's output is [row(1,3), row(1,3), row(2,3)]
    ProjectOperator {
        output_columns: Vec<usize>,
        input: Box<RelationalOperator>,
    },

    /// select the rows from input, which satisfy the predicate( predicate.eval(row)==true).
    /// e.g. if the input relation is [row(1,2,3), row(1,1,3), row(2,2,3)]
    /// predicate is Equal(InputRef(0), InputRef(1))
    /// the FilterOperator's output is [row(1,1,3), row(2,2,3)]
    FilterOperator(FilterData),

    // not necessary to do for join
    /// select the rows from two inputs' cartesian product, which satisfy the predicate( predicate.eval(row)==true).
    /// in the predicate, the InputRef's column index is in schema with left fields concat right fields.
    /// e.g. if
    /// the left input relation is [row(1,1), row(2,2)]
    /// the right input relation is [row(1), row(2)]
    /// predicate is Equal(InputRef(0), InputRef(2))
    /// the cartesian product is [row(1,1,1), row(1,1,2), row(2,2,1), row(2,2,2)]
    /// the JoinOperator's output is [row(1,1,1), row(2,2,2)]
    JoinOperator {
        predicate: Expr,
        left: Box<RelationalOperator>,
        right: Box<RelationalOperator>,
    },
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FilterData {
    predicate: Expr,
    input: Box<RelationalOperator>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ScanData {
    table_name: String,
    columns: Vec<String>,
}

impl RelationalOperator {
    pub fn schema(&self) -> Schema {
        match (self) {
            RelationalOperator::ScanOperator(ScanData {
                table_name,
                columns,
            }) => Schema {
                fields: columns.clone(),
            },
            RelationalOperator::ProjectOperator {
                output_columns,
                input,
            } => {
                let input_schema = input.schema();
                let fields = output_columns
                    .iter()
                    .map(|i| input_schema.fields[*i].clone())
                    .collect();
                Schema { fields }
            }
            RelationalOperator::FilterOperator(FilterData { predicate, input }) => input.schema(),
            RelationalOperator::JoinOperator {
                predicate,
                left,
                right,
            } => unimplemented!(),
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    Equal(Box<Expr>, Box<Expr>),
    And(Box<Expr>, Box<Expr>),
    /// InputRef(n) get the n-th field of one row
    InputRef(usize),
}

fn main() {
    println!("Hello, world!");
}

/// return the equivalent plan with the given plan, minimize the columns number in the tableScan.
fn prune_col(plan: RelationalOperator, used_ix: &mut Vec<usize>) -> RelationalOperator {
    use RelationalOperator::*;
    match (plan) {
        ScanOperator { .. } => plan,
        ProjectOperator {
            output_columns,
            input,
        } => {
            let inner = prune_col(*input, used_ix);
            let mut stack = Vec::new();
            match innermost_scan(&inner, &mut stack) {
                Some(ScanData {
                    table_name,
                    columns,
                }) => {
                    output_columns.iter().chain(stack.iter().flat_map(f));
                    ScanOperator(ScanData {
                        table_name,
                        columns: output_columns.iter().map(|&i| columns[i].clone()).collect(),
                    })
                },
                // ProjectOperator {
                //     output_columns: inner_columns,
                //     input,
                // } => ProjectOperator {
                //     output_columns: output_columns.iter().map(|&i| inner_columns[i]).collect(),
                //     input,
                // },
                None => ProjectOperator {
                    output_columns,
                    input: Box::new(inner),
                },
            }
        },
        gg => gg,
    }
}

fn mk_vec_strings(list: &[&str]) -> Vec<String> {
    list.iter().map(ToString::to_string).collect()
}

#[test]
fn prune_col_example_1() {
    // the plan1 and plan2 are equivalent
    use RelationalOperator::*;

    let plan1 = ScanData {
        table_name: "t".to_string(),
        columns: mk_vec_strings(&["a", "b", "c"]),
    };
    let plan1 = ProjectOperator {
        output_columns: vec![0, 2],
        input: Box::new(ScanOperator(plan1)),
    };

    let plan2 = ScanOperator(ScanData {
        table_name: "t".to_string(),
        columns: mk_vec_strings(&["a", "c"]),
    });

    assert_eq!(prune_col(plan1), plan2);
}

fn prune_col_example_2() {
    // the plan1 and plan2 are equivalent
    use RelationalOperator::*;

    let plan1 = ScanOperator(ScanData {
        table_name: "t".to_string(),
        columns: mk_vec_strings(&["a", "b", "c"]),
    });
    let plan1 = FilterOperator(FilterData {
        predicate: Expr::Equal(Box::new(Expr::InputRef(0)), Box::new(Expr::InputRef(2))),
        input: Box::new(plan1),
    });
    let plan1 = ProjectOperator {
        output_columns: vec![2],
        input: Box::new(plan1),
    };

    let plan2 = ScanOperator(ScanData{
        table_name: "t".to_string(),
        columns: mk_vec_strings(&["a", "c"]),
    });
    let plan2 = FilterOperator(FilterData {
        predicate: Expr::Equal(Box::new(Expr::InputRef(0)), Box::new(Expr::InputRef(1))),
        input: Box::new(plan2),
    });
    let plan2 = ProjectOperator {
        output_columns: vec![1],
        input: Box::new(plan2),
    };
}

fn prune_col_example_3() {
    // the plan1 and plan2 are equivalent
    use RelationalOperator::*;

    let l_plan1 = ScanOperator(ScanData {
        table_name: "left".to_string(),
        columns: vec!["a".to_string(), "b".to_string()],
    });

    let r_plan1 = ScanOperator(ScanData {
        table_name: "right".to_string(),
        columns: vec!["c".to_string()],
    });
    let plan1 = JoinOperator {
        predicate: Expr::Equal(Box::new(Expr::InputRef(0)), Box::new(Expr::InputRef(2))),
        left: Box::new(l_plan1),
        right: Box::new(r_plan1),
    };
    let plan1 = ProjectOperator {
        output_columns: vec![2],
        input: Box::new(plan1),
    };

    let l_plan2 = ScanOperator(ScanData {
        table_name: "left".to_string(),
        columns: vec!["a".to_string()],
    });
    let r_plan2 = ScanOperator(ScanData {
        table_name: "right".to_string(),
        columns: vec!["c".to_string()],
    });
    let plan2 = JoinOperator {
        predicate: Expr::Equal(Box::new(Expr::InputRef(0)), Box::new(Expr::InputRef(1))),
        left: Box::new(l_plan2),
        right: Box::new(r_plan2),
    };
    let plan2 = ProjectOperator {
        output_columns: vec![1],
        input: Box::new(plan2),
    };
}