PolarDB：Pengenalan optimizer kueri

Gambar berikut menunjukkan proses eksekusi setelah menerima pernyataan Structured Query Language (SQL).

1. Parser sintaksis mem-parsing teks SQL menjadi pohon sintaksis abstrak (AST).
2. Pohon sintaksis diubah menjadi rencana logis berbasis aljabar relasional.
3. Optimizer mengoptimalkan rencana logis untuk menghasilkan rencana fisik.
4. Eksekutor menjalankan rencana ini untuk mengambil hasil kueri dan mengembalikan hasil kueri ke klien.

Bagian ini menjelaskan cara kerja optimizer kueri, mencakup aspek-aspek berikut:

• Operator aljabar relasional
• Penulisan ulang SQL (fase Rule-Based Optimizer (RBO))
• Enumerasi rencana kueri (fase Cost-Based Optimizer (CBO))

Operator aljabar relasional

Dalam sistem database, kueri SQL biasanya direpresentasikan sebagai pohon yang terdiri dari operator aljabar relasional. Operator dalam skenario berikut tersedia:

• Project: digunakan untuk menggambarkan kolom SELECT dalam SQL, termasuk komputasi fungsi.
• Filter: digunakan untuk menggambarkan kondisi WHERE dalam SQL.
• JOIN: digunakan untuk menggambarkan JOIN dalam SQL. Operator fisik yang sesuai adalah HashJoin, BKAJoin, Nested-Loop Join, dan SortMergeJoin.
• Agg: digunakan untuk menggambarkan Group By dan fungsi agregat dalam SQL. Operator fisik yang sesuai adalah HashAgg dan SortAgg.
• Sort: digunakan untuk menggambarkan Order By dan Limit dalam SQL. Operator fisik yang sesuai adalah TopN dan MemSort.
• LogicalView: digunakan untuk menggambarkan PolarDB-X 1.0 pernyataan SQL yang dikirim ke lapisan penyimpanan MySQL. Pernyataan SQL tersebut dapat mencakup satu atau lebih operator logis.
• Gather: merepresentasikan operasi yang mengumpulkan data dari beberapa aliran data. Operator Gather ini biasanya muncul di atas LogicalView. Jika eksekusi paralel diaktifkan, operator Gather ditarik ke atas pada langkah optimasi paralel.

Pernyataan SQL kueri berikut digunakan sebagai contoh. Pernyataan ini diperoleh dengan memodifikasi TPC-H Query 3.

SELECT l_orderkey, sum(l_extendedprice *(1 - l_discount)) AS revenue
FROM CUSTOMER, ORDERS, LINEITEM
WHERE c_mktsegment = 'AUTOMOBILE'
  and c_custkey = o_custkey
  and l_orderkey = o_orderkey
  and o_orderdate < '1995-03-13'
  and l_shipdate > '1995-03-13'
GROUP BY l_orderkey;

Jalankan perintah EXPLAIN berikut untuk melihat PolarDB-X 1.0 rencana eksekusi:

HashAgg(group="l_orderkey", revenue="SUM(*)")
  HashJoin(condition="o_custkey = c_custkey", type="inner")
    Gather(concurrent=true)
      LogicalView(tables="ORDERS_[0-7],LINEITEM_[0-7]", shardCount=8, sql="SELECT `ORDERS`.`o_custkey`, `LINEITEM`.`l_orderkey`, (`LINEITEM`.`l_extendedprice` * (? - `LINEITEM`.`l_discount`)) AS `x` FROM `ORDERS` AS `ORDERS` INNER JOIN `LINEITEM` AS `LINEITEM` ON (((`ORDERS`.`o_orderkey` = `LINEITEM`.`l_orderkey`) AND (`ORDERS`.`o_orderdate` < ?)) AND (`LINEITEM`.`l_shipdate` > ?))")
    Gather(concurrent=true)
      LogicalView(tables="CUSTOMER_[0-7]", shardCount=8, sql="SELECT `c_custkey` FROM `CUSTOMER` AS `CUSTOMER` WHERE (`c_mktsegment` = ?)")

Bagan treemap berikut mengilustrasikan rencana eksekusi.

Penulisan ulang SQL (RBO)

Dalam fase penulisan ulang SQL, inputnya adalah rencana eksekusi logis dan outputnya adalah rencana eksekusi logis. Pada langkah ini, beberapa aturan heuristik utamanya diterapkan dan RBO digunakan. Oleh karena itu, langkah ini sering disebut sebagai fase RBO.

Langkah penulisan ulang SQL memiliki fitur utama berikut:

• Unnesting subquery

  Unnesting subquery adalah untuk menyatakan subquery terkait yang berisi item terkait sebagai SemiJoin atau operator serupa. Ini memfasilitasi berbagai optimasi selanjutnya, seperti mendorong ke lapisan penyimpanan MySQL atau PolarDB-X 1.0 memilih algoritma untuk eksekusi di lapisan. Dalam contoh berikut, subquery IN diubah menjadi operator SemiJoin dan akhirnya diubah menjadi operator SemiHashJoin fisik yang PolarDB-X 1.0 dieksekusi oleh.

  > explain  select id from t1 where id in (select id from t2 where t2.name = 'hello');
  SemiHashJoin(condition="id = id", type="semi")
    Gather(concurrent=true)
      LogicalView(tables="t1", shardCount=2, sql="SELECT `id` FROM `t1` AS `t1`")
    Gather(concurrent=true)
      LogicalView(tables="t2_[0-3]", shardCount=4, sql="SELECT `id` FROM `t2` AS `t2` WHERE (`name` = ?)")

• Pendorongan operator

  Pendorongan operator adalah langkah penting.PolarDB-X 1.0 memiliki aturan optimasi bawaan berikut untuk pendorongan operator.

  Aturan optimasi	Deskripsi
  Pendorongan predikat atau pemangkasan kolom	Dorong operator Filter dan Project ke lapisan penyimpanan MySQL untuk eksekusi dan saring baris dan kolom yang tidak diperlukan.
  Pengelompokan JOIN	Urutkan ulang dan kelompokkan operasi JOIN menggunakan metode sharding dan berdasarkan kondisi kesetaraan kunci shard. Ini memfasilitasi pendorongan operasi JOIN selanjutnya.
  Pendorongan JOIN	Dorong operasi JOIN yang memenuhi syarat ke lapisan penyimpanan MySQL untuk eksekusi.
  Pendorongan Agg	Pisahkan operasi Agg menjadi dua fase FinalAgg dan LocalAgg dan dorong LocalAgg ke lapisan penyimpanan MySQL.
  Pendorongan Sort	Pisahkan operasi Sort menjadi dua fase MergeSort dan LocalSort dan dorong LocalSort ke lapisan penyimpanan MySQL.

  Untuk informasi lebih lanjut tentang pendorongan kueri, lihat Penulisan ulang SQL dan pendorongan.

Enumerasi rencana kueri (CBO)

Rencana eksekusi logis yang dihasilkan dalam fase penulisan ulang SQL digunakan sebagai input Plan Enumerator. Kemudian, Plan Enumerator menghasilkan rencana eksekusi fisik akhir. Plan Enumerator memilih rencana kueri yang memiliki biaya minimum dari beberapa rencana kueri yang layak dengan menggunakan model biaya yang telah ditentukan. Berbeda dengan fase penulisan ulang SQL, dalam Plan Enumerator, rencana eksekusi yang lebih baik atau lebih buruk dapat dihasilkan berdasarkan aturan. Rencana eksekusi yang lebih baik dipilih berdasarkan hasil perbandingan biaya. Oleh karena itu, Plan Enumerator juga disebut CBO.

Komponen inti CBO memiliki bagian-bagian berikut:

• Statistik
• Estimasi kardinalitas
• Aturan transformasi
• Model biaya
• Mesin pencari ruang rencana

Proses CBO terdiri dari langkah-langkah berikut secara logis:

1. Mesin pencari mengonversi rencana eksekusi logis masukan dengan menggunakan aturan transformasi untuk membangun ruang pencarian untuk rencana eksekusi fisik.
2. Kemudian, model biaya digunakan untuk memperkirakan biaya setiap rencana eksekusi dalam ruang pencarian untuk memilih rencana eksekusi fisik yang memiliki biaya minimum.
3. Proses estimasi biaya tidak dapat dipisahkan dari estimasi kardinalitas. Dalam estimasi kardinalitas, informasi tentang setiap operator, seperti jumlah baris masukan dan laju seleksi, diperkirakan berdasarkan statistik setiap tabel dan setiap kolom. Kemudian, informasi yang diperkirakan disediakan ke model biaya operator untuk memperkirakan biaya rencana kueri.