Método rápido (er) para búsqueda de comodines de 250K + cadenas

Question

Tengo un diccionario de inglés en una base de datos MySQL con poco más de 250K entradas, y estoy usando un front-end simple de ruby ​​para buscarlo con comodines al comienzo de la instrumentos de cuerda. Hasta ahora he estado haciendo de esta manera:

SELECT * FROM words WHERE word LIKE '_e__o' 

o incluso

SELECT * FROM words WHERE word LIKE '____s' 

Siempre sé la longitud exacta de la palabra, pero todos excepto un único carácter potencialmente desconocida.

Esto es más lento que melaza, unas quince veces más lento que una consulta similar sin el comodín principal porque el índice de la columna no se puede utilizar.

He intentado algunos métodos para limitar el alcance de la búsqueda. Por ejemplo, agregué 26 columnas adicionales que contienen los recuentos de letras individuales de cada palabra y estrecho la búsqueda usando los primeros. También he intentado reducir el tamaño de la palabra. Estos métodos casi no hicieron diferencia, gracias a la ineficacia inherente de las búsquedas de comodines. He experimentado con la declaración REGEXP, que es incluso más lenta.

SQLite y PostgreSQL son tan limitados como MySQL, y aunque tengo una experiencia limitada con los sistemas NoSQL, mi investigación me da la impresión de que sobresalen en la escalabilidad, no en el rendimiento del tipo que necesito.

Mi pregunta es, entonces, ¿dónde debo buscar una solución? ¿Debo continuar tratando de encontrar una forma de optimizar mis consultas o agregar columnas suplementarias que puedan reducir mi posible conjunto de registros? ¿Hay sistemas diseñados específicamente para lograr una búsqueda rápida de comodines en esta línea?

Answer 1

Con PostgreSQL 9.1 y la extensión pg_trgm puede crear índices que se puedan usar para una condición similar a la que está describiendo.

Para ver un ejemplo aquí: http://www.depesz.com/2011/02/19/waiting-for-9-1-faster-likeilike/

verifiqué sobre una mesa con 300k filas usando LIKE '____1' y no hace uso de dicho índice. Tomó aproximadamente 120ms contar el número de filas en esa tabla (en una computadora portátil vieja). Es bastante interesante que la expresión LIKE 'd___1' no sea más rápida, tiene más o menos la misma velocidad.

También depende del número de caracteres en el término de búsqueda, cuanto más tiempo pasa, más lento será lo que yo sepa.

Debería verificar con sus datos si el rendimiento es aceptable.

Answer 2

Puede probar el uso de Apache Lucene, un motor de búsqueda de texto completo. Fue hecho para responder consultas como esta, por lo que podría tener más suerte.

Wildcard searching with lucene.

Answer 3

Crear una solución de tabla de búsqueda en memoria: puede tener una tabla ordenada para cada longitud.

Luego, para que coincida, digamos que conozca la 4ª y la 8ª letra, recorra las palabras marcando solo cada 4ª letra. Todos son del mismo largo, por lo que será rápido. Solo si la letra coincide, verifique la octava letra.

es fuerza bruta, pero será rápido. Digamos que en el peor de los casos tienes 50,000 palabras de 8 letras. Eso es 50,000 comparaciones. asumiendo ruby ​​run time perf issues aún debería ser < 1sec.

La memoria requerida sería de 250k x 10. Entonces 2.5 Meg.

Answer 4

Supongo que el tiempo inicialmente requerido para insertar las palabras y configurar su indexación es inconsecuente. Además, no harías actualizaciones a la lista de palabras muy a menudo, así que básicamente son datos estáticos.

Usted podría intentar un enfoque como este: -

• Ya que siempre sabe la longitud de la palabra, crear una tabla que contiene todas las palabras de longitud 1, otra tabla de palabras de longitud 2, etc.
• Cuando realiza una consulta, seleccione la tabla adecuada en función de la longitud de la palabra. Todavía será necesario hacer un análisis completo de esa tabla.

Si RDBMS lo permite, sería mejor con una sola tabla y particiones por longitud de palabra.

Si aún no es lo suficientemente rápido, puede dividirlo por longitud y letra conocida. Por ejemplo, podría tener una tabla que enumere las 8 letras con una "Z".

Cuando realiza una consulta, sabe que tiene una palabra de 8 letras que contiene una "E" y una "Z". Primero consulta el diccionario de datos para ver qué letra es más rara en palabras de 8 letras, y luego escanea esa tabla. Al consultar el diccionario de datos, me refiero a si la tabla words_8E o la tabla words_8z tiene el menor número de registros.

En cuanto a las formas normales y Buenas Prácticas

Este no es el tipo de cosa que recomendaría típicamente cuando el modelado de datos. En su caso particular, almacenar la palabra completa en una columna de un solo carácter no está realmente en 1st normal form. Esto es porque te importan los elementos individuales dentro de la palabra. Dado su caso de uso, una palabra es una lista de letras que una sola palabra. Como siempre, cómo modelar depende de lo que te importa.

Sus consultas le causan problemas porque no están en la primera forma normal.

El modelo completamente normalizado para este problema tendría dos tablas: word (WordId PK) y WordLetter (WordId PK, Position PK, Letter). A continuación, consulta todas las palabras con DONDE EXISTE una letra en la posición adecuada.

Aunque es correcto según la teoría de la base de datos, no creo que tenga un buen rendimiento.

Answer 5

Todo se reduce a la indexación.

Puede crear mesa como:

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 
) 

Entonces índice de todas sus palabras.

Si desea una lista de todas las palabras con una 'e' en la segunda posición:

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 

Si desea que todas las palabras con 'e' en la segunda posición, y 's' en la quinta posición:

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 
) 

O puede ejecutar dos consultas simples y combinar los resultados usted mismo.

Por supuesto, simplemente el almacenamiento en caché y la iteración a través de la lista en la memoria es probablemente más rápido que cualquiera de estos. Pero no lo suficientemente rápido como para valer la pena cargar la lista de 250K desde el DB cada vez.

Answer 6

Esto es más un ejercicio que una solución de la vida real. La idea es dividir las palabras en caracteres.

Permite diseñar primero la tabla que se necesita. Asumo la mesa words tiene las columnas 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 ; 

Tendremos un "números" auxilary tabla:

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

para poblar nuestra letter_search tabla:

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 

El tamaño de esta tabla de búsqueda será de aproximadamente 10 * 250K filas (donde 10, pon el tamaño promedio de tus palabras).

---

Por último, la consulta:

SELECT * FROM words WHERE word LIKE '_e__o' 

será escrito como:

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

Puede indexar esta consulta totalmente sin tener que escanear más de lo que el tamaño del conjunto de resultados que es óptimo

Crear una tabla de búsqueda de este modo:

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

que hace referencia a la tabla de Word:

Table: word 
word_id  word 
1   mouse 

Deja un índice en el patrón y ejecutar un selecto así:

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

Por supuesto, necesitará un pequeño script de ruby ​​para crear esta tabla de búsqueda donde el patrón es cada patrón posible para cada palabra en el diccionario. En otras palabras, las pautas de ratón serían:

m____ 
mo___ 
mou__ 
mous_ 
mouse 
_o___ 
_ou__ 
... 

El rubí para generar todos los patrones de una palabra dada podría parecerse a:

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 

Por ejemplo:

> 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

Una rápida La manera de bajarlo por un factor de 10 o más es crear una columna para la longitud de la cadena, poner un índice sobre ella y usarla en la cláusula where.