Package org.apache.drill.exec.physical.impl.TopN

Class PriorityQueueTemplate

java.lang.Object
org.apache.drill.exec.physical.impl.TopN.PriorityQueueTemplate
All Implemented Interfaces:
PriorityQueue
public abstract class PriorityQueueTemplate extends Object implements PriorityQueue

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    EST_MAX_QUEUE_SIZE
    The estimated maximum queue size used with allocating the SV4 for the queue.

    Fields inherited from interface org.apache.drill.exec.physical.impl.TopN.PriorityQueue

    TEMPLATE_DEFINITION

  • Constructor Summary

    Constructors
    Constructor
    Description
    PriorityQueueTemplate()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    add(RecordBatchData batch)
    The elements in the given batch are added to the priority queue.
    void
    cleanup()
    Releases all the memory consumed by the priority queue.
    int
    compare(int leftIndex, int rightIndex)
     
    abstract int
    doEval(int leftIndex, int rightIndex)
    Evaluates the value of record at leftIndex and rightIndex w.r.t min heap condition.
    abstract void
    doSetup(VectorContainer incoming, RecordBatch outgoing)
    Stores the reference to the hyperBatch container which holds all the records across incoming batches in it.
    void
    generate()
    This method must be called before fetching the final priority queue hyper batch and final Sv4 vector.
    SelectionVector4
    getFinalSv4()
    Retrieves the selection vector used to select the elements in the priority queue from the hyper batch provided by the PriorityQueue.getHyperBatch() method.
    VectorContainer
    getHyperBatch()
    Retrieves the final priority queue HyperBatch containing the results.
    SelectionVector4
    getSv4()
     
    void
    init(int limit, BufferAllocator allocator, boolean hasSv2)
    Initializes the priority queue.
    boolean
    isInitialized()
    When cleanup is called then heapSv4 is cleared and set to null and is only initialized during init call.
    int
    pop()
    Pop the root element which holds the minimum value in heap.
    void
    resetQueue(VectorContainer container, SelectionVector4 v4)
    Cleanup the old state of queue and recreate a new one with HyperContainer containing vectors in input container and the corresponding indexes (in SV4 format) from input SelectionVector4
    void
    swap(int sv0, int sv1)
     

    Methods inherited from class java.lang.Object

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

  • Field Details

    • EST_MAX_QUEUE_SIZE

      public static final int EST_MAX_QUEUE_SIZE
      The estimated maximum queue size used with allocating the SV4 for the queue. If the queue is larger, then a) we should probably be using a sort instead of top N, and b) the code will automatically grow the SV4 as needed up to the max supported size.
      See Also:

  • Constructor Details

    • PriorityQueueTemplate

      public PriorityQueueTemplate()

  • Method Details

    • init

      public void init(int limit, BufferAllocator allocator, boolean hasSv2) throws SchemaChangeException
      Description copied from interface: PriorityQueue
      Initializes the priority queue. This method must be called before any other methods on the priority queue are called.
      Specified by:
      init in interface PriorityQueue
      Parameters:
      limit - The size of the priority queue.
      allocator - The BufferAllocator to use when creating the priority queue.
      hasSv2 - True when incoming batches have 2 byte selection vectors. False otherwise.
      Throws:
      SchemaChangeException

    • resetQueue

      public void resetQueue(VectorContainer container, SelectionVector4 v4) throws SchemaChangeException
      Description copied from interface: PriorityQueue
      Cleanup the old state of queue and recreate a new one with HyperContainer containing vectors in input container and the corresponding indexes (in SV4 format) from input SelectionVector4
      Specified by:
      resetQueue in interface PriorityQueue
      Throws:
      SchemaChangeException

    • add

      public void add(RecordBatchData batch) throws SchemaChangeException
      Description copied from interface: PriorityQueue
      The elements in the given batch are added to the priority queue. Note that the priority queue only retains the top elements that fit within the size specified by the PriorityQueue.init(int, BufferAllocator, boolean) method.
      Specified by:
      add in interface PriorityQueue
      Parameters:
      batch - The batch containing elements we want to add.
      Throws:
      SchemaChangeException

    • generate

      public void generate()
      Description copied from interface: PriorityQueue
      This method must be called before fetching the final priority queue hyper batch and final Sv4 vector.
      Specified by:
      generate in interface PriorityQueue

    • getHyperBatch

      public VectorContainer getHyperBatch()
      Description copied from interface: PriorityQueue
      Retrieves the final priority queue HyperBatch containing the results. Note: this should be called after PriorityQueue.generate().
      Specified by:
      getHyperBatch in interface PriorityQueue
      Returns:
      The final priority queue HyperBatch containing the results.

    • getSv4

      public SelectionVector4 getSv4()
      Specified by:
      getSv4 in interface PriorityQueue

    • getFinalSv4

      public SelectionVector4 getFinalSv4()
      Description copied from interface: PriorityQueue
      Retrieves the selection vector used to select the elements in the priority queue from the hyper batch provided by the PriorityQueue.getHyperBatch() method. Note: this should be called after PriorityQueue.generate().
      Specified by:
      getFinalSv4 in interface PriorityQueue
      Returns:
      The selection vector used to select the elements in the priority queue.

    • cleanup

      public void cleanup()
      Description copied from interface: PriorityQueue
      Releases all the memory consumed by the priority queue.
      Specified by:
      cleanup in interface PriorityQueue

    • isInitialized

      public boolean isInitialized()
      When cleanup is called then heapSv4 is cleared and set to null and is only initialized during init call. Hence this is used to determine if priority queue is initialized or not.
      Specified by:
      isInitialized in interface PriorityQueue
      Returns:
      - true - queue is still initialized false - queue is not yet initialized and before using queue init should be called

    • pop

      public int pop()
      Pop the root element which holds the minimum value in heap. In this case root element will be the index of record with minimum value. After extracting the root element it swaps the root element with last element in heapSv4 and does heapify (by calling siftDown) again.
      Returns:
      - Index for

    • swap

      public void swap(int sv0, int sv1)

    • compare

      public int compare(int leftIndex, int rightIndex) throws SchemaChangeException
      Throws:
      SchemaChangeException

    • doSetup

      public abstract void doSetup(@Named("incoming") VectorContainer incoming, @Named("outgoing") RecordBatch outgoing) throws SchemaChangeException
      Stores the reference to the hyperBatch container which holds all the records across incoming batches in it. This is used in doEval function to compare records in this hyper batch at given indexes.
      Parameters:
      incoming - - reference to hyperBatch
      outgoing - - null
      Throws:
      SchemaChangeException

    • doEval

      public abstract int doEval(@Named("leftIndex") int leftIndex, @Named("rightIndex") int rightIndex) throws SchemaChangeException
      Evaluates the value of record at leftIndex and rightIndex w.r.t min heap condition. It is used in compare(int, int) method while Heapifying the queue.
      Parameters:
      leftIndex -
      rightIndex -
      Returns:
      Throws:
      SchemaChangeException