Szybka (er) metoda wyszukiwania wieloznacznego 250K + ciągi znaków

Question

Mam słownik języka angielskiego w bazie danych MySQL z nieco ponad 250 000 wpisów i używam prostego rubinowego interfejsu do wyszukiwania za pomocą symboli wieloznacznych na początku smyczki. Do tej pory robiłem to tak:

SELECT * FROM words WHERE word LIKE '_e__o' 

lub nawet

SELECT * FROM words WHERE word LIKE '____s' 

zawsze wiem dokładną długość słowa, ale wszyscy, ale pojedynczym znakiem są potencjalnie nieznane.

Jest wolniejszy niż melasa, około piętnaście razy wolniejszy niż podobne zapytanie bez wiodącej symbolu wieloznacznego, ponieważ nie można użyć indeksu dla kolumny.

Próbowałem kilka metod, aby zawęzić zakres wyszukiwania. Na przykład dodałem 26 dodatkowych kolumn zawierających liczbę liter każdego słowa i zawęzić wyszukiwanie przy użyciu tych pierwszych. Próbowałem również zwężania według długości słowa. Te metody nie robiły prawie żadnej różnicy, dzięki nieodłącznym nieskutecznym wyszukiwaniom prowadzącym do symboli wieloznacznych. Eksperymentowałem z instrukcją REGEXP, która jest jeszcze wolniejsza.

SQLite i PostgreSQL są tak samo ograniczone jak MySQL i choć mam ograniczone doświadczenie z systemami NoSQL, moje badania dają mi wrażenie, że wyróżniają się skalowalnością, a nie wydajnością, jakiej potrzebuję.

Moje pytanie brzmi: gdzie powinienem szukać rozwiązania? Czy powinienem nadal próbować znaleźć sposób na zoptymalizowanie moich zapytań lub dodać dodatkowe kolumny, które mogą zawęzić mój potencjalny zestaw rekordów? Czy istnieją systemy zaprojektowane specjalnie do szybkich poszukiwań w tym dziale?

Answer 1

Dzięki PostgreSQL 9.1 i rozszerzeniu pg_trgm można tworzyć indeksy, które można wykorzystać do podobnego warunku, który opisujesz.

Na przykład patrz tutaj: http://www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

zweryfikowany na stole z 300K rzędy pomocą LIKE '____1' i używa takiego wskaźnika. Zliczanie liczby wierszy w tym stole trwało około 120 ms (na starym laptopie). Co ciekawe, wyrażenie LIKE 'd___1' nie jest szybsze, ma mniej więcej taką samą prędkość.

To zależy również od liczby znaków w wyszukiwanym horyzoncie, długości, w jakiej się znajduje, tym wolniej będzie, o ile mogę to stwierdzić.

Musisz sprawdzić dane, jeśli wydajność jest akceptowalna.

Answer 2

Możesz spróbować użyć Apache Lucene, wyszukiwarki pełnotekstowej. Został stworzony, aby odpowiadać na takie zapytania, więc możesz mieć więcej szczęścia.

Wildcard searching with lucene.

Answer 3

Utwórz rozwiązanie w tablicy wyników pamięci: Możesz mieć posortowany stół dla każdej długości.

Następnie, aby dopasować, powiedz, że znasz czwartą i ósmą literę, zapętlaj wyrazy sprawdzając tylko każdą czwartą literę. Są one tej samej długości, więc będą szybkie. Tylko jeśli mecze listowe sprawdzają 8. list.

to brutalna siła, ale będzie szybka. Powiedzmy, że w najgorszym przypadku masz 50 000 8-literowych słów. To 50 000 porównań. zakładając, że problemy z czasem wykonania rubinowej pracy powinny być nadal: < 1sec.

Wymagana pamięć to 250k x 10. Tak więc 2,5 Meg.

Answer 4

Zakładam, że czas początkowo wprowadzony w celu wstawienia słów i ustawienia indeksowania jest nieistotny. Co więcej, nie aktualizowałbyś listy słów zbyt często, więc to w zasadzie statyczne dane.

Można spróbować podejścia takiego: -

• Od zawsze wiadomo, długość słowa, utworzyć tabelę zawierającą wszystkie słowa o długości 1, kolejny tabeli słowa długości 2 itd
• Podczas przeprowadzania zapytania wybierz z odpowiedniej tabeli na podstawie długości słowa. Nadal będzie trzeba wykonać pełne skanowanie tej tabeli.

Jeśli RDBMS na to pozwala, lepiej byłoby, gdybyś miał jedną tabelę i partycje według długości słowa.

Jeśli to nadal nie jest wystarczająco szybkie, możesz podzielić je według długości i znanej litery. Na przykład, możesz mieć tabelę zawierającą wszystkie 8 liter słowa zawierające "Z".

Gdy zapytasz, wiesz, że masz 8-literowe słowo zawierające "E" i "Z". Najpierw zapytaj słownik danych, aby zobaczyć, która litera jest najrzadsza w wyrazie 8-literowym, a następnie przeskanuj tę tabelę. Przez zapytanie do słownika danych rozumiem, czy tabela words_8E lub tabela words_8z ma najmniejszą liczbę rekordów.

chodzi Normal Form i Dobrej Praktyki

To nie jest coś takiego bym zazwyczaj zalecają podczas modelowania danych. W twoim przypadku przechowywanie całego słowa w kolumnie pojedynczego znaku nie jest w rzeczywistości 1st normal form. Dzieje się tak, ponieważ zależy ci na poszczególnych elementach w danym słowie. Biorąc pod uwagę twój przypadek użycia, słowo jest listą liter, a nie pojedynczym słowem. Jak zawsze, sposób modelowania zależy od tego, na czym Ci zależy.

Twoje zapytania sprawiają ci kłopoty, ponieważ nie są w pierwszej normalnej formie.

W pełni znormalizowany model tego problemu miałby dwie tabele: słowo (WordId PK) i WordLetter (WordId PK, Position PK, Letter). Następnie zapytałbyś o wszystkie słowa z wieloma GDZIE ISTNIEJSZYMI literą w odpowiedniej pozycji.

Chociaż nie jest to zgodne z teorią bazy danych, nie sądzę, aby to się udało.

Answer 5

Wszystko sprowadza się do indeksowania.

Można utworzyć tabelę jak:

create table letter_index (
    id integer not null primary key, 
    letter varchar(1), 
    position integer 
) 

create unique index letter_index_i1 (letter, position) 

create table letter_index_words (
    letter_index_id integer, 
    word_id integer 
) 

Wówczas indeks wszystkich wyrazów.

Jeśli chcesz listę wszystkich słów z „e” w 2. pozycji:

select words.* from words, letter_index_word liw, letter_index li 
where li.letter = 'e' and li.position = 2 
and liw.letter_index_id = li.id 
and words.id = liw.word_id 

Jeśli chcesz wszystkimi słowami z „e” w 2. pozycji, a „s” w piąte miejsce:

select words.* from words, letter_index_word liw, letter_index li 
where li.letter = 'e' and li.position = 2 
and liw.letter_index_id = li.id 
and words.id = liw.word_id 
and words.id in (
    select liw.word_id from letter_index_word liw, letter_index li 
    where li.letter = 's' and li.position = 5 
    and liw.letter_index_id = li.id 
) 

Można również uruchomić dwa proste zapytania i połączyć wyniki samodzielnie.

Oczywiście, po prostu buforowanie i powtarzanie listy w pamięci jest prawdopodobnie szybsze niż którekolwiek z tych. Ale nie na tyle szybko, aby być wartym załadowania listy 250K z DB za każdym razem.

Answer 6

To więcej ćwiczeń niż rzeczywistych rozwiązań. Pomysł polega na podzieleniu słów na postacie.

Umożliwia zaprojektowanie potrzebnej tabeli jako pierwszej. Zakładam, że Twój stół words ma kolumny word_id, word, size:

CREATE TABLE letter_search 
(word_id INT NOT NULL 
, position UNSIGNED TINYINT NOT NULL 
, letter CHAR(1) NOT NULL 
, PRIMARY KEY (word_id, position) 
, FOREIGN KEY (word_id) 
    REFERENCES words (word_id) 
     ON DELETE CASCADE 
     ON UPDATE CASCADE 
, INDEX position_letter_idx (position, letter) 
, INDEX letter_idx (letter) 
) ENGINE = InnoDB ; 

Będziemy potrzebować auxilary "Numery" tabeli:

CREATE TABLE num 
(i UNSIGNED TINYINT NOT NULL 
, PRIMARY KEY (i) 
) ; 

INSERT INTO num (i)    --- I suppose you don't have 
VALUES       --- words with 100 letters 
    (1), (2), ..., (100) ; 

Aby wypełnić naszą letter_search tabeli:

INSERT INTO letter_search 
    (word_id, position, letter) 
SELECT 
    w.word_id 
    , num.i 
    , SUBSTRING(w.word, num.i, 1) 
FROM 
    words AS w 
    JOIN 
    num 
     ON num.i <= w.size 

Wielkość z tej tabeli wyszukiwania będzie około 10 * 250K wierszy (gdzie 10, umieścić średnią wielkość słów).

---

Wreszcie, zapytanie:

SELECT * FROM words WHERE word LIKE '_e__o' 

zostanie zapisany jako:

SELECT w.* 
FROM 
    words AS w 
    JOIN 
    letter_search AS s2 
     ON (s2.position, s2.letter, s2.word_id) = (2, 'e', w.word_id) 
    JOIN 
    letter_search AS s5 
     ON (s5.position, s5.letter, s5.word_id) = (5, 'o', w.word_id) 
WHERE 
    w.size = 5 

Answer 7

Można indeks tej kwerendy w pełni, bez konieczności skanowania więcej niż rozmiar zestawu wyników który jest optymalny.

Tworzenie tabeli odnośników tak:

Table: lookup 
pattern  word_id 
_o_s_  1 
_ous_  1 
... 

których odesłano tabelę słowo:

Table: word 
word_id  word 
1   mouse 

umieścić wskaźnik na wzór i wykonanie select tak:

select w.word 
from lookup l, word w 
where l.pattern = '_ous_' and 
l.word_id = w.word_id; 

Oczywiście będziesz potrzebował małego skryptu ruby, aby stworzyć tabelę odnośników, w której wzór jest wszystkim możliwym wzorem każde słowo w słowniku. Innymi słowy wzory dla myszy będzie:

m____ 
mo___ 
mou__ 
mous_ 
mouse 
_o___ 
_ou__ 
... 

rubin, aby wygenerować wszystkie wzory na dane słowo może wyglądać tak:

def generate_patterns word 
    return [word, '_'] if word.size == 1 
    generate_patterns(word[1..-1]).map do |sub_word| 
    [word[0] + sub_word, '_' + sub_word] 
    end.flatten 
end 

Na przykład:

> generate_patterns 'mouse' 
mouse 
_ouse 
m_use 
__use 
mo_se 
_o_se 
m__se 
___se 
mou_e 
_ou_e 
m_u_e 
__u_e 
mo__e 
_o__e 
m___e 
____e 
mous_ 
_ous_ 
m_us_ 
__us_ 
mo_s_ 
_o_s_ 
m__s_ 
___s_ 
mou__ 
_ou__ 
m_u__ 
__u__ 
mo___ 
_o___ 
m____ 
_____ 

Answer 8

Szybkim sposobem na obniżenie go o współczynnik równy 10 jest utworzenie kolumny dla długości łańcucha, umieszczenie na niej indeksu i użycie go w klauzuli where.