Masalah
Catatan: Saya merujuk pada urutan matematis , bukan mekanisme urutan PostgreSQL .
Saya punya tabel yang mewakili urutan bilangan bulat. Definisi tersebut adalah:
CREATE TABLE sequences
(
id serial NOT NULL,
title character varying(255) NOT NULL,
date date NOT NULL,
sequence integer[] NOT NULL,
CONSTRAINT "PRIM_KEY_SEQUENCES" PRIMARY KEY (id)
);
Tujuan saya adalah menemukan baris menggunakan urutan yang diberikan. Dengan kata lain, baris di mana sequence
bidang adalah urutan yang berisi urutan yang diberikan (dalam kasus saya, urutan tersebut dipesan).
Contoh
Misalkan tabel tersebut berisi data berikut:
+----+-------+------------+-------------------------------+
| id | title | date | sequence |
+----+-------+------------+-------------------------------+
| 1 | BG703 | 2004-12-24 | {1,3,17,25,377,424,242,1234} |
| 2 | BG256 | 2005-05-11 | {5,7,12,742,225,547,2142,223} |
| 3 | BD404 | 2004-10-13 | {3,4,12,5698,526} |
| 4 | BK956 | 2004-08-17 | {12,4,3,17,25,377,456,25} |
+----+-------+------------+-------------------------------+
Jadi jika yang diberikan berikutnya adalah {12, 742, 225, 547}
, saya ingin mencari baris 2.
Demikian pula, jika urutan yang diberikan adalah {3, 17, 25, 377}
, saya ingin mencari baris 1 dan baris 4.
Akhirnya, jika urutan yang diberikan adalah {12, 4, 3, 25, 377}
, maka tidak ada baris yang dikembalikan.
Investigasi
Pertama, saya tidak sepenuhnya yakin bahwa merepresentasikan urutan dengan tipe data array adalah bijaksana. Meskipun ini sepertinya sesuai dengan situasi; Saya khawatir itu membuat penanganan lebih rumit. Mungkin lebih baik untuk mewakili urutan berbeda, menggunakan model hubungan dengan tabel lain.
Dengan cara yang sama, saya berpikir tentang memperluas urutan menggunakan unnest
fungsi array dan kemudian menambahkan kriteria pencarian saya. Namun demikian, jumlah istilah dalam urutan menjadi variabel I tidak melihat bagaimana melakukan itu.
Saya tahu juga mungkin untuk memotong urutan saya di kemudian hari menggunakan subarray
fungsi modul intarray tapi saya tidak melihat bagaimana itu menguntungkan saya untuk pencarian saya.
Kendala
Bahkan jika saat ini model saya masih dikembangkan, tabel ini dimaksudkan untuk terdiri dari banyak urutan, antara 50.000 dan 300.000 baris. Jadi saya punya kendala kinerja yang kuat.
Dalam contoh saya, saya menggunakan bilangan bulat yang relatif kecil. Dalam praktiknya, dimungkinkan bahwa bilangan bulat ini menjadi jauh lebih besar, hingga meluap bigint
. Dalam situasi seperti itu, saya pikir yang terbaik adalah menyimpan angka sebagai string (karena tidak perlu melakukan urutan operasi matematika ini). Namun, memilih solusi ini, ini membuat tidak mungkin untuk menggunakan modul intarray , yang disebutkan di atas.
bigint
Anda harus menggunakannumeric
sebagai tipe untuk menyimpannya. Ini jauh lebih lambat dan membutuhkan lebih banyak ruang.numeric
dan bukan string (text
misalnya)? Saya tidak perlu melakukan operasi matematika pada urutan saya.text
, dan mencegah Anda menyimpan data non-numerik palsu. Tergantung, jika Anda hanya melakukan I / O, Anda mungkin ingin teks mengurangi pemrosesan I / O.SELECT ARRAY[12, 4, 3, 17, 25, 377, 456, 25] @> ARRAY[12, 4, 3, 25, 377];
akan mengembalikan true, karena pesanan tidak dipertimbangkan oleh operator ini.Jawaban:
Jika Anda mencari peningkatan kinerja yang signifikan untuk jawaban dnoeth , pertimbangkan untuk menggunakan fungsi C asli dan membuat operator yang sesuai.
Berikut adalah contoh untuk array int4. ( Varian array generik dan skrip SQL yang sesuai ).
Sekarang Anda dapat memfilter baris seperti ini.
Saya telah melakukan percobaan kecil untuk menemukan seberapa cepat solusi ini.
Jadi, ini sekitar 16 kali lebih cepat. Jika itu tidak cukup, Anda dapat menambahkan dukungan untuk indeks GIN atau GiST, tetapi ini akan menjadi tugas yang jauh lebih sulit.
sumber
numeric
untuk mewakili data saya karena mungkin meluapbigint
. Mungkin sebaiknya mengedit jawaban Anda agar sesuai dengan batasan-batasan pertanyaan. Bagaimanapun, saya akan melakukan kinerja komparatif yang akan saya posting di sini.numeric
dantext
dan peningkatan berkisar antara 20 hingga 50 kali tergantung pada panjang array.numeric
.bigint
.bigint
, jadi sepertinya saya tidak punya pilihan. Tetapi jika Anda punya ide, saya tertarik :).Anda dapat dengan mudah menemukan bagian berikutnya ketika Anda melemparkan array ke string dan mengganti tanda kurung keriting dengan koma:
Lakukan hal yang sama untuk array yang Anda cari dan tambahkan yang memimpin dan mengikuti
%
:Sekarang Anda membandingkannya menggunakan
LIKE
:Edit:
Fiddle bekerja lagi.
Jika array dinormalisasi menjadi satu baris per nilai, Anda dapat menerapkan logika berbasis set:
n
harus berurutan, tidak ada duplikat, tidak ada kesenjangan. Sekarang gabung dengan nilai-nilai umum dan manfaatkan fakta bahwa urutannya berurutan :-)Terakhir hitung jumlah baris dengan boneka yang sama dan periksa apakah itu nomor yang benar:
Coba indeks pada urutan (val, id, n).
sumber
TEXT
bidang (varchar
adalah ide yang buruk menurut saya, urutan bisa panjang, karena jumlahnya, sehingga ukurannya agak tidak dapat diprediksi), untuk menghindari pemain; tetapi masih tidak memungkinkan untuk menggunakan indeks untuk meningkatkan kinerja (selanjutnya menggunakan bidang string tampaknya tidak selalu bijaksana, lihat komentar @CraigRinger di atas).25
ada dua kaliid=4
, apakah ini sebenarnya mungkin? Berapa banyak kecocokan yang ada dalam rata-rata / maksimum untuk urutan yang dicari?{1, 1, 1, 1, 12, 2, 2, 12, 12, 1, 1, 5, 4}
sangat mungkin. Mengenai jumlah pertandingan, urutan yang digunakan biasanya dianggap membatasi jumlah hasil. Namun, beberapa urutan sangat mirip, dan kadang-kadang bisa menarik untuk menggunakan urutan yang lebih pendek untuk mendapatkan hasil lebih banyak. Saya memperkirakan bahwa jumlah kecocokan untuk sebagian besar kasus adalah antara 0 dan 100. Dengan selalu ada kemungkinan bahwa kadang-kadang kecocokan berikutnya dengan banyak urutan ketika pendek atau sangat umum.