Almacenamiento de enteros sin signo de 64 bits en bases de datos SQLite, por diversión y beneficio

vie 22 abril 2022

Por C. Titus Brown

En la ciencia.

Etiquetas: Sourmashsqlite

El problema: almacenar y consultando muchos enteros sin signo de 64 bits

Durante los últimos seis años, nos hemos metido en un agujero de conejo con la búsqueda de secuencias basada en hashing, usando un MinHash-enfoque derivado llamado FracMinHash. (Puede leer más sobre FracMinHash aquípero es esencialmente una versión de fondo de ModHash.) Todo esto está implementado en el software sourmashun conjunto de herramientas de bioinformática de línea de comandos basado en Python y Rust.

La idea básica es que tomamos largas secuencias de ADN, extraemos subsecuencias de una longitud fija (digamos k=31), las trituramos y luego las esbozamos conservando solo aquellas que caen por debajo de cierto valor de umbral. Luego buscamos coincidencias entre bocetos en función del número de hashes superpuestos. Este es un proxy para el número de subsecuencias superpuestas k = 31, que a su vez se puede convertir en varias métricas de similitud de secuencia.

La escala de los problemas que estamos abordando es bastante grande. Como ejemplo, tenemos una base de datos (bacteria Genbank) con 1,15 millones de cubos de hash, que contienen un total de 4600 millones de hash en estos cubos (lo que representa aproximadamente 4,6 billones de k-mers originales). Por lo tanto, debemos hacer cosas moderadamente inteligentes para almacenarlos y buscarlos rápidamente.

Ya tenemos una variedad de formatos para almacenar y consultar colecciones de bocetos, incluidos archivos zip directos que contienen bocetos serializados en JSON, un formato personalizado basado en disco Secuencia de árboles en flor, y un índice invertido que vive en la memoria. El índice invertido resulta ser rápido una vez cargado, pero la serialización no es tan buena y el consumo de memoria es muy alto. ¡Esto es algo que quería arreglar!

Desde hace mucho tiempo me encanta SQLite, el diminuto motor de base de datos incrustado que es ridículamente rápido, y decidí descubrir cómo almacenar y consulta nuestros bocetos en SQLite.

Uso de SQLite para almacenar enteros sin signo de 64 bits: un primer intento

El desafío al que me enfrenté aquí fue que nuestros bocetos se componen de enteros sin signo de 64 bits y SQLite no almacena Ints sin firmar de 64 bits de forma nativa. ¡Pero esto es exactamente lo que necesitaba!

Introduzca convertidores de tipo! Encontré dos recursos realmente buenos para convertir automáticamente unidades de 64 bits en tipos de datos que SQLite podría manejar: esta publicación de stackoverflow, «Python int demasiado grande para convertir a SQLite INTEGER»y esta genial tutorial de wellsr.com, Adaptación y conversión de tipos de datos SQLite para Python.

En resumen, pasé el código de la respuesta de stackoverflow para hacer lo siguiente:

  • escriba una función que, para cualquier valor hash mayor que 2**63-1, convierta números en una cadena hexadecimal;
  • escribe la función opuesta que convierte las cadenas hexadecimales en números;
  • registre estas funciones como adaptadores en un tipo de datos SQLite para que se ejecuten automáticamente para cada columna de ese tipo.

Esto funciona porque SQLite tiene un sistema de tipeo interno realmente flexible donde puede almacenar básicamente cualquier cosa como una cadena, sin importar el tipo de columna oficial.

El código de Python se ve así:

MAX_SQLITE_INT = 2 ** 63 - 1
sqlite3.register_adapter(
    int, lambda x: hex(x) if x > MAX_SQLITE_INT else x)
sqlite3.register_converter(
    'integer', lambda b: int(b, 16 if b[:2] == b'0x' else 10))

y cuando se conecta a la base de datos, puede decirle a SQLite que preste atención a esos adaptadores así:

conn = sqlite3.connect(dbfile,
    detect_types=sqlite3.PARSE_DECLTYPES)

Luego defines tus tablas en SQLite,

CREATE TABLE IF NOT EXISTS hashes
    (hashval INTEGER NOT NULL,
    sketch_id INTEGER NOT NULL,
    FOREIGN KEY (sketch_id) REFERENCES sketches (id))

CREATE TABLE IF NOT EXISTS sketches
  (id INTEGER PRIMARY KEY,
   name TEXT,
   ...)

y puede hacer todas las consultas que desee, y los números enteros grandes se convertirán en cadenas hexadecimales, y la vida es buena. ¿Derecha?

¡Este código realmente funcionó bien! Excepto por un problema.

Fue muy lento. Una clave para hacer que las bases de datos relacionales en general (y SQLite en particular) sean rápidas es usar índices, ¡y estas columnas INTEGER ya no podrían indexarse ​​como columnas INTEGER porque contenían cadenas hexadecimales! Lo que significa que una vez que las bases de datos crecieron, bueno, básicamente la búsqueda y la recuperación eran demasiado lentas para ser útiles.

Este código era perfectamente funcional y vive en algunos compromisospero no fue lo suficientemente rápido para ser utilizado para el código de producción.

Desafortunadamente (¿o afortunadamente?), ahora estaba en eso. Ya había dedicado suficiente tiempo a este problema y tenía suficiente código y pruebas en funcionamiento, por lo que decidí continuar. Ver: falacia del costo hundido.

Almacenamiento de enteros sin signo de 64 bits eficientemente en SQLite

En realidad, no estaba convencido de que SQLite pudiera hacerlo de manera eficiente, así que pregunté en twitter sobre enfoques alternativos. Entre una variedad de respuestas, @jgoldschrafe dijo algo muy importante que resonó:

SQLite no es un monstruo de rendimiento para casos de uso complejos, pero debería estar absolutamente bien para esto.

y eso me dio el coraje para mantener el rumbo y trabajar en una resolución basada en SQLite.

La siguiente clave fue una idea con la que había jugado, basada en pistas aquí y entonces confirmado por el todavía increíble @jgoldschrafe – No necesitaba más de 64 bits, y solo necesitaba hacer una búsqueda basada en la igualdad. Entonces podría convertir entradas de 64 bits sin firmar en números de 64 bits con firma, insertarlos en la base de datos y hacer pruebas de igualdad entre una consulta y los hashvals. ¡Mientras hiciera la conversión sistemáticamente, todo funcionaría!

Terminé escribiendo dos funciones de adaptador que llamo en código Python para los valores relevantes (no usando el registro del convertidor de tipo SQLite) –

MAX_SQLITE_INT = 2 ** 63 - 1
convert_hash_to = lambda x: BitArray(uint=x, length=64).int if x > MAX_SQLITE_INT else x
convert_hash_from = lambda x: BitArray(int=x, length=64).uint if x < 0 else x

Tenga en cuenta que aquí estoy usando el encantador paquete de cadena de bits para que no tenga que pensar demasiado en jugar con los bits (aunque esa es una posible optimización ahora que tengo todo bloqueado con las pruebas).

El esquema SQL que estoy usando se ve así:

CREATE TABLE IF NOT EXISTS sketches
  (id INTEGER PRIMARY KEY,
   name TEXT,
   ...)

CREATE TABLE IF NOT EXISTS sourmash_hashes (
   hashval INTEGER NOT NULL,
   sketch_id INTEGER NOT NULL,
   FOREIGN KEY (sketch_id) REFERENCES sourmash_sketches (id)
)

y también construyo tres índices, que corresponden a los diversos tipos de consultas que quiero hacer:

CREATE INDEX IF NOT EXISTS sourmash_hashval_idx ON sourmash_hashes (
   hashval,
   sketch_id
)
CREATE INDEX IF NOT EXISTS sourmash_hashval_idx2 ON sourmash_hashes (
   hashval
)
CREATE INDEX IF NOT EXISTS sourmash_sketch_idx ON sourmash_hashes (
   sketch_id
)

Una de las decisiones de diseño que tomé a mitad de este PR fue permitir hashvals duplicados en sourmash_hashes – dado que diferentes bocetos pueden compartir hashvals con otros bocetos, tenemos que hacer las cosas de esta manera o tener otra tabla intermedia que vincule hashvals únicos a potencialmente múltiples sketch_ids. Parecía más simple tener hashvals no únicos y, en su lugar, crear un índice para las posibles consultas. (Podría revisar esto más tarde, ahora que puedo refactorizar sin miedo;).

En este punto, la inserción ahora es fácil:

sketch_id = ...

# insert all the hashes
hashes_to_sketch = []
for h in ss.minhash.hashes:
    hh = convert_hash_to(h)
    hashes_to_sketch.append((hh, sketch_id))

c.executemany("INSERT INTO sourmash_hashes (hashval, sketch_id) VALUES (?, ?)",
              hashes_to_sketch)

y la recuperación es igualmente simple:

sketch_id = ...

c.execute(f"SELECT hashval FROM sourmash_hashes WHERE sourmash_hashes.sketch_id=?", sketch_id)

for hashval, in c:
    hh = convert_hash_from(hashval)
    minhash.add_hash(hh)

¡Así que esto fue bastante efectivo para almacenar los bocetos en SQLite! Pude reconstruir bocetos perfectamente después de un viaje de ida y vuelta a través de SQLite, que fue un gran primer paso.

Siguiente pregunta: ¿podría rápidamente búsqueda los hashes como un índice invertido? Es decir, ¿podría encontrar bocetos basados ​​en consultas con hashes, en lugar de (como arriba) usar sketch_id recuperar hashes para un boceto ya identificado?

Coincidencia en entradas sin firmar de 64 bits en SQLite

¡Esto terminó siendo bastante simple!

Para consultar con una colección de hashes, configuro una tabla temporal que contiene los hashes de consulta y luego realizo una combinación en la coincidencia de valores exactos. Convenientemente, a esto no le importa si los valores en la base de datos están firmados o no, ¡solo le importa si los patrones de bits son iguales!

El código, para un cursor c:

def _get_matching_sketches(self, c, hashes, max_hash):
        """
        For hashvals in 'hashes', retrieve all matching sketches,
        together with the number of overlapping hashes for each sketch.
        """
        c.execute("DROP TABLE IF EXISTS sourmash_hash_query")
        c.execute("CREATE TEMPORARY TABLE sourmash_hash_query (hashval INTEGER PRIMARY KEY)")

        hashvals = [ (convert_hash_to(h),) for h in hashes ]
        c.executemany("INSERT OR IGNORE INTO sourmash_hash_query (hashval) VALUES (?)",
                      hashvals)

        c.execute(f"""
        SELECT DISTINCT sourmash_hashes.sketch_id,COUNT(sourmash_hashes.hashval) as CNT
        FROM sourmash_hashes, sourmash_hash_query
        WHERE sourmash_hashes.hashval=sourmash_hash_query.hashval
        GROUP BY sourmash_hashes.sketch_id ORDER BY CNT DESC
        """, template_values)

        return c

Como beneficio adicional, esta consulta ordena los resultados por el tamaño de la superposición entre los bocetos, lo que conduce a un código de umbral bastante bueno y eficiente.

Evaluación comparativa!!

Solo diré que el rendimiento es definitivamente aceptable: los puntos de referencia a continuación comparan sqldb con nuestros otros formatos de base de datos. La base de datos que estamos buscando es una colección de 48 000 bocetos con 161 millones de hashes en total: GTDB RS202, si tienes curiosidad :).

Para hashes de consulta de 53,9k, con 19,0k encontrados en la base de datos, la implementación de SQLite es agradable y rápida, aunque ocupa un gran espacio en el disco:

formato de base de datos tamaño de la base de datos tiempo memoria
sqldb 15GB 28,2 s 2,6GB
algo 3,5 GB 2m 43s 2,9 GB
Código Postal 1,7 GB 5m 16s 1,9 GB

Para consultas más grandes, con hashes de consulta de 374,6k, donde encontramos 189,1k en la base de datos, el rendimiento se nivela un poco:

formato de base de datos tamaño de la base de datos tiempo memoria
sqldb 15GB 3m 58s 9.9 GB
algo 3,5 GB 7m 33s 2,6GB
Código Postal 1,7 GB 5m 53s 2,0 GB

Tenga en cuenta que las búsquedas de archivos zip no usan ninguna indexación, por lo que la búsqueda es lineal y se espera que el tiempo sea más o menos el mismo independientemente de la consulta Y los SBT no están realmente destinados a este caso de uso, pero son la otra base de datos de «búsqueda rápida» que tenemos, así que los comparé de todos modos.

(Hay muchos matices en lo que estamos haciendo aquí y creo que entiendo principalmente estos números de rendimiento; consulte el problema de la evaluación comparativa por mis pensamientos.)

Lo realmente bueno es que para nuestro caso de uso motivador, buscar hashes en un índice inverso para correlacionarlos con otras etiquetas, el rendimiento con SQLite es mucho mejor que nuestro actual formato de búsqueda JSON en disco/en memoria.

Para hashes de consulta de 53.9k, obtenemos:

formato de base de datos lca tamaño de la base de datos tiempo memoria
sql 1,6 GB 20s 380 MB
JSON 175 MB 1m 21s 6,2 GB

lo cual es francamente excelente: ¡para un aumento de 8 veces en el tamaño del disco, obtenemos una consulta 4 veces más rápida y un uso de memoria 16 veces menor! (El rendimiento en memoria incluye la carga desde el disco, que es la razón principal por la que es tan terrible).

¿Más mejoras de rendimiento?

Todavía estoy bastante agotado por esta odisea de codificación (> 250 confirmaciones, que terminaron con casi 3000 líneas de código agregadas o modificadas), así que dejo algo de trabajo para el futuro. Más específicamente, nos gustaría comparar tener múltiples lectores leer de la base de datos a la vez, por ejemplo, backends de servidores web. Espero que funcione bastante bien para eso, pero tendremos que comprobarlo.

Uso los siguientes PRAGMA para la configuración, y me pregunto si debería dedicar tiempo a probar diferentes parámetros; esta es principalmente una base de datos construida alrededor de escribir una vez y leer muchas veces. Consejos bienvenidos :).

PRAGMA cache_size=10000000
PRAGMA synchronous = OFF
PRAGMA journal_mode = MEMORY
PRAGMA temp_store = MEMORY

Pensamientos concluyentes

La segunda solución anterior es el código que está en mi solicitud de extracción actual, y espero que finalmente se fusione con sourmash y se lance como parte de sourmash v4.4.0. Está completamente integrado en sourmash (con una gama mucho más amplia de casos de uso que los que expliqué anteriormente;), y estoy muy contento con él. En realidad, hay toda una ‘otra historia sobre los manifiestos que motivaron una parte de lo anterior; puedes leer sobre eso aquí.

No planeo volver a revisar los índices inversos en sourmash en el corto plazo, pero estamos empezando a pensar más seriamente en mejores (… formas que no sean JSON) de serializar bocetos. Avro se ve interesante y hay algunos formatos de columna rápidos como Arrow y Parquet; ver este problema para nuestras notas.

De todos modos, esa es mi odisea de SQLite. Pensamientos bienvenidos!

–tito



Fuente del artículo

Deja un comentario