Package com.tangosol.util

Class SimpleMapIndex

  • All Implemented Interfaces:
    MapIndex
    Direct Known Subclasses:
    ConditionalIndex
    public class SimpleMapIndex
extends Base
implements MapIndex
    SimpleMapIndex is a MapIndex implementation used to correlate property values extracted from resource map entries with corresponding keys using what is commonly known as an Inverted Index algorithm.
    Since:
    Coherence 3.5
    Author:
    tb 2009.03.19

    • Field Detail

      • m_extractor

        protected ValueExtractor m_extractor
        ValueExtractor object that this MapIndex uses to extract an indexable property value from a [converted] value stored in the resource map.

      • m_comparator

        protected Comparator m_comparator
        Comparator used to sort the index. Used iff the Ordered flag is true. Null implies a natural order.

      • m_fOrdered

        protected boolean m_fOrdered
        Specifies whether or not this MapIndex orders the contents of the indexed information.

      • m_mapForward

        protected Map m_mapForward
        Map that contains the index values (forward index). The keys of the Map are the keys to the map being indexed and the values are the extracted values. This map is used by the IndexAwareComparators to avoid a conversion and value extraction steps.

      • m_mapInverse

        protected Map m_mapInverse
        Map that contains the index contents (inverse index). The keys of the Map are the return values from the ValueExtractor operating against the entries of the resource map, and for each key, the corresponding value stored in the Map is a Set of keys to the resource map.

      • m_fSplitCollection

        protected boolean m_fSplitCollection
        If a value extracted by the ValueExtractor is a Collection, this property specifies whether or not it should be treated as a Collection of contained attributes or indexed as a single composite attribute.

      • m_cUnits

        protected volatile long m_cUnits
        The size footprint of the index, in units (as defined by the UnitCalculator).

      • m_ldtLogMissingIdx

        protected long m_ldtLogMissingIdx
        The time at which the most recent logging of "missing inverse index" messages started.

      • m_cLogMissingIdx

        protected int m_cLogMissingIdx
        The number of "missing inverse index" messages that have been logged.

      • m_setKeyExcluded

        protected Set m_setKeyExcluded
        A set of keys for the entries, which could not be included in the index.

      • m_fForwardIndex

        protected boolean m_fForwardIndex
        Specifies whether or not this MapIndex supports a forward index.

      • m_fImmutableValues

        protected boolean m_fImmutableValues
        Specifies whether or not the index is based on the immutable values (e.g. keys).

    • Constructor Detail

      • SimpleMapIndex

        public SimpleMapIndex​(ValueExtractor extractor,
                      boolean fOrdered,
                      Comparator comparator,
                      BackingMapContext ctx)
        Construct an index for the given map.
        Parameters:
        extractor - the ValueExtractor that is used to extract an indexed value from a resource map entry
        fOrdered - true iff the contents of the indexed information should be ordered; false otherwise
        comparator - the Comparator object which imposes an ordering on entries in the index map; or null if the entries' values natural ordering should be used
        ctx - the context associated with the indexed cache

      • SimpleMapIndex

        protected SimpleMapIndex​(ValueExtractor extractor,
                         boolean fOrdered,
                         Comparator comparator,
                         boolean fInit,
                         BackingMapContext ctx)
        Construct an index for the given map.
        Parameters:
        extractor - the ValueExtractor that is used to extract an indexed value from a resource map entry
        fOrdered - true iff the contents of the indexed information should be ordered; false otherwise
        comparator - the Comparator object which imposes an ordering on entries in the index map; or null if the entries' values natural ordering should be used
        fInit - initialize the index if true
        ctx - the context associated with the indexed cache

    • Method Detail

      • getValueExtractor

        public ValueExtractor getValueExtractor()
        Obtain the ValueExtractor object that the MapIndex uses to extract an indexable Object from a value stored in the indexed Map. This property is never null.
        Specified by:
        getValueExtractor in interface MapIndex
        Returns:
        a ValueExtractor object, never null

      • isOrdered

        public boolean isOrdered()
        Determine if the MapIndex orders the contents of the indexed information. To determine in which way the contents are ordered, get the Comparator from the index contents SortedMap object.
        Specified by:
        isOrdered in interface MapIndex
        Returns:
        true if the index contents are ordered, false otherwise

      • isPartial

        public boolean isPartial()
        Determine if indexed information for any entry in the indexed Map has been excluded from this index. This information is used for IndexAwareFilter implementations to determine the most optimal way to apply the index.

        Note: Queries that use a partial index are allowed not to return entries that are not indexed even though they would match the corresponding filter were they evaluated during the full scan (if there were no index). However, it's not allowable for a query to return entries that do not match the corresponding filter, regardless of their presence in the index.

        Specified by:
        isPartial in interface MapIndex
        Returns:
        true if any entry of the indexed Map has been excluded from the index, false otherwise

      • getComparator

        public Comparator getComparator()
        Get the Comparator used to sort the index.
        Specified by:
        getComparator in interface MapIndex
        Returns:
        the comparator

      • getIndexContents

        public Map getIndexContents()
        Get the Map that contains the index contents.

        The keys of the Map are the return values from the ValueExtractor operating against the indexed Map's values, and for each key, the corresponding value stored in the Map is a Set of keys to the indexed Map.

        If the MapIndex is known to be ordered, then the returned Map object will be an instance of SortedMap. The SortedMap may or may not have a Comparator object associated with it; see SortedMap.comparator().

        A client should assume that the returned Map object is read-only and must not attempt to modify it.

        Specified by:
        getIndexContents in interface MapIndex
        Returns:
        a Map (or a SortedMap) of the index contents

      • get

        public Object get​(Object oKey)
        Using the index information if possible, get the value associated with the specified key. This is expected to be more efficient than using the ValueExtractor against an object containing the value, because the index should already have the necessary information at hand.
        Specified by:
        get in interface MapIndex
        Parameters:
        oKey - the key that specifies the object to extract the value from
        Returns:
        the value that would be extracted by this MapIndex's ValueExtractor from the object specified by the passed key; NO_VALUE if the index does not have the necessary information

      • insert

        public void insert​(Map.Entry entry)
        Update this index in response to a insert operation on a cache.
        Specified by:
        insert in interface MapIndex
        Parameters:
        entry - the entry representing the object being inserted

      • update

        public void update​(Map.Entry entry)
        Update this index in response to an update operation on a cache.
        Specified by:
        update in interface MapIndex
        Parameters:
        entry - the entry representing the object being updated

      • delete

        public void delete​(Map.Entry entry)
        Update this index in response to a remove operation on a cache.
        Specified by:
        delete in interface MapIndex
        Parameters:
        entry - the entry representing the object being removed

      • isOptimizeMV

        public boolean isOptimizeMV()
        Specifies whether an attempt will be made to search the forward map for an existing reference that is "equal" to the specified mutli-value and use it instead (if available) to reduce the index memory footprint.
        Returns:
        true iff multi-value optimization is allowed

      • setOptimizeMV

        public void setOptimizeMV​(boolean fOptimizeMV)
        For an indexed value that is a multi-value (Collection or array) this flag specifies whether an attempt should be made to search the forward map for an existing reference that is "equal" to the specified mutli-value and use it instead (if available) to reduce the index memory footprint.

        Note, that even if this optimization is allowed, the full search could be quite expensive and our algorithm will always limit the number of cycles it spends on the search.

        Parameters:
        fOptimizeMV - the boolean value to set

      • getUnits

        public long getUnits()
        Retrieve the size of this index in units (as defined by the UnitCalculator).
        Specified by:
        getUnits in interface MapIndex
        Returns:
        the main, non-partitioned index size

      • setUnits

        protected void setUnits​(long cUnits)
        Set the size of this index in units (as defined by the UnitCalculator).
        Parameters:
        cUnits - new index size

      • isForwardIndexSupported

        public boolean isForwardIndexSupported()
        Determine whether or not this SimpleMapIndex supports a forward index.
        Returns:
        true if this SimpleMapIndex supports a forward index; false otherwise

      • initialize

        protected void initialize​(boolean fForwardIndex)
        Initialize the index's data structures.
        Parameters:
        fForwardIndex - specifies whether or not this index supports a forward map

      • getForwardEntry

        protected Map.Entry getForwardEntry​(Object oKey)
        Get the forward index entry associated with the specified key.
        Parameters:
        oKey - the key
        Returns:
        the entry associated with the given key

      • addForwardEntry

        protected void addForwardEntry​(Object oKey,
                               Object oIxValueNew)
        Add a new mapping to the forward index map.
        Parameters:
        oKey - the key to add to the mapping
        oIxValueNew - the new value to add to the mapping

      • updateForwardEntry

        protected void updateForwardEntry​(Object oKey,
                                  Object oIxValueNew)
        Update a mapping in the forward index map.
        Parameters:
        oKey - the key to update
        oIxValueNew - the new value for the mapping

      • removeForwardEntry

        protected void removeForwardEntry​(Object oKey)
        Remove the forward index entry for the specified key.
        Parameters:
        oKey - the key to remove the forward index entry for

      • extractNewValue

        protected Object extractNewValue​(Map.Entry entry)
        Extract the "new" value from the specified entry.
        Parameters:
        entry - the entry to extract the "new" value from
        Returns:
        the extracted "new" value, or NO_VALUE if the extraction failed

      • extractOldValue

        protected Object extractOldValue​(MapTrigger.Entry entry)
        Extract the "old" value from the specified entry.
        Parameters:
        entry - the entry to extract the "old" value from
        Returns:
        the extracted "old" value, or NO_VALUE if the extraction failed

      • ensureCollection

        protected Collection ensureCollection​(Object oValue)
        Return a Collection representation of the specified value, which could be a Collection, Object[], scalar, or NO_VALUE.
        Parameters:
        oValue - the value
        Returns:
        a Collection representation of the specified value, or an empty Collection if NO_VALUE

      • instantiateForwardIndex

        protected Map instantiateForwardIndex()
        Instantiate the forward index.

        Note: To optimize the memory footprint of the forward index, any subclasses of the SimpleMapIndex that override this method must also implement the getForwardEntry(Object) method accordingly.

        Returns:
        the forward index

      • instantiateInverseIndex

        protected Map instantiateInverseIndex​(boolean fOrdered,
                                      Comparator comparator)
        Instantiate the inverse index.
        Parameters:
        fOrdered - true iff the contents of the indexed information should be ordered; false otherwise
        comparator - the Comparator object which imposes an ordering on entries in the index map; or null if the entries' values natural ordering should be used
        Returns:
        the inverse index

      • insertInternal

        protected void insertInternal​(Map.Entry entry)
        Update this index in response to a insert operation on a cache.
        Parameters:
        entry - the entry representing the object being inserted

      • updateInternal

        protected void updateInternal​(Map.Entry entry)
        Update this index in response to an update operation on a cache.
        Parameters:
        entry - the entry representing the object being updated

      • deleteInternal

        protected void deleteInternal​(Map.Entry entry)
        Update this index in response to a remove operation on a cache.
        Parameters:
        entry - the entry representing the object being removed

      • addInverseMapping

        protected Object addInverseMapping​(Object oIxValue,
                                   Object oKey)
        Add a new mapping from the given indexed value to the given key in the inverse index.
        Parameters:
        oIxValue - the indexed value (serves as a key in the inverse index)
        oKey - the key to insert into the inverse index
        Returns:
        an already existing reference that is "equal" to the specified value (if available)

      • addInverseMapping

        protected Object addInverseMapping​(Map<Object,​Set<Object>> mapIndex,
                                   Object oIxValue,
                                   Object oKey)
        Add a new mapping from the given indexed value to the given key in the supplied index.
        Parameters:
        mapIndex - the index to which to add the mapping
        oIxValue - the indexed value (serves as a key in the inverse index)
        oKey - the key to insert into the inverse index
        Returns:
        an already existing reference that is "equal" to the specified value (if available)

      • addInverseCollectionMapping

        protected Object addInverseCollectionMapping​(Map mapIndex,
                                             Object oIxValue,
                                             Object oKey)
        Add new mappings from the elements of the given value to the given key in the supplied index. The given value is expected to be either a Collection or an Object array.
        Parameters:
        mapIndex - the index to which to add the mapping
        oIxValue - the indexed Collection value (each element serves as a key in the inverse index)
        oKey - the key to insert into the inverse index
        Returns:
        an already existing reference that is "equal" to the specified value (if available)

      • removeInverseMapping

        protected void removeInverseMapping​(Object oIxValue,
                                    Object oKey,
                                    Collection colIgnore)
        Remove the mapping from the given indexed value to the given key from the inverse index.
        Parameters:
        oIxValue - the indexed value, or NO_VALUE if unknown
        oKey - the key
        colIgnore - the Collection of values to ignore (exclude from removal), or null

      • removeInverseMapping

        protected void removeInverseMapping​(Object oIxValue,
                                    Object oKey)
        Remove the mapping from the given indexed value to the given key from the inverse index.
        Parameters:
        oIxValue - the indexed value, or NO_VALUE if unknown
        oKey - the key

      • removeInverseMapping

        protected void removeInverseMapping​(Map mapIndex,
                                    Object oIxValue,
                                    Object oKey)
        Remove the mapping from the given indexed value to the given key from the supplied index.
        Parameters:
        mapIndex - the index from which to remove the mapping
        oIxValue - the indexed value
        oKey - the key

      • logMissingIdx

        protected void logMissingIdx​(Object oIxValue,
                             Object oKey)
        Log messages for missing inverse index.
        Parameters:
        oIxValue - the indexed value
        oKey - the key

      • collectRemoved

        protected Set collectRemoved​(Object oIxValueOld,
                             Object oIxValueNew)
        Given that the old value is known to be a Collection or an array, collect all the enclosed elements that are not part of the new value.
        Parameters:
        oIxValueOld - the old value (must be a collection or an array)
        oIxValueNew - the new value
        Returns:
        the set of values that are contained in the old collection or array, but not part of the new value

      • instantiateSet

        protected Set instantiateSet()
        Factory method used to create a new set containing the keys associated with a single value.
        Returns:
        a Set to keep the corresponding keys at

      • onMappingRemoved

        protected void onMappingRemoved()
        Decrease the size of the index by the size of an index map entry.

      • onMappingRemoved

        protected void onMappingRemoved​(Object oValue)
        Decrease the size of the index by the estimated size of the specified removed value.
        Parameters:
        oValue - the value being removed from the index

      • onMappingAdded

        protected void onMappingAdded()
        Increase the size of the index by the size of an index map entry.

      • onMappingAdded

        protected void onMappingAdded​(Object oValue,
                              int cSize)
        Increase the size of the index by the estimated size of the specified added value.
        Parameters:
        oValue - the value being added to the index
        cSize - the current key set size indexed by the given value

      • updateExcludedKeys

        protected void updateExcludedKeys​(Map.Entry entry,
                                  boolean fExclude)
        Check the entry against the set of entries not included in the index and update the set if necessary.
        Parameters:
        entry - the entry to be checked
        fExclude - true iff the insert or update of the entry into the index caused an exception

      • isKeyExcluded

        protected boolean isKeyExcluded​(Object oKey)
        Check if the entry with the given key is excluded from the index.
        Parameters:
        oKey - the key to test
        Returns:
        true if the key is in the list of keys currently excluded from the index, false if the entry with the key is in the index

      • toString

        public String toString()
        Returns a string representation of this SimpleMapIndex.
        Overrides:
        toString in class Object
        Returns:
        a String representation of this SimpleMapIndex

      • toString

        public String toString​(boolean fVerbose)
        Returns a string representation of this SimpleMapIndex. If called in verbose mode, include the contents of the index (the inverse index). Otherwise, just print the number of entries in the index.
        Parameters:
        fVerbose - if true then print the content of the index otherwise print the number of entries
        Returns:
        a String representation of this SimpleMapIndex

      • equals

        public boolean equals​(Object o)
        Compares the specified object with this index for equality. Returns true if the given object is also a SimpleMapIndex and the two represent the same index.
        Overrides:
        equals in class Object
        Parameters:
        o - object to be compared for equality with this MapIndex
        Returns:
        true if the specified object is equal to this index

      • hashCode

        public int hashCode()
        Returns the hash code value for this MapIndex.
        Overrides:
        hashCode in class Object
        Returns:
        the hash code value for this MapIndex