Deutsch
Support

2021-01-25

DuckDBs Full-Text-Search-Erweiterung im Test

Laurens Kuiper

Textsuche in einer Datenbank ist umständlich, weil SQL keine gute Möglichkeit bietet, Fragen wie „Gib mir alle Dokumente über Stockenten“ zu formulieren: String-Muster mit LIKE reichen nur begrenzt. Trotzdem ist das Speichern von Text in einer Datenbank Alltag. Denken Sie an die Tabelle products (id INTEGER, name VARCHAR, description VARCHAR) – für eine Website, die diese Produkte verkauft, wäre eine Suche über name und description nützlich.

Von einer Suchmaschine erwarten wir Ergebnisse in Millisekunden. Lange Zeit waren Datenbanken dafür ungeeignet, weil sie große invertierte Indizes nicht schnell genug durchsuchen konnten: Transaktionale Systeme sind nicht für diesen Einsatz gebaut. Analytische Datenbanksysteme können jedoch mit modernen Information-Retrieval-Systemen mithalten. Ein gutes Beispiel ist das Unternehmen Spinque. Bei Spinque dient MonetDB als Rechenengine für maßgeschneiderte Suchmaschinen.

DuckDBs FTS-Implementierung folgt dem Paper „Old Dogs Are Great at New Tricks“. Eine wichtige Beobachtung dort: Fortschritte im Datenbanksystem, etwa Parallelisierung, beschleunigen die Suchmaschine „gratis“.

Genug zum „Warum“, jetzt zum „Wie“.

Daten vorbereiten

Der TREC 2004 Robust Retrieval Track umfasst 250 „Topics“ (Suchanfragen) über die TREC-Disks 4 und 5. Die Daten bestehen aus vielen Textdateien im SGML-Format sowie einer zugehörigen DTD (Document Type Definition). Dieses Format ist selten geworden, ähnelt aber XML. Wir wandeln es mit OpenSPs Kommandozeilenwerkzeug osx nach XML um. Weil es viele Dateien sind, habe ich ein Bash-Skript geschrieben:

Terminal window
mkdir -p latimes/xml
for i in $(seq -w 1 9); do
    cat dtds/la.dtd latimes-$i | osx > latimes/xml/latimes-$i.xml
done

Das sortiert die latimes-Dateien. Dasselbe für fbis, cr, fr94 und ft.

Zum Parsen des XML habe ich BeautifulSoup verwendet. Jedes Dokument hat eine docno-Kennung und ein text-Feld. Weil die Dokumente nicht aus derselben Quelle stammen, unterscheiden sie sich in den übrigen Feldern. Ich habe alle Felder übernommen.

import duckdb
import multiprocessing
import pandas as pd
import re
from bs4 import BeautifulSoup as bs
from tqdm import tqdm


# fill variable 'files' with the path to each .xml file that we created here


def process_file(fpath):
    dict_list = []
    with open(fpath, 'r') as f:
        content = f.read()
        bs_content = bs(content, "html.parser")
        # find all 'doc' nodes
        for doc in bs_content.findChildren('doc', recursive=True):
            row_dict = {}
            for c in doc.findChildren(recursive=True):
                row_dict[c.name] = ''.join(c.findAll(text=True, recursive=False)).trim()
            dict_list.append(row_dict)
    return dict_list


# process documents (in parallel to speed things up)
pool = multiprocessing.Pool(multiprocessing.cpu_count())
list_of_dict_lists = []
for x in tqdm(pool.imap_unordered(process_file, files), total=len(files)):
    list_of_dict_lists.append(x)
pool.close()
pool.join()


# create pandas dataframe from the parsed data
documents_df = pd.DataFrame([x for sublist in list_of_dict_lists for x in sublist])

Mit dem DataFrame können wir ihn in DuckDB registrieren.

# create database connection and register the dataframe
con = duckdb.connect(database='db/trec04_05.db', read_only=False)
con.register('documents_df', documents_df)


# create a table from the dataframe so that it persists
con.execute("CREATE TABLE documents AS (SELECT * FROM documents_df)")
con.close()

Das ist das Ende meines Vorbereitungsskripts, daher habe ich die Datenbankverbindung geschlossen.

Die Suchmaschine bauen

Den invertierten Index und das Retrieval-Modell bauen wir mit einem PRAGMA-Statement. Die Erweiterung ist hier dokumentiert. Wir erzeugen eine Index-Tabelle auf der Tabelle documents bzw. main.documents, die unser Skript angelegt hat. Die Spalte, die unsere Dokumente identifiziert, heißt docno, und wir wollen einen invertierten Index über die angegebenen Felder. Ich habe alle Felder über die Abkürzung * übergeben.

con = duckdb.connect(database='db/trec04_05.db', read_only=False)
con.execute("PRAGMA create_fts_index('documents', 'docno', '*', stopwords='english')")

Unter der Haube läuft ein parametrisiertes SQL-Skript. Das Schema fts_main_documents wird angelegt, zusammen mit den Tabellen docs, terms, dict und stats, die den invertierten Index bilden. Wer neugierig ist, wie das aussieht, findet den Quellcode im Ordner extension im DuckDB-Repository.

Den Benchmark ausführen

Die Daten sind jetzt vollständig vorbereitet. Als Nächstes wollen wir die Anfragen im Benchmark einzeln ausführen. Die Topics-Datei laden wir so:

# the 'topics' file is not structured nicely, therefore we need parse some of it using regex
def after_tag(s, tag):
    m = re.findall(r'<' + tag + r'>([\s\S]*?)<.*>', s)
    return m[0].replace('\n', '').strip()


topic_dict = {}
with open('../../trec/topics', 'r') as f:
    bs_content = bs(f.read(), "lxml")
    for top in bs_content.findChildren('top'):
        top_content = top.getText()
        # we need the number and title of each topic
        num = after_tag(str(top), 'num').split(' ')[1]
        title = after_tag(str(top), 'title')
        topic_dict[num] = title

Damit haben wir ein Dictionary mit Query-Nummer als Schlüssel und Query-String als Wert, z. B. 301 -> 'International Organized Crime'.

Die Ergebnisse wollen wir in einem bestimmten Format speichern, damit sie von trec eval ausgewertet werden können:

# create a prepared statement to make querying our document collection easier
con.execute("""
    PREPARE fts_query AS (
        WITH scored_docs AS (
            SELECT *, fts_main_documents.match_bm25(docno, ?) AS score FROM documents)
        SELECT docno, score
        FROM scored_docs
        WHERE score IS NOT NULL
        ORDER BY score DESC
        LIMIT 1000)
    """)


# enable parallelism
con.execute('PRAGMA threads=32')
results = []
for query in topic_dict:
    q_str = topic_dict[query].replace('\'', ' ')
    con.execute("EXECUTE fts_query('" + q_str + "')")
    for i, row in enumerate(con.fetchall()):
        results.append(query + " Q0 " + row[0].trim() + " " + str(i) + " " + str(row[1]) + " STANDARD")
con.close()


with open('results', 'w+') as f:
    for r in results:
        f.write(r + '\n')

Ergebnisse

Mit der Datei results können wir sie über trec_eval mit den Relevanzbewertungen qrels vergleichen.

Terminal window
./trec_eval -m P.30 -m map qrels results
map                     all 0.2324
P_30                    all 0.2948

Nicht schlecht! Die Ergebnisse liegen unter den reproduzierbaren Werten von Anserini, sind aber durchaus akzeptabel. Die Leistungsunterschiede erklären sich durch Unterschiede bei

  1. Welcher Stemmer verwendet wurde (wir haben ‚porter‘ verwendet)
  2. Welche Stoppwörter verwendet wurden (wir haben die 571 englischen Stoppwörter des SMART-Systems verwendet)
  3. Vorverarbeitung (Entfernen von Akzenten, Satzzeichen, Zahlen)
  4. BM25-Parametern (wir haben die Standardwerte k=1.2 und b=0.75 verwendet, nicht konjunktiv)
  5. Welche Felder indexiert wurden (wir haben alle Spalten über * verwendet)

Die Retrieval-Zeit pro Anfrage lag auf unserer Maschine zwischen 0,5 und 1,3 Sekunden und wird mit weiteren Verbesserungen an DuckDB sinken. Ich hoffe, der Beitrag hat Ihnen gefallen und Sie zum Ausprobieren der Erweiterung angeregt!