воскресенье, 1 мая 2016 г.

Oracle Text: Высокоскоростной парсер поисковых запросов, часть I

Хотя эта разработка достаточно древняя, она все еще актуальна и может быть неплохим наглядным пособием по программированию на PL/SQL. Oracle Text активно применяется, кроме того, решение все еще превосходит по скорости функции Oracle с регулярными выражениями.

Данная разработка была выполнена в 2008-2009 году для прикладных применений совместно с Web-based database applications for Oracle.

Oracle Text представляет собой продвинутый механизм полнотекстового поиска с использованием контекстных индексов по столбцам таблицы БД, в том числе содержащих BLOB. 

Однако его прямое использование осложнено тем фактом, что в программном интерфейсе отсутствует какой-либо парсер собственно поисковых запросов (что, в общем, неудивительно), и выставлять Oracle Text непосредственно пользователям весьма опрометчиво. Как минимум, работоспособность Oracle Text в части выполнения запросов вида "абсолютно что угодно от пользователя" под серьезным сомнением.

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

Для начала опишем необходимые нам для парсинга структуры данных, вместе с заголовком функции (парсер нужен именно в виде функции, понятно, почему):

  -- --------------------------------------------------------------  
  function search_string_parser (p_search_str in varchar2,  
                 p_query_mode in varchar2 default 'keyword',  
                 p_logical_op in varchar2 default 'and',  
                 p_query_opt in varchar2   
                 default ctx_api.c_query_op_about,  
                 p_expansion_level in number default 1,  
                 p_thes_name in varchar2 default 'default',  
                 p_refine_on in number   
                 default ctx_api.c_refine_off,  
                 p_exp_detail_on in number  
                 default ctx_api.c_exp_detail_off)   
                 return varchar2 deterministic is  
  -- --------------------------------------------  
  -- p_query_opt must be:  
  -- about (c_query_op_about)  
  -- bt (c_query_op_bt)  
  -- nt (c_query_op_nt)  
  -- rt (c_query_op_rt)  
  -- syn (c_query_op_syn)  
  -- p_expansion_level must be positive when   
  --          specified.  
  -- p_thes_name can be <= 30 characters.  
  -- Known issues:  
  -- 1. p_thes_name cannot contain "_" symbols,   
  --  it will be removed from result string!  
  -- 2. If p_exp_detail_on is enabled,  
  --  p_expansion_level value will be ignored.  
  -- 3. If p_query_opt in ('about','syn','rt') or  
  --  p_query_mode = 'keyword',  
  --  p_exp_detail_on will be ignored.  
  -- --------------------------------------------  
  type token_tab is table of varchar2(4000) index by binary_integer;  
  v_token token_tab; -- Token table  
   
  type exp_lvl_tab is table of number index by binary_integer;  
  v_exp_lvl exp_lvl_tab; -- Expansion levels table  
    
  type v_tt_rec is record (v_tt_token varchar2(4000),   
              v_tt_cnt number); -- TT record type  
  type v_tt_tab is table of v_tt_rec index by binary_integer; -- TT table type  
   
  v_tt v_tt_tab;      -- TT table  
  v_count pls_integer;   -- TT tokens counter  
  v_count2 pls_integer;  -- TT tokens counter 2  
  c_refine_level constant pls_integer := 1; -- Refine level constant. Higher value  
                       -- means more supercategories occurences.  
                       -- Minimum value is 1!  
  /* Note: TT is the Top Term abbreviation */  
  -- v_temp varchar2(4000); -- DEBUG  
  -- v_temp2 number;    -- DEBUG  
   
  v_buffer varchar2(4000); -- Search string buffer  
   
  v_temp_value varchar2(4000); -- Parser variables  
  v_temp_value2 varchar2(4000);  
  v_quotes pls_integer;    -- Quotation variable  
  n pls_integer;        -- Quotation parser counter  
  i pls_integer;        -- Common parser counter  
  j pls_integer;        -- Common final string forming counter  
   
  -- Note: Cannot call procedure hr_show_doc from javascript   
  -- when pass symbolic logical operators into parsed string  
  v_query_mode varchar2(10); -- Query mode buffer  
  c_or_operator constant varchar2(5) := ' or ';  -- OR operator  
  c_and_operator constant varchar2(5) := ' and '; -- AND operator  
  v_operator varchar2(5) := c_and_operator; -- Operator buffer, default AND  
  v_op_fin varchar2(5);           -- Final op buffer  
  v_exp_detail_on number(1) := p_exp_detail_on; -- Expansion detail flag buffer  
   
  v_ext1 varchar2(6); -- Open thes extension  
  v_ext2 varchar2(50); -- Close thes extension (including level and  
            -- thesaurus name)  
  v_expansion_level varchar2(10); -- Expansion functions level  
  v_thes_name varchar2(30);    -- Thesaurus name buffer  
   
  -- --------------------------------------------------------------  

Как вы понимаете, это фрагмент окончательного варианта парсера, который является частью пакета PL/SQL. Пакет будет рассмотрен в следующих частях и доступен для скачивания.

Ключевыми структурами данных являются PL/SQL таблицы, которые будут использоваться для токенов (здесь: отдельных слов) поискового запроса в процессе парсинга:

  type token_tab is table of varchar2(4000) index by binary_integer;  
  v_token token_tab; -- Token table  
   
  type v_tt_rec is record (v_tt_token varchar2(4000),    
        v_tt_cnt number); -- TT record type   
  type v_tt_tab is table of v_tt_rec index by binary_integer; -- TT table type   
     
  v_tt v_tt_tab;   -- TT table   
  v_count pls_integer;  -- TT tokens counter   
  v_count2 pls_integer; -- TT tokens counter 2   


Для начала напишем несколько подпрограмм, которые понадобятся нам в дальнейшем:

  -- Delete unneeded delimiters in whole token  
  function del_delm(p_str in varchar2) return varchar2 is  
  v_str varchar2(4000);  
  begin  
  v_str := replace(p_str,',','');  
  while instr(v_str,' ') > 0 loop -- Remove unneeded spaces  
   v_str := replace(v_str,' ',' ');  
  end loop;  
  return v_str;  
  end del_delm;  
   
  ---- Escape key word in search string  
  function escape_key_word(p_str in varchar2) return varchar2 is  
  v_str varchar2(4000) := p_str; -- Init variable with parameter  
  begin  
  -- Escape all keywords  
  for i in v_reserved.first..v_reserved.last loop  
   v_str := replace(v_str,lower(v_reserved(i)),'{'||lower(v_reserved(i))||'}');  
  end loop;  
  return v_str;  
  end escape_key_word;  
   
  -- Remove key word in search string  
  function remove_key_word(p_str in varchar2) return varchar2 is  
  v_str varchar2(4000) := p_str; -- Init variable with parameter  
  begin  
  -- Remove all keywords  
  for i in v_reserved.first..v_reserved.last loop  
   v_str := replace(v_str,lower(v_reserved(i)),'');  
  end loop;  
  return v_str;  
  end remove_key_word;  
   
  -- Free tokens memory  
  procedure free_memory is  
  /* Uses for clean out PL/SQL tables in parser function */  
  begin  
  v_token.delete;  
  v_tt.delete;  
  if v_exp_detail_on = ctx_api.c_exp_detail_on then  
   v_exp_lvl.delete;  
  end if;  
  exception  
  when others then null;  
  end free_memory;  
   

Важной частью собственно парсера здесь являются процедуры удаления зарезервированных слов Oracle Text из запроса, экранирования ключевых слов OracleText и явного освобождения памяти токенов по завершении работы парсера, без этого существует достаточно высокий риск утечки памяти.

Массив ключевых слов OracleText определяется как:

  type ReservedWordList is table of varchar2(8);  
  v_reserved ReservedWordList := ReservedWordList('ABOUT','ACCUM','BT','BTG','BTI','BTP','FUZZY','HASPATH',  
                  'INPATH','MDATA','MINUS','NEAR','NT','NTG','NTI','NTP','PT','RT','SQE',  
                  'SYN','TR','TRSYN','TT','WITHIN');  
   

Собственно, просто для безопасности я бы, пожалуй, добавил к списку зарезервированных слов, подлежащих безусловному удалению из поискового запроса, ключевое слово UNION. Просто в порядке паранойи от SQL Injection. Почему это не было сделано в окончательном варианте - чтобы кардинально не менять смысл поисковых запросов на английском языке. Собственно, достаточно уже того, что ключевые слова about, within, near, fuzzy и minus сами по себе достаточно сильно меняют смысл поискового запроса, будучи удаленными. Однако, с учетом того факта, что первоначальным предназначением парсера был разбор поисковых запросов на русском языке, с этим можно в достаточной степени мириться. Да, это недостаток существующей реализации.

Прежде, чем приступать к собственно парсингу, с входной строкой следует проделать некоторые базовые процедуры очистки, а также выполнить некоторые очевидные проверки:

  begin /* MAIN BLOCK */  
  -- -----------------------------------------  
  -- Threat null search string  
  if nvl(length(p_search_str),0) = 0 then return null; end if;  
  -- Lowercase and trim spaces  
  v_buffer := trim(lower(p_search_str));  
  -- -----------------------------------------  
  -- Check query mode. If cannot identify, set KEYWORD by default.  
  if lower(p_query_mode) = 'keyword' or   
    lower(p_query_mode) = 'concept' then  
   v_query_mode := lower(p_query_mode);  
  else v_query_mode := 'keyword';  
  end if;  
  -- -----------------------------------------  
  -- Threat query mode  
  if v_query_mode = 'concept' then -- Check search string for keywords  
   v_buffer := escape_key_word(v_buffer); -- In CONCEPT mode ESCAPE keywords  
  else   
   v_buffer := remove_key_word(v_buffer); -- In KEYWORD mode REMOVE keywords  
   v_exp_detail_on := ctx_api.c_exp_detail_off; -- Turn off exp_detail in KEYWORD mode  
  end if;  
  -- -----------------------------------------  
  -- Threat logical operator  
  if lower(p_logical_op) = 'and' or instr(p_logical_op,'&') > 0 then  
   v_operator := c_and_operator;  
  elsif lower(p_logical_op) = 'or' or instr(p_logical_op,'|') > 0 then  
   v_operator := c_or_operator;  
  else               
   v_operator := c_or_operator;  
  end if;  
  -- -----------------------------------------  
  -- Threat ABOUT, RT, SYN and Expansion level flag  
  if (substr(lower(p_query_opt),1,2) = 'ab' or   
    substr(lower(p_query_opt),1,2) = 'rt' or   
    substr(lower(p_query_opt),1,2) = 'sy') then  
   v_exp_detail_on := ctx_api.c_exp_detail_off; -- Turn off exp_detail in ABOUT,RT,SYN mode  
  end if;  
  -- -----------------------------------------  
  /* First and last symbol check and clean */  
  if substr(v_buffer,1,1) = '|' then v_buffer := trim(both '|' from v_buffer);  
   elsif substr(v_buffer,1,1) = '&' then v_buffer := trim(both '&' from v_buffer);  
   elsif substr(v_buffer,1,1) = '~' then v_buffer := trim(both '~' from v_buffer);  
   elsif substr(v_buffer,1,1) = ',' then v_buffer := trim(both ',' from v_buffer);  
   elsif substr(v_buffer,1,1) = '=' then v_buffer := trim(both '=' from v_buffer);  
  end if;  
  -- -----------------------------------------  
  -- Clean search string from punctuation, garbage and DR engine keywords  
  v_buffer := trim(replace(v_buffer,'|', ' ')); -- Replace any search meta to space  
  v_buffer := trim(replace(v_buffer,'~', ' '));  
  v_buffer := trim(replace(v_buffer, '`', ' '));  
  v_buffer := trim(replace(v_buffer, '$', ' ')); -- STEM op  
  v_buffer := trim(replace(v_buffer, '>', ' ')); -- threshold op  
  v_buffer := trim(replace(v_buffer, '*', ' ')); -- weight op  
   
  v_buffer := trim(replace(v_buffer,':',' '));  
  v_buffer := trim(replace(v_buffer,';',' '));  
  v_buffer := trim(replace(v_buffer,':'',',' '));  
  v_buffer := trim(replace(v_buffer,'!',' ')); -- SOUNDEX op  
  v_buffer := trim(replace(v_buffer,'()','')); -- Suppress empty parenthes  
  v_buffer := trim(replace(v_buffer,'[]','')); -- Suppress empty parenthes  
  v_buffer := trim(replace(v_buffer,'{}','')); -- Suppress empty parenthes  
  v_buffer := trim(replace(v_buffer,'?',' ')); -- FUZZY equiv  
  v_buffer := trim(replace(v_buffer,'&',' ')); -- Must be before ',' threat  
  v_buffer := trim(replace(v_buffer,'+',' ')); -- ACCUM equiv  
  v_buffer := trim(replace(v_buffer,'\',' '));  
  --v_buffer := trim(replace(v_buffer,'-',' ')); -- This is printjoin char   
  v_buffer := trim(replace(v_buffer,',',' ')); -- Threat ','  
  v_buffer := trim(replace(v_buffer,'.',' '));  
  v_buffer := trim(replace(v_buffer,' and ',' ')); -- Remove logical ops  
  v_buffer := trim(replace(v_buffer,' or ',' ')); -- Remove logical ops  
  v_buffer := trim(replace(v_buffer,'""','" "')); -- Correct double quotation  
  -- -----------------------------------------  
   

Данные операции совершенно необходимы, например, очистка поисковой строки от мусора, избыточных пробелов, приведение строки к нижнему регистру, удаление символов, могущих быть интерпретированными как спецсимволы OracleText либо приводящих к ошибке выполнения запроса.

Хотя кажется, что это много кода, реально для выполнения данных операций требуется всего около 0.01 секунды в максимуме, на достаточно слабых процессорах.

Далее мы начинаем парсинг.

Мне хотелось реализовать функциональность поиска Google, когда часть запроса, взятая в кавычки, используется для поиска на безусловное соответствие. С этой целью сперва мы проверяем строку на наличие парных кавычек и выбираем части запроса в кавычках во внутренний буфер:

  -- Parse '"' pairs  
  v_quotes := length(v_buffer)-length(replace(v_buffer,'"', ''));  
  -- if there are quotes and the quotes are balanced, we'll extract that  
  -- terms "as is" and save them into a phrases array  
  if (v_quotes > 0 or mod(v_quotes,2) = 0) then  
   -- If this predicate be AND, odd '"' will be  
   -- ignored all '"' pairs in next parsing stage  
   v_temp_value2 := v_buffer;  
   for i in 1..v_quotes/2 loop  
    n := instr(v_temp_value2,'"');  
    v_temp_value := v_temp_value || substr(v_temp_value2,1,n-1);  
    v_temp_value2 := substr(v_temp_value2,n+1);  
    n := instr(v_temp_value2,'"');  
    v_token(i) := trim(substr(v_temp_value2,1,n-1));  
    v_temp_value2 := substr(v_temp_value2,n+1);  
   end loop;  
    v_temp_value := v_temp_value || v_temp_value2;  
  else  
   v_temp_value := v_buffer;  
  end if;  
   
  v_buffer := v_temp_value; -- Let's parse next...  
     
  -- dbms_output.put_line('Rest string: '||v_temp_value); -- Debug output  
   
  -- Threat single phrase exception  
  if trim(v_buffer) is null and v_token.count > 0 then  
   goto Final;  
  end if;  
   
   

Да, и обрабатываем случай, если в качестве запроса поиска мы имеем единственный токен в кавычках, в этом случае переходим сразу к финальному блоку парсера.

Основная часть парсера. Обрабатываем остаток строки, после того, как выбрали из нее все закавыченные токены для непосредственной передачи в OracleText:

  -- Parse and get tokens in the rest string ...  
  if instr(v_buffer,' ') > 0 then -- Look ' ' delimiters  
   if v_token.count = 0 then i := 1;  
   else i := v_token.last + 1; -- Continue parsing  
   end if;  
   while instr(v_buffer,' ') > 0 loop  
   v_token(i) := substr(v_buffer,1,instr(v_buffer,' ')-1);  
   i := i + 1; -- Increment counter  
   v_buffer := substr(v_buffer,instr(v_buffer,' ')+1);  
   v_buffer := trim(v_buffer);  
   end loop;  
   -- Get the last token  
   if substr(v_buffer,length(v_buffer))='\' or  
    substr(v_buffer,length(v_buffer))='?' or  
    substr(v_buffer,length(v_buffer))=';' then  
   v_buffer :=  
    substr(v_buffer,1,length(v_buffer)-1)||'\'||  
    substr(v_buffer,length(v_buffer));  
   end if;  
   v_token(i):=v_buffer;  
  else  
   -- Only one word was in search string  
   if substr(v_buffer,length(v_buffer))='\' or  
    substr(v_buffer,length(v_buffer))='?' or  
    substr(v_buffer,length(v_buffer))=';' then  
   v_buffer := substr(v_buffer,1,length(v_buffer)-1)||'\'||  
         substr(v_buffer,length(v_buffer));  
   end if;  
   v_token(1) := v_buffer;  
  end if;  
  -- Parsing complete!  
   

Завершающая стадия парсинга:

  <<Final>>  
  loop  
  if v_query_mode = 'keyword' then  
   v_ext1 := '';  
   v_ext2 := '';  
  else  
   v_ext1 :=   
   case substr(lower(p_query_opt),1,2)  
   when 'ab' then 'about('  
   when 'bt' then 'bt('  
   when 'nt' then 'nt('  
   when 'rt' then 'rt('  
   when 'sy' then 'syn('  
   end; -- End case  
   if v_exp_detail_on = ctx_api.c_exp_detail_off then  
   v_ext2 := v_expansion_level||v_thes_name||')';  
   end if;  
  end if;  
  -- Threat final string  
  v_buffer := null;  
  for j in v_token.first..v_token.last loop  
   if substr(v_token(j),1,1) = '(' then  
   -- If token is single word in () (i.e.(cat)),  
   -- we'll ignore this token  
   v_token(j) := null;  
   end if;  
   if instr(v_token(j),'(') > 0 then -- Threat parenthes in qualifiers  
   v_token(j) := replace(v_token(j),'(',' (');  
   end if;  
   v_op_fin := v_operator;  
   if v_buffer is null then v_op_fin := null; end if; -- Start line?  
   -- Skip empty token entries. This also remove tokens cutted with context refiner.  
   if v_token(j) is not null then  
   if v_exp_detail_on = ctx_api.c_exp_detail_off then  -- Expansion OFF  
    v_buffer := v_buffer||v_op_fin||v_ext1||'{'||del_delm(v_token(j))||'}'||v_ext2;  
   elsif v_exp_detail_on = ctx_api.c_exp_detail_on then -- Expansion ON  
    v_buffer := v_buffer||v_op_fin||v_ext1||'{'||del_delm(v_token(j))||'}'||','||v_exp_lvl(j)||v_thes_name||')';  
   end if;  
   end if;   
  end loop;  
  exit when 1=1; -- Only one labeled loop  
  end loop;  
   
  -- Finally release token tables memory  
  free_memory;  
      

Убираем пустые токены, если таковые вдруг образовались в процессе разбора, формируем финальную строку и освобождаем промежуточные таблицы.

Затем возвращаем результат и обрабатываем исключения, если таковые возникли:

  return v_buffer;  
   
  exception  
  when text_error then  
   free_memory; -- Release memory and exit if text_error exception occurs  
   raise_application_error(-20150,'Oracle Text error. Possible specified thesaurus not loaded.');  
  when others then   
   free_memory; -- When any others error, let's release memory  
   return null; -- and exit from function with null return  
  end search_string_parser; /* END MAIN BLOCK */  
   
   

Замечание. Из кода следует, что парсер выполняет несколько больше функций, чем может показаться на первый взгляд. Для чего здесь упоминается тезаурус и при чем он вообще, рассмотрим в следующих частях статьи.