sware

SWARE: Sortedness Aware Indexing

Quellcode für die Einreichung des ICDE 2023-Papiers: „Indexing for Near Sorted Data“

Um

Das Repository enthält den Quellcode für B+tree- und SWARE-Implementierungen. In der aktuellen Version des Codes sind beide Implementierungen generisch, aber die Anwendungsdateien, die diese Indexdatenstrukturen testen, unterstützen nur den Datentyp Integer. Außerdem verwenden die Anwendungsdateien für jeden Eintrag denselben Wert sowohl für den Schlüssel als auch für den Wert. Zukünftige Erweiterungen des Codes werden größere Datentypen unterstützen.

Beide Datenstrukturen erfordern während der Codeausführung eine Pufferpoolzuweisung, die bei Bedarf auf die erforderliche Menge erweitert werden kann, um vollständig im Speicher ausgeführt zu werden. Die Pufferpoolzuteilung wird in Form der Anzahl der Blöcke angegeben, wobei jeder Block 4 KB groß ist. Wenn Sie beispielsweise eine Zuweisung von 1 Mio. Blöcken verwenden, weisen Sie der Baumdatenstruktur 1 Mio. x 4 KB = 4 GB Speicher zu.

Der SA B+-Baum benötigt außerdem die Anzahl der Einträge, die sein In-Memory-Puffer während der Ausführung des Programms aufnehmen kann, sowie den Füllfaktor, der beim Massenladen beibehalten werden muss. Jeder Eintrag ist ein Schlüssel-Wert-Paar.

Wie man läuft

Erzeugen einer Aufnahmearbeitslast

Verwenden Sie den Sortierdatengenerator aus diesem Repo: https://github.com/BU-DiSC/bods, um Aufnahmeschlüssel zu generieren (Sie können Payload size=0 angeben, um nur Schlüssel zu generieren). Wie oben erwähnt, verwenden die Anwendungsdateien denselben Wert sowohl für den Schlüssel als auch für den Wert jedes Eintrags (K-, V-Paar). Notieren Sie sich den Pfad zur generierten Arbeitslast.

B+ Baum

1. Kompilieren Sie mit dem Befehl „make bplustree“
2. Führen Sie die ausführbare Datei im folgenden Format aus:

./ test_base_index < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. queries >

Sie würden zum Beispiel Folgendes verwenden:

./ test_base_index createdata_1000000 - elems_100000 - K_100000 - L_1seed1632764083 . dat sample . txt 1000000 100000 100000 200000

Hier nehmen wir eine Arbeitslast von 1 Mio. Einträgen/Schlüsseln mit K=L=100.000 auf. Wir verwenden einen Pufferpool-Cache für 1 Mio. Blöcke und führen 200.000 Punktabfragen aus. Die Ausgabelatenzen sowohl für die Aufnahme als auch für Punktabfragen werden in „sample.txt“ geschrieben.

SA B+ Baum

1. Kompilieren Sie mit dem Befehl „make satree“
2. Führen Sie die ausführbare Datei im folgenden Format aus:

./ test_satree < ingestion_workload_path > < output_file_name > < buffer_pool_allocation > < K > < L > < #. entries > < swareBuffer allocation > < fill factor % >  < #. queries >

Sie würden zum Beispiel Folgendes verwenden:

/ test_satree createdata_1000000 - elems_10 - K_10 - L_1seed1632764083 . dat swaresample . txt 1000000 10 10 1000000 10000 95 200000

Hier erfassen wir eine Arbeitslast von 1 Mio. Einträgen/Schlüsseln mit K=L=100.000 (10 % aller Einträge). Wir verwenden einen Pufferpool-Cache für 1 Mio. Blöcke und führen 200.000 Punktabfragen aus. Die Ausgabelatenzen für Aufnahme- und Punktabfragen werden in „swaresample.txt“ geschrieben. Der In-Memory-Puffer fasst 10.000 Einträge (1 % von 1 Million) und wir behalten einen Füllfaktor von 95 % bei.