if (search == null || search.length() == 0) {
return null;
}
char[] searchArray = search.toCharArray();
int last_char_index = 0; //индекс в искомой строке
Edge edge = Edge.find(0, searchArray[last_char_index]);
if ((edge == null) || !edge.valid) {
return null;
}
while (last_char_index < search.length()) {
if (edge == null) {
return null;
}
int edge_length = edge.last_char_index - edge.first_char_index + 1;
if (((search.length() - last_char_index) == edge_length) && (search.substring(last_char_index).hashCode() == edge.hash)) {
return edge;
}
for (int i = edge.first_char_index; (i <= edge.last_char_index) && (last_char_index < search.length()); i++) {
if (isTerms(i) != -1) {
return null;
}
if (searchArray[last_char_index] != SuffixTree.T[i]) {
return null;
}
last_char_index++;
}
if (last_char_index < search.length()) {
edge = Edge.find(edge.end_node, searchArray[last_char_index]);
}
}
return edge;
}
Учитывая специфику применения ОСД, приведем метод, который считывает данные из индексируемого столбца, и создает для них ОСД. Метод начинается с получения всех данных индексируемого столбца, потом выполняется создание общей строки с терминальными символами (см. Листинг 3.5). Далее происходит построение ОСД, перевод его в бинарный вид и сохранение ОСД в новой таблице в БД (см. Листинг 3.6).
Листинг 3.5 - Построение S$ из индексируемого столбца
String querySelect = "SELECT ROWID, " + colName + " FROM " + tableName;
StringBuilder stringBuilder = new StringBuilder();
Statement statement = connection.createStatement();
ResultSet resultSet = statement.executeQuery(querySelect);
ArrayList<Integer> idnx_terms = new ArrayList<Integer>();
int[] index_terms;
int indx = 0;
int lastIndex = 0;
while (resultSet.next()) {
String text = resultSet.getString(2);
String rowId = resultSet.getString(1);
stringBuilder.append(text).append(rowId);
idnx_terms.add(lastIndex + text.length());
lastIndex += 18 + text.length();
termsMap.put(indx, rowId);
indx++;
}
Как видим, из Листинга 3.5, получение данных из индексируемого столбца происходит посредством применения реализации JDBC библиотеки Oracle. В процессе прохождения по ResultSet, добавляем строку, её ROWID (в роли $) в StringBuilder. При этом, попутно заполняем массив idnx_terms, который хранит в себе индексы начала $, а также хэш-таблицу с терминальными строками, где ключ - номер строки.
Листинг 3.6 - Построение ОСД и сохранение его в таблицу
SuffixTree suffixTree = new SuffixTree(stringBuilder.toString(), index_terms, termsMap);
byte[] bytes = toByteArray(suffixTree);
String indexTableName = schemaName + "." + indexName;
String queryCreateTable = "CREATE TABLE " + indexTableName + "_TAB (colName VARCHAR2(50), st BLOB, PRIMARY KEY (colName))";
statement.executeUpdate(queryCreateTable);
String queryInsertTable = "INSERT INTO " + indexTableName + "_TAB VALUES (?, ?)";
PreparedStatement preparedStatement = connection.prepareStatement(queryInsertTable);
Blob blob = BLOB.createTemporary(connection, false, BLOB.DURATION_SESSION);
blob.setBytes(1, bytes);
preparedStatement.setString(1, tableName + "_" + colName);
preparedStatement.setBlob(2, blob);
preparedStatement.execute();
3.2 Реализация TYPE в СУБД Oracle
Для того, чтобы СУБД Oracle могла работать с java кодом, одним из методов является вызов следующей команды: CREATE OR REPLACE AND COMPILE JAVA SOURCE NAMED "SuffixTree" AS <Код на java>. После этого код скомпилирован, и его можно использовать внутри СУБД. Мы намеренно не приводим код, его можно увидеть в приложении А данной работы.
Согласно главе 2, сначала определяем TYPE (см. Листинг 3.4)
Листинг 3.4 - Создание TYPE
create or replace TYPE suffixtree_im AS OBJECT
(
frids SYS.ODCIRIDLIST,
searchStr VARCHAR2(1000),
STATIC FUNCTION ODCIGETINTERFACES(ifclist OUT SYS.ODCIOBJECTLIST) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXCREATE
(ia SYS.ODCIINDEXINFO, parms VARCHAR2, env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXTRUNCATE (ia SYS.ODCIINDEXINFO,
env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXDROP(ia SYS.ODCIINDEXINFO,
env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXINSERT(ia SYS.ODCIINDEXINFO, rid ROWID,
newval NUMBER, env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXDELETE(ia SYS.ODCIINDEXINFO, rid ROWID, oldval NUMBER,
env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXUPDATE(ia SYS.ODCIINDEXINFO, rid ROWID, oldval NUMBER,
newval NUMBER, env SYS.ODCIEnv) RETURN NUMBER,
STATIC FUNCTION ODCIINDEXSTART(SCTX IN OUT suffixtree_im, ia SYS.ODCIINDEXINFO,
op SYS.ODCIPREDINFO, qi SYS.ODCIQUERYINFO,
strt NUMBER, stop NUMBER, searchStr VARCHAR2,
env SYS.ODCIEnv) RETURN NUMBER,
MEMBER FUNCTION ODCIINDEXFETCH(SELF IN OUT suffixtree_im, nrows NUMBER,
rids OUT SYS.ODCIRIDLIST, env SYS.ODCIEnv)
RETURN NUMBER,
MEMBER FUNCTION ODCIINDEXCLOSE(env SYS.ODCIEnv) RETURN NUMBER
);
Где frids - лист rowed строк, удовлетворяющих искомой подстоке; searchStr - искомая подстрока.
Далее реализуем объявленные в TYPE suffixtree_im функции в TYPE BODY (см. Листинг 3.7).
Листинг 3.7 - Реализация TYPE BODY suffixtree_im
create or replace TYPE BODY suffixtree_im
IS
STATIC FUNCTION ODCIGETINTERFACES(ifclist OUT SYS.ODCIOBJECTLIST)
RETURN NUMBER IS
BEGIN
ifclist:= SYS.ODCIOBJECTLIST(SYS.ODCIOBJECT('SYS','ODCIINDEX2'));
RETURN ODCICONST.SUCCESS;
END ODCIGETINTERFACES;
STATIC FUNCTION ODCIINDEXCREATE (ia SYS.ODCIINDEXINFO, parms VARCHAR2, env SYS.ODCIEnv) RETURN
NUMBER
IS
stmt VARCHAR2(4000);
BEGIN
DBMS_OUTPUT.PUT_LINE('Start create index');
stmt:= createIndex(ia);
DBMS_OUTPUT.PUT_LINE(stmt);
RETURN ODCICONST.SUCCESS;
END;
STATIC FUNCTION ODCIINDEXDROP(ia SYS.ODCIINDEXINFO, env SYS.ODCIEnv) RETURN NUMBER IS
stmt VARCHAR2(2000);
BEGIN
stmt:= 'DROP TABLE ' || ia.INDEXSCHEMA || '.' || ia.INDEXNAME || '_TAB';
EXECUTE IMMEDIATE stmt;
RETURN ODCICONST.SUCCESS;
EXCEPTION
WHEN OTHERS THEN
RETURN ODCICONST.SUCCESS;
END;
STATIC FUNCTION ODCIINDEXSTART(SCTX IN OUT suffixtree_im, ia SYS.ODCIINDEXINFO,
op SYS.ODCIPREDINFO, qi SYS.ODCIQUERYINFO,
strt NUMBER, stop NUMBER, searchStr VARCHAR2,
env SYS.ODCIEnv) RETURN NUMBER IS
stmt VARCHAR2(2000);
BEGIN
DBMS_OUTPUT.PUT_LINE(searchStr);
SCTX:= suffixtree_im(SYS.ODCIRIDLIST(), searchStr);
stmt:= readSt(ia);
DBMS_OUTPUT.PUT_LINE(stmt);
RETURN ODCICONST.SUCCESS;
END;
MEMBER FUNCTION ODCIINDEXFETCH(SELF IN OUT suffixtree_im, nrows NUMBER,
rids OUT SYS.ODCIRIDLIST, env SYS.ODCIEnv) RETURN NUMBER IS
BEGIN
DBMS_OUTPUT.PUT_LINE('Find ' || SELF.searchStr);
IF (SELF.frids.count > 0) THEN
RETURN ODCICONST.SUCCESS;
END IF;
rids:= containsStr(SELF.searchStr);
SELF.frids:= rids;
RETURN ODCICONST.SUCCESS;
END;
MEMBER FUNCTION ODCIINDEXCLOSE(env SYS.ODCIEnv) RETURN NUMBER IS
BEGIN
DBMS_OUTPUT.PUT_LINE('Close');
RETURN ODCICONST.SUCCESS;
END;
END;
Функции ODCIINDEXTRUNCATE, ODCIINDEXINSERT, ODCIINDEXDELETE, ODCIINDEXUPDATE не приведены, т.к. согласно главе 2, реализация индекса не поддерживает данные операции - все функции возвращают ODCICONST.ERROR.
Далее, согласно п.4 перечня шагов по созданию индекса, реализуем функции-обёртки, вызывающие определенные методы в JVM.
Это такие методы как:
1. containsStr(seacrh IN VARCHAR2) - возвращает лист rowid строк, содержащих искомую подстроку.
2. createIndex(ia IN SYS.ODCIINDEXINFO) - создает ОСД для инексируемого столбца, возвращает результат операции.
3. readSt(ia IN SYS.ODCIINDEXINFO) - читает ОСД из таблицы БД, если ОСД нет в оперативной памяти, возвращает служебную информацию о том, где производилось чтение (таблица/оперативная память).
Листинг методов приведен в Приложении Б.
Согласно п.6, реализуем функцию поиска подстроки containsTextFunc и оператор CONTAINS_OP, использующий функцию containsTextFunc (см. Листинг 3.8, 3.9).
Листинг 3.8 - Реализация функции поиска подстроки в строках таблицы
create or replace FUNCTION containsTextFunc(colText VARCHAR2, searchStr VARCHAR2, indexctx IN SYS.ODCIIndexCtx, scanctx IN OUT suffixtree_im, scanflg IN NUMBER)
RETURN NUMBER AS
frids SYS.ODCIRIDLIST;
size_list INTEGER;
BEGIN
DBMS_OUTPUT.PUT_LINE('containsTextFunc');
IF (indexctx.IndexInfo IS NOT NULL) THEN
DBMS_OUTPUT.PUT_LINE(searchStr);
frids:= scanctx.frids;
size_list:= frids.count;
DBMS_OUTPUT.PUT_LINE('Size list: ' || size_list);
FOR i in 1.. size_list LOOP
IF (indexctx.rid = frids(i)) THEN
RETURN 1;
END IF;
END LOOP;
RETURN 0;
ELSE
RAISE_APPLICATION_ERROR(-20101, 'A column that has a domain index of' ||
' Position indextype must be the first argument');
END IF;
END;
Где colText - название индексируемого столбца, searchStr - искомая подстрока, indexctx - контекст используемого индекса (неявный аргумент), scanctx - экземпляр нового TYPE suffixtree_im (неявный аргумент), scanflg - флаг сканирования (неявный аргумент). Примечание: неявным аргументом называем такой аргумент, который передает сама СУБД Oracle, это значит, что пользователю не надо его передавать явно.
Листинг 3.9 - Реализация оператора поиска подстроки в строках таблицы
CREATE OR REPLACE OPERATOR "SYSTEM"."CONTAINS_OP" BINDING
(VARCHAR2, VARCHAR2) RETURN NUMBER
WITH INDEX CONTEXT, SCAN CONTEXT "SYSTEM"."SUFFIXTREE_IM"
USING "CONTAINSTEXTFUNC"
Здесь мы командой «WITH INDEX CONTEXT, SCAN CONTEXT "SYSTEM"."SUFFIXTREE_IM"» определяем, чтобы названные выше аргументы (indexctx, scanctx, scanflg) передавались самой СУБД Oracle.
Теперь создаем новый INDEXTYPE contains_indextype, используя новый оператор CONTAINS_OP и TYPE suffixtree_im (см. Листинг 3.10).
Листинг 3.10 - Создание INDEXTYPE contains_indextype
CREATE INDEXTYPE contains_indextype
FOR contains_op(VARCHAR2, VARCHAR2)
USING suffixtree_im;
Когда contains_indextype создан, мы можем создать INDEX. Для примера берется таблица text_table со столбцом text (см. Листинг 3.11).
Листинг 3.11 - Создание INDEX text_index
CREATE INDEX text_index ON text_table(text)
INDEXTYPE IS contains_indextype;
Индекс успешно создан, теперь можно переходить к исследованию полученных результатов (Глава 4).
Выводы по Главе 3: В этой главе, мы реализовали алгоритм построения ОСД (на основе алгоритма Укконена) и поиска строк с заданной подстрокой в нем (алгоритмы были описаны в Главе 2 данной работы). Также встроили эту реализацию в СУБД Oracle, добавив функционал записи ОСД в таблицу, чтения из неё, а также добавив метод построения ОСД из строк индексируемого столбца. Для всего этого использовалась библиотека JDBC Oracle.
В Oracle был создан новый TYPE, который реализует функции интерфейса ODCIIndex, отвечающего за взаимодействие СУБД с пользовательским индексом. Также реализованы функции-обёртки PL/SQL, вызывающие соответствующие методы в JVM. Одним из завершающих этапов реализации было создание функции поиска подстроки в строках таблицы, использующей новый TYPE, а также создание оператора, использующего эту функцию. После чего был успешно создан пользовательский INDEXTYPE, а далее INDEX. При создании INDEX, ОСД было построено без ошибок, таким образом, считаем, что этап реализации нового типа индекса проведен успешно.
4. Исследование полученных результатов
Для исследования, создадим индекс для таблицы text_table, столбца text (см. Листинг 3.11).
Скорость создания индекса линейна, это показывает эксперимент с построением индекса над столбцом, количество строк которого растет в 2 раза (с одинаковой длиной) перед каждым построением - алгоритм затрачивает каждый раз примерно в 2 раза больше времени.
Для того, чтобы определить увидеть, что функция поиска строк, содержащих искомую подстроку, вызывается и отрабатывает верно, сделаем следующий запрос: select text from text_table where contains_op(text, 'they') = 1;
Запрос возвращает все строки, содержащие в себе подстроку «they». Результат выполнения запроса показан на рисунке 4.1.
Рис. 4.1 Результат поиска строк с подстрокой «they».
Результат верный, попробуем сделать еще один запрос, уже с другой подстрокой - «be»: select text from text_table where contains_op(text, 'be') = 1;
Результат также верен, он показан на рисунке 4.2.
Рис. 4.2 Результат поиска строк с подстрокой «be»
Согласно требованиям, к создаваемому индексу, таблица не может изменяться, проверим это, попытавшись удалить стоку из таблицы text_table. Результат выполнения запроса возвращает ошибку, означающую, что индекс не смог обновиться. Результат показан на рисунке 4.3.
Рис. 4.3 Результат запроса на удаления строки из индексируемой таблицы
Для получения оценки и плана запроса, выполним следующие команды:
set autotrace traceonly explain
select text from text_table where contains_op(text, 'a') = 1;
Результат показан на рисунке 4.4.
Рис. 4.4 Оценка запроса, применяющего пользовательский индекс
Для сравнения, выберем индекс Oracle Text, с его оператором contains(). Oracle Text поставляется с СУБД начиная с 11 версии. Для того чтобы построить индекс над таблицей text_table2 (копия text_table), выполним следующую команду:
CREATE INDEX docs_idx ON text_table2 (text) INDEXTYPE IS ctxsys.context;
Время построения индекса Oracle Text несколько ниже, (процентов на 20-25), но только потому, что jvm проводит сериализацию ОСД, а это достаточно затратная операция. Если провести сравнения, без сохранения ОСД, то индекс на основе ОСД, строится за время, меньшее чем Oracle Text, процентов на 5-10%.
Сравним полученные метрики нового индекса с метриками индекса Oracle Text. Запросы аналогичны приведенным выше, их результат показан на рисунке 4.5.
Рис. 4.5 Оценка запроса, применяющего oracle text индекс
Как видим из рисунков 4.4 и 4.5, планы запросов схожи, различие лишь в графе Cost - у пользовательского индекса стоимость чуть ниже, чем у Oracle Text. Скорость выполнения запросов у двух индексов, примерно одинаковы.
Выводы по главе 4: В данной главе, был протестирован новый тип индекса, на основе ОСД. Согласно полученным результатам запросов, делаем вывод, что алгоритм построения ОСД и поиска в нём работает корректно, т.к. вернувшиеся строки индексируемого столбца в действительности содержат искомую подстроку. Подтвердили эмпирическим путем, что скорость построения ОСД линейна, что соответствует теории. Установили, что Oracle Text затрачивает чуть больше ресурсов ЦПУ. Скорость индексов при поиске подстроки примерно одинакова. Однако Oracle Text строит индекс несколько быстрее, поскольку значительное время jvm тратит на сохранение ОСД.
Заключение
В данной работе была достигнута задача повышения эффективности поиска путем индексирования исходных текстов с использованием суффиксных деревьев.
Выводы по главе 1: Рассмотрены цели индексирования данных, а также некоторые существующие подходы к индексированию данных, посредством применения различных структур хранения индексов. Это такие структуры как битовые карты, хэш-индексы, b-деревья, суффиксное дерево. Были приведены их достоинства и недостатки. Согласно техническому заданию, особо акцентировано внимание на суффиксном дереве, как целевой структуре хранения данных в данной работе.
Выводы по главе 2: Сформулированы принципы построения ОСД, с учетом контекста его применения - в СУБД Oracle. Это такие принципы как: использование rowid (18 знаков) индексируемой строки в качестве терминального символа; способ получения всех rowid строк, содержащих искомую подстроку; построение ОСД алгоритмом Укконена над общей строкой, полученной посредством конкатенации всех строк (с терминальной строкой на конце) индексируемого столбца; сохранение ОСД в таблице БД. Рассмотрели правила создания Extensible Indexing (основываясь на документации СУБД Oracle) применимо к задаче данной работы. Выработали концепцию взаимодействия jvm с СУБД Oracle.