PostgreSQL Antipatterns: Kisah Penyempurnaan Iteratif Pencarian berdasarkan Nama, atau "Mengoptimalkan Bolak-balik"

Ribuan manajer dari kantor penjualan di seluruh negeri mencatat sistem CRM kami puluhan ribu kontak setiap hari — fakta komunikasi dengan klien potensial atau yang sudah ada. Dan untuk ini, Anda harus terlebih dahulu menemukan klien, dan sebaiknya dengan sangat cepat. Dan ini paling sering terjadi berdasarkan nama.

Oleh karena itu, tidak mengherankan bahwa, sekali lagi menganalisis kueri "berat" di salah satu database yang paling banyak dimuat - database kami sendiri Akun perusahaan VLSI, saya menemukan "di atas" meminta pencarian "cepat" berdasarkan nama untuk kartu organisasi.

Selain itu, penyelidikan lebih lanjut mengungkapkan sebuah contoh menarik optimasi pertama dan kemudian penurunan kinerja permintaan dengan penyempurnaan berurutan oleh beberapa tim, yang masing-masing bertindak semata-mata dengan niat terbaik.

0: apa yang diinginkan pengguna?

[KDPV karenanya]

Apa yang biasanya dimaksud pengguna ketika mereka berbicara tentang pencarian “cepat” berdasarkan nama? Ini hampir tidak pernah menjadi pencarian yang "jujur" untuk substring sejenisnya ... LIKE '%роза%' - karena hasilnya tidak hanya mencakup 'Розалия' и 'Магазин Роза'tapi 'Гроза' dan bahkan 'Дом Деда Мороза'.

Pengguna berasumsi pada tingkat sehari-hari bahwa Anda akan memberinya cari berdasarkan awal kata dalam judul dan membuatnya lebih relevan dimulai dengan masuk. Dan Anda akan melakukannya hampir seketika - untuk masukan interlinear.

1: batasi tugas

Dan terlebih lagi, seseorang tidak akan masuk secara spesifik 'роз магаз', sehingga Anda harus mencari setiap kata berdasarkan awalan. Tidak, jauh lebih mudah bagi pengguna untuk menanggapi petunjuk singkat untuk kata terakhir daripada dengan sengaja “meremehkan” petunjuk sebelumnya - lihat bagaimana mesin pencari menangani hal ini.

Umumnya, benar merumuskan persyaratan untuk masalah tersebut lebih dari separuh solusi. Terkadang analisis kasus penggunaan yang cermat dapat mempengaruhi hasilnya secara signifikan.

Apa yang dilakukan pengembang abstrak?

1.0: mesin pencari eksternal

Oh, pencarian itu sulit, saya tidak ingin melakukan apa pun - ayo serahkan ke pengembang! Biarkan mereka menerapkan mesin pencari di luar database: Sphinx, ElasticSearch,...

Opsi yang berfungsi, meskipun padat karya dalam hal sinkronisasi dan kecepatan perubahan. Namun tidak dalam kasus kami, karena pencarian dilakukan untuk setiap klien hanya dalam kerangka data akunnya. Dan datanya memiliki variabilitas yang cukup tinggi - dan jika manajer kini telah memasukkan kartunya 'Магазин Роза', kemudian setelah 5-10 detik dia mungkin sudah ingat bahwa dia lupa menunjukkan emailnya di sana dan ingin mencarinya serta memperbaikinya.

Oleh karena itu - ayo cari “langsung di database”. Untungnya, PostgreSQL memungkinkan kita melakukan ini, dan bukan hanya satu opsi - kita akan melihatnya.

1.1: substring "jujur".

Kami berpegang teguh pada kata “substring”. Tapi untuk pencarian indeks berdasarkan substring (dan bahkan dengan ekspresi reguler!) ada yang bagus modul pg_trgm! Hanya dengan demikian perlu dilakukan pengurutan dengan benar.

Mari kita coba mengambil pelat berikut untuk menyederhanakan modelnya:

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

Kami mengunggah 7.8 juta catatan organisasi nyata di sana dan mengindeksnya:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

Mari kita cari 10 record pertama untuk pencarian interlinear:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;

[lihat penjelasan.tensor.ru]

Nah, seperti ... 26 md, 31 MB membaca data dan lebih dari 1.7 ribu catatan yang difilter - untuk 10 catatan yang dicari. Biaya overhead terlalu tinggi, bukankah ada yang lebih efisien?

1.2: mencari berdasarkan teks? Itu FTS!

Memang, PostgreSQL menyediakan solusi yang sangat kuat mesin pencari teks lengkap (Pencarian Teks Lengkap), termasuk kemampuan untuk pencarian awalan. Pilihan yang bagus, Anda bahkan tidak perlu memasang ekstensi! Mari mencoba:

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;

[lihat penjelasan.tensor.ru]

Di sini paralelisasi eksekusi kueri sedikit membantu kami, memotong separuh waktu 11 md. Dan kami harus membaca 1.5 kali lebih sedikit - secara total 20MB. Namun di sini, semakin sedikit, semakin baik, karena semakin besar volume yang kita baca, semakin tinggi kemungkinan terjadinya cache miss, dan setiap halaman tambahan data yang dibaca dari disk berpotensi menjadi “rem” untuk permintaan tersebut.

1.3: masih SUKA?

Permintaan sebelumnya baik untuk semua orang, tetapi hanya jika Anda menariknya seratus ribu kali sehari, permintaan itu akan datang 2TB membaca data. Paling-paling, dari memori, tetapi jika Anda kurang beruntung, maka dari disk. Jadi mari kita coba membuatnya lebih kecil.

Mari kita ingat apa yang ingin dilihat pengguna pertama "yang dimulai dengan...". Jadi ini dalam bentuknya yang paling murni pencarian awalan melalui text_pattern_ops! Dan hanya jika kita “tidak memiliki cukup” hingga 10 catatan yang kita cari, maka kita harus menyelesaikan membacanya menggunakan pencarian FTS:

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
LIMIT 10;

[lihat penjelasan.tensor.ru]

Performa luar biasa - total 0.05ms dan sedikit lebih dari 100KB membaca! Hanya saja kami lupa diurutkan berdasarkan namaagar pengguna tidak tersesat dalam hasilnya:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[lihat penjelasan.tensor.ru]

Oh, ada sesuatu yang tidak begitu indah lagi - sepertinya ada indeks, tetapi penyortiran melewatinya... Tentu saja, ini sudah berkali-kali lebih efektif daripada opsi sebelumnya, tapi...

1.4: “selesaikan dengan file”

Namun ada indeks yang memungkinkan Anda mencari berdasarkan rentang dan tetap menggunakan penyortiran secara normal - pohon biasa!

CREATE INDEX ON firms(lower(name));

Hanya permintaannya yang harus “dikumpulkan secara manual”:

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'роза' AND
  lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[lihat penjelasan.tensor.ru]

Luar biasa - penyortiran berfungsi, dan konsumsi sumber daya tetap “mikroskopis”, ribuan kali lebih efektif daripada FTS “murni”.! Yang tersisa hanyalah menggabungkannya menjadi satu permintaan:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'роза' AND
    lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
    lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
  ORDER BY
    lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

Perhatikan bahwa subkueri kedua dijalankan hanya jika yang pertama menghasilkan kurang dari yang diharapkan terakhir LIMIT jumlah baris. Saya sedang berbicara tentang metode optimasi kueri ini sudah menulis sebelumnya.

Jadi ya, sekarang kami memiliki btree dan gin, tetapi secara statistik ternyata demikian kurang dari 10% permintaan mencapai eksekusi blok kedua. Artinya, dengan batasan umum yang diketahui sebelumnya untuk tugas tersebut, kami dapat mengurangi total konsumsi sumber daya server hampir seribu kali lipat!

1.5*: kita dapat melakukannya tanpa file

Di atas LIKE Kami dicegah menggunakan penyortiran yang salah. Namun hal ini dapat “diatur pada jalur yang benar” dengan menentukan operator USING:

Secara default diasumsikan ASC. Selain itu, Anda dapat menentukan nama operator pengurutan tertentu dalam sebuah klausa USING. Operator pengurutan harus merupakan anggota dari beberapa keluarga operator B-tree yang kurang dari atau lebih besar darinya. ASC biasanya setara USING < и DESC biasanya setara USING >.

Dalam kasus kami, “kurang” adalah ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[lihat penjelasan.tensor.ru]

2: bagaimana permintaan menjadi buruk

Sekarang kami meninggalkan permintaan kami untuk "mendidih" selama enam bulan atau satu tahun, dan kami terkejut menemukannya lagi "di atas" dengan indikator total "pemompaan" memori harian (buffer berbagi hit) di 5.5TB - yaitu, bahkan lebih dari aslinya.

Tidak, tentu saja, bisnis kami telah berkembang dan beban kerja kami meningkat, tetapi tidak dalam jumlah yang sama! Ini berarti ada sesuatu yang mencurigakan di sini - mari kita cari tahu.

2.1: lahirnya paging

Pada titik tertentu, tim pengembangan lain ingin memungkinkan untuk “melompat” dari pencarian subskrip cepat ke registri dengan hasil yang sama namun diperluas. Apa itu registri tanpa navigasi halaman? Mari kita mengacaukannya!

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

Sekarang dimungkinkan untuk menampilkan registri hasil pencarian dengan pemuatan "halaman demi halaman" tanpa tekanan apa pun bagi pengembang.

Tentu saja, pada kenyataannya, untuk setiap halaman data berikutnya semakin banyak yang dibaca (semua dari waktu sebelumnya, yang akan kita buang, ditambah “ekor” yang diperlukan) - yaitu, ini adalah antipola yang jelas. Tetapi akan lebih tepat untuk memulai pencarian pada iterasi berikutnya dari kunci yang disimpan di antarmuka, tetapi tentang itu di lain waktu.

2.2: Saya ingin sesuatu yang eksotis

Suatu saat pengembang menginginkannya mendiversifikasi sampel yang dihasilkan dengan data dari tabel lain, yang seluruh permintaan sebelumnya dikirim ke CTE:

WITH q AS (
  ...
  LIMIT <N> + 10
)
SELECT
  *
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
  q
LIMIT 10 OFFSET <N>;

Meski begitu, itu lumayan, karena subkueri hanya dievaluasi untuk 10 record yang dikembalikan, jika tidak ...

2.3: DISTINCT tidak masuk akal dan tanpa ampun

Di suatu tempat dalam proses evolusi dari subkueri ke-2 hilang NOT LIKE kondisi. Yang jelas setelah ini UNION ALL mulai kembali beberapa entri dua kali - pertama kali ditemukan di awal baris, dan kemudian lagi - di awal kata pertama baris ini. Pada batasnya, semua rekaman subkueri ke-2 bisa cocok dengan rekaman subkueri pertama.

Apa yang dilakukan pengembang alih-alih mencari penyebabnya?.. Tidak ada pertanyaan!

• dua kali lipat ukurannya sampel asli
• terapkan BERBEDAuntuk mendapatkan hanya satu contoh dari setiap baris

WITH q AS (
  ( ... LIMIT <2 * N> + 10)
  UNION ALL
  ( ... LIMIT <2 * N> + 10)
  LIMIT <2 * N> + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET <N>;

Artinya, jelas bahwa hasilnya pada akhirnya sama persis, tetapi peluang untuk "terbang" ke subkueri CTE ke-2 menjadi jauh lebih tinggi, dan bahkan tanpa ini, jelas lebih mudah dibaca.

Tapi ini bukanlah hal yang paling menyedihkan. Karena pengembang diminta untuk memilih DISTINCT bukan untuk yang spesifik, tapi untuk semua bidang sekaligus catatan, maka bidang sub_query — hasil dari subquery — secara otomatis disertakan di sana. Sekarang, untuk mengeksekusi DISTINCT, database sudah harus dijalankan bukan 10 subquery, tapi semuanya <2 * N> + 10!

2.4: kerja sama di atas segalanya!

Jadi, para pengembang terus hidup - mereka tidak repot, karena pengguna jelas tidak memiliki cukup kesabaran untuk "menyesuaikan" registri ke nilai N yang signifikan dengan perlambatan kronis dalam menerima setiap "halaman" berikutnya.

Hingga pengembang dari departemen lain mendatangi mereka dan ingin menggunakan metode yang nyaman tersebut untuk pencarian berulang - yaitu, kita mengambil bagian dari beberapa sampel, memfilternya berdasarkan kondisi tambahan, menggambar hasilnya, lalu bagian berikutnya (yang dalam kasus kita dicapai dengan menambah N), dan seterusnya hingga kita memenuhi layar.

Pada umumnya pada spesimen yang tertangkap N mencapai nilai hampir 17K, dan hanya dalam satu hari setidaknya 4K permintaan tersebut dieksekusi “sepanjang rantai”. Yang terakhir dipindai dengan berani Memori 1GB per iterasi...

Total

Sumber: www.habr.com