Tampilkan hasil pencarian dan masalah kinerja

Salah satu skenario khas di semua aplikasi yang sudah dikenal adalah mencari data sesuai dengan kriteria tertentu dan menampilkannya dalam bentuk yang mudah dibaca. Mungkin juga ada peluang tambahan untuk menyortir, mengelompokkan, membuat halaman. Tugasnya, secara teori, sepele, tetapi ketika menyelesaikannya, banyak pengembang membuat sejumlah kesalahan, yang kemudian menderita karena kinerja. Mari kita coba mempertimbangkan berbagai solusi untuk masalah ini dan merumuskan rekomendasi untuk memilih implementasi yang paling efektif.

gambar

Opsi Paging # 1


Opsi paling sederhana yang muncul di benak Anda adalah membuat paginasi hasil pencarian dalam bentuk paling klasik.


Misalkan aplikasi menggunakan database relasional. Dalam hal ini, untuk menampilkan informasi dalam formulir ini, Anda perlu menjalankan dua query SQL:

  • Dapatkan baris untuk halaman saat ini.
  • Hitung jumlah total baris yang cocok dengan kriteria pencarian - ini diperlukan untuk menampilkan halaman.

Pertimbangkan kueri pertama menggunakan database uji MS SQL AdventureWorks untuk server 2016 sebagai contoh . Untuk tujuan ini, kami 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 menampilkan 50 pesanan pertama dari daftar yang diurutkan dalam urutan menurun berdasarkan tanggal penambahan, dengan kata lain, 50 pesanan terakhir.

Ini berjalan cepat berdasarkan pengujian, tetapi 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 bisa mendapatkan statistik I / O untuk setiap permintaan dengan menjalankan perintah SET STATISTICS IO ON di runtime kueri.

Seperti yang Anda lihat dari rencana eksekusi, sumber daya paling intensif adalah untuk mengurutkan semua baris dalam tabel sumber berdasarkan tanggal mereka ditambahkan. Dan masalahnya adalah semakin banyak baris muncul di tabel, semakin sulit penyortirannya. Dalam praktiknya, situasi seperti itu harus dihindari, jadi tambahkan indeks pada 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.

Jelas, itu menjadi jauh lebih baik. Tetapi apakah semua masalah telah diselesaikan? Mari kita ubah permintaan pencarian untuk pesanan di mana total biaya barang 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 sedikit lebih buruk daripada yang sebelumnya, tetapi jumlah sebenarnya pembacaan logis hampir dua kali lipat dengan pemindaian tabel penuh. Ada jalan keluar - jika kita membuat harga komposit dari indeks yang ada dan menambahkan harga total barang sebagai bidang kedua, maka sekali lagi kita mendapatkan 165 pembacaan logis:

CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);

Serangkaian contoh ini dapat dilanjutkan untuk waktu yang lama, tetapi dua pemikiran utama yang ingin saya ungkapkan di sini adalah:

  • Menambahkan kriteria baru atau urutan apa pun ke permintaan pencarian dapat secara signifikan mempengaruhi kecepatan pelaksanaannya.
  • Tetapi jika kita perlu mengurangi hanya sebagian dari data, dan tidak semua hasil yang sesuai dengan kondisi pencarian, ada banyak cara untuk mengoptimalkan permintaan seperti itu.

Sekarang mari kita beralih ke permintaan kedua, yang disebutkan di bagian paling awal - ke yang menghitung jumlah rekaman yang memenuhi kriteria pencarian. Ambil contoh yang sama - temukan pesanan yang harganya lebih dari $ 100:

SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100

Dengan adanya indeks komposit yang ditunjukkan di atas, kami 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 tidak mengejutkan, karena bidang SubTotal tidak di posisi pertama, sehingga kueri tidak dapat menggunakannya. Masalahnya dipecahkan dengan menambahkan indeks lain ke bidang SubTotal, dan sebagai hasilnya sudah hanya 48 pembacaan logis.

Anda dapat memberikan beberapa contoh lagi permintaan untuk menghitung kuantitas, tetapi esensinya tetap sama: mendapatkan sepotong data dan menghitung jumlah total adalah dua permintaan yang berbeda secara mendasar , dan masing-masing memerlukan langkah-langkah sendiri untuk optimasi. Dalam kasus umum, Anda tidak dapat menemukan kombinasi indeks yang berfungsi sama baiknya untuk kedua kueri.

Dengan demikian, salah satu persyaratan penting yang harus diklarifikasi ketika mengembangkan solusi pencarian adalah apakah benar-benar penting bagi bisnis untuk melihat jumlah objek yang ditemukan. Sering terjadi tidak. Dan navigasi ke nomor halaman tertentu, menurut saya, adalah solusi dengan ruang lingkup yang sangat sempit, karena sebagian besar skenario paging terlihat seperti "pergi ke halaman berikutnya."

Opsi Paging # 2


Misalkan pengguna tidak peduli tentang mengetahui jumlah objek yang ditemukan. Mari kita coba untuk menyederhanakan halaman pencarian:


Pada kenyataannya, hanya fakta bahwa tidak ada cara untuk pergi ke nomor halaman tertentu telah berubah, dan sekarang tabel ini tidak perlu tahu berapa banyak dari mereka dapat ditampilkan. Tetapi muncul pertanyaan - bagaimana tabel mengetahui jika ada data untuk halaman berikutnya (untuk menampilkan tautan "Next" dengan benar)?

Jawabannya sangat sederhana: Anda dapat mengurangi dari database satu catatan lebih dari yang Anda perlu tampilkan, dan kehadiran catatan "tambahan" ini akan menunjukkan apakah ada bagian berikutnya. Jadi, untuk mendapatkan satu halaman data, Anda hanya perlu menyelesaikan satu permintaan, yang secara signifikan meningkatkan kinerja dan membuatnya lebih mudah untuk mendukung fungsi ini. Dalam praktik saya, ada kasus ketika menolak untuk menghitung jumlah total rekaman yang mempercepat output hasil sebanyak 4-5 kali.

Untuk pendekatan ini, ada beberapa opsi untuk antarmuka pengguna: perintah "back" dan "forward", seperti dalam contoh di atas, tombol "load more", yang hanya menambahkan bagian baru ke hasil yang ditampilkan, "scrolling tak terbatas", yang bekerja pada prinsip "load more" ", Tetapi sinyal untuk mendapatkan bagian selanjutnya adalah pengguna untuk menggulir semua hasil yang ditampilkan hingga akhir. Apa pun solusi visualnya, prinsip pengambilan sampel data tetap sama.

Nuansa penerapan paging


Dalam semua contoh kueri di atas, pendekatan "offset + angka" digunakan, ketika kueri itu sendiri menunjukkan urutan baris hasil dan berapa banyak baris yang harus dikembalikan. Pertama, pertimbangkan cara terbaik untuk mengatur transfer parameter dalam kasus ini. Dalam praktiknya, saya bertemu beberapa cara:

  • Nomor seri halaman yang diminta (pageIndex), ukuran halaman (pageSize).
  • Nomor seri catatan pertama yang akan dikembalikan (startIndex), jumlah maksimum catatan sebagai hasil (hitungan).
  • Nomor seri catatan pertama yang akan dikembalikan (startIndex), nomor seri catatan terakhir yang akan dikembalikan (endIndex).

Pada pandangan pertama, mungkin terlihat bahwa ini sangat mendasar sehingga tidak ada perbedaan. Tapi ini tidak begitu - opsi yang paling nyaman dan universal adalah yang kedua (startIndex, count). Ada beberapa alasan untuk ini:

  • +1 , , pageIndex pageSize . , 50 . , , . «+1» , , 1 51, — 51 101 .. 51 pageIndex, 52 102 .. , — «» , .
  • Opsi ketiga tidak masuk akal sama sekali, karena untuk mengeksekusi query di sebagian besar database, Anda masih perlu mentransfer kuantitas, bukan indeks dari catatan terakhir. Biarkan pengurangan startIndex dari endIndex dan operasi aritmatika dasar, tetapi berlebihan di sini.

Sekarang kita harus menggambarkan kekurangan implementasi paging melalui "offset + kuantitas":

  • Mendapatkan setiap halaman berikutnya akan lebih mahal dan lebih lambat dari yang sebelumnya, karena basis data masih harus melalui semua catatan "dari awal" sesuai dengan kriteria pencarian dan urutkan, dan kemudian berhenti pada fragmen yang diinginkan.
  • Tidak semua DBMS dapat mendukung pendekatan ini.

Ada beberapa alternatif, tetapi mereka juga tidak sempurna. Yang pertama dari pendekatan ini disebut "paging keyset" atau "metode pencarian" dan terdiri dari yang berikut: setelah menerima bagian, Anda bisa mengingat nilai-nilai bidang dalam catatan terakhir pada halaman, dan kemudian menggunakannya untuk mendapatkan bagian berikutnya. Misalnya, kami melakukan permintaan berikut:

SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Dan dalam catatan terakhir kami mendapat nilai tanggal pesanan '2014-06-29'. Kemudian, untuk mendapatkan halaman berikutnya, Anda dapat 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 bahwa OrderDate adalah bidang yang tidak unik, dan kondisi yang disebutkan di atas kemungkinan akan melewati banyak baris yang diperlukan. Untuk membuat permintaan ini tidak ambigu, Anda perlu menambahkan bidang unik ke kondisi (misalkan 75074 adalah nilai terakhir dari 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 bekerja dengan benar, tetapi dalam kasus umum akan sulit untuk mengoptimalkan, karena kondisinya mengandung operator OR. Jika nilai kunci utama tumbuh dengan pertumbuhan OrderDate, maka kondisinya dapat disederhanakan dengan hanya menyaring filter oleh SalesOrderID. Tetapi jika tidak ada korelasi ketat antara nilai-nilai kunci primer dan bidang di mana hasilnya diurutkan - di sebagian besar DBMSs ini OR tidak dapat dihindari. Pengecualian yang saya ketahui adalah PostgreSQL, di mana perbandingan tuple didukung sepenuhnya, dan kondisi di atas dapat dituliskan sebagai “WHERE (OrderDate, SalesOrderID) <('2014-06-29', 75074). Jika Anda memiliki kunci komposit dengan dua bidang ini, permintaan serupa harus cukup mudah.

Pendekatan alternatif kedua dapat ditemukan, misalnya, di API gulir ElasticSearch atauCosmos DB - saat kueri di samping data mengembalikan pengenal khusus yang dengannya Anda bisa mendapatkan kumpulan data berikutnya. Jika pengenal ini memiliki masa pakai tak terbatas (seperti pada Comsos DB), maka ini adalah cara yang bagus untuk menerapkan paging dengan transisi berurutan antar halaman (opsi # 2 yang disebutkan di atas). Kerugian yang mungkin terjadi: tidak semua DBMS didukung; pengidentifikasi batch yang diterima berikutnya mungkin memiliki masa hidup terbatas, yang umumnya tidak cocok untuk menerapkan interaksi pengguna (seperti API gulir ElasticSearch).

Penyaringan kompleks


Kami memperumit tugas lebih lanjut. Misalkan ada persyaratan untuk mengimplementasikan apa yang disebut pencarian segi, yang akrab bagi semua orang dari toko online. Contoh di atas berdasarkan tabel pesanan tidak terlalu indikatif dalam kasus ini, jadi kami akan beralih ke tabel Produk dari database AdventureWorks:


Apa gagasan pencarian segi? Dalam hal itu, untuk setiap elemen filter, jumlah catatan yang cocok dengan kriteria ini ditampilkan dengan mempertimbangkan filter yang dipilih di semua kategori lainnya .

Misalnya, jika kita memilih kategori Sepeda dan warna Hitam dalam contoh ini, tabel hanya akan menampilkan sepeda hitam, tetapi pada saat yang sama:

  • Untuk setiap kriteria grup "Kategori", jumlah produk dari kategori ini dalam warna hitam akan ditampilkan.
  • Untuk setiap kriteria kelompok Warna, jumlah sepeda warna itu akan ditampilkan.

Berikut adalah contoh keluaran hasil untuk kondisi seperti ini:


Jika selain menandai kategori "Pakaian", meja juga akan menampilkan 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 akan berubah ... Saya harap contoh ini cukup untuk memahami algoritme pencarian segi yang sudah dikenal.

Sekarang bayangkan bagaimana ini dapat diimplementasikan pada basis relasional. Setiap kelompok kriteria, seperti Kategori dan Warna, akan memerlukan permintaan 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 keputusan ini? Sangat sederhana - skalanya tidak baik. Setiap bagian filter memerlukan kueri terpisah untuk menghitung jumlah, dan kueri ini bukan yang termudah. Di toko online, di beberapa bagian, mungkin ada beberapa lusin bagian dari filter, yang dapat menjadi masalah serius untuk kinerja.

Biasanya, setelah pernyataan ini, mereka menawarkan saya beberapa solusi, yaitu:

  • Gabungkan semua jumlah kuantitas menjadi satu permintaan. Secara teknis, ini dimungkinkan menggunakan kata kunci UNION, hanya saja ini tidak akan banyak membantu dalam kinerja - bagaimanapun, database harus mengeksekusi masing-masing fragmen dari awal.
  • . , . , . , 10 «», 5 . «» , -. 9- , , . 50 , , 250. , . , 5-10 . , , - , , ( ).

Untungnya, tugas semacam itu telah lama memiliki solusi yang cukup efektif yang dapat diprediksi bekerja pada sejumlah besar data. Untuk salah satu opsi ini, masuk akal untuk membagi perhitungan ulang faset dan membuat halaman hasil menjadi dua panggilan paralel ke server dan mengatur antarmuka pengguna sedemikian rupa sehingga memuat data pada aspek “tidak mengganggu” dengan tampilan hasil pencarian.

  • «» . , , , , — «1425 , ?» , «». «». , , . -. , , .
  • search engine , Solr, ElasticSearch, Sphinx . «» . , , — . , search engine , : , , ; search engine . — . « ». «» , , . , - transactional outbox .


  1. — , . «» «» — , :
    • — .
    • , , , . - — .
  2. , — #2.
  3. faceted search, :
    • .
    • search engine Solr, ElasticSearch, Sphinx . , , .
  4. faceted search . , , .
  5. SQL , , , ( «» ). , — «». , .

All Articles