Quadcap Embeddable Database

com/quadcap/sql/JoinInnerCursor.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.ByteArrayOutputStream;
import java.io.Externalizable;
import java.io.IOException;
import java.io.ObjectInput;
import java.io.ObjectOutput;

import java.util.BitSet;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

import java.sql.SQLException;

import com.quadcap.sql.file.BlockFile;
import com.quadcap.sql.file.ByteUtil;
import com.quadcap.sql.file.PageManager;
import com.quadcap.sql.file.RandomAccess;

import com.quadcap.sql.io.ObjectOutputStream;

import com.quadcap.sql.index.BCursor;
import com.quadcap.sql.index.Btree;
import com.quadcap.sql.index.Comparator;

import com.quadcap.sql.types.Value;
import com.quadcap.sql.types.ValueBoolean;
import com.quadcap.sql.types.ValueInteger;
import com.quadcap.sql.types.Type;

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

/**
 * Cursor implementing <b>INNER JOIN</b> using nested loops (optimized using
 * the inner index)
 *
 * @author Stan Bailes
 */
public class JoinInnerCursor extends JoinCursor {
    Database                            db;
    BlockFile                           file;
    BlockFile                           tempFile;

    /** The join columns in the outer table. */
    int[]                               caCols;

    /** The current join key. */
    byte[]                              caKey;

    /** Cache number of columns in inner table. */
    int                                 cbCnt;

    /** The join columns in the inner table. */
    int[]                               cbCols;

    /** Map inner, non-join-key columns from join cursor to inner cursor pos */
    int[]                               cbMap;

    /** Map outer columns from join cursor to outer cursor pos */
    int[]                               caMap;

    /** If the inner is really a table, or null if it's a view. */      
    Table                               cbTable;

    /** If there's an index on the join columns of the inner table */
    IndexConstraint                     cbIndex;

    /** Either the index from above, or a temporary one we create. */
    Btree                               index;

    /** Did we make 'index', or were the columns already indexed? */
    boolean                             tempIndex;

    /** Did we make create new (temporary) rows for the inner index? */
    boolean                             mustFreeRows = false;

    BCursor                             cbKeys;

    /** Used to compare the inner and outer join keys. */
    Comparator                          compare;

    /** Temporary used to build keys for inner table index */
    MapRow                              mapRow;

    /**
     * Constructor takes a whole shitload of parameters.
     *
     * @param session my execution session context (transaction, etc)
     * @param ca the outer join cursor
     * @param caCols the join columns in the outer cursor
     * @param cb the inner join cursor
     * @param cbCols the join columns in the inner cursor
     * @param where the ON/WHERE predicate expression
     * @param tuple the format we're supposed to return
     * @param row A mapping between the inner/outer rows and the join row
     * @param left Include non-matching outer rows with nulls for inner
     * @param inner Include matching rows
     * @param flip Left is Right, Right is Left
     */
    public JoinInnerCursor(Session session, Cursor outer, Cursor ca, int[] caCols,
                           Cursor cb, int[] cbCols, 
                           Expression where, Tuple tuple, JoinMapRow row,
                           boolean left, boolean inner)
        throws SQLException
    {
        super(session, outer, ca, cb, where, tuple, row, left, inner);
        this.db = session.getDatabase();
        this.file = db.getFile();
        try {
            this.tempFile = db.getTempFile();
        } catch (IOException e) {
            throw DbException.wrapThrowable(e);
        }
        this.caCols = caCols;
        this.cbCnt = cb.getColumnCount();
        this.cbCols = cbCols;
        this.cbIndex = findIndex(cb, cbCols);
        this.compare = new Key(cbCols.length);
        
        int joinCnt = cbCols.length;

    }
        
    final IndexConstraint findIndex(Cursor r, int[] cols) 
        throws SQLException 
    {
        IndexConstraint ret = null;
        BitSet b = null;
        this.cbTable = r.getTable();
        if (this.cbTable == null) {
            return null;
        }
        final int num = cbTable.getNumConstraints();
        for (int ci = 0; ci < num; ci++) {
            Constraint c = cbTable.getConstraint(ci);
            if (!(c instanceof IndexConstraint)) continue;
            int[] ccols = c.getColumns();
            if (cols.length != ccols.length) continue;
            if (b == null) b = intArrayToBitSet(cols);
            boolean match = true;
            for (int i = 0; i < ccols.length; i++) {
                if (!b.get(ccols[i])) {
                    match = false;
                    break;
                }
            }
            if (match) ret = (IndexConstraint)c;
        }
        return ret;
    }

    final static BitSet intArrayToBitSet(int[] a) {
        BitSet b = new BitSet();
        for (int i = 0; i < a.length; i++) {
            b.set(a[i]);
        }
        return b;
    }
    
    final byte[] makeInnerKey(Cursor cursor, Row row, long rowId)
        throws IOException, SQLException
    {
        return Key.makeKey(cursor, row, cbCols, rowId, true);
    }

    final byte[] makeOuterKey(Cursor cursor, Row row)
        throws IOException, SQLException
    {
        if (cbIndex != null) {
            mapRow.setRow(row);
            return cbIndex.makeKey(session, mapRow, Long.MIN_VALUE);
        }
        return Key.makeKey(cursor, row, caCols, Long.MIN_VALUE,
                           true);
    }


    protected void bfirst() throws SQLException {
        try {
            row.setB(null);
            if (index == null) {
                this.index = makeInnerIndex();
                this.rb = new LazyRow(cbCnt);
            }
            caKey = makeOuterKey(ca, ra);
            if (cbKeys == null) cbKeys = index.getCursor(false);
            cbKeys.seek(caKey);
        } catch (IOException e) {
            throw DbException.wrapThrowable(e);
        }
    }

    final protected boolean bnext() throws SQLException {
        try {
            boolean ret = false;
        
            while (!ret && cbKeys.next()) {
                byte[] cbKey = cbKeys.getKeyBuf();
                int len = cbKeys.getKeyLen();
                if (compare.compare(caKey, 0, caKey.length,
                                    cbKey, 0, len) != 0) {
                    break;
                }
                long rowId = cbKeys.getValAsLong();
                boolean isTemp = cbTable == null;
                db.getRow(rowId, (LazyRow)rb, isTemp);
                row.setB(rb);
                //Debug.println("bnext: rb = " + rb + ", row = " + row);
                ret = true;
            }
            if (!ret) row.setB(null);
            return ret;
        } catch (IOException ex) {
            throw DbException.wrapThrowable(ex);
        }
    }

    final void makeTemporaryIndexForTable() throws IOException, SQLException {
        //#ifdef DEBUG
        if (Trace.bit(17)) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < cbCols.length; i++) {
                if (i > 0) sb.append(", ");
                sb.append(cb.getColumn(cbCols[i]).getName());
            }
            Debug.println("Make Temporary Index for " + cb.getName() +
                          " (" + sb + ")");
        }
        //#endif
        Comparator tempCompare = new Key(cbCols.length + 1);
        index = session.makeTempTree(tempCompare);
        while (cb.next()) {
            long rowId = cb.getRowId();
            Row r = cb.getRow();
            byte[] key = makeInnerKey(cb, r, rowId);
            index.set(key, session.getBuf8(rowId));
        }
    }

    final void makeTemporaryIndexForView() throws IOException, SQLException {
        Comparator tempCompare = new Key(cbCols.length + 1);
        index = session.makeTempTree(tempCompare);
        int cnt = 0;
        mustFreeRows = true;
        while (cb.next()) {
            Row r = cb.getRow();
            byte[] key = makeInnerKey(cb, r, cnt++);
            long rowId = session.getDatabase().putRow(session, tempFile, cb, r);
            index.set(key, session.getBuf8(rowId));
        }
    }

    final Btree makeInnerIndex() throws IOException, SQLException {
        if (cbTable != null) {
            if (cbIndex != null) {
                int[] map = new int[cb.getColumnCount() + 1];
                for (int i = 0; i < cbCols.length; i++) {
                    int ic = cbCols[i];
                    int oc = caCols[i];
                    map[ic] = oc;
                }
                mapRow = new MapRow(map, 1);
                index = cbIndex.getIndex(db);
            } else {
                makeTemporaryIndexForTable();
                tempIndex = true;
            }
        } else {
            makeTemporaryIndexForView();
            tempIndex = true;
        }
        return index;
    }

    public void freeRows(Btree index, BlockFile file)
        throws IOException 
    {
        BCursor c = index.getCursor();
        try {
            while (c.next()) {
                long rowId = c.getValAsLong();
                db.removeRow(file, rowId);
            }
        } finally {
            c.release();
        }
    }

    public void close() throws SQLException {
        try {
            super.close();
        } finally {
            try {
                if (cbKeys != null) cbKeys.release();
            } finally {
                try {
                    cbKeys = null;
                    if (tempIndex && mustFreeRows) {
                        freeRows(index, tempFile);
                    }
                } catch (IOException e2) {
                    throw DbException.wrapThrowable(e2);
                } finally {
                    try {
                        mustFreeRows = false;
                        if (tempIndex) {
                            index.free();
                            session.getDatabase().releaseTempFile();
                        }
                    } catch (IOException e3) {
                        throw DbException.wrapThrowable(e3);
                    } finally {
                        index = null;
                        if (tempFile != null) {
                            session.getDatabase().releaseTempFile();
                            tempFile = null;
                        }
                        tempIndex = false;
                    }
                }
            }
        }
    }
}