Salah satu skenario umum di semua aplikasi yang kita kenal adalah mencari data menurut kriteria tertentu dan menampilkannya dalam bentuk yang mudah dibaca. Mungkin juga ada opsi tambahan untuk pengurutan, pengelompokan, dan paging. Secara teori, tugas ini sepele, tetapi ketika menyelesaikannya, banyak pengembang membuat sejumlah kesalahan, yang kemudian menyebabkan produktivitas menurun. Mari kita coba mempertimbangkan berbagai opsi untuk memecahkan masalah ini dan merumuskan rekomendasi untuk memilih implementasi yang paling efektif.
Opsi halaman #1
Opsi paling sederhana yang terlintas dalam pikiran adalah menampilkan hasil pencarian halaman demi halaman dalam bentuknya yang paling klasik.
Katakanlah aplikasi Anda menggunakan database relasional. Dalam hal ini, untuk menampilkan informasi dalam formulir ini, Anda perlu menjalankan dua kueri SQL:
- Dapatkan baris untuk halaman saat ini.
- Hitung jumlah baris yang sesuai dengan kriteria pencarian - ini diperlukan untuk menampilkan halaman.
Mari kita lihat query pertama menggunakan database tes MS SQL sebagai contoh untuk server 2016. Untuk tujuan ini kita akan menggunakan tabel Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Kueri di atas akan mengembalikan 50 pesanan pertama dari daftar, diurutkan berdasarkan tanggal penambahan, dengan kata lain, 50 pesanan terbaru.
Ini berjalan cepat di basis pengujian, tapi mari kita lihat rencana eksekusi dan statistik I/O:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Anda dapat memperoleh statistik I/O untuk setiap kueri dengan menjalankan perintah SET STATISTICS IO ON di runtime kueri.
Seperti yang Anda lihat dari rencana eksekusi, opsi yang paling banyak menggunakan sumber daya adalah mengurutkan semua baris tabel sumber berdasarkan tanggal ditambahkan. Dan masalahnya adalah semakin banyak baris yang muncul di tabel, semakin “sulit” penyortirannya. Dalam praktiknya, situasi seperti ini harus dihindari, jadi mari tambahkan indeks ke tanggal penambahan dan lihat apakah konsumsi sumber daya telah berubah:
Table 'SalesOrderHeader'. Scan count 1, logical reads 165, physical reads 0, read-ahead reads 5, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Yang jelas, kondisinya menjadi jauh lebih baik. Tapi apakah semua masalah sudah teratasi? Mari kita ubah kueri untuk mencari pesanan yang total harga pokok barangnya melebihi $100:
SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Table 'SalesOrderHeader'. Scan count 1, logical reads 1081, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Kami memiliki situasi yang lucu: rencana kueri tidak jauh lebih buruk dari yang sebelumnya, tetapi jumlah sebenarnya dari pembacaan logis hampir dua kali lebih besar dibandingkan dengan pemindaian tabel penuh. Ada jalan keluarnya - jika kita membuat indeks komposit dari indeks yang sudah ada dan menambahkan total harga barang sebagai kolom kedua, kita akan kembali mendapatkan 165 bacaan logis:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Rangkaian contoh ini bisa dilanjutkan untuk waktu yang lama, namun dua pemikiran utama yang ingin saya ungkapkan di sini adalah:
- Menambahkan kriteria atau susunan pengurutan baru ke kueri penelusuran dapat berdampak signifikan pada kecepatan kueri penelusuran.
- Namun jika kita hanya perlu mengurangi sebagian data, dan tidak semua hasil yang cocok dengan istilah penelusuran, ada banyak cara untuk mengoptimalkan kueri tersebut.
Sekarang mari kita beralih ke kueri kedua yang disebutkan di awal - kueri yang menghitung jumlah rekaman yang memenuhi kriteria pencarian. Mari kita ambil contoh yang sama - mencari pesanan yang jumlahnya lebih dari $100:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Mengingat indeks komposit yang ditunjukkan di atas, kita memperoleh:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Fakta bahwa kueri melewati seluruh indeks tidaklah mengejutkan, karena bidang SubTotal tidak berada di posisi pertama, sehingga kueri tidak dapat menggunakannya. Masalahnya diselesaikan dengan menambahkan indeks lain pada bidang SubTotal, dan sebagai hasilnya hanya memberikan 48 pembacaan logis.
Anda dapat memberikan beberapa contoh lagi permintaan penghitungan besaran, tetapi intinya tetap sama: menerima sepotong data dan menghitung jumlah total adalah dua permintaan yang berbeda secara mendasar, dan masing-masing memerlukan tindakannya sendiri untuk pengoptimalan. Secara umum, Anda tidak akan dapat menemukan kombinasi indeks yang berfungsi sama baiknya untuk kedua kueri.
Oleh karena itu, salah satu persyaratan penting yang harus diklarifikasi ketika mengembangkan solusi pencarian tersebut adalah apakah penting bagi bisnis untuk melihat jumlah total objek yang ditemukan. Sering terjadi bahwa tidak. Dan navigasi berdasarkan nomor halaman tertentu, menurut saya, adalah solusi dengan cakupan yang sangat sempit, karena sebagian besar skenario paging terlihat seperti “buka halaman berikutnya”.
Opsi halaman #2
Anggaplah pengguna tidak peduli untuk mengetahui jumlah total objek yang ditemukan. Mari kita coba menyederhanakan halaman pencarian:
Faktanya, satu-satunya hal yang berubah adalah tidak ada cara untuk menavigasi ke nomor halaman tertentu, dan sekarang tabel ini tidak perlu mengetahui berapa banyak nomor halaman untuk menampilkannya. Namun muncul pertanyaan - bagaimana tabel mengetahui jika ada data untuk halaman berikutnya (agar dapat menampilkan link "Berikutnya" dengan benar)?
Jawabannya sangat sederhana: Anda dapat membaca satu record lebih banyak dari database daripada yang diperlukan untuk ditampilkan, dan kehadiran record “tambahan” ini akan menunjukkan apakah ada bagian berikutnya. Dengan cara ini, Anda hanya perlu menjalankan satu permintaan untuk mendapatkan satu halaman data, yang secara signifikan meningkatkan kinerja dan mempermudah dukungan fungsi tersebut. Dalam praktik saya, ada kasus ketika menolak menghitung jumlah total catatan mempercepat penyampaian hasil sebanyak 4-5 kali lipat.
Ada beberapa opsi antarmuka pengguna untuk pendekatan ini: perintah "kembali" dan "maju", seperti pada contoh di atas, tombol "muat lebih banyak", yang hanya menambahkan bagian baru ke hasil yang ditampilkan, "gulir tak terbatas", yang berfungsi dengan prinsip "muat lebih banyak" ", namun sinyal untuk mendapatkan porsi selanjutnya adalah pengguna menggulir semua hasil yang ditampilkan hingga akhir. Apapun solusi visualnya, prinsip pengambilan sampel data tetap sama.
Nuansa implementasi paging
Semua contoh kueri yang diberikan di atas menggunakan pendekatan “offset + count”, ketika kueri itu sendiri menentukan urutan baris hasil dan berapa banyak baris yang perlu dikembalikan. Pertama, mari kita lihat cara terbaik mengatur penerusan parameter dalam kasus ini. Dalam praktiknya, saya menemukan beberapa metode:
- Nomor seri halaman yang diminta (pageIndex), ukuran halaman (pageSize).
- Nomor seri record pertama yang dikembalikan (startIndex), jumlah maksimum record dalam hasil (count).
- Nomor urut record pertama yang dikembalikan (startIndex), nomor urut record terakhir yang dikembalikan (endIndex).
Pada pandangan pertama, tampaknya ini sangat mendasar sehingga tidak ada perbedaan. Namun tidak demikian - opsi yang paling nyaman dan universal adalah yang kedua (startIndex, count). Ada beberapa alasan untuk ini:
- Untuk pendekatan pengoreksian entri +1 yang diberikan di atas, opsi pertama dengan pageIndex dan pageSize sangat merepotkan. Misalnya kita ingin menampilkan 50 postingan per halaman. Menurut algoritma di atas, Anda perlu membaca satu catatan lebih banyak dari yang diperlukan. Jika “+1” ini tidak diterapkan di server, ternyata untuk halaman pertama kita harus meminta record dari 1 hingga 51, untuk halaman kedua - dari 51 hingga 101, dst. Jika Anda menentukan ukuran halaman 51 dan meningkatkan pageIndex, maka halaman kedua akan kembali dari 52 menjadi 102, dan seterusnya. Oleh karena itu, pada opsi pertama, satu-satunya cara untuk mengimplementasikan tombol untuk menuju ke halaman berikutnya dengan benar adalah dengan meminta server mengoreksi baris "ekstra", yang akan menjadi nuansa yang sangat tersirat.
- Opsi ketiga tidak masuk akal sama sekali, karena untuk menjalankan kueri di sebagian besar database, Anda masih harus meneruskan penghitungan, bukan indeks dari rekaman terakhir. Mengurangi startIndex dari endIndex mungkin merupakan operasi aritmatika yang sederhana, namun tidak berguna di sini.
Sekarang kita harus menjelaskan kelemahan penerapan paging melalui “offset + kuantitas”:
- Mengambil setiap halaman berikutnya akan lebih mahal dan lebih lambat dari yang sebelumnya, karena database masih harus menelusuri semua catatan “dari awal” sesuai dengan kriteria pencarian dan penyortiran, dan kemudian berhenti pada fragmen yang diinginkan.
- Tidak semua DBMS dapat mendukung pendekatan ini.
Ada alternatif lain, tapi juga tidak sempurna. Pendekatan pertama disebut "paging keyset" atau "metode pencarian" dan adalah sebagai berikut: setelah menerima sebagian, Anda dapat mengingat nilai bidang dalam catatan terakhir pada halaman, dan kemudian menggunakannya untuk memperoleh porsi selanjutnya. Misalnya, kami menjalankan kueri berikut:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Dan pada record terakhir kita mendapatkan nilai tanggal pemesanan '2014-06-29'. Kemudian untuk mendapatkan halaman berikutnya Anda bisa mencoba melakukan ini:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Masalahnya adalah OrderDate adalah bidang yang tidak unik dan kondisi yang ditentukan di atas kemungkinan besar akan kehilangan banyak baris yang diperlukan. Untuk menambah kejelasan pada kueri ini, Anda perlu menambahkan bidang unik ke kondisi (asumsikan bahwa 75074 adalah nilai terakhir kunci utama dari bagian pertama):
SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Opsi ini akan berfungsi dengan benar, namun secara umum akan sulit untuk dioptimalkan karena kondisinya berisi operator OR. Jika nilai kunci utama meningkat seiring bertambahnya Tanggal Pesanan, maka kondisi dapat disederhanakan dengan hanya menyisakan filter berdasarkan SalesOrderID. Tetapi jika tidak ada korelasi yang ketat antara nilai kunci utama dan bidang yang digunakan untuk mengurutkan hasilnya, OR ini tidak dapat dihindari di sebagian besar DBMS. Pengecualian yang saya ketahui adalah PostgreSQL, yang sepenuhnya mendukung perbandingan tuple, dan kondisi di atas dapat ditulis sebagai "WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)". Mengingat kunci komposit dengan dua bidang ini, kueri seperti ini seharusnya cukup mudah.
Pendekatan alternatif kedua dapat ditemukan, misalnya, di или — ketika permintaan, selain data, mengembalikan pengidentifikasi khusus yang dapat digunakan untuk mendapatkan bagian data berikutnya. Jika pengidentifikasi ini memiliki masa pakai yang tidak terbatas (seperti di Comsos DB), maka ini adalah cara terbaik untuk mengimplementasikan paging dengan transisi berurutan antar halaman (opsi #2 yang disebutkan di atas). Kemungkinan kelemahannya: tidak didukung di semua DBMS; pengidentifikasi potongan berikutnya yang dihasilkan mungkin memiliki masa pakai terbatas, yang umumnya tidak cocok untuk mengimplementasikan interaksi pengguna (seperti API gulir ElasticSearch).
Penyaringan yang rumit
Mari kita memperumit tugas ini lebih jauh. Misalkan ada persyaratan untuk menerapkan apa yang disebut pencarian segi, yang sangat familiar bagi semua orang di toko online. Contoh di atas berdasarkan tabel pesanan tidak terlalu ilustratif dalam kasus ini, jadi mari beralih ke tabel Produk dari database AdventureWorks:
Apa ide di balik pencarian segi? Faktanya adalah bahwa untuk setiap elemen filter, jumlah catatan yang memenuhi kriteria ini ditampilkan dengan mempertimbangkan filter akun yang dipilih di semua kategori lainnya.
Misalnya, jika kita memilih kategori Sepeda dan warna Hitam pada contoh ini, tabel hanya akan menampilkan sepeda berwarna hitam, namun:
- Untuk setiap kriteria di grup Kategori, jumlah produk dari kategori tersebut akan ditampilkan dalam warna hitam.
- Untuk setiap kriteria grup “Warna”, jumlah sepeda dengan warna ini akan ditampilkan.
Berikut adalah contoh keluaran hasil untuk kondisi seperti itu:
Jika Anda juga mencentang kategori “Pakaian”, tabel juga akan menampilkan stok pakaian hitam yang tersedia. Jumlah produk hitam di bagian “Warna” juga akan dihitung ulang sesuai dengan kondisi baru, hanya di bagian “Kategori” tidak ada yang berubah... Saya harap contoh ini cukup untuk memahami algoritma pencarian segi yang biasa.
Sekarang mari kita bayangkan bagaimana hal ini dapat diimplementasikan secara relasional. Setiap kelompok kriteria, seperti Kategori dan Warna, akan memerlukan kueri terpisah:
SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC
SELECT Color, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC
Apa yang salah dengan solusi ini? Ini sangat sederhana - skalanya tidak baik. Setiap bagian filter memerlukan kueri terpisah untuk menghitung kuantitas, dan kueri ini bukan yang termudah. Di toko online, beberapa kategori mungkin memiliki beberapa lusin bagian filter, yang dapat menjadi masalah kinerja yang serius.
Biasanya setelah pernyataan tersebut saya ditawari beberapa solusi, yaitu:
- Gabungkan semua jumlah kuantitas ke dalam satu kueri. Secara teknis hal ini dimungkinkan dengan menggunakan kata kunci UNION, tetapi ini tidak akan banyak membantu kinerja - database masih harus mengeksekusi setiap fragmen dari awal.
- Jumlah cache. Hal ini disarankan kepada saya hampir setiap kali saya menjelaskan suatu masalah. Peringatannya adalah hal ini umumnya tidak mungkin. Katakanlah kita memiliki 10 "segi", yang masing-masing memiliki 5 nilai. Ini adalah situasi yang sangat “sederhana” dibandingkan dengan apa yang bisa dilihat di toko online yang sama. Pemilihan salah satu unsur segi mempengaruhi besaran pada 9 unsur lainnya, dengan kata lain untuk setiap kombinasi kriteria besarannya dapat berbeda. Dalam contoh kita, ada total 50 kriteria yang dapat dipilih pengguna, sehingga akan ada 250 kemungkinan kombinasi. Tidak ada cukup memori atau waktu untuk mengisi array data tersebut. Di sini Anda dapat menolak dan mengatakan bahwa tidak semua kombinasi itu nyata dan pengguna jarang memilih lebih dari 5-10 kriteria. Ya, dimungkinkan untuk melakukan pemuatan lambat dan melakukan cache hanya dalam jumlah yang pernah dipilih, namun semakin banyak pilihan yang ada, semakin kurang efisien cache tersebut dan semakin nyata masalah waktu responsnya (terutama jika kumpulan data berubah secara berkala).
Untungnya, masalah seperti ini telah lama memiliki solusi yang cukup efektif dan dapat diprediksi dapat bekerja pada data dalam jumlah besar. Untuk salah satu opsi ini, masuk akal untuk membagi penghitungan ulang faset dan menerima halaman hasil menjadi dua panggilan paralel ke server dan mengatur antarmuka pengguna sedemikian rupa sehingga memuat data berdasarkan faset “tidak mengganggu” tampilan Hasil Pencarian.
- Sebisa mungkin lakukan perhitungan ulang lengkap “segi”. Misalnya, jangan menghitung ulang semuanya setiap kali kriteria pencarian berubah, tetapi temukan jumlah total hasil yang sesuai dengan kondisi saat ini dan minta pengguna untuk menampilkannya - “1425 catatan ditemukan, tunjukkan?” Pengguna dapat terus mengubah istilah pencarian atau mengklik tombol “tampilkan”. Hanya dalam kasus kedua semua permintaan untuk mendapatkan hasil dan menghitung ulang kuantitas pada semua “segi” akan dieksekusi. Dalam hal ini, seperti yang dapat Anda lihat dengan mudah, Anda harus menangani permintaan untuk mendapatkan jumlah total hasil dan pengoptimalannya. Cara ini banyak ditemukan di toko online kecil. Jelas, ini bukan obat mujarab untuk masalah ini, namun dalam kasus sederhana ini bisa menjadi kompromi yang baik.
- Gunakan mesin pencari untuk menemukan hasil dan menghitung aspek, seperti Solr, ElasticSearch, Sphinx, dan lainnya. Semuanya dirancang untuk membangun “segi” dan melakukannya dengan cukup efisien karena indeks terbalik. Cara kerja mesin pencari, mengapa dalam kasus seperti itu mereka lebih efektif daripada database tujuan umum, praktik dan kendala apa yang ada - ini adalah topik untuk artikel terpisah. Di sini saya ingin menarik perhatian Anda pada fakta bahwa mesin pencari tidak dapat menggantikan penyimpanan data utama, ini digunakan sebagai tambahan: setiap perubahan dalam database utama yang relevan untuk pencarian disinkronkan ke dalam indeks pencarian; Mesin pencari biasanya hanya berinteraksi dengan mesin pencari dan tidak mengakses database utama. Salah satu poin terpenting di sini adalah bagaimana mengatur sinkronisasi ini dengan andal. Itu semua tergantung pada persyaratan “waktu reaksi”. Jika waktu antara perubahan dalam database utama dan “manifestasinya” dalam pencarian tidak penting, Anda dapat membuat layanan yang mencari catatan yang baru diubah setiap beberapa menit dan mengindeksnya. Jika Anda menginginkan waktu respons sesingkat mungkin, Anda dapat menerapkan sesuatu seperti untuk mengirim pembaruan ke layanan pencarian.
Temuan
- Menerapkan paging sisi server merupakan komplikasi yang signifikan dan hanya masuk akal untuk kumpulan data yang berkembang pesat atau yang berukuran besar. Tidak ada resep pasti mengenai cara mengevaluasi “besar” atau “berkembang pesat”, namun saya akan mengikuti pendekatan ini:
- Jika menerima kumpulan data lengkap, dengan mempertimbangkan waktu server dan transmisi jaringan, sesuai dengan persyaratan kinerja secara normal, tidak ada gunanya menerapkan paging di sisi server.
- Mungkin ada situasi di mana diperkirakan tidak akan ada masalah kinerja dalam waktu dekat, karena hanya ada sedikit data, namun pengumpulan data terus bertambah. Jika kumpulan data tertentu di masa mendatang mungkin tidak lagi memenuhi poin sebelumnya, lebih baik segera mulai melakukan paging.
- Jika tidak ada persyaratan ketat dari pihak bisnis untuk menampilkan jumlah total hasil atau menampilkan nomor halaman, dan sistem Anda tidak memiliki mesin pencari, lebih baik tidak menerapkan poin ini dan pertimbangkan opsi #2.
- Jika ada persyaratan yang jelas untuk pencarian tersaring, Anda memiliki dua opsi tanpa mengorbankan kinerja:
- Jangan menghitung ulang seluruh kuantitas setiap kali kriteria pencarian berubah.
- Gunakan mesin pencari seperti Solr, ElasticSearch, Sphinx dan lain-lain. Namun perlu dipahami bahwa itu tidak bisa menjadi pengganti database utama, dan harus digunakan sebagai tambahan penyimpanan utama untuk menyelesaikan masalah pencarian.
- Selain itu, dalam kasus pencarian segi, masuk akal untuk membagi pengambilan halaman hasil pencarian dan penghitungan menjadi dua permintaan paralel. Menghitung jumlah mungkin memerlukan waktu lebih lama dibandingkan memperoleh hasil, sedangkan hasil lebih penting bagi pengguna.
- Jika Anda menggunakan database SQL untuk pencarian, perubahan kode apa pun yang terkait dengan bagian ini harus diuji kinerjanya dengan baik pada jumlah data yang sesuai (melebihi volume dalam database langsung). Disarankan juga untuk menggunakan pemantauan waktu eksekusi kueri pada semua instance database, dan terutama pada database "langsung". Meskipun semuanya baik-baik saja dengan rencana kueri pada tahap pengembangan, seiring bertambahnya volume data, situasinya dapat berubah secara signifikan.
Sumber: www.habr.com