Metodo rapido (er) per la ricerca con caratteri jolly di stringhe 250K +

Question

Ho un dizionario inglese in un database MySQL con oltre 250.000 voci e sto usando un semplice front-end ruby ​​per cercarlo utilizzando i caratteri jolly all'inizio del stringhe. Finora ho fatto in questo modo:

SELECT * FROM words WHERE word LIKE '_e__o' 

o anche

SELECT * FROM words WHERE word LIKE '____s' 

So sempre la lunghezza esatta della parola, ma tutti, ma un singolo carattere sono potenzialmente sconosciuto.

Questo è più lento di melassa, circa quindici volte più lento di una query simile senza il carattere jolly iniziale perché non è possibile utilizzare l'indice per la colonna.

Ho provato alcuni metodi per restringere l'ambito della ricerca. Ad esempio, ho aggiunto 26 colonne aggiuntive contenenti i conteggi delle singole lettere di ogni parola e ristretto la ricerca utilizzando quelli per primi. Ho anche provato a restringere in base alla lunghezza delle parole. Questi metodi non hanno fatto praticamente alcuna differenza, grazie all'inefficienza intrinseca delle ricerche con caratteri jolly principali. Ho sperimentato la dichiarazione REGEXP, che è ancora più lenta.

SQLite e PostgreSQL sono limitati come MySQL e, sebbene io abbia esperienza limitata con i sistemi NoSQL, la mia ricerca mi dà l'impressione che eccellano in termini di scalabilità, non di prestazioni del tipo di cui ho bisogno.

La mia domanda quindi, è dove dovrei cercare una soluzione? Devo continuare a cercare un modo per ottimizzare le mie query o aggiungere colonne supplementari che possano restringere il mio potenziale recordset? Esistono sistemi progettati specificamente per eseguire una ricerca rapida con caratteri jolly in questo filone?

Answer 1

Con PostgreSQL 9.1 e l'estensione pg_trgm è possibile creare indici che sono utilizzabili per una condizione simile che si sta descrivendo.

Per un esempio vedere qui: http://www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

ho verificato su un tavolo con 300k righe utilizzando LIKE '____1' e si fa uso di tale indice. Ci sono voluti circa 120ms per contare il numero di righe in quella tabella (su un vecchio laptop). Interessante l'espressione LIKE 'd___1' non è più veloce, si tratta della stessa velocità.

Dipende anche dal numero di caratteri nel termine di ricerca, il longe diventa, più lento sarà per quanto posso dire.

È necessario verificare con i dati se le prestazioni sono accettabili.

Answer 2

Puoi provare a utilizzare Apache Lucene, un motore di ricerca completo. È stato creato per rispondere a domande come questa, quindi potresti avere più fortuna.

Wildcard searching with lucene.

Answer 3

Creare una soluzione di tabella di ricerca in memoria: è possibile avere una tabella ordinata per ciascuna lunghezza.

Quindi, per corrispondere, diciamo di conoscere la 4a e la 8a lettera, scorrere tra le parole controllando solo ogni quarta lettera. Sono tutti della stessa lunghezza, quindi sarà veloce. Solo se la corrispondenza delle lettere controlla l'ottava lettera.

è forza bruta, ma sarà veloce. Diciamo il caso peggiore avete 50.000 parole di 8 lettere. Ecco 50.000 confronti. assumendo i problemi perf perfetti di run time dovrebbe essere < 1sec.

La memoria richiesta sarebbe 250k x 10. Quindi 2,5 Meg.

Answer 4

Suppongo che il tempo inizialmente impiegato per inserire le parole e impostare l'indicizzazione sia irrilevante. Inoltre, non si aggiornerebbero molto spesso l'elenco di parole, quindi sono fondamentalmente dati statici.

Si potrebbe provare un approccio come questo: -

• Poiché si sa sempre la lunghezza della parola, creare una tabella che contiene tutte le parole di lunghezza 1, un altro tavolo di parole di lunghezza 2, ecc
• Quando conduci una query, seleziona la tabella appropriata in base alla lunghezza della parola. Dovrà comunque eseguire una scansione completa di quel tavolo.

Se RDBMS lo consente, con una singola tabella e partizioni si preferirebbe la lunghezza della parola.

Se non è ancora abbastanza veloce, è possibile dividerlo ulteriormente per lunghezza e lettera nota. Ad esempio, potresti avere una tabella che elenca tutte le 8 lettere che contengono una "Z".

Quando si interroga, si sa di avere una parola di 8 lettere contenente "E" e "Z". Per prima cosa, interrogare il dizionario dei dati per vedere quale lettera è più rara in 8 lettere e poi scansionare quella tabella. Eseguendo una query sul dizionario dei dati, intendo capire se la tabella words_8E o la tabella words_8z ha il numero minimo di record.

Per quanto riguarda forme normali e buone pratiche

Questo non è il tipo di cosa che di solito raccomandare durante la modellazione dei dati. Nel tuo caso particolare, la memorizzazione dell'intera parola in una singola colonna di caratteri non è in realtà in 1st normal form. Questo perché ti preoccupi dei singoli elementi all'interno della parola. Dato il tuo caso d'uso, una parola è una lista di lettere che una singola parola. Come sempre, come modellare dipende da cosa ti interessa.

Le tue domande ti danno problemi perché non è nella prima forma normale.

Il modello completamente normalizzato per questo problema avrebbe due tabelle: word (WordId PK) e WordLetter (WordId PK, Position PK, Letter). Dovresti quindi eseguire una query per tutte le parole con più DOVE ESISTE una lettera nella posizione appropriata.

Sebbene corretto secondo la teoria del database, non penso che questo si comporterà bene.

Answer 5

Tutto si riduce all'indicizzazione.

È possibile creare tavolo come:

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 
) 

Poi indice tutte le tue parole.

Se si desidera un elenco di tutte le parole, con una 'e' in 2 ° posizione:

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 

Se si desidera che tutte le parole con 'e' nel 2 ° posizione e 's' in la quinta posizione:

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 
) 

Oppure puoi eseguire due semplici query e unire i risultati tu stesso.

Ovviamente, la semplice memorizzazione nella cache e l'iterazione attraverso l'elenco in memoria è probabilmente più veloce di qualsiasi di queste. Ma non abbastanza veloce da valere la pena di caricare ogni volta la lista dei 250K dal DB.

Answer 6

Questo è più di un esercizio che una soluzione di vita reale. L'idea è di dividere le parole in caratteri.

Consente di progettare prima la tabella necessaria. Presumo vostro tavolo words ha le colonne 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 ; 

Avremo bisogno di una tabella "numeri" AUSILIARI:

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) ; 

per popolare la letter_search tavolo:

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 

Le dimensioni di questa tabella di ricerca saranno circa 10 * 250K righe (dove 10, metti la dimensione media delle tue parole).

---

Infine, la query:

SELECT * FROM words WHERE word LIKE '_e__o' 

sarà scritto come:

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

È possibile indicizzare questa query completamente senza dover eseguire la scansione di più di quanto le dimensioni del set di risultati che è ottimale

Creare una tabella di ricerca in questo modo:

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

che fa riferimento la tabella di Word:

Table: word 
word_id  word 
1   mouse 

Mettere un indice sul modello ed eseguire una selezione in questo modo:

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

Ovviamente avrai bisogno di un piccolo script rubino per creare questa tabella di ricerca in cui lo schema è per ogni modello possibile ogni parola nel dizionario In altre parole, i modelli per il mouse potrebbe essere:

m____ 
mo___ 
mou__ 
mous_ 
mouse 
_o___ 
_ou__ 
... 

Il rubino di generare tutti i modelli di una determinata parola potrebbe apparire come:

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 

Ad esempio:

> 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

Un rapido per ridurlo di un fattore pari a 10 è necessario creare una colonna per la lunghezza della stringa, inserirvi un indice e usarla nella clausola where.