Слияние кода завершено, страница обновится автоматически
CQEngine — Collection Query Engine — это высокопроизводительная коллекция Java, которую можно искать с помощью запросов, похожих на SQL, с чрезвычайно низкой задержкой.
Поддерживает сохранение в куче, сохранение вне кучи, сохранение на диске и поддерживает изоляцию транзакций MVCC.
Интересные обзоры CQEngine:
Классический способ извлечения объектов, соответствующих некоторым критериям из коллекции, заключается в том, чтобы перебрать коллекцию и применить некоторые тесты к каждому объекту. Если объект соответствует критериям, он добавляется в набор результатов. Это повторяется для каждого объекта в коллекции.
Обычная итерация крайне неэффективна, её сложность по времени составляет O(n t). Её можно оптимизировать, но она требует статистического знания состава коллекции. Подробнее: Ограничения Итерации.
Краткий обзор тестов
Даже с оптимизацией, применённой к обычной итерации, CQEngine может значительно превзойти обычную итерацию. Вот график теста, сравнивающего задержку CQEngine с итерацией для запроса типа диапазона:
Подробности этого теста и других тестов с различными типами запросов см. на вики-странице Benchmark.
CQEngine решает проблемы масштабируемости и задержки итераций, позволяя создавать индексы для полей объектов, хранящихся в коллекции, и применяя алгоритмы, основанные на правилах теории множеств, для снижения сложности времени доступа к ним.
Индексирование и оптимизация плана запросов
К любому количеству отдельных полей в коллекции объектов можно добавить простые индексы, что позволяет отвечать на запросы только по этим полям со сложностью O(1).
Можно добавить несколько индексов для одного поля, каждый из которых оптимизирован для разных типов запросов — например, равенство, числовой диапазон, строка начинается с и т. д.
Можно создать составные индексы, которые охватывают несколько полей, что также позволяет отвечать на запросы, ссылающиеся на несколько полей, со сложностью O(1).
Полностью поддерживаются вложенные запросы, такие как эквивалент SQL «WHERE color = 'blue' AND(NOT(doors = 2 OR price > 53.00))».
Можно добавлять постоянные индексы запросов; они позволяют отвечать на произвольно сложные запросы или фрагменты вложенных запросов со сложностью O(1) независимо от количества упомянутых полей. Большие запросы, содержащие ветви или фрагменты запросов, для которых существуют постоянные индексы запросов, автоматически получат выгоду от... Оценка сложности времени выполнения их ветвей; в общей сложности можно использовать несколько индексов для ускорения сложных запросов
Оптимизация статистического плана запроса — когда у нескольких полей есть подходящие индексы, CQEngine будет использовать статистическую информацию из индексов, чтобы внутренне составить план запроса, который выбирает индексы, способные выполнить запрос с минимальной сложностью по времени. Когда некоторые из упомянутых полей имеют подходящие индексы, а некоторые нет, CQEngine сначала будет использовать доступные индексы и затем переберёт наименьший возможный набор результатов из этих индексов, чтобы отфильтровать объекты для остальной части запроса. В таких случаях сложность по времени будет больше, чем O(1), но обычно значительно меньше, чем O(n)
Резервное копирование итераций — если подходящие индексы недоступны, CQEngine оценит запрос через итерацию, используя ленивую оценку. CQEngine всегда может оценить каждый запрос, даже если подходящие индексы отсутствуют. Запросы не связаны с индексами, поэтому индексы можно добавить после факта, чтобы ускорить существующие запросы
CQEngine поддерживает полную параллельность и ожидает, что объекты будут добавлены в коллекцию и удалены из неё во время выполнения; CQEngine позаботится об обновлении всех зарегистрированных индексов в реальном времени
Типобезопасность — почти все ошибки в запросах приводят к ошибкам времени компиляции вместо исключений во время выполнения: все индексы и все запросы строго типизированы с использованием дженериков как на уровне объектов, так и на уровне полей
В куче/вне кучи/на диске — объекты могут храниться в куче (как обычная Java-коллекция), вне кучи (в собственной памяти, внутри процесса JVM, но вне Java-кучи) или сохраняться на диске
Предоставляется несколько реализаций IndexedCollection CQEngine, поддерживающих различные уровни параллелизма и изоляции транзакций:
ConcurrentIndexedCollection — безблокировочные параллельные чтения и записи без изоляции транзакций
ObjectLockingIndexedCollection — безблокировочные параллельные чтения, некоторая блокировка записей для изоляции и согласованности транзакций на уровне объекта
TransactionalIndexedCollection — безблокировочные параллельные чтения и последовательные записи для полной изоляции транзакций с использованием многоверсионного управления параллелизмом
Для получения более подробной информации см. TransactionIsolation.
В приложениях CQEngine в основном взаимодействуют с IndexedCollection, которая является реализацией java.util.Set, и предоставляет два дополнительных метода:
addIndex(SomeIndex) позволяет добавлять индексы в коллекцию
retrieve(Query) принимает Query и возвращает | Compound | ✓ | ✓ | | | | | | | | | | | ✓ |
| Navigable | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | | | | ✓ |
| PartialNavigable | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | | | ✓ | | ✓
| RadixTree | ✓ | ✓ | | | | ✓ | | | | | | | |
| ReversedRadixTree | ✓ | ✓ | | | | | ✓ | | | | | | |
| InvertedRadixTree | ✓ | ✓ | | | | | | | ✓ | | | | | ✓
| SuffixTree | ✓ | ✓ | | | | | ✓ | ✓ | | | | | |
| StandingQuery | | | | | | | | | | | | ✓ | |
| Fallback | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | ✓
| OffHeap | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | | ✓[1] | |
| PartialOffHeap | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | | ✓ | |
| Disk | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | | | | | | ✓[1] | | Атрибуты
CQEngine нуждается в доступе к полям внутри объектов, чтобы создавать индексы по полям и извлекать значение определённого поля из любого заданного объекта.
Вместо рефлексии CQEngine использует атрибуты, которые представляют собой более мощную концепцию. Атрибут — это объект-аксессор, который может считывать значение определённого поля в POJO.
Вот как можно определить атрибут для объекта Car (POJO), который считывает поле Car.carId:
public static final Attribute<Car, Integer> CAR_ID = new SimpleAttribute<Car, Integer>("carId") {
public Integer getValue(Car car, QueryOptions queryOptions) { return car.carId; }
};
...или альтернативно, с помощью лямбда-выражения или ссылки на метод:
public static final Attribute<Car, Integer> Car_ID = attribute("carId", Car::getCarId);
(О некоторых предостережениях относительно использования лямбд читайте в разделе LambdaAttributes).
Обычно атрибуты определяются как анонимные статические конечные объекты, подобные этому. Передача строкового параметра «carId» конструктору на самом деле не обязательна, но рекомендуется, так как он будет отображаться в запросах toString.
Поскольку этот атрибут считывает поле из объекта Car, обычно его размещают внутри класса Car — это делает запросы более читаемыми. Однако его действительно можно определить в любом классе, например, в классе CarAttributes или подобном. Приведённый выше пример относится к SimpleAttribute, который предназначен для полей, содержащих только одно значение.
CQEngine также поддерживает MultiValueAttribute, который может считывать значения полей, которые сами являются коллекциями. Таким образом, он поддерживает создание индексов для объектов на основе таких вещей, как ключевые слова, связанные с этими объектами.
Вот как определить MultiValueAttribute для объекта Car, который считывает значения из Car.features, где это поле представляет собой List:
public static final Attribute<Car, String> FEATURES = new MultiValueAttribute<Car, String>("features") {
public Iterable<String> getValues(Car car, QueryOptions queryOptions) { return car.features; }
};
...или альтернативно, с использованием лямбда-выражения или ссылки на метод:
public static final Attribute<Car, String> FEATURES = attribute(String.class, "features", Car::getFeatures);
Нулевые значения Обратите внимание, что если ваши данные содержат нулевые значения, вам следует использовать SimpleNullableAttribute или MultiValueNullableAttribute.
В частности, обратите внимание, что SimpleAttribute и MultiValueAttribute не выполняют никакой проверки на нулевое значение ваших данных, поэтому если ваши данные непреднамеренно... Использование атрибутов, допускающих значение null
Если вы используете атрибут, не допускающий значение null, и получаете исключение NullPointerException, это, вероятно, связано с тем, что вы использовали неправильный тип атрибута. Проблема обычно решается, если вы измените свой код так, чтобы использовать атрибут, допускающий значение null. Если вы не уверены, могут ли ваши данные содержать значения null, просто используйте атрибуты, допускающие значение null. Они содержат логику для автоматической проверки и обработки значений null.
Атрибуты, допускающие значение null, также позволяют CQEngine работать с объектным наследованием, где некоторые объекты в коллекции имеют определённые необязательные поля (например, в подклассах), а другие — нет.
Создание запросов динамически
Динамические запросы можно составлять во время выполнения программы, создавая и комбинируя объекты Query напрямую; см. этот пакет и этот пакет. В сложных случаях также возможно определять атрибуты во время выполнения, используя ReflectiveAttribute или AttributeBytecodeGenerator.
Генерация атрибутов автоматически
CQEngine также предоставляет несколько способов автоматической генерации атрибутов.
Обратите внимание, что это альтернатива использованию ReflectiveAttribute, который обсуждался выше. В то время как ReflectiveAttribute — это особый тип атрибута, который считывает значения во время выполнения с помощью отражения, AttributeSourceGenerator и AttributeBytecodeGenerator генерируют код для атрибутов, который компилируется и поэтому не использует отражение во время выполнения, что может быть более эффективным.
Подробнее см. в AutoGenerateAttributes.
Атрибуты как функции
Следует отметить, что от атрибутов требуется только возвращать значение для объекта. Хотя большинство будет делать это, нет требования, чтобы атрибут предоставлял значение путём чтения поля в объекте. Таким образом, атрибуты могут быть виртуальными, реализованными как функции.
Вычисленные атрибуты
Атрибут может вычислять подходящее значение для объекта на основе функции, применяемой к данным, содержащимся в других полях, или к внешним источникам данных.
Вот как определить вычисляемый (или виртуальный) атрибут с помощью функции. Над другими полями автомобиля:
public static final Attribute<Car, Boolean> IS_DIRTY = new SimpleAttribute<Car, Boolean>("is_dirty") {
public Boolean getValue(Car car, QueryOptions queryOptions) { return car.description.contains("dirty"); }
};
...или то же самое с использованием лямбда-выражения:
public static final Attribute<Car, Boolean> IS_DIRTY = attribute("is_dirty", car -> car.description.contains("dirty"));
На основе виртуального атрибута выше можно создать HashIndex, который позволит быстро извлекать автомобили, которые являются грязными или чистыми, без необходимости сканирования коллекции.
Ассоциации с другими IndexedCollections или внешними источниками данных
Вот пример виртуального атрибута, который связывает каждый автомобиль со списком мест, где его можно обслужить, из внешнего источника данных:
public static final Attribute<Car, String> SERVICE_LOCATIONS = new MultiValueAttribute<Car, String>() {
public List<String> getValues(Car car, QueryOptions queryOptions) {
return CarServiceManager.getServiceLocationsForCar(car);
}
};
Атрибут выше позволит искать в IndexedCollection автомобилей автомобили, у которых есть варианты обслуживания в определённом месте.
Места, где можно обслуживать автомобиль, могут быть получены из другой IndexedCollection, например, гаражей. Однако следует соблюдать осторожность при создании индексов на виртуальных атрибутах, если ссылочные данные могут измениться, оставив устаревшую информацию в индексах. Стратегия для решения этой проблемы заключается в следующем: если для виртуального атрибута, на который ссылается запрос, не существует индекса, и в запросе также упоминаются другие атрибуты, для которых существуют индексы, CQEngine автоматически сократит набор кандидатов объектов до минимума, используя другие индексы, прежде чем запрашивать виртуальный атрибут. В свою очередь, если виртуальные атрибуты выполняют выборки из других IndexedCollection, эти коллекции можно проиндексировать соответствующим образом без риска устаревших данных.
В приведённых выше примерах определены атрибуты основной IndexedCollection, которые считывают данные из вторичных коллекций или внешних источников данных.
Также можно выполнять SQL EXISTS-подобные запросы и соединения между IndexedCollection на стороне запроса (в отличие от стороны атрибутов). Примеры см. в разделе «Соединения» (Joins).
IndexedCollection CQEngine можно настроить для хранения объектов, добавленных в них, в куче (по умолчанию), вне кучи или на диске.
В куче
Храните коллекцию в куче Java:
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>();
Вне кучи
Храните коллекцию в собственной памяти внутри процесса JVM, но вне кучи Java:
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>(OffHeapPersistence.onPrimaryKey(Car.CAR_ID));
Обратите внимание, что сохранение вне кучи автоматически создаст индекс для указанного первичного ключа, поэтому нет необходимости добавлять индекс к этому атрибуту позже.
На диске
Храните коллекцию во временном файле на диске (затем см. DiskPersistence.getFile()):
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>(DiskPersistence.onPrimaryKey(Car.CAR_ID));
Или храните коллекцию в конкретном файле на диске:
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>(DiskPersistence.onPrimaryKeyInFile(Car.CAR_ID, new File("cars.dat")));
Обратите внимание, что сохранение на диске автоматически создаст индекс для указанного первичного ключа, поэтому нет необходимости добавлять индекс к этому атрибуту позже.
Обёртка
Оберните любую коллекцию Java в IndexedCollection CQEngine без копирования объектов. Это может быть удобным способом выполнения запросов или создания индексов для существующих коллекций. Однако применяются некоторые предостережения, касающиеся поддержки параллелизма и производительности базовой коллекции. Использование WrappingPersistence
Для получения более подробной информации см. WrappingPersistence.
Collection<Car> collection = // получаем любую коллекцию Java
IndexedCollection<Car> indexedCollection = new ConcurrentIndexedCollection<Car>(
WrappingPersistence.aroundCollection(collection)
);
Composite
CompositePersistence настраивает комбинацию типов персистентности для использования в одной коллекции. Сама коллекция будет сохраняться в первом типе персистентности (первичная персистентность), а дополнительные типы персистентности, предоставленные, будут использоваться внекучевыми или дисковыми индексами, добавленными к коллекции впоследствии.
Сохраните коллекцию в куче и также настройте DiskPersistence для использования DiskIndexes, добавленных к коллекции впоследствии:
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<Car>(CompositePersistence.of(
OnHeapPersistence.onPrimaryKey(Car.CAR_ID),
DiskPersistence.onPrimaryKeyInFile(Car.CAR_ID, new File("cars.dat"))
));
Индексы также могут быть сохранены в куче, вне кучи или на диске. Каждому индексу требуется определённый тип персистентности. Необходимо заранее настроить коллекцию с соответствующей комбинацией персистентностей для использования любыми добавляемыми индексами.
Можно сохранить коллекцию в куче, но некоторые индексы — вне кучи. Также можно иметь различные типы индексов в одной коллекции, каждый из которых использует свой тип персистентности. Персистентность в куче является самой быстрой, за ней следует персистентность вне кучи, а затем — дисковая персистентность.
Если и коллекция, и все её индексы хранятся вне кучи или на диске, то можно создать чрезвычайно большие коллекции, которые вообще не используют память кучи или оперативную память.
CQEngine был протестирован с использованием персистентности вне кучи для коллекций из 10 миллионов объектов и с использованием дисковой персистентности для коллекций из 100 миллионов объектов.
В куче
Добавьте индекс в куче по «производителю»:
cars.addIndex(NavigableIndex.onAttribute(Car.MANUFACTURER));
Вне кучи
Добавьте внекучевой индекс по «производителю»:
cars.addIndex(OffHeapIndex.onAttribute(Car.MANUFACTURER));
На диске
Добавьте дисковый индекс по «производителю»:
cars.addIndex(DiskIndex.onAttribute(Car.MANUFACTURER));
Когда IndexedCollection или один или несколько индексов расположены вне кучи или на диске, позаботьтесь о том, чтобы закрыть ResultSet после завершения чтения. Вы можете использовать блок try-with-resources для достижения этого:
try (ResultSet<Car> results = cars.retrieve(equal(Car.MANUFACTURER, "Ford"))) {
results.forEach(System.out::println);
}
ResultSet CQEngine предоставляют следующие методы:
ResultSet, возвращая следующий объект, соответствующий запросу, при каждой итерации, как определено посредством ленивой оценки;ResultSet<Car> results = cars.retrieve(query, queryOptions(orderBy(descending(Car.PRICE))));
Сортировать по цене по убыванию, затем по количеству дверей по возрастанию
ResultSet<Car> results = cars.retrieve(query, queryOptions(orderBy(descending(Car.PRICE), ascending(Car.DOORS))));
Обратите внимание, что при упорядочивании результатов, как указано выше, используется стратегия упорядочивания materialize по умолчанию. Это относительно дорого, зависит от количества объектов, соответствующих запросу, и может вызвать задержку при доступе к первому объекту. Требуется, чтобы все результаты были материализованы в отсортированный набор заранее, прежде чем можно будет начать итерацию.
CQEngine также поддерживает использование индекса для ускорения или устранения накладных расходов на упорядочивание результатов. Эта стратегия снижает задержку доступа к первому объекту в отсортированных результатах за счёт увеличения общих накладных расходов, если весь ResultSet был пройден. Подробнее: OrderingStrategies
Стратегии слияния — это алгоритмы, которые CQEngine использует для оценки запросов с несколькими ветвями.
По умолчанию CQEngine будет использовать стратегии, подходящие для большинства приложений, однако эти стратегии можно переопределить для настройки производительности. Подробнее: MergeStrategies.
Квантование включает преобразование мелкозернистых или непрерывных значений в дискретные или крупнозернистые значения. Квантизатор — это функция, которая принимает мелкозернистые значения в качестве входных данных и сопоставляет их с крупнозернистыми аналогами в качестве выходных данных, отбрасывая некоторую точность.
Квантование может быть полезным инструментом для настройки размера индексов, обмена уменьшением размера индекса на увеличение нагрузки на ЦП и наоборот. Подробнее: Квантование и включённые квантизаторы.
CQEngine разработан с учётом поддержки группировки и агрегирования, но обратите внимание, что это не встроено в саму библиотеку CQEngine, поскольку CQEngine предназначен для интеграции с Java 8+ Streams. Это позволяет группировать, агрегировать и преобразовывать результаты CQEngine гибкими способами с использованием лямбда-выражений.
CQEngine ResultSet можно преобразовать в Java 8 Stream, вызвав ResultSet.stream().
Обратите внимание, что потоки оцениваются через фильтрацию и они не используют индексы CQEngine. Поэтому для достижения наилучшей производительности большая часть общего запроса должна быть заключена в запрос CQEngine, а не в лямбда-выражениях в потоке. Такое сочетание значительно превзойдёт поток и лямбда-выражение, которое просто фильтрует коллекцию.
Вот как преобразовать ResultSet в Stream, чтобы вычислить отдельный набор цветов автомобилей, соответствующих запросу CQEngine.
public static void main(String[] args) {
IndexedCollection<Car> cars = new ConcurrentIndexedCollection<>();
cars.addAll(CarFactory.createCollectionOfCars(10));
cars.addIndex(NavigableIndex.onAttribute(Car.MANUFACTURER));
Set<Car.Color> distinctColorsOfFordCars = cars.retrieve(equal(Car.MANUFACTURER, "Ford"))
.stream()
.map(Car::getColor)
.collect(Collectors.toSet());
System.out.println(distinctColorsOfFordCars); // prints: [GREEN, RED]
}
MetadataEngine — это высокоуровневый API, который может извлекать метаданные и статистику из индексов, добавленных в коллекцию.
Он предоставляет доступ к следующему:
CQEngine легко интегрируется с JPA/ORM-фреймворками, такими как Hibernate или EclipseLink.
Проще говоря, CQEngine может создавать индексы и выполнять запросы к любому типу коллекций Java или произвольным источникам данных. ORM-фреймворки возвращают объекты сущностей, загруженные из таблиц базы данных в коллекции Java, поэтому CQEngine может выступать в качестве очень быстрого механизма запросов в памяти поверх таких данных.
Использование в Maven и не-Maven проектах
CQEngine находится в Maven Central, и его можно добавить в проект Maven следующим образом:
<dependency>
<groupId>com.googlecode.cqengine</groupId>
<artifactId>cqengine</artifactId>
<version>x.x.x</version>
</dependency>
См. ReleaseNotes для получения последней версии.
Для не-Maven проектов также предоставляется версия, созданная с помощью maven-shade-plugin, которая содержит CQEngine и все его зависимости, упакованные в один файл jar (заканчивающийся на «-all»). Его можно загрузить из Maven central как «-all.jar» здесь.
Использование CQEngine в Scala, Kotlin или других языках JVM
В целом, CQEngine должен быть совместим с другими языками JVM, кроме Java, однако может потребоваться применить несколько хитростей, чтобы он заработал. См. OtherJVMLanguages.md для некоторых советов.
Связанные проекты
CQEngine чем-то похож на Microsoft LINQ, но разница в том, что запросы LINQ к коллекциям оцениваются через итерацию/фильтрацию, тогда как CQEngine использует теорию множеств, поэтому CQEngine превзойдёт LINQ.
Concurrent Trees предоставляет Concurrent Radix Trees и Concurrent Suffix Trees, используемые некоторыми индексами в CQEngine.
Статус проекта
Сообщайте о любых ошибках/запросах функций на вкладке Issues. Для поддержки используйте Дискуссионный форум, а не прямую электронную почту разработчикам.
Большое спасибо JetBrains за поддержку CQEngine бесплатными лицензиями IntelliJ!
Вы можете оставить комментарий после Вход в систему
Неприемлемый контент может быть отображен здесь и не будет показан на странице. Вы можете проверить и изменить его с помощью соответствующей функции редактирования.
Если вы подтверждаете, что содержание не содержит непристойной лексики/перенаправления на рекламу/насилия/вульгарной порнографии/нарушений/пиратства/ложного/незначительного или незаконного контента, связанного с национальными законами и предписаниями, вы можете нажать «Отправить» для подачи апелляции, и мы обработаем ее как можно скорее.
Комментарии ( 0 )