Package com.qfs.bitmap

Interface IBitmapIndex

All Superinterfaces:
IMemoryMonitored
All Known Subinterfaces:
IWritableBitmapIndex
All Known Implementing Classes:
ABitmapIndex, LeafBitmapMatcher, QFSBitmapIndex
public interface IBitmapIndex extends IMemoryMonitored
An object which is able to perform searches on tuplized data structures, and returns results using bitmaps.
Author:
ActiveViam

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    ANY
    The ANY value.
    static final double
    MATCH_FROM_ALLOWED_RATIO_THRESHOLD
    The maximum ratio between the number of members in a filter and the number of members in the level for which to compute the accepted members from the matching bitmaps in the index.

  • Method Summary

    Modifier and Type
    Method
    Description
    IBitmap
    and(IBitmap... bitmaps)
    Performs a logical AND between the bitmaps and return the result.
    void
    and(IMatchProcedure procedure, IBitmap[] filters)
    Performs a logical AND between multiple bitmaps at once.
    IBitmap
    createBitmap()
    Creates a new IBitmap object.
    IBitmap
    createBitmap(int initialBufferSize)
    Creates a new IBitmap object, with initial buffer size.
    IBitmap
    createOnesBitmap(int size)
    Creates a bitmap with all the bits set.
    long
    dataSizeInBytes()
    Gets an estimation of the size of index data only.
    IBitmap
    getBitmap(int level, int value)
    Retrieves the bitmap stored at that position of that level.
    List<? extends IBitmap>
    getBitmaps(int level, gnu.trove.list.array.TIntArrayList allowedValues)
    Returns all the bitmaps stored at the given positions for the given level.
    int
    getLevelCardinality(int level)
    Returns the cardinality (i.e the number of distinct values) of a given level.
    int
    getLevels()
    Gets the number of indexed levels.
    List<? extends IBitmap>
    getOtherBitmaps(int level, gnu.trove.list.array.TIntArrayList excludedValues)
    Returns all the bitmaps for the given level whose positions are not in the excludedValues list.
    IBitmap
    matchBitmap(int[] pattern)
    Matching algorithm: AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
    IBitmap
    matchBitmap(int[][] compositePattern)
    Matching algorithm: When the pattern defines several predicates for one level, OR the bitmaps of the predicates together, then AND the bitmaps of each level that is different from ANY.
    IBitmap
    matchBitmap(int[][] compositePattern, IBitmap filter)
    Matching algorithm: When the pattern defines several predicates for one level, apply the filter, OR the bitmaps of the predicates together, then AND the bitmaps of each level that is different from ANY.
    IBitmap
    matchBitmap(int[] pattern, boolean cloneResult)
    Matching algorithm: AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
    IBitmap
    matchBitmap(int[] pattern, IBitmap filter)
    Matching algorithm: apply the filter, and AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
    IBitmap
    matchBitmap(int[] pattern, IBitmap filter, boolean cloneResult)
    Matching algorithm: apply the filter, and AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
    default IBitmap
    matchFromExcludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap trueBitmap)
    Computes the IBitmap that will match the given values at the given level, using the complement of the given values.
    default IBitmap
    matchFromIncludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap falseBitmap)
    Computes the IBitmap that will match the given values at the given level, directly using the values.
    default IBitmap
    matchInCondition(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap trueBitmap, IBitmap falseBitmap)
    Computes the IBitmap that will match the given values at the given level.
    void
    matchProcedure(int[][] pattern, IMatchProcedure procedure, IBitmap... filters)
    Perform a search on the index and call a match procedure for each row at which there is a match.
    void
    matchProcedure(int[] pattern, IMatchProcedure procedure, IBitmap... filters)
    Perform a search on the index and call a match procedure for each row at which there is a match.
    IBitmap
    or(List<? extends IBitmap> bitmaps)
    Performs a logical OR between the bitmaps and return the result.
    default boolean
    shouldMatchFromExcludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values)
    Returns true if we should compute the list of accepted values from its complement, false if we should compute it from the list itself.
    int
    size()
    Gets the number of indexed tuples this object can match.
    long
    sizeInBytes()
    Gets an estimation of the total size of the index.

    Methods inherited from interface com.qfs.monitoring.memory.IMemoryMonitored

    getMemoryStatistic

  • Field Details

    • ANY

      static final int ANY
      The ANY value.
      See Also:

    • MATCH_FROM_ALLOWED_RATIO_THRESHOLD

      static final double MATCH_FROM_ALLOWED_RATIO_THRESHOLD
      The maximum ratio between the number of members in a filter and the number of members in the level for which to compute the accepted members from the matching bitmaps in the index. Above this ratio, computations are made using the bitmaps of the members of the level that are not in this filter.
      See Also:

  • Method Details

    • matchBitmap

      IBitmap matchBitmap(int[] pattern)
      Matching algorithm: AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).

      This is equivalent to calling matchBitmap(int[], boolean) with cloneResult set to true.

      Parameters:
      pattern - a pattern indicating which values are set for each level
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchBitmap

      IBitmap matchBitmap(int[] pattern, IBitmap filter)
      Matching algorithm: apply the filter, and AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).

      This is equivalent to calling matchBitmap(int[], IBitmap, boolean) with cloneResult set to true.

      Parameters:
      pattern - a pattern indicating which values are set for each level
      filter - the bitmap which filters the rows on which to perform the search
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchBitmap

      IBitmap matchBitmap(int[] pattern, boolean cloneResult)
      Matching algorithm: AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
      Parameters:
      pattern - a pattern indicating which values are set for each level
      cloneResult - if true the resulting bitmap will always be cloned, otherwise the returned bitmap might be an underlying bitmap stored in this index
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchBitmap

      IBitmap matchBitmap(int[] pattern, IBitmap filter, boolean cloneResult)
      Matching algorithm: apply the filter, and AND the bitmaps of each level value that is explicitly set in the pattern (different from ANY).
      Parameters:
      pattern - a pattern indicating which values are set for each level
      filter - the bitmap which filters the rows on which to perform the search
      cloneResult - if true the resulting bitmap will always be cloned, otherwise the returned bitmap might be an underlying bitmap stored in this index
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchBitmap

      IBitmap matchBitmap(int[][] compositePattern)
      Matching algorithm: When the pattern defines several predicates for one level, OR the bitmaps of the predicates together, then AND the bitmaps of each level that is different from ANY.
      Parameters:
      compositePattern - pattern to look for
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchBitmap

      IBitmap matchBitmap(int[][] compositePattern, IBitmap filter)
      Matching algorithm: When the pattern defines several predicates for one level, apply the filter, OR the bitmaps of the predicates together, then AND the bitmaps of each level that is different from ANY.
      Parameters:
      compositePattern - pattern to look for
      filter - the bitmap which filters the rows on which to perform the search
      Returns:
      the resulting bitmap (or null if there is no match)

    • matchProcedure

      void matchProcedure(int[] pattern, IMatchProcedure procedure, IBitmap... filters)
      Perform a search on the index and call a match procedure for each row at which there is a match.
      Parameters:
      pattern - the pattern to search for, ANY is a wildcard that tells the bitmap index to not put any constraint on this coordinate
      procedure - the procedure to apply when we find a matching point, a point matches when it respects all the constraint on the coordinates of the pattern, and when it is not filtered out by the filters
      filters - an optional extra array of filters that filter out points: basically to find the matching points we perform a big and on all the constraints provided by the pattern and on the filters

    • matchProcedure

      void matchProcedure(int[][] pattern, IMatchProcedure procedure, IBitmap... filters)
      Perform a search on the index and call a match procedure for each row at which there is a match.
      Parameters:
      pattern - the pattern to search for, ANY is a wildcard that tells the bitmap index to not put any constraint on this coordinate. It differs from the pattern from matchProcedure(int[], IMatchProcedure, IBitmap...) in that it allows to have multiple possibilities for each coordinate. An OR is performed on all the conditions provided for one coordinate
      procedure - the procedure to apply when we find a matching point, a point matches when it respects all the constraint on the coordinates of the pattern, and when it is not filtered out by the filters
      filters - an optional extra array of filters that filter out points: basically to find the matching points we perform a big and on all the constraints provided by the pattern and on the filters

    • shouldMatchFromExcludedValues

      default boolean shouldMatchFromExcludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values)
      Returns true if we should compute the list of accepted values from its complement, false if we should compute it from the list itself.
      Parameters:
      mappingCoord - the hierarchical mapping coordinate of the level at which we want the given values
      values - the values we want to include
      Returns:
      true if we should compute the list of accepted values from its complement, false if we should compute it from the list itself

    • matchInCondition

      default IBitmap matchInCondition(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap trueBitmap, IBitmap falseBitmap)
      Computes the IBitmap that will match the given values at the given level.
      Parameters:
      mappingCoord - the hierarchical mapping coordinate of the level
      values - the values that are permitted at the given level
      trueBitmap - the default value if nothing matches the given values
      falseBitmap - the default value if nothing matches the given values
      Returns:
      the IBitmap that will match any of the given values at the given level

    • matchFromIncludedValues

      default IBitmap matchFromIncludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap falseBitmap)
      Computes the IBitmap that will match the given values at the given level, directly using the values.
      Parameters:
      mappingCoord - the hierarchical mapping coordinate of the level
      values - the values that are permitted at the given level
      falseBitmap - the default value if nothing matches the given values
      Returns:
      the IBitmap that will match any of the given values at the given level

    • matchFromExcludedValues

      default IBitmap matchFromExcludedValues(int mappingCoord, gnu.trove.list.array.TIntArrayList values, IBitmap trueBitmap)
      Computes the IBitmap that will match the given values at the given level, using the complement of the given values.
      Parameters:
      mappingCoord - the hierarchical mapping coordinate of the level
      values - the values that are permitted at the given level
      trueBitmap - the default value if nothing matches the given values
      Returns:
      the IBitmap that will match any of the given values at the given level

    • size

      int size()
      Gets the number of indexed tuples this object can match.
      Returns:
      the number of tuples

    • getLevelCardinality

      int getLevelCardinality(int level)
      Returns the cardinality (i.e the number of distinct values) of a given level.
      Parameters:
      level - the index of the level whose cardinality will be returned
      Returns:
      the cardinality of the desired level

    • getBitmap

      IBitmap getBitmap(int level, int value)
      Retrieves the bitmap stored at that position of that level.
      Parameters:
      level - a level
      value - the position in the level
      Returns:
      the stored bitmap or null

    • getBitmaps

      List<? extends IBitmap> getBitmaps(int level, gnu.trove.list.array.TIntArrayList allowedValues)
      Returns all the bitmaps stored at the given positions for the given level. This method should be used when the size of allowedValues is relatively small.
      Parameters:
      level - the level
      allowedValues - the list of positions
      Returns:
      the bitmaps stored at these positions

    • getOtherBitmaps

      List<? extends IBitmap> getOtherBitmaps(int level, gnu.trove.list.array.TIntArrayList excludedValues)
      Returns all the bitmaps for the given level whose positions are not in the excludedValues list. This method should be used when the size of excludedValues is relatively large.
      Parameters:
      level - the level
      excludedValues - the list of excluded positions, it must be sorted in increasing order
      Returns:
      the bitmaps whose positions are not in the excluded list

    • and

      IBitmap and(IBitmap... bitmaps)
      Performs a logical AND between the bitmaps and return the result.
      Parameters:
      bitmaps - the bitmaps to AND
      Returns:
      the resulting bitmap

    • and

      void and(IMatchProcedure procedure, IBitmap[] filters)
      Performs a logical AND between multiple bitmaps at once.

      No resulting bitmap is built, instead a match procedure is called for each resulting bit.

      Parameters:
      filters - the bitmaps to AND together
      procedure - the match procedure interested in the result of the AND operation

    • or

      IBitmap or(List<? extends IBitmap> bitmaps)
      Performs a logical OR between the bitmaps and return the result.
      Parameters:
      bitmaps - the bitmaps to OR
      Returns:
      the resulting bitmap

    • createBitmap

      IBitmap createBitmap()
      Creates a new IBitmap object.
      Returns:
      the newly created IBitmap

    • createBitmap

      IBitmap createBitmap(int initialBufferSize)
      Creates a new IBitmap object, with initial buffer size.
      Parameters:
      initialBufferSize - initial size of the bitmap buffer
      Returns:
      the newly created IBitmap

    • createOnesBitmap

      IBitmap createOnesBitmap(int size)
      Creates a bitmap with all the bits set.
      Parameters:
      size - the size of the bitmap (in bits)
      Returns:
      the created bitmap

    • getLevels

      int getLevels()
      Gets the number of indexed levels.
      Returns:
      the number of indexed levels

    • sizeInBytes

      long sizeInBytes()
      Gets an estimation of the total size of the index.

      This includes data as well as abject internal attributes, class pointers, ...

      Returns:
      the size of this index measured in bytes

    • dataSizeInBytes

      long dataSizeInBytes()
      Gets an estimation of the size of index data only.
      Returns:
      size in bytes