4paradigm / 4paradigm/OpenMLDB

Implement an efficient encoding scheme for `Traverse`

Offen
#1,915 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
call-for-contributions enhancement storage-engine
Vorherrschende Sprache
C++
Sterne
1.7k
Forks
331
Ø Merge
12 T. 12 Std.
Gemergte PRs (30 T.)
1

Beschreibung

# Problem
Currently, the records used by the `Travserse` function are encoded as follows (both pk and value are strings)
```
record length | pk length | pk | ts | value | record length | pk length | pk | ts | value ...
```
As the same pk may have multiple values, this encoding scheme may cause inefficiency because of the duplicate records for pk

# Solution
We can implement a compact format to store those data. The basic idea is to arrange the ts and values corresponding to the same pk continuously. For example, for pk1 (with ts1_x and val1_x), and pk2 (with ts2_x and val2_x):
```
pk1 | ts1_1 | val1_1 | ts1_2 | val1_2 | pk2 | ts2_1 | val2_1 | ts2_2 | val2_2
```

Specifically, considering the string type for `pk` and `val`, we need to record the length of a string as well. We also record the number of `ts` and `val` corresponding to the same pk (num_of_vals). Here is the detailed encoding scheme for one pk, more pk can be packed subsequently.
```
pk_len | pk | num_of_vals | ts | val_len | val | ts | val_len | val | ... (there are `num_of_vals` occurrences of "ts | val_len | val" in total)
```

# Related modules
https://github.com/4paradigm/OpenMLDB/blob/main/src/tablet/tablet_impl.cc#L1402
https://github.com/4paradigm/OpenMLDB/blob/main/src/base/kv_iterator.h#L81

Beitragsleitfaden

Beitragsleitfaden öffnen

Rechercherichtung

The issue points to tablet_impl.cc line 1402 and kv_iterator.h line 81 as the related modules. Start by examining the current encoding in those files to understand the Traverse function's data layout. Then design and implement the new compact format as described, ensuring it handles variable-length strings correctly. Test the changes with existing database operations to verify correctness and performance improvement.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
cpp
Bereich
databases
Issue-Typ
Refactoring
Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Aktivitätsstatus
Veraltet
Klarheit
Klar beschrieben
Anfängerfreundlichkeit
45/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.