Package com.qfs.bitmap

Interface IBitmapIndex

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int ANY
      The ANY value.
      static 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

      All Methods Instance Methods Abstract Methods Default Methods 
      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.

    • Field Detail

      • 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:
        Constant Field Values

    • Method Detail

      • 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