Accelerare la ricerca di stringhe regolari in MongoDB

Question

Sto provando a utilizzare MongoDB per implementare un dizionario di lingua naturale. Ho una collezione di lessemi, ognuno dei quali ha un numero di wordforms come documenti secondari. Questo è ciò che un singolo lessema assomiglia:

{ 
    "_id" : ObjectId("51ecff7ee36f2317c9000000"), 
    "pos" : "N", 
    "lemma" : "skrun", 
    "gloss" : "screw", 
    "wordforms" : [ 
     { 
      "number" : "sg", 
      "surface_form" : "skrun", 
      "phonetic" : "ˈskruːn", 
      "gender" : "m" 
     }, 
     { 
      "number" : "pl", 
      "surface_form" : "skrejjen", 
      "phonetic" : "'skrɛjjɛn", 
      "pattern" : "CCCVCCVC" 
     } 
    ], 
    "source" : "Mayer2013" 
} 

Attualmente ho una collezione di circa 4000 lessemi, e ciascuno di questi ha, in media, una lista di alcuni 1000 wordforms (piuttosto che semplicemente 2 di cui sopra). Ciò significa che ho affettivamente 4.000.000 forme di parole uniche nella raccolta e devo essere in grado di cercare attraverso di loro in un ragionevole lasso di tempo.

Una query normale sarebbe simile a questa:

db.lexemes.find({"wordforms.surface_form":"skrejjen"}) 

Ho un indice su wordforms.surface_form, e questa ricerca è molto veloce. Tuttavia, se desidero avere caratteri jolly nella mia ricerca, la performance è abissale. Ad esempio:

db.lexemes.find({"wordforms.surface_form":/skrej/}) 

richiede più di 5 minuti (a quel punto ho rinunciato ad aspettare). Come accennato a in this question, la ricerca di espressioni regolari sugli indici è nota per essere negativa. So che aggiungendo il^anchor in regex cerca helps a lot, ma limita anche severamente le mie capacità di ricerca. Anche se sono disposto a fare questo sacrificio, ho notato che i tempi di risposta possono variare molto a seconda della regex. La query

db.lexemes.find({"wordforms.surface_form":/^s/}) 

Takes 35s per completare.

I migliori risultati che ho avuto finora sono stati quando ho spento l'indice usando hint. In questo caso, le cose sembrano migliorare notevolmente. Questa query:

db.lexemes.find({"wordforms.surface_form":/skrej/}).hint('_id_') 

richiede circa 3 secondi per completare.

La mia domanda è, c'è qualcos'altro che posso fare per migliorare questi tempi di ricerca? Così come sono, sono ancora un po 'lenti e sto già pensando di migrare a MySQL nella speranza di ottenere prestazioni. Ma mi piacerebbe davvero mantenere la flessibilità di Mongo ed evitare la noiosa normalizzazione in un RDBMS. Eventuali suggerimenti? Pensi che mi imbatterò in qualche lentezza indipendentemente dal motore DB, con questa quantità di dati testuali?

Conosco la nuova funzionalità di text search di Mongo, ma i vantaggi di questo (tokenizzazione e derivazione) non sono rilevanti nel mio caso (per non dire che la mia lingua non è supportata). Non è chiaro se la ricerca di testo è in realtà più veloce rispetto all'utilizzo di espressioni regolari comunque.

Answer 1

Come suggerito da Derick, ho refactoring i dati nel mio database in modo tale che non ho "wordforms" come una collezione piuttosto che come documenti secondari sotto "lessemi". I risultati erano in effetti migliori! Ecco alcuni confronti di velocità. L'ultimo esempio utilizzando hint è intenzionalmente bypassando gli indici su surface_form, che nel vecchio schema era effettivamente più veloce.

Vecchio schema (vedi original question)

Query                Avg. Time 
db.lexemes.find({"wordforms.surface_form":"skrun"})    0s 
db.lexemes.find({"wordforms.surface_form":/^skr/})     1.0s 
db.lexemes.find({"wordforms.surface_form":/skru/})     > 3mins ! 
db.lexemes.find({"wordforms.surface_form":/skru/}).hint('_id_') 2.8s 

Nuovo schema di (vedi Derick's answer)

Query                Avg. Time 
db.wordforms.find({"surface_form":"skrun"})      0s 
db.wordforms.find({"surface_form":/^skr/})       0.001s 
db.wordforms.find({"surface_form":/skru/})       1.4s 
db.wordforms.find({"surface_form":/skru/}).hint('_id_')   3.0s 

Per me questo è abbastanza buona evidenza che uno schema refactoring dovrebbe rendere la ricerca più veloce, e vale i dati ridondanti (o richiesto un join aggiuntivo).

Answer 2

Una possibilità sarebbe quella di memorizzare tutte le varianti che si pensa possano essere utili come un elemento dell'array - non sono sicuro che sia possibile!

{ 
     "number" : "pl", 
     "surface_form" : "skrejjen", 
     "surface_forms: [ "skrej", "skre" ], 
     "phonetic" : "'skrɛjjɛn", 
     "pattern" : "CCCVCCVC" 
    } 

Probabilmente suggerisco anche di non memorizzare 1000 forme di parole con ogni parola, ma girarle per avere documenti più piccoli.Il più piccolo dei documenti sono, meno MongoDB avrebbe dovuto leggere in memoria per ogni ricerca (fino a quando le condizioni di ricerca non richiedono una scansione completa del corso):

{ 
    "word": { 
     "pos" : "N", 
     "lemma" : "skrun", 
     "gloss" : "screw", 
    }, 
    "form" : { 
     "number" : "sg", 
     "surface_form" : "skrun", 
     "phonetic" : "ˈskruːn", 
     "gender" : "m" 
    }, 
    "source" : "Mayer2013" 
} 

{ 
    "word": { 
     "pos" : "N", 
     "lemma" : "skrun", 
     "gloss" : "screw", 
    }, 
    "form" : { 
     "number" : "pl", 
     "surface_form" : "skrejjen", 
     "phonetic" : "'skrɛjjɛn", 
     "pattern" : "CCCVCCVC" 
    }, 
    "source" : "Mayer2013" 
} 

Dubito anche che MySQL sarebbe si sta comportando meglio qui con la ricerca di forme di parole casuali poichè dovrà fare una scansione completa della tabella proprio come sarebbe MongoDB. L'unica cosa che potrebbe aiutare c'è una cache delle query - ma questo è qualcosa che si potrebbe costruire nella vostra ricerca UI/API nell'applicazione abbastanza facilmente, naturalmente.