In this paper, we introduce structural join index hierarchy (SJIH) indexing mechanisms that mimic the class composition hierarchy of the complex objects to provide direct access to multimedia objects and/or their component objects. A cost model for processing the queries and maintaining the indices is developed. A heuristic algorithm is designed to select appropriate indices to efficiently process a given set of multimedia queries. Through the use of a News-on-Demand example, we show that SJIH indexing mechanisms facilitate efficient query processing in multimedia applications.