I am trying to simulate SQL joins using java and very large text files (INNER, RIGHT OUTER and LEFT OUTER). The files have already been sorted using an external sort routine.

The issue I have is I am trying to find the most efficient way to deal with the INNER join part of the algorithm. Right now I am using two Lists to store the lines that have the same key and iterate through the set of lines in the right file once for every line in the left file (provided the keys still match). In other words, the join key is not unique in each file so would need to account for the Cartesian product situations ...
        
    left_01, 1
    left_02, 1
    right_01, 1
    right_02, 1
    right_03, 1
    
    left_01 joins to right_01 using key 1
    left_01 joins to right_02 using key 1
    left_01 joins to right_03 using key 1
    left_02 joins to right_01 using key 1
    left_02 joins to right_02 using key 1
    left_02 joins to right_03 using key 1
 
My concern is one of memory. I will run out of memory if i use the approach below but still want the inner join part to work fairly quickly. What is the best approach to deal with the INNER join part keeping in mind that these files may potentially be huge

        
    public class Joiner {
        
      private void join(BufferedReader left, BufferedReader right, BufferedWriter output) throws Throwable {
    
        BufferedReader _left = left;
        BufferedReader _right = right;
        BufferedWriter _output = output;
        Record _leftRecord;
        Record _rightRecord;
      
        _leftRecord = read(_left);
        _rightRecord = read(_right);
        
        while( _leftRecord != null && _rightRecord != null ) {
                
          if( _leftRecord.getKey() < _rightRecord.getKey() ) {
            write(_output, _leftRecord, null);
            _leftRecord = read(_left);
          }
          else if( _leftRecord.getKey() > _rightRecord.getKey() ) {
            write(_output, null, _rightRecord);
            _rightRecord = read(_right);
          }
          else {
            List<Record> leftList = new ArrayList<Record>();
            List<Record> rightList = new ArrayList<Record>();
    
            _leftRecord = readRecords(leftList, _leftRecord, _left);
            _rightRecord = readRecords(rightList, _rightRecord, _right);
            
            for( Record equalKeyLeftRecord : leftList ){
              for( Record equalKeyRightRecord : rightList ){
                write(_output, equalKeyLeftRecord, equalKeyRightRecord);
              }
            }
          }
        }
        
        if( _leftRecord != null ) {
          write(_output, _leftRecord, null);
          _leftRecord = read(_left);
          while(_leftRecord != null) {
            write(_output, _leftRecord, null);
            _leftRecord = read(_left);        
          }
        }
        else {  
          if( _rightRecord != null ) {
            write(_output, null, _rightRecord);
            _rightRecord = read(_right);
            while(_rightRecord != null) {
              write(_output, null, _rightRecord);
              _rightRecord = read(_right);
            }
          }     
        }
        _left.close();
        _right.close();
        _output.flush();
        _output.close();
      }
    
      private Record read(BufferedReader reader) throws Throwable {
        Record record = null;
    
        String data = reader.readLine();
        if( data != null ) {
          record = new Record(data.split("\t"));
        }
        return record;
      }
      
      private Record readRecords(List<Record> list, Record record, BufferedReader reader) throws Throwable {
        int key = record.getKey();
        list.add(record);
        record = read(reader);
        while( record != null && record.getKey() == key) {
          list.add(record);
          record = read(reader);
        }
        return record;    
      }
    
      private void write(BufferedWriter writer, Record left, Record right) throws Throwable {   
        String leftKey = (left == null ? "null" : Integer.toString(left.getKey()));
        String leftData = (left == null ? "null" : left.getData());
        String rightKey = (right == null ? "null" : Integer.toString(right.getKey()));
        String rightData = (right == null ? "null" : right.getData());
        
        writer.write("[" + leftKey + "][" + leftData + "][" + rightKey + "][" + rightData + "]\n");
      }
    
      public static void main(String[] args) {
            try {
              
              BufferedReader leftReader = new BufferedReader(new FileReader("LEFT.DAT"));
              BufferedReader rightReader = new BufferedReader(new FileReader("RIGHT.DAT"));
              BufferedWriter output = new BufferedWriter(new FileWriter("OUTPUT.DAT"));
              
          Joiner joiner = new Joiner();
          joiner.join(leftReader, rightReader, output);
        } 
            catch (Throwable e) {
          e.printStackTrace();
        }
      }
    }
    

After applying the ideas from the proposed answer, I changed the loop to this

        
	private void join(RandomAccessFile left, RandomAccessFile right, BufferedWriter output) throws Throwable {
		
		long _pointer = 0;
		
		RandomAccessFile _left = left;
		RandomAccessFile _right = right;
		
		BufferedWriter _output = output;
		
		Record _leftRecord;
		Record _rightRecord;
			
		_leftRecord = read(_left);
		_rightRecord = read(_right);
		
		while( _leftRecord != null && _rightRecord != null ) {
						
			if( _leftRecord.getKey() < _rightRecord.getKey() ) {
				write(_output, _leftRecord, null);
				_leftRecord = read(_left);
			}
			else if( _leftRecord.getKey() > _rightRecord.getKey() ) {
				write(_output, null, _rightRecord);				
				_pointer = _right.getFilePointer();
				_rightRecord = read(_right);
			}
			else {			
				long _tempPointer = 0;
				int key = _leftRecord.getKey();															
				while( _leftRecord != null && _leftRecord.getKey() == key ) {
					_right.seek(_pointer);
					_rightRecord = read(_right);
					while( _rightRecord != null && _rightRecord.getKey() == key ) {
						write(_output, _leftRecord, _rightRecord );
						_tempPointer = _right.getFilePointer();
						_rightRecord = read(_right); 
					}
					_leftRecord = read(_left);
				}
				_pointer = _tempPointer;
			}
		}
		
		if( _leftRecord != null ) {
			write(_output, _leftRecord, null);
			_leftRecord = read(_left);
			while(_leftRecord != null) {
				write(_output, _leftRecord, null);
				_leftRecord = read(_left);				
			}
		}
		else {	
			if( _rightRecord != null ) {
				write(_output, null, _rightRecord);
				_rightRecord = read(_right);
				while(_rightRecord != null) {
					write(_output, null, _rightRecord);
					_rightRecord = read(_right);
				}
			}			
		}
		_left.close();
		_right.close();
		_output.flush();
		_output.close();
	}