org.apache.paimon.mergetree.compact

Class LoserTree<T>

java.lang.Object

org.apache.paimon.mergetree.compact.LoserTree<T>

All Implemented Interfaces:

Closeable, AutoCloseable

public class LoserTree<T>
extends Object
implements Closeable

A variant of the loser tree. In the LSM-Tree architecture, there will be duplicate Keys in multiple RecordReader, and these Keys need to be merged. In the loser tree, we return in the order of the Keys, but because the returned objects may be reused in the RecordReader or the MergeFunction, for a single RecordReader, we cannot get the next Key immediately after returning a Key, and we need to wait until the same Key in all RecordReader is returned before proceeding to the next Key.

The process of building the loser tree is the same as a regular loser tree. The difference is that in the process of adjusting the tree, we need to record the index of the same key and the state of the winner/loser for subsequent quick adjustment of the position of the winner.

Detailed design can refer to https://cwiki.apache.org/confluence/x/9Ak0Dw.

Constructor Summary

Constructors

Constructor and Description
LoserTree(List<RecordReader<T>> nextBatchReaders, Comparator<T> firstComparator, Comparator<T> secondComparator)

Method Summary

Modifier and Type	Method and Description
void	adjustForNextLoop() Adjust the Key that needs to be returned in the next round.
void	close()
void	initializeIfNeeded() Initialize the loser tree in the same way as the regular loser tree.
T	peekWinner() Peek the current winner, mainly for key comparisons.
T	popWinner() Pop the current winner and update its state to State#WINNER_POPPED.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LoserTree

public LoserTree(List<RecordReader<T>> nextBatchReaders,
                 Comparator<T> firstComparator,
                 Comparator<T> secondComparator)

Method Detail

initializeIfNeeded

public void initializeIfNeeded()
                        throws IOException

Initialize the loser tree in the same way as the regular loser tree.

Throws:

IOException

adjustForNextLoop

public void adjustForNextLoop()
                       throws IOException

Adjust the Key that needs to be returned in the next round.

Throws:

IOException

popWinner

public T popWinner()

Pop the current winner and update its state to State#WINNER_POPPED.

peekWinner

public T peekWinner()

Peek the current winner, mainly for key comparisons.

close

public void close()
           throws IOException

Specified by:

close in interface Closeable

Specified by:

close in interface AutoCloseable

Throws:

IOException