Dalam artikel pertama tentang struktur file QVD, saya menggambarkan struktur umum dan membahas metadata dengan cukup detail, dan yang kedua tentang penyimpanan kolom (karakter). Dalam artikel ini, saya akan menjelaskan format untuk menyimpan informasi tentang string, merangkum, dan berbicara tentang rencana dan pencapaian.
Jadi (ingat) file QVD sesuai dengan tabel relasional, dalam file QVD tabel disimpan dalam dua bagian yang terhubung secara tidak langsung:
Tabel karakter (istilah saya) mengandung nilai unik untuk setiap kolom di tabel sumber. Saya berbicara tentang mereka di artikel kedua.
Tabel baris berisi baris tabel sumber, setiap baris menyimpan indeks nilai kolom (bidang) dari baris dalam tabel simbol yang sesuai. Tentang hal inilah artikel ini akan dibuat.
Pada contoh piring kami (ingat - dari bagian pertama)
SET NULLINTERPRET =<sym>; tab1: LOAD * INLINE [ ID, NAME 123.12,"Pete" 124,12/31/2018 -2,"Vasya" 1,"John" <sym>,"None" ];
Di tabel baris file QVD kami, label ini akan sesuai dengan 5 baris - selalu cocok dengan persis: berapa banyak baris dalam tabel, berapa banyak baris dalam tabel baris file QVD.
Baris dalam tabel baris terdiri dari bilangan bulat non-negatif, masing-masing angka ini adalah indeks ke dalam tabel simbol yang sesuai. Pada tingkat logis, semuanya sederhana, tetap mengklarifikasi nuansa dan memberikan contoh (membongkar - karena papan nama kami disajikan dalam QVD).
Tabel baris terdiri dari K * N byte, di mana
- K - jumlah baris dalam tabel sumber (nilai tag metadata "NoOfRecords")
- Panjang N-byte dari string tabel karakter (nilai tag metadata "RecordByteSize")
Tabel garis dimulai dengan offset "Offset" (tag metadata) relatif ke awal bagian biner file.
Informasi tentang tabel baris (panjang, ukuran baris, offset) disimpan di bagian umum metadata.
Semua baris tabel baris memiliki format yang sama dan merupakan gabungan dari "angka yang tidak ditandai". Panjang angka minimal cukup untuk mewakili bidang tertentu: panjangnya tergantung pada jumlah nilai unik bidang tertentu.
Untuk bidang dengan satu nilai (seperti yang sudah saya tulis), panjang ini akan menjadi nol (nilai ini sama di setiap baris tabel sumber dan disimpan dalam tabel simbol yang sesuai).
Untuk bidang dengan dua nilai, panjang ini akan sama dengan satu (nilai indeks yang mungkin dalam tabel simbol adalah 0 dan 1), dan seterusnya.
Karena total panjang baris dari tabel baris harus merupakan kelipatan byte, panjang "karakter terakhir" disejajarkan dengan batas byte (lihat di bawah ini ketika kita akan menguraikan plat kita).
Informasi tentang format masing-masing bidang disimpan di bagian metadata yang dikhususkan untuk bidang ini (kami akan tinggal sedikit lebih di bawah), panjang representasi bit bidang disimpan dalam tag "BitWidth".
Menyimpan Nilai NULL
Bagaimana cara menyimpan nilai yang hilang? Menahan diri dari mendiskusikan topik mengapa, saya akan menjawab dengan cara ini: seperti yang saya pahami, kombinasi berikut ini sesuai dengan nilai NULL
- tag "Bias" dari bidang yang sesuai mengambil nilai "-2" (semuanya, saya menemukan dua nilai yang mungkin dari tag ini - "0" dan "-2")
- indeks bidang untuk baris tempat bidang ini NULL adalah 0
Dengan demikian, semua indeks lain dalam kolom yang memiliki nilai NULL meningkat 2 - kita akan melihat dalam contoh kita sedikit lebih rendah.
Urutan bidang di baris
Urutan bidang di baris tabel baris sesuai dengan bit offset bidang, yang disimpan dalam tag "BitOffset" pada bagian metadata yang terkait dengan bidang ini.
Mari kita menganalisis contoh kita (lihat metadata di bagian pertama dari seri ini).
Bidang ID
- bit offset 0 - bidang akan menjadi "paling kanan"
- bit length 3 - bidang akan menempati 3 bit dalam satu baris tabel baris
- Bias adalah "-2" - bidang memiliki nilai NULL, semua indeks bertambah 2
Bidang "NAME"
- bit offset 3 - bidang terletak di sebelah kiri bidang ID sebanyak 3 bit
- bit length 5 - bidang akan menempati 5 bit di baris tabel baris (sejajar dengan batas byte)
- Bias adalah "0" - bidang tidak memiliki nilai NULL, semua indeks "jujur"
Presentasi papan nama kami.
Mari kita lihat "nol dan satu" yang sebenarnya - saya akan memberikan fragmen file QVD sebagai representasi biner "dalam format heksadesimal" (sangat ringkas).
Pertama, seluruh bagian biner (yang disorot dengan warna merah muda, metadata terpotong - itu menyakitkan banyak dari mereka ...)
Cukup kompak, setuju. Mari kita lihat lebih dekat - tepat setelah metadata ada tabel simbol (by the way, dalam file ini berakhir dengan linefeed dan byte nol - secara teknis ini terjadi, nol byte setelah metadata perlu dilewati ...).
Tabel simbol pertama disorot pada gambar di bawah ini.
Kita melihat:
Nilai unik pertama dari bidang ID adalah
- ketik "6" (byte pertama dialokasikan) adalah angka floating-point dengan string (lihat artikel kedua)
- setelah byte pertama, 8 dari byte berikutnya adalah biner yang mewakili angka floating-point
- setelah mereka datang representasi string - sangat mudah (tidak perlu diingat - berapa nomornya), berakhir dengan byte nol
Tiga nilai unik yang tersisa adalah tipe 5 (integer dengan string) - nilainya "124", "-2" dan "1" (mudah dilihat di sepanjang garis).
Pada gambar di bawah ini, saya menyoroti tabel simbol kedua (untuk bidang "NAME")
Nilai unik pertama dari bidang "NAME" adalah ketik "4" (byte pertama dialokasikan) - string yang diakhiri dengan nol.
Empat nilai unik lainnya adalah string "12/31/2018", "Vaysa", "John" dan "None".
Sekarang - tabel baris (disorot pada gambar di bawah)
Seperti yang diharapkan - 5 byte (5 baris dengan satu byte).
Baris pertama (sesuai dengan baris 123.12, "Pete" dari piring kami)
Nilai string adalah byte "02" (biner 000000010).
Pisahkan itu (ingat deskripsi di atas)
- 3 bit kanan (biner 010, menurut kami ini 2) - ini adalah indeks ke dalam tabel simbol dari bidang "ID"
- kami memiliki bidang "ID" yang berisi NULL, sehingga indeksnya naik 2, yaitu indeks yang dihasilkan adalah 0, yang sesuai dengan karakter "123.12".
- 5 bit berikutnya (biner dan desimal 0) adalah indeks dalam tabel simbol dari bidang "NAME", itu tidak mengandung NULL, oleh karena itu ini adalah indeks "Pete" dalam tabel simbol.
Baris kedua (124.12 / 31/2018) di tabel baris
Nilai - byte "0B" (biner 00001011)
- 3 bit kanan (biner 011, menurut kami 3) - ini adalah indeks ke dalam tabel simbol dari bidang "ID"
- kami memiliki bidang "ID" yang berisi NULL, sehingga indeksnya naik 2, yaitu indeks yang dihasilkan adalah 1, yang sesuai dengan simbol "124".
- 5 bit berikutnya (biner dan desimal 1) adalah indeks dalam tabel simbol dari bidang "NAME", itu tidak mengandung NULL, oleh karena itu ini adalah indeks "12/31/2018" dalam tabel simbol.
Nah dan seterusnya, mari kita lihat baris terakhir - di sana kita memilikinya, "Tidak ada" (yaitu NULL dan string "Tidak Ada"):
Nilainya byte "20" (biner 0010000)
- 3 bit kanan (biner dan desimal 0) - ini adalah indeks ke dalam tabel simbol bidang "ID"
- kami memiliki bidang "ID" yang berisi NULL, sehingga indeksnya naik 2, yaitu indeks akhir adalah -2, yang sesuai dengan nilai NULL.
- 5 bit berikutnya (biner 100, desimal 4) adalah indeks dalam tabel simbol dari bidang "NAME", itu tidak mengandung NULL, jadi ini adalah indeks "Tidak Ada" di tabel simbol.
PENTING Saya tidak dapat menemukan contoh yang mengonfirmasi hal ini, tetapi saya menemukan file yang berisi indeks akhir -1 untuk nilai NULL. Oleh karena itu, dalam program saya, saya menganggap NULL semua bidang yang indeks akhirnya negatif.
Baris yang lebih panjang di tabel baris
Pada akhir parsing format QVD, saya akan secara singkat memikirkan nuansa penting - garis panjang di bidang tabel toko baris dalam urutan kanan-ke-kiri, di mana bidang dengan offset bit nol akan menjadi yang paling kanan (seperti yang saya jelaskan di atas). TETAPI urutan byte terbalik, mis. byte pertama akan menjadi yang paling kanan (dan akan berisi bidang "kanan" - bidang dengan offset bit nol), byte terakhir akan menjadi yang pertama (yaitu, berisi bidang paling "kiri" - bidang dengan bit offset maksimum).
Sebuah contoh harus diberikan, tetapi tidak dibebani dengan detail. Mari kita lihat label seperti itu (saya kutip sebuah fragmen - untuk mendapatkan garis panjang di tabel baris, Anda perlu menambah jumlah nilai unik).
tab2: LOAD * INLINE [ ID, VAL, NAME, PHONE, SINGLE 1, 100001, "Pete1", "1234567890", "single value" 2, 200002, "Pete2", "2234567890", "single value" ... ];
Informasi singkat tentang bidang (memeras metadata):
- ID: lebar 8 bit, bit offset - 0, bias - 0
- VAL: lebar 5 bit, bit offset - 8, bias - 0
- NAME: lebar 6 bit, bit offset - 18, bias - 0
- TELEPON: lebar 5 bit, bit offset - 13, bias - 0
- TUNGGAL: lebar 0 bit (memiliki satu nilai)
Tabel baris terdiri dari string dengan panjang 3 byte, masing-masing, di baris tabel baris data tentang bidang akan didekomposisi secara logis sebagai berikut:
- 6 bit pertama - bidang "NAME"
- 5 bit berikutnya - bidang "PHONE"
- lalu 5 bit - bidang "VAL"
- 8 bit terakhir - bidang ID
Urutan logis dikonversikan ke byte fisik dalam urutan terbalik, mis.
- bidang "ID" sepenuhnya menempati byte pertama (yang dalam urutan logis adalah yang terakhir)
- bidang "VAL" menempati 5 bit lebih rendah dari byte kedua
- bidang "PHONE" menempati 3 bit atas dari byte kedua dan 2 bit lebih rendah dari byte ketiga
- bidang "NAME" menempati 6 bit teratas dari byte ketiga
Mari kita lihat contoh-contoh, di sini terlihat seperti apa baris pertama dari tabel baris (disorot dengan warna merah muda)
Nilai bidang
- ID - biner 00000000, desimal 0
- VAL - biner 00010, desimal 2, kurangi 2 dari bias - dapatkan 0
- PONSEL - biner 00010, desimal 2, kurangi 2 dari bias - dapatkan 0
- NAME - biner 000000, desimal 0
Artinya, baris pertama berisi karakter pertama dari tabel karakter yang sesuai.
Secara umum, lebih mudah untuk memulai parsing dari baris pertama - biasanya berisi nol sebagai indeks (file QVD dibangun sedemikian rupa sehingga nilai-nilai dari baris pertama masuk ke tabel simbol terlebih dahulu).
Mari kita lihat baris kedua untuk diperbaiki
Nilai bidang
- ID - biner 00000001, desimal 1
- VAL - biner 00011, desimal 3, kurangi 2 dari bias - dapatkan 1
- PONSEL - biner 00011, desimal 3, kurangi 2 dari bias - dapatkan 1
- NAME - biner 000001, desimal 1
Yaitu, baris kedua berisi karakter kedua dari tabel karakter yang sesuai.
Saya akan berbagi sedikit pengalaman - bagaimana saya secara teknis "membaca" QVD.
Versi pertama ditulis dengan python (saya akan memuliakannya dan meletakkannya di github).
Masalah utama dengan cepat menjadi jelas:
- tabel simbol hanya dapat dibaca “berturut-turut” (tidak mungkin membaca nomor simbol N tanpa membaca semua karakter sebelumnya)
- file nyata tidak sesuai dengan RAM
- dari operasi paling lambat (kecuali untuk bekerja dengan file) - operasi bit (membongkar deretan tabel string)
- kinerja menurun drastis pada file QVD "lebar" (ketika ada banyak kolom)
Beberapa masalah ini dapat diatasi dengan mengubah bahasa (dari python ke C, misalnya). Bagian diperlukan beberapa tindakan tambahan.
Implementasi saat ini agak cepat terlihat seperti ini - logika umum diimplementasikan dalam python, dan operasi yang paling kritis dilakukan dalam program C terpisah yang berjalan secara paralel.
Sebentar lagi
- tabel simbol ditulis ke file, indeks juga dibuat untuk bidang teks, sehingga dimungkinkan untuk membaca nomor simbol N
- bekerja dengan QVD dan file dengan tabel simbol dilaksanakan melalui file yang dipetakan memori (jadi lebih cepat)
- pertama, secara paralel (dengan batasan jumlah prosesor), file dibuat dengan tabel simbol (dan indeks)
- kemudian secara paralel (dengan batasan yang sama) baris-baris tabel baris dibaca dan file csv dibuat (dalam HDFS)
- langkah terakhir adalah mengonversi file-file ini ke tabel ORC (menggunakan alat Hive)
- di C mengimplementasikan pembuatan file dengan tabel simbol dan pembuatan file CSV untuk berbagai baris
Saya tidak ingin memberikan angka untuk kinerja - mereka akan membutuhkan pengikatan pada perangkat keras, pada tingkat kualitatif ternyata menyalin file QVD ke tabel ORC dengan kecepatan menyalin data melalui jaringan. Atau, dengan kata lain, mengambil data dari QVD cukup realistis (di tingkat rumah tangga).
Saya juga menerapkan logika membuat file QVD - ini bekerja cukup cepat pada python (tampaknya, saya belum mencapai volume besar - tidak perlu. Saya akan sampai di sana - Saya akan menulis ulang dengan cara yang sama seperti versi "membaca").
Rencana masa depan
Apa selanjutnya
- Saya berencana untuk meletakkan versi kode Python di github (versi ini akan memungkinkan Anda untuk "menjelajahi" file QVD - lihat metadata, baca dan tulis karakter, string. Versi ini sesederhana dan sejelas mungkin - tanpa file untuk tabel karakter, dengan pembacaan berurutan, menggunakan perpustakaan standar untuk bekerja dengan bit, dll.)
- Saya berpikir tentang melakukan sesuatu untuk panda (seperti read_qvd ()), ia menahan bahwa itu akan lambat pada python, serta fakta bahwa jelas tidak setiap QVD akan "masuk" ke dalam memori, oleh karena itu
- Saya berpikir tentang menjadikan file QVD sebagai sumber data untuk Spark - seharusnya tidak ada masalah dengan "tidak masuk ke memori" (dan bahasa di sana - scala - lebih dekat ke perangkat keras)
Alih-alih kata penutup
Untuk waktu yang lama saya berkeliling file QVD, sepertinya "semuanya rumit di sana." Ternyata itu sulit, tetapi tidak terlalu, dorongan yang baik adalah github, yang saya sebutkan di bagian pertama (semacam katalis). Lalu itu masalah teknologi. Saya dan semua orang mencatat (satu konfirmasi lagi) - semuanya dapat dilakukan dalam pemrograman, pertanyaannya adalah waktu dan motivasi.
Saya harap saya tidak terlalu lelah dengan detailnya, saya siap untuk menjawab pertanyaan (dalam komentar atau dengan cara lain). Jika akan ada kelanjutan, saya pasti akan menulis.