001/**
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018
019package org.apache.hadoop.mapred.join;
020
021import java.io.IOException;
022import java.util.ArrayList;
023import java.util.PriorityQueue;
024
025import org.apache.hadoop.classification.InterfaceAudience;
026import org.apache.hadoop.classification.InterfaceStability;
027import org.apache.hadoop.io.Writable;
028import org.apache.hadoop.io.WritableComparable;
029import org.apache.hadoop.io.WritableComparator;
030import org.apache.hadoop.mapred.JobConf;
031
032/**
033 * Prefer the "rightmost" data source for this key.
034 * For example, <tt>override(S1,S2,S3)</tt> will prefer values
035 * from S3 over S2, and values from S2 over S1 for all keys
036 * emitted from all sources.
037 */
038@InterfaceAudience.Public
039@InterfaceStability.Stable
040public class OverrideRecordReader<K extends WritableComparable,
041                                  V extends Writable>
042    extends MultiFilterRecordReader<K,V> {
043
044  OverrideRecordReader(int id, JobConf conf, int capacity,
045      Class<? extends WritableComparator> cmpcl) throws IOException {
046    super(id, conf, capacity, cmpcl);
047  }
048
049  /**
050   * Emit the value with the highest position in the tuple.
051   */
052  @SuppressWarnings("unchecked") // No static typeinfo on Tuples
053  protected V emit(TupleWritable dst) {
054    return (V) dst.iterator().next();
055  }
056
057  /**
058   * Instead of filling the JoinCollector with iterators from all
059   * data sources, fill only the rightmost for this key.
060   * This not only saves space by discarding the other sources, but
061   * it also emits the number of key-value pairs in the preferred
062   * RecordReader instead of repeating that stream n times, where
063   * n is the cardinality of the cross product of the discarded
064   * streams for the given key.
065   */
066  protected void fillJoinCollector(K iterkey) throws IOException {
067    final PriorityQueue<ComposableRecordReader<K,?>> q = getRecordReaderQueue();
068    if (!q.isEmpty()) {
069      int highpos = -1;
070      ArrayList<ComposableRecordReader<K,?>> list =
071        new ArrayList<ComposableRecordReader<K,?>>(kids.length);
072      q.peek().key(iterkey);
073      final WritableComparator cmp = getComparator();
074      while (0 == cmp.compare(q.peek().key(), iterkey)) {
075        ComposableRecordReader<K,?> t = q.poll();
076        if (-1 == highpos || list.get(highpos).id() < t.id()) {
077          highpos = list.size();
078        }
079        list.add(t);
080        if (q.isEmpty())
081          break;
082      }
083      ComposableRecordReader<K,?> t = list.remove(highpos);
084      t.accept(jc, iterkey);
085      for (ComposableRecordReader<K,?> rr : list) {
086        rr.skip(iterkey);
087      }
088      list.add(t);
089      for (ComposableRecordReader<K,?> rr : list) {
090        if (rr.hasNext()) {
091          q.add(rr);
092        }
093      }
094    }
095  }
096
097}