Offline Full-Text Search en Android & iOS

22 sept. 2018

A veces tu app usa datos que no cambian muy seguido, por lo que podrías guardar una copia en el almacenamiento local, convirtiendo tu app en una solución offline-first, más rápida y siempre disponible para tus queridos usuarios. Eso suena bien, pero obviamente querés hacer algo con esos datos. Supongamos que querés permitir que el usuario busque en miles de documentos, alguien podría decir “ok, olvidate del enfoque offline-first y mové los datos a un Elasticsearch”, pero ese no soy yo, porque la buena noticia es que SQLite soporta full-text search (FTS) nativamente y está disponible tanto para Android como para iOS.

¿Por qué full-text search?

Siempre que ejecutás una query como esta:

SELECT * FROM movies WHERE title LIKE '%pulp%'

el motor de la base de datos tiene que escanear toda la tabla, porque no hay forma de saber qué película contiene ese término en su título sin verificar cada una de las filas, y es aún peor si necesitamos buscar en varios campos al mismo tiempo.

Un enfoque de búsqueda full-text tiene dos pasos: indexación y búsqueda. Durante la indexación se escanean todos los documentos, lo que genera una lista de términos de búsqueda (índice). Luego, cuando ejecutamos la consulta, ese índice se utiliza para realizar la búsqueda.

Implementando FTS en SQLite usando el módulo FTS5

Afortunadamente, podemos implementar una búsqueda full-text en una aplicación móvil sin tener que configurar ni mantener un motor de búsqueda costoso en el servidor, simplemente usando el módulo FTS5 de SQLite, que podría ser lo suficientemente bueno para nuestras necesidades.

Vamos a crear una aplicación para buscar películas en una base de datos local. Lo primero es crear la tabla para nuestras películas, pero no será una tabla común, tiene que ser una tabla FTS:

CREATE VIRTUAL TABLE movies
USING FTS5(title, overview, year UNINDEXED);

Acabamos de crear nuestra tabla FTS. Ahora podemos realizar una búsqueda rápida por título y descripción general en miles de películas, y con una sola consulta. Notar la opción UNINDEXED: esto significa que el año no es parte del índice, por lo que no podremos buscar en ese campo (y tiene sentido).

Insertar datos es tan simple como en cualquier otra tabla. Para este artículo, creé un script SQL con 3.000 películas. Pero, para darte un ejemplo, así es como se ve una sola inserción:

INSERT INTO movies ('title', 'overview', 'poster', 'year')
VALUES ('Pulp Fiction', 'A burger-loving hit man...', '1994');

Ahora ejecutemos una consulta para encontrar todas las películas que coincidan con el término “pulp”:

SELECT * FROM movies WHERE movies MATCH 'pulp';

Tener en cuenta que no es necesario especificar cada campo en la cláusula where, ya que todos los campos indexados (título y descripción general) se evalúan con la operación match.

Ahora, en nuestro caso, queremos crear una barra de búsqueda con autocompletado, por lo que necesitamos mostrar todas las películas que coincidan con la entrada del usuario tan pronto como cambie. En este escenario, si el usuario escribe “pul”, deberíamos encontrar todas las películas que contengan un término que comience así. Por lo tanto, nuestra consulta cambia un poco:

SELECT * FROM movies WHERE movies MATCH 'pul*';

En este punto, nuestra aplicación puede realizar una búsqueda full-text y encontrar todas las películas que coinciden con la entrada del usuario. Pero si ejecutás la última consulta, te darás cuenta de que las películas no están ordenadas en función del resultado que mejor coincide. Aquí viene el último pero importante paso: el ranking.

Rankear los resultados

Ahora necesitamos rankear los resultados encontrados en nuestra base de datos SQLite. Para ello, necesitamos una función de ranking, y una de las funciones más utilizadas en nuestro contexto es Okapi BM25. En versiones anteriores del módulo FTS (FTS3/FTS4), tenías que implementar esta función por tu cuenta y realizar el ranking en el lado de la aplicación. Pero ahora con FTS5 esto es parte del módulo, y es tan simple como:

SELECT * FROM movies WHERE movies MATCH 'pul*' ORDER BY rank;

entonces, por debajo, SQLite crea una columna oculta llamada rank, que contiene el score de cada película, que se calculó utilizando Okapi BM25.

Distintos pesos para cada campo

Hasta ahora, veníamos asumiendo que todos los campos tenían el mismo peso, por lo que daba lo mismo si el término buscado por el usuario estaba presente en el título o en la descripción general. Pero en la mayoría de los casos, y esta no es la excepción, queremos priorizar ciertos campos. Por lo tanto, mejoremos nuestro autocompletado y otorguemos al campo de título un peso de 10:1 sobre la descripción general, es decir, será 10 veces más importante si encontramos el término buscado dentro del título, que si lo encontramos dentro de la descripción.

SELECT * FROM movies WHERE movies MATCH 'pul*'
AND rank MATCH 'bm25(10.0, 1.0)' ORDER BY rank

¿Qué es esto? Te explico: si no especifica una función de ranking cuando ordena por rank, SQLite usa por debajo la función bm25(), sin ningún parámetro (todos los campos tienen el mismo peso), pero como queremos cambiarlo, tenemos que usar explícitamente la función, definiendo los pesos que queremos en el mismo orden en que declaramos los campos durante la creación de la tabla.

FTS5 en acción

Finalmente, así es como funciona FTS5. Notar que cuando escribí “Jedi”, se devolvieron todas las películas de Star Wars (porque ese término está presente en la descripción general), pero el primer resultado fue “Return of the Jedi”, ya que el título tiene un mayor peso.

FTS4: alternativa para dispositivos antiguos

Como mencioné antes, el enfoque anterior se implementó usando el módulo FTS5, pero dependiendo del target que tenga tu aplicación Android / iOS, es posible que no puedas usarlo, pero con un poco más de trabajo podemos implementar la búsqueda full-text usando FTS4 en su lugar.

¿Qué módulo debería usar?

Según la documentación oficial, FTS5 se lanzó con SQLite 3.9.0, por lo que debería estar incluido en todos los dispositivos que ejecuten:

iOS ≥ 10.0
Android ≥ API 24

Si nos fijamos en el gráfico de adopción de iOS, en este momento el 95% de los usuarios utilizan iOS 10 o iOS 11, por lo que quizá no tenga sentido implementar el enfoque FTS4 solo para un 5%. Es tu elección.

Pero como en el mundo Android solo un 30% tiene una API ≥ 24, deberías considerar usar FTS4 en su lugar.

Trabajando con FTS4

Primero, la sintáxis para crear una table FTS cambia un poco:

CREATE VIRTUAL TABLE movies
USING FTS4(title, overview, year, year=NONINDEXED);

como podés ver, tenés que usar la palabra clave FTS4 en su lugar, y los campos no indexados se declaran como nonindexed.

Fácil, ¿verdad? Ahora el gran cambio llega cuando queremos realizar la búsqueda. Como mencioné antes, FTS4 no admite ordenar por una función de ranking, por lo que debes implementarla por tu cuenta. Lo bueno es que FTS4 tiene una función que puedes incluir como parte del select, y devuelve un conjunto de valores que puede usar nuestra implementación de Okapi BM25. Esta función se llama matchinfo y se usa de la siguiente manera:

SELECT *, MATCHINFO(movies, 'pcnalx') FROM movies
WHERE movies MATCH 'pul*';

Esta función recibe el nombre de la tabla como primer parámetro y un conjunto de caracteres, cada uno de los cuales representa un campo calculado, como segundo parámetro. Los valores que necesitamos para utilizar la función Okapi BM25 están representados por pcnalx. Ahora, veamos cómo clasificar los resultados en la aplicación utilizando esos valores.

Rankear los resultados en Swift (iOS)

// OkapiBM25 usage in Swift
func search(text: String) -> [Movie] {

    var movies: [Movie] = []
    var statement: OpaquePointer?

    let query = "SELECT title, overview, poster, year, matchinfo(movies, 'pcnalx') FROM movies WHERE movies MATCH '\(text)*'"

    if sqlite3_prepare_v2(db, query, -1, &statement, nil) != SQLITE_OK {
        print("Error preparing select: \(String(cString: sqlite3_errmsg(db)!))")
    }

    while sqlite3_step(statement) == SQLITE_ROW {
        if
            let cTitle = sqlite3_column_text(statement, 0),
            let cOverview = sqlite3_column_text(statement, 1),
            let cPoster = sqlite3_column_text(statement, 2)
        {
            let cYear = sqlite3_column_int64(statement, 3)

            // Read and prepare matchinfo blob
            let buf = sqlite3_column_blob(statement, 4).assumingMemoryBound(to: UInt32.self)
            let blob = [UInt32](UnsafeBufferPointer(start: buf, count: Int(sqlite3_column_bytes(statement, 4))))

            // Calculate score based on matchinfo values
            // Here I'm only using the first column (title) to calculate the score
            let score = OkapiBM25.score(matchinfo: blob, column: 0)

            movies.append(
                Movie(
                    title: String(cString: cTitle),
                    overview: String(cString: cOverview),
                    poster: String(cString: cPoster),
                    year: Int(cYear),
                    score: score
                )
            )

        }
    }

    if sqlite3_finalize(statement) != SQLITE_OK {
        print("Error finalizing prepared statement: \(String(cString: sqlite3_errmsg(db)!))")
    }

    // Sort the movies by the Okapi BM25 score
    return movies.sorted(by: {$0.score > $1.score})
}

Rankear los resultados en Kotlin (Android)

// OkapiBM25 usage in Kotlin
fun search(text: String): List<Movie> {
    val movies = mutableListOf<Movie>()
    val cursor = getDatabase().rawQuery("SELECT title, overview, poster, matchinfo(movies, 'pcnalx') FROM movies WHERE movies MATCH '$text*'", null)
    if (cursor.moveToFirst()) {
        do {
            // Read and prepare matchinfo blob
            val matchinfo = cursor.getBlob(3).toIntArray()

            // Calculate score based on matchinfo values
            // Here I'm only using the first column (title) to calculate the score
            val score = OkapiBM25.score(matchinfo = matchinfo, column = 0)

            val movie = Movie(
                    title = cursor.getString(0),
                    overview = cursor.getString(1),
                    poster = cursor.getString(2),
                    score = score)

            movies.add(movie)

        } while (cursor.moveToNext())
    }
    cursor.close()
    return movies.sortedByDescending { it.score }
}

Conclusión

El módulo FTS de SQLite puede ser una excelente manera de implementar una búsqueda full-text tanto en iOS como en Android, sin ninguna dependencia externa ni servidor ejecutándose por detrás. Yo implementé esta solución en una de mis aplicaciones que tengo publicadas en Google Play Store y App Store, y como está funcionando muy bien, escribí esta publicación para compartirla con la comunidad. Pueden encontrar el ejemplo funcional que hice para este artículo en mi repositorio de Github. Happy coding!

Github Repos

FTS5 implementation (iOS)
FTS4 implementation (iOS & Android)