Стратегии упорядочивания

Часто приходится искать компромисс между издержками на получение результатов и издержками на сортировку результатов. Поэтому CQEngine поддерживает различные стратегии минимизации издержек, описанные ниже.

Стратегия упорядочивания: materialize

По умолчанию CQEngine использует стратегию упорядочивания, известную как materialize, чтобы упорядочивать результаты. По сути, это позволяет CQEngine использовать наиболее подходящие индексы для поиска объектов, соответствующих запросу, а затем явно сортировать результаты.

Стратегия упорядочивания: index

Стратегия упорядочивания index позволяет CQEngine использовать индекс по атрибуту, по которому должны быть упорядочены результаты, для управления поиском. Никакие другие индексы не будут использоваться для поиска, но результаты не нужно будет сортировать впоследствии.

Эту стратегию можно включить, настроив EngineThresholds.INDEX_ORDERING_SELECTIVITY, как описано в разделе «Лучшие практики» ниже.

Обратите внимание, что набор индексов, необходимых для поддержки стратегии упорядочивания index для любого конкретного атрибута, зависит от типа атрибута:

• Для SimpleAttribute (тип атрибута, который возвращает ровно одно значение для каждого объекта в коллекции):
  • Требуется индекс для атрибута, который будет использоваться для упорядочения.
    • Одного индекса достаточно, потому что SimpleAttribute гарантирует, что каждый объект в коллекции будет иметь ровно одно значение этого типа атрибута.
• Для SimpleNullableAttribute, MultiValueAttribute или MultiValueNullableAttribute:
  • Индекс для атрибута, который будет использоваться для упорядочивания И
  • Индекс для объектов в коллекции, которые имеют отсутствующие значения для атрибута, который будет использоваться для упорядочивания.
    • Одного индекса недостаточно, поскольку эти типы атрибутов не гарантируют, что каждый объект в коллекции предоставит хотя бы одно значение этих типов атрибутов.
    • Например, если результаты должны быть упорядочены по атрибуту Car.FEATURES, но не у каждой машины в коллекции есть специальные функции, то эти объекты в коллекции будут отсутствовать в индексе для Car.FEATURES.

Вот пример того, как включить стратегию упорядочивания index для MultiValueAttribute (полный исходный код здесь):

public static void main(String[] args) {
    IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>();
    cars.addIndex(NavigableIndex.onAttribute(Car.FEATURES));
    cars.addIndex(NavigableIndex.onAttribute(forObjectsMissing(Car.FEATURES)));
    cars.addAll(CarFactory.createCollectionOfCars(100));

    ResultSet<Car> results = cars.retrieve(
            between(Car.CAR_ID, 40, 50),
            queryOptions(
                    orderBy(ascending(missingLast(Car.FEATURES))),
                    applyThresholds(threshold(INDEX_ORDERING_SELECTIVITY, 1.0))
            )
    );
    for (Car car : results) {
        System.out.println(car); // печатает автомобили с 40 по 50, используя индекс Car.FEATURES для ускорения упорядочивания
    }
}

Лучшие практики

Стратегия упорядочивания index заставляет CQEngine использовать индекс для атрибута, по которому результаты должны быть упорядочены (если доступно), для управления своим поиском.

• Эта стратегия может быть полезна, когда результаты должны быть упорядочены во временных рядах (например, самые последние сначала), и объекты, соответствующие запросу, будут храниться последовательно в индексе, используемом для упорядочивания.
  • Поэтому частичные индексы могут быть чрезвычайно полезны для ускоренного упорядочивания по индексу, поскольку их можно настроить так, чтобы они хранили только объекты, соответствующие любому запросу.
• Также имеет смысл использовать эту стратегию, когда запрос соответствует большой доле collection — потому что это позволяет избежать необходимости сортировать большую часть коллекции впоследствии.

Стратегия упорядочивания materialize позволяет CQEngine использовать другие индексы для поиска объектов, соответствующих запросу, а затем сортировать эти результаты впоследствии.

• Эта стратегия полезна для общих запросов, где объекты, которые должны быть возвращены, не обязательно будут храниться последовательно в любом конкретном индексе, используемом для упорядочения.
• Также имеет смысл извлекать результаты и сортировать их впоследствии, когда необходимо отсортировать небольшое количество результатов и когда другие индексы могут сузить набор объектов-кандидатов более эффективно, чем индекс, используемый для упорядочения.

Приложение может включить стратегию упорядочивания индекса, установив пороговое значение с помощью параметров запроса: applyThresholds(threshold(INDEX_ORDERING_SELECTIVITY, 1.0)).

Пороги избирательности:

• Порог 1,0 говорит CQEngine всегда использовать стратегию упорядочивания по индексу, если требуемые индексы доступны.
• Порог 0,0 (по умолчанию на данный момент) говорит CQEngine никогда не использовать стратегию index и всегда использовать обычную стратегию materialize.
• Установка порога между 0,0 и 1,0, например, 0,5, заставляет CQEngine выбирать между стратегиями index и materialize автоматически, основываясь на избирательности запроса.

Что такое избирательность?

• Избирательность запроса — это мера того, насколько «избирательным» (или «специфичным») является запрос, или, другими словами, насколько велика доля коллекции, которой он соответствует.
• Запрос с высокой избирательностью (приближающейся к 1,0) является специфическим: он соответствует небольшой части коллекции.
• Запрос с низкой избирательностью (приближающийся к 0,0) расплывчат: он соответствует большой части коллекции.

Если указан порог между 0,0 и 1,0, то CQEngine автоматически вычислит избирательность запроса. Затем он автоматически будет использовать стратегию index, если избирательность ниже заданного порога, и стратегию materialize, если избирательность выше заданного порога.

Однако следует отметить, что существует компромисс в вычислениях:

• Вычисление избирательности самого запроса влечёт за собой дополнительные вычислительные затраты.
• Иногда производительность может быть лучше, если принудительно использовать определённую стратегию для определённых типов запросов, чем нести накладные расходы, пытаясь вычислить наилучшую стратегию на лету.