Quadcap Embeddable Database

com/quadcap/sql/JoinedTable.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.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Vector;

import java.sql.SQLException;

import antlr.RecognitionException;

import com.quadcap.sql.types.Op;

import com.quadcap.util.Debug;

/**
 * A table expression representing a single join operation.
 *
 * @author Stan Bailes
 */
public class JoinedTable extends TableExpression implements Externalizable {
    int                 op                      = -1;
    TableExpression     a                       = null;
    TableExpression     b                       = null;
    Tuple               tuple                   = null;
    Expression          onExpression            = null;
    /** Vector<String> **/
    Vector              usingList               = null;

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

    /**
     * Either a cross join or a natural join over any common columns.
     */
    public JoinedTable(int op, TableExpression a, TableExpression b) {
        this.op = op;
        this.a = a;
        this.b = b;
    }

    /**
     * Join 'ON' on
     */
    public void setOnExpression(Expression on) {
        this.onExpression = on;
    }

    /**
     * Join 'USING' column list
     */
    public void setUsingList(Vector usingList) {
        this.usingList = usingList;
    }

    
    /**
     * Verify the correctness of the join expression -- the grammar can't 
     * catch all of the possible errors.
     */
    /*{joinedTable.xml-100}
     * <section name="Semantic Constraints">
     *
     * <p>The syntax as specified here will accept certain join expressions 
     * that are illegal;  as a result there are additional semantic checks
     * performed on all join expressions:</p>
     *
     * <ul>
     * <li>At most one of the {<code>NATURAL, UNION, ON, USING</code>} may be
     *     specified in a join expression.</li>
     * <li>If neither <code>NATURAL</code> or <code>UNION</code> is specified,
     *     then
     *     either <code>ON</code> or <code>USING</code> must be specified.</li>
     * </ul>
     * </section>
     */
    public void checkSyntax() throws RecognitionException {
        if ((op & Op.NATURAL) != 0) {
            if (usingList != null) {
                throw new RecognitionException("Can't specify both NATURAL and " +
                                          "USING");
            }
            if (onExpression != null) {
                throw new RecognitionException("Can't specify both NATURAL and ON");
            }
        } else if (op == Op.LEFT || op == Op.RIGHT || 
                   op == Op.FULL || op == Op.INNER) {
            if (usingList == null && onExpression == null) {
                throw new RecognitionException(Op.toString(op) + 
                                          " join requires ON or USING " +
                                          "clause");
            }
        } else if (op == Op.UNION) {
            if (usingList != null) {
                throw new RecognitionException("Can't specify both UNION and USING");
            }
            if (onExpression != null) {
                throw new RecognitionException("Can't specify both UNION and ON");
            }
        }
    }

    /**
     * Override base method to propagate to base tables.
     */
    public void setWhere(Expression where) {
        this.where = where;
        a.setWhere(where);
        b.setWhere(where);
    }

    public int rank() { return 2; }

    public boolean isUpdatable() { return false; }

    public void getBaseTables(Vector v) {
        a.getBaseTables(v);
        b.getBaseTables(v);
    }

    public void visitSubExpressions(ExpressionVisitor ev) {
        if (a != null) ev.visit(a);
        if (b != null) ev.visit(b);
    }

    String toString(Iterator iter) {
        StringBuffer sb = new StringBuffer();
        while (iter.hasNext()) {
            if (sb.length() > 0) sb.append(", ");
            sb.append(iter.next().toString());
        }
        return sb.toString();
    }

    static String isa(Object x) {
        return x == null ? "null" :
            x.getClass().getName() + ":" + x;
    }

    public Cursor getCursor(Session session, Cursor outer)
        throws SQLException
    {
        int nop = op & ~Op.NATURAL;
        int[] map = null;

        Cursor ra = a.getCursor(session, outer);
        Cursor rb = b.getCursor(session, outer);

        int size = ra.getColumnCount() + rb.getColumnCount();

        if ((op & Op.NATURAL) != 0) {
            getNaturalJoinColumns(ra, rb);
        }
             
        int usize = usingList == null ? 0 : usingList.size();
        map = new int[size - usize];       
        Tuple jtl = mapColumns(ra, rb, map, true);
        JoinMapRow jrl = new JoinMapRow(map);

        map = new int[size - usize];
        Tuple jtr = mapColumns(ra, rb, map, false);
        JoinMapRow jrr = new JoinMapRow(map);


        Cursor ret = null;
        Cursor left = null;
        Cursor right = null;
        if (onExpression != null) {
            where = new BinaryExpression(Op.AND, where, onExpression);
        }

        switch (nop) {
        case Op.CROSS:
        case Op.INNER:
            ret = getCrossCursor(session, outer,
                                 ra, rb, where, jtl, jrl,
                                 false /* left */,
                                 true /* inner */);
            break;
        case Op.LEFT:
            ret = getCrossCursor(session, outer,
                                 ra, rb, where, jtl, jrl,
                                 true /* left */,
                                 true /* inner */);
            break;
        case Op.RIGHT:
            ret = getCrossCursor(session, outer,
                                 rb, ra, where, jtr, jrr,
                                 true /* left */,
                                 true /* inner */);
            break;
        case Op.FULL:
            left = getCrossCursor(session, outer,
                                  ra, rb, where, jtl, jrl,
                                  true /* left */,
                                  true /* inner */);
            right = getCrossCursor(session, outer,
                                   rb, ra, where, jtr, jrr,
                                  true /* left */,
                                  false /* inner */);
            break;
        case Op.UNION:
            ret = new JoinUnionCursor(session, outer, ra, rb, where, jtl, jrl);
            break;
        default:
            throw new SQLException("Bad join type: " + nop);   
        }
        if (left != null && right != null) {
            MultiCursor mc = new MultiCursor(session, left);
            mc.appendCursor(session, right);
            ret = mc;
        }
        if (ret == null) {
            throw new SQLException("Bad join");
        }
        return ret;
    }

    Cursor getCrossCursor(Session session, Cursor outer, Cursor ca, Cursor cb,
                          Expression where, Tuple jt, JoinMapRow jrl,
                          boolean left, boolean inner)
        throws SQLException
    {
        int[][] cols =
            usingList != null ? getUsingColumns(ca, cb) :
            new Analyze(session, where).getJoinColumns(ca, cb);

        Cursor ret = null;
        if (cols == null) {
            //Debug.println("CROSS");
            ret = new JoinCrossCursor(session, outer, ca, cb, where, jt, jrl,
                                      left, inner);
        } else {
            //Debug.println("INNER");
            int[] aCols = cols[0];
            int[] bCols = cols[1];
            ret = new JoinInnerCursor(session, outer, ca, aCols, cb, bCols,
                                      where, jt, jrl, left, inner);
        }
        return ret;
    }

    int[][] getUsingColumns(Tuple a, Tuple b) throws SQLException {
        int[][] ret = null;
        if (usingList != null) {
            int len = usingList.size();
            ret = new int[2][len];
            for (int i = 0; i < len; i++) {
                String u = usingList.get(i).toString();
                Column ca = a.getColumn(u);
                Column cb = b.getColumn(u);
                ret[0][i] = ca.getColumn();
                ret[1][i] = cb.getColumn();
            }
        }
        return ret;
    }

    void getNaturalJoinColumns(Tuple ta, Tuple tb) throws SQLException {
        usingList = new Vector();
        HashMap t = new HashMap();
        for (int i = 1; i <= tb.getColumnCount(); i++) {
            Column cb = tb.getColumn(i);
            t.put(cb.getShortName(), cb);
        }
        for (int i = 1; i <= ta.getColumnCount(); i++) {
            Column ca = ta.getColumn(i);
            if (t.containsKey(ca.getShortName())) {
                usingList.addElement(ca.getShortName());
            }
        }
    }

    /**
     * Build the tuple for this join operation
     */
    private final Tuple mapColumns(Tuple ra, Tuple rb, int[] map, boolean left)
        throws SQLException
    {
        HashMap uMap = null;
        TupleImpl ti = new TupleImpl();
        int usize = usingList == null ? 0 : usingList.size();

        // First, add the common columns, where we drop the table names.
        if (usize > 0) {
            Tuple outer = left ? ra : rb;
            uMap = new HashMap();
            int[] umap = outer.mapColumns(usingList);
            for (int i = 0; i < umap.length; i++) {
                int u = umap[i];
                Column ci = outer.getColumn(u);
                uMap.put(ci.getShortName(), "");
                Column col = new Column(ci.getShortName(), ci);
                col.setJoinColumn(true);
                ti.addColumn(col);
                map[i] = 0-u;
            }
        }

        // Then the remaining columns from 'A'
        int base = usize;
        for (int i = 1; i <= ra.getColumnCount(); i++) {
            Column ci = ra.getColumn(i);
            if (uMap == null || !uMap.containsKey(ci.getShortName())) {
                int c = ci.getColumn();
                if (map[base] == 0) {
                    map[base++] = left ? 0 - c : c;
                    ti.addColumn(ci.getName(), ci.getType());
                }
            }
        }

        // And the remaining columns from 'B'
        for (int i = 1; i <= rb.getColumnCount(); i++) {
            Column ci = rb.getColumn(i);
            if (uMap == null || !uMap.containsKey(ci.getShortName())) {
                int c = ci.getColumn();
                if (map[base] == 0) {
                    map[base++] = left ? c : 0 - c;
                    ti.addColumn(ci.getName(), ci.getType());
                }
            }
        }
        return ti;
    }

    public void readExternal(ObjectInput in)
        throws IOException, ClassNotFoundException
    {
        this.op = in.readInt();
        this.a = (TableExpression)in.readObject();
        this.b = (TableExpression)in.readObject();
        this.onExpression = (Expression)in.readObject();
        this.usingList = (Vector)in.readObject();
    }
    
    public void writeExternal(ObjectOutput out) throws IOException {
        out.writeInt(op);
        out.writeObject(a);
        out.writeObject(b);
        out.writeObject(onExpression);
        out.writeObject(usingList);
    }

    public String toString() {
        StringBuffer sb = new StringBuffer(a.toString());
        
        if ((op & Op.NATURAL) != 0) sb.append(" NATURAL");
        op &= ~Op.NATURAL;
        sb.append(' ');
        sb.append(Op.toString(op));
        sb.append(" JOIN ");
        sb.append(b.toString());
        return sb.toString();
    }

    //#ifdef DEBUG
    public String name() {
        StringBuffer sb = new StringBuffer('(');
        sb.append(a.name());
        sb.append("\n  ");
        sb.append(Op.toString(op));
        sb.append("\n");
        sb.append(b.name());
        sb.append(')');
        return sb.toString();
    }
    //#endif
}