---
# System prepended metadata

title: NTHU DB Assignment 3

---

# NTHU DB Assignment 3

- Deadline: **2021/04/21 (Wen.) 23:59:59**

## GitHub

https://github.com/vanilladb/vanillacore/tree/master/src/main/java/org/vanilladb/core/util

## Notes
- Planner # 接收 SQL 語句
- 呼叫 Parse # 翻議成 Query Data
- Plan/Open -> Scan
- Scan -> BeforeFirst -> Next (getVal)

- BasicQueryPlanner.java / QueryData.java / Lexer.java

![](https://i.imgur.com/V111ucu.png)

org/vanilladb/bench/server/param/tpcc/TpccSchemaBuilderProcParamHelper.java




## doQuery
- **ConsoleSQLInterpreter doQuery()**
- ResultSet rs = stmt.executeQuery(cmd);
    - **JdbcStatement executeQuery()** 
    - RemoteResultSet rrs = rstmt.executeQuery(qry);
        - **RemoteStatementImpl executeQuery()**
        - Plan pln = VanillaDb.newPlanner().createQueryPlan(qry, tx);
            - **Planner createQueryPlan()**
            - QueryData data = parser.queryCommand();
                - **Parser queryCommand()**
                - return new QueryData(isExplain, projs.asStringSet(), tables, pred, groupFields, projs.aggregationFns(), sortFields, sortDirs);
            - Verifier.verifyQueryData(data, tx);
            - return qPlanner.createPlan(data, tx);
                - **BasicQueryPlanner createPlan()**
                - TablePlan、ProductPlan、ProductPlan、ProjectPlan、SortPlan 
                    - **Construct Plan Tree**
                - return p
        - return new RemoteResultSetImpl(pln, rconn);
            - **RemoteResultSetImpl implements RemoteResultSet RemoteResultSetImpl()**
            - private Scan s; 
            - s = plan.open();
            - schema = plan.schema();
    - return new JdbcResultSet(rrs);
        - **JdbcResultSet beforeFirst()**
        - private RemoteResultSet rrs;
        - rrs.beforeFirst();
            - **RemoteResultSetImpl implements RemoteResultSet              beforeFirst()**
            - private Scan s;
            - s.beforeFirst();
                - **set every plan/scan pointer to beforeFirst**
- ResultSetMetaData md = rs.getMetaData();
- rs.beforeFirst();
- while ( rs.next() ) { 
    - String fldname = md.getColumnName(i);
    - rs.getVal(fldname) 
- }
- rs.close();

## Schema
```{java}
private final String TABLES_DDL[] = {
			"CREATE TABLE warehouse ( w_id INT, w_name VARCHAR(10), "
					+ "w_street_1 VARCHAR(20), w_street_2 VARCHAR(20), w_city VARCHAR(20), "
					+ "w_state VARCHAR(2), w_zip VARCHAR(9), w_tax DOUBLE,  w_ytd DOUBLE )",
			"CREATE TABLE district ( d_id INT, d_w_id INT, d_name VARCHAR(10), "
					+ "d_street_1 VARCHAR(20), d_street_2 VARCHAR(20), d_city VARCHAR(20), "
					+ "d_state VARCHAR(2), d_zip VARCHAR(9), d_tax DOUBLE, d_ytd DOUBLE, "
					+ "d_next_o_id INT )",
			"CREATE TABLE customer ( c_id INT, c_d_id INT, c_w_id INT, "
					+ "c_first VARCHAR(16), c_middle VARCHAR(2), c_last VARCHAR(16), "
					+ "c_street_1 VARCHAR(20), c_street_2 VARCHAR(20), c_city VARCHAR(20), "
					+ "c_state VARCHAR(2), c_zip VARCHAR(9), c_phone VARCHAR(16), "
					+ "c_since LONG, c_credit VARCHAR(2), c_credit_lim DOUBLE, "
					+ "c_discount DOUBLE, c_balance DOUBLE, c_ytd_payment DOUBLE, "
					+ "c_payment_cnt INT, c_delivery_cnt INT, c_data VARCHAR(500) ) ",
			"CREATE TABLE history ( h_c_id INT, h_c_d_id INT, h_c_w_id INT, "
					+ "h_d_id INT, h_w_id INT, h_date LONG, h_amount DOUBLE, "
					+ "h_data VARCHAR(24) )",
			"CREATE TABLE new_order ( no_o_id INT, no_d_id INT, no_w_id INT )",
			"CREATE TABLE orders ( o_id INT, o_d_id INT, o_w_id INT, "
					+ "o_c_id INT, o_entry_d LONG, o_carrier_id INT, o_ol_cnt INT, "
					+ "o_all_local INT )",
			"CREATE TABLE order_line ( ol_o_id INT, ol_d_id INT, ol_w_id INT, "
					+ "ol_number INT, ol_i_id INT, ol_supply_w_id INT, ol_delivery_d LONG, "
					+ "ol_quantity INT, ol_amount DOUBLE, ol_dist_info VARCHAR(24) )",
			"CREATE TABLE item ( i_id INT, i_im_id INT, i_name VARCHAR(24), "
					+ "i_price DOUBLE, i_data VARCHAR(50) )",
			"CREATE TABLE stock ( s_i_id INT, s_w_id INT, s_quantity INT, "
					+ "s_dist_01 VARCHAR(24), s_dist_02 VARCHAR(24), s_dist_03 VARCHAR(24), "
					+ "s_dist_04 VARCHAR(24), s_dist_05 VARCHAR(24), s_dist_06 VARCHAR(24), "
					+ "s_dist_07 VARCHAR(24), s_dist_08 VARCHAR(24), s_dist_09 VARCHAR(24), "
					+ "s_dist_10 VARCHAR(24), s_ytd INT, s_order_cnt INT, s_remote_cnt INT, "
					+ "s_data VARCHAR(50) )" };
	private final String INDEXES_DDL[] = {
			"CREATE INDEX idx_warehouse ON warehouse (w_id)",
			"CREATE INDEX idx_district ON district (d_id)",
			"CREATE INDEX idx_customer ON customer (c_id)",
			"CREATE INDEX idx_history ON history (h_c_id)",
			"CREATE INDEX idx_order ON orders (o_id)",
			"CREATE INDEX idx_new_order ON new_order (no_o_id)",
			"CREATE INDEX idx_order_line ON order_line (ol_o_id)",
			"CREATE INDEX idx_stock ON stock (s_i_id)",
			"CREATE INDEX idx_item ON item (i_id)" };

```

## SQL Command

```{SQL}
# EXPLAIN
EXPLAIN SELECT i_id, i_name, i_price FROM item WHERE i_id < 30;

# SELECT
SELECT i_id, i_name, i_price FROM item WHERE i_id < 30;
```

## getExplain()
### ExplainPlan
```{java}
@Override
public String getExplain(){

    return explain;
}
```
### ProductPlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className
						 + " (#blks=" + this.blocksAccessed() + "," 
						 + " #recs=" + this.recordsOutput() + ")\n"
						 + p1.getExplain()
						 + p2.getExplain();

		return total;
	}
```
### ProjectPlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className+  "(#blks=" + this.blocksAccessed() + "," 
										 + "#recs=" + this.recordsOutput() + ")\n"
										 + p.getExplain();
		return total;
	}
```
### SelectPlan
```{java}
	@Override
	public String getExplain(int depth){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String explain =  "\t".repeat(depth) + "->" + className + " pred:(" + this.pred.toString() + ")"
						 + " (#blks=" + this.blocksAccessed() + "," 
						 + " #recs=" + this.recordsOutput() + ")\n"
						 + p.getExplain(depth + 1);

		return explain;
	}
```
### TablePlan
```{java}
	@Override
	public String getExplain(int depth){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String explain = "\t".repeat(depth) + "->" + className  + " on (" + ti.tableName() +") "
						+  "(#blks=" + this.blocksAccessed() + "," + "#recs=" + this.recordsOutput() + ")\n";
		return explain;
	}
```
### GroupByPlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className+  "(#blks=" + this.blocksAccessed() + "," 
										 + "#recs=" + this.recordsOutput() + ")\n"
										 + sp.getExplain();
		return total;
	}
```

### MaterializePlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className+  "(#blks=" + this.blocksAccessed() + "," 
										 + "#recs=" + this.recordsOutput() + ")\n"
										 + p.getExplain();
		return total;
	}
```
### MergeJoinPlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className+  "(#blks=" + this.blocksAccessed() + "," 
										 + "#recs=" + this.recordsOutput() + ")\n"
										 + sp1.getExplain()
										 + sp2.getExplain();
		return total;
	}
```

### SortPlan
```{java}
	@Override
	public String getExplain(){
		String[] tmp = this.getClass().getName().split("\\.");
		String className = tmp[tmp.length-1];
		
		String total =  "\t".repeat(depth) + "->" + className+  "(#blks=" + this.blocksAccessed() + "," 
										 + "#recs=" + this.recordsOutput() + ")\n"
										 + p.getExplain();
		return total;
	}

```
	
## code update

**Parser**
```{java}
/*******************************************************************************
 * Copyright 2016, 2017 vanilladb.org contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *******************************************************************************/
package org.vanilladb.core.query.parse;

import static org.vanilladb.core.sql.RecordComparator.DIR_ASC;
import static org.vanilladb.core.sql.RecordComparator.DIR_DESC;
import static org.vanilladb.core.sql.Type.BIGINT;
import static org.vanilladb.core.sql.Type.DOUBLE;
import static org.vanilladb.core.sql.Type.INTEGER;
import static org.vanilladb.core.sql.Type.VARCHAR;
import static org.vanilladb.core.sql.predicate.BinaryArithmeticExpression.OP_ADD;
import static org.vanilladb.core.sql.predicate.BinaryArithmeticExpression.OP_DIV;
import static org.vanilladb.core.sql.predicate.BinaryArithmeticExpression.OP_MUL;
import static org.vanilladb.core.sql.predicate.BinaryArithmeticExpression.OP_SUB;
import static org.vanilladb.core.sql.predicate.Term.OP_EQ;
import static org.vanilladb.core.sql.predicate.Term.OP_GT;
import static org.vanilladb.core.sql.predicate.Term.OP_GTE;
import static org.vanilladb.core.sql.predicate.Term.OP_LT;
import static org.vanilladb.core.sql.predicate.Term.OP_LTE;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.vanilladb.core.sql.Constant;
import org.vanilladb.core.sql.DoubleConstant;
import org.vanilladb.core.sql.Schema;
import org.vanilladb.core.sql.VarcharConstant;
import org.vanilladb.core.sql.aggfn.AggregationFn;
import org.vanilladb.core.sql.aggfn.AvgFn;
import org.vanilladb.core.sql.aggfn.CountFn;
import org.vanilladb.core.sql.aggfn.DistinctCountFn;
import org.vanilladb.core.sql.aggfn.MaxFn;
import org.vanilladb.core.sql.aggfn.MinFn;
import org.vanilladb.core.sql.aggfn.SumFn;
import org.vanilladb.core.sql.predicate.BinaryArithmeticExpression;
import org.vanilladb.core.sql.predicate.ConstantExpression;
import org.vanilladb.core.sql.predicate.Expression;
import org.vanilladb.core.sql.predicate.FieldNameExpression;
import org.vanilladb.core.sql.predicate.Predicate;
import org.vanilladb.core.sql.predicate.Term;
import org.vanilladb.core.storage.index.IndexType;
import org.vanilladb.core.util.CoreProperties;

/**
 * The VanillaDb parser. Note that VanillaDb parser cannot parse double value in
 * scientific notation.
 */
public class Parser {
	public static final IndexType DEFAULT_INDEX_TYPE;

	static {
		int defaultIdxType = CoreProperties.getLoader().getPropertyAsInteger(
				Parser.class.getName() + ".DEFAULT_INDEX_TYPE", 1);
		DEFAULT_INDEX_TYPE = IndexType.fromInteger(defaultIdxType);
	}

	private static class ProjectEl {
		String fld;
		AggregationFn aggFn;

		ProjectEl(String fld) {
			this.fld = fld;
		}

		ProjectEl(AggregationFn aggFn) {
			this.aggFn = aggFn;
		}
	}

	private static class ProjectList {
		List<ProjectEl> els = new ArrayList<ProjectEl>();

		void addField(String fld) {
			els.add(new ProjectEl(fld));
		}

		void addAggFn(AggregationFn aggFn) {
			els.add(new ProjectEl(aggFn));
		}

		Set<String> asStringSet() {
			if (els.size() == 0)
				return null;
			Set<String> ret = new HashSet<String>(els.size());
			for (ProjectEl el : els) {
				if (el.fld != null)
					ret.add(el.fld);
				else
					ret.add(el.aggFn.fieldName());
			}
			return ret;
		}

		Set<AggregationFn> aggregationFns() {
			if (els.size() == 0)
				return null;
			Set<AggregationFn> ret = new HashSet<AggregationFn>(els.size());
			for (ProjectEl el : els) {
				if (el.aggFn != null)
					ret.add(el.aggFn);
			}
			return ret.size() == 0 ? null : ret;
		}
	}

	private static class SortEl extends ProjectEl {
		int dir;

		SortEl(String fld, int dir) {
			super(fld);
			this.dir = dir;
		}

		SortEl(AggregationFn aggFn, int dir) {
			super(aggFn);
			this.dir = dir;
		}
	}

	private static class SortList {
		List<SortEl> els = new ArrayList<SortEl>();

		void addField(String fld, int sortDir) {
			els.add(new SortEl(fld, sortDir));
		}

		void addAggFn(AggregationFn aggFn, int sortDir) {
			els.add(new SortEl(aggFn, sortDir));
		}

		List<String> fieldList() {
			if (els.size() == 0)
				return null;
			List<String> ret = new ArrayList<String>(els.size());
			for (SortEl el : els) {
				if (el.fld != null)
					ret.add(el.fld);
				else
					ret.add(el.aggFn.fieldName());
			}
			return ret;
		}

		List<Integer> directionList() {
			if (els.size() == 0)
				return null;
			List<Integer> ret = new ArrayList<Integer>(els.size());
			for (SortEl el : els)
				ret.add(el.dir);
			return ret;
		}
	}

	/*
	 * Instance members.
	 */

	private Lexer lex;

	public Parser(String s) {
		lex = new Lexer(s);
	}

	/*
	 * Methods for parsing constants and IDs.
	 */

	private String id() {
		return lex.eatId();
	}

	private Constant constant() {
		if (lex.matchStringConstant())
			return new VarcharConstant(lex.eatStringConstant());
		else
			return new DoubleConstant(lex.eatNumericConstant());
	}

	private Set<String> idSet() {
		Set<String> list = new HashSet<String>();
		do {
			if (lex.matchDelim(','))
				lex.eatDelim(',');
			list.add(id());
		} while (lex.matchDelim(','));
		return list;
	}

	private List<String> idList() {
		List<String> list = new ArrayList<String>();
		do {
			if (lex.matchDelim(','))
				lex.eatDelim(',');
			list.add(id());
		} while (lex.matchDelim(','));
		return list;
	}

	private List<Constant> constList() {
		List<Constant> list = new ArrayList<Constant>();
		do {
			if (lex.matchDelim(','))
				lex.eatDelim(',');
			list.add(constant());
		} while (lex.matchDelim(','));
		return list;
	}

	/*
	 * Methods for parsing queries.
	 */
	public QueryData queryCommand() {
		boolean isExplain = false;
		if (lex.matchKeyword("explain")) {
			lex.eatKeyword("explain");
			isExplain = true;
		}
		
		lex.eatKeyword("select");
		ProjectList projs = projectList();
		lex.eatKeyword("from");
		Set<String> tables = idSet();
		Predicate pred = new Predicate();
		if (lex.matchKeyword("where")) {
			lex.eatKeyword("where");
			pred = predicate();
		}
		/*
		 * Non-null group-by fields (but may be empty) if "group by" appears or
		 * there is an aggFn in the project list.
		 */
		Set<String> groupFields = null;
		if (lex.matchKeyword("group")) {
			lex.eatKeyword("group");
			lex.eatKeyword("by");
			groupFields = idSet();
		}
		if (groupFields == null && projs.aggregationFns() != null)
			groupFields = new HashSet<String>();
		// Need to preserve the order of sort fields
		List<String> sortFields = null;
		List<Integer> sortDirs = null;
		if (lex.matchKeyword("order")) {
			lex.eatKeyword("order");
			lex.eatKeyword("by");
			// neither null nor empty if "sort by" appears
			SortList sortList = sortList();
			sortFields = sortList.fieldList();
			sortDirs = sortList.directionList();
		}
		return new QueryData(isExplain, projs.asStringSet(), tables, pred,
				groupFields, projs.aggregationFns(), sortFields, sortDirs);
	}

	/*
	 * Methods for parsing projection.
	 */

	private ProjectList projectList() {
		ProjectList list = new ProjectList();
		do {
			if (lex.matchDelim(','))
				lex.eatDelim(',');
			if (lex.matchId())
				list.addField(id());
			else {
				AggregationFn aggFn = aggregationFn();
				list.addAggFn(aggFn);
			}
		} while (lex.matchDelim(','));
		return list;
	}

	private AggregationFn aggregationFn() {
		AggregationFn aggFn = null;
		if (lex.matchKeyword("avg")) {
			lex.eatKeyword("avg");
			lex.eatDelim('(');
			aggFn = new AvgFn(id());
			lex.eatDelim(')');
		} else if (lex.matchKeyword("count")) {
			lex.eatKeyword("count");
			lex.eatDelim('(');
			if (lex.matchKeyword("distinct")) {
				lex.eatKeyword("distinct");
				aggFn = new DistinctCountFn(id());
			} else
				aggFn = new CountFn(id());
			lex.eatDelim(')');
		} else if (lex.matchKeyword("max")) {
			lex.eatKeyword("max");
			lex.eatDelim('(');
			aggFn = new MaxFn(id());
			lex.eatDelim(')');
		} else if (lex.matchKeyword("min")) {
			lex.eatKeyword("min");
			lex.eatDelim('(');
			aggFn = new MinFn(id());
			lex.eatDelim(')');
		} else if (lex.matchKeyword("sum")) {
			lex.eatKeyword("sum");
			lex.eatDelim('(');
			aggFn = new SumFn(id());
			lex.eatDelim(')');
		} else
			throw new UnsupportedOperationException();
		return aggFn;
	}

	/*
	 * Methods for parsing predicate.
	 */

	private Predicate predicate() {
		Predicate pred = new Predicate(term());
		while (lex.matchKeyword("and")) {
			lex.eatKeyword("and");
			pred.conjunctWith(term());
		}
		return pred;
	}

	private Term term() {
		Expression lhs = queryExpression();
		Term.Operator op;
		if (lex.matchDelim('=')) {
			lex.eatDelim('=');
			op = OP_EQ;
		} else if (lex.matchDelim('>')) {
			lex.eatDelim('>');
			if (lex.matchDelim('=')) {
				lex.eatDelim('=');
				op = OP_GTE;
			} else
				op = OP_GT;
		} else if (lex.matchDelim('<')) {
			lex.eatDelim('<');
			if (lex.matchDelim('=')) {
				lex.eatDelim('=');
				op = OP_LTE;
			} else
				op = OP_LT;
		} else
			throw new UnsupportedOperationException();
		Expression rhs = queryExpression();
		return new Term(lhs, op, rhs);
	}

	private Expression queryExpression() {
		return lex.matchId() ? new FieldNameExpression(id())
				: new ConstantExpression(constant());
	}

	/*
	 * Methods for parsing sort.
	 */

	private SortList sortList() {
		SortList list = new SortList();
		do {
			if (lex.matchDelim(','))
				lex.eatDelim(',');
			if (lex.matchId()) {
				String fld = id();
				int dir = sortDirection();
				list.addField(fld, dir);
			} else {
				AggregationFn aggFn = aggregationFn();
				int dir = sortDirection();
				list.addAggFn(aggFn, dir);
			}
		} while (lex.matchDelim(','));
		return list;
	}

	private int sortDirection() {
		int dir = DIR_ASC;
		if (lex.matchKeyword("asc")) {
			lex.eatKeyword("asc");
		} else if (lex.matchKeyword("desc")) {
			lex.eatKeyword("desc");
			dir = DIR_DESC;
		}
		return dir;
	}

	/*
	 * Methods for parsing the various update commands.
	 */

	public Object updateCommand() {
		if (lex.matchKeyword("insert"))
			return insert();
		else if (lex.matchKeyword("delete"))
			return delete();
		else if (lex.matchKeyword("update"))
			return modify();
		else if (lex.matchKeyword("create"))
			return create();
		else if (lex.matchKeyword("drop"))
			return drop();
		else
			throw new UnsupportedOperationException();
	}

	private InsertData insert() {
		lex.eatKeyword("insert");
		lex.eatKeyword("into");
		String tblname = lex.eatId();
		lex.eatDelim('(');
		// Need to preserve the order of ids
		List<String> flds = idList();
		lex.eatDelim(')');
		lex.eatKeyword("values");
		lex.eatDelim('(');
		List<Constant> vals = constList();
		lex.eatDelim(')');
		return new InsertData(tblname, flds, vals);
	}

	private DeleteData delete() {
		lex.eatKeyword("delete");
		lex.eatKeyword("from");
		String tblname = lex.eatId();
		Predicate pred = new Predicate();
		if (lex.matchKeyword("where")) {
			lex.eatKeyword("where");
			pred = predicate();
		}
		return new DeleteData(tblname, pred);
	}

	private ModifyData modify() {
		lex.eatKeyword("update");
		String tblname = lex.eatId();
		lex.eatKeyword("set");
		Map<String, Expression> map = new HashMap<String, Expression>();
		while (lex.matchId()) {
			String fldname = id();
			lex.eatDelim('=');
			Expression newval = modifyExpression();
			map.put(fldname, newval);
			if (lex.matchDelim(','))
				lex.eatDelim(',');
		}
		Predicate pred = new Predicate();
		if (lex.matchKeyword("where")) {
			lex.eatKeyword("where");
			pred = predicate();
		}
		return new ModifyData(tblname, map, pred);
	}

	private Expression modifyExpression() {
		if (lex.matchKeyword("add")) {
			lex.eatKeyword("add");
			lex.eatDelim('(');
			Expression lhs = queryExpression();
			lex.eatDelim(',');
			Expression rhs = queryExpression();
			lex.eatDelim(')');
			return new BinaryArithmeticExpression(lhs, OP_ADD, rhs);
		} else if (lex.matchKeyword("sub")) {
			lex.eatKeyword("sub");
			lex.eatDelim('(');
			Expression lhs = queryExpression();
			lex.eatDelim(',');
			Expression rhs = queryExpression();
			lex.eatDelim(')');
			return new BinaryArithmeticExpression(lhs, OP_SUB, rhs);
		} else if (lex.matchKeyword("mul")) {
			lex.eatKeyword("mul");
			lex.eatDelim('(');
			Expression lhs = queryExpression();
			lex.eatDelim(',');
			Expression rhs = queryExpression();
			lex.eatDelim(')');
			return new BinaryArithmeticExpression(lhs, OP_MUL, rhs);
		} else if (lex.matchKeyword("div")) {
			lex.eatKeyword("div");
			lex.eatDelim('(');
			Expression lhs = queryExpression();
			lex.eatDelim(',');
			Expression rhs = queryExpression();
			lex.eatDelim(')');
			return new BinaryArithmeticExpression(lhs, OP_DIV, rhs);
		} else if (lex.matchId())
			return new FieldNameExpression(id());
		else
			return new ConstantExpression(constant());
	}

	/*
	 * Method for parsing various create commands.
	 */

	private Object create() {
		lex.eatKeyword("create");
		if (lex.matchKeyword("table"))
			return createTable();
		else if (lex.matchKeyword("view"))
			return createView();
		else if (lex.matchKeyword("index"))
			return createIndex();
		else
			throw new UnsupportedOperationException();
	}

	private CreateTableData createTable() {
		lex.eatKeyword("table");
		String tblname = lex.eatId();
		lex.eatDelim('(');
		Schema sch = fieldDefs();
		lex.eatDelim(')');
		return new CreateTableData(tblname, sch);
	}

	private Schema fieldDefs() {
		Schema schema = fieldDef();
		if (lex.matchDelim(',')) {
			lex.eatDelim(',');
			Schema schema2 = fieldDefs();
			schema.addAll(schema2);
		}
		return schema;
	}

	private Schema fieldDef() {
		String fldname = id();
		return fieldType(fldname);
	}

	private Schema fieldType(String fldName) {
		Schema schema = new Schema();
		if (lex.matchKeyword("int")) {
			lex.eatKeyword("int");
			schema.addField(fldName, INTEGER);
		} else if (lex.matchKeyword("long")) {
			lex.eatKeyword("long");
			schema.addField(fldName, BIGINT);
		} else if (lex.matchKeyword("double")) {
			lex.eatKeyword("double");
			schema.addField(fldName, DOUBLE);
		} else {
			lex.eatKeyword("varchar");
			lex.eatDelim('(');
			double arg = lex.eatNumericConstant();
			lex.eatDelim(')');
			schema.addField(fldName, VARCHAR((int) arg));
		}
		return schema;
	}

	private CreateViewData createView() {
		lex.eatKeyword("view");
		String viewname = lex.eatId();
		lex.eatKeyword("as");
		QueryData qd = queryCommand();
		return new CreateViewData(viewname, qd);
	}

	private CreateIndexData createIndex() {
		lex.eatKeyword("index");
		String idxName = lex.eatId();
		lex.eatKeyword("on");
		String tblName = lex.eatId();
		lex.eatDelim('(');
		List<String> fldNames = idList();
		lex.eatDelim(')');
		
		// Index type
		IndexType idxType = DEFAULT_INDEX_TYPE;
		if (lex.matchKeyword("using")) {
			lex.eatKeyword("using");
			
			if (lex.matchKeyword("hash")) {
				lex.eatKeyword("hash");
				idxType = IndexType.HASH;
			} else if (lex.matchKeyword("btree")) {
				lex.eatKeyword("btree");
				idxType = IndexType.BTREE;
			} else
				throw new UnsupportedOperationException();
		}
		
		return new CreateIndexData(idxName, tblName, fldNames, idxType);
	}

	/*
	 * Method for parsing various drop commands.
	 */

	private Object drop() {
		lex.eatKeyword("drop");
		if (lex.matchKeyword("table"))
			return dropTable();
		else if (lex.matchKeyword("view"))
			return dropView();
		else if (lex.matchKeyword("index"))
			return dropIndex();
		else
			throw new UnsupportedOperationException();
	}

	private DropTableData dropTable() {
		lex.eatKeyword("table");
		String tblname = lex.eatId();
		return new DropTableData(tblname);
	}

	private DropViewData dropView() {
		lex.eatKeyword("view");
		String viewname = lex.eatId();
		return new DropViewData(viewname);
	}

	private DropIndexData dropIndex() {
		lex.eatKeyword("index");
		String idxname = lex.eatId();
		return new DropIndexData(idxname);
	}
}

```

**QueryData**
```{java}
/*******************************************************************************
 * Copyright 2016, 2017 vanilladb.org contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *******************************************************************************/
package org.vanilladb.core.query.parse;

import static org.vanilladb.core.sql.RecordComparator.DIR_DESC;

import java.util.List;
import java.util.Set;

import org.vanilladb.core.sql.RecordComparator;
import org.vanilladb.core.sql.aggfn.AggregationFn;
import org.vanilladb.core.sql.predicate.Predicate;


public class QueryData {
	private boolean isExplain;
	private Set<String> projFields;
	private Set<String> tables;
	private Predicate pred;
	private Set<String> groupFields;
	private Set<AggregationFn> aggFn;
	private List<String> sortFields;
	private List<Integer> sortDirs;


	/**
	 * Saves the information of a SQL query.
	 * 
	 * @param projFields
	 *            a collection of field names
	 * @param tables
	 *            a collection of table names
	 * @param pred
	 *            the query predicate
	 * @param groupFields
	 *            a collection of grouping field names
	 * @param aggFn
	 *            a collection of aggregation functions
	 * @param sortFields
	 *            a list of field names for sorting
	 * @param sortDirs
	 *            a list of sort directions
	 */
	public QueryData(boolean isExplain, Set<String> projFields, Set<String> tables, Predicate pred,
			Set<String> groupFields, Set<AggregationFn> aggFn, List<String> sortFields, List<Integer> sortDirs) {
		
		this.isExplain = isExplain;
		this.projFields = projFields;
		this.tables = tables;
		this.pred = pred;
		this.groupFields = groupFields;
		this.aggFn = aggFn;
		this.sortFields = sortFields;
		this.sortDirs = sortDirs;
	}

	/**
	 * Return whether need to explain the query or not.
	 * 
	 * @return a boolean whether need to explain the query or not.
	 */
	public boolean isExplain(){
		return this.isExplain;
	}

	/**
	 * Returns the fields mentioned in the select clause.
	 * 
	 * @return a collection of field names
	 */
	public Set<String> projectFields() {
		return projFields;
	}

	/**
	 * Returns the tables mentioned in the from clause.
	 * 
	 * @return a collection of table names
	 */
	public Set<String> tables() {
		return tables;
	}

	/**
	 * Returns the predicate that describes which records should be in the
	 * output table.
	 * 
	 * @return the query predicate
	 */
	public Predicate pred() {
		return pred;
	}

	/**
	 * Returns the fields used to sort the query result.
	 * 
	 * @return a list of field names for sorting
	 */
	public List<String> sortFields() {
		return sortFields;
	}

	/**
	 * Returns a list of sort directions to the sorting fields. The values of
	 * sort directions are defined in {@link RecordComparator}.
	 * 
	 * @return a list of sort directions
	 */
	public List<Integer> sortDirections() {
		return sortDirs;
	}

	/**
	 * Returns the field names mentioned in the group by clause.
	 * 
	 * @return a collection of grouping field names
	 */
	public Set<String> groupFields() {
		return groupFields;
	}

	/**
	 * Returns the aggregation functions mentioned in the clause.
	 * 
	 * @return a collection of aggregation functions
	 */
	public Set<AggregationFn> aggregationFn() {
		return aggFn;
	}



	public String toString() {
		StringBuilder result = new StringBuilder();
		result.append("select ");
		for (String fldname : projFields)
			result.append(fldname + ", ");
		// remove the last comma
		result.delete(result.length() - 2, result.length());
		result.append(" from ");
		for (String tblname : tables)
			result.append(tblname + ", ");
		result.delete(result.length() - 2, result.length());

		String predString = pred.toString();
		if (!predString.equals(""))
			result.append(" where " + predString);

		if (groupFields != null) {
			result.append(" group by ");
			for (String gbf : groupFields)
				result.append(gbf + ", ");
			result.delete(result.length() - 2, result.length());
		}

		if (sortFields != null) {
			result.append(" sort by ");
			for (int i = 0; i < sortFields.size(); i++) {
				String sbf = sortFields.get(i);
				int sbd = sortDirs.get(i);
				result.append(sbf + (sbd == DIR_DESC ? " desc" : "") + ", ");
			}
			result.delete(result.length() - 2, result.length());
		}
		return result.toString();
	}
}

```

**Lexer**

```{java}
/*******************************************************************************
 * Copyright 2016, 2017 vanilladb.org contributors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *******************************************************************************/
package org.vanilladb.core.query.parse;

import java.io.IOException;
import java.io.StreamTokenizer;
import java.io.StringReader;
import java.util.Arrays;
import java.util.Collection;

/**
 * The lexical analyzer.
 */
public class Lexer {
	private Collection<String> keywords;
	private StreamTokenizer tok;

	/**
	 * Creates a new lexical analyzer for the specified SQL statement.
	 * 
	 * @param s
	 *            the SQL statement
	 */
	public Lexer(String s) {
		initKeywords();
		tok = new StreamTokenizer(new StringReader(s));
		tok.wordChars('_', '_');
		tok.ordinaryChar('.');
		/*
		 * Tokens in TT_WORD type like ids and keywords are converted into lower
		 * case.
		 */
		tok.lowerCaseMode(true);
		nextToken();
	}

	/*
	 * Methods to check the status of the current token.
	 */

	/**
	 * Returns true if the current token is the specified delimiter character.
	 * 
	 * @param delimiter
	 *            a character denoting the delimiter
	 * @return true if the delimiter is the current token
	 */
	public boolean matchDelim(char delimiter) {
		return delimiter == (char) tok.ttype;
	}

	/**
	 * Returns true if the current token is a numeric value.
	 * 
	 * @return true if the current token is a numeric value
	 */
	public boolean matchNumericConstant() {
		return tok.ttype == StreamTokenizer.TT_NUMBER;
	}

	/**
	 * Returns true if the current token is a string.
	 * 
	 * @return true if the current token is a string
	 */
	public boolean matchStringConstant() {
		return '\'' == (char) tok.ttype;
	}

	/**
	 * Returns true if the current token is the specified keyword.
	 * 
	 * @param keyword
	 *            the keyword string
	 * @return true if that keyword is the current token
	 */
	public boolean matchKeyword(String keyword) {
		return tok.ttype == StreamTokenizer.TT_WORD && tok.sval.equals(keyword)
				&& keywords.contains(tok.sval);
	}

	/**
	 * Returns true if the current token is a legal identifier.
	 * 
	 * @return true if the current token is an identifier
	 */
	public boolean matchId() {
		return tok.ttype == StreamTokenizer.TT_WORD
				&& !keywords.contains(tok.sval);
	}

	/*
	 * Methods to "eat" the current token.
	 */

	/**
	 * Throws an exception if the current token is not the specified delimiter.
	 * Otherwise, moves to the next token.
	 * 
	 * @param delimiter
	 *            a character denoting the delimiter
	 */
	public void eatDelim(char delimiter) {
		if (!matchDelim(delimiter))
			throw new BadSyntaxException();
		nextToken();
	}

	/**
	 * Throws an exception if the current token is not an integer. Otherwise,
	 * returns that integer and moves to the next token.
	 * 
	 * @return the integer value of the current token
	 */
	public double eatNumericConstant() {
		if (!matchNumericConstant())
			throw new BadSyntaxException();
		double d = tok.nval;
		nextToken();
		return d;
	}

	/**
	 * Throws an exception if the current token is not a string. Otherwise,
	 * returns that string and moves to the next token.
	 * 
	 * @return the string value of the current token
	 */
	public String eatStringConstant() {
		if (!matchStringConstant())
			throw new BadSyntaxException();
		/*
		 * The input string constant is a quoted string token likes 'str', and
		 * its token type (ttype) is the quote character. So the string
		 * constants are not converted to lower case.
		 */
		String s = tok.sval;
		nextToken();
		return s;
	}

	/**
	 * Throws an exception if the current token is not the specified keyword.
	 * Otherwise, moves to the next token.
	 * 
	 * @param keyword
	 *            the keyword string
	 */
	public void eatKeyword(String keyword) {
		if (!matchKeyword(keyword))
			throw new BadSyntaxException();
		nextToken();
	}

	/**
	 * Throws an exception if the current token is not an identifier. Otherwise,
	 * returns the identifier string and moves to the next token.
	 * 
	 * @return the string value of the current token
	 */
	public String eatId() {
		if (!matchId())
			throw new BadSyntaxException();
		String s = tok.sval;
		nextToken();
		return s;
	}

	private void nextToken() {
		try {
			tok.nextToken();
		} catch (IOException e) {
			throw new BadSyntaxException();
		}
	}

	private void initKeywords() {
		keywords = Arrays.asList("select", "from", "where", "and", "insert",
				"into", "values", "delete", "drop", "update", "set", "create", "table",
				"int", "double", "varchar", "view", "as", "index", "on",
				"long", "order", "by", "asc", "desc", "sum", "count", "avg",
				"min", "max", "distinct", "group", "add", "sub", "mul", "div",
				"using", "hash", "btree", "explain");
	}
}

```

			String viewdef = VanillaDb.catalogMgr().getViewDef(tblname, tx);

```{java}
  public java.lang.String getViewDef(java.lang.String viewName, org.vanilladb.core.storage.tx.Transaction tx) {
    return null;
  }
```