class CollectionQueryEngine implements QueryEngineInternal<O> {

    @Override
    public ResultSet<O> retrieve(final Query<O> query, final QueryOptions queryOptions) {
        @SuppressWarnings("unchecked")
        OrderByOption<O> orderByOption = (OrderByOption<O>) queryOptions.get(OrderByOption.class);

        // Store the root query in the queryOptions, so that when retrieveRecursive() examines child branches, that
        // both the branch query and the root query will be available to PartialIndexes so they may determine if they
        // can be used to accelerate the overall query...
        queryOptions.put(ROOT_QUERY, query);

        // Log decisions made to the query log, if provided...
        final QueryLog queryLog = queryOptions.get(QueryLog.class); // might be null

        SortedKeyStatisticsAttributeIndex<?, O> indexForOrdering = null;
        if (orderByOption != null) {
            // Results must be ordered. Determine the ordering strategy to use: i.e. if we should use an index to order
            // results, or if we should retrieve results and sort them afterwards instead.

            Double selectivityThreshold = Thresholds.getThreshold(queryOptions, EngineThresholds.INDEX_ORDERING_SELECTIVITY);
            if (selectivityThreshold == null) {
                selectivityThreshold = EngineThresholds.INDEX_ORDERING_SELECTIVITY.getThresholdDefault();
            }
            final List<AttributeOrder<O>> allSortOrders = orderByOption.getAttributeOrders();
            if (selectivityThreshold != 0.0) {
                // Index ordering can be used.
                // Check if an index is actually available to support it...
                AttributeOrder<O> firstOrder = allSortOrders.iterator().next();
                @SuppressWarnings("unchecked")
                Attribute<O, Comparable> firstAttribute = (Attribute<O, Comparable>)firstOrder.getAttribute();
                if (firstAttribute instanceof OrderControlAttribute) {
                    @SuppressWarnings("unchecked")
                    Attribute<O, Comparable> firstAttributeDelegate = ((OrderControlAttribute)firstAttribute).getDelegateAttribute();
                    firstAttribute = firstAttributeDelegate;
                }

                // Before we check if an index is available to support index ordering, we need to account for the fact
                // that even if such an index is available, it might not contain all objects in the collection.
                //
                // An index built on a SimpleAttribute, is guaranteed to contain all objects in the collection, because
                // SimpleAttribute is guaranteed to return a value for every object.
                // OTOH an index built on a non-SimpleAttribute, is not guaranteed to contain all objects in the
                // collection, because non-SimpleAttributes are permitted to return *zero* or more values for any
                // object. Objects for which non-SimpleAttributes return zero values, will be omitted from the index.
                //
                // Therefore, if we will use an index to order results, we must ensure that the collection also has a
                // suitable index to allow the objects which are not in the index to be retrieved as well. When
                // ordering results, we must return those objects either before or after the objects which are found in
                // the index. Here we proceed to locate a suitable index to use for ordering results, only if we will
                // also be able to retrieve the objects missing from that index efficiently as well...
                if (firstAttribute instanceof SimpleAttribute || standingQueryIndexes.get(not(has(firstAttribute))) != null) {
                    // Either we are sorting by a SimpleAttribute, or we are sorting by a non-SimpleAttribute and we
                    // also will be able to retrieve objects which do not have values for the non-SimpleAttribute
                    // efficiently. Now check if an index exists which would allow index ordering...
                    for (Index<O> index : this.getIndexesOnAttribute(firstAttribute)) {
                        if (index instanceof SortedKeyStatisticsAttributeIndex && !index.isQuantized()) {
                            indexForOrdering = (SortedKeyStatisticsAttributeIndex<?, O>)index;
                            break;
                        }
                    }
                }


                if (queryLog != null) {
                    queryLog.log("indexForOrdering: " + (indexForOrdering == null ? null : indexForOrdering.getClass().getSimpleName()));
                }
                // At this point we might have found an appropriate indexForOrdering, or it might still be null.
                if (indexForOrdering != null) {
                    // We found an appropriate index.
                    // Determine if the selectivity of the query is below the selectivity threshold to use index ordering...
                    final double querySelectivity;
                    if (selectivityThreshold == 1.0) {
                        // Index ordering has been requested explicitly.
                        // Don't bother calculating query selectivity, assign low selectivity so we will use the index...
                        querySelectivity = 0.0;
                    }
                    else if (!indexForOrdering.supportsQuery(has(firstAttribute), queryOptions)) {
                        // Index ordering was not requested explicitly, and we cannot calculate the selectivity.
                        // In this case even though we have an index which supports index ordering,
                        // we don't have enough information to say that it would be beneficial.
                        // Assign high selectivity so that the materialize strategy will be used instead...
                        querySelectivity = 1.0;
                    }
                    else {
                        // The index supports has() queries, which allows us to calculate selectivity.
                        // Calculate query selectivity, based on the query cardinality and index cardinality...
                        final int queryCardinality = retrieveRecursive(query, queryOptions).getMergeCost();
                        final int indexCardinality = indexForOrdering.retrieve(has(firstAttribute), queryOptions).getMergeCost();
                        if (queryLog != null) {
                            queryLog.log("queryCardinality: " + queryCardinality);
                            queryLog.log("indexCardinality: " + indexCardinality);
                        }
                        if (indexCardinality == 0) {
                            // Handle edge case where the index is empty.
                            querySelectivity = 1.0; // treat is as if the query has high selectivity (tend to use materialize).
                        }
                        else if (queryCardinality > indexCardinality) {
                            // Handle edge case where query cardinality is greater than index cardinality.
                            querySelectivity = 0.0; // treat is as if the query has low selectivity (tend to use index ordering).
                        }
                        else {
                            querySelectivity = 1.0 - queryCardinality / (double)indexCardinality;
                        }
                    }

                    if (queryLog != null) {
                        queryLog.log("querySelectivity: " + querySelectivity);
                        queryLog.log("selectivityThreshold: " + selectivityThreshold);
                    }
                    if (querySelectivity > selectivityThreshold) {
                        // Selectivity is too high for index ordering strategy.
                        // Use the materialize ordering strategy instead.
                        indexForOrdering = null;
                    }
                    // else: querySelectivity <= selectivityThreshold, so we use the index ordering strategy.
                }
            }
        }
        ResultSet<O> resultSet;
        if (indexForOrdering != null) {
            // Retrieve results, using an index to accelerate ordering...
            resultSet = retrieveWithIndexOrdering(query, queryOptions, orderByOption, indexForOrdering);
            if (queryLog != null) {
                queryLog.log("orderingStrategy: index");
            }
        }
        else {
            // Retrieve results, without using an index to accelerate ordering...
            resultSet = retrieveWithoutIndexOrdering(query, queryOptions, orderByOption);
            if (queryLog != null) {
                queryLog.log("orderingStrategy: materialize");
            }
        }

        // Return the results, ensuring that the close() method will close any resources which were opened...
        // TODO: possibly not necessary to wrap here, as the IndexedCollections also ensure close() is called...
        return new CloseableResultSet<O>(resultSet, query, queryOptions) {
            @Override
            public void close() {
                super.close();
                CloseableRequestResources.closeForQueryOptions(queryOptions);
            }
        };
    }

    public  CollectionQueryEngine();

}