report2010

Отчет о работе за 2010 год

Схематичное перечисление:

• Было проведено исследование требований, которые предъявляет современная наука к технологиям СУБД. Результаты были доложены на нескольких конференциях, готовится публикация ( Научные вызовы технологиям баз данных, Базы данных и астрономия - практический подход).
• Закончен двуязычный русско-английский астрономический тезаурус, http://vo.astronet.ru/dict/, предполагается его дальнейшее развитие и использование для семантического астрономического поиска
• Проведено исследование нескольких ранжирующих функций для полнотекстового поиска в PostgreSQL и сравнение с MySQL и другими поисковыми системами на основе коллекции TREC 8. Было показано, что ранжирование в PostgreSQL коньюктивных (AND) запросов достаточно неплохое, в то время как дизьюнктивные (OR) запросы ранжируются неудовлетворительно. Последние запросы играют важную роль для неполного поиска и семантического поиска. В случае неполного поиска, когда полнотекстовый поиск не вернул (или вернул мало) результатов, можно попробовать расширить запрос, например, трансформацией коньюктивного запроса в дизьюнктивный. При этомб документы ранжируются в зависимости от наличия слов из запроса, например, для запроса 'a AND b AND c' не было ничего найдено, поэтому осуществляем поиск с запросом 'a OR b OR c', при этом документ, содержащий 'a и b' будет ранжироваться выше, чем документ с 'a', или документ с 'c'. Для семантического поиска характерно использование словарей для расширения запроса, при котором исходный простой коньюктивный запрос может легко преобразоваться в сложный, например, запрос 'closed galaxies' после использования словаря превращается в 'close (m33 OR (andromeda AND galaxies) OR (magellanic AND clouds))'. Для улучшения ранжирования дизьюнктивных запросов была разработана новая ранжирующая функция, которая показала на тестовой коллекции TREC 8 хорошую производительность, причем для обоих видов запросов. Также, она гораздо лучше ранжирования в MySQL, которая использует вариант известной формулы tf*idf, для которой требуется статистика по всей коллекции. По материалам исследования готовится публикация.
• Была проведена работа по улучшению семантического графа по материалам астрономического глоссария http://www.astronet.ru/db/graph/
• Была проведена работа по улучшению оценки стоимости обхода обратного индекса по заданному запросу для правильного выбора плана. Ранее использовалась эмпирическая оценка, которая давала очень грубую и завышенную оценку (во много тысяч раз!), что приводило к неиспользованию полнотекстового индекса, а следовательно, плохой производительности. Учет структур в реализации обобщенного обратного индекса позволил получить более точную оценку стоимости его обхода. Результаты исследования были доложены на конференции, а реализация вошла в предстоящий релиз PostgreSQL 9.1.
• Проводились работы по улучшению и развитию алгоритмов обобщенного поискового дерева (GiST, разработанное в рамках грантов РФФИ), которое используется для создания новых типов данных и запросов с индексной поддержкой, и используется во многих научных проектов в астрономии, биологии, науках о Земле и других областях знания. Была изменена стратегия обхода поискового дерева с поиска вглубь (dfs, depth first search) на обход с выбором наилучшего пути в соответствии с заданным правилом (bfs, best first search). Это позволило реализовать алгоритм поиска ближайших соседей с использованием GiST, при котором количество посещаемых узлов становится минимальным и пропорционально лишь глубине дерева. Классическая реализация поиска ближайших соседей в реляционных базах данных основана на чтение всей таблицы, вычисления расстояний до заданной точки, упорядочиванию записей по расстоянию и выдачи первых (ближаших) к-записей, что является абсолютно немасштабируемым решением и в условия "больших данных" , которыми оперирует современная наука, не может быть удовлетворительным решением. Используемые подходы с ограничением поискового пространства не решают проблему, так как требуют знания размеров области наперед. Использование новой стратегии обхода позволило эффективно решить эту проблему - в поисковом дереве посещаются только узлы-кандидаты (на основе оценки минимального расстояния от точки до апроксимирующего прямоугольника) и индекс выдает указатели на записи в таблице уже в нужном порядке. Таким образом достигается высокая производительность выполнения запроса на очень больших базах данных. Эта работа по реализации эффективного поиска ближайших соседей в PostgreSQL была завершена, результаты были доложены на нескольких конференциях и вошли в предстоящий релиз PostgreSQL 9.1. Результаты тестирования на синтетических и реальных данных показали высокую производительность при слабой зависимости от размера базы данных. Особенностью реализации является незначительное изменение (добавление) программного интерфейса GiST при полном сохранении совместимости с ранее разработанными пользовательскими типами данных.
• Сравнение производительности различных способов хранения сферических данных в СУБД PostgreSQL. Одним из основных видов научной информации в современной астрономии являются каталоги объектов различных классов – звезд, инфракрасных и рентгеновских источников, галактик. Объемы каталогов стремительно растут с вводом в строй новых крупномасштабных обзорных проектов - SDSS, PanSTARRS, ожидаемый через несколько лет LSST. Задача эффективного хранения такой информации в современных системах управления базами данных (СУБД) становится все более важной. Основной проблемой при этом является обеспечение возможности быстрого поиска объектов по заданным координатам, что требует создания специальных структур, описывающих их распределение в пространстве координат – поисковых индексов. Для наиболее развитой на данный момент открытой СУБД – PostgreSQL – существуют две основных реализации подобных индексов – Q3C, основанная на бинарном дереве (реализованная при поддержке РФФИ), и реализованная как GiST-индекс pgSphere. Мы провели сравнение производительности основных операций, востребованных в реальной работе с каталогами, для этих индексов. Рассмотренные сценарии включали в себя одномоментную заливку большого объема данных с последующим построением индекса, проведение позиционных выборок с разным размером окна, а также задачу непрерывного пополнения базы постоянно поступающими данным с поддержанием индексов в актуальном состоянии. Проведенные эксперименты показали, что реализация Q3C существенно выигрывает как в случае одномоментной, так и при непрерывной вставке данных в базу, тогда как pgSphere, основанная на более совершенной индексной структуре, оказывается быстрее в задаче позиционной выборки данных. В заключении мы обсуждаем возможные сценарии использования этих типов индексов в реальных условиях современных обзорных экспериментов разного уровня.