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 un buen modelo de base de datos/búsqueda si quiero hacer todos los siguientes:

1. Etiquetas de almacenamiento en diversas entidades, (cómo las tablas es decir Entidad, etiqueta, y Entity_Tag normalizada?)
   • Búsqueda de elementos con etiquetas particulares
   • la construcción de una nube de etiquetas de todas las etiquetas que se aplican a un resultado de búsqueda en particular conjunto
   • cómo mostrar una lista de etiquetas para cada elemento en un resultado de búsqueda?

Tal vez tenga sentido para almacenar las etiquetas en una forma normalizada, sino también como una cadena delimitada por espacios a los efectos del # 2, # 4, # 3 y tal vez. ¿Pensamientos?

He oído decir que Stack Overflow utiliza Lucene para la búsqueda. ¿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 óptimo, pero tanto DotNetKicks como Kigg son implementaciones de clones de Digg de código abierto. Puede ver cómo están haciendo etiquetas y buscar.

Mis mejores conjeturas sin mucha deliberación :)

1. nunca como la idea de la serialización de valores múltiples en un solo campo, por lo que las cadenas delimitadas almacenados en un campo no apelan a mí ... podría 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.

Así que mi toma inicial es probablemente Entity -> EntityTag < - Tag.

2. Este enfoque hace que encontrar elementos a través de Tag sea muy 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. Todavía 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 las etiquetas en la base de datos imo.

Answer 2

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

Así que aquí voy de nuevo ...

En cuanto a desbordamiento de pila, resulta que utilizan SQL server 2005 full text search.

En cuanto a los proyectos OS recomendados por @Grant:

• DotNetKicks * utiliza la base de datos para el etiquetado 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 utiliza Linq-to-SQL para consultas de búsqueda y de etiquetas. Ambas consultas se unen a Historias-> StoryTags-> Etiquetas.
• Ambos proyectos tienen un enfoque 3-mesa para etiquetar como todo el mundo en general, parece recomendar

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

• How Do You Recommend Implementing Tags or Tagging?
• How to structure data for searchability?
• Database Design for Tagging

Lo que estoy haciendo actualmente para cada uno de los artículos que he mencionado:

1. En el PP, 3 mesas: Entidad, Tag, Entity_Tag. Yo uso la base de datos para:
   • acumulación de todo el sitio nubes de etiquetas
   • Navegar por etiqueta (es decir, las direcciones URL como de SO /questions/tagged/ASP.NET)
2. Para la búsqueda utilizo Lucene + NHibernate.Buscar
   • Las etiquetas se concat'd en un TagString que está indexado por Lucene
     • Así que tengo toda la potencia del motor de consultas de Lucene (Y/O/NO consultas)
     • puedo buscar texto y filtrar por etiquetas al mismo tiempo
     • el analizador de Lucene se fusiona palabras de mejores búsquedas de etiquetas (es decir, una búsqueda de etiquetas de "prueba" también encontrarán cosas etiquetado como "prueba")
   • Lucene devuelve un conjunto de resultados potencialmente enorme, que me paginate 20 resultados
   • Entonces NHibernate cargas de las Entidades resultado por Id, ya sea desde el caché Entidad
   • Por lo tanto, es muy posible DB o que un resultado de la búsqueda en 0 hits con el PP
3. no hacer esto todavía, pero creo que probablemente voy a tratar de encontrar una manera de construir la nube de etiquetas de la TagString en Lucene, en lugar de dar otro golpe DB
4. no lo ha hecho aún así, 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, que tengo que:

• Insertar nuevas etiquetas que no existen ya
• Insertar/Eliminar en la tabla EntityTag
• actualización Entidad .TagString
• actualizar 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 toda la entidad para actualizar TagString. No estoy entusiasmado con eso, pero creo que si lo hago en un hilo de fondo, estará bien.

El tiempo dirá ...