database-design - fulltext - php mysql full text search

Arquitectura de datos óptima para etiquetado, nubes y búsqueda(como StackOverflow)

Question

Me encantaría saber cómo está estructurado el etiquetado y la búsqueda de Stack Overflow, porque parece funcionar bastante bien.

¿Qué es una buena base de datos / modelo de búsqueda si quiero hacer todo lo siguiente?

1. Almacenamiento de etiquetas en varias entidades (¿cómo se normalizan las tablas Entity, Tag y Entity_Tag?)
   • Búsqueda de artículos con etiquetas particulares
   • Creación de una nube de etiquetas de todas las etiquetas que se aplican a un determinado conjunto de resultados de búsqueda
   • ¿Cómo mostrar una lista de etiquetas para cada artículo en un resultado de búsqueda?

Quizás tenga sentido almacenar las etiquetas en una forma normalizada, pero también como una cadena delimitada por espacios para los propósitos de # 2, # 4 y quizás # 3. ¿Pensamientos?

He oído decir que Stack Overflow usa Lucene para buscar. ¿Es eso cierto? He escuchado un par de podcasts sobre la optimización de SQL, pero nada sobre Lucene. Si usan Lucene, me pregunto qué parte del resultado de la búsqueda proviene de Lucene, y si la nube de etiquetas "drill-down" proviene de Lucene.

Answer 1

No sé si califican como óptimos, pero tanto DotNetKicks como Kigg son implementaciones de clones Digg de código abierto. Puede ver cómo están haciendo etiquetas y buscar.

Mis mejores conjeturas sin mucha deliberación :)

1. Nunca me gusta la idea de serializar múltiples valores en un solo campo, por lo que las cadenas delimitadas almacenadas en un campo no me atraen ... podrían funcionar para rutas de adyacencia con árboles, pero esas siempre están ordenadas y no es necesario que las etiquetas estén. Esto parece que gravaría el trabajo del operador LIKE que podría hacer para encontrarlos.

Entonces mi toma inicial probablemente sea Entity -> Entity Tag <- Tag.

2. Este enfoque hace que encontrar elementos a través de Tag sea bastante fácil, únase a través de EntityTag, llámelo un día.

3. Necesita una operación secundaria aquí para seleccionar las etiquetas distintas para el conjunto de resultados. Entonces a) tira del conjunto de resultados, b.) Normaliza el espacio de etiquetas. Creo que haces esto sin importar cuál sea la respuesta al # 1: incluso rellenar etiquetas en un campo generará etiquetas duplicadas (y tienes que deserializarlas para realizar esta operación, por lo tanto, más trabajo, otro argumento para una relación completa enfoque).

4. Aún es fácil. Aquí hay un área donde el enfoque serializado funciona mejor. No es necesario unirse a las etiquetas de los niños, está ahí mismo en la Entidad. Dicho esto, sacar las etiquetas 0..n a través de la combinación de dos tablas no parece demasiado difícil para mí. Si está hablando de consideraciones de rendimiento, compile primero la normalización y luego optimícela a través de caché o denorm.

La otra opción es "hacer ambas cosas". Esto se siente como una optimización prematura, pero puede hacer el enfoque normalizado completo para respaldar cualquier operación centrada en etiquetas y serializar si persiste para tener una versión desnormalizada allí mismo en la Entidad. Un poco más de trabajo, un poco de potencial para desconectarse si no está completamente cubierto, pero lo mejor de ambos mundos si hay limitaciones reales para la forma totalmente normalizada en sus casos de uso.

Lucene también es interesante, puede declarar metadatos específicos en los índices IIRC, por lo que podría aprovechar potencialmente la búsqueda de etiquetas de esta manera también. Mi sospecha es que si vas demasiado lejos en este camino, terminas teniendo algunas desconexiones entre lo que almacenas en la base de datos y el índice en algún momento. Puedo hablar favorablemente sobre Lucene, es muy capaz y fácil de usar, creo. Text lo usó para sus capacidades de búsqueda y admitió todos los weblogs.asp.net antes de cambiar a Community Server. Me quedaría con él para la búsqueda de texto completo si MSSQL no aparece en la imagen / es suficiente, resuelva los problemas de la etiqueta en la base de datos imo.

Answer 2

Wow, acabo de escribir una gran publicación y SO se atragantó y se colgó de ella, y cuando pulsé el botón Atrás para volver a enviarla, el editor de marcas estaba vacío. aaargh.

Así que aquí voy de nuevo ...

En cuanto al desbordamiento de pila, resulta que utilizan la búsqueda de texto completo de SQL Server 2005 .

En cuanto a los proyectos de SO recomendados por @Grant:

• * DotNetKicks usa el DB para etiquetar y Lucene para la búsqueda de texto completo. Parece que no hay forma de combinar una búsqueda de texto completo con una búsqueda de etiqueta
• Kigg usa Linq-to-SQL para consultas de búsqueda y de etiquetas. Ambas consultas se unen a Historias-> StoryTags-> Etiquetas.
• Ambos proyectos tienen un enfoque de 3 tablas para etiquetar ya que todo el mundo parece recomendar

También encontré algunas otras preguntas sobre SO que me había perdido antes:

• ¿Cómo se recomiendan la implementación de etiquetas o el etiquetado?
• ¿Cómo estructurar datos para búsqueda?
• Diseño de base de datos para etiquetado

Lo que estoy haciendo actualmente por cada uno de los elementos que mencioné:

1. En el DB, 3 tablas: Entity, Tag, Entity_Tag. Yo uso el DB para:
   • Crear nubes de etiquetas en todo el sitio
   • navegar por etiqueta (es decir, URL como SO /questions/tagged/ASP.NET )
2. Para la búsqueda uso Lucene + NHibernate.Search
   • Las etiquetas se combinan en un TagString indexado por Lucene
     • Así que tengo toda la potencia del motor de consultas Lucene (consultas AND / OR / NOT)
     • Puedo buscar texto y filtrar por etiquetas al mismo tiempo
     • El analizador de Lucene combina las palabras para una mejor búsqueda de etiquetas (es decir, una búsqueda de etiquetas para "prueba" también encontrará cosas etiquetadas como "prueba")
   • Lucene devuelve un conjunto de resultados potencialmente enorme, que voy paginando a 20 resultados
   • Luego, NHibernate carga las Id. De resultado por Id, ya sea desde la base de datos o la memoria caché de entidad
   • Por lo tanto, es muy posible que una búsqueda genere 0 hits en la base de datos
3. Todavía no estoy haciendo esto, pero creo que probablemente intentaré encontrar la forma de construir la nube de etiquetas desde TagString en Lucene, en lugar de tomar otro golpe en la base de datos.
4. Todavía no he hecho esto, pero probablemente almaceno TagString en el DB para que pueda mostrar la lista de etiquetas de una entidad sin tener que hacer 2 uniones más.

Esto significa que cada vez que se modifican las etiquetas de una Entidad, tengo que:

• Inserta cualquier etiqueta nueva que no exista
• Insertar / Eliminar de la tabla EntityTag
• Actualizar Entity.TagString
• Actualice el índice de Lucene para la Entidad

Dado que la proporción de lecturas y escrituras es muy grande en mi aplicación, creo que estoy de acuerdo con esto. La única parte que consume mucho tiempo es la indexación de Lucene, porque Lucene solo puede insertar y eliminar de su índice, por lo que tengo que volver a indexar la entidad completa para actualizar TagString. No estoy entusiasmado con eso, pero creo que si lo hago en un hilo de fondo, estará bien.

El tiempo dirá...