Quadcap Embeddable Database

com/quadcap/sql/InExpression.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.Enumeration;
import java.util.Vector;

import java.sql.SQLException;

import com.quadcap.sql.index.Btree;

import com.quadcap.sql.types.Op;
import com.quadcap.sql.types.Type;
import com.quadcap.sql.types.TypeBoolean;
import com.quadcap.sql.types.Value;
import com.quadcap.sql.types.ValueBoolean;

import com.quadcap.util.Debug;
import com.quadcap.util.Util;

/**
 * Expression implementing <b>IN </b><i>(list)</i>.
 *
 * @author Stan Bailes
 */
public class InExpression extends Expression implements Externalizable {
    Expression                          e       = null;
    Expression                          f       = null;
    boolean                             not     = false;

    /**
     * Private class to maintain per-session state for this expression
     */
    class InSessionState implements StatementContext {
        boolean                         correlatedSubquery = true;
        Session                         session;
        Btree                           index   = null;
        byte[]                          aByte = new byte[1];

        /**
         * Construct "IN" session state
         */
        public InSessionState(Session session) {
            this.session = session;
        }

        public boolean initialized() {
            return index != null;
        }

        /**
         * Initialize "IN" session state from RHS cursor.
         */
        void init(Expression f, Cursor cursor) throws SQLException {
            // Ok, there's probably a better way to do this, but the
            // idea is that if this is a correlated subquery, then
            // attempting to evaluate the query without reference to
            // the outer cursor will fail (by throwing an exception)
            Cursor d = f.getCursor(session, null);
            try {
                d.beforeFirst();
                d.next();
                Type eType = e.getType(session, cursor);
                Type fType = d.getColumn(1).getType();
                if (eType.toString().equals(fType.toString())) {
                    correlatedSubquery = false;
                } else {
                    // not really a correlated query, per se, but if the types
                    // don't match, our index-based optimization doesn't work.
                    // XXX (Though we could fix this by performing the appropriate
                    // XXX conversion when building the index...)
                    correlatedSubquery = true;
                } 
            } catch (Throwable t) {
                correlatedSubquery = true;
            } finally {
                d.close();
            }
            if (!correlatedSubquery) {
                Cursor c = f.getCursor(session, cursor);
                try {
                    this.index = session.makeTempTree();
                    c.beforeFirst();
                    if (c.getColumnCount() != 1) {
                        throw new SQLException("'IN' comparator: Rank mismatch",
                                               "42000");
                    }
                    while (c.next()) {
                        Row fcrow = c.getRow();
                        Value fval = fcrow.item(1);
                        if (!Value.isNull(fval)) {
                            byte[] key = Value.bytes(fval);
                            index.set(key, key.length, aByte, 0, 1);
                        }
                    }
                } catch (IOException ex) {
                    throw DbException.wrapThrowable(ex);
                } finally {
                    c.close();
                }
            }
        }

        /**
         * Initialize "IN" session state from RHS row.
         */
        void init(Row r) throws SQLException {
            try {
                this.index = session.makeTempTree();
                for (int i = 1; i <= r.size(); i++) {
                    Value fval = r.item(i);
                    byte[] key = Value.bytes(fval);
                    index.set(key, key.length, aByte, 0, 1);
                }
            } catch (IOException ex) {
                throw DbException.wrapThrowable(ex);
            }
        }

        /** Whenever you get around to finishing me is fine. */
        public int priority() { return 4; }

        /** Clean up any resources held by this context */
        public void finish(boolean abort) throws IOException {
            try {
                if (index != null) {
                    index.free();
                }
            } finally {
                if (index != null) session.getDatabase().releaseTempFile();
                index = null;
            }
        }

        /** Get ready for another day */
        public void reset() throws IOException {
            finish(false);
        }

        /** Does RHS set contain this value?  */
        public boolean contains(Value eval, Expression f, Cursor cursor) throws SQLException {
            if (!correlatedSubquery) {
                byte[] ekey = Value.bytes(eval);
                try {
                    return index.get(ekey, ekey.length, aByte) != -1;
                } catch (IOException ex) {
                    throw DbException.wrapThrowable(ex);
                }
            } else {
                return matchCorrelated(f, cursor, eval);
            }
        }

        /** Correlated sub-queries can't be short-circuited, alas. */            
        boolean matchCorrelated(Expression f, Cursor cursor, Value eval)
            throws SQLException
        {
            boolean match = false;
            Cursor c = f.getCursor(session, cursor);
            try {
                c.beforeFirst();
                if (c.getColumnCount() != 1) {
                    throw new SQLException("'IN' comparator: Rank mismatch",
                                           "42000");
                }
                while (!match && c.next()) {
                    Row fcrow = c.getRow();
                    Value fval = fcrow.item(1);
                    match = Value.boolOp(Op.EQ, eval, fval);
                }
            } finally {
                c.close();
            }
            return match;
        }
        
    }

    private InSessionState getSessionState(Session session) {
        InSessionState s = (InSessionState)session.getContext(this, false);
        if (s == null) {
            s = new InSessionState(session);
            session.putContext(this, false, s);
        }
        return s;
    }

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

    /**
     * Explicit constructor, called by SQL parser.
     */
    public InExpression(Expression e, Expression f) {
        this.e = e;
        this.f = f;
    }

    /** 
     * "IN" always returns a scalar value.
     */
    public int rank() { return 0; }

    /**
     * "IN" always returns a scalar value.
     */
    public Type getType(Session session, Cursor cursor) {
        return TypeBoolean.typeBoolean;
    }

    /**
     * Implementation of IN varies based on the rank of the LHS
     */
    public Value getValue(Session session, Cursor cursor) throws SQLException {
        switch (e.rank()) {
        case 0:
            return getValue1(session, cursor);
        case 1:
            return getValue2(session, cursor);
        default:
            throw new SQLException("bad rank (" + e.rank() +
                                   ") for left argument to IN", "42000");
        }
    }

    private Value getValue1(Session session, Cursor cursor)
        throws SQLException
    {
        Value eval = e.getValue(session, cursor);
        boolean match = false;
        switch (f.rank()) {
        case 0:
            throw new SQLException("'IN' comparator: Rank mismatch", "42000");
        case 1:
            Row frow = f.getValues(session, cursor);
            for (int i = 1; !match && i <= frow.size(); i++) {
                Value fval = frow.item(i);
                match = Value.boolOp(Op.EQ, eval, fval);
            }
            break;
        case 2:
            InSessionState s = getSessionState(session);
            if (!s.initialized()) {
                s.init(f, cursor);
            }
            match = s.contains(eval, f, cursor);
            break;
        default:
            throw new SQLException("internal error, bad rank: " + f.rank(),
                                   "Q0004");
        }
        match ^= not;
        return new ValueBoolean(match);
    }

    
    private Value getValue2(Session session, Cursor cursor)
        throws SQLException
    {
        Row erow = e.getValues(session, cursor);
        boolean match = false;
        switch (f.rank()) {
        case 0:
        case 1:
            throw new SQLException("'IN' comparator: Rank mismatch", "42000");
        case 2:
            Cursor c = f.getCursor(session, cursor);
            try {
                if (c.getColumnCount() != cursor.getColumnCount()) {
                    throw new SQLException("'IN' comparator: Rank mismatch",
                                           "42000");
                }
                while (!match && c.next()) {
                    Row frow = c.getRow();
                    match = matchRow(erow, frow);
                }
            } finally {
                c.close();
            }
            break;
        default:
            throw new SQLException("internal error, bad rank: " + f.rank(),
                                   "Q0005");
        }
        match ^= not;
        return new ValueBoolean(match);
    }

    static boolean matchRow(Row erow, Row frow) throws SQLException {
        boolean match = true;
        for (int i = 1; match && i <= erow.size(); i++) {
            match = Value.boolOp(Op.EQ, erow.item(i), frow.item(i));
        }
        return match;
    }
    
    public void invert() {
        not = !not;
    }

    public String toString() {
        String n = not ? "not " : "";
        return "(" + n + e + " IN " + f + ")";
    }

    public Expression getLhs() { return e; }
    
    public void visitSubExpressions(ExpressionVisitor ev) {
        ev.visit(e);
        ev.visit(f);
    }

    public void readExternal(ObjectInput in)
        throws IOException, ClassNotFoundException
    {
        e = (Expression)in.readObject();
        f = (Expression)in.readObject();
        not = (in.read() == 1);
    }
    
    public void writeExternal(ObjectOutput out) throws IOException {
        out.writeObject(e);
        out.writeObject(f);
        out.write(not ? 1 : 0);
    }
}