Quadcap Embeddable Database

com/quadcap/sql/SelectExpression.java

Go to the documentation of this file.

package com.quadcap.sql;

/* Copyright 1999 - 2003 Quadcap Software.  All rights reserved.
 *
 * This software is distributed under the Quadcap Free Software License.
 * This software may be used or modified for any purpose, personal or
 * commercial.  Open Source redistributions are permitted.  Commercial
 * redistribution of larger works derived from, or works which bundle
 * this software requires a "Commercial Redistribution License"; see
 * http://www.quadcap.com/purchase.
 *
 * Redistributions qualify as "Open Source" under  one of the following terms:
 *   
 *    Redistributions are made at no charge beyond the reasonable cost of
 *    materials and delivery.
 *
 *    Redistributions are accompanied by a copy of the Source Code or by an
 *    irrevocable offer to provide a copy of the Source Code for up to three
 *    years at the cost of materials and delivery.  Such redistributions
 *    must allow further use, modification, and redistribution of the Source
 *    Code under substantially the same terms as this license.
 *
 * Redistributions of source code must retain the copyright notices as they
 * appear in each source code file, these license terms, and the
 * disclaimer/limitation of liability set forth as paragraph 6 below.
 *
 * Redistributions in binary form must reproduce this Copyright Notice,
 * these license terms, and the disclaimer/limitation of liability set
 * forth as paragraph 6 below, in the documentation and/or other materials
 * provided with the distribution.
 *
 * The Software is provided on an "AS IS" basis.  No warranty is
 * provided that the Software is free of defects, or fit for a
 * particular purpose.  
 *
 * Limitation of Liability. Quadcap Software shall not be liable
 * for any damages suffered by the Licensee or any third party resulting
 * from use of the Software.
 */

import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;

import java.util.Vector;

import java.sql.SQLException;

import com.quadcap.sql.types.Op;
import com.quadcap.sql.types.Value;
import com.quadcap.sql.types.ValueLong;
import com.quadcap.sql.types.ValueNull;

import com.quadcap.util.Debug;

/**
 * A table expression representing a <b>SELECT</b> clause.
 *
 * @author Stan Bailes
 */

public class SelectExpression extends TableExpression
    implements Externalizable
{
    boolean                     distinct                = false;
    Vector                      items                   = null;
    Vector                      from                    = null;
    Vector                      groupBy                 = null;
    Expression                  having                  = null;
    Vector                      aggregates              = null;

    /**
     * Default constructor
     */
    public SelectExpression() {}

    /**
     * The typical 'select from table where' stuff
     */
    public SelectExpression(String tableName, Expression where) {
        Vector v = new Vector();
        v.addElement(new SelectFromTable(tableName));
        this.setFrom(v);
        this.setWhere(where);
    }

    /**
     * Get the FROM list
     */
    public Vector getFrom() {
        return from;
    }

    /**
     * Set the DISTINCT flag
     */
    public void setDistinct(boolean b) { this.distinct = b; }

    /**
     * Set the select items (i.e., the colums returned from this select)
     */
    public void setItems(Vector v) { this.items = v; }

    /**
     * Set the from list (a list of tables is implicitly joined)
     */
    public void setFrom(Vector v) { this.from = v; }

    /**
     * Set the GROUP BY clause as a list of names
     */
    public void setGroupBy(Vector v) { this.groupBy = v; }

    /**
     * Set the HAVING expression
     */
    public void setHaving(Expression e) { this.having = e; }

    /**
     * We're a table
     */
    public int rank() { return 2; }

    /**
     * Well, a bunch of things can prevent us from being updateable.
     * Here are the ones we know about:
     */
    public boolean isUpdatable() {
        if (groupBy != null) return false;
        if (having != null) return false;
        if (distinct) return false;
        if (from == null || from.size() > 1) return false;
        if (aggregates != null && aggregates.size() > 0) return false;

        TableExpression t = (TableExpression)from.elementAt(0);
        if (!t.isUpdatable()) return false;
        
        return true;    // Good luck, sir.
    }

    /**
     * Cross-join multiple tables in 'from' clause.
     *
     * TODO:
     *  First, tables which have selection constraintsfind pairs
     *  of tables that have candidate join columns and greedily join
     *  them.  Next, pick tables which have matching non-key join
     *  columns and join them Finally, join all the rest.
     */    
    TableExpression scheduleJoin() throws SQLException {
        while (from.size() > 1) {
            TableExpression a = (TableExpression)from.elementAt(0);
            TableExpression b = (TableExpression)from.elementAt(1);
            JoinedTable t = new JoinedTable(Op.CROSS, a, b);
            //t.setOnExpression(where);
            from.removeElementAt(0);
            from.setElementAt(t, 0);
        }
        TableExpression item = (TableExpression)from.elementAt(0);
        return item;
    }

    /**
     * This is the main entry point to this madness.  Our handling of
     * selects is fairly literal, and pretty brute force.  Things work
     * much better if there are appropriate indexes to use based on the
     * query.....
     */
    public Cursor getCursor(Session session, Cursor cur) throws SQLException {
        if (from == null) {
            Row row = new Row(items.size());
            TupleImpl t = new TupleImpl();
            for (int i = 0; i < items.size(); i++) {
                SelectItem item = (SelectItem)items.elementAt(i);
                Expression expr = item.getExpression();
                Value v = expr.getValue(session, cur);
                String name = item.getAsName();
                if (name == null) name = "Column" + i;
                t.addColumn(name, v.getType());
                row.set(i+1, expr.getValue(session, cur));
            }
            return new StaticCursor(session, t, row);
        }
        TableExpression tab = null;
        
        if (from.size() > 1) {
            tab = scheduleJoin();
        } else {
            tab = (TableExpression)from.elementAt(0);
        }

        // give the join or query a chance to optimize
        tab.setWhere(where);

        Cursor c = tab.getCursor(session, cur);
        if (where != null) {
            // Actually, we could avoid creating a predicate cursor
            // in cases where the upstream index cursor is already
            // sufficient.
            c = new PredicateCursor(session, c, where);
        }
        if (groupBy != null) {
            GroupByCursor gc = new GroupByCursor(session, c, groupBy);
            c = gc;
            Vector tItems = items;  // why alias items here? XX
            if (having != null) {
                int cnt = (items == null) ? 0 : items.size();
                tItems = new Vector(cnt + 1);
                for (int i = 0; i < cnt; i++) {
                    tItems.addElement(items.elementAt(i));
                }
                tItems.addElement(new SelectItem(having));
            }
            if (isAggregate(session, tItems)) {
                ItemsCursor ic = new ItemsCursor(session, gc, tItems);
                c = new AggregateCursor(session, ic, gc, aggregates);
                if (having != null) {
                    c = new HavingCursor(session, c);
                }
            } else if (tItems != null) {
                ItemsCursor ic = new ItemsCursor(session, gc, tItems);
                c = ic;
                c = new AggregateCursor(session, ic, gc, aggregates);
                if (having != null) {
                    c = new HavingCursor(session, c);
                }
            }
        } else {
            if (isAggregate(session, items)) {
                Cursor optimized = optimizeAggregate(session, c, items);
                if (optimized != null) {
                    c = optimized;
                } else {
                    ItemsCursor ic = new ItemsCursor(session, c, items);
                    c = new AggregateCursor(session, ic, null, aggregates);
                }
            } else {
                if (items != null) {
                    c = new ItemsCursor(session, c, items);
                }
            }
        }
        if (distinct) {
            c = new DistinctCursor(session, c);
        }

        if (cur != null) c.setOuterCursor(cur);
        //#ifdef DEBUG
        showCursor(c);
        //#endif
        return c;
    }

    /**
     * Visitor class used to analyze the select expression for aggregate usage
     */
    class IsAggregate implements ExpressionVisitor {
        Session                 session         = null;
        Vector                  aggregates      = null;
        boolean                 seenName        = false;
        boolean                 seenAggregate   = false;

        public IsAggregate(Session session) {
            this.session = session;
        }
        
        public void visit(Expression sub) {
            if (sub instanceof AggregateExpression) {
                seenAggregate = true;
                //try {
                //    ((AggregateExpression)sub).reset(session);
                //} catch (IOException e) {
                //    Debug.print(e);
                //}
                if (aggregates == null) {
                    aggregates = new Vector();
                }
                aggregates.addElement(sub);
            } else {
                seenName |= (sub instanceof NameExpression);
                sub.visitSubExpressions(this);
            }
        }
        
        void reset() {
            seenName = seenAggregate = false;
        }
    }

    /**
     * Check the list of select items to see if any of them are aggregate
     * expressions.  (Side effect: set 'aggregates' variable.)
     */
    boolean isAggregate(Session session, Vector items) throws SQLException {
        if (items == null) return false;
        int cnt = 0;
        IsAggregate isVis = new IsAggregate(session);
        for (int i = 0; i < items.size(); i++) {
            SelectItem item = (SelectItem)items.elementAt(i);
            Expression expression = item.getExpression();
            isVis.reset();
            isVis.visit(expression);
            if (isVis.seenAggregate && isVis.seenName && groupBy == null) {
                throw new SQLException("Expressions can't mix aggregate and " +
                                       "non-aggregate values", "42000");
            }
            if (isVis.seenAggregate) cnt++;
        }
        this.aggregates = isVis.aggregates;
        if (cnt == 0) return false;
        return true;
    }

    /**
     * Helper to create a cursor containing a single constant value.
     */
    Cursor staticCursor(Session session, Cursor c, Vector items, Value v)
        throws SQLException
    {
        Row r = new Row(1);
        r.set(1, v);
        ItemsCursor it = new ItemsCursor(session, c, items);
        return new StaticCursor(session, it, r);
    }

    /**
     * Identify cases of MIN(column) or MAX(column) on indexed columns.
     * Compute the value directly and replace the index cursor with a
     * static cursor containing the value.
     */
    Cursor optimizeAggregate(Session session, Cursor c, Vector items)
        throws SQLException
    {
        Cursor ret = null;
        if (c instanceof IndexCursor) {
            IndexCursor ic = (IndexCursor)c;
            if (items.size() == 1) {
                SelectItem item = (SelectItem)items.get(0);
                Expression te = item.getExpression();
                if (te instanceof AggregateExpression) {
                    AggregateExpression ag = (AggregateExpression)te;
                    if (ag.isMin() || ag.isMax()) {
                        Expression inner = ag.getInnerExpression();
                        if (inner instanceof NameExpression) {
                            NameExpression nam = (NameExpression)inner;
                            Column col = ic.getConstraint().getColumn(0);
                            if (nam.getName().equals(col.getName())) {
                                // This is the lucky special case.  MAX or MIN
                                // on an indexed column.
                                if (c.absolute(ag.isMax() ? -1 : 1)) {
                                    Row r = c.getRow();
                                    ret = staticCursor(session, c, items,
                                                       r.item(1));
                                    c.close();
                                }
                            }
                        }
                    } else if (ag.isCount() && ag.all && c.size() > 0) {
                        // another easy case is count(*)
                        ret = staticCursor(session, c, items,
                                           new ValueLong(c.size()));
                        c.close();
                    }
                }
            }
        }
        return ret;
    }

    /**
     * Return the expression as a scalar value.  We try.  If there's only
     * a single column in the result, we just return the column's value for
     * the first row of the result.   Otherwise, return ValueNull.
     */
    public Value getValue(Session session, Cursor cur) throws SQLException {
        Value ret = ValueNull.valueNull;
        Cursor cursor = getCursor(session, cur);
        try {
            if (cursor.next()) {
                Row row = cursor.getRow();
                if (row.size() == 1) {
                    ret = row.item(1);    
                }
                if (cursor.next()) {
                    throw new SQLException("Cardinality violation", "21000");
                }
            }
            return ret;
        } finally {
            cursor.close();
        }
    }

    /**
     * Get the base tables that participate in this select expression
     */
    public void getBaseTables(Vector v) {
        for (int i = 0; i < from.size(); i++) {
            ((TableExpression)from.elementAt(i)).getBaseTables(v);
        }
    }

    /**
     * Expression implementation...
     */
    public void visitSubExpressions(ExpressionVisitor ev) {
        if (where != null) ev.visit(where);
    }

    /**
     * Visitor class to set the WHERE clause on all subtables in this SELECT
     */
    class AndWhere implements ExpressionVisitor {
        Expression where;
        AndWhere(Expression where) { this.where = where; }
        public void visit(Expression sub) {
            if (sub instanceof TableExpression) {
                TableExpression te = (TableExpression)sub;
                if (!te.anded) {
                    Expression oldW = te.getWhere();
                    if (oldW != null) {
                        where = new BinaryExpression(Op.AND, where, oldW);
                    }
                    te.setWhere(where);
                    te.anded = true;
                }
                sub.visitSubExpressions(this);
            }
        }
    }

    /**
     * Nope, I'm not a boolean
     *
     * @exception RuntimeException is thrown
     */
    public void invert() {
        throw new RuntimeException(
            "invert not implemented for SelectExpression");
    }

    /**
     * Read me from a stream
     */
    public void readExternal(ObjectInput in)
        throws IOException, ClassNotFoundException
    {
        this.distinct = (in.read() == 1);
        this.items = (Vector)in.readObject();
        this.from = (Vector)in.readObject();
        this.where = (Expression)in.readObject();
        this.groupBy = (Vector)in.readObject();
        this.having = (Expression)in.readObject();
    }

    /**
     * Write me to a stream
     */
    public void writeExternal(ObjectOutput out) throws IOException {
        out.write(distinct ? 1 : 0);
        out.writeObject(items);
        out.writeObject(from);
        out.writeObject(where);
        out.writeObject(groupBy);
        out.writeObject(having);
    }

    /**
     * Return a string representation for debugging purposes
     */
    public String toString() {
        StringBuffer sb = new StringBuffer("SELECT ");
        if (items == null) {
            sb.append("*");
        } else {
            for (int i = 0; i < items.size(); i++) {
                if (i > 0) sb.append(',');
                sb.append(items.elementAt(i).toString());
            }
        }
        if (from != null) {
            sb.append(" FROM ");
            for (int i = 0; i < from.size(); i++) {
                if (i > 0) sb.append(',');
                sb.append(from.elementAt(i).toString());
            }
        }
        if (where != null) {
            sb.append(" WHERE ");
            sb.append(where.toString());
        }
        if (groupBy != null) {
            sb.append(" GROUP BY ");
            for (int i = 0; i < groupBy.size(); i++) {
                if (i > 0) sb.append(',');
                sb.append(groupBy.elementAt(i).toString());
            }
        }
        if (having != null) {
            sb.append(" HAVING ");
            sb.append(having.toString());
        }
        return sb.toString();
    }

    //#ifdef DEBUG
    /**
     * Display a cursor (under trace control)
     */
    public static final void showCursor(Cursor c) {
        try {
            if (Trace.bit(2)) {
                Debug.println(c.toString());
            }
        } catch (Exception e) {
            Debug.print(e);
        }
    }

    /**
     * Display c cursor (or not)
     */
    public static void showCursor(Cursor c, boolean really) {
        try {
            if (really) {
                Debug.println("\n" + c);
            }
        } catch (Throwable e) {
            Debug.print(e);
        }
    }

    public String name() {
        return toString();
    }
    //#endif


}