• Donald H. (Donnie) Pinkston, III's avatar
    Documents and code changes for Assignment 3 · c7b4e8f9
    Donald H. (Donnie) Pinkston, III authored
    The design document and information document are included under the doc
    directory now.
    
    Added a lot of documentation, particularly to the Schema class.
    
    Made a few changes to the ArithmeticOperator and BooleanOperator
    classes' simplify() methods so that we can do some basic
    simplifications.
    
    Added the StatisticsUpdater so that it's easier for students to modify
    statistics based on selection predicates.
    
    Fixed a bug in SelectClause where ORDER BY clauses were using the
    FROM-clause schema rather than the SELECT-clause schema.
    c7b4e8f9
SelectClause.java 22.9 KB
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683
package edu.caltech.nanodb.queryast;


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

import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.LogManager;

import edu.caltech.nanodb.expressions.ColumnName;
import edu.caltech.nanodb.expressions.Expression;
import edu.caltech.nanodb.expressions.OrderByExpression;
import edu.caltech.nanodb.queryeval.InvalidSQLException;
import edu.caltech.nanodb.relations.ColumnInfo;
import edu.caltech.nanodb.relations.Schema;
import edu.caltech.nanodb.relations.SchemaNameException;
import edu.caltech.nanodb.server.NanoDBServer;
import edu.caltech.nanodb.storage.TableManager;


/**
 * This class represents a single <tt>SELECT ...</tt> statement or clause.
 * <tt>SELECT</tt> statements can appear as clauses within other expressions,
 * so the class is written to be used easily within other classes.
 */
public class SelectClause {

    /** A logging object for reporting anything interesting that happens. **/
    private static Logger logger = LogManager.getLogger(SelectClause.class);


    /**
     * The parent of this select-clause, if it is a nested subquery;
     * {@code null} otherwise.
     */
    private SelectClause parentSelect;


    /**
     * This flag indicates whether the <tt>SELECT</tt> expression should
     * generate duplicate rows, or whether it should simply produce distinct
     * or unique rows.
     */
    private boolean distinct = false;


    /**
     * The specification of values to be produced by the <tt>SELECT</tt>
     * clause.  These expressions comprise the Generalized Project operation
     * portion of the command.
     */
    private List<SelectValue> selectValues = new ArrayList<>();


    /**
     * This field holds a hierarchy of one or more base and derived relations
     * that produce the rows considered by this <tt>SELECT</tt> clause.  If
     * the <tt>SELECT</tt> expression has no <tt>FROM</tt> clause, this field
     * will be <tt>null</tt>.
     */
    private FromClause fromClause = null;


    /**
     * If a <tt>WHERE</tt> expression is specified, this field will refer to
     * the expression to be evaluated.
     */
    private Expression whereExpr = null;


    /**
     * This collection holds zero or more entries specifying <tt>GROUP BY</tt>
     * values.  If the <tt>SELECT</tt> expression has no <tt>GROUP BY</tt>
     * clause, this collection will be empty.
     */
    private List<Expression> groupByExprs = new ArrayList<>();


    /**
     * If a <tt>HAVING</tt> expression is specified, this field will refer to
     * the expression to be evaluated.
     */
    private Expression havingExpr = null;


    /**
     * This collection holds zero or more entries specifying <tt>ORDER BY</tt>
     * values.  If the <tt>SELECT</tt> expression has no <tt>ORDER BY</tt>
     * clause, this collection will be empty.
     */
    private List<OrderByExpression> orderByExprs = new ArrayList<>();


    /**
     * The maximum number of rows that may be returned by the <tt>SELECT</tt>
     * clause.  The default value of 0 means "no limit".
     */
    private int limit = 0;


    /**
     * The offset of the first row to return from the <tt>SELECT</tt> clause.
     * Earlier rows will be computed but not returned.  The default value of 0
     * means "start with the first row."
     */
    private int offset = 0;


    /**
     * When preparing SQL commands for execution, this value is filled in with
     * the schema that this <tt>SELECT</tt> clause produces.
     */
    private Schema resultSchema = null;


    /**
     * When preparing SQL commands for execution, this value is filled in with
     * the schema that this query's <tt>FROM</tt> clause produces.
     */
    private Schema fromSchema = null;


    /**
     * If this query is correlated with one or more enclosing queries, this
     * will contain column names, and the corresponding references to the
     * enclosing queries.
     *
     * @design (Donnie) We need to know both the column names and the
     *         corresponding parent-queries that will generate those values,
     *         so that we can set up the execution plan properly.
     */
    private HashMap<ColumnName, SelectClause> correlatedWith = new HashMap<>();


    /**
     * Mark the select clause's results as being distinct or not distinct.
     * This corresponds to whether the SQL command is
     * "<tt>SELECT [ALL] ...</tt>" or "<tt>SELECT DISTINCT ...</tt>".
     *
     * @param distinct If true, specifies that the results of this select
     *        clause are distinct.  If false, the results of the clause are
     *        not distinct.
     */
    public void setDistinct(boolean distinct) {
        this.distinct = distinct;
    }


    /**
     * Returns true if the select clause's results are to be distinct, or
     * false if the clause's results are not distinct.
     */
    public boolean isDistinct() {
        return distinct;
    }


    /**
     * Adds a specification to the set of values produced by this
     * <tt>SELECT</tt> clause.  This method is called by the parser as a
     * <tt>SELECT</tt> command (or subquery) is being parsed.
     */
    public void addSelectValue(SelectValue selectValue) {
        if (selectValue == null)
            throw new NullPointerException();

        selectValues.add(selectValue);
    }


    /**
     * Retrieves the select values for this select clause.
     *
     * @return the select values
     */
    public List<SelectValue> getSelectValues() {
        return selectValues;
    }


    public boolean isTrivialProject() {
        if (selectValues.size() == 1) {
            SelectValue selVal = selectValues.get(0);
            if (selVal.isWildcard() && !selVal.getWildcard().isTableSpecified())
                return true;
        }
        return false;
    }


    /**
     * Returns the parent of this query if it is a subquery; {@code null}
     * otherwise.
     *
     * @return the parent of this query if it is a subquery; {@code null}
     *         otherwise.
     */
    public SelectClause getParentSelect() {
        return parentSelect;
    }


    /**
     * Sets the hierarchy of base and derived relations that produce the rows
     * considered by this <tt>SELECT</tt> clause.
     */
    public void setFromClause(FromClause fromClause) {
        this.fromClause = fromClause;
    }


    /**
     * Retrieves the from clause for this select clause.  This can be
     * {@code null} if the query doesn't specify a FROM clause.
     *
     * @return the from clause
     */
    public FromClause getFromClause() {
        return fromClause;
    }


    /**
     * Returns the schema of the data produced by the FROM clause of this
     * query.  If the query has no FROM clause, this will be an empty schema.
     *
     * @return the schema produced by the FROM clause of this query, or an
     *         empty schema if the query has no FROM clause.
     */
    public Schema getFromSchema() {
        return fromSchema;
    }


    /**
     * Sets the expression for the <tt>WHERE</tt> clause.  A {@code null}
     * value indicates that the <tt>SELECT</tt> clause has no <tt>WHERE</tt>
     * condition.
     */
    public void setWhereExpr(Expression whereExpr) {
        this.whereExpr = whereExpr;
    }


    /**
     * Retrieves the where clause from this from clause.
     *
     * @return the where exprssion
     */
    public Expression getWhereExpr() {
        return whereExpr;
    }


    public void addGroupByExpr(Expression groupExpr) {
        groupByExprs.add(groupExpr);
    }


    public List<Expression> getGroupByExprs() {
        return groupByExprs;
    }


    public void setHavingExpr(Expression havingExpr) {
        this.havingExpr = havingExpr;
    }


    public Expression getHavingExpr() {
        return havingExpr;
    }


    public void addOrderByExpr(OrderByExpression orderByExpr) {
        orderByExprs.add(orderByExpr);
    }


    public List<OrderByExpression> getOrderByExprs() {
        return orderByExprs;
    }


    /**
     * If a <tt>LIMIT</tt> clause is specified, this method returns the
     * specified limit; otherwise, the default of 0 is returned.
     *
     * @return the offset specified in the SQL
     */
    public int getLimit() {
        return limit;
    }


    /**
     * Set the upper limit of how many rows should be produced by this query.
     * A value of 0 means "unlimited."  Negative values are disallowed and
     * will cause an exception to be thrown.
     *
     * @param limit a positive number specifying the maximum number of tuples
     *        to produce, or 0 to specify "unlimited."
     */
    public void setLimit(int limit) {
        if (limit < 0) {
            throw new InvalidSQLException("Limit must be at least 0 (got " +
                limit + ")");
        }

        this.limit = limit;
    }


    /**
     * If an <tt>OFFSET</tt> clause is specified, this method returns the
     * specified offset; otherwise, the default of 0 is returned.
     *
     * @return the offset specified in the SQL
     */
    public int getOffset() {
        return offset;
    }


    /**
     * Set the starting offset for the rows that should be produced by this
     * query.  A value of 0 means "start with the first row" (in other words,
     * "no offset").  Negative values are disallowed and will cause an
     * exception to be thrown.
     *
     * @param offset a positive number specifying the number of tuples to skip
     *        during query evaluation, or 0 to specify "start at the
     *        beginning."
     */
    public void setOffset(int offset) {
        if (offset < 0) {
            throw new InvalidSQLException("Offset must be at least 0 (got " +
                offset + ")");
        }

        this.offset = offset;
    }


    /**
     * Returns true if the select clause is correlated with some enclosing
     * query, or false otherwise.
     *
     * @return true if the select clause is correlated with some enclosing
     *         query, or false otherwise.
     */
    public boolean isCorrelated() {
        return !correlatedWith.isEmpty();
    }


    public Set<ColumnName> getCorrelatedColumns() {
        return correlatedWith.keySet();
    }


    /**
     * This method computes the resulting schema from this query, and in the
     * process it performs various semantic checks as well.
     *
     * @param tableManager the table manager to use for retrieving schema info
     *
     * @param parentSelect the enclosing SELECT query if this is a nested
     *        subquery, or {@code null} if this is a top-level query
     *
     * @return the schema of this select clause's result
     *
     * @throws SchemaNameException if the select clause contains some kind of
     *         semantic error involving schemas that are referenced
     */
    public Schema computeSchema(TableManager tableManager,
        SelectClause parentSelect) throws SchemaNameException {

        this.parentSelect = parentSelect;

        // Compute the schema of the FROM clause first.  We assume that no
        // subqueries in the FROM clause are correlated with this or enclosing
        // queries.
        if (fromClause != null) {
            fromSchema = fromClause.computeSchema(tableManager);
        }
        else {
            // No FROM clause - no FROM schema...
            fromSchema = new Schema();
        }

        // This helper-object is used for handling subqueries in the SELECT,
        // WHERE and HAVING clauses.  These nested queries need to have their
        // schemas computed, and possible correlated evaluation identified.
        SubquerySchemaComputer subquerySchemaComputer =
            new SubquerySchemaComputer(this, tableManager);

        // Make sure that all expressions in this SELECT clause reference
        // known and non-ambiguous names from the FROM clause.

        // SELECT values:  SELECT a, b + c, tbl.* ...
        List<ColumnInfo> resultColumnInfos = new ArrayList<>();
        Set<String> fromTables = fromSchema.getTableNames();

        for (SelectValue selVal : selectValues) {
            if (selVal.isWildcard()) {
                // Make sure that if a table name is specified, that the table
                // name is in the query's FROM-clause schema.
                ColumnName colName = selVal.getWildcard();
                if (colName.isTableSpecified()) {
                    if (!fromTables.contains(colName.getTableName())) {
                        throw new SchemaNameException(String.format(
                            "SELECT-value %s specifies an unrecognized " +
                            "table name.", colName));
                    }
                }
            }
            else {
                // An expression that is not a wildcard.  It could contain
                // column references that need to be resolved.  Also, it could
                // contain a scalar subquery, particularly one that requires
                // correlated evaluation.
                Expression expr = selVal.getExpression();

                // Get the list of column-values, and resolve each one.
                // Note that this will not descend into subqueries.
                resolveExpressionRefs("SELECT-value", expr, fromSchema,
                    /* checkParentQueries */ true);

                // If the expression contains any subqueries, resolve any
                // column-references that reference this or enclosing queries.
                expr.traverse(subquerySchemaComputer);
            }

            // Update the result-schema with this select-value's column-info(s).
            resultColumnInfos.addAll(selVal.getColumnInfos(fromSchema, resultSchema));
        }

        // Construct a resultSchema which is the "summation" of all
        // SelectValues' columnInfos.
        resultSchema = new Schema(resultColumnInfos);

        logger.debug("Query schema:  " + resultSchema);
        logger.debug("FROM-clause schema:  " + fromSchema);

        // WHERE clause:
        if (whereExpr != null) {
            resolveExpressionRefs("WHERE clause", whereExpr, fromSchema,
                /* checkParentQueries */ true);

            whereExpr.traverse(subquerySchemaComputer);
        }

        // GROUP BY clauses:
        for (Expression expr : groupByExprs) {
            // GROUP BY expressions aren't allowed to have subqueries.
            resolveExpressionRefs("GROUP BY clause", expr, fromSchema,
                /* checkParentQueries */ false);
        }

        // HAVING clause:
        if (havingExpr != null) {
            // The HAVING clause can reference values produced by grouping and
            // aggregation.  However, according to the SQL standard, it won't
            // see any values except from the FROM-clause's schema.
            resolveExpressionRefs("HAVING clause", havingExpr, fromSchema,
                /* checkParentQueries */ true);

            havingExpr.traverse(subquerySchemaComputer);
        }

        // ORDER BY clauses:  These are computed from the result of the
        // SELECT clause, not the result of the FROM clause.
        for (OrderByExpression expr : orderByExprs) {
            // ORDER BY expressions aren't allowed to have subqueries.
            resolveExpressionRefs("ORDER BY clause", expr.getExpression(),
                resultSchema, /* checkParentQueries */ false);
        }

        // All done!  Return the computed schema.
        return resultSchema;
    }


    /**
     * Returns the schema for this select clause, or {@code null} if the
     * {@link #computeSchema} method hasn't yet been called on this clause.
     *
     * @return the schema for this select clause
     */
    public Schema getSchema() {
        return resultSchema;
    }


    /**
     * This helper function goes through the expression and verifies that
     * every symbol-reference corresponds to an actual value produced by the
     * <tt>FROM</tt>-clause of the <tt>SELECT</tt> query.  Any column-names
     * that don't include a table-name are also updated to include the proper
     * table-name.
     * <p>
     * It's possible to have symbols that don't reference columns in the
     * <tt>FROM</tt> clause, if a query is correlated with an enclosing query.
     * In these cases, the unresolvable attributes are collected so they can
     * be resolved at the end of the process.
     *
     * @param desc A short string describing the context of the expression,
     *        since expressions can appear in the <tt>SELECT</tt> clause, the
     *        <tt>WHERE</tt> clause, the <tt>GROUP BY</tt> clause, etc.
     *
     * @param expr The expression that will be evaluated.
     *
     * @param s The schema against which the expression will be evaluated.
     *
     * @param checkParentQueries if this is true and the column-name can't be
     *        resolved against the current query, any parent queries will also
     *        be checked for the column-name.  This allows correlated queries
     *        to be resolved properly.
     *
     * @throws SchemaNameException if an expression-reference cannot be resolved
     *         against the specified schema, either because the named column
     *         or table doesn't appear in the schema, or if a column name is
     *         ambiguous.
     */
    private void resolveExpressionRefs(String desc, Expression expr, Schema s,
        boolean checkParentQueries) throws SchemaNameException {

        // Get the list of column-values in the expression, and resolve each one.
        // (This won't include subquery expressions, since they will reference
        // the subquery's schema.)
        ArrayList<ColumnName> exprColumns = new ArrayList<>();
        expr.getAllSymbols(exprColumns);

        for (ColumnName colName : exprColumns) {
            assert !colName.isColumnWildcard();
            resolveColumnRef(desc, expr, colName, s, checkParentQueries);
        }
    }


    /**
     * This helper function attempts to resolve a specific column-name against
     * a query's schema.

     * @param desc A short string describing the context of the expression,
     *        since expressions can appear in the <tt>SELECT</tt> clause, the
     *        <tt>WHERE</tt> clause, the <tt>GROUP BY</tt> clause, etc.
     *
     * @param expr The expression that will be evaluated.
     *
     * @param colName The column-name to resolve.
     *
     * @param s The schema against which the expression will be evaluated.
     *
     * @param checkParentQueries if this is true and the column-name can't be
     *        resolved against the current query, any parent queries will also
     *        be checked for the column-name.  This allows correlated queries
     *        to be resolved properly.
     *
     * @throws SchemaNameException if an expression-reference cannot be resolved
     *         against the specified schema, either because the named column
     *         or table doesn't appear in the schema, or if a column name is
     *         ambiguous.
     */
    private void resolveColumnRef(String desc, Expression expr,
        ColumnName colName, Schema s, boolean checkParentQueries)
        throws SchemaNameException {

        // This flag indicates whether we are referencing a column in a parent
        // query.
        boolean parentRef = false;

        // This is the query that we are examining.
        SelectClause clause = this;
        while (true) {
            // Attempt to resolve the column-name against the current schema's
            // columns.
            SortedMap<Integer, ColumnInfo> found = s.findColumns(colName);

            if (found.size() == 1) {
                // Found exactly one column that matches!
                if (!colName.isTableSpecified()) {
                    // Update the column-reference with the table name.
                    ColumnInfo colInfo = found.get(found.firstKey());
                    colName.setTableName(colInfo.getTableName());
                }

                if (parentRef) {
                    // This column-name references a column produced by a
                    // parent query, not this query.
                    assert clause != this;

                    // Sanity-check:  have we already seen this column name?
                    // If so, make sure that we find the same clause each time
                    if (correlatedWith.containsKey(colName) &&
                        correlatedWith.get(colName) != clause) {
                        throw new IllegalStateException(String.format(
                            "Column name %s is associated with two " +
                            "different queries", colName));
                    }
                    correlatedWith.put(colName, clause);
                }

                return;
            }

            if (found.size() > 1) {
                // In this case the column name is ambiguous - there may be
                // multiple columns in the schema with the same column name
                // but different table names.
                throw new SchemaNameException(String.format(
                    "%s %s contains an ambiguous column %s; found %s.",
                    desc, expr, colName, found.values()));
            }

            // We should only get to this point in the loop if we couldn't
            // find a column with the specified name.
            assert found.size() == 0;

            if (checkParentQueries && clause.parentSelect != null) {
                clause = clause.parentSelect;
                s = clause.getFromSchema();
                parentRef = true;
            }
            else {
                throw new SchemaNameException(String.format(
                    "%s %s references an unknown column %s.",
                    desc, expr, colName));
            }
        }
    }


    @Override
    public String toString() {
        StringBuilder buf = new StringBuilder();

        buf.append("SelectClause[id=").append(System.identityHashCode(this)).append('\n');

        if (selectValues.size() > 0)
            buf.append("\tvalues=").append(selectValues).append('\n');

        if (fromClause != null)
            buf.append("\tfrom=").append(fromClause).append('\n');

        if (whereExpr != null)
            buf.append("\twhere=").append(whereExpr).append('\n');

        if (groupByExprs.size() > 0)
            buf.append("\tgroup_by=").append(groupByExprs).append('\n');

        if (havingExpr != null)
            buf.append("\thaving=").append(havingExpr).append('\n');

        if (orderByExprs.size() > 0)
            buf.append("\torder_by=").append(orderByExprs).append('\n');

        if (correlatedWith.size() > 0) {
            buf.append("\tcorrelatedWith=[");

            boolean first = true;
            for (Map.Entry e: correlatedWith.entrySet()) {
                if (first)
                    first = false;
                else
                    buf.append(',');

                buf.append(e.getKey()).append(':');
                buf.append(System.identityHashCode(e.getValue()));
            }
            buf.append("]\n");
        }

        buf.append(']');

        return buf.toString();
    }
}